# Smart half edge iteration?

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.

• Make arrays with the black and blue edges, or with pointers to them, then there is no branching but it is likely slower. It's not clear what your goal is from your post. Optimization? You likely won't get this to be faster/simpler without additional details of what your algorithm does. – lightxbulb Aug 29 at 7:54
• Is your issue actually that you want to skip the twin of an edge that you've gone through? You don't even need to mark those. For example apply the operation only to the halfedge with the larger index from the twins: 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. – lightxbulb Aug 29 at 16:09
• I guess You could run the above once to split the HE in the order in which they would get visited. The question is then, how could you enforce that property every time you add an edge. Which I guess you could do If you had 2 independent arrays for the HE... I wonder if that would introduce noticeably more performance drop due to cache misses. – Makogan Aug 29 at 21:16
• I highly recommend that you profile your app before trying to optimize it. Did you get this branch as a hotspot or something? – lightxbulb Aug 29 at 23:41
• Mostly this particular pattern is annoying to code every time and makes guaranteeing correctness ahrder I am trying to make the code easier to replicate without htting performance too much – Makogan Aug 30 at 0:13

The iteration can be done using __builtin_clz (GCC, clang) or _BitScanReverse (MSVC) [edit: or std::countl_zero in C++20!] to efficiently extract the next 1-bit without branching on every bit. Although you do then need a nested pair of loops, where you loop over the fields in your bit array, and then loop extracting bits until the current field is zero.
This sounds abstract but the gist of it is very simple. Since there is an even number of HE by definition, you can store your half edges such that if $$n$$ is even then $$n + 1$$ is its pair. As such you can just iterate through the actual edges by skipping every other edge.