4c221b0da1816acf2ca302b10092df059484468dvboxsyncCopyright 1987, 1998 The Open Group
4c221b0da1816acf2ca302b10092df059484468dvboxsyncPermission to use, copy, modify, distribute, and sell this software and its
4c221b0da1816acf2ca302b10092df059484468dvboxsyncdocumentation for any purpose is hereby granted without fee, provided that
4c221b0da1816acf2ca302b10092df059484468dvboxsyncthe above copyright notice appear in all copies and that both that
4c221b0da1816acf2ca302b10092df059484468dvboxsynccopyright notice and this permission notice appear in supporting
4c221b0da1816acf2ca302b10092df059484468dvboxsyncdocumentation.
4c221b0da1816acf2ca302b10092df059484468dvboxsyncThe above copyright notice and this permission notice shall be included
4c221b0da1816acf2ca302b10092df059484468dvboxsyncin all copies or substantial portions of the Software.
4c221b0da1816acf2ca302b10092df059484468dvboxsyncTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
4c221b0da1816acf2ca302b10092df059484468dvboxsyncOR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
4c221b0da1816acf2ca302b10092df059484468dvboxsyncMERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
4c221b0da1816acf2ca302b10092df059484468dvboxsyncIN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
4c221b0da1816acf2ca302b10092df059484468dvboxsyncOTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
4c221b0da1816acf2ca302b10092df059484468dvboxsyncARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
4c221b0da1816acf2ca302b10092df059484468dvboxsyncOTHER DEALINGS IN THE SOFTWARE.
4c221b0da1816acf2ca302b10092df059484468dvboxsyncExcept as contained in this notice, the name of The Open Group shall
4c221b0da1816acf2ca302b10092df059484468dvboxsyncnot be used in advertising or otherwise to promote the sale, use or
4c221b0da1816acf2ca302b10092df059484468dvboxsyncother dealings in this Software without prior written authorization
4c221b0da1816acf2ca302b10092df059484468dvboxsyncfrom The Open Group.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * Created by Brian Kelleher; Oct 1985
4c221b0da1816acf2ca302b10092df059484468dvboxsync * Include file for filled polygon routines.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * These are the data structures needed to scan
4c221b0da1816acf2ca302b10092df059484468dvboxsync * convert regions. Two different scan conversion
4c221b0da1816acf2ca302b10092df059484468dvboxsync * methods are available -- the even-odd method, and
4c221b0da1816acf2ca302b10092df059484468dvboxsync * the winding number method.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * The even-odd rule states that a point is inside
4c221b0da1816acf2ca302b10092df059484468dvboxsync * the polygon if a ray drawn from that point in any
4c221b0da1816acf2ca302b10092df059484468dvboxsync * direction will pass through an odd number of
4c221b0da1816acf2ca302b10092df059484468dvboxsync * path segments.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * By the winding number rule, a point is decided
4c221b0da1816acf2ca302b10092df059484468dvboxsync * to be inside the polygon if a ray drawn from that
4c221b0da1816acf2ca302b10092df059484468dvboxsync * point in any direction passes through a different
4c221b0da1816acf2ca302b10092df059484468dvboxsync * number of clockwise and counter-clockwise path
4c221b0da1816acf2ca302b10092df059484468dvboxsync * segments.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * These data structures are adapted somewhat from
4c221b0da1816acf2ca302b10092df059484468dvboxsync * the algorithm in (Foley/Van Dam) for scan converting
4c221b0da1816acf2ca302b10092df059484468dvboxsync * polygons.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * The basic algorithm is to start at the top (smallest y)
4c221b0da1816acf2ca302b10092df059484468dvboxsync * of the polygon, stepping down to the bottom of
4c221b0da1816acf2ca302b10092df059484468dvboxsync * the polygon by incrementing the y coordinate. We
4c221b0da1816acf2ca302b10092df059484468dvboxsync * keep a list of edges which the current scanline crosses,
4c221b0da1816acf2ca302b10092df059484468dvboxsync * sorted by x. This list is called the Active Edge Table (AET)
4c221b0da1816acf2ca302b10092df059484468dvboxsync * As we change the y-coordinate, we update each entry in
4c221b0da1816acf2ca302b10092df059484468dvboxsync * in the active edge table to reflect the edges new xcoord.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * This list must be sorted at each scanline in case
4c221b0da1816acf2ca302b10092df059484468dvboxsync * two edges intersect.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * We also keep a data structure known as the Edge Table (ET),
4c221b0da1816acf2ca302b10092df059484468dvboxsync * which keeps track of all the edges which the current
4c221b0da1816acf2ca302b10092df059484468dvboxsync * scanline has not yet reached. The ET is basically a
4c221b0da1816acf2ca302b10092df059484468dvboxsync * list of ScanLineList structures containing a list of
4c221b0da1816acf2ca302b10092df059484468dvboxsync * edges which are entered at a given scanline. There is one
4c221b0da1816acf2ca302b10092df059484468dvboxsync * ScanLineList per scanline at which an edge is entered.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * When we enter a new edge, we move it from the ET to the AET.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * From the AET, we can implement the even-odd rule as in
4c221b0da1816acf2ca302b10092df059484468dvboxsync * The winding number rule is a little trickier. We also
4c221b0da1816acf2ca302b10092df059484468dvboxsync * keep the EdgeTableEntries in the AET linked by the
4c221b0da1816acf2ca302b10092df059484468dvboxsync * nextWETE (winding EdgeTableEntry) link. This allows
4c221b0da1816acf2ca302b10092df059484468dvboxsync * the edges to be linked just as before for updating
4c221b0da1816acf2ca302b10092df059484468dvboxsync * purposes, but only uses the edges linked by the nextWETE
4c221b0da1816acf2ca302b10092df059484468dvboxsync * link as edges representing spans of the polygon to
4c221b0da1816acf2ca302b10092df059484468dvboxsync * drawn (as with the even-odd rule).
4c221b0da1816acf2ca302b10092df059484468dvboxsync * for the winding number rule
4c221b0da1816acf2ca302b10092df059484468dvboxsync BRESINFO bres; /* Bresenham info to run the edge */
4c221b0da1816acf2ca302b10092df059484468dvboxsync struct _EdgeTableEntry *next; /* next in the list */
4c221b0da1816acf2ca302b10092df059484468dvboxsync struct _EdgeTableEntry *back; /* for insertion sort */
4c221b0da1816acf2ca302b10092df059484468dvboxsync struct _EdgeTableEntry *nextWETE; /* for winding num rule */
4c221b0da1816acf2ca302b10092df059484468dvboxsynctypedef struct {
4c221b0da1816acf2ca302b10092df059484468dvboxsync * Here is a struct to help with storage allocation
4c221b0da1816acf2ca302b10092df059484468dvboxsync * so we can allocate a big chunk at a time, and then take
4c221b0da1816acf2ca302b10092df059484468dvboxsync * pieces from this heap when we need to.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * number of points to buffer before sending them off
4c221b0da1816acf2ca302b10092df059484468dvboxsync * to scanlines() : Must be an even number
4c221b0da1816acf2ca302b10092df059484468dvboxsync * a few macros for the inner loops of the fill code where
4c221b0da1816acf2ca302b10092df059484468dvboxsync * performance considerations don't allow a procedure call.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * Evaluate the given edge at the given scanline.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * If the edge has expired, then we leave it and fix up
4c221b0da1816acf2ca302b10092df059484468dvboxsync * the active edge table; otherwise, we increment the
4c221b0da1816acf2ca302b10092df059484468dvboxsync * x value to be ready for the next scanline.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * The winding number rule is in effect, so we must notify
4c221b0da1816acf2ca302b10092df059484468dvboxsync * the caller when the edge has been removed so he
4c221b0da1816acf2ca302b10092df059484468dvboxsync * can reorder the Winding Active Edge Table.
4c221b0da1816acf2ca302b10092df059484468dvboxsync#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
4c221b0da1816acf2ca302b10092df059484468dvboxsync * Evaluate the given edge at the given scanline.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * If the edge has expired, then we leave it and fix up
4c221b0da1816acf2ca302b10092df059484468dvboxsync * the active edge table; otherwise, we increment the
4c221b0da1816acf2ca302b10092df059484468dvboxsync * x value to be ready for the next scanline.
4c221b0da1816acf2ca302b10092df059484468dvboxsync * The even-odd rule is in effect.
4c221b0da1816acf2ca302b10092df059484468dvboxsync int /*count*/,