Hello,

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:}