1
$\begingroup$

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

enter image description here

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?

$\endgroup$
  • $\begingroup$ Iterate in both directions - from the current clockwide, and anti-clockwise. $\endgroup$ – lightxbulb Feb 13 at 4:58
  • $\begingroup$ Right, but that's essentially the second loop I mentioned. Which I am hoping to avoid if can be $\endgroup$ – Makogan Feb 13 at 5:01
  • $\begingroup$ You visit all elements exactly once - what is the issue? Otherwise you would have to assign to your vertices, the leftmost/rightmost edges - then you would start at one end and finish at the other. $\endgroup$ – lightxbulb Feb 13 at 6:34
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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