2
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Aug 29, 2020 at 7:54
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Aug 29, 2020 at 16:09
  • $\begingroup$ 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. $\endgroup$
    – Makogan
    Aug 29, 2020 at 21:16
  • $\begingroup$ I highly recommend that you profile your app before trying to optimize it. Did you get this branch as a hotspot or something? $\endgroup$
    – lightxbulb
    Aug 29, 2020 at 23:41
  • $\begingroup$ 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 $\endgroup$
    – Makogan
    Aug 30, 2020 at 0:13

2 Answers 2

Reset to default
2
+50
$\begingroup$

One possibility would be to create a bit array with 1 bit per half-edge. When you start iterating, initialize them all to 1, then clear the bits of each half-edge and its partner as you iterate.

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.

Improve this answer
$\endgroup$
1
$\begingroup$

If anyone ever runs into this. There is a mathematical property of the half edge, that makes it such that any proper half edge can be expressed as an even permutation of vertices.

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.

The drawback is that you need to ensure that your edges are indeed stored like that, which can be complex.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So basically sort the array of half-edges so that pairs are adjacent to each other? What do you do for unpaired half-edges (on the boundary of the mesh)? $\endgroup$
    – Nathan Reed
    Sep 25, 2020 at 20:17
  • 1
    $\begingroup$ Half edges at the boundary should have pairs. however those pairs should have null faces. At minimum in my implementations I have found that not putting half edges at the boundary breaks many many algorithms. Plus if you put half edges at the boundary you can get the closed curve of the boundary through a linear iteration, which is nice. $\endgroup$
    – Makogan
    Sep 25, 2020 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.