pottle@batcomputer.tn.cornell.edu (Chris Pottle) (02/18/89)
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 vaguely remember a posting here a couple of years ago, so I know at least one exists. I'd appreciate hearing from you if you can provide a reference. Chris Pottle pottle@tesla.ee.cornell.edu
tonyw@microsoft.UUCP (Tony Williams) (02/24/89)
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
ritter@versatc.UUCP (Jack Ritter) (02/25/89)
> > 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. I recently implemented this algorithim. It breaks up an arbitrary self-intersecting polygon into a minimum number of trapezoids. I did all calculations in fixed point (eg, intercept calc and intersection calc.). It is FAST!!! I used quick sort for both active edge list sort and initial y sort. You must be careful of intersections and intercepts rounding down to an end point. For anyone interested in doing this algo: first get it to work on a 5 point star, draw within a SMALL area, such as 5 units by 5 units. This will create most of the rounding down/up problems. Once this works, you have yourself a robust mother. -- -> Even aliens think The Three Stooges are funny. <- Jack Ritter, S/W Eng. Versatec, 2710 Walsh Av, Santa Clara, CA 95051 Mail Stop 1-7. (408)982-4332, or (408)988-2800 X 5743 UUCP: {pyramid,mips,vsi1,arisia}!versatc!ritter