diff options
Diffstat (limited to 'xorg-server/mi/mipoly.c')
| -rw-r--r-- | xorg-server/mi/mipoly.c | 627 |
1 files changed, 618 insertions, 9 deletions
diff --git a/xorg-server/mi/mipoly.c b/xorg-server/mi/mipoly.c index 07d981845..a332376d1 100644 --- a/xorg-server/mi/mipoly.c +++ b/xorg-server/mi/mipoly.c @@ -26,13 +26,13 @@ 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, +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 +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. +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 @@ -47,11 +47,6 @@ SOFTWARE. * mipoly.c * * Written by Brian Kelleher; June 1986 - * - * Draw polygons. This routine translates the point by the - * origin if pGC->miTranslate is non-zero, and calls - * to the appropriate routine to actually scan convert the - * polygon. */ #ifdef HAVE_DIX_CONFIG_H #include <dix-config.h> @@ -62,8 +57,622 @@ SOFTWARE. #include "gcstruct.h" #include "pixmapstr.h" #include "mi.h" +#include "miscanfill.h" +#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) +{ + DDXPointPtr ptMin; + int ymin, ymax; + DDXPointPtr ptsStart = pts; + + ptMin = pts; + ymin = ymax = (pts++)->y; + + while (--n > 0) { + if (pts->y < ymin) { + ptMin = pts; + ymin = pts->y; + } + if (pts->y > ymax) + ymax = pts->y; + + pts++; + } + + *by = ymin; + *ty = ymax; + return ptMin - ptsStart; +} + +/* + * Written by Brian Kelleher; Dec. 1985. + * + * Fill a convex polygon. If the given polygon is not convex, then the result + * is undefined. The algorithm is to order the edges from smallest y to + * largest by partitioning the array into a left edge list and a right edge + * list. The algorithm used to traverse each edge is an extension of + * Bresenham's line algorithm with y as the major axis. For a derivation of + * the algorithm, see the author of this code. + */ +static Bool +miFillConvexPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn) +{ + int xl = 0, xr = 0; /* x vals of left and right edges */ + int dl = 0, dr = 0; /* decision variables */ + int ml = 0, m1l = 0; /* left edge slope and slope+1 */ + int mr = 0, m1r = 0; /* right edge slope and slope+1 */ + int incr1l = 0, incr2l = 0; /* left edge error increments */ + int incr1r = 0, incr2r = 0; /* right edge error increments */ + int dy; /* delta y */ + int y; /* current scanline */ + int left, right; /* indices to first endpoints */ + int i; /* loop counter */ + int nextleft, nextright; /* indices to second endpoints */ + DDXPointPtr ptsOut, FirstPoint; /* output buffer */ + int *width, *FirstWidth; /* output buffer */ + int imin; /* index of smallest vertex (in y) */ + int ymin; /* y-extents of polygon */ + int ymax; + + /* + * find leftx, bottomy, rightx, topy, and the index + * of bottomy. Also translate the points. + */ + imin = getPolyYBounds(ptsIn, count, &ymin, &ymax); + + dy = ymax - ymin + 1; + if ((count < 3) || (dy < 0)) + return TRUE; + ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * dy); + width = FirstWidth = malloc(sizeof(int) * dy); + if (!FirstPoint || !FirstWidth) { + free(FirstWidth); + free(FirstPoint); + return FALSE; + } + + nextleft = nextright = imin; + y = ptsIn[nextleft].y; + + /* + * loop through all edges of the polygon + */ + do { + /* + * add a left edge if we need to + */ + if (ptsIn[nextleft].y == y) { + left = nextleft; + + /* + * find the next edge, considering the end + * conditions of the array. + */ + nextleft++; + if (nextleft >= count) + nextleft = 0; + + /* + * now compute all of the random information + * needed to run the iterative algorithm. + */ + BRESINITPGON(ptsIn[nextleft].y - ptsIn[left].y, + ptsIn[left].x, ptsIn[nextleft].x, + xl, dl, ml, m1l, incr1l, incr2l); + } + + /* + * add a right edge if we need to + */ + if (ptsIn[nextright].y == y) { + right = nextright; + + /* + * find the next edge, considering the end + * conditions of the array. + */ + nextright--; + if (nextright < 0) + nextright = count - 1; + + /* + * now compute all of the random information + * needed to run the iterative algorithm. + */ + BRESINITPGON(ptsIn[nextright].y - ptsIn[right].y, + ptsIn[right].x, ptsIn[nextright].x, + xr, dr, mr, m1r, incr1r, incr2r); + } + + /* + * generate scans to fill while we still have + * a right edge as well as a left edge. + */ + i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y; + /* in case we're called with non-convex polygon */ + if (i < 0) { + free(FirstWidth); + free(FirstPoint); + return TRUE; + } + while (i-- > 0) { + ptsOut->y = y; + + /* + * reverse the edges if necessary + */ + if (xl < xr) { + *(width++) = xr - xl; + (ptsOut++)->x = xl; + } + else { + *(width++) = xl - xr; + (ptsOut++)->x = xr; + } + y++; + + /* increment down the edges */ + BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l); + BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r); + } + } while (y != ymax); + + /* + * Finally, fill the <remaining> spans + */ + (*pgc->ops->FillSpans) (dst, pgc, + ptsOut - FirstPoint, FirstPoint, FirstWidth, 1); + free(FirstWidth); + free(FirstPoint); + return TRUE; +} + +/* + * Written by Brian Kelleher; Oct. 1985 + * + * Routine to fill a polygon. Two fill rules are supported: frWINDING and + * frEVENODD. + */ +static Bool +miFillGeneralPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn) +{ + EdgeTableEntry *pAET; /* the Active Edge Table */ + int y; /* the current scanline */ + int nPts = 0; /* number of pts in buffer */ + EdgeTableEntry *pWETE; /* Winding Edge Table */ + ScanLineList *pSLL; /* Current ScanLineList */ + DDXPointPtr ptsOut; /* ptr to output buffers */ + int *width; + DDXPointRec FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */ + int FirstWidth[NUMPTSTOBUFFER]; + EdgeTableEntry *pPrevAET; /* previous AET entry */ + EdgeTable ET; /* Edge Table header node */ + EdgeTableEntry AET; /* Active ET header node */ + EdgeTableEntry *pETEs; /* Edge Table Entries buff */ + ScanLineListBlock SLLBlock; /* header for ScanLineList */ + int fixWAET = 0; + + if (count < 3) + return TRUE; + + if (!(pETEs = malloc(sizeof(EdgeTableEntry) * count))) + return FALSE; + ptsOut = FirstPoint; + width = FirstWidth; + if (!miCreateETandAET(count, ptsIn, &ET, &AET, pETEs, &SLLBlock)) { + free(pETEs); + return FALSE; + } + pSLL = ET.scanlines.next; + + if (pgc->fillRule == 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 && y == pSLL->scanline) { + miloadAET(&AET, pSLL->edgelist); + pSLL = pSLL->next; + } + pPrevAET = &AET; + pAET = AET.next; + + /* + * for each active edge + */ + while (pAET) { + ptsOut->x = pAET->bres.minor; + ptsOut++->y = y; + *width++ = pAET->next->bres.minor - pAET->bres.minor; + nPts++; + + /* + * send out the buffer when its full + */ + if (nPts == NUMPTSTOBUFFER) { + (*pgc->ops->FillSpans) (dst, pgc, + nPts, FirstPoint, FirstWidth, 1); + ptsOut = FirstPoint; + width = FirstWidth; + nPts = 0; + } + EVALUATEEDGEEVENODD(pAET, pPrevAET, y); + EVALUATEEDGEEVENODD(pAET, pPrevAET, y); + } + miInsertionSort(&AET); + } + } + else { /* default to WindingNumber */ + + /* + * 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 && y == pSLL->scanline) { + miloadAET(&AET, pSLL->edgelist); + micomputeWAET(&AET); + pSLL = pSLL->next; + } + pPrevAET = &AET; + pAET = AET.next; + pWETE = pAET; + + /* + * for each active edge + */ + while (pAET) { + /* + * if the next edge in the active edge table is + * also the next edge in the winding active edge + * table. + */ + if (pWETE == pAET) { + ptsOut->x = pAET->bres.minor; + ptsOut++->y = y; + *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor; + nPts++; + + /* + * send out the buffer + */ + if (nPts == NUMPTSTOBUFFER) { + (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, + FirstWidth, 1); + ptsOut = FirstPoint; + width = FirstWidth; + nPts = 0; + } + + pWETE = pWETE->nextWETE; + while (pWETE != pAET) + EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET); + pWETE = pWETE->nextWETE; + } + EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET); + } + + /* + * reevaluate the Winding active edge table if we + * just had to resort it or if we just exited an edge. + */ + if (miInsertionSort(&AET) || fixWAET) { + micomputeWAET(&AET); + fixWAET = 0; + } + } + } + + /* + * Get any spans that we missed by buffering + */ + (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, FirstWidth, 1); + free(pETEs); + miFreeStorage(SLLBlock.next); + return TRUE; +} + +/* + * Draw polygons. This routine translates the point by the origin if + * pGC->miTranslate is non-zero, and calls to the appropriate routine to + * actually scan convert the polygon. + */ void miFillPolygon(DrawablePtr dst, GCPtr pgc, int shape, int mode, int count, DDXPointPtr pPts) |