![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to XPolyReg.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / lib / X|
Return to XPolyReg.c CVS log | Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / lib / X |
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 = ®->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.