In the previous post we covered the basics of the half-edge data structure and how to traverse its elements using OpenMesh. This time, we’ll look under the hood of add_face – the function that builds the entire structure on the fly. When you call:

mesh.add_face(vh0, vh1, vh2);

OpenMesh performs a sequence of operations to wire up the entire topological graph. Let’s trace through what happens step by step.

Imagine two triangles forming a quad, and a third triangle attached to its right side. Let’s start with simple quad described in Post 1.

And add a third triangle attached to its right side.

auto v0 = mesh.add_vertex({0, 0, 0});
auto v1 = mesh.add_vertex({1, 0, 0});
auto v2 = mesh.add_vertex({1, 1, 0});
auto v3 = mesh.add_vertex({0, 1, 0});
auto v4 = mesh.add_vertex({2, 0.5, 0});   // the new triangle's tip
mesh.add_face(v0, v1, v2);   // F0
mesh.add_face(v0, v2, v3);   // F1
mesh.add_face(v2, v1, v4);   // F2

Before F2 is added, the boundary loop of the quad is closed and contains four halfedges:

h1(v1, v0)
-> h9(v0, v3)
-> h7(v3, v2)
-> h3(v2, v1)
-> h1

Now watch what happens if we add F2 without updating the boundary links.

Suppose we create the two missing edges – four new halfedges, h10 through h13 – assign the new face, and close its inner contour. The existing halfedge h3 now continues into h10.

Try walking the old boundary again:

h1(v1, v0)
-> h9(v0, v3)
-> h7(v3, v2)
-> h3(v2, v1)
-> h10(v1, v4)
-> h12(v4, v2)
-> h3
-> h10
-> ...

The walk never returns to h1.

We fall through h3 into the new face and orbit there forever. The boundary loop is broken.

Adding a face is therefore not simply a matter of creating the missing edges. The halfedge links around the seam must also be repaired, carefully and in the correct order. That is what most of the work inside add_face() is about.

The new edges brought not only h10 and h12 – the halfedges the face itself consumes – but also their twins: h11 (v4,v1) and h13 (v2,v4). Two fresh boundary halfedges with no face on them yet. The fix is to route the boundary loop through them instead of h3: h7 should lead into h13, h13 into h11, and h11 back into h1. Three pointer writes, and the walk closes again – h1 -> h9 -> h7 -> h13 -> h11 -> h1 – with the boundary now going around the new triangle.

Now add Face 2 using the existing edge E1 and the newly created edges E5 and E6, and update the affected halfedge links.

Computing next

But how do we compute these next pointers?

The invariant of the structure is that next(h) must be the next halfedge in the same cycle – either a face contour or a boundary loop – and it must start where h ends.

Therefore, to repair a boundary halfedge, we can stand at its end vertex and rotate through the outgoing halfedges until we find another boundary one:

fix_next(h):                      // h is boundary and ends at vertex v
    out = twin(h)                 // first outgoing candidate at v
    while face(out) != -1:        // already belongs to a face
        out = twin(prev(out))     // rotate around v
    next(h) = out                 // first free outgoing halfedge

Before running this algorithm, the inner contour of the new face must already be valid:

h3 -> h10 -> h12 -> h3

and all three halfedges must belong to F2.

Now run fix_next for h7, which ends at v2.

The outgoing halfedges at v2, in rotational order, are:

h6 (F1) -> h4 (F0) -> h3 (F2) -> h13 (boundary)

The search starts at:

twin(h7) = h6

Since h6 belongs to F1, it continues with:

twin(prev(h6)) = twin(h5) = h4

h4 belongs to F0, so it rotates again:

twin(prev(h4)) = twin(h2) = h3

But h3 now belongs to the newly added face F2, so the rotation continues once more:

twin(prev(h3)) = twin(h12) = h13

h13 is a boundary halfedge, so the search stops:

next(h7) = h13

Notice what changed. Before F2 was added, h3 was still a boundary halfedge, so the rotation stopped there:

next(h7) = h3

The new face consumed that old boundary halfedge. The same rotation now passes through it and reaches the next free outgoing halfedge, h13.

