#StackBounty: #computational-geometry #geometry #mesh #data-structure Smart half edge iteration?

Bounty: 50

In my HE implementation, half edges are stored in an array. When I iterate over the edges, I color all the HE black, and when I do an operation on an edge (e.g edge splitting) I mark both the current half edge and its pair blue. And in the loop I skip blue edges.

This essentially stops me from applying the same operation to an edge twice.
This however requires O(n) additional memory and iterating over every edge twice (once for each of the HE that compose the edge.)

    for(uint i=0; i < edge_num; i++)
        if(mesh.edges[i].color != BLUE)
            /*Do stuff*/
           mesh.edges[i].color = BLUE;
           mesh.edges[i].pair.color = BLUE;

I am wondering if there is a smarter way. In particular, a way that avoids branching. I know I could do something like depth first search or breath first search, but that’s likely to be slower than just skipping over edges.

Get this bounty!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.