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.
if (edge[i].twin_idx < i) do_something();
, this still requires branching however. You cannot remove branching, unless you order your edges at construction so that the first half of the array is made of halfedges on one side, and the second half is made of the other halfedges of the other side. Still, you need branching to order them like so. $\endgroup$