graphics - Most efficient algorithm to calculate vertex normals from set of triangles for Gouraud shading

Question

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?

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?

Answer 1

Visit each triangle, calculate the normal for each triangle, ADD those to the vertex normal for each corner vertex.
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.