--- /dev/null
+/***********************************************************
+
+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.
+
+
+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.
+
+******************************************************************/
+/* $XConsortium: mipolyutil.c,v 1.16 94/04/17 20:27:46 dpw 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.
+ *
+ */
+\f
+/*
+ * 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;
+}
+\f
+/*
+ * 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;
+}
+\f
+/*
+ * 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;
+ }
+}
+\f
+/*
+ * 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;
+}
+\f
+/*
+ * 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);
+}
+\f
+/*
+ * Clean up our act.
+ */
+void
+miFreeStorage(pSLLBlock)
+ register ScanLineListBlock *pSLLBlock;
+{
+ register ScanLineListBlock *tmpSLLBlock;
+
+ while (pSLLBlock)
+ {
+ tmpSLLBlock = pSLLBlock->next;
+ xfree(pSLLBlock);
+ pSLLBlock = tmpSLLBlock;
+ }
+}
projects / rdpsrv / blobdiff