Vertex winding order (counter clockwise oder vertex) - algorithm

This topic is 3340 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi, I have some codes to re-ordering my vertex to insure they are in the correct order. It work fine with a cube, but in some other cases it reverse the order and it shouldn't. What I do : ----------- 1 - I get the 3 triangle vertices vertex0, vertex1, vertex2 2 - I comput the normalized vector between the "volume" (and not the triangle face) and vertex0 (referenceNormal) 3 - I calculate the center of the triangle (centerVertex) 4 - I calculate the refVector = (vertex0 - centerVertex) 5 - for each vertex, I calculate the signed angle between refVector and the current vertex (based on referenceNormal). 6 - I sort the triangle indices based on the angles Here is the code :
override protected void UpdateVertexWinding()
{
for (int index = 0; index < (Indices.Count / 3); index++)
{
int indice0 = Indices[index * 3];
int indice1 = Indices[index * 3 + 1];
int indice2 = Indices[index * 3 + 2];

Vector3 vertex0 = Vertices[indice0];
Vector3 vertex1 = Vertices[indice1];
Vector3 vertex2 = Vertices[indice2];

// Compute the (normalized) vector from the center point (of surface) to this vertex.
Vector3 referenceNormal = Vertices[indice0] - _boundingBox.Center;
referenceNormal.Normalize();

// Center
Vector3 centerVertex = (vertex0 + vertex1 + vertex2) / 3;

// Angles
double[] angles = new double[3];
int[] indices = new int[3];
Vector3 refVector = vertex0 - centerVertex;
refVector.Normalize();

angles[0] = 0;
indices[0] = indice0;

angles[1] = refVector.SignedAngle3D(vertex1 - centerVertex, referenceNormal);
indices[1] = indice1;

angles[2] = refVector.SignedAngle3D(vertex2 - centerVertex, referenceNormal);
indices[2] = indice2;

// Sort
Array.Sort(angles, indices, new AngleComparer());

Indices[index * 3] = indices[0];
Indices[index * 3 + 1] = indices[1];
Indices[index * 3 + 2] = indices[2];
}
}

public double SignedAngle3D(Vector3 v2, Vector3 normal)
{
double a1 = this.Cross(v2).Dot(normal);
double a2 = this.Dot(v2);

return System.Math.Atan2(a1, a2);
}



Share on other sites
The way to do it is to have a line from the triangle center into some far away direction and count the number of intersection with other triangles. If there is no intersection or the number is even = vertex order is good
otherwise, change vertex order.

Share on other sites
Hi,

Can you describe the steps please ?

(I don't understand about the triangles, which triangles are you talking about ?)

Share on other sites
Quote:
 Original post by viewon01(I don't understand about the triangles, which triangles are you talking about ?)

The other triangles in the mesh (i.e. in your cube you'd have 12 triangles). If you extend a line from the tri center along the face normal you generate, if you intersect 1 other triangle it must be pointing inwards. If you don't, you've got the correct vertex order.

It's not as simple as saying 1 or 0, since the mesh may curve in on itself. So, if you hit an even number (eg 0,2,4) the order is correct. If you hit an odd number the order needs to be reversed.

Share on other sites
Thanks,

I understand now... it sounds logic.

It is a lot of intersections, if I have 1000 triangles, I have to check 1000 x 999 triangles intersection :-P

1. 1
2. 2
3. 3
Rutin
14
4. 4
frob
12
5. 5

• 9
• 9
• 11
• 11
• 23
• Forum Statistics

• Total Topics
633670
• Total Posts
3013262
×