3d - Repairing back-facing triangles without user input

My 3D application works with user-imported 3D models. Frequently, those models have a few vertices facing into the wrong direction. (For example, there is a 3D roof and a few triangles of that roof are facing inside the building). I want to repair those automatically.

We can make several assumptions about these 3D models: they are completely closed without holes, and the camera is always on the outside.

My idea: Shoot 500 rays from every triangle outwards into all directions. From the back side of the triangle, all rays will hit another part of the model. From the front side, at least one ray will hit nothing.

Is there a better algorithm? Are there any papers about something like this?

Answer

I think you can do this just by examining the index list.

For each occurrence of each edge in the index list (an edge should never appear more than twice, and exactly twice for a closed model):

If the indices that define the edge appear in the same order more than once, then you've found a winding order disagreement.

0---1
|  /|
| / |
|/  |
3---2

This quad could be defined by the index list (0,1,3,1,2,3), where the faces are (obviously) (0,1,3) and (1,2,3).

Note that the shared edge (1,3) appears in opposite order - (1,3) and (3,1) - which is required for the faces to have the same winding order. If you saw something like:

(0,1,3),(2,1,3), where the edge(1,3) appears in the same order in both faces, then they face opposite directions and one of them needs to be flipped.

Pick one of the faces that contains the edge and flip it by swapping the position of two of the indices within the list.

Repeat until you've traversed the entire list.

The only issue I can see here is if the edge you start with is backwards/part of a face that is wound in the wrong direction, in which case you'd wind up with a model that's backwards. However, you can try and detect that by counting the number of faces that you've flipped, and, if you reach a certain threshold - say, half of the total faces in the model - pick one of the faces that you've flipped - any one will do - and start over.

Follow-up

I didn't mention this before, but it might be wise to start with one face, then adjust the faces to which it is connected, and the ones to which those are connected, etc., however I have a weird feeling that that level of logic is unnecessary. As long as an edge is never flipped twice, everything should agree after a single pass. Feel free to point out or relay experience or problems with this method