addface::complex edge error in OpenMesh

Question

I've been following the OpenMesh tutorial First Steps - Building a Cube with a few modifications, I'm using a TriMesh instead of a PolyMesh and am building a pyramid instead of a cube.

Somehow, I'm getting the error PolymeshT::add_face:complex edge for my second and third faces. These faces should be between the points (0,0,0), (0,1,0) and (0,0,1) and the points (0,0,0), (0,0,1), and (1,0,0).

Two edges already exist when each face is constructed (0,0,0) to (0,1,0) and (0,0,0) to (0,0,1), but I should be able to create faces where some of the edges are already existing, shouldn't I?

Solutions I've tried so far

• Changing coordinates
• Using PolyMesh instead of TriMesh

I can't spot anything else that I'm doing differently than the tutorial.

#include <OpenMesh/Core/IO/MeshIO.hh>
#include <OpenMesh/Core/Mesh/TriMesh_ArrayKernelT.hh>
typedef OpenMesh::TriMesh_ArrayKernelT<> MyTriMesh;

// Make a pyramid
int main()
{
    MyTriMesh tin;

    // generate vertices
    MyTriMesh::VertexHandle vhandle[4];
    vhandle[0] = tin.add_vertex(MyTriMesh::Point(0, 0, 0));
    vhandle[1] = tin.add_vertex(MyTriMesh::Point(0, 1, 0));
    vhandle[2] = tin.add_vertex(MyTriMesh::Point(1, 0, 0));
    vhandle[3] = tin.add_vertex(MyTriMesh::Point(0, 0, 1));

    // generate (trianglar) faces
    std::vector<MyTriMesh::VertexHandle> face_vhandles;
    face_vhandles.clear();
    face_vhandles.push_back(vhandle[0]);
    face_vhandles.push_back(vhandle[1]);
    face_vhandles.push_back(vhandle[2]);
    tin.add_face(face_vhandles);

    printf("Vertices: %u\nEdges: %u\nTriangles: %u\n",
        tin.n_vertices(), tin.n_edges(), tin.n_faces());

    face_vhandles.clear();
    face_vhandles.push_back(vhandle[0]);
    face_vhandles.push_back(vhandle[1]);
    face_vhandles.push_back(vhandle[3]);
    tin.add_face(face_vhandles);

    printf("Vertices: %u\nEdges: %u\nTriangles: %u\n",
        tin.n_vertices(), tin.n_edges(), tin.n_faces());

    face_vhandles.clear();
    face_vhandles.push_back(vhandle[0]);
    face_vhandles.push_back(vhandle[3]);
    face_vhandles.push_back(vhandle[2]);
    tin.add_face(face_vhandles);

    printf("Vertices: %u\nEdges: %u\nTriangles: %u\n",
        tin.n_vertices(), tin.n_edges(), tin.n_faces());

    face_vhandles.clear();
    face_vhandles.push_back(vhandle[1]);
    face_vhandles.push_back(vhandle[3]);
    face_vhandles.push_back(vhandle[2]);
    tin.add_face(face_vhandles);

    printf("Vertices: %u\nEdges: %u\nTriangles: %u\n",
        tin.n_vertices(), tin.n_edges(), tin.n_faces());

}

Condolent

Answer 1

This error results from some of the faces' vertices being added in the wrong order.

OpenMesh uses a halfedge structure for describing the 3d structure of the mesh. Halfedges are directional edges between vertices. This allows the vertices on a face to be transversed by following the halfedges belonging to the face. However, for this reason the order in which vertices are added to a face is very important.

Typically, vertices should always be added in a counter-clockwise order. This results in the halfedges of adjacent faces pointing in opposite directions as in the picture below left. If the ordering of the vertices is not consistant, there is ambiguity as to which edge follows the halfedge, the bottom edge of 'A' or the bottom edge of 'B', as in the picture below right.

In the code from the question, faces 1 and 4 are ordered counter-clockwise and faces 2 and 3 are ordered clockwise. The simple fix is to switch the first and third vertices for these two faces.

face_vhandles.clear();
face_vhandles.push_back(vhandle[3]);
face_vhandles.push_back(vhandle[1]);
face_vhandles.push_back(vhandle[0]);
tin.add_face(face_vhandles);

face_vhandles.clear();
face_vhandles.push_back(vhandle[2]);
face_vhandles.push_back(vhandle[3]);
face_vhandles.push_back(vhandle[0]);
tin.add_face(face_vhandles);

Condolent

can we not create stl files with incorrect normals? that's insane. why require that my geometry be "valid"? i should still be able to add faces, even if they have "incorrect" normals -- otherwise i can't construct non-manifold geometries – Orientalize

Answer 2

To extend Cecilia's answer, if you are dealing with generated data and can't manually fix the orientation of the triangles, I made a short algorithm for fixing triangle orientation:

def calc_transitions(path):
    return ((path[0], path[1]),
            (path[1], path[2]),
            (path[2], path[0]))

def swap_path_match(path1, path2):
    tr1 = calc_transitions(path1)
    tr2 = calc_transitions(path2)
    
    for t in tr1:
        try:
            loc = tr2.index(t)
            swapped = (path2[(loc+2)%3], path2[(loc+1)%3], path2[loc])
            print('From', path1, ': matched (', t[0], '->', t[1], ') in', path2)
            print('Swapping', path2, 'to', swapped)
            return swapped
        except ValueError:
            continue
    
    return path2

To use this, you simply iterate over your list of faces:

for i in range(len(mesh)):
    for j in range(i+1, len(mesh)):
        mesh[j] = swap_path_match(mesh[i], mesh[j])

Where 'mesh' is a list of 3-tuples, e.g.

[(1, 2, 3), (2, 3, 4), (4, 3, 5)]

In this list, the 0th and 1st element have a conflicting edge, so they will be swapped to:

[(1, 2, 3), (4, 3, 2), (4, 3, 5)]

Now there is a conflict with the 1st and 2nd elements, so it will be swapped to:

[(1, 2, 3), (4, 3, 2), (5, 3, 4)]

The reason the other number gets moved to the front is just a quirk of the implementation; there's no point in maintaining the original ordering if the resulting sequence is equivalent.

To be clear, this doesn't solve geometries where any edge joins more than two triangles.

Mammilla

would you mind explaining how you could accomplish the rearrangement without any recursion? How can you possibly avoid starting from one triangle and then reorienting its neighbors recursively? Thank you! – Zaria

This solution already does not use recursion. – Mammilla

yes, that's why I'm amazed that it was possible to do it without any recursion! – Zaria

This was implemented with OpenMesh in mind. It seems like OpenMesh enumerates the faces such that they are adjacent, which this algorithm wouldn't work without. If we can assume that successive faces are also adjacent, then we only need to visit each face once, since the rotation is enforced from the first face. This could be implemented recursively, but all recursive algorithms can be written as a loop (SO Explanation), and I find recursive algorithms hard to read. – Mammilla