如何从给定的顶点索引列表生成边列表？

Question

我有一个如下图所示的面-顶点网格。

Face-Vertex Mesh

我有 'face_list' 和 'vertex_list' 数据集，但不确定如何有效地计算边列表。

Answer 1

计算面的法向量。如果2个相邻面的法向量指向不同的方向，则该面共有的两个顶点形成一条边。

面的法向量可以用 Cross product. For a face with the vertices A, B, C, the unit 法向量计算：

N = normalized(cross(B-A, C-A))

面的法向量可以与Dot product进行比较。 2 个法向量 N1 和 N2 方向相等，如果：

equally_directed = abs(dot(N1, N2)) == 1

使用矢量算法库。例如 OpenGL Mathematics (GLM) library for Python or NumPy.

最小示例：

import glm, math

vertices = [(-1,-1,-1), ( 1,-1,-1), ( 1, 1,-1), (-1, 1,-1), (-1,-1, 1), ( 1,-1, 1), ( 1, 1, 1), (-1, 1, 1)]
faces = [(0,1,2), (0,2,3), (5,4,7), (5,7,6), (4,0,3), (4,3,7), (1,5,6), (1,6,2), (4,5,1), (4,1,0), (3,2,6), (3,6,7)]

v = [glm.vec3(vertex) for vertex in vertices]
nv_list = [glm.normalize(glm.cross(v[i1]-v[i0], v[i2]-v[i0])) for i0,i1,i2 in faces]

edge_threshold = 0.99
edges = []
for i, f1 in enumerate(faces):
    for j, f2 in enumerate(faces[i+1:]):
        edge_candidates = [(f1[0], f1[1]), (f1[1], f1[2]), (f1[2], f1[0])]
        for ei0, ei1 in edge_candidates:
            if ei0 in f2 and ei1 in f2:
                cos_nv = math.fabs(glm.dot(nv_list[i], nv_list[j+i+1]))
                if  abs(cos_nv) < edge_threshold:
                    edges.append((ei0, ei1))

print(len(edges))
print(edges)

输出：

12
[(1, 2), (0, 1), (3, 0), (2, 3), (4, 7), (5, 4), (6, 5), (7, 6), (4, 0), (3, 7), (1, 5), (6, 2)]

如何从给定的顶点索引列表生成边列表？

How do I a generate a list of edges from a given list of vertex indices?

python

opengl

graphics

rendering

polygon