aboutsummaryrefslogtreecommitdiff
path: root/libX11/src/PolyReg.c
diff options
context:
space:
mode:
Diffstat (limited to 'libX11/src/PolyReg.c')
-rw-r--r--libX11/src/PolyReg.c1276
1 files changed, 638 insertions, 638 deletions
diff --git a/libX11/src/PolyReg.c b/libX11/src/PolyReg.c
index af367cf6f..74c8765fe 100644
--- a/libX11/src/PolyReg.c
+++ b/libX11/src/PolyReg.c
@@ -1,638 +1,638 @@
-/************************************************************************
-
-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.
-
-************************************************************************/
-
-#define LARGE_COORDINATE 1000000
-#define SMALL_COORDINATE -LARGE_COORDINATE
-
-#ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
-#include "Xlibint.h"
-#include "Xutil.h"
-#include <X11/Xregion.h>
-#include "poly.h"
-
-/*
- * 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.
- *
- */
-static void
-InsertEdgeInET(
- 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 *)Xmalloc(sizeof(ScanLineListBlock));
- (*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_axis < ETE->bres.minor_axis))
- {
- prev = start;
- start = start->next;
- }
- ETE->next = start;
-
- if (prev)
- prev->next = ETE;
- else
- pSLL->edgelist = ETE;
-}
-
-/*
- * 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.
- *
- */
-
-static void
-CreateETandAET(
- register int count,
- register XPoint *pts,
- EdgeTable *ET,
- EdgeTableEntry *AET,
- register EdgeTableEntry *pETEs,
- ScanLineListBlock *pSLLBlock)
-{
- register XPoint *top, *bottom;
- register XPoint *PrevPt, *CurrPt;
- int iSLLBlock = 0;
- int dy;
-
- if (count < 2) return;
-
- /*
- * initialize the Active Edge Table
- */
- AET->next = (EdgeTableEntry *)NULL;
- AET->back = (EdgeTableEntry *)NULL;
- AET->nextWETE = (EdgeTableEntry *)NULL;
- AET->bres.minor_axis = SMALL_COORDINATE;
-
- /*
- * initialize the Edge Table.
- */
- ET->scanlines.next = (ScanLineList *)NULL;
- ET->ymax = SMALL_COORDINATE;
- ET->ymin = LARGE_COORDINATE;
- 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);
-
- InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
-
- if (PrevPt->y > ET->ymax)
- ET->ymax = PrevPt->y;
- if (PrevPt->y < ET->ymin)
- ET->ymin = PrevPt->y;
- pETEs++;
- }
-
- PrevPt = CurrPt;
- }
-}
-
-/*
- * loadAET
- *
- * This routine moves EdgeTableEntries from the
- * EdgeTable into the Active Edge Table,
- * leaving them sorted by smaller x coordinate.
- *
- */
-
-static void
-loadAET(
- register EdgeTableEntry *AET,
- register EdgeTableEntry *ETEs)
-{
- register EdgeTableEntry *pPrevAET;
- register EdgeTableEntry *tmp;
-
- pPrevAET = AET;
- AET = AET->next;
- while (ETEs)
- {
- while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
- {
- 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---> ...
- *
- */
-static void
-computeWAET(
- 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.
- *
- */
-
-static int
-InsertionSort(
- 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_axis > AET->bres.minor_axis)
- 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.
- */
-static void
-FreeStorage(
- register ScanLineListBlock *pSLLBlock)
-{
- register ScanLineListBlock *tmpSLLBlock;
-
- while (pSLLBlock)
- {
- tmpSLLBlock = pSLLBlock->next;
- Xfree((char *)pSLLBlock);
- pSLLBlock = tmpSLLBlock;
- }
-}
-
-/*
- * Create an array of rectangles from a list of points.
- * If indeed these things (POINTS, RECTS) are the same,
- * then this proc is still needed, because it allocates
- * storage for the array, which was allocated on the
- * stack by the calling procedure.
- *
- */
-static int PtsToRegion(
- register int numFullPtBlocks,
- register int iCurPtBlock,
- POINTBLOCK *FirstPtBlock,
- REGION *reg)
-{
- register BOX *rects;
- register XPoint *pts;
- register POINTBLOCK *CurPtBlock;
- register int i;
- register BOX *extents;
- register int numRects;
- BOX *prevRects = reg->rects;
-
- extents = &reg->extents;
-
- numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
-
- if (!(reg->rects = (BOX *)Xrealloc((char *)reg->rects,
- (unsigned) (sizeof(BOX) * numRects)))) {
- Xfree(prevRects);
- return(0);
- }
-
- reg->size = numRects;
- CurPtBlock = FirstPtBlock;
- rects = reg->rects - 1;
- numRects = 0;
- extents->x1 = MAXSHORT, extents->x2 = MINSHORT;
-
- for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
- /* the loop uses 2 points per iteration */
- i = NUMPTSTOBUFFER >> 1;
- if (!numFullPtBlocks)
- i = iCurPtBlock >> 1;
- for (pts = CurPtBlock->pts; i--; pts += 2) {
- if (pts->x == pts[1].x)
- continue;
- if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
- pts[1].x == rects->x2 &&
- (numRects == 1 || rects[-1].y1 != rects->y1) &&
- (i && pts[2].y > pts[1].y)) {
- rects->y2 = pts[1].y + 1;
- continue;
- }
- numRects++;
- rects++;
- rects->x1 = pts->x; rects->y1 = pts->y;
- rects->x2 = pts[1].x; rects->y2 = pts[1].y + 1;
- if (rects->x1 < extents->x1)
- extents->x1 = rects->x1;
- if (rects->x2 > extents->x2)
- extents->x2 = rects->x2;
- }
- CurPtBlock = CurPtBlock->next;
- }
-
- if (numRects) {
- extents->y1 = reg->rects->y1;
- extents->y2 = rects->y2;
- } else {
- extents->x1 = 0;
- extents->y1 = 0;
- extents->x2 = 0;
- extents->y2 = 0;
- }
- reg->numRects = numRects;
-
- return(TRUE);
-}
-
-/*
- * polytoregion
- *
- * Scan converts a polygon by returning a run-length
- * encoding of the resultant bitmap -- the run-length
- * encoding is in the form of an array of rectangles.
- */
-Region
-XPolygonRegion(
- XPoint *Pts, /* the pts */
- int Count, /* number of pts */
- int rule) /* winding rule */
-{
- Region region;
- register EdgeTableEntry *pAET; /* Active Edge Table */
- register int y; /* current scanline */
- register int iPts = 0; /* number of pts in buffer */
- register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
- register ScanLineList *pSLL; /* current scanLineList */
- register XPoint *pts; /* output buffer */
- EdgeTableEntry *pPrevAET; /* ptr to previous AET */
- EdgeTable ET; /* header node for ET */
- EdgeTableEntry AET; /* header node for AET */
- EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
- ScanLineListBlock SLLBlock; /* header for scanlinelist */
- int fixWAET = FALSE;
- POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
- POINTBLOCK *tmpPtBlock;
- int numFullPtBlocks = 0;
-
- if (! (region = XCreateRegion())) return (Region) NULL;
-
- /* special case a rectangle */
- pts = Pts;
- if (((Count == 4) ||
- ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
- (((pts[0].y == pts[1].y) &&
- (pts[1].x == pts[2].x) &&
- (pts[2].y == pts[3].y) &&
- (pts[3].x == pts[0].x)) ||
- ((pts[0].x == pts[1].x) &&
- (pts[1].y == pts[2].y) &&
- (pts[2].x == pts[3].x) &&
- (pts[3].y == pts[0].y)))) {
- region->extents.x1 = min(pts[0].x, pts[2].x);
- region->extents.y1 = min(pts[0].y, pts[2].y);
- region->extents.x2 = max(pts[0].x, pts[2].x);
- region->extents.y2 = max(pts[0].y, pts[2].y);
- if ((region->extents.x1 != region->extents.x2) &&
- (region->extents.y1 != region->extents.y2)) {
- region->numRects = 1;
- *(region->rects) = region->extents;
- }
- return(region);
- }
-
- if (Count < 2) return region;
-
- if (! (pETEs = (EdgeTableEntry *)
- Xmalloc((unsigned) (sizeof(EdgeTableEntry) * Count)))) {
- XDestroyRegion(region);
- return (Region) NULL;
- }
-
- pts = FirstPtBlock.pts;
- CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
- pSLL = ET.scanlines.next;
- curPtBlock = &FirstPtBlock;
-
- if (rule == EvenOddRule) {
- /*
- * for each scanline
- */
- for (y = ET.ymin; y < ET.ymax; y++) {
- /*
- * Add a new edge to the active edge table when we
- * get to the next edge.
- */
- if (pSLL != NULL && y == pSLL->scanline) {
- loadAET(&AET, pSLL->edgelist);
- pSLL = pSLL->next;
- }
- pPrevAET = &AET;
- pAET = AET.next;
-
- /*
- * for each active edge
- */
- while (pAET) {
- pts->x = pAET->bres.minor_axis, pts->y = y;
- pts++, iPts++;
-
- /*
- * send out the buffer
- */
- if (iPts == NUMPTSTOBUFFER) {
- tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
- curPtBlock->next = tmpPtBlock;
- curPtBlock = tmpPtBlock;
- pts = curPtBlock->pts;
- numFullPtBlocks++;
- iPts = 0;
- }
- EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
- }
- (void) InsertionSort(&AET);
- }
- }
- else {
- /*
- * for each scanline
- */
- for (y = ET.ymin; y < ET.ymax; y++) {
- /*
- * Add a new edge to the active edge table when we
- * get to the next edge.
- */
- if (pSLL != NULL && y == pSLL->scanline) {
- loadAET(&AET, pSLL->edgelist);
- computeWAET(&AET);
- pSLL = pSLL->next;
- }
- pPrevAET = &AET;
- pAET = AET.next;
- pWETE = pAET;
-
- /*
- * for each active edge
- */
- while (pAET) {
- /*
- * add to the buffer only those edges that
- * are in the Winding active edge table.
- */
- if (pWETE == pAET) {
- pts->x = pAET->bres.minor_axis, pts->y = y;
- pts++, iPts++;
-
- /*
- * send out the buffer
- */
- if (iPts == NUMPTSTOBUFFER) {
- tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
- curPtBlock->next = tmpPtBlock;
- curPtBlock = tmpPtBlock;
- pts = curPtBlock->pts;
- numFullPtBlocks++; iPts = 0;
- }
- pWETE = pWETE->nextWETE;
- }
- EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
- }
-
- /*
- * recompute the winding active edge table if
- * we just resorted or have exited an edge.
- */
- if (InsertionSort(&AET) || fixWAET) {
- computeWAET(&AET);
- fixWAET = FALSE;
- }
- }
- }
- FreeStorage(SLLBlock.next);
- (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
- for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
- tmpPtBlock = curPtBlock->next;
- Xfree((char *)curPtBlock);
- curPtBlock = tmpPtBlock;
- }
- Xfree((char *)pETEs);
- return(region);
-}
+/************************************************************************
+
+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.
+
+************************************************************************/
+
+#define LARGE_COORDINATE 1000000
+#define SMALL_COORDINATE -LARGE_COORDINATE
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+#include "Xlibint.h"
+#include "Xutil.h"
+#include <X11/Xregion.h>
+#include "poly.h"
+
+/*
+ * 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.
+ *
+ */
+static void
+InsertEdgeInET(
+ 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 *)Xmalloc(sizeof(ScanLineListBlock));
+ (*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_axis < ETE->bres.minor_axis))
+ {
+ prev = start;
+ start = start->next;
+ }
+ ETE->next = start;
+
+ if (prev)
+ prev->next = ETE;
+ else
+ pSLL->edgelist = ETE;
+}
+
+/*
+ * 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.
+ *
+ */
+
+static void
+CreateETandAET(
+ register int count,
+ register XPoint *pts,
+ EdgeTable *ET,
+ EdgeTableEntry *AET,
+ register EdgeTableEntry *pETEs,
+ ScanLineListBlock *pSLLBlock)
+{
+ register XPoint *top, *bottom;
+ register XPoint *PrevPt, *CurrPt;
+ int iSLLBlock = 0;
+ int dy;
+
+ if (count < 2) return;
+
+ /*
+ * initialize the Active Edge Table
+ */
+ AET->next = (EdgeTableEntry *)NULL;
+ AET->back = (EdgeTableEntry *)NULL;
+ AET->nextWETE = (EdgeTableEntry *)NULL;
+ AET->bres.minor_axis = SMALL_COORDINATE;
+
+ /*
+ * initialize the Edge Table.
+ */
+ ET->scanlines.next = (ScanLineList *)NULL;
+ ET->ymax = SMALL_COORDINATE;
+ ET->ymin = LARGE_COORDINATE;
+ 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);
+
+ InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
+
+ if (PrevPt->y > ET->ymax)
+ ET->ymax = PrevPt->y;
+ if (PrevPt->y < ET->ymin)
+ ET->ymin = PrevPt->y;
+ pETEs++;
+ }
+
+ PrevPt = CurrPt;
+ }
+}
+
+/*
+ * loadAET
+ *
+ * This routine moves EdgeTableEntries from the
+ * EdgeTable into the Active Edge Table,
+ * leaving them sorted by smaller x coordinate.
+ *
+ */
+
+static void
+loadAET(
+ register EdgeTableEntry *AET,
+ register EdgeTableEntry *ETEs)
+{
+ register EdgeTableEntry *pPrevAET;
+ register EdgeTableEntry *tmp;
+
+ pPrevAET = AET;
+ AET = AET->next;
+ while (ETEs)
+ {
+ while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
+ {
+ 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---> ...
+ *
+ */
+static void
+computeWAET(
+ 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.
+ *
+ */
+
+static int
+InsertionSort(
+ 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_axis > AET->bres.minor_axis)
+ 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.
+ */
+static void
+FreeStorage(
+ register ScanLineListBlock *pSLLBlock)
+{
+ register ScanLineListBlock *tmpSLLBlock;
+
+ while (pSLLBlock)
+ {
+ tmpSLLBlock = pSLLBlock->next;
+ Xfree((char *)pSLLBlock);
+ pSLLBlock = tmpSLLBlock;
+ }
+}
+
+/*
+ * Create an array of rectangles from a list of points.
+ * If indeed these things (POINTS, RECTS) are the same,
+ * then this proc is still needed, because it allocates
+ * storage for the array, which was allocated on the
+ * stack by the calling procedure.
+ *
+ */
+static int PtsToRegion(
+ register int numFullPtBlocks,
+ register int iCurPtBlock,
+ POINTBLOCK *FirstPtBlock,
+ REGION *reg)
+{
+ register BOX *rects;
+ register XPoint *pts;
+ register POINTBLOCK *CurPtBlock;
+ register int i;
+ register BOX *extents;
+ register int numRects;
+ BOX *prevRects = reg->rects;
+
+ extents = &reg->extents;
+
+ numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
+
+ if (!(reg->rects = (BOX *)Xrealloc((char *)reg->rects,
+ (unsigned) (sizeof(BOX) * numRects)))) {
+ Xfree(prevRects);
+ return(0);
+ }
+
+ reg->size = numRects;
+ CurPtBlock = FirstPtBlock;
+ rects = reg->rects - 1;
+ numRects = 0;
+ extents->x1 = MAXSHORT, extents->x2 = MINSHORT;
+
+ for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
+ /* the loop uses 2 points per iteration */
+ i = NUMPTSTOBUFFER >> 1;
+ if (!numFullPtBlocks)
+ i = iCurPtBlock >> 1;
+ for (pts = CurPtBlock->pts; i--; pts += 2) {
+ if (pts->x == pts[1].x)
+ continue;
+ if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
+ pts[1].x == rects->x2 &&
+ (numRects == 1 || rects[-1].y1 != rects->y1) &&
+ (i && pts[2].y > pts[1].y)) {
+ rects->y2 = pts[1].y + 1;
+ continue;
+ }
+ numRects++;
+ rects++;
+ rects->x1 = pts->x; rects->y1 = pts->y;
+ rects->x2 = pts[1].x; rects->y2 = pts[1].y + 1;
+ if (rects->x1 < extents->x1)
+ extents->x1 = rects->x1;
+ if (rects->x2 > extents->x2)
+ extents->x2 = rects->x2;
+ }
+ CurPtBlock = CurPtBlock->next;
+ }
+
+ if (numRects) {
+ extents->y1 = reg->rects->y1;
+ extents->y2 = rects->y2;
+ } else {
+ extents->x1 = 0;
+ extents->y1 = 0;
+ extents->x2 = 0;
+ extents->y2 = 0;
+ }
+ reg->numRects = numRects;
+
+ return(TRUE);
+}
+
+/*
+ * polytoregion
+ *
+ * Scan converts a polygon by returning a run-length
+ * encoding of the resultant bitmap -- the run-length
+ * encoding is in the form of an array of rectangles.
+ */
+Region
+XPolygonRegion(
+ XPoint *Pts, /* the pts */
+ int Count, /* number of pts */
+ int rule) /* winding rule */
+{
+ Region region;
+ register EdgeTableEntry *pAET; /* Active Edge Table */
+ register int y; /* current scanline */
+ register int iPts = 0; /* number of pts in buffer */
+ register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
+ register ScanLineList *pSLL; /* current scanLineList */
+ register XPoint *pts; /* output buffer */
+ EdgeTableEntry *pPrevAET; /* ptr to previous AET */
+ EdgeTable ET; /* header node for ET */
+ EdgeTableEntry AET; /* header node for AET */
+ EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
+ ScanLineListBlock SLLBlock; /* header for scanlinelist */
+ int fixWAET = FALSE;
+ POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
+ POINTBLOCK *tmpPtBlock;
+ int numFullPtBlocks = 0;
+
+ if (! (region = XCreateRegion())) return (Region) NULL;
+
+ /* special case a rectangle */
+ pts = Pts;
+ if (((Count == 4) ||
+ ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
+ (((pts[0].y == pts[1].y) &&
+ (pts[1].x == pts[2].x) &&
+ (pts[2].y == pts[3].y) &&
+ (pts[3].x == pts[0].x)) ||
+ ((pts[0].x == pts[1].x) &&
+ (pts[1].y == pts[2].y) &&
+ (pts[2].x == pts[3].x) &&
+ (pts[3].y == pts[0].y)))) {
+ region->extents.x1 = min(pts[0].x, pts[2].x);
+ region->extents.y1 = min(pts[0].y, pts[2].y);
+ region->extents.x2 = max(pts[0].x, pts[2].x);
+ region->extents.y2 = max(pts[0].y, pts[2].y);
+ if ((region->extents.x1 != region->extents.x2) &&
+ (region->extents.y1 != region->extents.y2)) {
+ region->numRects = 1;
+ *(region->rects) = region->extents;
+ }
+ return(region);
+ }
+
+ if (Count < 2) return region;
+
+ if (! (pETEs = (EdgeTableEntry *)
+ Xmalloc((unsigned) (sizeof(EdgeTableEntry) * Count)))) {
+ XDestroyRegion(region);
+ return (Region) NULL;
+ }
+
+ pts = FirstPtBlock.pts;
+ CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
+ pSLL = ET.scanlines.next;
+ curPtBlock = &FirstPtBlock;
+
+ if (rule == EvenOddRule) {
+ /*
+ * for each scanline
+ */
+ for (y = ET.ymin; y < ET.ymax; y++) {
+ /*
+ * Add a new edge to the active edge table when we
+ * get to the next edge.
+ */
+ if (pSLL != NULL && y == pSLL->scanline) {
+ loadAET(&AET, pSLL->edgelist);
+ pSLL = pSLL->next;
+ }
+ pPrevAET = &AET;
+ pAET = AET.next;
+
+ /*
+ * for each active edge
+ */
+ while (pAET) {
+ pts->x = pAET->bres.minor_axis, pts->y = y;
+ pts++, iPts++;
+
+ /*
+ * send out the buffer
+ */
+ if (iPts == NUMPTSTOBUFFER) {
+ tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
+ curPtBlock->next = tmpPtBlock;
+ curPtBlock = tmpPtBlock;
+ pts = curPtBlock->pts;
+ numFullPtBlocks++;
+ iPts = 0;
+ }
+ EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
+ }
+ (void) InsertionSort(&AET);
+ }
+ }
+ else {
+ /*
+ * for each scanline
+ */
+ for (y = ET.ymin; y < ET.ymax; y++) {
+ /*
+ * Add a new edge to the active edge table when we
+ * get to the next edge.
+ */
+ if (pSLL != NULL && y == pSLL->scanline) {
+ loadAET(&AET, pSLL->edgelist);
+ computeWAET(&AET);
+ pSLL = pSLL->next;
+ }
+ pPrevAET = &AET;
+ pAET = AET.next;
+ pWETE = pAET;
+
+ /*
+ * for each active edge
+ */
+ while (pAET) {
+ /*
+ * add to the buffer only those edges that
+ * are in the Winding active edge table.
+ */
+ if (pWETE == pAET) {
+ pts->x = pAET->bres.minor_axis, pts->y = y;
+ pts++, iPts++;
+
+ /*
+ * send out the buffer
+ */
+ if (iPts == NUMPTSTOBUFFER) {
+ tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
+ curPtBlock->next = tmpPtBlock;
+ curPtBlock = tmpPtBlock;
+ pts = curPtBlock->pts;
+ numFullPtBlocks++; iPts = 0;
+ }
+ pWETE = pWETE->nextWETE;
+ }
+ EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
+ }
+
+ /*
+ * recompute the winding active edge table if
+ * we just resorted or have exited an edge.
+ */
+ if (InsertionSort(&AET) || fixWAET) {
+ computeWAET(&AET);
+ fixWAET = FALSE;
+ }
+ }
+ }
+ FreeStorage(SLLBlock.next);
+ (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
+ for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
+ tmpPtBlock = curPtBlock->next;
+ Xfree((char *)curPtBlock);
+ curPtBlock = tmpPtBlock;
+ }
+ Xfree((char *)pETEs);
+ return(region);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 17:05:31 +0000