寻求非流形顶点（3D四边形、三角形）检测的文献与算法建议

一、入门文献推荐 #

• 《Polygon Mesh Processing》：网格处理领域经典教材，其中专门章节详细讲解非流形网格的定义、检测规则与基础处理方法，适合从零建立领域认知。
• 《Non-Manifold Modeling for CAD and Visualization》：综述类文献，系统梳理非流形建模的核心问题与主流解决方案，能快速帮你把握领域脉络。
• 《Detection and Repair of Non-Manifold Conditions in Polygonal Meshes》：实操性极强的论文，包含具体的非流形顶点检测算法步骤，可直接对应代码实现。

二、核心检测算法思路 #

针对三角形/四边形网格，非流形顶点主要分为两类，对应两种检测逻辑：

1. 边共享型非流形：一条边被超过2个面共享（比如一条边同时属于3个三角形），这条边的两个顶点均为非流形顶点。
2. 顶点星型非流形：顶点周围的面无法形成单一连通环（比如顶点连接的面被分成两个独立区域），这类顶点也属于非流形顶点。

三、无外库Python实现步骤与代码框架 #

数据结构准备 #

先整理网格的基础映射关系：

• 用字典存储边到关联面的映射（边用排序后的顶点索引元组表示，避免(0,1)和(1,0)被视为不同边）
• 用字典存储顶点到关联边的映射

检测逻辑实现 #

# 输入参数说明：
# vertices: 列表，每个元素为(x,y,z)坐标，索引作为顶点ID
# faces: 列表，每个元素为顶点索引列表（三角形是3个元素，四边形是4个元素）

def detect_non_manifold_vertices(vertices, faces):
    # 构建边->关联面的映射
    edge_to_faces = {}
    # 构建顶点->关联边的映射
    vertex_to_edges = {vid: set() for vid in range(len(vertices))}

    # 遍历所有面，填充映射关系
    for face_id, face in enumerate(faces):
        vert_count = len(face)
        for i in range(vert_count):
            v1 = face[i]
            v2 = face[(i+1) % vert_count]
            # 标准化边的表示，避免方向问题
            edge = tuple(sorted((v1, v2)))
            # 更新边到面的映射
            edge_to_faces.setdefault(edge, []).append(face_id)
            # 更新顶点到边的映射
            vertex_to_edges[v1].add(edge)
            vertex_to_edges[v2].add(edge)

    non_manifold_verts = set()

    # 第一步：检测边共享型非流形顶点
    for edge, related_faces in edge_to_faces.items():
        if len(related_faces) > 2:
            non_manifold_verts.add(edge[0])
            non_manifold_verts.add(edge[1])

    # 第二步：检测顶点星型非流形顶点
    for vid in range(len(vertices)):
        if vid in non_manifold_verts:
            continue  # 已判定为非流形，跳过
        related_edges = vertex_to_edges[vid]
        if not related_edges:
            continue  # 孤立顶点，按需处理

        # 收集当前顶点关联的所有面
        related_faces = set()
        for edge in related_edges:
            related_faces.update(edge_to_faces[edge])
        related_faces = list(related_faces)
        if len(related_faces) <= 1:
            continue  # 仅关联0或1个面，不属于非流形（退化情况按需调整）

        # 构建面的邻接关系：共享含当前顶点的边则视为邻接
        face_adjacency = {fid: [] for fid in related_faces}
        face_to_v_edges = {}
        for fid in related_faces:
            face = faces[fid]
            # 提取当前面中包含目标顶点的边
            v_edges = []
            vert_count = len(face)
            for i in range(vert_count):
                v_a = face[i]
                v_b = face[(i+1) % vert_count]
                if vid in (v_a, v_b):
                    v_edges.append(tuple(sorted((v_a, v_b))))
            face_to_v_edges[fid] = set(v_edges)

        # 填充邻接表
        for i in range(len(related_faces)):
            f1 = related_faces[i]
            for j in range(i+1, len(related_faces)):
                f2 = related_faces[j]
                if face_to_v_edges[f1] & face_to_v_edges[f2]:
                    face_adjacency[f1].append(f2)
                    face_adjacency[f2].append(f1)

        # 连通性检测：若面无法形成单一连通分量，则顶点是非流形
        visited = set()
        start_face = related_faces[0]
        stack = [start_face]
        visited.add(start_face)

        while stack:
            current_face = stack.pop()
            for neighbor in face_adjacency[current_face]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)

        if len(visited) != len(related_faces):
            non_manifold_verts.add(vid)

    return list(non_manifold_verts)

四、后续拆分网格的提示 #

检测出非流形顶点后，拆分网格的核心思路是：对每个非流形顶点，在其所属的不同连通面组中创建独立的顶点副本，重新分配索引后更新对应面的顶点引用，最终实现各连通部分的独立。

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