+++ /dev/null
-/* $XConsortium: mipoly.h,v 1.5 94/04/17 20:27:42 dpw Exp $ */
-/*
-
-Copyright (c) 1987 X Consortium
-
-Permission is hereby granted, free of charge, to any person obtaining
-a copy of this software and associated documentation files (the
-"Software"), to deal in the Software without restriction, including
-without limitation the rights to use, copy, modify, merge, publish,
-distribute, sublicense, and/or sell copies of the Software, and to
-permit persons to whom the Software is furnished to do so, subject to
-the following conditions:
-
-The above copyright notice and this permission notice shall be included
-in all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
-OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
-MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
-IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR
-OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
-ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-OTHER DEALINGS IN THE SOFTWARE.
-
-Except as contained in this notice, the name of the X Consortium shall
-not be used in advertising or otherwise to promote the sale, use or
-other dealings in this Software without prior written authorization
-from the X Consortium.
-
-*/
-
-
-/*
- * fill.h
- *
- * Created by Brian Kelleher; Oct 1985
- *
- * Include file for filled polygon routines.
- *
- * These are the data structures needed to scan
- * convert regions. Two different scan conversion
- * methods are available -- the even-odd method, and
- * the winding number method.
- * The even-odd rule states that a point is inside
- * the polygon if a ray drawn from that point in any
- * direction will pass through an odd number of
- * path segments.
- * By the winding number rule, a point is decided
- * to be inside the polygon if a ray drawn from that
- * point in any direction passes through a different
- * number of clockwise and counter-clockwise path
- * segments.
- *
- * These data structures are adapted somewhat from
- * the algorithm in (Foley/Van Dam) for scan converting
- * polygons.
- * The basic algorithm is to start at the top (smallest y)
- * of the polygon, stepping down to the bottom of
- * the polygon by incrementing the y coordinate. We
- * keep a list of edges which the current scanline crosses,
- * sorted by x. This list is called the Active Edge Table (AET)
- * As we change the y-coordinate, we update each entry in
- * in the active edge table to reflect the edges new xcoord.
- * This list must be sorted at each scanline in case
- * two edges intersect.
- * We also keep a data structure known as the Edge Table (ET),
- * which keeps track of all the edges which the current
- * scanline has not yet reached. The ET is basically a
- * list of ScanLineList structures containing a list of
- * edges which are entered at a given scanline. There is one
- * ScanLineList per scanline at which an edge is entered.
- * When we enter a new edge, we move it from the ET to the AET.
- *
- * From the AET, we can implement the even-odd rule as in
- * (Foley/Van Dam).
- * The winding number rule is a little trickier. We also
- * keep the EdgeTableEntries in the AET linked by the
- * nextWETE (winding EdgeTableEntry) link. This allows
- * the edges to be linked just as before for updating
- * purposes, but only uses the edges linked by the nextWETE
- * link as edges representing spans of the polygon to
- * drawn (as with the even-odd rule).
- */
-
-/*
- * for the winding number rule
- */
-#define CLOCKWISE 1
-#define COUNTERCLOCKWISE -1
-
-typedef struct _EdgeTableEntry {
- int ymax; /* ycoord at which we exit this edge. */
- BRESINFO bres; /* Bresenham info to run the edge */
- struct _EdgeTableEntry *next; /* next in the list */
- struct _EdgeTableEntry *back; /* for insertion sort */
- struct _EdgeTableEntry *nextWETE; /* for winding num rule */
- int ClockWise; /* flag for winding number rule */
-} EdgeTableEntry;
-
-
-typedef struct _ScanLineList{
- int scanline; /* the scanline represented */
- EdgeTableEntry *edgelist; /* header node */
- struct _ScanLineList *next; /* next in the list */
-} ScanLineList;
-
-
-typedef struct {
- int ymax; /* ymax for the polygon */
- int ymin; /* ymin for the polygon */
- ScanLineList scanlines; /* header node */
-} EdgeTable;
-
-
-/*
- * Here is a struct to help with storage allocation
- * so we can allocate a big chunk at a time, and then take
- * pieces from this heap when we need to.
- */
-#define SLLSPERBLOCK 25
-
-typedef struct _ScanLineListBlock {
- ScanLineList SLLs[SLLSPERBLOCK];
- struct _ScanLineListBlock *next;
-} ScanLineListBlock;
-
-/*
- * number of points to buffer before sending them off
- * to scanlines() : Must be an even number
- */
-#define NUMPTSTOBUFFER 200
-
-\f
-/*
- *
- * a few macros for the inner loops of the fill code where
- * performance considerations don't allow a procedure call.
- *
- * Evaluate the given edge at the given scanline.
- * If the edge has expired, then we leave it and fix up
- * the active edge table; otherwise, we increment the
- * x value to be ready for the next scanline.
- * The winding number rule is in effect, so we must notify
- * the caller when the edge has been removed so he
- * can reorder the Winding Active Edge Table.
- */
-#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
- if (pAET->ymax == y) { /* leaving this edge */ \
- pPrevAET->next = pAET->next; \
- pAET = pPrevAET->next; \
- fixWAET = 1; \
- if (pAET) \
- pAET->back = pPrevAET; \
- } \
- else { \
- BRESINCRPGONSTRUCT(pAET->bres); \
- pPrevAET = pAET; \
- pAET = pAET->next; \
- } \
-}
-
-
-/*
- * Evaluate the given edge at the given scanline.
- * If the edge has expired, then we leave it and fix up
- * the active edge table; otherwise, we increment the
- * x value to be ready for the next scanline.
- * The even-odd rule is in effect.
- */
-#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
- if (pAET->ymax == y) { /* leaving this edge */ \
- pPrevAET->next = pAET->next; \
- pAET = pPrevAET->next; \
- if (pAET) \
- pAET->back = pPrevAET; \
- } \
- else { \
- BRESINCRPGONSTRUCT(pAET->bres); \
- pPrevAET = pAET; \
- pAET = pAET->next; \
- } \
-}
-
-/* mipolyutil.c */
-
-extern Bool miInsertEdgeInET(
-#if NeedFunctionPrototypes
- EdgeTable * /*ET*/,
- EdgeTableEntry * /*ETE*/,
- int /*scanline*/,
- ScanLineListBlock ** /*SLLBlock*/,
- int * /*iSLLBlock*/
-#endif
-);
-
-extern Bool miCreateETandAET(
-#if NeedFunctionPrototypes
- int /*count*/,
- DDXPointPtr /*pts*/,
- EdgeTable * /*ET*/,
- EdgeTableEntry * /*AET*/,
- EdgeTableEntry * /*pETEs*/,
- ScanLineListBlock * /*pSLLBlock*/
-#endif
-);
-
-extern void miloadAET(
-#if NeedFunctionPrototypes
- EdgeTableEntry * /*AET*/,
- EdgeTableEntry * /*ETEs*/
-#endif
-);
-
-extern void micomputeWAET(
-#if NeedFunctionPrototypes
- EdgeTableEntry * /*AET*/
-#endif
-);
-
-extern int miInsertionSort(
-#if NeedFunctionPrototypes
- EdgeTableEntry * /*AET*/
-#endif
-);
-
-extern void miFreeStorage(
-#if NeedFunctionPrototypes
- ScanLineListBlock * /*pSLLBlock*/
-#endif
-);