Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utcs!mnetor!seismo!columbia!topaz!ll-xn!cit-vax!nike!ucbcad!ucbvax!ucsfcgl!pixar!ph
From: ph@pixar.UUCP
Newsgroups: net.graphics
Subject: Re: Decomposing a polygon into a buncha trapezoids
Message-ID: <2940@pixar.pixar>
Date: Wed, 16-Jul-86 16:30:29 EDT
Article-I.D.: pixar.2940
Posted: Wed Jul 16 16:30:29 1986
Date-Received: Fri, 18-Jul-86 00:55:22 EDT
References: <115@tslvax.UUCP>
Distribution: net
Organization: Pixar -- Marin County, California
Lines: 32
Summary: scan converting concave polygons

Timothy Beres (tim@tslvax.uucp) asks how to decompose a concave polygon
into triangles and trapezoids with horizontal top and bottom.
I think the best approach would be a scan conversion algorithm.
Below is the outline of a simple scan converter for concave polygons which
has worked well for me; it could easily be modified to output trapezoids
and triangles.

To scan convert polygon having n vertices X[i] Y[i]:

create y-sorted array of indices ind[k] into vertex list: Y[ind[k-1]]<Y[ind[k]]
for (k=0, y=ymin; y<=ymax; y++) {
    /* maintain list of currently active polygon edges crossing scan line y */
    for (; k<n && Y[ind[k]]<=y; k++) {
	i = ind[k]
	/* invariant: y-1 < Y[i] <= y */
	insert or delete edges before and after vertex i (i-1 to i and i to i+1)
	    from active list if they cross scan line y
    }
    sort list of m active polygon edges by x of intersection point with line y
    for (j=0; j<m; j+=2) {
	/* span between j and j+1 is inside, span from j+1 and j+2 is outside */
	draw pixels between active[j].x and active[j+1].x
    }
}

This scan conversion algorithm requires no special cases for horizontal edges
as many others do.
-- 
Paul Heckbert
Pixar				415-499-3600
P.O. Box 13719			UUCP: {sun,ucbvax}!pixar!ph
San Rafael, CA 94913		ARPA: ph%pixar.uucp@ucbvax.berkeley.edu