最有效的算法从组三角形的洛德着色的计算顶点的法线(Most efficient algorithm

我们给出了一组三角形。 每个三角形是一个点的三元组。 每个点是实数的三元组。 我们可以计算表面法线每个三角形。 对于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面采用了邻居，你可以推理平滑在一起。

对于其中多个面满足一个顶点，计算每个这些面的法线。 两个向量的叉积返回一个垂直（正常）载体，它是我们所希望的。

A --- B
  \ /
   C

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

要小心，所有的面孔始终计算这些载体，否则你的正常可能是负方向，你需要。

因此，在有多个面相交顶点，总结了面的法线，规范所产生的载体，并将其应用到顶点。

有时候，你有一个网，其中的某些部分将被平滑，而另外一些则不。 一个易于画面的例子是由三角形的圆柱体。 气缸的圆形表面会光滑很好，但如果你考虑从周围的尖岭顶点的两端平坦三角形，它会看起来很奇怪。 为了避免这种情况，你可以引入从偏离正常的你计算面对的太远面孔忽略法线的规则。

编辑有一个非常好的计算Gourad阴影的视频显示技术 ，虽然它不讨论实际的算法。

你可能想看看的three.js所的来源。 具体而言， computeVertexNormals起作用。 它不支持保持锋利的边缘。 你的算法的效率依赖于集中在你所建模的原语的方式在很大程度上。

文章来源: Most efficient algorithm to calculate vertex normals from set of triangles for Gouraud shading