Jerry Yin and Jeffrey Goh

Dec. 10, 2019

Dec. 10, 2019

We can represent discrete surfaces as polygon meshes. Polygon meshes can be
thought of as graphs (which have vertices and edges between vertices) plus a
list of *faces*, where a face is a cycle of edges.

Below, we specify a mesh as a list of vertices and a list of faces, where each face is specified as a cycle of vertices. The edges of the mesh are implied—edges connect adjacent vertices of a face.

$\begin{aligned} v_1 &= (1,4) \qquad v_2 = (3,4) \qquad v_3 = (0,2) \qquad v_4 = (2, 2) \\ v_5 &= (4, 2) \qquad v_6 = (1, 0) \qquad v_7 = (3, 0) \end{aligned}$ $V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}$ $F = \{(v_1, v_3, v_4), (v_1, v_4, v_2), (v_2, v_4, v_5), (v_3, v_6, v_4), (v_4, v_6, v_7), (v_4, v_7, v_5)\}$The face-list representation is popular for on-disk storage due to its lack of redundancy, however it is difficult to write algorithms that operate directly on such a representation. For example, to determine whether or not $v_6$ and $v_3$ are connected, we must iterate through the face list until we find (or fail to find) the edge we are looking for.

Visualization of a half-edgeA popular data structure which can answer such queries in constant time is the *half-edge data structure*. In a half-edge data structure, we explicitly store the edges of the mesh by representing each edge with a pair of directed *half-edge twins*, with each of the two half-edges twins pointing in opposite directions. A half-edge stores a reference to its twin, as well as references to the previous and next half-edges along the same face or hole. A vertex stores its position and a reference to an arbitrary half-edge that originates from that vertex, and a face stores an arbitrary half-edge belonging to that face. A half-edge data structure stores arrays of vertex, face, and half-edge records.

For representing boundary edges (edges adjacent to a hole), we have two options. We can either represent boundary edges with a single half-edge whose twin pointer is null, or we can represent boundary edges as a pair of half-edges, with the half-edge adjacent to the hole having a null face pointer. It turns out the latter design choice results in much simpler code, since we will soon see that getting a half-edge’s twin is a far more common operation than getting a half-edge’s face, and being able to simply assume that we have a non-null twin results in far fewer special cases.

Below, we show the half-edge diagram and records table for a more complex mesh. The mesh vertices and connectivity can be edited in the editor.

Vertex | Coordinate | Incident edge |
---|---|---|

v_{1} | (1, 4, 0) | e_{0} |

v_{2} | (3, 4, 0) | e_{5} |

v_{3} | (0, 2, 0) | e_{1} |

v_{4} | (2, 2, 0) | e_{2} |

v_{5} | (4, 2, 0) | e_{8} |

v_{6} | (1, 0, 0) | e_{10} |

v_{7} | (3, 0, 0) | e_{14} |

Face | Half-edge |
---|---|

f_{0} | e_{0} |

f_{1} | e_{3} |

f_{2} | e_{6} |

f_{3} | e_{9} |

f_{4} | e_{12} |

f_{5} | e_{15} |

Half-edge | Origin | Twin | Incident face | Next | Prev |
---|---|---|---|---|---|

e_{0} | v_{1} | e_{18} | f_{0} | e_{1} | e_{2} |

e_{1} | v_{3} | e_{11} | f_{0} | e_{2} | e_{0} |

e_{2} | v_{4} | e_{3} | f_{0} | e_{0} | e_{1} |

e_{3} | v_{1} | e_{2} | f_{1} | e_{4} | e_{5} |

e_{4} | v_{4} | e_{6} | f_{1} | e_{5} | e_{3} |

e_{5} | v_{2} | e_{19} | f_{1} | e_{3} | e_{4} |

e_{6} | v_{2} | e_{4} | f_{2} | e_{7} | e_{8} |

e_{7} | v_{4} | e_{17} | f_{2} | e_{8} | e_{6} |

e_{8} | v_{5} | e_{20} | f_{2} | e_{6} | e_{7} |

e_{9} | v_{3} | e_{21} | f_{3} | e_{10} | e_{11} |

e_{10} | v_{6} | e_{12} | f_{3} | e_{11} | e_{9} |

e_{11} | v_{4} | e_{1} | f_{3} | e_{9} | e_{10} |

e_{12} | v_{4} | e_{10} | f_{4} | e_{13} | e_{14} |

e_{13} | v_{6} | e_{22} | f_{4} | e_{14} | e_{12} |

e_{14} | v_{7} | e_{15} | f_{4} | e_{12} | e_{13} |

e_{15} | v_{4} | e_{14} | f_{5} | e_{16} | e_{17} |

e_{16} | v_{7} | e_{23} | f_{5} | e_{17} | e_{15} |

e_{17} | v_{5} | e_{7} | f_{5} | e_{15} | e_{16} |

