Winding order of vertices

4
votes

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?

1
opengl3d
I'm not sure what you mean by an arbitrary group of triangles. Typically the triangles are created from meshes which are built with the correct winding order to begin with. – Vaughn Cato
Yes, when you export the mesh for some rendering system to use, it has the correct winding order. But how would that 3d modeller first determine the correct winding order of things? – newprogrammer

1 Answers

4
votes

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.