Bow-type弓形非流形几何的三角网格高效检测算法咨询

核心判定规则 #

弓形非流形顶点的核心判定依据是：该顶点邻接的所有三角面，通过「共享含该顶点的边」构成的连通分量数量 ≥ 2。
你最初的思路方向是正确的，但不能只判断顶点关联多个面就下结论——比如普通的流形内部顶点通常关联6-8个面，但所有面都通过边两两连通，连通分量数为1，属于合法结构。只有连通分量数超过1的顶点才是弓形非流形顶点，对应多个曲面仅在该点拼接的拓扑。

算法复杂度 #

该算法为线性时间复杂度O(V + F)，是当前理论最优的检测方案：

• 每个三角面只会被它的三个顶点各遍历一次，总遍历次数为3F
• 每个顶点的连通分量计算仅在其关联面集合内进行，无额外冗余计算

伪代码 #

输入：三角网格的所有顶点集合，每个顶点已存储关联三角面集合adj_faces
输出：所有弓形非流形顶点列表

bowtie_nonmanifold_vertices = []
for each vertex v in vertices:
    if len(v.adj_faces) <= 1:
        continue  # 最多关联1个面，不可能是多曲面连接
    # 构建v的邻接面连通图：两个面连通当且仅当共享一条含v的边
    visited = 空集合
    component_count = 0
    for each face f in v.adj_faces:
        if f not in visited:
            component_count += 1
            # BFS遍历所有和f连通的面
            queue = [f]
            visited.add(f)
            while queue not empty:
                current_f = queue.pop()
                # 遍历current_f的相邻面，筛选同时关联v的面
                for neighbor_f in current_f.adjacent_triangles:
                    if neighbor_f in v.adj_faces and neighbor_f not in visited:
                        visited.add(neighbor_f)
                        queue.append(neighbor_f)
    if component_count >= 2:
        bowtie_nonmanifold_vertices.append( (v, component_count) )
return bowtie_nonmanifold_vertices

基于现有代码的Python实现 #

可以直接在你现有TriMesh类的基础上增加检测方法：

from collections import deque

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
    
    # 新增弓形非流形检测方法
    def detect_bowtie_vertices(self):
        bowtie_vertices = []
        for v in self.vertices:
            adj_faces = v.adjacent_triangles
            if len(adj_faces) <= 1:
                continue
            visited = set()
            comp_cnt = 0
            for f in adj_faces:
                if f not in visited:
                    comp_cnt += 1
                    q = deque([f])
                    visited.add(f)
                    while q:
                        cur_f = q.popleft()
                        for nb_f in cur_f.adjacent_triangles:
                            if nb_f in adj_faces and nb_f not in visited:
                                visited.add(nb_f)
                                q.append(nb_f)
            if comp_cnt >= 2:
                bowtie_vertices.append((v.label, comp_cnt))
        return bowtie_vertices


if __name__ == "__main__":
    #     4---5   6   7
    #     |\t1|  /|\
    #     | \ | / | \
    #     |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)
    res = m.detect_bowtie_vertices()
    print("弓形非流形顶点（顶点标签，连接曲面数）：", res)
    # 输出结果：弓形非流形顶点（顶点标签，连接曲面数）： [('1', 2)]

结果验证 #

你给出的测试用例中顶点1的关联面是{t0,t1,t2}，其中t0和t1共享边1-4连通，t2和前两个面没有共享含顶点1的边，所以连通分量数为2，符合预期的检测结果。

内容的提问来源于stack exchange，提问作者BPL