1 files changed, 228 insertions, 0 deletions
diff --git a/mi/mipoly.h b/mi/mipoly.h
new file mode 100644
index 000000000..d946388a6
--- /dev/null
+++ b/mi/mipoly.h
@@ -0,0 +1,228 @@
+/* $Xorg: mipoly.h,v 1.4 2001/02/09 02:05:21 xorgcvs Exp $ */
+/*
+
+Copyright 1987, 1998  The Open Group
+
+Permission to use, copy, modify, distribute, and sell this software and its
+documentation for any purpose is hereby granted without fee, provided that
+the above copyright notice appear in all copies and that both that
+copyright notice and this permission notice appear in supporting
+documentation.
+
+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 OPEN GROUP 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 Open Group 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 Open Group.
+
+*/
+
+
+/*
+ *     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
+
+
+/*
+ *
+ *     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
+);