由网友(萌妹纸的霸气范)分享简介：我们给出了一组三角形。每个三角形是一个点的三重。每个点是实数的三重态。我们可以计算出曲面法线每个三角形。对于Gouraud着色然而，我们需要顶点法线。因此，我们必须访问每个顶点，并期待在共享顶点的三角形，它们的平均表面法​​线，我们得到的顶点正常。We are given a set of triangles. Ea...

我们给出了一组三角形。每个三角形是一个点的三重。每个点是实数的三重态。我们可以计算出曲面法线每个三角形。对于Gouraud着色然而，我们需要顶点法线。因此，我们必须访问每个顶点，并期待在共享顶点的三角形，它们的平均表面法​​线，我们得到的顶点正常。

We are given a set of triangles. Each triangle is a triplet of points. Each point is a triplet of real numbers. We can calculate surface normal for each triangle. For Gouraud shading however, we need vertex normals. Therefore we have to visit each vertex and look at the triangles that share that vertex, average their surface normals and we get vertex normal.

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

What is the most efficient algorithm and data structure to achieve this?

一个幼稚的做法是这样的（伪蟒蛇code）：

A naive approach is this (pseudo python code):

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

有没有更有效的方法？

Is there a more efficient approach?

推荐答案

参观每一个三角形，计算法线每个顶点，添加这些到每个顶点正常。 然后，在结束时，归一化的法线为每个顶点

Visit each triangle, calculate the normals for each vertex, ADD those to each vertex normal. Then at the end, normalise the normals for each vertex.

那么至少，你只需要遍历三角形一次，你只存储一个正常/顶点。

Then at least you only have to traverse the triangles once and you only store one normal/vertex.