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.

Answer 2

Each vertex belongs to one or more faces (usually triangles, sometimes quads -- I'll use triangles in this answer).

A triangle that is not attached to any other triangles cannot be 'smoothed'. It is flat. Only when a face has neighbours can you reason about smoothing them together.

For a vertex where multiple faces meet, calculate the normals for each of these faces. The cross product of two vectors returns a perpendicular (normal) vector, which is what we want.

A --- B
  \ /
   C

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

Be careful to calculate these vectors consistently across all faces, otherwise your normal may be in a negative direction to that you require.

So at a vertex where multiple faces meet, sum the normals of the faces, normalise the resulting vector, and apply it to the vertex.

Sometimes you have a mesh where some parts of it are to be smoothed, and others not. An easy to picture example is a cylinder made of triangles. The round surface of the cylinder would smooth well, but if you consider triangles from the flat ends at the vertices around the sharp ridge, it will look strange. To avoid this, you can introduce a rule that ignore normals from faces which deviate too far from the normal of the face you're calculating for.

EDIT there's a really good video showing technique for calculating Gourad shading, though it doesn't discuss an actual algorithm.

You might like to take a look at the source of of Three.js. Specifically, the computeVertexNormals function. It does not support maintaining sharp edges. The efficiency of your algorithm depends to a large extent upon the way in which you are modelling your primitives.