best way to compute vertex normals from a Triangle's list

Question

hi i'm a complete newbie in computergraphics so sorry if it's a stupid answer. i'm trying to make a simple 3d engine from scratch, more for educational purpose than for real use.

for now i compute only face normals. in this way:

i have a Surface object with inside a Triangle's list. i compute normals inside Triangle class, in this way:

triangle.computeFaceNormals() {
    Vec3D u = v1.sub(v3)
    Vec3D v = v1.sub(v2)
    Vec3D normal = Vec3D.cross(u,v)
    normal.normalized()
    this.n1 = this.n2 = this.n3 = normal
}

and when building surface:

t = new Triangle(v1,v2,v3)
t.computeFaceNormals()
surface.addTriangle(t)

and i think this is the best way to do that.. isn't it?

now.. this works, ok. but light it's not smoothed. i'm trying to compute also vertex normals. (i'm testing my engine with tubolar surfaces so i have almost all vertex shared with more then one triangles)

i've found this simple algorithm: flipcode vertex normal but.. hei this algorithm has.. exponential complexity? (if my memory doesn't fail my computer science background..) (bytheway.. it has 3 nested loops.. i don't think it's the best way to do it..)

any suggestion?

Answer 1

"Best" is pretty subjective -- it's going to involve weighing what you need out of the algorithm versus it's inputs, runtime complexity and other properties.

That said, both your approach and the linked FlipCode approach are reasonable in terms of producing usable results (you could quite simply copy your 'face normals' to each vertex, if you are not sharing actual vertex instances between triangles, which I'm unclear on from your code). Other techniques include weighting the contribution of each face normal by the size of the angle made with each face shared by the vertex.

You are correct in that the FlipCode approach appears suboptimal as written, but it could just be poorly specified: it's a little unclear whether or not it intends to suggest the second loop traverse all faces in the model, versus the handful of faces that share the vertex in question. If you have the adjacency information to reduce the search space of the second loop, it becomes less of a concern. Of course you may not have that adjacency information -- this is sort of what I mean by considering what inputs you have available to your algorithm.

If you don't just want to copy the face normal into the vertices, or you are sharing vertices and don't want to split them, you could:

foreach vertex:
   set vertex normal to (0,0,0)

foreach triangle:
   foreach vertex on that triangle:
      set vertex normal = normalize( vertex normal + face normal )

This assumes that each triangle is actually referencing each vertex rather than storing a copy of it -- I don't know what language you're using so I don't know if that's the case or not.

Answer 2

Josh Petrie has right. If you want to compute vertex normals, you should weight triangle contribution by angle. But you can use naive solution and just sum all normals from all faces around vertex.

So you just compute all face normals and normalize them. Then set all vertex normals to zero. Then for each face (triangle) add its normal to all of its vertices. Then normalize all vertex normals. And it's done.

It's not too correct but it could be enough.

And your face normal calculation above - it's correct but you should aware, which side normal heads. It could head up or down. It depends on cross product - AxB is not the same as BxA - it gives you opposite vector.

Answer 3

Let us assume that we have a cube made from 6 rectangles. We already know that the vertex normal for a cube is not the normalized sum of the connection faces because of the sharp edge. If you build a map of vertex value and it's different vertex normals for a cube you end up with 3 normals for each vertex.

Keeping the above point in mind this is how I calculate vertex normals(I have tested it and am using it).

class Face{
    uint vert_indices[3];
    vec3 surface_normal;
    vec3 vertex_normal[3];
}

Each face keep track of the vertex normals to use since two faces may share a vertex does not mean the vertex normal will be the same for each face.

Let us assume we are trying to calculate the vertex normal for vert when rendering face2.

vert is shared by face0,face1,face2,face3 and face4. All the above face are neighbours in order and face0 and face4 connect to form a loop.

The vertex normal for vert is the sum of all the connected neighbour chain to face2 normalized. The chain stops if the angle between two neighboured faces is more that 0.8 radians(angle == arccos(crossProduct(faceA.surface_normal, faceB.surface_normal))).

if the angle between face0 and face1 is more than 0.8 radian and the angle between face3 and face4 is more than 0.8 radian than the vertex normal for vert when rendering face2 is normalize(surfnormal1+surfnormal2+surfnormal3).