Algorithm to detect bow-type non-manifold geometry

Question

There are different types of non-manifold geometry and one of them is the Bow-type. In this instance, multiple surfaces are connected at one point and don’t share an edge.

You can see below an example of this particular type:

I'm trying to come up with an efficient algorithm to check whether a point is connected to multiple surfaces. In order to do so I've created a fast python prototype to play with where the mesh adjacency information is built, so you can basically make the typical topological queries such as {vertices->faces}, {edges->faces}, {vertices->faces}.

class Triangle:
    def __init__(self, a, b, c, label):
        self.a = a
        self.b = b
        self.c = c
        self.label = label
        self.adjacent_triangles = []

    def __repr__(self):
        return f"{self.label}"


class Vertex:
    def __init__(self, x, y, label):
        self.x = x
        self.y = y
        self.label = label
        self.adjacent_triangles = set()

    def __repr__(self):
        return f"{self.label} - {self.adjacent_triangles}"


class Edge:
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.adjacent_triangles = []

    def __repr__(self):
        return f"{self.__dict__}"


class TriMesh:
    def __init__(self, vertices, triangles):
        edges = {}

        def process_edge(a, b, triangle):
            vertex_index_a = min(a, b)
            vertex_index_b = max(a, b)
            key = f"{vertex_index_a}_{vertex_index_b}"

            if key in edges:
                edge = edges[key]
            else:
                edge = Edge(vertices[vertex_index_a], vertices[vertex_index_b])
                edges[key] = edge

            edge.adjacent_triangles.append(triangle)

        for triangle in triangles:
            process_edge(triangle.a, triangle.b, triangle)
            process_edge(triangle.b, triangle.c, triangle)
            process_edge(triangle.c, triangle.a, triangle)

        for key in edges:
            edge = edges[key]
            f0 = edge.adjacent_triangles[0]
            edge.a.adjacent_triangles.add(f0)
            edge.b.adjacent_triangles.add(f0)

            if len(edge.adjacent_triangles) < 2:
                continue

            f1 = edge.adjacent_triangles[1]
            edge.a.adjacent_triangles.add(f1)
            edge.b.adjacent_triangles.add(f1)
            f0.adjacent_triangles.append(f1)
            f1.adjacent_triangles.append(f0)

        self.vertices = vertices
        self.triangles = triangles
        self.edges = edges


if __name__ == "__main__":
    #     4---5   6   7
    #     |	1|  /|\
    #     | \ | / | \
    #     |t0\|/t2|t3\
    #     0---1---2---3
    v = [
        Vertex(0, 0, "0"),
        Vertex(1, 0, "1"),
        Vertex(2, 0, "2"),
        Vertex(3, 0, "3"),
        Vertex(0, 1, "4"),
        Vertex(1, 1, "5"),
        Vertex(2, 1, "6"),
        Vertex(3, 1, "7"),
    ]
    t = [
        Triangle(0, 1, 4, "t0"),
        Triangle(1, 5, 4, "t1"),
        Triangle(1, 2, 6, "t2"),
        Triangle(2, 3, 6, "t3"),
    ]

    m = TriMesh(vertices=v, triangles=t)

    for v in m.vertices:
        print(v)

What'd be an efficient algorithm that detects whether multiple surfaces are connected to one point? For instance, in the above you can see vertex 1 is shared by 2 surfaces, S1={t0,t1} & S2={t2}. So I know that particular 2d mesh is bow-type.

The first idea that comes to my mind would be come up with some algorithm that's able to extract surfaces shared from each point of the mesh, that way it becomes a matter to find the first point that's shared by multiple surfaces so you know the mesh is non-manifold bow-type. On the other hand, maybe there are smarter ways to check whether a mesh is bow-type or not. Could you please provide an implementation/pseudocode/explanation/theory if you know such a case?

Algorithm to detect bow-type non-manifold geometry

Answers (1)

Related Questions