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