e_{18} | v_{3} | e_{0} | ∅ | e_{19} | e_{21} |

e_{19} | v_{1} | e_{5} | ∅ | e_{20} | e_{18} |

e_{20} | v_{2} | e_{8} | ∅ | e_{23} | e_{19} |

e_{21} | v_{6} | e_{9} | ∅ | e_{18} | e_{22} |

e_{22} | v_{7} | e_{13} | ∅ | e_{21} | e_{23} |

e_{23} | v_{5} | e_{16} | ∅ | e_{22} | e_{20} |

Sometimes we need to traverse a face to get all of its vertices or half-edges. For example, if we wish to compute the centroid of a face, we must find the positions of the vertices of that face.

In code, given the face `f`

, this will look something like this:

```
start_he = f.halfedge
he = start_he
do {
# do something useful
he = he.next
} while he != start_he
```

Note that we use a do-while loop instead of a while loop, since we want to check
the condition at the end of the loop iteration. At the start of the first
iteration, `he == start_he`

, so if we checked the condition at the start of the
loop, our loop wouldn’t run for any iterations.

To traverse the face in the opposite direction, one can simply replace `he.next`

with `he.prev`

.

In the last section, we described how to construct a face iterator. Another
useful iterator is the vertex ring iterator. Often, we want to iterate around
the *vertex ring* (also known as a *vertex umbrella*) around a vertex. More
specifically, we want to iterate through all the half-edges with a given vertex
as its origin.

In the next two sections we will assume a counter-clockwise winding order for the faces (which is the default in OpenGL).

In code, given the vertex `v`

, iterating through all the half-edges going out of `v`

in counter-clockwise order looks like this:

```
start_he = v.halfedge
he = start_he
do {
# do something useful
he = he.prev.twin
} while he != start_he
```

Note that our code still works even if there are boundary half-edges or non-triangular faces.

Traversing the vertex ring in clockwise order to very similar to traversing the
ring in counter-clockwise order, except that we replace `he = he.prev.twin`

with `he = he.twin.next`

.

In the previous section, we discussed how to iterate over a face and over a vertex ring. Modifying a half-edge data structure is more tricky, because it can be easy for references to become inconsistent if the records are not modified properly.

Illustration of the EdgeFlip algorithm.

As an exercise, we will walk through how to implement the EdgeFlip algorithm, which, given a half-edge in the middle of two triangle faces, flips the orientation of the half-edge and its twin.

We will show the records table at each step of the algorithm.

