Computing face normals and winding

Question

Given a convex polyhedron with defined vertices (x, y, z) that specifies the faces of the polyhedron.

How can I go about calculating the surface normal of each face of the polyhedron?

I need the surface normal in order to compute the vertex normal to perform Gouraud shading. The only clue I could find about how to do this is Newell's method, but how do I make sure the normals are outward normals and not inward? Thanks for any help.

Answer 1

A simple-minded approach would be to first compute the (bary) centre C of the polyhedron by averaging all the vertices. Since the polyhedron is convex this will be in the its interior. Then for each face compute the normal via a cross product of any two edges of the face, and then determine the direction of the normal by computing the dot product of the normal with V-C, where V is one of the vertices on the face; if this dot product is negative, the normal is inward so negate (each component of) the normal to get an outward normal.

Answer 2

Compute the face normal

You have to compute the cross product of two vectors spanning the plane that contains the given face. It gives you the (non-unit) normal vector of that face. You have to normalize it and you are done.

If x0, x1, x2 are the vertices of a triangular face, then the normal can be computed as

vector3 get_normal(vector3 x0, vector3 x1, vector3 x2)
{
    vector3 v0 = x0 - x2;
    vector3 v1 = x1 - x2;
    vector3 n = cross(v0, v1);

    return normalize(n);
}

Note that the cross product follows the right-hand rule:

The right-hand rule states that the orientation of the vectors' cross product is determined by placing u and v tail-to-tail, flattening the right hand, extending it in the direction of u, and then curling the fingers in the direction that the angle v makes with u. The thumb then points in the direction of cross(u, v).

Orient your triangles

To make sure that all your normals are pointing inside/outside of the polyhedron, the triangles must be uniformly oriented, which means that all the vertices must follow a counter-clockwise (CCW) or clockwise (CW) order. This is also called winding in computer graphics.

You can check the orientation of your triangles by computing the determinant of the matrix below where x3 is a fourth point, your view point during the test.

| x0.x  x0.y  x0.z  1 |
| x1.x  x1.y  x1.z  1 |
| x2.x  x2.y  x2.z  1 |
| x3.x  x3.y  x3.z  1 |

• determinant > 0: x3 is on the + side of the plane defined by CCW points { x0, x1, x2 }
• determinant < 0: x3 is on the - side of the plane defined by CCW points { x0, x1, x2 }
• determinant = 0: x3 is coplanar with { x0, x1, x2 }

Rotating the order of the vertices (by shifting all of them left or right) doesn't change the orientation. So { x0, x1, x2 } has the same orientation as { x2, x0, x1 } and { x1, x2, x0 }.

However if you swap the order of two consecutive elements, you also swap to the opposite orientation. It means that { x0, x1, x2 } has the opposite orientation as { x1, x0, x2 }.

Using this information you can easily orient your triangles: test each triangle using the predicate matrix. If the test fails, simply swap the order of any two consecutive vertex elements and problem solved.