The same rule produces the other two boundary links.

For h13, which ends at the new vertex v4, the first outgoing candidate is:

twin(h13) = h12

h12 belongs to F2, so one rotation gives:

twin(prev(h12)) = twin(h10) = h11

h11 is boundary, therefore:

next(h13) = h11

There are only two outgoing halfedges at the new vertex v4, h12 and h11, so the rotation simply passes through the inner one and reaches the outer one.

Finally, consider h11, which ends at v1.

The rotation starts at:

twin(h11) = h10

h10 belongs to F2, so the next candidate is:

twin(prev(h10)) = twin(h3) = h2

h2 belongs to F0, so we rotate again:

twin(prev(h2)) = twin(h0) = h1

h1 is boundary, giving:

next(h11) = h1

All three required writes therefore follow from the same general rule:

next(h7)  = h13
next(h13) = h11
next(h11) = h1

The repaired boundary loop is:

h1 -> h9 -> h7 -> h13 -> h11 -> h1

The OpenMesh solution

For this common case, OpenMesh does not need to perform these rotations. The answers are already encoded in the old boundary loop.

Before inserting F2, the existing halfedge h3 was part of the boundary:

h7 -> h3 -> h1

Therefore:

prev(h3) = h7
next(h3) = h1

When h3 becomes part of the new face, its two new boundary replacements are already known:

h13 = twin(h12)
h11 = twin(h10)

OpenMesh can therefore construct the new boundary using direct pointer operations:

next(prev(h3)) = h13;
next(h13)      = h11;
next(h11)      = next(h3);

Substituting the actual handles gives:

next(h7)  = h13;
next(h13) = h11;
next(h11) = h1;

These are exactly the same links that the general fix_next algorithm found by rotating around the affected vertices.

There is one important catch: prev(h3) and next(h3) must be read before the old boundary links are overwritten.

For this reason, add_face does not apply each change immediately. Instead, it stores the planned assignments in next_cache_:

next_cache_[next_cache_count++] =
    std::make_pair(boundary_prev, outer_next);

Only after all old links have been inspected does OpenMesh apply the entire batch:

for (i = 0; i < next_cache_count; ++i)
    set_next_halfedge_handle(next_cache_[i].first, next_cache_[i].second);

Conceptually, fix_next rebuilds boundary connectivity by searching:

broken boundary
    -> rotate around each affected vertex
    -> find the first free outgoing halfedge
    -> restore next

OpenMesh usually reaches the same result through local splice operations:

read the old boundary neighbours
    -> determine exactly which links must change
    -> store the changes
    -> apply them as one batch

The more complicated re-link patches branch handles a different situation: two consecutive sides of the new face already exist as boundary halfedges, but they are not consecutive in the current boundary loop.

In that case, a whole boundary patch may lie between them. OpenMesh rotates around the shared vertex to find another free boundary gap, moves the patch into that gap, and then links the two reused halfedges directly.

This rotation follows the same underlying boundary invariant as fix_next, but it performs a larger patch-splicing operation rather than repairing only one next pointer.

Why adjust_outgoing_halfedge() is still needed

At the end, adjust_outgoing_halfedge() checks whether a vertex still points to a suitable outgoing halfedge. After adding a face, the halfedge stored by a boundary vertex may now belong to the new face and no longer be part of the boundary. The function rotates around the vertex, finds another outgoing boundary halfedge if one exists, and stores it as the vertex’s new representative. It does not change the mesh topology – it only fixes the vertex’s entry point for future traversal.

Summary

Conceptually, the function performs three main jobs:

validate and create the required edges
    -> build the inner contour of the new face
    -> repair the surrounding boundary and vertex references

The conceptual fix_next rule explains which boundary halfedges must be connected. OpenMesh usually avoids performing the full rotational search and instead computes the same links directly from the old boundary structure. It stores those changes in next_cache_, applies them only after all required reads are complete, and finally calls adjust_outgoing_halfedge() for any vertex whose stored traversal entry point is no longer suitable.