The most efficient algorithm for calculating vertex normals from a set of triangles for Gouraud shading

Question

We are given a set of triangles. Each triangle represents a triplet of points. Each dot represents a triplet of real numbers. We can calculate the surface normal for each triangle. However, for the shading of Gouro, we need vertex normals. Therefore, we must visit each vertex and look at the triangles that separate this vertex, average their surface normals and get the vertex normal.

What is the most efficient algorithm and data structure for this?

The 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 them to the vertex normal for each corner vertex. Then at the end we normalize the normals for each vertex.

Then at least you only need to cross the triangles once and you only save one normal / vertex.

Answer 2

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

A triangle that is not tied to other triangles cannot be “smoothed”. He is even. Only when a person has neighbors can you reason about smoothing them.

For a vertex where there are several faces, we calculate the normals for each of these faces. The cross product of two vectors returns the perpendicular (normal) vector we want.

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

Be careful to calculate these vectors sequentially on all faces, otherwise your normal one may be in the negative direction to what you need.

So, at the vertex where several faces meet, we summarize the normals of the faces, normalize the resulting vector and apply it to the vertex.

Sometimes you have a grid where some parts of it need to be smoothed and others not. An example of a simple illustration is a cylinder of triangles. The round surface of the cylinder will burn well, but if you look at triangles from the flat ends at the vertices around a sharp ridge, it will look strange. To avoid this, you can introduce a rule that ignores the normals from individuals who deviate too far from the normal of the person for whom you are counting.

EDIT there is a really good video showing the technique for calculating Gurad's shading , although he does not discuss the actual algorithm.

You may like the source from Three.js. In particular, the computeVertexNormals function. It does not support the maintenance of sharp edges. The effectiveness of your algorithm depends to a large extent on how you model your primitives.