pouët.net

I have a mesh imported from a not-so-good 3d program. The face normals are not correct, some are to the inside, and some to the outside. Also, if I try to calc by myself the normal vector of the triangles, the same.

I want to use two-sided triangles always. Is there any algorithm were given a mesh I can make all the faces the same side?

You know, if two faces are connected, then these should point to the same side.

I believe I could develop an algorithm by myself for this, but maybe there is already one, and you can tell me the name for this kind of algorithm.

Thanks in advance.

Sorry so much. Forget this stupid question, I'm silly.

I've just checked my model again, and it have some of the faces reversed in the original model, this is why I'm having problems.

i wonder, doesn't that imply that it doesn't matter if the face is inside or outside? :D

The real face is outside.

On more serious note though, is there any algorithm that would do what texel described (determining if polygon should be CW/CCW)? I can imagine one for simple convex meshes, or where only few faces are fliped, but any generic one ?

the same way you would do it in 2d, using a crossing test. send a ray from the center of your triangle in the normal direction, test all intersections in the mesh, if the number of intersections is even the orientation is correct.

shiva:

That would work for closed meshes but... Not all meshes are closed.

Sure it does. You can have different textures for example, but not only. I'm doing GI, and the illumination is not the same inside or outside an object

I wonder, maybe we can find an object, like a möbius ring, where inside/outside is not as clear... ;)

Sure baah, in a mobius string there is only one side... wtf

the face is in your mind!

I would start with one triangle, call it T, and then decide on a choice of normal direction for T first. Then move to the (max 3) triangles that share edges with T and propagate the normal direction for T to those neighbors. Then do the same thing for the neighbors until you covered the connected component of T.

One have to build some kind of datastructure containing neighboring info first, but that's either fast and easy or already present in your program :)

This works for connected, closed and non-closed combinatorial complexes (== nice meshes ?). If it's closed and embedded into Eucledian 3-space, you can't have any Mobius bands to worry about by embedding theory. If it is non-closed, then the algorithm above will sooner or later run into a case where you encounter a triangle where you have already a normal direction and this choice contradicts the normal direction you are about to assign to it. ( I hope ;) ) (And I see that you are using the terms "inside" and "outside", so I suppose you are not dealing with non-orientable surfaces anyway..)

Just walk across the faces. Start with any face, then flip neighbouring faces if necessary, and recursively process the neighbouring faces the same way. Like a recursive flood fill. You will only walk to connected parts of the mesh, so if some faces still haven't been processed when you're done, pick any unprocessed face and continue from there.

If you don't have the connectivity information the convention is that two faces A and B share an edge if they share two vertices. Also, one of the faces needs flipping if those two vertices appear in the same order in both faces (that means one is CW and the other is CCW).

Once you have all the faces of a connected part of the mesh facing the same way, you need to determine which way is "in" and which is "out". If the mesh is a fully closed surface, you can do this automatically by tracing a line from infinitely far away and towards the mesh. Use the fact that the angle of incidence must be < 90 degrees to check that the normal is facing the right way. If not, flip the whole mesh.

If the mesh is not connected, there are no definitive "in" and "out" directions, but you could try something like this: Define a centre of the mesh as the weighted average of all vertices. Sum up the area of all the faces facing away from and towards this area, now flip the whole thing as needed to maximise the area facing away from the centre.

Of course this fails for moebius strips etc.

* oh, and the bit about tracing a line, you're only looking for the first intersection with any face, of course.

Randomize all faces' orientations, display the mesh on screen, and pop up a dialog box saying "does the mesh look correct now?". If the user hits "yes", you're done. If not, start over.

Randomize all faces' orientations, use the mesh in a demo and put it on pouet, then wait until you've got more than 100 comments. If just two or less of the comments mention something like "the mesh seems to bug when running the demo on my laptop (vista, sp8, latest dx drivers, etc. etc.)", you're done. If not, put your source on sourceforge and let someone else start over.