Return to makemask.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / new / X / libibm / libsrc

Annotation of 43BSDTahoe/new/X/libibm/libsrc/makemask.c, revision 1.1

1.1     ! root        1: #ifndef lint
        !             2: static char *rcsid_makemask_c = "$Header: makemask.c,v 10.1 86/11/19 10:42:30 jg Exp $";
        !             3: #endif lint
        !             4: /* makemask.c -  builds a mask from vertex list
        !             5:  *
        !             6:  *     MakeMask     builds a mask from vertex list
        !             7:  *     AddEdge      adds edges to edge table for fill operation
        !             8:  *     FillMask     fills mask using scan line algorithm
        !             9:  *
        !            10:  *     Author:
        !            11:  *             Scott Bates
        !            12:  *             Brown University
        !            13:  *             IRIS, Box 1946
        !            14:  *             Providence, RI 02912
        !            15:  *
        !            16:  *
        !            17:  *             Copyright (c) 1986 Brown University
        !            18:  *
        !            19:  * Permission to use, copy, modify and distribute this software and its
        !            20:  * documentation for any purpose and without fee is hereby granted, provided
        !            21:  * that the above copyright notice appear in all copies, and that both
        !            22:  * that copyright notice and this permission notice appear in supporting
        !            23:  * documentation, and that the name of Brown University not be used in
        !            24:  * advertising or publicity pertaining to distribution of the software
        !            25:  * without specific, written prior permission. Brown University makes no
        !            26:  * representations about the suitability of this software for any purpose.
        !            27:  * It is provided "as-is" without express or implied warranty.
        !            28:  */
        !            29: 
        !            30: #include "private.h"
        !            31: #include "makemask.h"
        !            32: #include "pathlist.h"
        !            33: 
        !            34: /*
        !            35:  * Build mask from vertex list
        !            36:  */
        !            37: 
        !            38: BITMAP *
        !            39: MakeMask(Verts, VertCount)
        !            40:        Vertex *Verts;
        !            41:        int VertCount;
        !            42: {
        !            43:        register Vertex *LastPoint;
        !            44:        register Vertex *ThisPoint;
        !            45:        register Vertex *NextPoint;
        !            46:        register Vertex *Poly;
        !            47:        register struct Polygon *PolyData;
        !            48:        register End;
        !            49:        int Width = 0, Height = 0;
        !            50:        int FirstScanLine = 10240;
        !            51:        int Index, Size;
        !            52:        BITMAP *BitMap;
        !            53:        struct Polygon *FirstPoly;
        !            54: 
        !            55: #ifdef TRACE_X
        !            56:         fprintf (stderr, "In MakeMask\n");
        !            57:         fflush (stderr);
        !            58: #endif TRACE_X
        !            59: 
        !            60:        /*
        !            61:         * Allocate space for polygon pointers
        !            62:         */
        !            63: 
        !            64:        FirstPoly = (struct Polygon *) calloc(VertCount << 1,
        !            65:                   sizeof(struct Polygon));
        !            66:         if (FirstPoly == NULL) {
        !            67:             return (NULL);
        !            68:         }
        !            69: 
        !            70:        /*
        !            71:         * Determine width and height of off-screen bitmap
        !            72:         * and the first scan line to be filled.
        !            73:         */
        !            74: 
        !            75:        PolyData = FirstPoly - 1;
        !            76:        for(Index = 0; Index < VertCount; Index += 2) {
        !            77:                if(Width < Verts[Index].x)
        !            78:                        Width = Verts[Index].x;
        !            79:                if(Height < Verts[Index].y)
        !            80:                        Height = Verts[Index].y;
        !            81:                if(FirstScanLine > Verts[Index].y)
        !            82:                        FirstScanLine = Verts[Index].y;
        !            83:                if(Verts[Index].flags & START_OF_CLOSED_POLY) {
        !            84:                        (++PolyData)->PolyPoints = &Verts[Index];
        !            85:                        PolyData->PolyCount = 2;
        !            86:                } else {
        !            87:                        PolyData->PolyCount += 2;
        !            88:                }
        !            89:        }
        !            90:        (++PolyData)->PolyPoints = (Vertex *)NULL;
        !            91: 
        !            92:         /*
        !            93:          * Allocate space for bitmap structure
        !            94:          */
        !            95: 
        !            96:         BitMap = (BITMAP *) Xalloc (sizeof (BITMAP));
        !            97: 
        !            98:         /*
        !            99:          * Fill in bitmap structure
        !           100:         *
        !           101:         * NOTE: The bitmaps width has been rounded up 
        !           102:         *       to the nearest 32 bit bound. This was done
        !           103:         *       so that the mask could be fill 32 bits at
        !           104:         *       a time instead of the usual 16.
        !           105:          */
        !           106: 
        !           107:         BitMap->width = Width = ((Width + 32) >> 5) << 5;
        !           108:         BitMap->height = ++Height;
        !           109: 
        !           110:         /*
        !           111:          * Allocated space to hold bitimage data
        !           112:          */
        !           113:        
        !           114:         if((BitMap->data = calloc(1, BitmapSize(Width, Height))) == NULL) {
        !           115:             free ((caddr_t) BitMap);
        !           116:             return (NULL);
        !           117:         }
        !           118: 
        !           119:        /*
        !           120:         * Allocate space for edges and reset EdgeCount
        !           121:         */
        !           122: 
        !           123:        Edges = (struct edge *) calloc(VertCount << 1, sizeof(struct edge));
        !           124:         if (Edges == NULL) {
        !           125:             free ((caddr_t) BitMap->data);
        !           126:             free ((caddr_t) BitMap);
        !           127:             return (NULL);
        !           128:         }
        !           129:         if ((EdgeTable = (struct edge **)calloc(Height + 1, 4)) == NULL) {
        !           130:            free((caddr_t) Edges);
        !           131:             free ((caddr_t) BitMap->data);
        !           132:             free ((caddr_t) BitMap);
        !           133:             return (NULL);
        !           134:         }
        !           135:        EdgeCount = 0;
        !           136: 
        !           137:        /*
        !           138:         * Add the edges of all polygons to
        !           139:         * the edge table
        !           140:         */
        !           141: 
        !           142:        Poly = (PolyData = FirstPoly)->PolyPoints;
        !           143:        do {
        !           144:                /*
        !           145:                 * Test for valid polygon
        !           146:                 */
        !           147: 
        !           148:                if(PolyData->PolyCount > 5) {
        !           149:                        /*
        !           150:                         * AddEdge() initialization before adding
        !           151:                         * each polygon
        !           152:                         */
        !           153: 
        !           154:                        ShortenStartOfEdge = 0;
        !           155:                        Direction = Poly[PolyData->PolyCount - 2].y > Poly[0].y;
        !           156:                        End = PolyData->PolyCount - 4;
        !           157:                        LastPoint = Poly;
        !           158:                        ThisPoint = NextPoint =  Poly + 2;
        !           159: 
        !           160:                        /*
        !           161:                         * Add edges of this polygon to edge table
        !           162:                         */
        !           163: 
        !           164:                        while(End) {
        !           165:                                NextPoint += 2;
        !           166:                                AddEdge(LastPoint, ThisPoint, NextPoint);
        !           167:                                LastPoint = ThisPoint;
        !           168:                                ThisPoint = NextPoint;
        !           169:                                End -= 2;
        !           170:                        }
        !           171:                        NextPoint = &Poly[0];
        !           172:                        AddEdge(LastPoint, ThisPoint, NextPoint);
        !           173:                        LastPoint = ThisPoint;
        !           174:                        ThisPoint = NextPoint;
        !           175:                        NextPoint += 2;
        !           176:                        AddEdge(LastPoint, ThisPoint, NextPoint);
        !           177:                }
        !           178: 
        !           179:                /*
        !           180:                 * Increment pointer to next polygon to add
        !           181:                 */
        !           182: 
        !           183:                Poly = (++PolyData)->PolyPoints;
        !           184: 
        !           185:        } while(Poly);
        !           186: 
        !           187:        if(EdgeCount) {
        !           188:                /*
        !           189:                 * Fill the mask
        !           190:                 */
        !           191: 
        !           192:                FillMask(BitMap, FirstScanLine);
        !           193: 
        !           194:                /*
        !           195:                 * Frame mask to remove any abnomalities
        !           196:                 */
        !           197: 
        !           198:                for (Index = 0; Index < VertCount; Index += 2) {
        !           199:                        SinglePixelLine(BitMap, Verts[Index].x, Verts[Index].y,
        !           200:                                        Verts[Index + 1].x, Verts[Index + 1].y,
        !           201:                                        (CLIP *) 0, GXor, DrawSolidLine, 1, 0,
        !           202:                                        0, 0, 0);
        !           203:                }
        !           204: 
        !           205:                /* 
        !           206:                 * Return mask bitmap
        !           207:                 */
        !           208: 
        !           209:                return(BitMap);
        !           210:        }
        !           211: 
        !           212:        /*
        !           213:         * Indicate nothing to fill
        !           214:         */
        !           215: 
        !           216:        return(NULL);
        !           217: }
        !           218: 
        !           219: /*
        !           220:  * Add edge to edge table
        !           221:  */
        !           222: 
        !           223: static
        !           224: AddEdge(LastPoint, ThisPoint, NextPoint)
        !           225:     register Vertex *LastPoint;
        !           226:     register Vertex *ThisPoint;
        !           227:     register Vertex *NextPoint;
        !           228: {
        !           229:     register struct edge *NewEdge = &Edges[EdgeCount];
        !           230: 
        !           231: #ifdef TRACE_X
        !           232:     fprintf (stderr, "In AddEdge\n");
        !           233:     fflush (stderr);
        !           234: #endif TRACE_X
        !           235: 
        !           236:     /*
        !           237:      * Fill in new edge data
        !           238:      */
        !           239: 
        !           240:     if (ThisPoint->y != LastPoint->y) {
        !           241:        register Min_Y;
        !           242: 
        !           243:         if (ThisPoint->y < LastPoint->y) {
        !           244:             Min_Y = ThisPoint->y;
        !           245:             NewEdge->Min_X = SHIFT_LEFT_16(ThisPoint->x);
        !           246:             NewEdge->Max_Y = LastPoint->y;
        !           247:             NewEdge->Delta_X = SHIFT_LEFT_16(LastPoint->x - ThisPoint->x) /
        !           248:                                (LastPoint->y - ThisPoint->y);
        !           249:         } else {
        !           250:             Min_Y = LastPoint->y;
        !           251:             NewEdge->Min_X = SHIFT_LEFT_16(LastPoint->x);
        !           252:             NewEdge->Max_Y = ThisPoint->y;
        !           253:             NewEdge->Delta_X = SHIFT_LEFT_16(ThisPoint->x - LastPoint->x) /
        !           254:                                (ThisPoint->y - LastPoint->y);  
        !           255:         }
        !           256: 
        !           257:        /*
        !           258:         * Shorten edge if not maxima or minima (shortens end of edge)
        !           259:         */
        !           260: 
        !           261:         if((ThisPoint->y > LastPoint->y) ?
        !           262:           (NextPoint->y > ThisPoint->y) : (NextPoint->y < ThisPoint->y)) {
        !           263:                if (LastPoint->y > ThisPoint->y) {
        !           264:                        Min_Y++;
        !           265:                        NewEdge->Min_X += NewEdge->Delta_X;
        !           266:                } else  {
        !           267:                        NewEdge->Max_Y--;
        !           268:                }
        !           269:         }
        !           270: 
        !           271:        /*
        !           272:         * Check to see if this edge needs to be shortened
        !           273:         * at its start.
        !           274:         */
        !           275: 
        !           276:        if(ShortenStartOfEdge) {
        !           277:                if (ThisPoint->y > LastPoint->y) {
        !           278:                        Min_Y++;
        !           279:                        NewEdge->Min_X += NewEdge->Delta_X;
        !           280:                } else  {
        !           281:                        NewEdge->Max_Y--;
        !           282:                }
        !           283:                ShortenStartOfEdge = 0;
        !           284:        }
        !           285: 
        !           286:        /*
        !           287:         * Save direction of this edge
        !           288:         */
        !           289: 
        !           290:        if (NextPoint->y == ThisPoint->y) {
        !           291:                Direction = LastPoint->y > ThisPoint->y;
        !           292:        }
        !           293: 
        !           294:        /*
        !           295:         * Insert edge into edge table
        !           296:         */
        !           297: 
        !           298:         if (NewEdge->Max_Y >= Min_Y) {
        !           299:            register struct edge *EdgeList = (struct edge *)&EdgeTable[Min_Y];
        !           300: 
        !           301:            while(EdgeList->NextEdge) {
        !           302:                if(EdgeList->NextEdge->Min_X >= NewEdge->Min_X)
        !           303:                    break;
        !           304:                EdgeList = EdgeList->NextEdge;
        !           305:            }
        !           306:            NewEdge->NextEdge = EdgeList->NextEdge;
        !           307:            EdgeList->NextEdge = NewEdge;
        !           308:            EdgeCount++;
        !           309:         }
        !           310:     } else  { 
        !           311:        /*
        !           312:         * This is a horizontal edge. Therefore, if there is
        !           313:         * a change of direction between the preceding edge and
        !           314:         * and the next edge the next edge must be shortened at its 
        !           315:         * start.
        !           316:         */
        !           317: 
        !           318:        if(NextPoint->y != ThisPoint->y &&
        !           319:           (Direction != (NextPoint->y > ThisPoint->y))) {
        !           320:                ShortenStartOfEdge++;
        !           321:        }
        !           322:     }
        !           323: }
        !           324: 
        !           325: /*
        !           326:  * Fill polygon(s) to create mask
        !           327:  */
        !           328: 
        !           329: static
        !           330: FillMask(BitMap, FirstScanLine)
        !           331:     BITMAP *BitMap;
        !           332:     int FirstScanLine;
        !           333: {
        !           334:     register long *Bits;
        !           335:     register Start, Stop;
        !           336:     register FirstWord, LastWord;
        !           337:     register struct edge *AET;
        !           338:     struct edge *ActiveEdgeTable;
        !           339:     struct edge *TempEdge;
        !           340:     int NumberOfWords, CurrentScanLine, SortAgain;
        !           341: 
        !           342: #ifdef TRACE_X
        !           343:     fprintf (stderr, "In FillMask\n");
        !           344:     fflush (stderr);
        !           345: #endif TRACE_X
        !           346: 
        !           347:     NumberOfWords = (BitMap->width + 31) >> 5;
        !           348:     Bits = (long *)BitMap->data + FirstScanLine * NumberOfWords;
        !           349:     ActiveEdgeTable = EdgeTable[FirstScanLine];
        !           350:     CurrentScanLine = FirstScanLine;
        !           351: 
        !           352:     while(EdgeCount) {
        !           353:            /*
        !           354:             * Fill all ranges for current scan line
        !           355:             */
        !           356: 
        !           357:            AET = (struct edge *)&ActiveEdgeTable;
        !           358: 
        !           359:            while(AET->NextEdge && AET->NextEdge->NextEdge) {
        !           360:                Start = ROUND_16(AET->NextEdge->Min_X);
        !           361:                Stop = ROUND_16(AET->NextEdge->NextEdge->Min_X);
        !           362: 
        !           363:                if ((FirstWord = Start >> 5) < (LastWord = Stop >> 5)) {
        !           364:                        Bits[FirstWord] |= RightMasks[Start & 0x1F];
        !           365:                        while (++FirstWord < LastWord)
        !           366:                                Bits[FirstWord] = 0xFFFFFFFF;
        !           367:                        Bits[LastWord] |= LeftMasks[Stop & 0x1F];
        !           368:                } else {
        !           369:                        Bits[FirstWord] |= (RightMasks[Start & 0x1F] &
        !           370:                                LeftMasks[Stop & 0x1F]);
        !           371:                }
        !           372: 
        !           373:                AET = AET->NextEdge->NextEdge;
        !           374:            }
        !           375:            Bits += NumberOfWords;
        !           376: 
        !           377:            /*
        !           378:             * Remove finished edges from active edge table 
        !           379:             * and add any new edges for next scan line.
        !           380:             */
        !           381: 
        !           382:            AET = (struct edge *)&ActiveEdgeTable;
        !           383:            while(AET->NextEdge) {
        !           384:                    if(AET->NextEdge->Max_Y == CurrentScanLine) {
        !           385:                            AET->NextEdge = AET->NextEdge->NextEdge;
        !           386:                            EdgeCount--;
        !           387:                    } else  {
        !           388:                            AET->NextEdge->Min_X += AET->NextEdge->Delta_X;
        !           389:                            AET = AET->NextEdge;
        !           390:                    }
        !           391:            }
        !           392:            AET->NextEdge = EdgeTable[++CurrentScanLine];
        !           393: 
        !           394:            /*
        !           395:             * Sort active edge table
        !           396:             */
        !           397: 
        !           398:            do {
        !           399:                SortAgain = 0;
        !           400:                AET = (struct edge *)&ActiveEdgeTable;
        !           401:                while(AET->NextEdge && AET->NextEdge->NextEdge) {
        !           402:                    if(AET->NextEdge->Min_X > AET->NextEdge->NextEdge->Min_X) {
        !           403:                        TempEdge = AET->NextEdge;
        !           404:                        AET->NextEdge = AET->NextEdge->NextEdge;
        !           405:                        TempEdge->NextEdge = AET->NextEdge->NextEdge;
        !           406:                        AET->NextEdge->NextEdge = TempEdge;
        !           407:                        SortAgain = 1;
        !           408:                    }
        !           409:                    AET = AET->NextEdge;
        !           410:                }
        !           411:            }while(SortAgain);
        !           412:     }
        !           413:     free((caddr_t) EdgeTable);
        !           414:     free((caddr_t) Edges);
        !           415: }

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