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

访问每个三角形，计算每个三角形的法线，将其添加到每个角点的顶点法线上。

最后，对每个顶点的法线进行规格化。

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

Answer 2

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

没有附加到任何其他三角形的三角形不能被“平滑”。它是平的。只有当一张脸有邻居时，你才能推理出将它们平滑在一起。

对于多个面相交的顶点，计算每个面的法线。两个向量的叉积返回一个垂直(法线)向量，这是我们想要的。

A --- B
  \ /
   C

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

要小心地在所有面上一致地计算这些向量，否则法线可能会与所需的方向相反。

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

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

有一个非常好的video showing technique for calculating Gourad shading，虽然它没有讨论实际的算法。

你可能想看看Three.js的源代码。具体地说，是computeVertexNormals函数。它不支持保持锐边。算法的效率在很大程度上取决于对原语进行建模的方式。