mipoly.c (21321B)
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 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 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 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 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 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 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 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 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 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 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 }