Return to mipolyutil.c CVS log

Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi

Annotation of researchv9/X11/src/X.V11R1/server/ddx/mi/mipolyutil.c, revision 1.1

1.1     ! root        1: /***********************************************************
        !             2: Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
        !             3: and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
        !             4: 
        !             5:                         All Rights Reserved
        !             6: 
        !             7: Permission to use, copy, modify, and distribute this software and its 
        !             8: documentation for any purpose and without fee is hereby granted, 
        !             9: provided that the above copyright notice appear in all copies and that
        !            10: both that copyright notice and this permission notice appear in 
        !            11: supporting documentation, and that the names of Digital or MIT not be
        !            12: used in advertising or publicity pertaining to distribution of the
        !            13: software without specific, written prior permission.  
        !            14: 
        !            15: DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
        !            16: ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
        !            17: DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
        !            18: ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
        !            19: WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
        !            20: ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
        !            21: SOFTWARE.
        !            22: 
        !            23: ******************************************************************/
        !            24: /* $Header: mipolyutil.c,v 1.12 87/09/11 07:19:12 toddb Exp $ */
        !            25: #include "miscstruct.h"
        !            26: #include "gc.h"
        !            27: #include "miscanfill.h"
        !            28: #include "mipoly.h"
        !            29: 
        !            30: #define MAXINT 0x7fffffff
        !            31: #define MININT -MAXINT
        !            32: 
        !            33: /*
        !            34:  *     fillUtils.c
        !            35:  *
        !            36:  *     Written by Brian Kelleher;  Oct. 1985
        !            37:  *
        !            38:  *     This module contains all of the utility functions
        !            39:  *     needed to scan convert a polygon.
        !            40:  *
        !            41:  */
        !            42: 
        !            43: /*
        !            44:  *     InsertEdgeInET
        !            45:  *
        !            46:  *     Insert the given edge into the edge table.
        !            47:  *     First we must find the correct bucket in the
        !            48:  *     Edge table, then find the right slot in the
        !            49:  *     bucket.  Finally, we can insert it.
        !            50:  *
        !            51:  */
        !            52: void
        !            53: miInsertEdgeInET(ET, ETE, scanline, SLLBlock, iSLLBlock)
        !            54:     EdgeTable *ET;
        !            55:     EdgeTableEntry *ETE;
        !            56:     int scanline;
        !            57:     ScanLineListBlock **SLLBlock;
        !            58:     int *iSLLBlock;
        !            59: {
        !            60:     register EdgeTableEntry *start, *prev;
        !            61:     register ScanLineList *pSLL, *pPrevSLL;
        !            62:     ScanLineListBlock *tmpSLLBlock;
        !            63: 
        !            64:     /*
        !            65:      * find the right bucket to put the edge into
        !            66:      */
        !            67:     pPrevSLL = &ET->scanlines;
        !            68:     pSLL = pPrevSLL->next;
        !            69:     while (pSLL && (pSLL->scanline < scanline)) 
        !            70:     {
        !            71:         pPrevSLL = pSLL;
        !            72:         pSLL = pSLL->next;
        !            73:     }
        !            74: 
        !            75:     /*
        !            76:      * reassign pSLL (pointer to ScanLineList) if necessary
        !            77:      */
        !            78:     if ((!pSLL) || (pSLL->scanline > scanline)) 
        !            79:     {
        !            80:         if (*iSLLBlock > SLLSPERBLOCK-1) 
        !            81:         {
        !            82:             tmpSLLBlock = 
        !            83:                  (ScanLineListBlock *)Xalloc(sizeof(ScanLineListBlock));
        !            84:             (*SLLBlock)->next = tmpSLLBlock;
        !            85:             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
        !            86:             *SLLBlock = tmpSLLBlock;
        !            87:             *iSLLBlock = 0;
        !            88:         }
        !            89:         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
        !            90: 
        !            91:         pSLL->next = pPrevSLL->next;
        !            92:         pSLL->edgelist = (EdgeTableEntry *)NULL;
        !            93:         pPrevSLL->next = pSLL;
        !            94:     }
        !            95:     pSLL->scanline = scanline;
        !            96: 
        !            97:     /*
        !            98:      * now insert the edge in the right bucket
        !            99:      */
        !           100:     prev = (EdgeTableEntry *)NULL;
        !           101:     start = pSLL->edgelist;
        !           102:     while (start && (start->bres.minor < ETE->bres.minor)) 
        !           103:     {
        !           104:         prev = start;
        !           105:         start = start->next;
        !           106:     }
        !           107:     ETE->next = start;
        !           108: 
        !           109:     if (prev)
        !           110:         prev->next = ETE;
        !           111:     else
        !           112:         pSLL->edgelist = ETE;
        !           113: }
        !           114: 
        !           115: /*
        !           116:  *     CreateEdgeTable
        !           117:  *
        !           118:  *     This routine creates the edge table for
        !           119:  *     scan converting polygons. 
        !           120:  *     The Edge Table (ET) looks like:
        !           121:  *
        !           122:  *    EdgeTable
        !           123:  *     --------
        !           124:  *    |  ymax  |        ScanLineLists
        !           125:  *    |scanline|-->------------>-------------->...
        !           126:  *     --------   |scanline|   |scanline|
        !           127:  *                |edgelist|   |edgelist|
        !           128:  *                ---------    ---------
        !           129:  *                    |             |
        !           130:  *                    |             |
        !           131:  *                    V             V
        !           132:  *              list of ETEs   list of ETEs
        !           133:  *
        !           134:  *     where ETE is an EdgeTableEntry data structure,
        !           135:  *     and there is one ScanLineList per scanline at
        !           136:  *     which an edge is initially entered.
        !           137:  *
        !           138:  */
        !           139: 
        !           140: void
        !           141: miCreateETandAET(count, pts, ET, AET, pETEs, pSLLBlock)
        !           142:     register int count;
        !           143:     register DDXPointPtr pts;
        !           144:     EdgeTable *ET;
        !           145:     EdgeTableEntry *AET;
        !           146:     register EdgeTableEntry *pETEs;
        !           147:     ScanLineListBlock   *pSLLBlock;
        !           148: {
        !           149:     register DDXPointPtr top, bottom;
        !           150:     register DDXPointPtr PrevPt, CurrPt;
        !           151:     int iSLLBlock = 0;
        !           152: 
        !           153:     int dy;
        !           154: 
        !           155:     if (count < 2)  return;
        !           156: 
        !           157:     /*
        !           158:      *  initialize the Active Edge Table
        !           159:      */
        !           160:     AET->next = (EdgeTableEntry *)NULL;
        !           161:     AET->back = (EdgeTableEntry *)NULL;
        !           162:     AET->nextWETE = (EdgeTableEntry *)NULL;
        !           163:     AET->bres.minor = MININT;
        !           164: 
        !           165:     /*
        !           166:      *  initialize the Edge Table.
        !           167:      */
        !           168:     ET->scanlines.next = (ScanLineList *)NULL;
        !           169:     ET->ymax = MININT;
        !           170:     ET->ymin = MAXINT;
        !           171:     pSLLBlock->next = (ScanLineListBlock *)NULL;
        !           172: 
        !           173:     PrevPt = &pts[count-1];
        !           174: 
        !           175:     /*
        !           176:      *  for each vertex in the array of points.
        !           177:      *  In this loop we are dealing with two vertices at
        !           178:      *  a time -- these make up one edge of the polygon.
        !           179:      */
        !           180:     while (count--) 
        !           181:     {
        !           182:         CurrPt = pts++;
        !           183: 
        !           184:         /*
        !           185:          *  find out which point is above and which is below.
        !           186:          */
        !           187:         if (PrevPt->y > CurrPt->y) 
        !           188:         {
        !           189:             bottom = PrevPt, top = CurrPt;
        !           190:             pETEs->ClockWise = 0;
        !           191:         }
        !           192:         else 
        !           193:         {
        !           194:             bottom = CurrPt, top = PrevPt;
        !           195:             pETEs->ClockWise = 1;
        !           196:         }
        !           197: 
        !           198:         /*
        !           199:          * don't add horizontal edges to the Edge table.
        !           200:          */
        !           201:         if (bottom->y != top->y) 
        !           202:         {
        !           203:             pETEs->ymax = bottom->y-1;  /* -1 so we don't get last scanline */
        !           204: 
        !           205:             /*
        !           206:              *  initialize integer edge algorithm
        !           207:              */
        !           208:             dy = bottom->y - top->y;
        !           209:             BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
        !           210: 
        !           211:             miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
        !           212: 
        !           213:             ET->ymax = max(ET->ymax, PrevPt->y);
        !           214:             ET->ymin = min(ET->ymin, PrevPt->y);
        !           215:             pETEs++;
        !           216:         }
        !           217: 
        !           218:         PrevPt = CurrPt;
        !           219:     }
        !           220: }
        !           221: 
        !           222: /*
        !           223:  *     loadAET
        !           224:  *
        !           225:  *     This routine moves EdgeTableEntries from the
        !           226:  *     EdgeTable into the Active Edge Table,
        !           227:  *     leaving them sorted by smaller x coordinate.
        !           228:  *
        !           229:  */
        !           230: 
        !           231: void
        !           232: miloadAET(AET, ETEs)
        !           233:     register EdgeTableEntry *AET, *ETEs;
        !           234: {
        !           235:     register EdgeTableEntry *pPrevAET;
        !           236:     register EdgeTableEntry *tmp;
        !           237: 
        !           238:     pPrevAET = AET;
        !           239:     AET = AET->next;
        !           240:     while (ETEs) 
        !           241:     {
        !           242:         while (AET && (AET->bres.minor < ETEs->bres.minor)) 
        !           243:         {
        !           244:             pPrevAET = AET;
        !           245:             AET = AET->next;
        !           246:         }
        !           247:         tmp = ETEs->next;
        !           248:         ETEs->next = AET;
        !           249:         if (AET)
        !           250:             AET->back = ETEs;
        !           251:         ETEs->back = pPrevAET;
        !           252:         pPrevAET->next = ETEs;
        !           253:         pPrevAET = ETEs;
        !           254: 
        !           255:         ETEs = tmp;
        !           256:     }
        !           257: }
        !           258: 
        !           259: /*
        !           260:  *     computeWAET
        !           261:  *
        !           262:  *     This routine links the AET by the
        !           263:  *     nextWETE (winding EdgeTableEntry) link for
        !           264:  *     use by the winding number rule.  The final 
        !           265:  *     Active Edge Table (AET) might look something
        !           266:  *     like:
        !           267:  *
        !           268:  *     AET
        !           269:  *     ----------  ---------   ---------
        !           270:  *     |ymax    |  |ymax    |  |ymax    | 
        !           271:  *     | ...    |  |...     |  |...     |
        !           272:  *     |next    |->|next    |->|next    |->...
        !           273:  *     |nextWETE|  |nextWETE|  |nextWETE|
        !           274:  *     ---------   ---------   ^--------
        !           275:  *         |                   |       |
        !           276:  *         V------------------->       V---> ...
        !           277:  *
        !           278:  */
        !           279: void
        !           280: micomputeWAET(AET)
        !           281:     register EdgeTableEntry *AET;
        !           282: {
        !           283:     register EdgeTableEntry *pWETE;
        !           284:     register int inside = 1;
        !           285:     register int isInside = 0;
        !           286: 
        !           287:     AET->nextWETE = (EdgeTableEntry *)NULL;
        !           288:     pWETE = AET;
        !           289:     AET = AET->next;
        !           290:     while (AET) 
        !           291:     {
        !           292:         if (AET->ClockWise)
        !           293:             isInside++;
        !           294:         else
        !           295:             isInside--;
        !           296: 
        !           297:         if ((!inside && !isInside) ||
        !           298:             ( inside &&  isInside)) 
        !           299:         {
        !           300:             pWETE->nextWETE = AET;
        !           301:             pWETE = AET;
        !           302:             inside = !inside;
        !           303:         }
        !           304:         AET = AET->next;
        !           305:     }
        !           306:     pWETE->nextWETE = (EdgeTableEntry *)NULL;
        !           307: }
        !           308: 
        !           309: /*
        !           310:  *     InsertionSort
        !           311:  *
        !           312:  *     Just a simple insertion sort using
        !           313:  *     pointers and back pointers to sort the Active
        !           314:  *     Edge Table.
        !           315:  *
        !           316:  */
        !           317: 
        !           318: int
        !           319: miInsertionSort(AET)
        !           320:     register EdgeTableEntry *AET;
        !           321: {
        !           322:     register EdgeTableEntry *pETEchase;
        !           323:     register EdgeTableEntry *pETEinsert;
        !           324:     register EdgeTableEntry *pETEchaseBackTMP;
        !           325:     register int changed = 0;
        !           326: 
        !           327:     AET = AET->next;
        !           328:     while (AET) 
        !           329:     {
        !           330:         pETEinsert = AET;
        !           331:         pETEchase = AET;
        !           332:         while (pETEchase->back->bres.minor > AET->bres.minor)
        !           333:             pETEchase = pETEchase->back;
        !           334: 
        !           335:         AET = AET->next;
        !           336:         if (pETEchase != pETEinsert) 
        !           337:         {
        !           338:             pETEchaseBackTMP = pETEchase->back;
        !           339:             pETEinsert->back->next = AET;
        !           340:             if (AET)
        !           341:                 AET->back = pETEinsert->back;
        !           342:             pETEinsert->next = pETEchase;
        !           343:             pETEchase->back->next = pETEinsert;
        !           344:             pETEchase->back = pETEinsert;
        !           345:             pETEinsert->back = pETEchaseBackTMP;
        !           346:             changed = 1;
        !           347:         }
        !           348:     }
        !           349:     return(changed);
        !           350: }
        !           351: 
        !           352: /*
        !           353:  *     Clean up our act.
        !           354:  */
        !           355: void
        !           356: miFreeStorage(pSLLBlock)
        !           357:     register ScanLineListBlock   *pSLLBlock;
        !           358: {
        !           359:     register ScanLineListBlock   *tmpSLLBlock;
        !           360: 
        !           361:     while (pSLLBlock) 
        !           362:     {
        !           363:         tmpSLLBlock = pSLLBlock->next;
        !           364:         Xfree(pSLLBlock);
        !           365:         pSLLBlock = tmpSLLBlock;
        !           366:     }
        !           367: }

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