Winding order of vertices

3d, opengl

Solution

You did unerstand it wrong. It doesn't

test it against intersection against every other triangle.

First of all, you can orient (wind-up) your triangles based solely on normal vector of the triangle surface. Then there are only two options left - the whole model is either good or flipped ;)

So you've really got to check only ONE triangle, and then wind up the rest basing on the results of the last check, which is basically giving you O(n).

EDIT: Oh, I think i know when this approach might fail. I just remembered that for example Google Sketchup doesn't do it very well, and sometimes you need to orient faces yourself. However, if you increase the number of random rays (for random triangles), you really do increase your chance of marking everything correctly.

EDIT2: And before some 50k+ guy downvotes me to the ground - If the model is totally mixed up (all triangles are in random order), there is no other way to orient all of them properly, than checking them all against the other, convex models being the exception.

Problem

I understand what winding order is, and how it is used for backface culling. However, I am not exactly sure how 3d modelling programs like Blender can take an arbitrary group of triangles and wind them all correctly. I tried googling the answer and this was the best I found: http://www.gamedev.net/topic/550481-vertex-winding-order-counter-clockwise-oder-vertex---algorithm/ Basically, for each triangle, you find its center (barycenter to be precise), calculate a normal vector from that triangle, which gives you a ray. You take this ray and test it against intersection against every other triangle. If it's an even number, then your winding is correct, if it's an odd number, your winding is incorrect (I guess this depends on how exactly you generated the normal vector, but you use the odd/even strategy somehow). Anyways, that means this whole process is generally O(n^2). If you have 1000 triangles, then for each triangle, you have to test it against intersection for 999 other triangles. Is there a less obvious way to correctly wind vertices, that is more efficient?

Original source