从三角形集合计算顶点法线的最有效算法，用于Gouraud着色。

Question

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

最有效的算法和数据结构是什么？

一个朴素的方法是这样的（伪代码）：

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]])

有更高效的方法吗？

- Jayesh

Answer 1

访问每个三角形，计算每个三角形的法线，将其添加到每个角顶点的顶点法线中。
然后最后，对每个顶点的法线进行归一化处理。

这样至少您只需要遍历三角形一次，并且只存储一个法线/顶点。

- Martin Beckett

---

我认为这与我在问题中编写的伪代码相同。可能没有更有效的方法。 - Jayesh

Answer 2

每个顶点都属于一个或多个面（通常是三角形，有时是四边形 - 我在这个答案中将使用三角形）。

没有与任何其他三角形连接的三角形无法“平滑”。它是平的。只有当一个面有邻居时，你才能考虑将它们一起平滑。

对于一个多个面相遇的顶点，计算每个面的法向量。两个向量的叉积返回一个垂直（法向）向量，这正是我们想要的。

A --- B
  \ /
   C

v1 = B - A
v2 = C - A
normal = v1 cross v2

请注意在所有面上一致地计算这些向量，否则您的法线可能与所需方向相反。

因此，在多个面相交的顶点处，对面的法线求和，归一化结果向量，并将其应用于该顶点。

有时您会有一个网格，其中某些部分需要平滑，而其他部分不需要。一个易于理解的例子是由三角形组成的圆柱体。圆柱体的圆形表面会很好地平滑，但如果您考虑围绕锐边的顶点处的平面端面的三角形，它看起来会很奇怪。为了避免这种情况，您可以引入一条规则，忽略偏离要计算的面的法线太远的面的法线。

编辑 这里有一个非常好的视频展示Gourad阴影计算技术，尽管它没有讨论实际算法。

您可能想查看Three.js的源代码。具体来说，是computeVertexNormals函数。它不支持保持锐边。您的算法效率在很大程度上取决于您如何建模基本几何图形。

- Drew Noakes