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 /*
47 * mipoly.c
48 *
49 * Written by Brian Kelleher; June 1986
50 */
51 #ifdef HAVE_DIX_CONFIG_H
52 #include <dix-config.h>
53 #endif
54
55 #include <X11/X.h>
56 #include "windowstr.h"
57 #include "gcstruct.h"
58 #include "pixmapstr.h"
59 #include "mi.h"
60 #include "miscanfill.h"
61 #include "mipoly.h"
62 #include "regionstr.h"
63
64 /*
65 * Insert the given edge into the edge table. First we must find the correct
66 * bucket in the Edge table, then find the right slot in the bucket. Finally,
67 * we can insert it.
68 */
69 static Bool
miInsertEdgeInET(EdgeTable * ET,EdgeTableEntry * ETE,int scanline,ScanLineListBlock ** SLLBlock,int * iSLLBlock)70 miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline,
71 ScanLineListBlock ** SLLBlock, int *iSLLBlock)
72 {
73 EdgeTableEntry *start, *prev;
74 ScanLineList *pSLL, *pPrevSLL;
75 ScanLineListBlock *tmpSLLBlock;
76
77 /*
78 * find the right bucket to put the edge into
79 */
80 pPrevSLL = &ET->scanlines;
81 pSLL = pPrevSLL->next;
82 while (pSLL && (pSLL->scanline < scanline)) {
83 pPrevSLL = pSLL;
84 pSLL = pSLL->next;
85 }
86
87 /*
88 * reassign pSLL (pointer to ScanLineList) if necessary
89 */
90 if ((!pSLL) || (pSLL->scanline > scanline)) {
91 if (*iSLLBlock > SLLSPERBLOCK - 1) {
92 tmpSLLBlock = malloc(sizeof(ScanLineListBlock));
93 if (!tmpSLLBlock)
94 return FALSE;
95 (*SLLBlock)->next = tmpSLLBlock;
96 tmpSLLBlock->next = NULL;
97 *SLLBlock = tmpSLLBlock;
98 *iSLLBlock = 0;
99 }
100 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
101
102 pSLL->next = pPrevSLL->next;
103 pSLL->edgelist = NULL;
104 pPrevSLL->next = pSLL;
105 }
106 pSLL->scanline = scanline;
107
108 /*
109 * now insert the edge in the right bucket
110 */
111 prev = NULL;
112 start = pSLL->edgelist;
113 while (start && (start->bres.minor < ETE->bres.minor)) {
114 prev = start;
115 start = start->next;
116 }
117 ETE->next = start;
118
119 if (prev)
120 prev->next = ETE;
121 else
122 pSLL->edgelist = ETE;
123 return TRUE;
124 }
125
126 static void
miFreeStorage(ScanLineListBlock * pSLLBlock)127 miFreeStorage(ScanLineListBlock * pSLLBlock)
128 {
129 ScanLineListBlock *tmpSLLBlock;
130
131 while (pSLLBlock) {
132 tmpSLLBlock = pSLLBlock->next;
133 free(pSLLBlock);
134 pSLLBlock = tmpSLLBlock;
135 }
136 }
137
138 /*
139 * CreateEdgeTable
140 *
141 * This routine creates the edge table for scan converting polygons.
142 * The Edge Table (ET) looks like:
143 *
144 * EdgeTable
145 * --------
146 * | ymax | ScanLineLists
147 * |scanline|-->------------>-------------->...
148 * -------- |scanline| |scanline|
149 * |edgelist| |edgelist|
150 * --------- ---------
151 * | |
152 * | |
153 * V V
154 * list of ETEs list of ETEs
155 *
156 * where ETE is an EdgeTableEntry data structure, and there is one ScanLineList
157 * per scanline at which an edge is initially entered.
158 */
159
160 static Bool
miCreateETandAET(int count,DDXPointPtr pts,EdgeTable * ET,EdgeTableEntry * AET,EdgeTableEntry * pETEs,ScanLineListBlock * pSLLBlock)161 miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET,
162 EdgeTableEntry * AET, EdgeTableEntry * pETEs,
163 ScanLineListBlock * pSLLBlock)
164 {
165 DDXPointPtr top, bottom;
166 DDXPointPtr PrevPt, CurrPt;
167 int iSLLBlock = 0;
168
169 int dy;
170
171 if (count < 2)
172 return TRUE;
173
174 /*
175 * initialize the Active Edge Table
176 */
177 AET->next = NULL;
178 AET->back = NULL;
179 AET->nextWETE = NULL;
180 AET->bres.minor = MININT;
181
182 /*
183 * initialize the Edge Table.
184 */
185 ET->scanlines.next = NULL;
186 ET->ymax = MININT;
187 ET->ymin = MAXINT;
188 pSLLBlock->next = NULL;
189
190 PrevPt = &pts[count - 1];
191
192 /*
193 * for each vertex in the array of points.
194 * In this loop we are dealing with two vertices at
195 * a time -- these make up one edge of the polygon.
196 */
197 while (count--) {
198 CurrPt = pts++;
199
200 /*
201 * find out which point is above and which is below.
202 */
203 if (PrevPt->y > CurrPt->y) {
204 bottom = PrevPt, top = CurrPt;
205 pETEs->ClockWise = 0;
206 }
207 else {
208 bottom = CurrPt, top = PrevPt;
209 pETEs->ClockWise = 1;
210 }
211
212 /*
213 * don't add horizontal edges to the Edge table.
214 */
215 if (bottom->y != top->y) {
216 pETEs->ymax = bottom->y - 1; /* -1 so we don't get last scanline */
217
218 /*
219 * initialize integer edge algorithm
220 */
221 dy = bottom->y - top->y;
222 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
223
224 if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) {
225 miFreeStorage(pSLLBlock->next);
226 return FALSE;
227 }
228
229 ET->ymax = max(ET->ymax, PrevPt->y);
230 ET->ymin = min(ET->ymin, PrevPt->y);
231 pETEs++;
232 }
233
234 PrevPt = CurrPt;
235 }
236 return TRUE;
237 }
238
239 /*
240 * This routine moves EdgeTableEntries from the EdgeTable into the Active Edge
241 * Table, leaving them sorted by smaller x coordinate.
242 */
243
244 static void
miloadAET(EdgeTableEntry * AET,EdgeTableEntry * ETEs)245 miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs)
246 {
247 EdgeTableEntry *pPrevAET;
248 EdgeTableEntry *tmp;
249
250 pPrevAET = AET;
251 AET = AET->next;
252 while (ETEs) {
253 while (AET && (AET->bres.minor < ETEs->bres.minor)) {
254 pPrevAET = AET;
255 AET = AET->next;
256 }
257 tmp = ETEs->next;
258 ETEs->next = AET;
259 if (AET)
260 AET->back = ETEs;
261 ETEs->back = pPrevAET;
262 pPrevAET->next = ETEs;
263 pPrevAET = ETEs;
264
265 ETEs = tmp;
266 }
267 }
268
269 /*
270 * computeWAET
271 *
272 * This routine links the AET by the nextWETE (winding EdgeTableEntry) link for
273 * use by the winding number rule. The final Active Edge Table (AET) might
274 * look something like:
275 *
276 * AET
277 * ---------- --------- ---------
278 * |ymax | |ymax | |ymax |
279 * | ... | |... | |... |
280 * |next |->|next |->|next |->...
281 * |nextWETE| |nextWETE| |nextWETE|
282 * --------- --------- ^--------
283 * | | |
284 * V-------------------> V---> ...
285 *
286 */
287 static void
micomputeWAET(EdgeTableEntry * AET)288 micomputeWAET(EdgeTableEntry * AET)
289 {
290 EdgeTableEntry *pWETE;
291 int inside = 1;
292 int isInside = 0;
293
294 AET->nextWETE = NULL;
295 pWETE = AET;
296 AET = AET->next;
297 while (AET) {
298 if (AET->ClockWise)
299 isInside++;
300 else
301 isInside--;
302
303 if ((!inside && !isInside) || (inside && isInside)) {
304 pWETE->nextWETE = AET;
305 pWETE = AET;
306 inside = !inside;
307 }
308 AET = AET->next;
309 }
310 pWETE->nextWETE = NULL;
311 }
312
313 /*
314 * Just a simple insertion sort using pointers and back pointers to sort the
315 * Active Edge Table.
316 */
317
318 static int
miInsertionSort(EdgeTableEntry * AET)319 miInsertionSort(EdgeTableEntry * AET)
320 {
321 EdgeTableEntry *pETEchase;
322 EdgeTableEntry *pETEinsert;
323 EdgeTableEntry *pETEchaseBackTMP;
324 int changed = 0;
325
326 AET = AET->next;
327 while (AET) {
328 pETEinsert = AET;
329 pETEchase = AET;
330 while (pETEchase->back->bres.minor > AET->bres.minor)
331 pETEchase = pETEchase->back;
332
333 AET = AET->next;
334 if (pETEchase != pETEinsert) {
335 pETEchaseBackTMP = pETEchase->back;
336 pETEinsert->back->next = AET;
337 if (AET)
338 AET->back = pETEinsert->back;
339 pETEinsert->next = pETEchase;
340 pETEchase->back->next = pETEinsert;
341 pETEchase->back = pETEinsert;
342 pETEinsert->back = pETEchaseBackTMP;
343 changed = 1;
344 }
345 }
346 return changed;
347 }
348
349 /* Find the index of the point with the smallest y */
350 static int
getPolyYBounds(DDXPointPtr pts,int n,int * by,int * ty)351 getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty)
352 {
353 DDXPointPtr ptMin;
354 int ymin, ymax;
355 DDXPointPtr ptsStart = pts;
356
357 ptMin = pts;
358 ymin = ymax = (pts++)->y;
359
360 while (--n > 0) {
361 if (pts->y < ymin) {
362 ptMin = pts;
363 ymin = pts->y;
364 }
365 if (pts->y > ymax)
366 ymax = pts->y;
367
368 pts++;
369 }
370
371 *by = ymin;
372 *ty = ymax;
373 return ptMin - ptsStart;
374 }
375
376 /*
377 * Written by Brian Kelleher; Dec. 1985.
378 *
379 * Fill a convex polygon. If the given polygon is not convex, then the result
380 * is undefined. The algorithm is to order the edges from smallest y to
381 * largest by partitioning the array into a left edge list and a right edge
382 * list. The algorithm used to traverse each edge is an extension of
383 * Bresenham's line algorithm with y as the major axis. For a derivation of
384 * the algorithm, see the author of this code.
385 */
386 static Bool
miFillConvexPoly(DrawablePtr dst,GCPtr pgc,int count,DDXPointPtr ptsIn)387 miFillConvexPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn)
388 {
389 int xl = 0, xr = 0; /* x vals of left and right edges */
390 int dl = 0, dr = 0; /* decision variables */
391 int ml = 0, m1l = 0; /* left edge slope and slope+1 */
392 int mr = 0, m1r = 0; /* right edge slope and slope+1 */
393 int incr1l = 0, incr2l = 0; /* left edge error increments */
394 int incr1r = 0, incr2r = 0; /* right edge error increments */
395 int dy; /* delta y */
396 int y; /* current scanline */
397 int left, right; /* indices to first endpoints */
398 int i; /* loop counter */
399 int nextleft, nextright; /* indices to second endpoints */
400 DDXPointPtr ptsOut, FirstPoint; /* output buffer */
401 int *width, *FirstWidth; /* output buffer */
402 int imin; /* index of smallest vertex (in y) */
403 int ymin; /* y-extents of polygon */
404 int ymax;
405
406 /*
407 * find leftx, bottomy, rightx, topy, and the index
408 * of bottomy. Also translate the points.
409 */
410 imin = getPolyYBounds(ptsIn, count, &ymin, &ymax);
411
412 dy = ymax - ymin + 1;
413 if ((count < 3) || (dy < 0))
414 return TRUE;
415 ptsOut = FirstPoint = xallocarray(dy, sizeof(DDXPointRec));
416 width = FirstWidth = xallocarray(dy, sizeof(int));
417 if (!FirstPoint || !FirstWidth) {
418 free(FirstWidth);
419 free(FirstPoint);
420 return FALSE;
421 }
422
423 nextleft = nextright = imin;
424 y = ptsIn[nextleft].y;
425
426 /*
427 * loop through all edges of the polygon
428 */
429 do {
430 /*
431 * add a left edge if we need to
432 */
433 if (ptsIn[nextleft].y == y) {
434 left = nextleft;
435
436 /*
437 * find the next edge, considering the end
438 * conditions of the array.
439 */
440 nextleft++;
441 if (nextleft >= count)
442 nextleft = 0;
443
444 /*
445 * now compute all of the random information
446 * needed to run the iterative algorithm.
447 */
448 BRESINITPGON(ptsIn[nextleft].y - ptsIn[left].y,
449 ptsIn[left].x, ptsIn[nextleft].x,
450 xl, dl, ml, m1l, incr1l, incr2l);
451 }
452
453 /*
454 * add a right edge if we need to
455 */
456 if (ptsIn[nextright].y == y) {
457 right = nextright;
458
459 /*
460 * find the next edge, considering the end
461 * conditions of the array.
462 */
463 nextright--;
464 if (nextright < 0)
465 nextright = count - 1;
466
467 /*
468 * now compute all of the random information
469 * needed to run the iterative algorithm.
470 */
471 BRESINITPGON(ptsIn[nextright].y - ptsIn[right].y,
472 ptsIn[right].x, ptsIn[nextright].x,
473 xr, dr, mr, m1r, incr1r, incr2r);
474 }
475
476 /*
477 * generate scans to fill while we still have
478 * a right edge as well as a left edge.
479 */
480 i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y;
481 /* in case we're called with non-convex polygon */
482 if (i < 0) {
483 free(FirstWidth);
484 free(FirstPoint);
485 return TRUE;
486 }
487 while (i-- > 0) {
488 ptsOut->y = y;
489
490 /*
491 * reverse the edges if necessary
492 */
493 if (xl < xr) {
494 *(width++) = xr - xl;
495 (ptsOut++)->x = xl;
496 }
497 else {
498 *(width++) = xl - xr;
499 (ptsOut++)->x = xr;
500 }
501 y++;
502
503 /* increment down the edges */
504 BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l);
505 BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r);
506 }
507 } while (y != ymax);
508
509 /*
510 * Finally, fill the <remaining> spans
511 */
512 (*pgc->ops->FillSpans) (dst, pgc,
513 ptsOut - FirstPoint, FirstPoint, FirstWidth, 1);
514 free(FirstWidth);
515 free(FirstPoint);
516 return TRUE;
517 }
518
519 /*
520 * Written by Brian Kelleher; Oct. 1985
521 *
522 * Routine to fill a polygon. Two fill rules are supported: frWINDING and
523 * frEVENODD.
524 */
525 static Bool
miFillGeneralPoly(DrawablePtr dst,GCPtr pgc,int count,DDXPointPtr ptsIn)526 miFillGeneralPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn)
527 {
528 EdgeTableEntry *pAET; /* the Active Edge Table */
529 int y; /* the current scanline */
530 int nPts = 0; /* number of pts in buffer */
531 EdgeTableEntry *pWETE; /* Winding Edge Table */
532 ScanLineList *pSLL; /* Current ScanLineList */
533 DDXPointPtr ptsOut; /* ptr to output buffers */
534 int *width;
535 DDXPointRec FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */
536 int FirstWidth[NUMPTSTOBUFFER];
537 EdgeTableEntry *pPrevAET; /* previous AET entry */
538 EdgeTable ET; /* Edge Table header node */
539 EdgeTableEntry AET; /* Active ET header node */
540 EdgeTableEntry *pETEs; /* Edge Table Entries buff */
541 ScanLineListBlock SLLBlock; /* header for ScanLineList */
542 int fixWAET = 0;
543
544 if (count < 3)
545 return TRUE;
546
547 if (!(pETEs = malloc(sizeof(EdgeTableEntry) * count)))
548 return FALSE;
549 ptsOut = FirstPoint;
550 width = FirstWidth;
551 if (!miCreateETandAET(count, ptsIn, &ET, &AET, pETEs, &SLLBlock)) {
552 free(pETEs);
553 return FALSE;
554 }
555 pSLL = ET.scanlines.next;
556
557 if (pgc->fillRule == EvenOddRule) {
558 /*
559 * for each scanline
560 */
561 for (y = ET.ymin; y < ET.ymax; y++) {
562 /*
563 * Add a new edge to the active edge table when we
564 * get to the next edge.
565 */
566 if (pSLL && y == pSLL->scanline) {
567 miloadAET(&AET, pSLL->edgelist);
568 pSLL = pSLL->next;
569 }
570 pPrevAET = &AET;
571 pAET = AET.next;
572
573 /*
574 * for each active edge
575 */
576 while (pAET) {
577 ptsOut->x = pAET->bres.minor;
578 ptsOut++->y = y;
579 *width++ = pAET->next->bres.minor - pAET->bres.minor;
580 nPts++;
581
582 /*
583 * send out the buffer when its full
584 */
585 if (nPts == NUMPTSTOBUFFER) {
586 (*pgc->ops->FillSpans) (dst, pgc,
587 nPts, FirstPoint, FirstWidth, 1);
588 ptsOut = FirstPoint;
589 width = FirstWidth;
590 nPts = 0;
591 }
592 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
593 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
594 }
595 miInsertionSort(&AET);
596 }
597 }
598 else { /* default to WindingNumber */
599
600 /*
601 * for each scanline
602 */
603 for (y = ET.ymin; y < ET.ymax; y++) {
604 /*
605 * Add a new edge to the active edge table when we
606 * get to the next edge.
607 */
608 if (pSLL && y == pSLL->scanline) {
609 miloadAET(&AET, pSLL->edgelist);
610 micomputeWAET(&AET);
611 pSLL = pSLL->next;
612 }
613 pPrevAET = &AET;
614 pAET = AET.next;
615 pWETE = pAET;
616
617 /*
618 * for each active edge
619 */
620 while (pAET) {
621 /*
622 * if the next edge in the active edge table is
623 * also the next edge in the winding active edge
624 * table.
625 */
626 if (pWETE == pAET) {
627 ptsOut->x = pAET->bres.minor;
628 ptsOut++->y = y;
629 *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor;
630 nPts++;
631
632 /*
633 * send out the buffer
634 */
635 if (nPts == NUMPTSTOBUFFER) {
636 (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint,
637 FirstWidth, 1);
638 ptsOut = FirstPoint;
639 width = FirstWidth;
640 nPts = 0;
641 }
642
643 pWETE = pWETE->nextWETE;
644 while (pWETE != pAET)
645 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
646 pWETE = pWETE->nextWETE;
647 }
648 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
649 }
650
651 /*
652 * reevaluate the Winding active edge table if we
653 * just had to resort it or if we just exited an edge.
654 */
655 if (miInsertionSort(&AET) || fixWAET) {
656 micomputeWAET(&AET);
657 fixWAET = 0;
658 }
659 }
660 }
661
662 /*
663 * Get any spans that we missed by buffering
664 */
665 (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, FirstWidth, 1);
666 free(pETEs);
667 miFreeStorage(SLLBlock.next);
668 return TRUE;
669 }
670
671 /*
672 * Draw polygons. This routine translates the point by the origin if
673 * pGC->miTranslate is non-zero, and calls to the appropriate routine to
674 * actually scan convert the polygon.
675 */
676 void
miFillPolygon(DrawablePtr dst,GCPtr pgc,int shape,int mode,int count,DDXPointPtr pPts)677 miFillPolygon(DrawablePtr dst, GCPtr pgc,
678 int shape, int mode, int count, DDXPointPtr pPts)
679 {
680 int i;
681 int xorg, yorg;
682 DDXPointPtr ppt;
683
684 if (count == 0)
685 return;
686
687 ppt = pPts;
688 if (pgc->miTranslate) {
689 xorg = dst->x;
690 yorg = dst->y;
691
692 if (mode == CoordModeOrigin) {
693 for (i = 0; i < count; i++) {
694 ppt->x += xorg;
695 ppt++->y += yorg;
696 }
697 }
698 else {
699 ppt->x += xorg;
700 ppt++->y += yorg;
701 for (i = 1; i < count; i++) {
702 ppt->x += (ppt - 1)->x;
703 ppt->y += (ppt - 1)->y;
704 ppt++;
705 }
706 }
707 }
708 else {
709 if (mode == CoordModePrevious) {
710 ppt++;
711 for (i = 1; i < count; i++) {
712 ppt->x += (ppt - 1)->x;
713 ppt->y += (ppt - 1)->y;
714 ppt++;
715 }
716 }
717 }
718 if (shape == Convex)
719 miFillConvexPoly(dst, pgc, count, pPts);
720 else
721 miFillGeneralPoly(dst, pgc, count, pPts);
722 }
723