从一组三角形计算 Gouraud 着色的顶点法线的最有效算法

Question

我们有一组三角形。每个三角形都是三个点。每个点都是实数的三元组。我们可以计算每个三角形的表面法线。然而，对于 Gouraud 着色，我们需要顶点法线。因此，我们必须访问每个顶点并查看共享该顶点的三角形，平均它们的表面法线，然后得到顶点法线。

实现这一目标最有效的算法和数据结构是什么？

一个简单的方法是这样的（伪 python 代码）：

MAP = dict()
for T in triangles:
  for V in T.vertices:
    key = hash(V)
    if MAP.has(key):
      MAP[key].append(T)
    else:
      MAP[key] = []
      MAP[key].append(T)

VNORMALS = dict()
for key in MAP.keys():
  VNORMALS[key] = avg([T.surface_normal for T in MAP[key]])

有更有效的方法吗？

Answer 1

访问每个三角形，计算每个三角形的法线，将它们添加到每个角顶点的顶点法线。
然后最后，标准化每个顶点的法线。

那么至少你只需要遍历三角形一次并且只存储一个法线/顶点。