Very Computer

I've been writing a simple software polygon drawing routine (which
only works on convex polygons) and while implementing clipping (with
the Sutherland algorithm) I noticed polygons were being generated
which caused my routine to choke.

The problem is detecting which side is left and which side is right
when scanning from the top vertex.

Some of the polygons that were being generated had the following
characteristics:

- Repeated vertices (the same vertex appears twice either right after
the first occurance, or somewhere else in the vertex list.)
- Two non-top vertices with identical X coordinates.

By adding an extra check to my code, I could cope with the first
problem, but the solution to the second is eluding me.

For example, consider this vertex list:

(-29,-30),(-26,-18),(-26,-29)

Once my polygon drawing routine locates the top vertex, it cannot
determine which edge is left and which is right because the X
coordinates of the non-top vertices are exactly the same.

I think I may be able to just compare Y vertices in cases where X2 -
X1 = 0, but that seems like a bit of a kludge. Is there a more elegant
(less comparisons and "special cases") way?

Note that my vertex lists are not guaranteed to be ordered clock wise.
The only requirement is that each point connects to its neighbors (the
last vertex connects to the first.)

advance :)

Below is my DrawPolygon() routine. Troublesome polygons end up having
the xstart and xend elements swapped in the span list and cannot be
rendered without overflowing video memory. I'd prefer not to do any
checks within the DrawSpans() function to keep its inner-loop as tight
as possible.

void DrawSolidPolygon(INT32 xo, INT32 yo, UINT8 color, UINT32 xpitch,
UINT8 *vidbuf, POLYGON *p)
{
    SPAN    span_list[MAX_SPANS], *working_span_list_ptr;
    INT32   i, j, top_index, top_y, bottom_y, forward_side, flat_top;

    /*
     * Polygons with less than 3 vertices aren't really polygons
     */

    if (p->num_vertices < 3)
        return;

    /*
     * Find the top and bottom vertices
     */

    top_y = bottom_y = p->vertex_list[0].y; // initialize to something
valid
    top_index = 0;
    for (i = 1; i < p->num_vertices; i++)
    {
        if (p->vertex_list[i].y < top_y)
        {
            top_y = p->vertex_list[i].y;
            top_index = i;
        }
        else if (p->vertex_list[i].y > bottom_y)
            bottom_y = p->vertex_list[i].y;
    }

    /*
     * Next, we must determine which side of the polygon is which. The
     * forward_side flag will be set to 1 if traversing the vertex
list
     * forward moves down the left side of the polygon, otherwise it
will
     * be set to 0.
     *
     * flat_top indicates we have a flat top, in which case we will
have to
     * compare the X coordinates of the 2 flat top vertices. If the X
and Y
     * are both the same as top_index's Y, we do not count it as a
flat top
     * because that ends up causing problems (this situation occurs a
lot with
     * clipping code.)
     */

    flat_top = 0;
    for (i = top_index; p->vertex_list[i].y == top_y; )
    {        
        if (i != top_index && p->vertex_list[i].x !=
p->vertex_list[top_index].x) // obviously we have another vertex with
Y==top_y
            flat_top = 1;   // which means there is a flat top to this
polygon
        INDEX_FORWARD(i);
        if (i == top_index) // infinite loop! all vertices have Y ==
top_y
            break;
    }
    for (j = top_index; p->vertex_list[j].y == top_y; )
    {
        if (j != top_index && p->vertex_list[j].x !=
p->vertex_list[top_index].x)
            flat_top = 1;
        INDEX_BACKWARD(j);
        if (j == top_index)
            break;
    }

    if (flat_top)       // back up to the last vertex with Y == top_y
    {
        INDEX_BACKWARD(i);
        INDEX_FORWARD(j);
    }

    forward_side = (p->vertex_list[i].x - p->vertex_list[j].x) >> 31;
    forward_side &= 1;

    /*
     * Now scan! First, we scan forward, then we scan backward.
     */

    working_span_list_ptr = span_list;
    i = top_index;
    do
    {
        j = i;
        INDEX_FORWARD(i);
        ScanEdge(p->vertex_list[j].x + xo, p->vertex_list[j].y,
                 p->vertex_list[i].x + xo, p->vertex_list[i].y,
                 forward_side, working_span_list_ptr);
        working_span_list_ptr += abs(p->vertex_list[j].y -
p->vertex_list[i].y);
    }
    while (p->vertex_list[i].y != bottom_y);

    working_span_list_ptr = span_list;
    i = top_index;
    forward_side = !forward_side;
    do
    {
        j = i;
        INDEX_BACKWARD(i);
        ScanEdge(p->vertex_list[j].x + xo, p->vertex_list[j].y,
                 p->vertex_list[i].x + xo, p->vertex_list[i].y,
                 forward_side, working_span_list_ptr);
        working_span_list_ptr += abs(p->vertex_list[j].y -
p->vertex_list[i].y);
    }
    while (p->vertex_list[i].y != bottom_y);

    /*
     * Render the spans
     */

    DrawSpans(yo + top_y, color, bottom_y - top_y, xpitch, vidbuf,
span_list);

Quote:}