Is a closed polygonal mesh flipped?

Question

I have a 3d modeling application. Right now I'm drawing the meshes double-sided, but I'd like to switch to single sided when the object is closed.

If the polygonal mesh is closed (no boundary edges/completely periodic), it seems like I should always be able to determine if the object is currently flipped, and automatically correct.

Being flipped means that my normals point into the object instead of out of the object. Being flipped is a result of a mismatch between my winding rules and the current frontface setting, but I compute the normals directly from the geometry, so looking at the normals is a simple way to detect it.

One thing I was thinking was to take the bounding box, find the highest point, and see if its normal points up or down - if it's down, then the object is flipped.

But it seems like this solution might be prone to errors with degenerate geometry, or floating point error, as I'd only be looking at a single point. I guess I could get all 6 axis-aligned extents, but that seems like a slightly better kludge, and not a proper solution.

Is there a robust, simple way to do this? Robust and hard would also work.. :)

Answer 1

This is a robust, but slow way to get there:

Take a corner of a bounding box offset from the centroid (force it to be guaranteed outside your closed polygonal mesh), then create a line segment from that to the center point of any triangle on your mesh.

Measure the angle between that line segment and the normal of the triangle.

Intersect that line segment with each triangle face of your mesh (including the tri you used to generate the segment).

If there are an odd number of intersections, the angle between the normal and the line segment should be <180. If there are an even number, it should be >180.

If there are an even number of intersections, the numbers should be reversed.

This should work for very complex surfaces, but they must be closed, or it breaks down.

Answer 2

"I'm drawing the meshes double-sided"

Why are you doing that? If you're using OpenGL then there is a much better way to go and save yourself all the work. use:

glLightModeli(GL_LIGHT_MODEL_TWO_SIDE, 1);

With this, all the polygons are always two sided.
The only reason why you would want to use one-sided lighting is if you have an open or partially inverted mesh and you want to somehow indicate what part belong to the inside by having them unlighted.

Generally, the problem you're posing is an open problem in geometry processing and AFAIK there is no sure-fire general way that can always determine the orientation. As you suggest, there are heuristics that work almost always.
Another approach is reminiscent of a famous point-in-polygon algorithm: choose a vertex on the mesh and shoot a ray from it in the direction of the normal. If the ray hits an even number of faces then the normal is pointed to the outside, if it is odd then the normal is towards to inside. notice not to count the point of origin as an intersection. This approach will work only if the mesh is a closed manifold and it can reach some edge cases if the ray happens to pass exactly between two polygons so you might want to do it a number of times and take the leading vote.