Why is my clockwise sorting of Vector3s inconsistent?

Question

I've attempted to write a Comparer class for Vector3s (or, rather, VertexPositionNormalTextures) which will sort a list of them into clockwise order in order to fix my backface culling issues. I've tried to adapt a very common method on the web which gets a signed angle between two vectors. However, at runtime my list complains that the sorting method is inconsistent, which is to say that either two items are compared inconsistently on different passes, or an item is compared to itself and not found equal.

Here's the comparer class:

public class ClockwiseSorter : IComparer<VertexPositionNormalTexture>
    {
        private Vector3 center;
        public ClockwiseSorter(Vector3 c)
        {
            center = c;
        }
        public int Compare(VertexPositionNormalTexture a, VertexPositionNormalTexture b)
        {
            Vector3 normal = Vector3.Cross(a.Position - center, b.Position - center);
            normal.Normalize();
            double theta = GetSignedAngleBetween2DVectors(a.Position - center, b.Position - center, Vector3.Cross(a.Position - center, normal));

            if (theta > 0)
                return -1;
            else if (theta < 0)
                return 1;
            else
                return 0;
        }

        /// Find the angle between two vectors. This will not only give the angle difference, but the direction.
        /// For example, it may give you -1 radian, or 1 radian, depending on the direction. Angle given will be the 
        /// angle from the FromVector to the DestVector, in radians.
        /// </summary>
        /// <param name="FromVector">Vector to start at.</param>
        /// <param name="DestVector">Destination vector.</param>
        /// <param name="DestVectorsRight">Right vector of the destination vector</param>
        /// <returns>Signed angle, in radians</returns>        
        /// <remarks>All three vectors must lie along the same plane.</remarks>
        public static double GetSignedAngleBetween2DVectors(Vector3 FromVector, Vector3 DestVector, Vector3 DestVectorsRight)
        {
            FromVector.Normalize();
            DestVector.Normalize();
            DestVectorsRight.Normalize();

            float forwardDot = Vector3.Dot(FromVector, DestVector);
            float rightDot = Vector3.Dot(FromVector, DestVectorsRight);

            // Keep dot in range to prevent rounding errors
            forwardDot = MathHelper.Clamp(forwardDot, -1.0f, 1.0f);

            double angleBetween = Math.Acos(forwardDot);

            if (rightDot < 0.0f)
                angleBetween *= -1.0f;

            return angleBetween;
        }

    }

I get the center vector by averaging the values of all the vectors:

        private Vector3 AverageVectors(List<VertexPositionNormalTexture> vectors)
    {
        Vector3 sum = Vector3.Zero;
        foreach (VertexPositionNormalTexture vector in vectors)
            sum += vector.Position;
        return (sum / vectors.Count);
    }

Am I screwing up somewhere, not thinking about this correctly? Or have I calculated the normal or center incorrectly? Backface culling has been nothing but a headache for me, I'm kind of desperate to move on...

Answer 1

If you have a triangle with vertex A,B and C,

the triangle normal is calcultated with the cross product operation

N = (B-A) x (C-A)

now you have to determine what direction is facing the normal.

for this can be useful the center of the mesh as you use in your code, though if mesh is not convex it can provide erroneous results.

You have to determine the angle between the normal and the vector build from the center of triangle to the center of the mesh.

TriangleCenter= (A+B+C) / 3;

P = MeshCenter - TriangleCenter;

P.Normalize();
N.Normalize();

the dot product  d = P.N = |P||N|.cos(alfa)

if (d>0) P and N are in the same direction  (AntiClockWise order) 
if (d<0) P and N are in opposite direction  (Clockwise order)