<p>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.</p>
<p>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 <span class="math-container">$n$</span> is even then <span class="math-container">$n + 1$</span> is its pair. As such you can just iterate through the actual edges by skipping every other edge.</p>
<p>The drawback is that you need to ensure that your edges are indeed stored like that, which can be complex.</p>

CC BY-SA 4.0
2020-09-25T20:17:05.887Z
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)?
Nathan Reed
CC BY-SA 4.0
2020-09-25T21:54:57.620Z
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.
Makogan
CC BY-SA 4.0
2020-09-25T20:08:02.893Z
2020-09-25T20:08:02.893Z
Makogan
<p>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.</p>
<p>The iteration can be done using <a href="https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fclz" rel="nofollow noreferrer"><code>__builtin_clz</code></a> (GCC, clang)  or <a href="https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64?view=vs-2019" rel="nofollow noreferrer"><code>_BitScanReverse</code></a> (MSVC)  [edit: or <a href="https://en.cppreference.com/w/cpp/numeric/countl_zero" rel="nofollow noreferrer"><code>std::countl_zero</code></a> 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.</p>

CC BY-SA 4.0
2020-08-29T23:38:19.167Z
2020-09-03T22:55:47.977Z
2020-09-03T22:55:47.977Z
Nathan Reed
<p>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.</p>
<p>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.)</p>
<pre><code>    for(uint i=0; i &lt; edge_num; i++)
    {
        if(mesh.edges[i].color != BLUE)
        {
            /*Do stuff*/
           mesh.edges[i].color = BLUE;
           mesh.edges[i].pair.color = BLUE;
        }
    }
</code></pre>
<p>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.</p>

CC BY-SA 4.0
2020-08-29T07:54:21.577Z
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
CC BY-SA 4.0
2020-08-29T16:09:53.160Z
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
CC BY-SA 4.0
2020-08-29T21:16:25.140Z
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
CC BY-SA 4.0
2020-08-29T23:41:06.580Z
I highly recommend that you profile your app before trying to optimize it. Did you get this branch as a hotspot or something?
lightxbulb
CC BY-SA 4.0
2020-08-30T00:13:13.563Z
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
CC BY-SA 4.0
2020-08-30T09:45:36.610Z
You can make it a function: then you won't have to code it every time. I don't think you can make it much simpler.
lightxbulb
CC BY-SA 4.0
2020-08-30T17:33:38.140Z
The problem is that the inner body is slightly different every time, so the iteration pattern is teh same but the logic isn;t
Makogan
CC BY-SA 4.0
2020-08-30T17:38:41.773Z
Try a higher level iteration function + a lambda. The lambda will be specialized, the higher level function would perform your custom iteration. But honestly, that's over-engineering, and you shouldn't really have an issue with a simple if statement imo.
lightxbulb
<computational-geometry><geometry><mesh><data-structure>
Smart half edge iteration?
Makogan
# Smart half edge iteration?

(Asked by: username_0 on 2020-08-24)

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.

**Tags:** computational-geometry, geometry, mesh, data-structure

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: I highly recommend that you profile your app before trying to optimize it. Did you get this branch as a hotspot or something?  
> **username_0**: 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  
> **username_1**: You can make it a function: then you won't have to code it every time. I don't think you can make it much simpler.  
> **username_0**: The problem is that the inner body is slightly different every time, so the iteration pattern is teh same but the logic isn;t  
> **username_1**: Try a higher level iteration function + a lambda. The lambda will be specialized, the higher level function would perform your custom iteration. But honestly, that's over-engineering, and you shouldn't really have an issue with a simple if statement imo.  

---

## 2 answers

### Answer by username_0 on 2020-09-25. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_2**: 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)?  
> **username_0**: 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.  

---

### Answer by username_2 on 2020-08-29. Score: 2

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`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fclz) (GCC, clang) or [`_BitScanReverse`](https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64?view=vs-2019) (MSVC) [edit: or [`std::countl_zero`](https://en.cppreference.com/w/cpp/numeric/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.


---

