R6.6 is the Xorg base-lineXORG-MAIN

1 files changed, 398 insertions, 0 deletions

diff --git a/mi/mipolyutil.c b/mi/mipolyutil.c
new file mode 100644
index 000000000..879bd6e1d
--- /dev/null
+++ b/mi/mipolyutil.c
@@ -0,0 +1,398 @@
+/***********************************************************
+
+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.
+
+
+Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
+
+                        All Rights Reserved
+
+Permission to use, copy, modify, and distribute this software and its 
+documentation for any purpose and without fee is hereby granted, 
+provided that the above copyright notice appear in all copies and that
+both that copyright notice and this permission notice appear in 
+supporting documentation, and that the name of Digital not be
+used in advertising or publicity pertaining to distribution of the
+software without specific, written prior permission.  
+
+DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
+ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
+DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
+ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
+WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
+ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
+SOFTWARE.
+
+******************************************************************/
+/* $Xorg: mipolyutil.c,v 1.4 2001/02/09 02:05:21 xorgcvs Exp $ */
+#include "miscstruct.h"
+#include "gc.h"
+#include "miscanfill.h"
+#include "mipoly.h"
+
+#define MAXINT 0x7fffffff
+#define MININT -MAXINT
+
+/*
+ *     fillUtils.c
+ *
+ *     Written by Brian Kelleher;  Oct. 1985
+ *
+ *     This module contains all of the utility functions
+ *     needed to scan convert a polygon.
+ *
+ */
+
+/*
+ *     InsertEdgeInET
+ *
+ *     Insert the given edge into the edge table.
+ *     First we must find the correct bucket in the
+ *     Edge table, then find the right slot in the
+ *     bucket.  Finally, we can insert it.
+ *
+ */
+Bool
+miInsertEdgeInET(ET, ETE, scanline, SLLBlock, iSLLBlock)
+    EdgeTable *ET;
+    EdgeTableEntry *ETE;
+    int scanline;
+    ScanLineListBlock **SLLBlock;
+    int *iSLLBlock;
+{
+    register EdgeTableEntry *start, *prev;
+    register ScanLineList *pSLL, *pPrevSLL;
+    ScanLineListBlock *tmpSLLBlock;
+
+    /*
+     * find the right bucket to put the edge into
+     */
+    pPrevSLL = &ET->scanlines;
+    pSLL = pPrevSLL->next;
+    while (pSLL && (pSLL->scanline < scanline)) 
+    {
+        pPrevSLL = pSLL;
+        pSLL = pSLL->next;
+    }
+
+    /*
+     * reassign pSLL (pointer to ScanLineList) if necessary
+     */
+    if ((!pSLL) || (pSLL->scanline > scanline)) 
+    {
+        if (*iSLLBlock > SLLSPERBLOCK-1) 
+        {
+            tmpSLLBlock = 
+		  (ScanLineListBlock *)xalloc(sizeof(ScanLineListBlock));
+	    if (!tmpSLLBlock)
+		return FALSE;
+            (*SLLBlock)->next = tmpSLLBlock;
+            tmpSLLBlock->next = (ScanLineListBlock *)NULL;
+            *SLLBlock = tmpSLLBlock;
+            *iSLLBlock = 0;
+        }
+        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
+
+        pSLL->next = pPrevSLL->next;
+        pSLL->edgelist = (EdgeTableEntry *)NULL;
+        pPrevSLL->next = pSLL;
+    }
+    pSLL->scanline = scanline;
+
+    /*
+     * now insert the edge in the right bucket
+     */
+    prev = (EdgeTableEntry *)NULL;
+    start = pSLL->edgelist;
+    while (start && (start->bres.minor < ETE->bres.minor)) 
+    {
+        prev = start;
+        start = start->next;
+    }
+    ETE->next = start;
+
+    if (prev)
+        prev->next = ETE;
+    else
+        pSLL->edgelist = ETE;
+    return TRUE;
+}
+
+/*
+ *     CreateEdgeTable
+ *
+ *     This routine creates the edge table for
+ *     scan converting polygons. 
+ *     The Edge Table (ET) looks like:
+ *
+ *    EdgeTable
+ *     --------
+ *    |  ymax  |        ScanLineLists
+ *    |scanline|-->------------>-------------->...
+ *     --------   |scanline|   |scanline|
+ *                |edgelist|   |edgelist|
+ *                ---------    ---------
+ *                    |             |
+ *                    |             |
+ *                    V             V
+ *              list of ETEs   list of ETEs
+ *
+ *     where ETE is an EdgeTableEntry data structure,
+ *     and there is one ScanLineList per scanline at
+ *     which an edge is initially entered.
+ *
+ */
+
+Bool
+miCreateETandAET(count, pts, ET, AET, pETEs, pSLLBlock)
+    register int count;
+    register DDXPointPtr pts;
+    EdgeTable *ET;
+    EdgeTableEntry *AET;
+    register EdgeTableEntry *pETEs;
+    ScanLineListBlock   *pSLLBlock;
+{
+    register DDXPointPtr top, bottom;
+    register DDXPointPtr PrevPt, CurrPt;
+    int iSLLBlock = 0;
+
+    int dy;
+
+    if (count < 2)  return TRUE;
+
+    /*
+     *  initialize the Active Edge Table
+     */
+    AET->next = (EdgeTableEntry *)NULL;
+    AET->back = (EdgeTableEntry *)NULL;
+    AET->nextWETE = (EdgeTableEntry *)NULL;
+    AET->bres.minor = MININT;
+
+    /*
+     *  initialize the Edge Table.
+     */
+    ET->scanlines.next = (ScanLineList *)NULL;
+    ET->ymax = MININT;
+    ET->ymin = MAXINT;
+    pSLLBlock->next = (ScanLineListBlock *)NULL;
+
+    PrevPt = &pts[count-1];
+
+    /*
+     *  for each vertex in the array of points.
+     *  In this loop we are dealing with two vertices at
+     *  a time -- these make up one edge of the polygon.
+     */
+    while (count--) 
+    {
+        CurrPt = pts++;
+
+        /*
+         *  find out which point is above and which is below.
+         */
+        if (PrevPt->y > CurrPt->y) 
+        {
+            bottom = PrevPt, top = CurrPt;
+            pETEs->ClockWise = 0;
+        }
+        else 
+        {
+            bottom = CurrPt, top = PrevPt;
+            pETEs->ClockWise = 1;
+        }
+
+        /*
+         * don't add horizontal edges to the Edge table.
+         */
+        if (bottom->y != top->y) 
+        {
+            pETEs->ymax = bottom->y-1;  /* -1 so we don't get last scanline */
+
+            /*
+             *  initialize integer edge algorithm
+             */
+            dy = bottom->y - top->y;
+            BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
+
+            if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock))
+	    {
+		miFreeStorage(pSLLBlock->next);
+		return FALSE;
+	    }
+
+            ET->ymax = max(ET->ymax, PrevPt->y);
+            ET->ymin = min(ET->ymin, PrevPt->y);
+            pETEs++;
+        }
+
+        PrevPt = CurrPt;
+    }
+    return TRUE;
+}
+
+/*
+ *     loadAET
+ *
+ *     This routine moves EdgeTableEntries from the
+ *     EdgeTable into the Active Edge Table,
+ *     leaving them sorted by smaller x coordinate.
+ *
+ */
+
+void
+miloadAET(AET, ETEs)
+    register EdgeTableEntry *AET, *ETEs;
+{
+    register EdgeTableEntry *pPrevAET;
+    register EdgeTableEntry *tmp;
+
+    pPrevAET = AET;
+    AET = AET->next;
+    while (ETEs) 
+    {
+        while (AET && (AET->bres.minor < ETEs->bres.minor)) 
+        {
+            pPrevAET = AET;
+            AET = AET->next;
+        }
+        tmp = ETEs->next;
+        ETEs->next = AET;
+        if (AET)
+            AET->back = ETEs;
+        ETEs->back = pPrevAET;
+        pPrevAET->next = ETEs;
+        pPrevAET = ETEs;
+
+        ETEs = tmp;
+    }
+}
+
+/*
+ *     computeWAET
+ *
+ *     This routine links the AET by the
+ *     nextWETE (winding EdgeTableEntry) link for
+ *     use by the winding number rule.  The final 
+ *     Active Edge Table (AET) might look something
+ *     like:
+ *
+ *     AET
+ *     ----------  ---------   ---------
+ *     |ymax    |  |ymax    |  |ymax    | 
+ *     | ...    |  |...     |  |...     |
+ *     |next    |->|next    |->|next    |->...
+ *     |nextWETE|  |nextWETE|  |nextWETE|
+ *     ---------   ---------   ^--------
+ *         |                   |       |
+ *         V------------------->       V---> ...
+ *
+ */
+void
+micomputeWAET(AET)
+    register EdgeTableEntry *AET;
+{
+    register EdgeTableEntry *pWETE;
+    register int inside = 1;
+    register int isInside = 0;
+
+    AET->nextWETE = (EdgeTableEntry *)NULL;
+    pWETE = AET;
+    AET = AET->next;
+    while (AET) 
+    {
+        if (AET->ClockWise)
+            isInside++;
+        else
+            isInside--;
+
+        if ((!inside && !isInside) ||
+            ( inside &&  isInside)) 
+        {
+            pWETE->nextWETE = AET;
+            pWETE = AET;
+            inside = !inside;
+        }
+        AET = AET->next;
+    }
+    pWETE->nextWETE = (EdgeTableEntry *)NULL;
+}
+
+/*
+ *     InsertionSort
+ *
+ *     Just a simple insertion sort using
+ *     pointers and back pointers to sort the Active
+ *     Edge Table.
+ *
+ */
+
+int
+miInsertionSort(AET)
+    register EdgeTableEntry *AET;
+{
+    register EdgeTableEntry *pETEchase;
+    register EdgeTableEntry *pETEinsert;
+    register EdgeTableEntry *pETEchaseBackTMP;
+    register int changed = 0;
+
+    AET = AET->next;
+    while (AET) 
+    {
+        pETEinsert = AET;
+        pETEchase = AET;
+        while (pETEchase->back->bres.minor > AET->bres.minor)
+            pETEchase = pETEchase->back;
+
+        AET = AET->next;
+        if (pETEchase != pETEinsert) 
+        {
+            pETEchaseBackTMP = pETEchase->back;
+            pETEinsert->back->next = AET;
+            if (AET)
+                AET->back = pETEinsert->back;
+            pETEinsert->next = pETEchase;
+            pETEchase->back->next = pETEinsert;
+            pETEchase->back = pETEinsert;
+            pETEinsert->back = pETEchaseBackTMP;
+            changed = 1;
+        }
+    }
+    return(changed);
+}
+
+/*
+ *     Clean up our act.
+ */
+void
+miFreeStorage(pSLLBlock)
+    register ScanLineListBlock   *pSLLBlock;
+{
+    register ScanLineListBlock   *tmpSLLBlock;
+
+    while (pSLLBlock) 
+    {
+        tmpSLLBlock = pSLLBlock->next;
+        xfree(pSLLBlock);
+        pSLLBlock = tmpSLLBlock;
+    }
+}