Knowing if middle vertex is left or right when sorting a triangle vertices by Y?

Question

I'm reading Chris Hecker's Texture Mapping articles and for the life of me I can't understand how he's using the Y order of vertices to determine if the middle vertex was on the left or right.

Sorting code:

    if (Y0 < Y1)
    {
        if (Y2 < Y0)
        {
            Top = 2; Middle = 0; Bottom = 1;
            MiddleCompare = 0; BottomCompare = 1;
        }
        else
        {
            Top = 0;
            if (Y1 < Y2)
            {
                Middle = 1; Bottom = 2;
                MiddleCompare = 1; BottomCompare = 2;
            }
            else
            {
                Middle = 2; Bottom = 1;
                MiddleCompare = 2; BottomCompare = 1;
            }
        }
    }
    else
    {
        if (Y2 < Y1)
        {
            Top = 2; Middle = 1; Bottom = 0;
            MiddleCompare = 1; BottomCompare = 0;
        }
        else
        {
            Top = 1;
            if (Y0 < Y2)
            {
                Middle = 0; Bottom = 2;
                MiddleCompare = 3; BottomCompare = 2;
            }
            else
            {
                Middle = 2; Bottom = 0;
                MiddleCompare = 2; BottomCompare = 3;
            }
        }
    }

Then he writes:

if (BottomCompare > MiddleCompare)
{
    MiddleIsLeft = 0;
    Left = &TopToBottom; Right = &TopToMiddle;
}
else
{
    MiddleIsLeft = 1;
    Left = &TopToMiddle; Right = &TopToBottom;
}

My questions:

How are we relying on the Y order to tell if the middle vertex is left or right? It's really confusing cause the sorting is only done on Y, there was no mention of X.
Obviously, the BottomCompare and MiddleCompare variables exist to achieve the comparison. In the first half of the comparison (the 'if'), MiddleCompare equals Middle and BottomCompare equals Bottom. But in the second half (the 'else') BottomCompare equals 3 when Bottom equals 0, and MiddleCompare equals 3 when Middle equals 0. Why is that?

score 2 · Accepted Answer · edited Jun 20 '20 at 09:12

What you are missing is:

The polygon winding rule.

The vertexes of triangle/polygon should be in specific order CW/CCW.
You should deciding target side for line not for point.

Deciding single point would be mistake as some points are in both sides.

So for example if:

order is CW
x+ axis goes right
y+ axis goes down
vertexes are A,B,C

example

Then you decide the left/right side from the change in y axis. So while rasterizing any of the outlines (AB,BC,CA) you look at the y change between first and last point. For example AB line:

dy = (B.y-A.y)
if (dy> 0) right
if (dy< 0) left
if (dy==0) both

For more info see related Q/A closed convex polygon filling.

score 1 · Answer 2 · answered Apr 26 '16 at 06:16

Edit: I am too late after Spektre's answer, but I do not want to throw away my hand-drawn picture :)

It seems you have missed important part: triangle vertices are numbered in clockwise manner. So knowing of Y-order allows to reject impossible variants.

And value 3 of *Compare is used to provide cyclic order.

Example for Y0 < Y1. For clockwise order point 2 may lie in one of marked regions (at right hand of P0-P1 vector):

Knowing if middle vertex is left or right when sorting a triangle vertices by Y?

2 Answers2