4

我们得到一组三角形。每个三角形是三个点。每个点都是实数的三元组。我们可以计算每个三角形的表面法线。然而，对于 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]])

有没有更有效的方法？

4

2 回答 2

4

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

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

于 2012-11-03T02:39:28.657 回答
3

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

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

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

A --- B
  \ /
   C

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

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

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

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

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

你可能想看看 Three.js 的源代码。具体来说，computeVertexNormals功能。它不支持保持锋利的边缘。算法的效率在很大程度上取决于对基元建模的方式。

于 2013-02-07T23:29:32.273 回答