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