How to handle Half edge boundary edge iteration from vertex?

Question

Ok so let's say we have a portion of a mesh that looks somewhat like this:

A triangle fan with one of the triangles removed. If that triangles was not removed, we could get all the edges adjacent to that vertex this way:

std::vector<GraphEdgePtr> GraphVertex::GetVertexEdges()
{
    std::vector<GraphEdgePtr> edges;
    auto current_edge = edge;
    do
    {
        edges.push_back(current_edge);
        current_edge = current_edge->pair->next;
    } while(current_edge != edges[0]);

    return edges;
}

However, if the triangle is removed, the above will segfault. One could create an additional loop that iterates backwards from the starting edge in the case the first loop finds a null pointer.

However that is a bit inelegant in my opinion. Is there a way to do it in a single loop? Using a stack or a queue or some sort for example?

Answer 1

It depends a little on your actual data structure and how it even encodes boundary edges. What I find more useful than representing the boundary with a null half edge pointer, and thus having this situation of a half edge without an opposite and thus a hard stop for any such iteration, is instead encoding the boundary with a full half edge pair too, but with one of the half edges having a null face pointer.

So the boundary edge actually does have an opposite (or pair pointer) and that opposite is fully integrated into the pointer structure, complete with next pointer and everything. Just that its face pointer in null, thus denoting an empty face or hole. So basically every hole is represented by a null face with half edges going around it.

In addition to being able to iterate around vertices regardless of the starting point, this also has the advantage that you can easily iterate around boundary curves. And you can even have more than one hole at a vertex (although, that can still be problematic in other situations). Of course you might still have to handle the boundary half edges specially in some situations, especially when you're using the face pointers, but you won't get around that anyway if your mesh can have holes.

---

If that is too much of a hassle to restructure your data and algorithms this way, though, maybe you can instead adjust your vertex starting edge pointers to always point to the boundary edge if there is one. You'd of course have to make sure that stays consistent, but if you can assume that as a precondition, you can just start iterating from there. And you can also check immediately if the vertex is at a boundary without having to iterate.