We begin with our input half-edge highlighted (either *e _{3}* or

Vertex | Coordinate | Incident edge |
---|---|---|

v_{1} | (0, 1, 0) | e_{0} |

v_{2} | (1, 1, 0) | e_{5} |

v_{3} | (0, 0, 0) | e_{1} |

v_{4} | (1, 0, 0) | e_{2} |

Face | Half-edge |
---|---|

f_{0} | e_{0} |

f_{1} | e_{3} |

Half-edge | Origin | Twin | Incident face | Next | Prev |
---|---|---|---|---|---|

e_{0} | v_{1} | e_{6} | f_{0} | e_{1} | e_{2} |

e_{1} | v_{3} | e_{7} | f_{0} | e_{2} | e_{0} |

e_{2} | v_{4} | e_{3} | f_{0} | e_{0} | e_{1} |

e_{3} | v_{1} | e_{2} | f_{1} | e_{4} | e_{5} |

e_{4} | v_{4} | e_{8} | f_{1} | e_{5} | e_{3} |

e_{5} | v_{2} | e_{9} | f_{1} | e_{3} | e_{4} |

e_{6} | v_{3} | e_{0} | ∅ | e_{9} | e_{7} |

e_{7} | v_{4} | e_{1} | ∅ | e_{6} | e_{8} |

e_{8} | v_{2} | e_{4} | ∅ | e_{7} | e_{9} |

e_{9} | v_{1} | e_{5} | ∅ | e_{8} | e_{6} |

We first get references to all affected half-edges, since traversing the mesh whilst it is in an inconsistent state will be difficult.

```
def FlipEdge(HalfEdge e):
e5 = e.prev
e4 = e.next
twin = e.twin
e1 = twin.prev
e0 = twin.next
```

Next, we make sure there’s no face or vertex references to `e`

or `twin`

(*e _{3}* and

```
for he in {e0, e1, e4, e5}:
he.origin.halfedge = &he
e1.face.halfedge = &e1
e5.face.halfedge = &e5
```

These operations are safe to do since the choice of representative half-edge is arbitrary; the mesh is still in a consistent state. The affected cells are coloured light blue, although not all cells change to values different from their old values.

Vertex | Coordinate | Incident edge |
---|---|---|

v_{1} | (0, 1, 0) | e_{0} |

v_{2} | (1, 1, 0) | e_{5} |

v_{3} | (0, 0, 0) | e_{1} |

v_{4} | (1, 0, 0) | e_{4} |

Face | Half-edge |
---|---|

f_{0} | e_{1} |

f_{1} | e_{5} |

Half-edge | Origin | Twin | Incident face | Next | Prev |
---|---|---|---|---|---|

e_{0} | v_{1} | e_{6} | f_{0} | e_{1} | e_{2} |

e_{1} | v_{3} | e_{7} | f_{0} | e_{2} | e_{0} |

e_{2} | v_{4} | e_{3} | f_{0} | e_{0} | e_{1} |

e_{3} | v_{1} | e_{2} | f_{1} | e_{4} | e_{5} |

e_{4} | v_{4} | e_{8} | f_{1} | e_{5} | e_{3} |

e_{5} | v_{2} | e_{9} | f_{1} | e_{3} | e_{4} |

e_{6} | v_{3} | e_{0} | ∅ | e_{9} | e_{7} |

e_{7} | v_{4} | e_{1} | ∅ | e_{6} | e_{8} |

e_{8} | v_{2} | e_{4} | ∅ | e_{7} | e_{9} |

e_{9} | v_{1} | e_{5} | ∅ | e_{8} | e_{6} |

Next we recycle `e`

and `twin`

. We will (arbitrarily) have `e`

be the top
diagonal half-edge in the diagram, and `twin`

be its twin. We can fill in the
members of `e`

and `twin`

according to the below diagram. After this, our data
structure will become inconsistent. We outline inconsistent cells in red.

```
e.next = &e5
e.prev = &e0
e.origin = e1.origin
e.face = e5.face
twin.next = &e1
twin.prev = &e4
twin.origin = e5.origin
twin.face = e1.face
```

Vertex | Coordinate | Incident edge |
---|---|---|

v_{1} | (0, 1, 0) | e_{0} |

v_{2} | (1, 1, 0) | e_{5} |

v_{3} | (0, 0, 0) | e_{1} |

v_{4} | (1, 0, 0) | e_{4} |

Face | Half-edge |
---|---|

f_{0} | e_{1} |

f_{1} | e_{5} |

Half-edge | Origin | Twin | Incident face | Next | Prev |
---|---|---|---|---|---|

e_{0} | v_{1} | e_{6} | f_{0} | e_{1} | e_{2} |

e_{1} | v_{3} | e_{7} | f_{0} | e_{2} | e_{0} |

e_{2} | v_{2} | e_{3} | f_{0} | e_{1} | e_{4} |

e_{3} | v_{3} | e_{2} | f_{1} | e_{5} | e_{0} |

e_{4} | v_{4} | e_{8} | f_{1} | e_{5} | e_{3} |

e_{5} | v_{2} | e_{9} | f_{1} | e_{3} | e_{4} |

e_{6} | v_{3} | e_{0} | ∅ | e_{9} | e_{7} |

e_{7} | v_{4} | e_{1} | ∅ | e_{6} | e_{8} |

e_{8} | v_{2} | e_{4} | ∅ | e_{7} | e_{9} |

e_{9} | v_{1} | e_{5} | ∅ | e_{8} | e_{6} |

We update affected `next`

and `prev`

references. Again, we can reference the
diagram to fill in these values.

```
e0.next = &e
e1.next = &e4
e4.next = &twin
e5.next = &e0
e0.prev = &e5
e1.prev = &twin
e4.prev = &e1
e5.prev = &e
```

Vertex | Coordinate | Incident edge |
---|---|---|

v_{1} | (0, 1, 0) | e_{0} |

v_{2} | (1, 1, 0) | e_{5} |

v_{3} | (0, 0, 0) | e_{1} |

v_{4} | (1, 0, 0) | e_{4} |

Face | Half-edge |
---|---|

f_{0} | e_{1} |

f_{1} | e_{5} |

Half-edge | Origin | Twin | Incident face | Next | Prev |
---|---|---|---|---|---|

e_{0} | v_{1} | e_{6} | f_{0} | e_{3} | e_{5} |

e_{1} | v_{3} | e_{7} | f_{0} | e_{4} | e_{2} |

e_{2} | v_{2} | e_{3} | f_{0} | e_{1} | e_{4} |

e_{3} | v_{3} | e_{2} | f_{1} | e_{5} | e_{0} |

e_{4} | v_{4} | e_{8} | f_{1} | e_{2} | e_{1} |

e_{5} | v_{2} | e_{9} | f_{1} | e_{0} | e_{3} |

e_{6} | v_{3} | e_{0} | ∅ | e_{9} | e_{7} |

e_{7} | v_{4} | e_{1} | ∅ | e_{6} | e_{8} |

e_{8} | v_{2} | e_{4} | ∅ | e_{7} | e_{9} |

e_{9} | v_{1} | e_{5} | ∅ | e_{8} | e_{6} |