![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mipolyutil.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 / server / ddx / mi|
Return to mipolyutil.c CVS log | Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi |
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.