Path: utzoo!attcan!uunet!microsoft!tonyw
From: tonyw@microsoft.UUCP (Tony Williams)
Newsgroups: comp.graphics
Subject: Re: Looking for Polygon Dissection Algorithm
Message-ID: <726@microsoft.UUCP>
Date: 23 Feb 89 22:06:56 GMT
References: <7422@batcomputer.tn.cornell.edu>
Reply-To: tonyw@microsoft.UUCP (Tony Williams)
Organization: Microsoft Corp., Redmond WA
Lines: 21

In article <7422@batcomputer.tn.cornell.edu> pottle@tcgould.tn.cornell.edu (Chris Pottle) writes:
>We have constructed a graphics display based on scanline hardware which
>requires primitive objects which are trapezoids with horizontal bases.
>We are therefore seeking pointers to algorithms which dissect polygons
>into these primitives.

I am posting this rather than mailing, as I have not seen this reference
posted here before, and it really is the seminal paper on the subject.

"The Inside Story on Self-intersecting Polygons", Martin E Newell and
Carlo H sequin, Lambda, Second Quarter 1980.

This does exactly what you want.
Caveat:
If your hardware requires integer
coordinates for the trapezoid corners, you will see straight edges
being broken into a series of edges at slightly different angles.
To avoid this, the algorithm used to generate the non-horizontal edges
should either permit fractional coordinates or provide for a specifiable
initial error term (eg in DDA algorithms).
   Tony