diff options
Diffstat (limited to 'mi')
| -rw-r--r-- | mi/Makefile.am | 1 | ||||
| -rw-r--r-- | mi/mipoly.c | 285 | ||||
| -rw-r--r-- | mi/mipoly.h | 17 | ||||
| -rw-r--r-- | mi/mipolyutil.c | 369 |
4 files changed, 285 insertions, 387 deletions
diff --git a/mi/Makefile.am b/mi/Makefile.am index 44e4f2053..ce416c41f 100644 --- a/mi/Makefile.am +++ b/mi/Makefile.am @@ -40,7 +40,6 @@ libmi_la_SOURCES = \ mipolyrect.c \ mipolyseg.c \ mipolytext.c \ - mipolyutil.c \ mipushpxl.c \ miscanfill.h \ miscrinit.c \ diff --git a/mi/mipoly.c b/mi/mipoly.c index 3d49789b0..0ed2edb44 100644 --- a/mi/mipoly.c +++ b/mi/mipoly.c @@ -61,6 +61,291 @@ SOFTWARE. #include "mipoly.h" #include "regionstr.h" +/* + * 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 Bool +miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline, + ScanLineListBlock ** SLLBlock, int *iSLLBlock) +{ + EdgeTableEntry *start, *prev; + 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 = malloc(sizeof(ScanLineListBlock)); + if (!tmpSLLBlock) + return FALSE; + (*SLLBlock)->next = tmpSLLBlock; + tmpSLLBlock->next = NULL; + *SLLBlock = tmpSLLBlock; + *iSLLBlock = 0; + } + pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); + + pSLL->next = pPrevSLL->next; + pSLL->edgelist = NULL; + pPrevSLL->next = pSLL; + } + pSLL->scanline = scanline; + + /* + * now insert the edge in the right bucket + */ + prev = 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; +} + +static void +miFreeStorage(ScanLineListBlock * pSLLBlock) +{ + ScanLineListBlock *tmpSLLBlock; + + while (pSLLBlock) { + tmpSLLBlock = pSLLBlock->next; + free(pSLLBlock); + pSLLBlock = tmpSLLBlock; + } +} + +/* + * 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 Bool +miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET, + EdgeTableEntry * AET, EdgeTableEntry * pETEs, + ScanLineListBlock * pSLLBlock) +{ + DDXPointPtr top, bottom; + DDXPointPtr PrevPt, CurrPt; + int iSLLBlock = 0; + + int dy; + + if (count < 2) + return TRUE; + + /* + * initialize the Active Edge Table + */ + AET->next = NULL; + AET->back = NULL; + AET->nextWETE = NULL; + AET->bres.minor = MININT; + + /* + * initialize the Edge Table. + */ + ET->scanlines.next = NULL; + ET->ymax = MININT; + ET->ymin = MAXINT; + pSLLBlock->next = 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; +} + +/* + * This routine moves EdgeTableEntries from the EdgeTable into the Active Edge + * Table, leaving them sorted by smaller x coordinate. + */ + +static void +miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs) +{ + EdgeTableEntry *pPrevAET; + 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---> ... + * + */ +static void +micomputeWAET(EdgeTableEntry * AET) +{ + EdgeTableEntry *pWETE; + int inside = 1; + int isInside = 0; + + AET->nextWETE = 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 = NULL; +} + +/* + * Just a simple insertion sort using pointers and back pointers to sort the + * Active Edge Table. + */ + +static int +miInsertionSort(EdgeTableEntry * AET) +{ + EdgeTableEntry *pETEchase; + EdgeTableEntry *pETEinsert; + EdgeTableEntry *pETEchaseBackTMP; + 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; +} + /* Find the index of the point with the smallest y */ static int getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty) diff --git a/mi/mipoly.h b/mi/mipoly.h index 02fcfc86d..fc5a5cf3f 100644 --- a/mi/mipoly.h +++ b/mi/mipoly.h @@ -171,20 +171,3 @@ typedef struct _ScanLineListBlock { pAET = pAET->next; \ } \ } - -/* mipolyutil.c */ - -extern Bool miCreateETandAET(int /*count */ , - DDXPointPtr /*pts */ , - EdgeTable * /*ET*/, - EdgeTableEntry * /*AET*/, - EdgeTableEntry * /*pETEs */ , - ScanLineListBlock * /*pSLLBlock */); - -extern void miloadAET(EdgeTableEntry * /*AET*/, EdgeTableEntry * /*ETEs */); - -extern void micomputeWAET(EdgeTableEntry * /*AET*/); - -extern int miInsertionSort(EdgeTableEntry * /*AET*/); - -extern void miFreeStorage(ScanLineListBlock * /*pSLLBlock */); diff --git a/mi/mipolyutil.c b/mi/mipolyutil.c deleted file mode 100644 index 5e6301d43..000000000 --- a/mi/mipolyutil.c +++ /dev/null @@ -1,369 +0,0 @@ -/*********************************************************** - -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. - -******************************************************************/ -#ifdef HAVE_DIX_CONFIG_H -#include <dix-config.h> -#endif - -#include "regionstr.h" -#include "gc.h" -#include "miscanfill.h" -#include "mipoly.h" -#include "misc.h" /* 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. - * - */ -static Bool -miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline, - ScanLineListBlock ** SLLBlock, int *iSLLBlock) -{ - EdgeTableEntry *start, *prev; - 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 = malloc(sizeof(ScanLineListBlock)); - if (!tmpSLLBlock) - return FALSE; - (*SLLBlock)->next = tmpSLLBlock; - tmpSLLBlock->next = NULL; - *SLLBlock = tmpSLLBlock; - *iSLLBlock = 0; - } - pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); - - pSLL->next = pPrevSLL->next; - pSLL->edgelist = NULL; - pPrevSLL->next = pSLL; - } - pSLL->scanline = scanline; - - /* - * now insert the edge in the right bucket - */ - prev = 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(int count, DDXPointPtr pts, EdgeTable * ET, - EdgeTableEntry * AET, EdgeTableEntry * pETEs, - ScanLineListBlock * pSLLBlock) -{ - DDXPointPtr top, bottom; - DDXPointPtr PrevPt, CurrPt; - int iSLLBlock = 0; - - int dy; - - if (count < 2) - return TRUE; - - /* - * initialize the Active Edge Table - */ - AET->next = NULL; - AET->back = NULL; - AET->nextWETE = NULL; - AET->bres.minor = MININT; - - /* - * initialize the Edge Table. - */ - ET->scanlines.next = NULL; - ET->ymax = MININT; - ET->ymin = MAXINT; - pSLLBlock->next = 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(EdgeTableEntry * AET, EdgeTableEntry * ETEs) -{ - EdgeTableEntry *pPrevAET; - 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(EdgeTableEntry * AET) -{ - EdgeTableEntry *pWETE; - int inside = 1; - int isInside = 0; - - AET->nextWETE = 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 = NULL; -} - -/* - * InsertionSort - * - * Just a simple insertion sort using - * pointers and back pointers to sort the Active - * Edge Table. - * - */ - -int -miInsertionSort(EdgeTableEntry * AET) -{ - EdgeTableEntry *pETEchase; - EdgeTableEntry *pETEinsert; - EdgeTableEntry *pETEchaseBackTMP; - 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(ScanLineListBlock * pSLLBlock) -{ - ScanLineListBlock *tmpSLLBlock; - - while (pSLLBlock) { - tmpSLLBlock = pSLLBlock->next; - free(pSLLBlock); - pSLLBlock = tmpSLLBlock; - } -} |