# Algorithm to Choose Consistent Normals for All Faces on a Polyhedron

I have a polyhedron $P$, in 3D, which consists of $f$ faces, each face consists of $V$ vertexes.

My question is, how to choose a consistent normal orientation for all the faces? Consistent here means that if I unfold all the faces of that polyhedron onto a common plane all the normals will agree.

For the sake of argument, the polyhedron can be either convex or concave. However, it can be unfolded onto a plane without overlap.

-
Is it convex? If no: Can it be unfolded onto a plane without overlap? If no: Is it non-self-intersecting? Oh, and do you have a point in the interior? That would help. –  TonyK Feb 9 '11 at 8:57
@Tony, for the sake of argument, the polyhedron can be either convex or concave. However, it can be unfolded onto a plane without overlap. –  Graviton Feb 9 '11 at 9:03

You didn't specify any data structures you have for your polyhedron (e.g. adjacency lists/matrices between vertices, edges, faces), and this is a math site, so I'll only address the mathematical aspect of the question and not provide an efficient implementation with data structures.

Any two adjacent faces share an edge. A normal defines an orientation of a face, and thus of its edges. If you don't now the orientation of the edges with respect to their faces yet, either, you can determine the orientation a face normal induces on the edges as follows (you need at least something like an ordered list of the vertices to define the face): Traverse the edges (i.e. the vectors between consecutive pairs of vertices) of the face and add up the cross products of all pairs of consecutive edges; then the order in which you traversed the edges is or isn't the one corresponding to the normal according as the dot product of the sum of the cross products with the normal is positive or negative.

So that gives you the relationship between the choice of normals and the orientation of the edges these choices induce. Then you choose a normal on an arbitrary one of the faces and for a pair of adjacent faces where you've chosen a normal on one and not on the other, choose the other normal so that the induced orientations of the edges are opposite.

-
Note after seeing TonyK's comment to the question: This method makes no assumptions about convexity and doesn't need a point in the interior. I'm not sure about self-intersection, but I don't think that should be a problem, either. –  joriki Feb 9 '11 at 9:08