Jump to content
  • Advertisement
Sign in to follow this  
polar01

Vertex winding order (counter clockwise oder vertex) - algorithm

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
Hi,

Thanks for your answer.

I dont't understand your explanation...

Can you describe the steps please ?

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

Thanks for your help

Share this post


Link to post
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 this post


Link to post
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

Thanks for your advice

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!