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