![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to makemask.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / new / X / libibm / libsrc|
Return to makemask.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / new / X / libibm / libsrc |
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.