Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is my first question in math and if I cannot get it right for the first time, please forgive me. I'm working on a simulation and I need to order vertices of a triangle in counter-clockwise manner.

I'm reading these vertices from an STL file, which provides the three vertices and pre-calculated normals of the triangles that define an object. IOW, I have triangulation data for a 3D solid.

I can do the ordering with calculating the normal of the triangle using the vertices and trying to equalize the signs of the normal vector with the provided one in the file.

I wonder whether there's another way to find the correct order using nothing but the vertices.

Thanks in advance.

share|improve this question
    
What do you mean by "expected" normals? Can you elaborate on the problem? –  yohBS Feb 15 '12 at 10:03
    
What is "the correct order"? Three vertices in three dimensions can't be ordered counterclockwise per se, only with respect to a selected orientation of the triangle given e.g. by a normal. So if you don't want to use the normals, there must be some other way to define which is "the correct order". Perhaps you want the order to be counterclockwise with respect to the outward normal with respect to the entire solid? Clearly you can't find that from only the vertices of a single triangle, since the triangle could just as well be part of a different solid with the opposite outward normal. –  joriki Feb 15 '12 at 11:17
    
However, if by "using nothing but the vertices" you mean all the vertices, not just the ones for this triangle, and if you know that the solid is convex, then you could take any other vertex of the solid as a fourth vertex (one that isn't coplanar with the triangle, in case that's a possibility), compute the scalar triple product of the three vectors from the three vertices to the fourth, and determine the order according to its sign. –  joriki Feb 15 '12 at 11:24
add comment

1 Answer 1

up vote 0 down vote accepted

If you know from the start that the triangles form a triangulation of an orientable surface (i.e. any two triangles are either disjoint, have a vertex in common, or have an edge in common, and the triangles having a given vertex in common share edges in a cyclic way) then you can pick one of the triangles, say $\Delta:=\{a,b,c\}$, and orient it at will. By orienting I mean that one cyclic order, e.g., $a\to b\to c\to a$, of the vertices is declared positive, the other negative. Starting from this seed orient all other triangles coherently. This means the following: When two triangles $\Delta_1:=\{a,b,c\}$ and $\Delta_2:=\{a,b,d\}$ with $c\ne d$ share an edge $\{a,b\}$ then the orientation of this edge in $\Delta_1$ should be opposite to its orientation in $\Delta_2$.

share|improve this answer
    
It helped a lot, thanks. –  SilentStorm Feb 15 '12 at 18:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.