Mercurial > ecos

comparison packages/services/gfx/mw/current/src/engine/devrgn2.c @ 208:e0c0827131d1 ecos

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