|
1 /**************************************************************************** |
|
2 ** |
|
3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). |
|
4 ** All rights reserved. |
|
5 ** Contact: Nokia Corporation (qt-info@nokia.com) |
|
6 ** |
|
7 ** This file is part of the Qt3Support module of the Qt Toolkit. |
|
8 ** |
|
9 ** $QT_BEGIN_LICENSE:LGPL$ |
|
10 ** No Commercial Usage |
|
11 ** This file contains pre-release code and may not be distributed. |
|
12 ** You may use this file in accordance with the terms and conditions |
|
13 ** contained in the Technology Preview License Agreement accompanying |
|
14 ** this package. |
|
15 ** |
|
16 ** GNU Lesser General Public License Usage |
|
17 ** Alternatively, this file may be used under the terms of the GNU Lesser |
|
18 ** General Public License version 2.1 as published by the Free Software |
|
19 ** Foundation and appearing in the file LICENSE.LGPL included in the |
|
20 ** packaging of this file. Please review the following information to |
|
21 ** ensure the GNU Lesser General Public License version 2.1 requirements |
|
22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
|
23 ** |
|
24 ** In addition, as a special exception, Nokia gives you certain additional |
|
25 ** rights. These rights are described in the Nokia Qt LGPL Exception |
|
26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
|
27 ** |
|
28 ** If you have questions regarding the use of this file, please contact |
|
29 ** Nokia at qt-info@nokia.com. |
|
30 ** |
|
31 ** |
|
32 ** |
|
33 ** |
|
34 ** |
|
35 ** |
|
36 ** |
|
37 ** |
|
38 ** $QT_END_LICENSE$ |
|
39 ** |
|
40 ****************************************************************************/ |
|
41 |
|
42 #include "q3polygonscanner.h" |
|
43 #include "q3pointarray.h" |
|
44 #include <stdlib.h> |
|
45 |
|
46 QT_BEGIN_NAMESPACE |
|
47 |
|
48 // Based on Xserver code miFillGeneralPoly... |
|
49 /* |
|
50 * |
|
51 * Written by Brian Kelleher; Oct. 1985 |
|
52 * |
|
53 * Routine to fill a polygon. Two fill rules are |
|
54 * supported: frWINDING and frEVENODD. |
|
55 * |
|
56 * See fillpoly.h for a complete description of the algorithm. |
|
57 */ |
|
58 |
|
59 /* |
|
60 * These are the data structures needed to scan |
|
61 * convert regions. Two different scan conversion |
|
62 * methods are available -- the even-odd method, and |
|
63 * the winding number method. |
|
64 * The even-odd rule states that a point is inside |
|
65 * the polygon if a ray drawn from that point in any |
|
66 * direction will pass through an odd number of |
|
67 * path segments. |
|
68 * By the winding number rule, a point is decided |
|
69 * to be inside the polygon if a ray drawn from that |
|
70 * point in any direction passes through a different |
|
71 * number of clockwise and counterclockwise path |
|
72 * segments. |
|
73 * |
|
74 * These data structures are adapted somewhat from |
|
75 * the algorithm in (Foley/Van Dam) for scan converting |
|
76 * polygons. |
|
77 * The basic algorithm is to start at the top (smallest y) |
|
78 * of the polygon, stepping down to the bottom of |
|
79 * the polygon by incrementing the y coordinate. We |
|
80 * keep a list of edges which the current scanline crosses, |
|
81 * sorted by x. This list is called the Active Edge Table (AET) |
|
82 * As we change the y-coordinate, we update each entry in |
|
83 * in the active edge table to reflect the edges new xcoord. |
|
84 * This list must be sorted at each scanline in case |
|
85 * two edges intersect. |
|
86 * We also keep a data structure known as the Edge Table (ET), |
|
87 * which keeps track of all the edges which the current |
|
88 * scanline has not yet reached. The ET is basically a |
|
89 * list of ScanLineList structures containing a list of |
|
90 * edges which are entered at a given scanline. There is one |
|
91 * ScanLineList per scanline at which an edge is entered. |
|
92 * When we enter a new edge, we move it from the ET to the AET. |
|
93 * |
|
94 * From the AET, we can implement the even-odd rule as in |
|
95 * (Foley/Van Dam). |
|
96 * The winding number rule is a little trickier. We also |
|
97 * keep the EdgeTableEntries in the AET linked by the |
|
98 * nextWETE (winding EdgeTableEntry) link. This allows |
|
99 * the edges to be linked just as before for updating |
|
100 * purposes, but only uses the edges linked by the nextWETE |
|
101 * link as edges representing spans of the polygon to |
|
102 * drawn (as with the even-odd rule). |
|
103 */ |
|
104 |
|
105 /* $XConsortium: miscanfill.h,v 1.5 94/04/17 20:27:50 dpw Exp $ */ |
|
106 /* |
|
107 |
|
108 Copyright (c) 1987 X Consortium |
|
109 |
|
110 Permission is hereby granted, free of charge, to any person obtaining |
|
111 a copy of this software and associated documentation files (the |
|
112 "Software"), to deal in the Software without restriction, including |
|
113 without limitation the rights to use, copy, modify, merge, publish, |
|
114 distribute, sublicense, and/or sell copies of the Software, and to |
|
115 permit persons to whom the Software is furnished to do so, subject to |
|
116 the following conditions: |
|
117 |
|
118 The above copyright notice and this permission notice shall be included |
|
119 in all copies or substantial portions of the Software. |
|
120 |
|
121 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |
|
122 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
|
123 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
|
124 IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR |
|
125 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
|
126 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
|
127 OTHER DEALINGS IN THE SOFTWARE. |
|
128 |
|
129 Except as contained in this notice, the name of the X Consortium shall |
|
130 not be used in advertising or otherwise to promote the sale, use or |
|
131 other dealings in this Software without prior written authorization |
|
132 from the X Consortium. |
|
133 |
|
134 */ |
|
135 |
|
136 |
|
137 /* |
|
138 * scanfill.h |
|
139 * |
|
140 * Written by Brian Kelleher; Jan 1985 |
|
141 * |
|
142 * This file contains a few macros to help track |
|
143 * the edge of a filled object. The object is assumed |
|
144 * to be filled in scanline order, and thus the |
|
145 * algorithm used is an extension of Bresenham's line |
|
146 * drawing algorithm which assumes that y is always the |
|
147 * major axis. |
|
148 * Since these pieces of code are the same for any filled shape, |
|
149 * it is more convenient to gather the library in one |
|
150 * place, but since these pieces of code are also in |
|
151 * the inner loops of output primitives, procedure call |
|
152 * overhead is out of the question. |
|
153 * See the author for a derivation if needed. |
|
154 */ |
|
155 |
|
156 /* |
|
157 * In scan converting polygons, we want to choose those pixels |
|
158 * which are inside the polygon. Thus, we add .5 to the starting |
|
159 * x coordinate for both left and right edges. Now we choose the |
|
160 * first pixel which is inside the pgon for the left edge and the |
|
161 * first pixel which is outside the pgon for the right edge. |
|
162 * Draw the left pixel, but not the right. |
|
163 * |
|
164 * How to add .5 to the starting x coordinate: |
|
165 * If the edge is moving to the right, then subtract dy from the |
|
166 * error term from the general form of the algorithm. |
|
167 * If the edge is moving to the left, then add dy to the error term. |
|
168 * |
|
169 * The reason for the difference between edges moving to the left |
|
170 * and edges moving to the right is simple: If an edge is moving |
|
171 * to the right, then we want the algorithm to flip immediately. |
|
172 * If it is moving to the left, then we don't want it to flip until |
|
173 * we traverse an entire pixel. |
|
174 */ |
|
175 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \ |
|
176 int dx; /* local storage */ \ |
|
177 \ |
|
178 /* \ |
|
179 * if the edge is horizontal, then it is ignored \ |
|
180 * and assumed not to be processed. Otherwise, do this stuff. \ |
|
181 */ \ |
|
182 if ((dy) != 0) { \ |
|
183 xStart = (x1); \ |
|
184 dx = (x2) - xStart; \ |
|
185 if (dx < 0) { \ |
|
186 m = dx / (dy); \ |
|
187 m1 = m - 1; \ |
|
188 incr1 = -2 * dx + 2 * (dy) * m1; \ |
|
189 incr2 = -2 * dx + 2 * (dy) * m; \ |
|
190 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \ |
|
191 } else { \ |
|
192 m = dx / (dy); \ |
|
193 m1 = m + 1; \ |
|
194 incr1 = 2 * dx - 2 * (dy) * m1; \ |
|
195 incr2 = 2 * dx - 2 * (dy) * m; \ |
|
196 d = -2 * m * (dy) + 2 * dx; \ |
|
197 } \ |
|
198 } \ |
|
199 } |
|
200 |
|
201 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \ |
|
202 if (m1 > 0) { \ |
|
203 if (d > 0) { \ |
|
204 minval += m1; \ |
|
205 d += incr1; \ |
|
206 } \ |
|
207 else { \ |
|
208 minval += m; \ |
|
209 d += incr2; \ |
|
210 } \ |
|
211 } else {\ |
|
212 if (d >= 0) { \ |
|
213 minval += m1; \ |
|
214 d += incr1; \ |
|
215 } \ |
|
216 else { \ |
|
217 minval += m; \ |
|
218 d += incr2; \ |
|
219 } \ |
|
220 } \ |
|
221 } |
|
222 |
|
223 |
|
224 /* |
|
225 * This structure contains all of the information needed |
|
226 * to run the bresenham algorithm. |
|
227 * The variables may be hardcoded into the declarations |
|
228 * instead of using this structure to make use of |
|
229 * register declarations. |
|
230 */ |
|
231 typedef struct { |
|
232 int minor; /* minor axis */ |
|
233 int d; /* decision variable */ |
|
234 int m, m1; /* slope and slope+1 */ |
|
235 int incr1, incr2; /* error increments */ |
|
236 } BRESINFO; |
|
237 |
|
238 |
|
239 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \ |
|
240 BRESINITPGON(dmaj, min1, min2, bres.minor, bres.d, \ |
|
241 bres.m, bres.m1, bres.incr1, bres.incr2) |
|
242 |
|
243 #define BRESINCRPGONSTRUCT(bres) \ |
|
244 BRESINCRPGON(bres.d, bres.minor, bres.m, bres.m1, bres.incr1, bres.incr2) |
|
245 |
|
246 |
|
247 typedef struct _EdgeTableEntry { |
|
248 int ymax; /* ycoord at which we exit this edge. */ |
|
249 BRESINFO bres; /* Bresenham info to run the edge */ |
|
250 struct _EdgeTableEntry *next; /* next in the list */ |
|
251 struct _EdgeTableEntry *back; /* for insertion sort */ |
|
252 struct _EdgeTableEntry *nextWETE; /* for winding num rule */ |
|
253 int ClockWise; /* flag for winding number rule */ |
|
254 } EdgeTableEntry; |
|
255 |
|
256 |
|
257 typedef struct _ScanLineList{ |
|
258 int scanline; /* the scanline represented */ |
|
259 EdgeTableEntry *edgelist; /* header node */ |
|
260 struct _ScanLineList *next; /* next in the list */ |
|
261 } ScanLineList; |
|
262 |
|
263 |
|
264 typedef struct { |
|
265 int ymax; /* ymax for the polygon */ |
|
266 int ymin; /* ymin for the polygon */ |
|
267 ScanLineList scanlines; /* header node */ |
|
268 } EdgeTable; |
|
269 |
|
270 |
|
271 /* |
|
272 * Here is a struct to help with storage allocation |
|
273 * so we can allocate a big chunk at a time, and then take |
|
274 * pieces from this heap when we need to. |
|
275 */ |
|
276 #define SLLSPERBLOCK 25 |
|
277 |
|
278 typedef struct _ScanLineListBlock { |
|
279 ScanLineList SLLs[SLLSPERBLOCK]; |
|
280 struct _ScanLineListBlock *next; |
|
281 } ScanLineListBlock; |
|
282 |
|
283 /* |
|
284 * number of points to buffer before sending them off |
|
285 * to scanlines() : Must be an even number |
|
286 */ |
|
287 #define NUMPTSTOBUFFER 200 |
|
288 |
|
289 /* |
|
290 * |
|
291 * a few macros for the inner loops of the fill code where |
|
292 * performance considerations don't allow a procedure call. |
|
293 * |
|
294 * Evaluate the given edge at the given scanline. |
|
295 * If the edge has expired, then we leave it and fix up |
|
296 * the active edge table; otherwise, we increment the |
|
297 * x value to be ready for the next scanline. |
|
298 * The winding number rule is in effect, so we must notify |
|
299 * the caller when the edge has been removed so he |
|
300 * can reorder the Winding Active Edge Table. |
|
301 */ |
|
302 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \ |
|
303 if (pAET->ymax == y) { /* leaving this edge */ \ |
|
304 pPrevAET->next = pAET->next; \ |
|
305 pAET = pPrevAET->next; \ |
|
306 fixWAET = 1; \ |
|
307 if (pAET) \ |
|
308 pAET->back = pPrevAET; \ |
|
309 } \ |
|
310 else { \ |
|
311 BRESINCRPGONSTRUCT(pAET->bres); \ |
|
312 pPrevAET = pAET; \ |
|
313 pAET = pAET->next; \ |
|
314 } \ |
|
315 } |
|
316 |
|
317 |
|
318 /* |
|
319 * Evaluate the given edge at the given scanline. |
|
320 * If the edge has expired, then we leave it and fix up |
|
321 * the active edge table; otherwise, we increment the |
|
322 * x value to be ready for the next scanline. |
|
323 * The even-odd rule is in effect. |
|
324 */ |
|
325 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \ |
|
326 if (pAET->ymax == y) { /* leaving this edge */ \ |
|
327 pPrevAET->next = pAET->next; \ |
|
328 pAET = pPrevAET->next; \ |
|
329 if (pAET) \ |
|
330 pAET->back = pPrevAET; \ |
|
331 } \ |
|
332 else { \ |
|
333 BRESINCRPGONSTRUCT(pAET->bres) \ |
|
334 pPrevAET = pAET; \ |
|
335 pAET = pAET->next; \ |
|
336 } \ |
|
337 } |
|
338 |
|
339 /*********************************************************** |
|
340 |
|
341 Copyright (c) 1987 X Consortium |
|
342 |
|
343 Permission is hereby granted, free of charge, to any person obtaining a copy |
|
344 of this software and associated documentation files (the "Software"), to deal |
|
345 in the Software without restriction, including without limitation the rights |
|
346 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
|
347 copies of the Software, and to permit persons to whom the Software is |
|
348 furnished to do so, subject to the following conditions: |
|
349 |
|
350 The above copyright notice and this permission notice shall be included in |
|
351 all copies or substantial portions of the Software. |
|
352 |
|
353 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
|
354 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
|
355 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
|
356 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN |
|
357 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
|
358 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
|
359 |
|
360 Except as contained in this notice, the name of the X Consortium shall not be |
|
361 used in advertising or otherwise to promote the sale, use or other dealings |
|
362 in this Software without prior written authorization from the X Consortium. |
|
363 |
|
364 |
|
365 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. |
|
366 |
|
367 All Rights Reserved |
|
368 |
|
369 Permission to use, copy, modify, and distribute this software and its |
|
370 documentation for any purpose and without fee is hereby granted, |
|
371 provided that the above copyright notice appear in all copies and that |
|
372 both that copyright notice and this permission notice appear in |
|
373 supporting documentation, and that the name of Digital not be |
|
374 used in advertising or publicity pertaining to distribution of the |
|
375 software without specific, written prior permission. |
|
376 |
|
377 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING |
|
378 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL |
|
379 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR |
|
380 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
|
381 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
|
382 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
|
383 SOFTWARE. |
|
384 |
|
385 ******************************************************************/ |
|
386 |
|
387 #define MAXINT 0x7fffffff |
|
388 #define MININT -MAXINT |
|
389 |
|
390 /* |
|
391 * fillUtils.c |
|
392 * |
|
393 * Written by Brian Kelleher; Oct. 1985 |
|
394 * |
|
395 * This module contains all of the utility functions |
|
396 * needed to scan convert a polygon. |
|
397 * |
|
398 */ |
|
399 /* |
|
400 * InsertEdgeInET |
|
401 * |
|
402 * Insert the given edge into the edge table. |
|
403 * First we must find the correct bucket in the |
|
404 * Edge table, then find the right slot in the |
|
405 * bucket. Finally, we can insert it. |
|
406 * |
|
407 */ |
|
408 static bool |
|
409 miInsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, |
|
410 int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock) |
|
411 { |
|
412 register EdgeTableEntry *start, *prev; |
|
413 register ScanLineList *pSLL, *pPrevSLL; |
|
414 ScanLineListBlock *tmpSLLBlock; |
|
415 |
|
416 /* |
|
417 * find the right bucket to put the edge into |
|
418 */ |
|
419 pPrevSLL = &ET->scanlines; |
|
420 pSLL = pPrevSLL->next; |
|
421 while (pSLL && (pSLL->scanline < scanline)) |
|
422 { |
|
423 pPrevSLL = pSLL; |
|
424 pSLL = pSLL->next; |
|
425 } |
|
426 |
|
427 /* |
|
428 * reassign pSLL (pointer to ScanLineList) if necessary |
|
429 */ |
|
430 if ((!pSLL) || (pSLL->scanline > scanline)) |
|
431 { |
|
432 if (*iSLLBlock > SLLSPERBLOCK-1) |
|
433 { |
|
434 tmpSLLBlock = |
|
435 (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock)); |
|
436 if (!tmpSLLBlock) |
|
437 return false; |
|
438 (*SLLBlock)->next = tmpSLLBlock; |
|
439 tmpSLLBlock->next = 0; |
|
440 *SLLBlock = tmpSLLBlock; |
|
441 *iSLLBlock = 0; |
|
442 } |
|
443 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); |
|
444 |
|
445 pSLL->next = pPrevSLL->next; |
|
446 pSLL->edgelist = 0; |
|
447 pPrevSLL->next = pSLL; |
|
448 } |
|
449 pSLL->scanline = scanline; |
|
450 |
|
451 /* |
|
452 * now insert the edge in the right bucket |
|
453 */ |
|
454 prev = 0; |
|
455 start = pSLL->edgelist; |
|
456 while (start && (start->bres.minor < ETE->bres.minor)) |
|
457 { |
|
458 prev = start; |
|
459 start = start->next; |
|
460 } |
|
461 ETE->next = start; |
|
462 |
|
463 if (prev) |
|
464 prev->next = ETE; |
|
465 else |
|
466 pSLL->edgelist = ETE; |
|
467 return true; |
|
468 } |
|
469 |
|
470 /* |
|
471 * CreateEdgeTable |
|
472 * |
|
473 * This routine creates the edge table for |
|
474 * scan converting polygons. |
|
475 * The Edge Table (ET) looks like: |
|
476 * |
|
477 * EdgeTable |
|
478 * -------- |
|
479 * | ymax | ScanLineLists |
|
480 * |scanline|-->------------>-------------->... |
|
481 * -------- |scanline| |scanline| |
|
482 * |edgelist| |edgelist| |
|
483 * --------- --------- |
|
484 * | | |
|
485 * | | |
|
486 * V V |
|
487 * list of ETEs list of ETEs |
|
488 * |
|
489 * where ETE is an EdgeTableEntry data structure, |
|
490 * and there is one ScanLineList per scanline at |
|
491 * which an edge is initially entered. |
|
492 * |
|
493 */ |
|
494 |
|
495 typedef struct { |
|
496 #if defined(Q_OS_MAC) |
|
497 int y, x; |
|
498 #else |
|
499 int x, y; |
|
500 #endif |
|
501 |
|
502 } DDXPointRec, *DDXPointPtr; |
|
503 |
|
504 /* |
|
505 * Clean up our act. |
|
506 */ |
|
507 static void |
|
508 miFreeStorage(ScanLineListBlock *pSLLBlock) |
|
509 { |
|
510 register ScanLineListBlock *tmpSLLBlock; |
|
511 |
|
512 while (pSLLBlock) |
|
513 { |
|
514 tmpSLLBlock = pSLLBlock->next; |
|
515 free(pSLLBlock); |
|
516 pSLLBlock = tmpSLLBlock; |
|
517 } |
|
518 } |
|
519 |
|
520 static bool |
|
521 miCreateETandAET(int count, DDXPointPtr pts, EdgeTable *ET, |
|
522 EdgeTableEntry *AET, EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock) |
|
523 { |
|
524 register DDXPointPtr top, bottom; |
|
525 register DDXPointPtr PrevPt, CurrPt; |
|
526 int iSLLBlock = 0; |
|
527 |
|
528 int dy; |
|
529 |
|
530 if (count < 2) return true; |
|
531 |
|
532 /* |
|
533 * initialize the Active Edge Table |
|
534 */ |
|
535 AET->next = 0; |
|
536 AET->back = 0; |
|
537 AET->nextWETE = 0; |
|
538 AET->bres.minor = MININT; |
|
539 |
|
540 /* |
|
541 * initialize the Edge Table. |
|
542 */ |
|
543 ET->scanlines.next = 0; |
|
544 ET->ymax = MININT; |
|
545 ET->ymin = MAXINT; |
|
546 pSLLBlock->next = 0; |
|
547 |
|
548 PrevPt = &pts[count-1]; |
|
549 |
|
550 /* |
|
551 * for each vertex in the array of points. |
|
552 * In this loop we are dealing with two vertices at |
|
553 * a time -- these make up one edge of the polygon. |
|
554 */ |
|
555 while (count--) |
|
556 { |
|
557 CurrPt = pts++; |
|
558 |
|
559 /* |
|
560 * find out which point is above and which is below. |
|
561 */ |
|
562 if (PrevPt->y > CurrPt->y) |
|
563 { |
|
564 bottom = PrevPt, top = CurrPt; |
|
565 pETEs->ClockWise = 0; |
|
566 } |
|
567 else |
|
568 { |
|
569 bottom = CurrPt, top = PrevPt; |
|
570 pETEs->ClockWise = 1; |
|
571 } |
|
572 |
|
573 /* |
|
574 * don't add horizontal edges to the Edge table. |
|
575 */ |
|
576 if (bottom->y != top->y) |
|
577 { |
|
578 pETEs->ymax = bottom->y-1; /* -1 so we don't get last scanline */ |
|
579 |
|
580 /* |
|
581 * initialize integer edge algorithm |
|
582 */ |
|
583 dy = bottom->y - top->y; |
|
584 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres) |
|
585 |
|
586 if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) |
|
587 { |
|
588 miFreeStorage(pSLLBlock->next); |
|
589 return false; |
|
590 } |
|
591 |
|
592 ET->ymax = qMax(ET->ymax, PrevPt->y); |
|
593 ET->ymin = qMin(ET->ymin, PrevPt->y); |
|
594 pETEs++; |
|
595 } |
|
596 |
|
597 PrevPt = CurrPt; |
|
598 } |
|
599 return true; |
|
600 } |
|
601 |
|
602 /* |
|
603 * loadAET |
|
604 * |
|
605 * This routine moves EdgeTableEntries from the |
|
606 * EdgeTable into the Active Edge Table, |
|
607 * leaving them sorted by smaller x coordinate. |
|
608 * |
|
609 */ |
|
610 |
|
611 static void |
|
612 miloadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs) |
|
613 { |
|
614 register EdgeTableEntry *pPrevAET; |
|
615 register EdgeTableEntry *tmp; |
|
616 |
|
617 pPrevAET = AET; |
|
618 AET = AET->next; |
|
619 while (ETEs) |
|
620 { |
|
621 while (AET && (AET->bres.minor < ETEs->bres.minor)) |
|
622 { |
|
623 pPrevAET = AET; |
|
624 AET = AET->next; |
|
625 } |
|
626 tmp = ETEs->next; |
|
627 ETEs->next = AET; |
|
628 if (AET) |
|
629 AET->back = ETEs; |
|
630 ETEs->back = pPrevAET; |
|
631 pPrevAET->next = ETEs; |
|
632 pPrevAET = ETEs; |
|
633 |
|
634 ETEs = tmp; |
|
635 } |
|
636 } |
|
637 |
|
638 /* |
|
639 * computeWAET |
|
640 * |
|
641 * This routine links the AET by the |
|
642 * nextWETE (winding EdgeTableEntry) link for |
|
643 * use by the winding number rule. The final |
|
644 * Active Edge Table (AET) might look something |
|
645 * like: |
|
646 * |
|
647 * AET |
|
648 * ---------- --------- --------- |
|
649 * |ymax | |ymax | |ymax | |
|
650 * | ... | |... | |... | |
|
651 * |next |->|next |->|next |->... |
|
652 * |nextWETE| |nextWETE| |nextWETE| |
|
653 * --------- --------- ^-------- |
|
654 * | | | |
|
655 * V-------------------> V---> ... |
|
656 * |
|
657 */ |
|
658 static void |
|
659 micomputeWAET(EdgeTableEntry *AET) |
|
660 { |
|
661 register EdgeTableEntry *pWETE; |
|
662 register int inside = 1; |
|
663 register int isInside = 0; |
|
664 |
|
665 AET->nextWETE = 0; |
|
666 pWETE = AET; |
|
667 AET = AET->next; |
|
668 while (AET) |
|
669 { |
|
670 if (AET->ClockWise) |
|
671 isInside++; |
|
672 else |
|
673 isInside--; |
|
674 |
|
675 if ((!inside && !isInside) || |
|
676 (inside && isInside)) |
|
677 { |
|
678 pWETE->nextWETE = AET; |
|
679 pWETE = AET; |
|
680 inside = !inside; |
|
681 } |
|
682 AET = AET->next; |
|
683 } |
|
684 pWETE->nextWETE = 0; |
|
685 } |
|
686 |
|
687 /* |
|
688 * InsertionSort |
|
689 * |
|
690 * Just a simple insertion sort using |
|
691 * pointers and back pointers to sort the Active |
|
692 * Edge Table. |
|
693 * |
|
694 */ |
|
695 |
|
696 static int |
|
697 miInsertionSort(EdgeTableEntry *AET) |
|
698 { |
|
699 register EdgeTableEntry *pETEchase; |
|
700 register EdgeTableEntry *pETEinsert; |
|
701 register EdgeTableEntry *pETEchaseBackTMP; |
|
702 register int changed = 0; |
|
703 |
|
704 AET = AET->next; |
|
705 while (AET) |
|
706 { |
|
707 pETEinsert = AET; |
|
708 pETEchase = AET; |
|
709 while (pETEchase->back->bres.minor > AET->bres.minor) |
|
710 pETEchase = pETEchase->back; |
|
711 |
|
712 AET = AET->next; |
|
713 if (pETEchase != pETEinsert) |
|
714 { |
|
715 pETEchaseBackTMP = pETEchase->back; |
|
716 pETEinsert->back->next = AET; |
|
717 if (AET) |
|
718 AET->back = pETEinsert->back; |
|
719 pETEinsert->next = pETEchase; |
|
720 pETEchase->back->next = pETEinsert; |
|
721 pETEchase->back = pETEinsert; |
|
722 pETEinsert->back = pETEchaseBackTMP; |
|
723 changed = 1; |
|
724 } |
|
725 } |
|
726 return changed; |
|
727 } |
|
728 |
|
729 /*! |
|
730 \overload |
|
731 */ |
|
732 void Q3PolygonScanner::scan(const Q3PointArray& pa, bool winding, int index, int npoints) |
|
733 { |
|
734 scan(pa, winding, index, npoints, true); |
|
735 } |
|
736 |
|
737 /*! |
|
738 \overload |
|
739 |
|
740 If \a stitchable is false, the right and bottom edges of the |
|
741 polygon are included. This causes adjacent polygons to overlap. |
|
742 */ |
|
743 void Q3PolygonScanner::scan(const Q3PointArray& pa, bool winding, int index, int npoints, bool stitchable) |
|
744 { |
|
745 scan(pa, winding, index, npoints, |
|
746 stitchable ? Edge(Left+Top) : Edge(Left+Right+Top+Bottom)); |
|
747 } |
|
748 |
|
749 /*! |
|
750 Calls processSpans() for all scanlines of the polygon defined by |
|
751 \a npoints starting at \a index in \a pa. |
|
752 |
|
753 If \a winding is true, the Winding algorithm rather than the |
|
754 Odd-Even rule is used. |
|
755 |
|
756 The \a edges is any bitwise combination of: |
|
757 \list |
|
758 \i Q3PolygonScanner::Left |
|
759 \i Q3PolygonScanner::Right |
|
760 \i Q3PolygonScanner::Top |
|
761 \i Q3PolygonScanner::Bottom |
|
762 \endlist |
|
763 \a edges determines which edges are included. |
|
764 |
|
765 \warning The edges feature does not work properly. |
|
766 |
|
767 */ |
|
768 void Q3PolygonScanner::scan(const Q3PointArray& pa, bool winding, int index, int npoints, Edge edges) |
|
769 { |
|
770 |
|
771 |
|
772 DDXPointPtr ptsIn = (DDXPointPtr)pa.data(); |
|
773 ptsIn += index; |
|
774 register EdgeTableEntry *pAET; /* the Active Edge Table */ |
|
775 register int y; /* the current scanline */ |
|
776 register int nPts = 0; /* number of pts in buffer */ |
|
777 register EdgeTableEntry *pWETE; /* Winding Edge Table */ |
|
778 register ScanLineList *pSLL; /* Current ScanLineList */ |
|
779 register DDXPointPtr ptsOut; /* ptr to output buffers */ |
|
780 int *width; |
|
781 DDXPointRec FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */ |
|
782 int FirstWidth[NUMPTSTOBUFFER]; |
|
783 EdgeTableEntry *pPrevAET; /* previous AET entry */ |
|
784 EdgeTable ET; /* Edge Table header node */ |
|
785 EdgeTableEntry AET; /* Active ET header node */ |
|
786 EdgeTableEntry *pETEs; /* Edge Table Entries buff */ |
|
787 ScanLineListBlock SLLBlock; /* header for ScanLineList */ |
|
788 int fixWAET = 0; |
|
789 int edge_l = (edges & Left) ? 1 : 0; |
|
790 int edge_r = (edges & Right) ? 1 : 0; |
|
791 int edge_t = 1; //#### (edges & Top) ? 1 : 0; |
|
792 int edge_b = (edges & Bottom) ? 1 : 0; |
|
793 |
|
794 if (npoints == -1) |
|
795 npoints = pa.size(); |
|
796 |
|
797 if (npoints < 3) |
|
798 return; |
|
799 |
|
800 if(!(pETEs = (EdgeTableEntry *) |
|
801 malloc(sizeof(EdgeTableEntry) * npoints))) |
|
802 return; |
|
803 ptsOut = FirstPoint; |
|
804 width = FirstWidth; |
|
805 if (!miCreateETandAET(npoints, ptsIn, &ET, &AET, pETEs, &SLLBlock)) |
|
806 { |
|
807 free(pETEs); |
|
808 return; |
|
809 } |
|
810 pSLL = ET.scanlines.next; |
|
811 |
|
812 if (!winding) |
|
813 { |
|
814 /* |
|
815 * for each scanline |
|
816 */ |
|
817 for (y = ET.ymin+1-edge_t; y < ET.ymax+edge_b; y++) |
|
818 { |
|
819 /* |
|
820 * Add a new edge to the active edge table when we |
|
821 * get to the next edge. |
|
822 */ |
|
823 if (pSLL && y == pSLL->scanline) |
|
824 { |
|
825 miloadAET(&AET, pSLL->edgelist); |
|
826 pSLL = pSLL->next; |
|
827 } |
|
828 pPrevAET = &AET; |
|
829 pAET = AET.next; |
|
830 |
|
831 /* |
|
832 * for each active edge |
|
833 */ |
|
834 while (pAET) |
|
835 { |
|
836 ptsOut->x = pAET->bres.minor + 1 - edge_l; |
|
837 ptsOut++->y = y; |
|
838 *width++ = pAET->next->bres.minor - pAET->bres.minor |
|
839 - 1 + edge_l + edge_r; |
|
840 nPts++; |
|
841 |
|
842 /* |
|
843 * send out the buffer when its full |
|
844 */ |
|
845 if (nPts == NUMPTSTOBUFFER) |
|
846 { |
|
847 processSpans(nPts, (QPoint*)FirstPoint, FirstWidth); |
|
848 ptsOut = FirstPoint; |
|
849 width = FirstWidth; |
|
850 nPts = 0; |
|
851 } |
|
852 EVALUATEEDGEEVENODD(pAET, pPrevAET, y) |
|
853 EVALUATEEDGEEVENODD(pAET, pPrevAET, y) |
|
854 } |
|
855 miInsertionSort(&AET); |
|
856 } |
|
857 } |
|
858 else /* default to WindingNumber */ |
|
859 { |
|
860 /* |
|
861 * for each scanline |
|
862 */ |
|
863 for (y = ET.ymin+1-edge_t; y < ET.ymax+edge_b; y++) |
|
864 { |
|
865 /* |
|
866 * Add a new edge to the active edge table when we |
|
867 * get to the next edge. |
|
868 */ |
|
869 if (pSLL && y == pSLL->scanline) |
|
870 { |
|
871 miloadAET(&AET, pSLL->edgelist); |
|
872 micomputeWAET(&AET); |
|
873 pSLL = pSLL->next; |
|
874 } |
|
875 pPrevAET = &AET; |
|
876 pAET = AET.next; |
|
877 pWETE = pAET; |
|
878 |
|
879 /* |
|
880 * for each active edge |
|
881 */ |
|
882 while (pAET) |
|
883 { |
|
884 /* |
|
885 * if the next edge in the active edge table is |
|
886 * also the next edge in the winding active edge |
|
887 * table. |
|
888 */ |
|
889 if (pWETE == pAET) |
|
890 { |
|
891 ptsOut->x = pAET->bres.minor + 1 - edge_l; |
|
892 ptsOut++->y = y; |
|
893 *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor - 1 + edge_l + edge_r; |
|
894 nPts++; |
|
895 |
|
896 /* |
|
897 * send out the buffer |
|
898 */ |
|
899 if (nPts == NUMPTSTOBUFFER) |
|
900 { |
|
901 processSpans(nPts, (QPoint*)FirstPoint, FirstWidth); |
|
902 ptsOut = FirstPoint; |
|
903 width = FirstWidth; |
|
904 nPts = 0; |
|
905 } |
|
906 |
|
907 pWETE = pWETE->nextWETE; |
|
908 while (pWETE != pAET) { |
|
909 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) |
|
910 } |
|
911 pWETE = pWETE->nextWETE; |
|
912 } |
|
913 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) |
|
914 } |
|
915 |
|
916 /* |
|
917 * reevaluate the Winding active edge table if we |
|
918 * just had to resort it or if we just exited an edge. |
|
919 */ |
|
920 if (miInsertionSort(&AET) || fixWAET) |
|
921 { |
|
922 micomputeWAET(&AET); |
|
923 fixWAET = 0; |
|
924 } |
|
925 } |
|
926 } |
|
927 |
|
928 /* |
|
929 * Get any spans that we missed by buffering |
|
930 */ |
|
931 |
|
932 |
|
933 processSpans(nPts, (QPoint*)FirstPoint, FirstWidth); |
|
934 free(pETEs); |
|
935 miFreeStorage(SLLBlock.next); |
|
936 } |
|
937 /***** END OF X11-based CODE *****/ |
|
938 |
|
939 QT_END_NAMESPACE |