Windedness Of Triangle
Author
A bit embarrassing to ask such a basic question, but I am just not in a problem-solving mood lately.
I just need to know how to detect if my 3D triangle is CCW or not.
Detecting CW or degenerate is optional, but I can not figure out the proper way to get all of these results in one quick test. The method I invented seems too intensive.
My idea was to dot a vector against C from (B - A), where the vector is obtained via scalar product of (B - A) and the triangle normal (which means calculating the triangle normal also if not already done). This works, but damn, isn't there a faster way?
Thank you,
L. Spiro
I would have done it this way, if the normal is given:
sign( dot( cross(b-a),(c-a) ), normal ) ).
Note: I believe there should be a formula using a determinant for this, but I can't remember it.
if it's positive, then the winding is anti-clockwise. If negative, it's clockwise. And if it is equal to zero( or very close to it ), then a, b and c are co-linear.
If the normal is not given, the winding is undefined: you have to make a convention for computing your normals. It is either cross( b-a, c-a ) or cross( c-a, b-a ).
a,b,c being respectively the first, second and third vectors defining the triangle.
sign( dot( cross(b-a),(c-a) ), normal ) ).
Note: I believe there should be a formula using a determinant for this, but I can't remember it.
if it's positive, then the winding is anti-clockwise. If negative, it's clockwise. And if it is equal to zero( or very close to it ), then a, b and c are co-linear.
If the normal is not given, the winding is undefined: you have to make a convention for computing your normals. It is either cross( b-a, c-a ) or cross( c-a, b-a ).
a,b,c being respectively the first, second and third vectors defining the triangle.
Author
Are you sure about that formula?
cross( (b-a),(c-a) ) == normal, so dot( cross( (b-a),(c-a) ), normal ) always evaluates to a positive value.
I think you meant:
normal = cross( (b - a),(c - a) );
sign( dot( cross( normal, (b - a) ), (c - a) ) );
That is basically the method I am using.
For 2D is it very simple. All on one line. I was hoping there was something similar for 3D, but maybe there can be if I know the normal before-hand (which I do).
Thank you for your reply.
L. Spiro
cross( (b-a),(c-a) ) == normal, so dot( cross( (b-a),(c-a) ), normal ) always evaluates to a positive value.
I think you meant:
normal = cross( (b - a),(c - a) );
sign( dot( cross( normal, (b - a) ), (c - a) ) );
That is basically the method I am using.
For 2D is it very simple. All on one line. I was hoping there was something similar for 3D, but maybe there can be if I know the normal before-hand (which I do).
Thank you for your reply.
L. Spiro
A triangle in 3D can be CW or CCW, depending on from which side you look onto it. This means, that this viewing direction must be taken into account in the formula, either as term or as convention. For instance OpenGL calculates the signed area of a triangle/polygon in window coordinates (camera is looking along the z-axis). Then depending on the sign the triangle is either CW or CCW. Read here formula (2.6) at page 63. If you don't like looking along the z-axis, you can use any direction by projecting the triangle corners into a plane perpedicular to that direction.
Author
I just realized that by calculating the normal the result will always be true except in degenerate situations, because the normal is always relative to the orientation of the triangle.
What I have to do is supply the known normal and use that, which does make my test much faster.
The triangles are not used for graphics and can not be viewed. They are part of the process of deconstructing polygons into convex polygons, which begins in my case by using ear cutting into triangles. Checking potential ears requires checking the windedness of the intermediate triangles, but using the normal of the original polygon.
If I had taken the time to deconstruct the problem mentally in more detail I would have been able to describe what I needed better. But I kept distracting myself with Mystery Science Theater 3000.
Thank you all.
L. Spiro
What I have to do is supply the known normal and use that, which does make my test much faster.
The triangles are not used for graphics and can not be viewed. They are part of the process of deconstructing polygons into convex polygons, which begins in my case by using ear cutting into triangles. Checking potential ears requires checking the windedness of the intermediate triangles, but using the normal of the original polygon.
If I had taken the time to deconstruct the problem mentally in more detail I would have been able to describe what I needed better. But I kept distracting myself with Mystery Science Theater 3000.
Thank you all.
L. Spiro
So basically the normal of the polygon defines what is front and what is back. Then the inverted normal would be the direction that a camera had to look to see the front-side of the polygon. Now calculate 2D-corrdinates for the vertices in the plane of the polygon (perpendicular to the normal) and you can use formula (2.6) from the GL-spec to calculate the *signed* area of a triangle and of the polygon. If both have the same sign, the order of their vertices will also be the same.
Quote:Original post by YogurtEmperor
Are you sure about that formula?
cross( (b-a),(c-a) ) == normal, so dot( cross( (b-a),(c-a) ), normal ) always evaluates to a positive value.
I think you meant:
normal = cross( (b - a),(c - a) );
sign( dot( cross( normal, (b - a) ), (c - a) ) );
That is basically the method I am using.
For 2D is it very simple. All on one line. I was hoping there was something similar for 3D, but maybe there can be if I know the normal before-hand (which I do).
Thank you for your reply.
L. Spiro
Nope...It depends of how the normal has been defined. You should know what is the convention: there's nothing that restricts me to chose the opposite of cross( b-a, c-a ) as the normal of the triangle, since it is also a normal. Simply put, you cannot know the "windedness" of a triangle beforehand: it is arbitrary. You can make an assumption then compute them and display the model lit, to validate it.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement