How to efficiently determine the normal to a polygon in 3D space?

Question

I have a bunch of coplanar points defining a polygon in 3D space. These are always wound the same way (e.g. clockwise). I need to determine the signed normal to the plane containing this polygon, i.e., know which way is "up" for that polygon.

This seems easy enough at first: take two edges (vertex differences) and compute the cross product. But that fails if the edges happen to be colinear (you get a zero-magnitude cross product).

So then I tried walking the vertex list until I find a second edge that makes a reasonably large angle with the first edge. This works reliably on a convex polygon, but it can fail (point the opposite direction) on a non-convex polygon if the two edges I end up with don't define a triangle that's inside the polygon.

I know that if I triangulated the polygon first, then I could easily and reliably check the facing of any triangle... but the problem is that my triangulation library requires knowing the plane normal. So, egg must come before chicken.

How do I pick two edges (or three vertices) in an non-convex polygon that will reliably define which way the polygon is facing?

Answer 1

If I were you, I would have done it in the following way:

1. Choose any point C near the polygon (any vertex or mass center).
2. Sum cross products (P[i] - C) x (P[i+1] - C) for all i (including last and first points pair).
3. Normalize the sum vector.

Note that after step 2 you have a vector which has normal direction with proper orientation, and its magnitude is 2 S, where S is the area of your polygon. That's why it should work unless your polygon has zero or almost zero area.

By the way, point C is used here only to make calculation a bit more precise for small polygons located far from the origin. You can choose C = 0, efficiently removing it from calculations.