7 replies to this topic

[Stainless]

I have a problem that a lot of the free 3d meshes I am using for demonstrations are generated with mixed winding order on the triangles.

So when I render them half the triangles disappear.

I have tried writing some code that calculates a face normal for each triangle and compares it to the vertex normals, if the angle between the face normal and the vertex normals is greater than 90 degrees, I flip the winding order.

This seems to work for objects that are supplied with vertex normals, but some of the objects I want to use don't have vertex normals.

I am struggling to come up with an alternative technique for this case.

The best I can come up with at the moment is to calculate the centre of the object, throw a ray through each vertex and compare the direction of this ray with the face normal, but that only works for some objects.

Out of ideas, anyone got anything?

[}:+()___ (Smile)]

Winding order is mostly topological characteristic, so you can fix it without even point coordinates.

Pick triangle with right winding order, mark it as processed. For each its edge find adjacent unprocessed triangles. If such triangle sweeps edge points in the same order as in the processed area than flip winding order. Mark corrected adjacent triangles as processed and repeat algorithm for the new edges of processed area. When you couldn't find adjacent triangles at all, you'll have fully processed connected piece of mesh. Pick another triangle and move to next piece. If you pick triangle with wrong winding order than whole piece will be backfaced, you can correct this later.

[Stainless]

I see where you are going with this, but it's not really a general case solution.

If you do pick a starting triangle with the wrong winding order, then it's possible that the entire object will end up with the wrong winding order.

It's worth thinking about though, the idea of using connections may be something I can work with.......

[Reedbeta]

I think the idea is that it simplifies the problem to an either/or choice, since either the whole thing is right or the whole thing is inside-out. You might have the user manually pick the correct orientation, or pick a correct triangle to start with - it's not a lot of work to do that once per model, and is the sort of thing that humans are better at than computers.

[Stainless]

True, but it doesn't solve my problem, I need it to be a "human interaction free" solution

I think I'm going to put it in my toolbox though, I'll try and find time to do it tomorrow and let you know how well it works

[TheNut]

What if you picked an arbitrary point at "infinity" whose normal points towards the origin. Use that as your outside point. Find the polygon on your model closest to that outside point and calculate the dot product between their normal vectors. If the result is positive, you flip the winding order, else your winding is correct and you can proceed with Smile's algorithm for the rest of the model.

[}:+()___ (Smile)]

When you close connecting peice you can raytrace several points (centers of triangles) from that piece. After that you can determine winding order for the whole piece by majority rule. And, of course, my algorithm doesn't work for bad meshes: when 3 or more triangles share the same edge or for Möbius-like shapes.

[Stainless]

What I am thinking about at the moment is a general case solution. It's a bit expensive though.

Render the object into a depth buffer, I don't care about anything else, with culling off. Then using the depth buffer as a test parse the object again.

If the polygon is the "front" polygon, and it's surface normal is pointing away from the camera, then flip it's winding.

Repeat this for all six major axes.

I'm not at all sure if this will work with all objects though, the case I think may fail is an object with engines.

I did a quick check on one mesh and there are a lot of cases when three polygons share an edge. It's probably where the artist added a subdivided basic shape to the mesh.