Incorrect value from Triangulator.DetermineWindingOrder

[Videogamers0]

I use the following method to generate vertices for a 5-point star shape:

        private static List<Vector2> Get5PointStarVertices(Rectangle Region)
        {
            float InnerRadius = Region.Width / 5.0f;
            float OuterRadius = Region.Width / 2.0f;

            float Ang36 = (float)(Math.PI / 5.0);   // 36° x PI/180
            float Ang72 = 2.0f * Ang36;     // 72° x PI/180
            float Sin36 = (float)Math.Sin(Ang36);
            float Sin72 = (float)Math.Sin(Ang72);
            float Cos36 = (float)Math.Cos(Ang36);
            float Cos72 = (float)Math.Cos(Ang72);

            Vector2 Center = new Vector2((Region.Left + Region.Right) / 2.0f, (Region.Top + Region.Bottom) / 2.0f);

            List<Vector2> Vertices = new(10);

            float YOffset = InnerRadius / 8;

            //  Top of the star: 12:00 hours
            Vertices.Add(new Vector2(Center.X, Center.Y - OuterRadius + YOffset));

            //  Right-side vertices
            Vertices.Add(new Vector2(Center.X + InnerRadius * Sin36, Center.Y - InnerRadius * Cos36 + YOffset));
            Vertices.Add(new Vector2(Region.Right, Center.Y - InnerRadius * Cos36 + YOffset));
            Vertices.Add(new Vector2(Center.X + InnerRadius * Sin72, Center.Y + InnerRadius * Cos72 + YOffset));
            Vertices.Add(new Vector2(Center.X + OuterRadius * Sin36 + InnerRadius / 2, Center.Y + OuterRadius * Cos36 + YOffset));

            //  Bottom-center of the star: 6:00 hours
            Vertices.Add(new Vector2(Center.X, Center.Y + InnerRadius + YOffset));

            //  Left-side vertices
            Vertices.Add(new Vector2(Center.X - OuterRadius * Sin36 - InnerRadius / 2, Center.Y + OuterRadius * Cos36 + YOffset));
            Vertices.Add(new Vector2(Center.X - InnerRadius * Sin72, Center.Y + InnerRadius * Cos72 + YOffset));
            Vertices.Add(new Vector2(Region.Left, Center.Y - InnerRadius * Cos36 + YOffset));
            Vertices.Add(new Vector2(Center.X - InnerRadius * Sin36, Center.Y - InnerRadius * Cos36 + YOffset));

            return Vertices;
        }

Then, using the following code:

List<Vector2> StarVertices = Get5PointStarVertices(new(0, 0, 256, 256));
WindingOrder Order1 = Triangulator.DetermineWindingOrder(StarVertices.ToArray());
WindingOrder Order2 = Triangulator.DetermineWindingOrder(StarVertices.Reverse<Vector2>().ToArray());

Both Order1 and Order2 result in WindingOrder.Clockwise. Shouldn't they be different values? This is causing me unexpected results when I use PrimitiveDrawing.DrawSolidPolygon

[Chestnut45]

I've been having some similar issues with the PrimitiveDrawing class, here's what I've been able to find out so far:

• The param info for Triangulator.Triangulate() says that the inputVertices should be passed in CCW winding order (which is the desired order passed by DrawSolidPolygon().

• However, there's a redundant check at the top of the function that means it should work no matter which winding order your inputVertices are:
  

It seems that it could be replaced with this (though this wouldn't fix the problem, I feel it's a bit cleaner):

outputVertices = EnsureWindingOrder(inputVertices, WindingOrder.CounterClockwise);

The main problem does look to be DetermineWindingOrder():

If I'm not entirely mistaken, this is just a complete mess, and is trying to do 2 (or more) methods at once. It should be able to be simplified to something like this:

float sum = 0;
Vector2 v1 = vertices[vertices.Length - 1];

for (int i = 0; i < vertices.Length; i++)
{
    Vector2 v2 = vertices[i];
    sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    v1 = v2;
}

// The return condition may have to be inverted if we have an inverted y-axis
return sum > 0 ? WindingOrder.Clockwise : WindingOrder.CounterClockwise;

I'm fairly certain that this is an improvement (or at least still correct), and my guess would be that it would fix the problems we're having, but I've never extended or contributed to a library before, so I have no idea how to go about testing these 'fixes' to see if I'm completely wrong, so I hope just posting it here may be helpful :)

[EDIT]: Complete brainfart, I'll just clone and test these changes to see if they fix anything after lunch, will report back :)

[Chestnut45]

Confirmed, I was able to reproduce your exact issue, the code above does resolve it, and returns a different winding direction as expected. It'll have to be run against all of the tests to make sure nothing else was relying on that funky behaviour, but it also happens to be nearly twice as fast as well!

On my machine, timed with a Stopwatch, using Stopwatch.Elapsed.TotalMilliseconds:
old code took 0.0128ms
new code took 0.0074ms

[Videogamers0]

Interesting findings thank you for investigating this. So it looks like the issue is DetermineWindingOrder giving unreliable results when clockWiseCount == counterClockWiseCount, which happens to be the case with star shapes like the one I'm generating that make an equal number of right and left turns while traversing the outline. Your algorithm appears to be the universally accepted one (https://stackoverflow.com/a/1165943 , https://stackoverflow.com/a/18472899) that works on my shapes.

[Chestnut45]

That sounds about right, I'm glad I could help! Although, the issue likely also stems from the fact that the old algorithm discarded information about how much each vertex was CW/CCW, since you could have a situation where you make a larger number of small left turns, but a few large right turns, which could more than make up the difference when considering the average amount turned.

I can't imagine this would break anything else, but either way, I'll do my best to find out how to build the whole project and run the tests to make sure it doesn't. I'm on Ubuntu using VSCode so I can't just use the VS solution file. A problem to solve tomorrow, I suppose!

Cheers :)