Return to XPolyReg.c CVS log

Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / lib / X

Annotation of researchv9/X11/src/X.V11R1/lib/X/XPolyReg.c, revision 1.1

1.1     ! root        1: /* $Header: XPolyReg.c,v 11.11 87/09/13 22:01:50 toddb Exp $ */
        !             2: /************************************************************************
        !             3: Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
        !             4: and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
        !             5: 
        !             6:                         All Rights Reserved
        !             7: 
        !             8: Permission to use, copy, modify, and distribute this software and its 
        !             9: documentation for any purpose and without fee is hereby granted, 
        !            10: provided that the above copyright notice appear in all copies and that
        !            11: both that copyright notice and this permission notice appear in 
        !            12: supporting documentation, and that the names of Digital or MIT not be
        !            13: used in advertising or publicity pertaining to distribution of the
        !            14: software without specific, written prior permission.  
        !            15: 
        !            16: DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
        !            17: ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
        !            18: DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
        !            19: ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
        !            20: WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
        !            21: ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
        !            22: SOFTWARE.
        !            23: 
        !            24: ************************************************************************/
        !            25: 
        !            26: #define MAXINT 1000000
        !            27: #define MININT -MAXINT
        !            28: 
        !            29: #include "region.h"
        !            30: #include "poly.h"
        !            31: #include "Xlib.h"
        !            32: #include "Xutil.h"
        !            33: 
        !            34: /*
        !            35:  *     InsertEdgeInET
        !            36:  *
        !            37:  *     Insert the given edge into the edge table.
        !            38:  *     First we must find the correct bucket in the
        !            39:  *     Edge table, then find the right slot in the
        !            40:  *     bucket.  Finally, we can insert it.
        !            41:  *
        !            42:  */
        !            43: static void
        !            44: InsertEdgeInET(ET, ETE, scanline, SLLBlock, iSLLBlock)
        !            45:     EdgeTable *ET;
        !            46:     EdgeTableEntry *ETE;
        !            47:     int scanline;
        !            48:     ScanLineListBlock **SLLBlock;
        !            49:     int *iSLLBlock;
        !            50: {
        !            51:     register EdgeTableEntry *start, *prev;
        !            52:     register ScanLineList *pSLL, *pPrevSLL;
        !            53:     ScanLineListBlock *tmpSLLBlock;
        !            54: 
        !            55:     /*
        !            56:      * find the right bucket to put the edge into
        !            57:      */
        !            58:     pPrevSLL = &ET->scanlines;
        !            59:     pSLL = pPrevSLL->next;
        !            60:     while (pSLL && (pSLL->scanline < scanline)) 
        !            61:     {
        !            62:         pPrevSLL = pSLL;
        !            63:         pSLL = pSLL->next;
        !            64:     }
        !            65: 
        !            66:     /*
        !            67:      * reassign pSLL (pointer to ScanLineList) if necessary
        !            68:      */
        !            69:     if ((!pSLL) || (pSLL->scanline > scanline)) 
        !            70:     {
        !            71:         if (*iSLLBlock > SLLSPERBLOCK-1) 
        !            72:         {
        !            73:             tmpSLLBlock = 
        !            74:                  (ScanLineListBlock *)Xmalloc(sizeof(ScanLineListBlock));
        !            75:             (*SLLBlock)->next = tmpSLLBlock;
        !            76:             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
        !            77:             *SLLBlock = tmpSLLBlock;
        !            78:             *iSLLBlock = 0;
        !            79:         }
        !            80:         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
        !            81: 
        !            82:         pSLL->next = pPrevSLL->next;
        !            83:         pSLL->edgelist = (EdgeTableEntry *)NULL;
        !            84:         pPrevSLL->next = pSLL;
        !            85:     }
        !            86:     pSLL->scanline = scanline;
        !            87: 
        !            88:     /*
        !            89:      * now insert the edge in the right bucket
        !            90:      */
        !            91:     prev = (EdgeTableEntry *)NULL;
        !            92:     start = pSLL->edgelist;
        !            93:     while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) 
        !            94:     {
        !            95:         prev = start;
        !            96:         start = start->next;
        !            97:     }
        !            98:     ETE->next = start;
        !            99: 
        !           100:     if (prev)
        !           101:         prev->next = ETE;
        !           102:     else
        !           103:         pSLL->edgelist = ETE;
        !           104: }
        !           105: 
        !           106: /*
        !           107:  *     CreateEdgeTable
        !           108:  *
        !           109:  *     This routine creates the edge table for
        !           110:  *     scan converting polygons. 
        !           111:  *     The Edge Table (ET) looks like:
        !           112:  *
        !           113:  *    EdgeTable
        !           114:  *     --------
        !           115:  *    |  ymax  |        ScanLineLists
        !           116:  *    |scanline|-->------------>-------------->...
        !           117:  *     --------   |scanline|   |scanline|
        !           118:  *                |edgelist|   |edgelist|
        !           119:  *                ---------    ---------
        !           120:  *                    |             |
        !           121:  *                    |             |
        !           122:  *                    V             V
        !           123:  *              list of ETEs   list of ETEs
        !           124:  *
        !           125:  *     where ETE is an EdgeTableEntry data structure,
        !           126:  *     and there is one ScanLineList per scanline at
        !           127:  *     which an edge is initially entered.
        !           128:  *
        !           129:  */
        !           130: 
        !           131: static void
        !           132: CreateETandAET(count, pts, ET, AET, pETEs, pSLLBlock)
        !           133:     register int count;
        !           134:     register XPoint *pts;
        !           135:     EdgeTable *ET;
        !           136:     EdgeTableEntry *AET;
        !           137:     register EdgeTableEntry *pETEs;
        !           138:     ScanLineListBlock   *pSLLBlock;
        !           139: {
        !           140:     register XPoint *top, *bottom;
        !           141:     register XPoint *PrevPt, *CurrPt;
        !           142:     int iSLLBlock = 0;
        !           143:     int dy;
        !           144: 
        !           145:     if (count < 2)  return;
        !           146: 
        !           147:     /*
        !           148:      *  initialize the Active Edge Table
        !           149:      */
        !           150:     AET->next = (EdgeTableEntry *)NULL;
        !           151:     AET->back = (EdgeTableEntry *)NULL;
        !           152:     AET->nextWETE = (EdgeTableEntry *)NULL;
        !           153:     AET->bres.minor_axis = MININT;
        !           154: 
        !           155:     /*
        !           156:      *  initialize the Edge Table.
        !           157:      */
        !           158:     ET->scanlines.next = (ScanLineList *)NULL;
        !           159:     ET->ymax = MININT;
        !           160:     ET->ymin = MAXINT;
        !           161:     pSLLBlock->next = (ScanLineListBlock *)NULL;
        !           162: 
        !           163:     PrevPt = &pts[count-1];
        !           164: 
        !           165:     /*
        !           166:      *  for each vertex in the array of points.
        !           167:      *  In this loop we are dealing with two vertices at
        !           168:      *  a time -- these make up one edge of the polygon.
        !           169:      */
        !           170:     while (count--) 
        !           171:     {
        !           172:         CurrPt = pts++;
        !           173: 
        !           174:         /*
        !           175:          *  find out which point is above and which is below.
        !           176:          */
        !           177:         if (PrevPt->y > CurrPt->y) 
        !           178:         {
        !           179:             bottom = PrevPt, top = CurrPt;
        !           180:             pETEs->ClockWise = 0;
        !           181:         }
        !           182:         else 
        !           183:         {
        !           184:             bottom = CurrPt, top = PrevPt;
        !           185:             pETEs->ClockWise = 1;
        !           186:         }
        !           187: 
        !           188:         /*
        !           189:          * don't add horizontal edges to the Edge table.
        !           190:          */
        !           191:         if (bottom->y != top->y) 
        !           192:         {
        !           193:             pETEs->ymax = bottom->y-1;  /* -1 so we don't get last scanline */
        !           194: 
        !           195:             /*
        !           196:              *  initialize integer edge algorithm
        !           197:              */
        !           198:             dy = bottom->y - top->y;
        !           199:             BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
        !           200: 
        !           201:             InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
        !           202: 
        !           203:             ET->ymax = MAX(ET->ymax, PrevPt->y);
        !           204:             ET->ymin = MIN(ET->ymin, PrevPt->y);
        !           205:             pETEs++;
        !           206:         }
        !           207: 
        !           208:         PrevPt = CurrPt;
        !           209:     }
        !           210: }
        !           211: 
        !           212: /*
        !           213:  *     loadAET
        !           214:  *
        !           215:  *     This routine moves EdgeTableEntries from the
        !           216:  *     EdgeTable into the Active Edge Table,
        !           217:  *     leaving them sorted by smaller x coordinate.
        !           218:  *
        !           219:  */
        !           220: 
        !           221: static void
        !           222: loadAET(AET, ETEs)
        !           223:     register EdgeTableEntry *AET, *ETEs;
        !           224: {
        !           225:     register EdgeTableEntry *pPrevAET;
        !           226:     register EdgeTableEntry *tmp;
        !           227: 
        !           228:     pPrevAET = AET;
        !           229:     AET = AET->next;
        !           230:     while (ETEs) 
        !           231:     {
        !           232:         while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis)) 
        !           233:         {
        !           234:             pPrevAET = AET;
        !           235:             AET = AET->next;
        !           236:         }
        !           237:         tmp = ETEs->next;
        !           238:         ETEs->next = AET;
        !           239:         if (AET)
        !           240:             AET->back = ETEs;
        !           241:         ETEs->back = pPrevAET;
        !           242:         pPrevAET->next = ETEs;
        !           243:         pPrevAET = ETEs;
        !           244: 
        !           245:         ETEs = tmp;
        !           246:     }
        !           247: }
        !           248: 
        !           249: /*
        !           250:  *     computeWAET
        !           251:  *
        !           252:  *     This routine links the AET by the
        !           253:  *     nextWETE (winding EdgeTableEntry) link for
        !           254:  *     use by the winding number rule.  The final 
        !           255:  *     Active Edge Table (AET) might look something
        !           256:  *     like:
        !           257:  *
        !           258:  *     AET
        !           259:  *     ----------  ---------   ---------
        !           260:  *     |ymax    |  |ymax    |  |ymax    | 
        !           261:  *     | ...    |  |...     |  |...     |
        !           262:  *     |next    |->|next    |->|next    |->...
        !           263:  *     |nextWETE|  |nextWETE|  |nextWETE|
        !           264:  *     ---------   ---------   ^--------
        !           265:  *         |                   |       |
        !           266:  *         V------------------->       V---> ...
        !           267:  *
        !           268:  */
        !           269: static void
        !           270: computeWAET(AET)
        !           271:     register EdgeTableEntry *AET;
        !           272: {
        !           273:     register EdgeTableEntry *pWETE;
        !           274:     register int inside = 1;
        !           275:     register int isInside = 0;
        !           276: 
        !           277:     AET->nextWETE = (EdgeTableEntry *)NULL;
        !           278:     pWETE = AET;
        !           279:     AET = AET->next;
        !           280:     while (AET) 
        !           281:     {
        !           282:         if (AET->ClockWise)
        !           283:             isInside++;
        !           284:         else
        !           285:             isInside--;
        !           286: 
        !           287:         if ((!inside && !isInside) ||
        !           288:             ( inside &&  isInside)) 
        !           289:         {
        !           290:             pWETE->nextWETE = AET;
        !           291:             pWETE = AET;
        !           292:             inside = !inside;
        !           293:         }
        !           294:         AET = AET->next;
        !           295:     }
        !           296:     pWETE->nextWETE = (EdgeTableEntry *)NULL;
        !           297: }
        !           298: 
        !           299: /*
        !           300:  *     InsertionSort
        !           301:  *
        !           302:  *     Just a simple insertion sort using
        !           303:  *     pointers and back pointers to sort the Active
        !           304:  *     Edge Table.
        !           305:  *
        !           306:  */
        !           307: 
        !           308: static int
        !           309: InsertionSort(AET)
        !           310:     register EdgeTableEntry *AET;
        !           311: {
        !           312:     register EdgeTableEntry *pETEchase;
        !           313:     register EdgeTableEntry *pETEinsert;
        !           314:     register EdgeTableEntry *pETEchaseBackTMP;
        !           315:     register int changed = 0;
        !           316: 
        !           317:     AET = AET->next;
        !           318:     while (AET) 
        !           319:     {
        !           320:         pETEinsert = AET;
        !           321:         pETEchase = AET;
        !           322:         while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
        !           323:             pETEchase = pETEchase->back;
        !           324: 
        !           325:         AET = AET->next;
        !           326:         if (pETEchase != pETEinsert) 
        !           327:         {
        !           328:             pETEchaseBackTMP = pETEchase->back;
        !           329:             pETEinsert->back->next = AET;
        !           330:             if (AET)
        !           331:                 AET->back = pETEinsert->back;
        !           332:             pETEinsert->next = pETEchase;
        !           333:             pETEchase->back->next = pETEinsert;
        !           334:             pETEchase->back = pETEinsert;
        !           335:             pETEinsert->back = pETEchaseBackTMP;
        !           336:             changed = 1;
        !           337:         }
        !           338:     }
        !           339:     return(changed);
        !           340: }
        !           341: 
        !           342: /*
        !           343:  *     Clean up our act.
        !           344:  */
        !           345: static void
        !           346: FreeStorage(pSLLBlock)
        !           347:     register ScanLineListBlock   *pSLLBlock;
        !           348: {
        !           349:     register ScanLineListBlock   *tmpSLLBlock;
        !           350: 
        !           351:     while (pSLLBlock) 
        !           352:     {
        !           353:         tmpSLLBlock = pSLLBlock->next;
        !           354:         Xfree((char *)pSLLBlock);
        !           355:         pSLLBlock = tmpSLLBlock;
        !           356:     }
        !           357: }
        !           358: 
        !           359: /*
        !           360:  *     Create an array of rectangles from a list of points.
        !           361:  *     If indeed these things (POINTS, RECTS) are the same,
        !           362:  *     then this proc is still needed, because it allocates
        !           363:  *     storage for the array, which was allocated on the
        !           364:  *     stack by the calling procedure.
        !           365:  *
        !           366:  */
        !           367: static int PtsToRegion(numFullPtBlocks, iCurPtBlock, FirstPtBlock, reg)
        !           368:     register int  numFullPtBlocks, iCurPtBlock;
        !           369:     POINTBLOCK *FirstPtBlock;
        !           370:     REGION *reg;
        !           371: {
        !           372:     register BOX  *rects;
        !           373:     register XPoint *pts;
        !           374:     register POINTBLOCK *CurPtBlock;
        !           375:     register int i;
        !           376:     register BOX *extents;
        !           377:     int numRects;
        !           378:  
        !           379:     extents = &reg->extents;
        !           380:  
        !           381:     numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
        !           382:  
        !           383:     if (!(reg->rects = (BOX *)Xrealloc((char *)reg->rects, 
        !           384:            (unsigned) (sizeof(BOX) * numRects))))       return(0);
        !           385:  
        !           386:     CurPtBlock = FirstPtBlock;
        !           387:     rects = reg->rects;
        !           388:  
        !           389:     extents->y1 = FirstPtBlock->pts[0].y;
        !           390:     extents->x1 = MAXSHORT,  extents->x2 = MINSHORT;
        !           391:  
        !           392:     while (numFullPtBlocks--) {
        !           393:         i = NUMPTSTOBUFFER >> 1;  /* the loop uses 2 points per iteration */
        !           394:         pts = CurPtBlock->pts;
        !           395:         while (i--) {
        !           396:             rects->x1 = pts->x,  rects->y1 = pts->y;
        !           397:             extents->x1 = MIN(extents->x1, pts->x);
        !           398:             pts++;
        !           399:             rects->x2 = pts->x,  rects->y2 = pts->y + 1;
        !           400:             extents->x2 = MAX(extents->x2, pts->x);
        !           401:             rects++,  pts++;
        !           402:         }
        !           403:         CurPtBlock = CurPtBlock->next;
        !           404:     }
        !           405: 
        !           406:     extents->y2 = CurPtBlock->pts[iCurPtBlock-1].y+1;
        !           407:     pts = CurPtBlock->pts;
        !           408:     iCurPtBlock >>= 1;
        !           409:     while (iCurPtBlock--) {
        !           410:         rects->x1 = pts->x,  rects->y1 = pts->y;
        !           411:         extents->x1 = MIN(extents->x1, pts->x);
        !           412:         pts++;
        !           413:         rects->x2 = pts->x,  rects->y2 = pts->y + 1;
        !           414:         extents->x2 = MAX(extents->x2, pts->x);
        !           415:         rects++,  pts++;
        !           416:     }
        !           417:  
        !           418:     reg->size = reg->numRects = numRects;
        !           419:  
        !           420:     return(TRUE);
        !           421: }
        !           422: 
        !           423: Region XCreateRegion();
        !           424: /*
        !           425:  *     polytoregion
        !           426:  *
        !           427:  *     Scan converts a polygon by returning a run-length
        !           428:  *     encoding of the resultant bitmap -- the run-length
        !           429:  *     encoding is in the form of an array of rectangles.
        !           430:  */
        !           431: Region 
        !           432: XPolygonRegion(Pts, Count, rule)
        !           433:     int       Count;                 /* number of pts           */
        !           434:     XPoint     *Pts;                /* the pts                 */
        !           435:     int        rule;                        /* winding rule */
        !           436: {
        !           437:     Region region;
        !           438:     register EdgeTableEntry *pAET;   /* Active Edge Table       */
        !           439:     register int y;                  /* current scanline        */
        !           440:     register int iPts = 0;           /* number of pts in buffer */
        !           441:     register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
        !           442:     register ScanLineList *pSLL;     /* current scanLineList    */
        !           443:     register XPoint *pts;             /* output buffer           */
        !           444:     EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
        !           445:     EdgeTable ET;                    /* header node for ET      */
        !           446:     EdgeTableEntry AET;              /* header node for AET     */
        !           447:     EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
        !           448:     ScanLineListBlock SLLBlock;      /* header for scanlinelist */
        !           449:     int fixWAET = FALSE;
        !           450:     POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
        !           451:     POINTBLOCK *tmpPtBlock;
        !           452:     int numFullPtBlocks = 0;
        !           453:  
        !           454:     pETEs = (EdgeTableEntry *)Xalloca(sizeof(EdgeTableEntry) * Count);
        !           455:     pts = FirstPtBlock.pts;
        !           456:     CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
        !           457:     pSLL = ET.scanlines.next;
        !           458:     curPtBlock = &FirstPtBlock;
        !           459:  
        !           460:     if (rule == EvenOddRule) {
        !           461:         /*
        !           462:          *  for each scanline
        !           463:          */
        !           464:         for (y = ET.ymin; y < ET.ymax; y++) {
        !           465:             /*
        !           466:              *  Add a new edge to the active edge table when we
        !           467:              *  get to the next edge.
        !           468:              */
        !           469:             if (pSLL != NULL && y == pSLL->scanline) {
        !           470:                 loadAET(&AET, pSLL->edgelist);
        !           471:                 pSLL = pSLL->next;
        !           472:             }
        !           473:             pPrevAET = &AET;
        !           474:             pAET = AET.next;
        !           475:  
        !           476:             /*
        !           477:              *  for each active edge
        !           478:              */
        !           479:             while (pAET) {
        !           480:                 pts->x = pAET->bres.minor_axis,  pts->y = y;
        !           481:                 pts++, iPts++;
        !           482:  
        !           483:                 /*
        !           484:                  *  send out the buffer
        !           485:                  */
        !           486:                 if (iPts == NUMPTSTOBUFFER) {
        !           487:                     tmpPtBlock = (POINTBLOCK *)Xalloca(sizeof(POINTBLOCK));
        !           488:                     curPtBlock->next = tmpPtBlock;
        !           489:                     curPtBlock = tmpPtBlock;
        !           490:                     pts = curPtBlock->pts;
        !           491:                     numFullPtBlocks++;
        !           492:                     iPts = 0;
        !           493:                 }
        !           494:                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
        !           495:             }
        !           496:             (void) InsertionSort(&AET);
        !           497:         }
        !           498:     }
        !           499:     else {
        !           500:         /*
        !           501:          *  for each scanline
        !           502:          */
        !           503:         for (y = ET.ymin; y < ET.ymax; y++) {
        !           504:             /*
        !           505:              *  Add a new edge to the active edge table when we
        !           506:              *  get to the next edge.
        !           507:              */
        !           508:             if (pSLL != NULL && y == pSLL->scanline) {
        !           509:                 loadAET(&AET, pSLL->edgelist);
        !           510:                 computeWAET(&AET);
        !           511:                 pSLL = pSLL->next;
        !           512:             }
        !           513:             pPrevAET = &AET;
        !           514:             pAET = AET.next;
        !           515:             pWETE = pAET;
        !           516:  
        !           517:             /*
        !           518:              *  for each active edge
        !           519:              */
        !           520:             while (pAET) {
        !           521:                 /*
        !           522:                  *  add to the buffer only those edges that
        !           523:                  *  are in the Winding active edge table.
        !           524:                  */
        !           525:                 if (pWETE == pAET) {
        !           526:                     pts->x = pAET->bres.minor_axis,  pts->y = y;
        !           527:                     pts++, iPts++;
        !           528:  
        !           529:                     /*
        !           530:                      *  send out the buffer
        !           531:                      */
        !           532:                     if (iPts == NUMPTSTOBUFFER) {
        !           533:                         tmpPtBlock = (POINTBLOCK *)Xalloca(sizeof(POINTBLOCK));
        !           534:                         curPtBlock->next = tmpPtBlock;
        !           535:                         curPtBlock = tmpPtBlock;
        !           536:                         pts = curPtBlock->pts;
        !           537:                         numFullPtBlocks++;    iPts = 0;
        !           538:                     }
        !           539:                     pWETE = pWETE->nextWETE;
        !           540:                 }
        !           541:                 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
        !           542:             }
        !           543:  
        !           544:             /*
        !           545:              *  recompute the winding active edge table if
        !           546:              *  we just resorted or have exited an edge.
        !           547:              */
        !           548:             if (InsertionSort(&AET) || fixWAET) {
        !           549:                 computeWAET(&AET);
        !           550:                 fixWAET = FALSE;
        !           551:             }
        !           552:         }
        !           553:     }
        !           554:     FreeStorage(SLLBlock.next);        
        !           555:     region = XCreateRegion();
        !           556:     (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
        !           557:     return(region);
        !           558: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.