1/* 2 3Copyright 1988, 1998 The Open Group 4 5Permission to use, copy, modify, distribute, and sell this software and its 6documentation for any purpose is hereby granted without fee, provided that 7the above copyright notice appear in all copies and that both that 8copyright notice and this permission notice appear in supporting 9documentation. 10 11The above copyright notice and this permission notice shall be included 12in all copies or substantial portions of the Software. 13 14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 15OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 16MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 17IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR 18OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 19ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 20OTHER DEALINGS IN THE SOFTWARE. 21 22Except as contained in this notice, the name of The Open Group shall 23not be used in advertising or otherwise to promote the sale, use or 24other dealings in this Software without prior written authorization 25from The Open Group. 26 27*/ 28 29/* Author: Keith Packard, MIT X Consortium */ 30 31/* 32 * Mostly integer wideline code. Uses a technique similar to 33 * bresenham zero-width lines, except walks an X edge 34 */ 35 36#ifdef HAVE_DIX_CONFIG_H 37#include <dix-config.h> 38#endif 39 40#include <stdio.h> 41#ifdef _XOPEN_SOURCE 42#include <math.h> 43#else 44#define _XOPEN_SOURCE /* to get prototype for hypot on some systems */ 45#include <math.h> 46#undef _XOPEN_SOURCE 47#endif 48#include <X11/X.h> 49#include "windowstr.h" 50#include "gcstruct.h" 51#include "regionstr.h" 52#include "miwideline.h" 53#include "mi.h" 54 55static Bool 56InitSpans(Spans *spans, size_t nspans) 57{ 58 spans->points = malloc(nspans * sizeof (*spans->points)); 59 if (!spans->points) 60 return FALSE; 61 spans->widths = malloc(nspans * sizeof (*spans->widths)); 62 if (!spans->widths) 63 { 64 free(spans->points); 65 return FALSE; 66 } 67 return TRUE; 68} 69 70/* 71 * interface data to span-merging polygon filler 72 */ 73 74typedef struct _SpanData { 75 SpanGroup fgGroup, bgGroup; 76} SpanDataRec, *SpanDataPtr; 77 78static void 79AppendSpanGroup(GCPtr pGC, unsigned long pixel, Spans *spanPtr, SpanDataPtr spanData) 80{ 81 SpanGroup *group, *othergroup = NULL; 82 if (pixel == pGC->fgPixel) 83 { 84 group = &spanData->fgGroup; 85 if (pGC->lineStyle == LineDoubleDash) 86 othergroup = &spanData->bgGroup; 87 } 88 else 89 { 90 group = &spanData->bgGroup; 91 othergroup = &spanData->fgGroup; 92 } 93 miAppendSpans (group, othergroup, spanPtr); 94} 95 96 97static void miLineArc(DrawablePtr pDraw, GCPtr pGC, 98 unsigned long pixel, SpanDataPtr spanData, 99 LineFacePtr leftFace, 100 LineFacePtr rightFace, 101 double xorg, double yorg, Bool isInt); 102 103 104/* 105 * spans-based polygon filler 106 */ 107 108static void 109fillSpans(DrawablePtr pDrawable, GCPtr pGC, unsigned long pixel, Spans *spans, SpanDataPtr spanData) 110{ 111 if (!spanData) 112 { 113 ChangeGCVal oldPixel, tmpPixel; 114 oldPixel.val = pGC->fgPixel; 115 if (pixel != oldPixel.val) 116 { 117 tmpPixel.val = (XID)pixel; 118 ChangeGC (NullClient, pGC, GCForeground, &tmpPixel); 119 ValidateGC (pDrawable, pGC); 120 } 121 (*pGC->ops->FillSpans) (pDrawable, pGC, spans->count, spans->points, spans->widths, TRUE); 122 free(spans->widths); 123 free(spans->points); 124 if (pixel != oldPixel.val) 125 { 126 ChangeGC (NullClient, pGC, GCForeground, &oldPixel); 127 ValidateGC (pDrawable, pGC); 128 } 129 } 130 else 131 AppendSpanGroup (pGC, pixel, spans, spanData); 132} 133 134static void 135miFillPolyHelper (DrawablePtr pDrawable, GCPtr pGC, unsigned long pixel, 136 SpanDataPtr spanData, int y, int overall_height, 137 PolyEdgePtr left, PolyEdgePtr right, 138 int left_count, int right_count) 139{ 140 int left_x = 0, left_e = 0; 141 int left_stepx = 0; 142 int left_signdx = 0; 143 int left_dy = 0, left_dx = 0; 144 145 int right_x = 0, right_e = 0; 146 int right_stepx = 0; 147 int right_signdx = 0; 148 int right_dy = 0, right_dx = 0; 149 150 int height = 0; 151 int left_height = 0, right_height = 0; 152 153 DDXPointPtr ppt; 154 int *pwidth; 155 int xorg; 156 Spans spanRec; 157 158 if (!InitSpans(&spanRec, overall_height)) 159 return; 160 ppt = spanRec.points; 161 pwidth = spanRec.widths; 162 163 xorg = 0; 164 if (pGC->miTranslate) 165 { 166 y += pDrawable->y; 167 xorg = pDrawable->x; 168 } 169 while ((left_count || left_height) && 170 (right_count || right_height)) 171 { 172 if (!left_height && left_count) 173 { 174 left_height = left->height; 175 left_x = left->x; 176 left_stepx = left->stepx; 177 left_signdx = left->signdx; 178 left_e = left->e; 179 left_dy = left->dy; 180 left_dx = left->dx; 181 --left_count; 182 ++left; 183 } 184 185 if (!right_height && right_count) 186 { 187 right_height = right->height; 188 right_x = right->x; 189 right_stepx = right->stepx; 190 right_signdx = right->signdx; 191 right_e = right->e; 192 right_dy = right->dy; 193 right_dx = right->dx; 194 --right_count; 195 ++right; 196 } 197 198 height = left_height; 199 if (height > right_height) 200 height = right_height; 201 202 left_height -= height; 203 right_height -= height; 204 205 while (--height >= 0) 206 { 207 if (right_x >= left_x) 208 { 209 ppt->y = y; 210 ppt->x = left_x + xorg; 211 ppt++; 212 *pwidth++ = right_x - left_x + 1; 213 } 214 y++; 215 216 left_x += left_stepx; 217 left_e += left_dx; 218 if (left_e > 0) 219 { 220 left_x += left_signdx; 221 left_e -= left_dy; 222 } 223 224 right_x += right_stepx; 225 right_e += right_dx; 226 if (right_e > 0) 227 { 228 right_x += right_signdx; 229 right_e -= right_dy; 230 } 231 } 232 } 233 spanRec.count = ppt - spanRec.points; 234 fillSpans (pDrawable, pGC, pixel, &spanRec, spanData); 235} 236 237static void 238miFillRectPolyHelper ( 239 DrawablePtr pDrawable, 240 GCPtr pGC, 241 unsigned long pixel, 242 SpanDataPtr spanData, 243 int x, 244 int y, 245 int w, 246 int h) 247{ 248 DDXPointPtr ppt; 249 int *pwidth; 250 ChangeGCVal oldPixel, tmpPixel; 251 Spans spanRec; 252 xRectangle rect; 253 254 if (!spanData) 255 { 256 rect.x = x; 257 rect.y = y; 258 rect.width = w; 259 rect.height = h; 260 oldPixel.val = pGC->fgPixel; 261 if (pixel != oldPixel.val) 262 { 263 tmpPixel.val = (XID)pixel; 264 ChangeGC (NullClient, pGC, GCForeground, &tmpPixel); 265 ValidateGC (pDrawable, pGC); 266 } 267 (*pGC->ops->PolyFillRect) (pDrawable, pGC, 1, &rect); 268 if (pixel != oldPixel.val) 269 { 270 ChangeGC (NullClient, pGC, GCForeground, &oldPixel); 271 ValidateGC (pDrawable, pGC); 272 } 273 } 274 else 275 { 276 if (!InitSpans(&spanRec, h)) 277 return; 278 ppt = spanRec.points; 279 pwidth = spanRec.widths; 280 281 if (pGC->miTranslate) 282 { 283 y += pDrawable->y; 284 x += pDrawable->x; 285 } 286 while (h--) 287 { 288 ppt->x = x; 289 ppt->y = y; 290 ppt++; 291 *pwidth++ = w; 292 y++; 293 } 294 spanRec.count = ppt - spanRec.points; 295 AppendSpanGroup (pGC, pixel, &spanRec, spanData); 296 } 297} 298 299/* static */ int 300miPolyBuildEdge ( 301 double x0, 302 double y0, 303 double k, /* x0 * dy - y0 * dx */ 304 int dx, 305 int dy, 306 int xi, 307 int yi, 308 int left, 309 PolyEdgePtr edge) 310{ 311 int x, y, e; 312 int xady; 313 314 if (dy < 0) 315 { 316 dy = -dy; 317 dx = -dx; 318 k = -k; 319 } 320 321#ifdef NOTDEF 322 { 323 double realk, kerror; 324 realk = x0 * dy - y0 * dx; 325 kerror = Fabs (realk - k); 326 if (kerror > .1) 327 printf ("realk: %g k: %g\n", realk, k); 328 } 329#endif 330 y = ICEIL (y0); 331 xady = ICEIL (k) + y * dx; 332 333 if (xady <= 0) 334 x = - (-xady / dy) - 1; 335 else 336 x = (xady - 1) / dy; 337 338 e = xady - x * dy; 339 340 if (dx >= 0) 341 { 342 edge->signdx = 1; 343 edge->stepx = dx / dy; 344 edge->dx = dx % dy; 345 } 346 else 347 { 348 edge->signdx = -1; 349 edge->stepx = - (-dx / dy); 350 edge->dx = -dx % dy; 351 e = dy - e + 1; 352 } 353 edge->dy = dy; 354 edge->x = x + left + xi; 355 edge->e = e - dy; /* bias to compare against 0 instead of dy */ 356 return y + yi; 357} 358 359#define StepAround(v, incr, max) (((v) + (incr) < 0) ? (max - 1) : ((v) + (incr) == max) ? 0 : ((v) + (incr))) 360 361/* static */ int 362miPolyBuildPoly ( 363 PolyVertexPtr vertices, 364 PolySlopePtr slopes, 365 int count, 366 int xi, 367 int yi, 368 PolyEdgePtr left, 369 PolyEdgePtr right, 370 int *pnleft, 371 int *pnright, 372 int *h) 373{ 374 int top, bottom; 375 double miny, maxy; 376 int i; 377 int j; 378 int clockwise; 379 int slopeoff; 380 int s; 381 int nright, nleft; 382 int y, lasty = 0, bottomy, topy = 0; 383 384 /* find the top of the polygon */ 385 maxy = miny = vertices[0].y; 386 bottom = top = 0; 387 for (i = 1; i < count; i++) 388 { 389 if (vertices[i].y < miny) 390 { 391 top = i; 392 miny = vertices[i].y; 393 } 394 if (vertices[i].y >= maxy) 395 { 396 bottom = i; 397 maxy = vertices[i].y; 398 } 399 } 400 clockwise = 1; 401 slopeoff = 0; 402 403 i = top; 404 j = StepAround (top, -1, count); 405 406 if ((int64_t)slopes[j].dy * slopes[i].dx > (int64_t)slopes[i].dy * slopes[j].dx) 407 { 408 clockwise = -1; 409 slopeoff = -1; 410 } 411 412 bottomy = ICEIL (maxy) + yi; 413 414 nright = 0; 415 416 s = StepAround (top, slopeoff, count); 417 i = top; 418 while (i != bottom) 419 { 420 if (slopes[s].dy != 0) 421 { 422 y = miPolyBuildEdge (vertices[i].x, vertices[i].y, 423 slopes[s].k, 424 slopes[s].dx, slopes[s].dy, 425 xi, yi, 0, 426 &right[nright]); 427 if (nright != 0) 428 right[nright-1].height = y - lasty; 429 else 430 topy = y; 431 nright++; 432 lasty = y; 433 } 434 435 i = StepAround (i, clockwise, count); 436 s = StepAround (s, clockwise, count); 437 } 438 if (nright != 0) 439 right[nright-1].height = bottomy - lasty; 440 441 if (slopeoff == 0) 442 slopeoff = -1; 443 else 444 slopeoff = 0; 445 446 nleft = 0; 447 s = StepAround (top, slopeoff, count); 448 i = top; 449 while (i != bottom) 450 { 451 if (slopes[s].dy != 0) 452 { 453 y = miPolyBuildEdge (vertices[i].x, vertices[i].y, 454 slopes[s].k, 455 slopes[s].dx, slopes[s].dy, xi, yi, 1, 456 &left[nleft]); 457 458 if (nleft != 0) 459 left[nleft-1].height = y - lasty; 460 nleft++; 461 lasty = y; 462 } 463 i = StepAround (i, -clockwise, count); 464 s = StepAround (s, -clockwise, count); 465 } 466 if (nleft != 0) 467 left[nleft-1].height = bottomy - lasty; 468 *pnleft = nleft; 469 *pnright = nright; 470 *h = bottomy - topy; 471 return topy; 472} 473 474static void 475miLineOnePoint ( 476 DrawablePtr pDrawable, 477 GCPtr pGC, 478 unsigned long pixel, 479 SpanDataPtr spanData, 480 int x, 481 int y) 482{ 483 DDXPointRec pt; 484 int wid; 485 unsigned long oldPixel; 486 487 MILINESETPIXEL (pDrawable, pGC, pixel, oldPixel); 488 if (pGC->fillStyle == FillSolid) 489 { 490 pt.x = x; 491 pt.y = y; 492 (*pGC->ops->PolyPoint) (pDrawable, pGC, CoordModeOrigin, 1, &pt); 493 } 494 else 495 { 496 wid = 1; 497 if (pGC->miTranslate) 498 { 499 x += pDrawable->x; 500 y += pDrawable->y; 501 } 502 pt.x = x; 503 pt.y = y; 504 (*pGC->ops->FillSpans) (pDrawable, pGC, 1, &pt, &wid, TRUE); 505 } 506 MILINERESETPIXEL (pDrawable, pGC, pixel, oldPixel); 507} 508 509static void 510miLineJoin ( 511 DrawablePtr pDrawable, 512 GCPtr pGC, 513 unsigned long pixel, 514 SpanDataPtr spanData, 515 LineFacePtr pLeft, 516 LineFacePtr pRight) 517{ 518 double mx = 0, my = 0; 519 double denom = 0.0; 520 PolyVertexRec vertices[4]; 521 PolySlopeRec slopes[4]; 522 int edgecount; 523 PolyEdgeRec left[4], right[4]; 524 int nleft, nright; 525 int y, height; 526 int swapslopes; 527 int joinStyle = pGC->joinStyle; 528 int lw = pGC->lineWidth; 529 530 if (lw == 1 && !spanData) { 531 /* See if one of the lines will draw the joining pixel */ 532 if (pLeft->dx > 0 || (pLeft->dx == 0 && pLeft->dy > 0)) 533 return; 534 if (pRight->dx > 0 || (pRight->dx == 0 && pRight->dy > 0)) 535 return; 536 if (joinStyle != JoinRound) { 537 denom = - pLeft->dx * (double)pRight->dy + pRight->dx * (double)pLeft->dy; 538 if (denom == 0) 539 return; /* no join to draw */ 540 } 541 if (joinStyle != JoinMiter) { 542 miLineOnePoint (pDrawable, pGC, pixel, spanData, pLeft->x, pLeft->y); 543 return; 544 } 545 } else { 546 if (joinStyle == JoinRound) 547 { 548 miLineArc(pDrawable, pGC, pixel, spanData, 549 pLeft, pRight, 550 (double)0.0, (double)0.0, TRUE); 551 return; 552 } 553 denom = - pLeft->dx * (double)pRight->dy + pRight->dx * (double)pLeft->dy; 554 if (denom == 0.0) 555 return; /* no join to draw */ 556 } 557 558 swapslopes = 0; 559 if (denom > 0) 560 { 561 pLeft->xa = -pLeft->xa; 562 pLeft->ya = -pLeft->ya; 563 pLeft->dx = -pLeft->dx; 564 pLeft->dy = -pLeft->dy; 565 } 566 else 567 { 568 swapslopes = 1; 569 pRight->xa = -pRight->xa; 570 pRight->ya = -pRight->ya; 571 pRight->dx = -pRight->dx; 572 pRight->dy = -pRight->dy; 573 } 574 575 vertices[0].x = pRight->xa; 576 vertices[0].y = pRight->ya; 577 slopes[0].dx = -pRight->dy; 578 slopes[0].dy = pRight->dx; 579 slopes[0].k = 0; 580 581 vertices[1].x = 0; 582 vertices[1].y = 0; 583 slopes[1].dx = pLeft->dy; 584 slopes[1].dy = -pLeft->dx; 585 slopes[1].k = 0; 586 587 vertices[2].x = pLeft->xa; 588 vertices[2].y = pLeft->ya; 589 590 if (joinStyle == JoinMiter) 591 { 592 my = (pLeft->dy * (pRight->xa * pRight->dy - pRight->ya * pRight->dx) - 593 pRight->dy * (pLeft->xa * pLeft->dy - pLeft->ya * pLeft->dx )) / 594 denom; 595 if (pLeft->dy != 0) 596 { 597 mx = pLeft->xa + (my - pLeft->ya) * 598 (double) pLeft->dx / (double) pLeft->dy; 599 } 600 else 601 { 602 mx = pRight->xa + (my - pRight->ya) * 603 (double) pRight->dx / (double) pRight->dy; 604 } 605 /* check miter limit */ 606 if ((mx * mx + my * my) * 4 > SQSECANT * lw * lw) 607 joinStyle = JoinBevel; 608 } 609 610 if (joinStyle == JoinMiter) 611 { 612 slopes[2].dx = pLeft->dx; 613 slopes[2].dy = pLeft->dy; 614 slopes[2].k = pLeft->k; 615 if (swapslopes) 616 { 617 slopes[2].dx = -slopes[2].dx; 618 slopes[2].dy = -slopes[2].dy; 619 slopes[2].k = -slopes[2].k; 620 } 621 vertices[3].x = mx; 622 vertices[3].y = my; 623 slopes[3].dx = pRight->dx; 624 slopes[3].dy = pRight->dy; 625 slopes[3].k = pRight->k; 626 if (swapslopes) 627 { 628 slopes[3].dx = -slopes[3].dx; 629 slopes[3].dy = -slopes[3].dy; 630 slopes[3].k = -slopes[3].k; 631 } 632 edgecount = 4; 633 } 634 else 635 { 636 double scale, dx, dy, adx, ady; 637 638 adx = dx = pRight->xa - pLeft->xa; 639 ady = dy = pRight->ya - pLeft->ya; 640 if (adx < 0) 641 adx = -adx; 642 if (ady < 0) 643 ady = -ady; 644 scale = ady; 645 if (adx > ady) 646 scale = adx; 647 slopes[2].dx = (dx * 65536) / scale; 648 slopes[2].dy = (dy * 65536) / scale; 649 slopes[2].k = ((pLeft->xa + pRight->xa) * slopes[2].dy - 650 (pLeft->ya + pRight->ya) * slopes[2].dx) / 2.0; 651 edgecount = 3; 652 } 653 654 y = miPolyBuildPoly (vertices, slopes, edgecount, pLeft->x, pLeft->y, 655 left, right, &nleft, &nright, &height); 656 miFillPolyHelper (pDrawable, pGC, pixel, spanData, y, height, left, right, nleft, nright); 657} 658 659static int 660miLineArcI ( 661 DrawablePtr pDraw, 662 GCPtr pGC, 663 int xorg, 664 int yorg, 665 DDXPointPtr points, 666 int *widths) 667{ 668 DDXPointPtr tpts, bpts; 669 int *twids, *bwids; 670 int x, y, e, ex, slw; 671 672 tpts = points; 673 twids = widths; 674 if (pGC->miTranslate) 675 { 676 xorg += pDraw->x; 677 yorg += pDraw->y; 678 } 679 slw = pGC->lineWidth; 680 if (slw == 1) 681 { 682 tpts->x = xorg; 683 tpts->y = yorg; 684 *twids = 1; 685 return 1; 686 } 687 bpts = tpts + slw; 688 bwids = twids + slw; 689 y = (slw >> 1) + 1; 690 if (slw & 1) 691 e = - ((y << 2) + 3); 692 else 693 e = - (y << 3); 694 ex = -4; 695 x = 0; 696 while (y) 697 { 698 e += (y << 3) - 4; 699 while (e >= 0) 700 { 701 x++; 702 e += (ex = -((x << 3) + 4)); 703 } 704 y--; 705 slw = (x << 1) + 1; 706 if ((e == ex) && (slw > 1)) 707 slw--; 708 tpts->x = xorg - x; 709 tpts->y = yorg - y; 710 tpts++; 711 *twids++ = slw; 712 if ((y != 0) && ((slw > 1) || (e != ex))) 713 { 714 bpts--; 715 bpts->x = xorg - x; 716 bpts->y = yorg + y; 717 *--bwids = slw; 718 } 719 } 720 return pGC->lineWidth; 721} 722 723#define CLIPSTEPEDGE(edgey,edge,edgeleft) \ 724 if (ybase == edgey) \ 725 { \ 726 if (edgeleft) \ 727 { \ 728 if (edge->x > xcl) \ 729 xcl = edge->x; \ 730 } \ 731 else \ 732 { \ 733 if (edge->x < xcr) \ 734 xcr = edge->x; \ 735 } \ 736 edgey++; \ 737 edge->x += edge->stepx; \ 738 edge->e += edge->dx; \ 739 if (edge->e > 0) \ 740 { \ 741 edge->x += edge->signdx; \ 742 edge->e -= edge->dy; \ 743 } \ 744 } 745 746static int 747miLineArcD ( 748 DrawablePtr pDraw, 749 GCPtr pGC, 750 double xorg, 751 double yorg, 752 DDXPointPtr points, 753 int *widths, 754 PolyEdgePtr edge1, 755 int edgey1, 756 Bool edgeleft1, 757 PolyEdgePtr edge2, 758 int edgey2, 759 Bool edgeleft2) 760{ 761 DDXPointPtr pts; 762 int *wids; 763 double radius, x0, y0, el, er, yk, xlk, xrk, k; 764 int xbase, ybase, y, boty, xl, xr, xcl, xcr; 765 int ymin, ymax; 766 Bool edge1IsMin, edge2IsMin; 767 int ymin1, ymin2; 768 769 pts = points; 770 wids = widths; 771 xbase = floor(xorg); 772 x0 = xorg - xbase; 773 ybase = ICEIL (yorg); 774 y0 = yorg - ybase; 775 if (pGC->miTranslate) 776 { 777 xbase += pDraw->x; 778 ybase += pDraw->y; 779 edge1->x += pDraw->x; 780 edge2->x += pDraw->x; 781 edgey1 += pDraw->y; 782 edgey2 += pDraw->y; 783 } 784 xlk = x0 + x0 + 1.0; 785 xrk = x0 + x0 - 1.0; 786 yk = y0 + y0 - 1.0; 787 radius = ((double)pGC->lineWidth) / 2.0; 788 y = floor(radius - y0 + 1.0); 789 ybase -= y; 790 ymin = ybase; 791 ymax = 65536; 792 edge1IsMin = FALSE; 793 ymin1 = edgey1; 794 if (edge1->dy >= 0) 795 { 796 if (!edge1->dy) 797 { 798 if (edgeleft1) 799 edge1IsMin = TRUE; 800 else 801 ymax = edgey1; 802 edgey1 = 65536; 803 } 804 else 805 { 806 if ((edge1->signdx < 0) == edgeleft1) 807 edge1IsMin = TRUE; 808 } 809 } 810 edge2IsMin = FALSE; 811 ymin2 = edgey2; 812 if (edge2->dy >= 0) 813 { 814 if (!edge2->dy) 815 { 816 if (edgeleft2) 817 edge2IsMin = TRUE; 818 else 819 ymax = edgey2; 820 edgey2 = 65536; 821 } 822 else 823 { 824 if ((edge2->signdx < 0) == edgeleft2) 825 edge2IsMin = TRUE; 826 } 827 } 828 if (edge1IsMin) 829 { 830 ymin = ymin1; 831 if (edge2IsMin && ymin1 > ymin2) 832 ymin = ymin2; 833 } else if (edge2IsMin) 834 ymin = ymin2; 835 el = radius * radius - ((y + y0) * (y + y0)) - (x0 * x0); 836 er = el + xrk; 837 xl = 1; 838 xr = 0; 839 if (x0 < 0.5) 840 { 841 xl = 0; 842 el -= xlk; 843 } 844 boty = (y0 < -0.5) ? 1 : 0; 845 if (ybase + y - boty > ymax) 846 boty = ymax - ybase - y; 847 while (y > boty) 848 { 849 k = (y << 1) + yk; 850 er += k; 851 while (er > 0.0) 852 { 853 xr++; 854 er += xrk - (xr << 1); 855 } 856 el += k; 857 while (el >= 0.0) 858 { 859 xl--; 860 el += (xl << 1) - xlk; 861 } 862 y--; 863 ybase++; 864 if (ybase < ymin) 865 continue; 866 xcl = xl + xbase; 867 xcr = xr + xbase; 868 CLIPSTEPEDGE(edgey1, edge1, edgeleft1); 869 CLIPSTEPEDGE(edgey2, edge2, edgeleft2); 870 if (xcr >= xcl) 871 { 872 pts->x = xcl; 873 pts->y = ybase; 874 pts++; 875 *wids++ = xcr - xcl + 1; 876 } 877 } 878 er = xrk - (xr << 1) - er; 879 el = (xl << 1) - xlk - el; 880 boty = floor(-y0 - radius + 1.0); 881 if (ybase + y - boty > ymax) 882 boty = ymax - ybase - y; 883 while (y > boty) 884 { 885 k = (y << 1) + yk; 886 er -= k; 887 while ((er >= 0.0) && (xr >= 0)) 888 { 889 xr--; 890 er += xrk - (xr << 1); 891 } 892 el -= k; 893 while ((el > 0.0) && (xl <= 0)) 894 { 895 xl++; 896 el += (xl << 1) - xlk; 897 } 898 y--; 899 ybase++; 900 if (ybase < ymin) 901 continue; 902 xcl = xl + xbase; 903 xcr = xr + xbase; 904 CLIPSTEPEDGE(edgey1, edge1, edgeleft1); 905 CLIPSTEPEDGE(edgey2, edge2, edgeleft2); 906 if (xcr >= xcl) 907 { 908 pts->x = xcl; 909 pts->y = ybase; 910 pts++; 911 *wids++ = xcr - xcl + 1; 912 } 913 } 914 return pts - points; 915} 916 917static int 918miRoundJoinFace (LineFacePtr face, PolyEdgePtr edge, Bool *leftEdge) 919{ 920 int y; 921 int dx, dy; 922 double xa, ya; 923 Bool left; 924 925 dx = -face->dy; 926 dy = face->dx; 927 xa = face->xa; 928 ya = face->ya; 929 left = 1; 930 if (ya > 0) 931 { 932 ya = 0.0; 933 xa = 0.0; 934 } 935 if (dy < 0 || (dy == 0 && dx > 0)) 936 { 937 dx = -dx; 938 dy = -dy; 939 left = !left; 940 } 941 if (dx == 0 && dy == 0) 942 dy = 1; 943 if (dy == 0) 944 { 945 y = ICEIL (face->ya) + face->y; 946 edge->x = -32767; 947 edge->stepx = 0; 948 edge->signdx = 0; 949 edge->e = -1; 950 edge->dy = 0; 951 edge->dx = 0; 952 edge->height = 0; 953 } 954 else 955 { 956 y = miPolyBuildEdge (xa, ya, 0.0, dx, dy, face->x, face->y, !left, edge); 957 edge->height = 32767; 958 } 959 *leftEdge = !left; 960 return y; 961} 962 963void 964miRoundJoinClip (LineFacePtr pLeft, LineFacePtr pRight, 965 PolyEdgePtr edge1, PolyEdgePtr edge2, 966 int *y1, int *y2, Bool *left1, Bool *left2) 967{ 968 double denom; 969 970 denom = - pLeft->dx * (double)pRight->dy + pRight->dx * (double)pLeft->dy; 971 972 if (denom >= 0) 973 { 974 pLeft->xa = -pLeft->xa; 975 pLeft->ya = -pLeft->ya; 976 } 977 else 978 { 979 pRight->xa = -pRight->xa; 980 pRight->ya = -pRight->ya; 981 } 982 *y1 = miRoundJoinFace (pLeft, edge1, left1); 983 *y2 = miRoundJoinFace (pRight, edge2, left2); 984} 985 986int 987miRoundCapClip (LineFacePtr face, Bool isInt, PolyEdgePtr edge, Bool *leftEdge) 988{ 989 int y; 990 int dx, dy; 991 double xa, ya, k; 992 Bool left; 993 994 dx = -face->dy; 995 dy = face->dx; 996 xa = face->xa; 997 ya = face->ya; 998 k = 0.0; 999 if (!isInt) 1000 k = face->k; 1001 left = 1; 1002 if (dy < 0 || (dy == 0 && dx > 0)) 1003 { 1004 dx = -dx; 1005 dy = -dy; 1006 xa = -xa; 1007 ya = -ya; 1008 left = !left; 1009 } 1010 if (dx == 0 && dy == 0) 1011 dy = 1; 1012 if (dy == 0) 1013 { 1014 y = ICEIL (face->ya) + face->y; 1015 edge->x = -32767; 1016 edge->stepx = 0; 1017 edge->signdx = 0; 1018 edge->e = -1; 1019 edge->dy = 0; 1020 edge->dx = 0; 1021 edge->height = 0; 1022 } 1023 else 1024 { 1025 y = miPolyBuildEdge (xa, ya, k, dx, dy, face->x, face->y, !left, edge); 1026 edge->height = 32767; 1027 } 1028 *leftEdge = !left; 1029 return y; 1030} 1031 1032static void 1033miLineArc ( 1034 DrawablePtr pDraw, 1035 GCPtr pGC, 1036 unsigned long pixel, 1037 SpanDataPtr spanData, 1038 LineFacePtr leftFace, 1039 LineFacePtr rightFace, 1040 double xorg, 1041 double yorg, 1042 Bool isInt) 1043{ 1044 int xorgi = 0, yorgi = 0; 1045 Spans spanRec; 1046 int n; 1047 PolyEdgeRec edge1, edge2; 1048 int edgey1, edgey2; 1049 Bool edgeleft1, edgeleft2; 1050 1051 if (isInt) 1052 { 1053 xorgi = leftFace ? leftFace->x : rightFace->x; 1054 yorgi = leftFace ? leftFace->y : rightFace->y; 1055 } 1056 edgey1 = 65536; 1057 edgey2 = 65536; 1058 edge1.x = 0; /* not used, keep memory checkers happy */ 1059 edge1.dy = -1; 1060 edge2.x = 0; /* not used, keep memory checkers happy */ 1061 edge2.dy = -1; 1062 edgeleft1 = FALSE; 1063 edgeleft2 = FALSE; 1064 if ((pGC->lineStyle != LineSolid || pGC->lineWidth > 2) && 1065 ((pGC->capStyle == CapRound && pGC->joinStyle != JoinRound) || 1066 (pGC->joinStyle == JoinRound && pGC->capStyle == CapButt))) 1067 { 1068 if (isInt) 1069 { 1070 xorg = (double) xorgi; 1071 yorg = (double) yorgi; 1072 } 1073 if (leftFace && rightFace) 1074 { 1075 miRoundJoinClip (leftFace, rightFace, &edge1, &edge2, 1076 &edgey1, &edgey2, &edgeleft1, &edgeleft2); 1077 } 1078 else if (leftFace) 1079 { 1080 edgey1 = miRoundCapClip (leftFace, isInt, &edge1, &edgeleft1); 1081 } 1082 else if (rightFace) 1083 { 1084 edgey2 = miRoundCapClip (rightFace, isInt, &edge2, &edgeleft2); 1085 } 1086 isInt = FALSE; 1087 } 1088 if (!InitSpans(&spanRec, pGC->lineWidth)) 1089 return; 1090 if (isInt) 1091 n = miLineArcI(pDraw, pGC, xorgi, yorgi, spanRec.points, spanRec.widths); 1092 else 1093 n = miLineArcD(pDraw, pGC, xorg, yorg, spanRec.points, spanRec.widths, 1094 &edge1, edgey1, edgeleft1, 1095 &edge2, edgey2, edgeleft2); 1096 spanRec.count = n; 1097 fillSpans (pDraw, pGC, pixel, &spanRec, spanData); 1098} 1099 1100static void 1101miLineProjectingCap (DrawablePtr pDrawable, GCPtr pGC, unsigned long pixel, 1102 SpanDataPtr spanData, LineFacePtr face, Bool isLeft, 1103 double xorg, double yorg, Bool isInt) 1104{ 1105 int xorgi = 0, yorgi = 0; 1106 int lw; 1107 PolyEdgeRec lefts[2], rights[2]; 1108 int lefty, righty, topy, bottomy; 1109 PolyEdgePtr left, right; 1110 PolyEdgePtr top, bottom; 1111 double xa,ya; 1112 double k; 1113 double xap, yap; 1114 int dx, dy; 1115 double projectXoff, projectYoff; 1116 double maxy; 1117 int finaly; 1118 1119 if (isInt) 1120 { 1121 xorgi = face->x; 1122 yorgi = face->y; 1123 } 1124 lw = pGC->lineWidth; 1125 dx = face->dx; 1126 dy = face->dy; 1127 k = face->k; 1128 if (dy == 0) 1129 { 1130 lefts[0].height = lw; 1131 lefts[0].x = xorgi; 1132 if (isLeft) 1133 lefts[0].x -= (lw >> 1); 1134 lefts[0].stepx = 0; 1135 lefts[0].signdx = 1; 1136 lefts[0].e = -lw; 1137 lefts[0].dx = 0; 1138 lefts[0].dy = lw; 1139 rights[0].height = lw; 1140 rights[0].x = xorgi; 1141 if (!isLeft) 1142 rights[0].x += ((lw + 1) >> 1); 1143 rights[0].stepx = 0; 1144 rights[0].signdx = 1; 1145 rights[0].e = -lw; 1146 rights[0].dx = 0; 1147 rights[0].dy = lw; 1148 miFillPolyHelper (pDrawable, pGC, pixel, spanData, yorgi - (lw >> 1), lw, 1149 lefts, rights, 1, 1); 1150 } 1151 else if (dx == 0) 1152 { 1153 if (dy < 0) { 1154 dy = -dy; 1155 isLeft = !isLeft; 1156 } 1157 topy = yorgi; 1158 bottomy = yorgi + dy; 1159 if (isLeft) 1160 topy -= (lw >> 1); 1161 else 1162 bottomy += (lw >> 1); 1163 lefts[0].height = bottomy - topy; 1164 lefts[0].x = xorgi - (lw >> 1); 1165 lefts[0].stepx = 0; 1166 lefts[0].signdx = 1; 1167 lefts[0].e = -dy; 1168 lefts[0].dx = dx; 1169 lefts[0].dy = dy; 1170 1171 rights[0].height = bottomy - topy; 1172 rights[0].x = lefts[0].x + (lw-1); 1173 rights[0].stepx = 0; 1174 rights[0].signdx = 1; 1175 rights[0].e = -dy; 1176 rights[0].dx = dx; 1177 rights[0].dy = dy; 1178 miFillPolyHelper (pDrawable, pGC, pixel, spanData, topy, bottomy - topy, lefts, rights, 1, 1); 1179 } 1180 else 1181 { 1182 xa = face->xa; 1183 ya = face->ya; 1184 projectXoff = -ya; 1185 projectYoff = xa; 1186 if (dx < 0) 1187 { 1188 right = &rights[1]; 1189 left = &lefts[0]; 1190 top = &rights[0]; 1191 bottom = &lefts[1]; 1192 } 1193 else 1194 { 1195 right = &rights[0]; 1196 left = &lefts[1]; 1197 top = &lefts[0]; 1198 bottom = &rights[1]; 1199 } 1200 if (isLeft) 1201 { 1202 righty = miPolyBuildEdge (xa, ya, 1203 k, dx, dy, xorgi, yorgi, 0, right); 1204 1205 xa = -xa; 1206 ya = -ya; 1207 k = -k; 1208 lefty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff, 1209 k, dx, dy, xorgi, yorgi, 1, left); 1210 if (dx > 0) 1211 { 1212 ya = -ya; 1213 xa = -xa; 1214 } 1215 xap = xa - projectXoff; 1216 yap = ya - projectYoff; 1217 topy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy, 1218 -dy, dx, xorgi, yorgi, dx > 0, top); 1219 bottomy = miPolyBuildEdge (xa, ya, 1220 0.0, -dy, dx, xorgi, yorgi, dx < 0, bottom); 1221 maxy = -ya; 1222 } 1223 else 1224 { 1225 righty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff, 1226 k, dx, dy, xorgi, yorgi, 0, right); 1227 1228 xa = -xa; 1229 ya = -ya; 1230 k = -k; 1231 lefty = miPolyBuildEdge (xa, ya, 1232 k, dx, dy, xorgi, yorgi, 1, left); 1233 if (dx > 0) 1234 { 1235 ya = -ya; 1236 xa = -xa; 1237 } 1238 xap = xa - projectXoff; 1239 yap = ya - projectYoff; 1240 topy = miPolyBuildEdge (xa, ya, 0.0, -dy, dx, xorgi, xorgi, dx > 0, top); 1241 bottomy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy, 1242 -dy, dx, xorgi, xorgi, dx < 0, bottom); 1243 maxy = -ya + projectYoff; 1244 } 1245 finaly = ICEIL(maxy) + yorgi; 1246 if (dx < 0) 1247 { 1248 left->height = bottomy - lefty; 1249 right->height = finaly - righty; 1250 top->height = righty - topy; 1251 } 1252 else 1253 { 1254 right->height = bottomy - righty; 1255 left->height = finaly - lefty; 1256 top->height = lefty - topy; 1257 } 1258 bottom->height = finaly - bottomy; 1259 miFillPolyHelper (pDrawable, pGC, pixel, spanData, topy, 1260 bottom->height + bottomy - topy, lefts, rights, 2, 2); 1261 } 1262} 1263 1264static void 1265miWideSegment ( 1266 DrawablePtr pDrawable, 1267 GCPtr pGC, 1268 unsigned long pixel, 1269 SpanDataPtr spanData, 1270 int x1, 1271 int y1, 1272 int x2, 1273 int y2, 1274 Bool projectLeft, 1275 Bool projectRight, 1276 LineFacePtr leftFace, 1277 LineFacePtr rightFace) 1278{ 1279 double l, L, r; 1280 double xa, ya; 1281 double projectXoff = 0.0, projectYoff = 0.0; 1282 double k; 1283 double maxy; 1284 int x, y; 1285 int dx, dy; 1286 int finaly; 1287 PolyEdgePtr left, right; 1288 PolyEdgePtr top, bottom; 1289 int lefty, righty, topy, bottomy; 1290 int signdx; 1291 PolyEdgeRec lefts[2], rights[2]; 1292 LineFacePtr tface; 1293 int lw = pGC->lineWidth; 1294 1295 /* draw top-to-bottom always */ 1296 if (y2 < y1 || (y2 == y1 && x2 < x1)) 1297 { 1298 x = x1; 1299 x1 = x2; 1300 x2 = x; 1301 1302 y = y1; 1303 y1 = y2; 1304 y2 = y; 1305 1306 x = projectLeft; 1307 projectLeft = projectRight; 1308 projectRight = x; 1309 1310 tface = leftFace; 1311 leftFace = rightFace; 1312 rightFace = tface; 1313 } 1314 1315 dy = y2 - y1; 1316 signdx = 1; 1317 dx = x2 - x1; 1318 if (dx < 0) 1319 signdx = -1; 1320 1321 leftFace->x = x1; 1322 leftFace->y = y1; 1323 leftFace->dx = dx; 1324 leftFace->dy = dy; 1325 1326 rightFace->x = x2; 1327 rightFace->y = y2; 1328 rightFace->dx = -dx; 1329 rightFace->dy = -dy; 1330 1331 if (dy == 0) 1332 { 1333 rightFace->xa = 0; 1334 rightFace->ya = (double) lw / 2.0; 1335 rightFace->k = -(double) (lw * dx) / 2.0; 1336 leftFace->xa = 0; 1337 leftFace->ya = -rightFace->ya; 1338 leftFace->k = rightFace->k; 1339 x = x1; 1340 if (projectLeft) 1341 x -= (lw >> 1); 1342 y = y1 - (lw >> 1); 1343 dx = x2 - x; 1344 if (projectRight) 1345 dx += ((lw + 1) >> 1); 1346 dy = lw; 1347 miFillRectPolyHelper (pDrawable, pGC, pixel, spanData, 1348 x, y, dx, dy); 1349 } 1350 else if (dx == 0) 1351 { 1352 leftFace->xa = (double) lw / 2.0; 1353 leftFace->ya = 0; 1354 leftFace->k = (double) (lw * dy) / 2.0; 1355 rightFace->xa = -leftFace->xa; 1356 rightFace->ya = 0; 1357 rightFace->k = leftFace->k; 1358 y = y1; 1359 if (projectLeft) 1360 y -= lw >> 1; 1361 x = x1 - (lw >> 1); 1362 dy = y2 - y; 1363 if (projectRight) 1364 dy += ((lw + 1) >> 1); 1365 dx = lw; 1366 miFillRectPolyHelper (pDrawable, pGC, pixel, spanData, 1367 x, y, dx, dy); 1368 } 1369 else 1370 { 1371 l = ((double) lw) / 2.0; 1372 L = hypot ((double) dx, (double) dy); 1373 1374 if (dx < 0) 1375 { 1376 right = &rights[1]; 1377 left = &lefts[0]; 1378 top = &rights[0]; 1379 bottom = &lefts[1]; 1380 } 1381 else 1382 { 1383 right = &rights[0]; 1384 left = &lefts[1]; 1385 top = &lefts[0]; 1386 bottom = &rights[1]; 1387 } 1388 r = l / L; 1389 1390 /* coord of upper bound at integral y */ 1391 ya = -r * dx; 1392 xa = r * dy; 1393 1394 if (projectLeft | projectRight) 1395 { 1396 projectXoff = -ya; 1397 projectYoff = xa; 1398 } 1399 1400 /* xa * dy - ya * dx */ 1401 k = l * L; 1402 1403 leftFace->xa = xa; 1404 leftFace->ya = ya; 1405 leftFace->k = k; 1406 rightFace->xa = -xa; 1407 rightFace->ya = -ya; 1408 rightFace->k = k; 1409 1410 if (projectLeft) 1411 righty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff, 1412 k, dx, dy, x1, y1, 0, right); 1413 else 1414 righty = miPolyBuildEdge (xa, ya, 1415 k, dx, dy, x1, y1, 0, right); 1416 1417 /* coord of lower bound at integral y */ 1418 ya = -ya; 1419 xa = -xa; 1420 1421 /* xa * dy - ya * dx */ 1422 k = - k; 1423 1424 if (projectLeft) 1425 lefty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff, 1426 k, dx, dy, x1, y1, 1, left); 1427 else 1428 lefty = miPolyBuildEdge (xa, ya, 1429 k, dx, dy, x1, y1, 1, left); 1430 1431 /* coord of top face at integral y */ 1432 1433 if (signdx > 0) 1434 { 1435 ya = -ya; 1436 xa = -xa; 1437 } 1438 1439 if (projectLeft) 1440 { 1441 double xap = xa - projectXoff; 1442 double yap = ya - projectYoff; 1443 topy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy, 1444 -dy, dx, x1, y1, dx > 0, top); 1445 } 1446 else 1447 topy = miPolyBuildEdge (xa, ya, 0.0, -dy, dx, x1, y1, dx > 0, top); 1448 1449 /* coord of bottom face at integral y */ 1450 1451 if (projectRight) 1452 { 1453 double xap = xa + projectXoff; 1454 double yap = ya + projectYoff; 1455 bottomy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy, 1456 -dy, dx, x2, y2, dx < 0, bottom); 1457 maxy = -ya + projectYoff; 1458 } 1459 else 1460 { 1461 bottomy = miPolyBuildEdge (xa, ya, 1462 0.0, -dy, dx, x2, y2, dx < 0, bottom); 1463 maxy = -ya; 1464 } 1465 1466 finaly = ICEIL (maxy) + y2; 1467 1468 if (dx < 0) 1469 { 1470 left->height = bottomy - lefty; 1471 right->height = finaly - righty; 1472 top->height = righty - topy; 1473 } 1474 else 1475 { 1476 right->height = bottomy - righty; 1477 left->height = finaly - lefty; 1478 top->height = lefty - topy; 1479 } 1480 bottom->height = finaly - bottomy; 1481 miFillPolyHelper (pDrawable, pGC, pixel, spanData, topy, 1482 bottom->height + bottomy - topy, lefts, rights, 2, 2); 1483 } 1484} 1485 1486static SpanDataPtr 1487miSetupSpanData (GCPtr pGC, SpanDataPtr spanData, int npt) 1488{ 1489 if ((npt < 3 && pGC->capStyle != CapRound) || miSpansEasyRop(pGC->alu)) 1490 return (SpanDataPtr) NULL; 1491 if (pGC->lineStyle == LineDoubleDash) 1492 miInitSpanGroup (&spanData->bgGroup); 1493 miInitSpanGroup (&spanData->fgGroup); 1494 return spanData; 1495} 1496 1497static void 1498miCleanupSpanData (DrawablePtr pDrawable, GCPtr pGC, SpanDataPtr spanData) 1499{ 1500 if (pGC->lineStyle == LineDoubleDash) 1501 { 1502 ChangeGCVal oldPixel, pixel; 1503 pixel.val = pGC->bgPixel; 1504 oldPixel.val = pGC->fgPixel; 1505 if (pixel.val != oldPixel.val) 1506 { 1507 ChangeGC (NullClient, pGC, GCForeground, &pixel); 1508 ValidateGC (pDrawable, pGC); 1509 } 1510 miFillUniqueSpanGroup (pDrawable, pGC, &spanData->bgGroup); 1511 miFreeSpanGroup (&spanData->bgGroup); 1512 if (pixel.val != oldPixel.val) 1513 { 1514 ChangeGC (NullClient, pGC, GCForeground, &oldPixel); 1515 ValidateGC (pDrawable, pGC); 1516 } 1517 } 1518 miFillUniqueSpanGroup (pDrawable, pGC, &spanData->fgGroup); 1519 miFreeSpanGroup (&spanData->fgGroup); 1520} 1521 1522void 1523miWideLine (DrawablePtr pDrawable, GCPtr pGC, 1524 int mode, int npt, DDXPointPtr pPts) 1525{ 1526 int x1, y1, x2, y2; 1527 SpanDataRec spanDataRec; 1528 SpanDataPtr spanData; 1529 long pixel; 1530 Bool projectLeft, projectRight; 1531 LineFaceRec leftFace, rightFace, prevRightFace; 1532 LineFaceRec firstFace; 1533 int first; 1534 Bool somethingDrawn = FALSE; 1535 Bool selfJoin; 1536 1537 spanData = miSetupSpanData (pGC, &spanDataRec, npt); 1538 pixel = pGC->fgPixel; 1539 x2 = pPts->x; 1540 y2 = pPts->y; 1541 first = TRUE; 1542 selfJoin = FALSE; 1543 if (npt > 1) 1544 { 1545 if (mode == CoordModePrevious) 1546 { 1547 int nptTmp; 1548 DDXPointPtr pPtsTmp; 1549 1550 x1 = x2; 1551 y1 = y2; 1552 nptTmp = npt; 1553 pPtsTmp = pPts + 1; 1554 while (--nptTmp) 1555 { 1556 x1 += pPtsTmp->x; 1557 y1 += pPtsTmp->y; 1558 ++pPtsTmp; 1559 } 1560 if (x2 == x1 && y2 == y1) 1561 selfJoin = TRUE; 1562 } 1563 else if (x2 == pPts[npt-1].x && y2 == pPts[npt-1].y) 1564 { 1565 selfJoin = TRUE; 1566 } 1567 } 1568 projectLeft = pGC->capStyle == CapProjecting && !selfJoin; 1569 projectRight = FALSE; 1570 while (--npt) 1571 { 1572 x1 = x2; 1573 y1 = y2; 1574 ++pPts; 1575 x2 = pPts->x; 1576 y2 = pPts->y; 1577 if (mode == CoordModePrevious) 1578 { 1579 x2 += x1; 1580 y2 += y1; 1581 } 1582 if (x1 != x2 || y1 != y2) 1583 { 1584 somethingDrawn = TRUE; 1585 if (npt == 1 && pGC->capStyle == CapProjecting && !selfJoin) 1586 projectRight = TRUE; 1587 miWideSegment (pDrawable, pGC, pixel, spanData, x1, y1, x2, y2, 1588 projectLeft, projectRight, &leftFace, &rightFace); 1589 if (first) 1590 { 1591 if (selfJoin) 1592 firstFace = leftFace; 1593 else if (pGC->capStyle == CapRound) 1594 { 1595 if (pGC->lineWidth == 1 && !spanData) 1596 miLineOnePoint (pDrawable, pGC, pixel, spanData, x1, y1); 1597 else 1598 miLineArc (pDrawable, pGC, pixel, spanData, 1599 &leftFace, (LineFacePtr) NULL, 1600 (double)0.0, (double)0.0, 1601 TRUE); 1602 } 1603 } 1604 else 1605 { 1606 miLineJoin (pDrawable, pGC, pixel, spanData, &leftFace, 1607 &prevRightFace); 1608 } 1609 prevRightFace = rightFace; 1610 first = FALSE; 1611 projectLeft = FALSE; 1612 } 1613 if (npt == 1 && somethingDrawn) 1614 { 1615 if (selfJoin) 1616 miLineJoin (pDrawable, pGC, pixel, spanData, &firstFace, 1617 &rightFace); 1618 else if (pGC->capStyle == CapRound) 1619 { 1620 if (pGC->lineWidth == 1 && !spanData) 1621 miLineOnePoint (pDrawable, pGC, pixel, spanData, x2, y2); 1622 else 1623 miLineArc (pDrawable, pGC, pixel, spanData, 1624 (LineFacePtr) NULL, &rightFace, 1625 (double)0.0, (double)0.0, 1626 TRUE); 1627 } 1628 } 1629 } 1630 /* handle crock where all points are coincedent */ 1631 if (!somethingDrawn) 1632 { 1633 projectLeft = pGC->capStyle == CapProjecting; 1634 miWideSegment (pDrawable, pGC, pixel, spanData, 1635 x2, y2, x2, y2, projectLeft, projectLeft, 1636 &leftFace, &rightFace); 1637 if (pGC->capStyle == CapRound) 1638 { 1639 miLineArc (pDrawable, pGC, pixel, spanData, 1640 &leftFace, (LineFacePtr) NULL, 1641 (double)0.0, (double)0.0, 1642 TRUE); 1643 rightFace.dx = -1; /* sleezy hack to make it work */ 1644 miLineArc (pDrawable, pGC, pixel, spanData, 1645 (LineFacePtr) NULL, &rightFace, 1646 (double)0.0, (double)0.0, 1647 TRUE); 1648 } 1649 } 1650 if (spanData) 1651 miCleanupSpanData (pDrawable, pGC, spanData); 1652} 1653 1654#define V_TOP 0 1655#define V_RIGHT 1 1656#define V_BOTTOM 2 1657#define V_LEFT 3 1658 1659static void 1660miWideDashSegment ( 1661 DrawablePtr pDrawable, 1662 GCPtr pGC, 1663 SpanDataPtr spanData, 1664 int *pDashOffset, 1665 int *pDashIndex, 1666 int x1, 1667 int y1, 1668 int x2, 1669 int y2, 1670 Bool projectLeft, 1671 Bool projectRight, 1672 LineFacePtr leftFace, 1673 LineFacePtr rightFace) 1674{ 1675 int dashIndex, dashRemain; 1676 unsigned char *pDash; 1677 double L, l; 1678 double k; 1679 PolyVertexRec vertices[4]; 1680 PolyVertexRec saveRight, saveBottom; 1681 PolySlopeRec slopes[4]; 1682 PolyEdgeRec left[2], right[2]; 1683 LineFaceRec lcapFace, rcapFace; 1684 int nleft, nright; 1685 int h; 1686 int y; 1687 int dy, dx; 1688 unsigned long pixel; 1689 double LRemain; 1690 double r; 1691 double rdx, rdy; 1692 double dashDx, dashDy; 1693 double saveK = 0.0; 1694 Bool first = TRUE; 1695 double lcenterx, lcentery, rcenterx = 0.0, rcentery = 0.0; 1696 unsigned long fgPixel, bgPixel; 1697 1698 dx = x2 - x1; 1699 dy = y2 - y1; 1700 dashIndex = *pDashIndex; 1701 pDash = pGC->dash; 1702 dashRemain = pDash[dashIndex] - *pDashOffset; 1703 fgPixel = pGC->fgPixel; 1704 bgPixel = pGC->bgPixel; 1705 if (pGC->fillStyle == FillOpaqueStippled || 1706 pGC->fillStyle == FillTiled) 1707 { 1708 bgPixel = fgPixel; 1709 } 1710 1711 l = ((double) pGC->lineWidth) / 2.0; 1712 if (dx == 0) 1713 { 1714 L = dy; 1715 rdx = 0; 1716 rdy = l; 1717 if (dy < 0) 1718 { 1719 L = -dy; 1720 rdy = -l; 1721 } 1722 } 1723 else if (dy == 0) 1724 { 1725 L = dx; 1726 rdx = l; 1727 rdy = 0; 1728 if (dx < 0) 1729 { 1730 L = -dx; 1731 rdx = -l; 1732 } 1733 } 1734 else 1735 { 1736 L = hypot ((double) dx, (double) dy); 1737 r = l / L; 1738 1739 rdx = r * dx; 1740 rdy = r * dy; 1741 } 1742 k = l * L; 1743 LRemain = L; 1744 /* All position comments are relative to a line with dx and dy > 0, 1745 * but the code does not depend on this */ 1746 /* top */ 1747 slopes[V_TOP].dx = dx; 1748 slopes[V_TOP].dy = dy; 1749 slopes[V_TOP].k = k; 1750 /* right */ 1751 slopes[V_RIGHT].dx = -dy; 1752 slopes[V_RIGHT].dy = dx; 1753 slopes[V_RIGHT].k = 0; 1754 /* bottom */ 1755 slopes[V_BOTTOM].dx = -dx; 1756 slopes[V_BOTTOM].dy = -dy; 1757 slopes[V_BOTTOM].k = k; 1758 /* left */ 1759 slopes[V_LEFT].dx = dy; 1760 slopes[V_LEFT].dy = -dx; 1761 slopes[V_LEFT].k = 0; 1762 1763 /* preload the start coordinates */ 1764 vertices[V_RIGHT].x = vertices[V_TOP].x = rdy; 1765 vertices[V_RIGHT].y = vertices[V_TOP].y = -rdx; 1766 1767 vertices[V_BOTTOM].x = vertices[V_LEFT].x = -rdy; 1768 vertices[V_BOTTOM].y = vertices[V_LEFT].y = rdx; 1769 1770 if (projectLeft) 1771 { 1772 vertices[V_TOP].x -= rdx; 1773 vertices[V_TOP].y -= rdy; 1774 1775 vertices[V_LEFT].x -= rdx; 1776 vertices[V_LEFT].y -= rdy; 1777 1778 slopes[V_LEFT].k = rdx * dx + rdy * dy; 1779 } 1780 1781 lcenterx = x1; 1782 lcentery = y1; 1783 1784 if (pGC->capStyle == CapRound) 1785 { 1786 lcapFace.dx = dx; 1787 lcapFace.dy = dy; 1788 lcapFace.x = x1; 1789 lcapFace.y = y1; 1790 1791 rcapFace.dx = -dx; 1792 rcapFace.dy = -dy; 1793 rcapFace.x = x1; 1794 rcapFace.y = y1; 1795 } 1796 while (LRemain > dashRemain) 1797 { 1798 dashDx = (dashRemain * dx) / L; 1799 dashDy = (dashRemain * dy) / L; 1800 1801 rcenterx = lcenterx + dashDx; 1802 rcentery = lcentery + dashDy; 1803 1804 vertices[V_RIGHT].x += dashDx; 1805 vertices[V_RIGHT].y += dashDy; 1806 1807 vertices[V_BOTTOM].x += dashDx; 1808 vertices[V_BOTTOM].y += dashDy; 1809 1810 slopes[V_RIGHT].k = vertices[V_RIGHT].x * dx + vertices[V_RIGHT].y * dy; 1811 1812 if (pGC->lineStyle == LineDoubleDash || !(dashIndex & 1)) 1813 { 1814 if (pGC->lineStyle == LineOnOffDash && 1815 pGC->capStyle == CapProjecting) 1816 { 1817 saveRight = vertices[V_RIGHT]; 1818 saveBottom = vertices[V_BOTTOM]; 1819 saveK = slopes[V_RIGHT].k; 1820 1821 if (!first) 1822 { 1823 vertices[V_TOP].x -= rdx; 1824 vertices[V_TOP].y -= rdy; 1825 1826 vertices[V_LEFT].x -= rdx; 1827 vertices[V_LEFT].y -= rdy; 1828 1829 slopes[V_LEFT].k = vertices[V_LEFT].x * 1830 slopes[V_LEFT].dy - 1831 vertices[V_LEFT].y * 1832 slopes[V_LEFT].dx; 1833 } 1834 1835 vertices[V_RIGHT].x += rdx; 1836 vertices[V_RIGHT].y += rdy; 1837 1838 vertices[V_BOTTOM].x += rdx; 1839 vertices[V_BOTTOM].y += rdy; 1840 1841 slopes[V_RIGHT].k = vertices[V_RIGHT].x * 1842 slopes[V_RIGHT].dy - 1843 vertices[V_RIGHT].y * 1844 slopes[V_RIGHT].dx; 1845 } 1846 y = miPolyBuildPoly (vertices, slopes, 4, x1, y1, 1847 left, right, &nleft, &nright, &h); 1848 pixel = (dashIndex & 1) ? bgPixel : fgPixel; 1849 miFillPolyHelper (pDrawable, pGC, pixel, spanData, y, h, left, right, nleft, nright); 1850 1851 if (pGC->lineStyle == LineOnOffDash) 1852 { 1853 switch (pGC->capStyle) 1854 { 1855 case CapProjecting: 1856 vertices[V_BOTTOM] = saveBottom; 1857 vertices[V_RIGHT] = saveRight; 1858 slopes[V_RIGHT].k = saveK; 1859 break; 1860 case CapRound: 1861 if (!first) 1862 { 1863 if (dx < 0) 1864 { 1865 lcapFace.xa = -vertices[V_LEFT].x; 1866 lcapFace.ya = -vertices[V_LEFT].y; 1867 lcapFace.k = slopes[V_LEFT].k; 1868 } 1869 else 1870 { 1871 lcapFace.xa = vertices[V_TOP].x; 1872 lcapFace.ya = vertices[V_TOP].y; 1873 lcapFace.k = -slopes[V_LEFT].k; 1874 } 1875 miLineArc (pDrawable, pGC, pixel, spanData, 1876 &lcapFace, (LineFacePtr) NULL, 1877 lcenterx, lcentery, FALSE); 1878 } 1879 if (dx < 0) 1880 { 1881 rcapFace.xa = vertices[V_BOTTOM].x; 1882 rcapFace.ya = vertices[V_BOTTOM].y; 1883 rcapFace.k = slopes[V_RIGHT].k; 1884 } 1885 else 1886 { 1887 rcapFace.xa = -vertices[V_RIGHT].x; 1888 rcapFace.ya = -vertices[V_RIGHT].y; 1889 rcapFace.k = -slopes[V_RIGHT].k; 1890 } 1891 miLineArc (pDrawable, pGC, pixel, spanData, 1892 (LineFacePtr) NULL, &rcapFace, 1893 rcenterx, rcentery, FALSE); 1894 break; 1895 } 1896 } 1897 } 1898 LRemain -= dashRemain; 1899 ++dashIndex; 1900 if (dashIndex == pGC->numInDashList) 1901 dashIndex = 0; 1902 dashRemain = pDash[dashIndex]; 1903 1904 lcenterx = rcenterx; 1905 lcentery = rcentery; 1906 1907 vertices[V_TOP] = vertices[V_RIGHT]; 1908 vertices[V_LEFT] = vertices[V_BOTTOM]; 1909 slopes[V_LEFT].k = -slopes[V_RIGHT].k; 1910 first = FALSE; 1911 } 1912 1913 if (pGC->lineStyle == LineDoubleDash || !(dashIndex & 1)) 1914 { 1915 vertices[V_TOP].x -= dx; 1916 vertices[V_TOP].y -= dy; 1917 1918 vertices[V_LEFT].x -= dx; 1919 vertices[V_LEFT].y -= dy; 1920 1921 vertices[V_RIGHT].x = rdy; 1922 vertices[V_RIGHT].y = -rdx; 1923 1924 vertices[V_BOTTOM].x = -rdy; 1925 vertices[V_BOTTOM].y = rdx; 1926 1927 1928 if (projectRight) 1929 { 1930 vertices[V_RIGHT].x += rdx; 1931 vertices[V_RIGHT].y += rdy; 1932 1933 vertices[V_BOTTOM].x += rdx; 1934 vertices[V_BOTTOM].y += rdy; 1935 slopes[V_RIGHT].k = vertices[V_RIGHT].x * 1936 slopes[V_RIGHT].dy - 1937 vertices[V_RIGHT].y * 1938 slopes[V_RIGHT].dx; 1939 } 1940 else 1941 slopes[V_RIGHT].k = 0; 1942 1943 if (!first && pGC->lineStyle == LineOnOffDash && 1944 pGC->capStyle == CapProjecting) 1945 { 1946 vertices[V_TOP].x -= rdx; 1947 vertices[V_TOP].y -= rdy; 1948 1949 vertices[V_LEFT].x -= rdx; 1950 vertices[V_LEFT].y -= rdy; 1951 slopes[V_LEFT].k = vertices[V_LEFT].x * 1952 slopes[V_LEFT].dy - 1953 vertices[V_LEFT].y * 1954 slopes[V_LEFT].dx; 1955 } 1956 else 1957 slopes[V_LEFT].k += dx * dx + dy * dy; 1958 1959 1960 y = miPolyBuildPoly (vertices, slopes, 4, x2, y2, 1961 left, right, &nleft, &nright, &h); 1962 1963 pixel = (dashIndex & 1) ? pGC->bgPixel : pGC->fgPixel; 1964 miFillPolyHelper (pDrawable, pGC, pixel, spanData, y, h, left, right, nleft, nright); 1965 if (!first && pGC->lineStyle == LineOnOffDash && 1966 pGC->capStyle == CapRound) 1967 { 1968 lcapFace.x = x2; 1969 lcapFace.y = y2; 1970 if (dx < 0) 1971 { 1972 lcapFace.xa = -vertices[V_LEFT].x; 1973 lcapFace.ya = -vertices[V_LEFT].y; 1974 lcapFace.k = slopes[V_LEFT].k; 1975 } 1976 else 1977 { 1978 lcapFace.xa = vertices[V_TOP].x; 1979 lcapFace.ya = vertices[V_TOP].y; 1980 lcapFace.k = -slopes[V_LEFT].k; 1981 } 1982 miLineArc (pDrawable, pGC, pixel, spanData, 1983 &lcapFace, (LineFacePtr) NULL, 1984 rcenterx, rcentery, FALSE); 1985 } 1986 } 1987 dashRemain = ((double) dashRemain) - LRemain; 1988 if (dashRemain == 0) 1989 { 1990 dashIndex++; 1991 if (dashIndex == pGC->numInDashList) 1992 dashIndex = 0; 1993 dashRemain = pDash[dashIndex]; 1994 } 1995 1996 leftFace->x = x1; 1997 leftFace->y = y1; 1998 leftFace->dx = dx; 1999 leftFace->dy = dy; 2000 leftFace->xa = rdy; 2001 leftFace->ya = -rdx; 2002 leftFace->k = k; 2003 2004 rightFace->x = x2; 2005 rightFace->y = y2; 2006 rightFace->dx = -dx; 2007 rightFace->dy = -dy; 2008 rightFace->xa = -rdy; 2009 rightFace->ya = rdx; 2010 rightFace->k = k; 2011 2012 *pDashIndex = dashIndex; 2013 *pDashOffset = pDash[dashIndex] - dashRemain; 2014} 2015 2016void 2017miWideDash (DrawablePtr pDrawable, GCPtr pGC, 2018 int mode, int npt, DDXPointPtr pPts) 2019{ 2020 int x1, y1, x2, y2; 2021 unsigned long pixel; 2022 Bool projectLeft, projectRight; 2023 LineFaceRec leftFace, rightFace, prevRightFace; 2024 LineFaceRec firstFace; 2025 int first; 2026 int dashIndex, dashOffset; 2027 int prevDashIndex; 2028 SpanDataRec spanDataRec; 2029 SpanDataPtr spanData; 2030 Bool somethingDrawn = FALSE; 2031 Bool selfJoin; 2032 Bool endIsFg = FALSE, startIsFg = FALSE; 2033 Bool firstIsFg = FALSE, prevIsFg = FALSE; 2034 2035#if 0 2036 /* XXX backward compatibility */ 2037 if (pGC->lineWidth == 0) 2038 { 2039 miZeroDashLine (pDrawable, pGC, mode, npt, pPts); 2040 return; 2041 } 2042#endif 2043 if (pGC->lineStyle == LineDoubleDash && 2044 (pGC->fillStyle == FillOpaqueStippled || pGC->fillStyle == FillTiled)) 2045 { 2046 miWideLine (pDrawable, pGC, mode, npt, pPts); 2047 return; 2048 } 2049 if (npt == 0) 2050 return; 2051 spanData = miSetupSpanData (pGC, &spanDataRec, npt); 2052 x2 = pPts->x; 2053 y2 = pPts->y; 2054 first = TRUE; 2055 selfJoin = FALSE; 2056 if (mode == CoordModePrevious) 2057 { 2058 int nptTmp; 2059 DDXPointPtr pPtsTmp; 2060 2061 x1 = x2; 2062 y1 = y2; 2063 nptTmp = npt; 2064 pPtsTmp = pPts + 1; 2065 while (--nptTmp) 2066 { 2067 x1 += pPtsTmp->x; 2068 y1 += pPtsTmp->y; 2069 ++pPtsTmp; 2070 } 2071 if (x2 == x1 && y2 == y1) 2072 selfJoin = TRUE; 2073 } 2074 else if (x2 == pPts[npt-1].x && y2 == pPts[npt-1].y) 2075 { 2076 selfJoin = TRUE; 2077 } 2078 projectLeft = pGC->capStyle == CapProjecting && !selfJoin; 2079 projectRight = FALSE; 2080 dashIndex = 0; 2081 dashOffset = 0; 2082 miStepDash ((int)pGC->dashOffset, &dashIndex, 2083 pGC->dash, (int)pGC->numInDashList, &dashOffset); 2084 while (--npt) 2085 { 2086 x1 = x2; 2087 y1 = y2; 2088 ++pPts; 2089 x2 = pPts->x; 2090 y2 = pPts->y; 2091 if (mode == CoordModePrevious) 2092 { 2093 x2 += x1; 2094 y2 += y1; 2095 } 2096 if (x1 != x2 || y1 != y2) 2097 { 2098 somethingDrawn = TRUE; 2099 if (npt == 1 && pGC->capStyle == CapProjecting && 2100 (!selfJoin || !firstIsFg)) 2101 projectRight = TRUE; 2102 prevDashIndex = dashIndex; 2103 miWideDashSegment (pDrawable, pGC, spanData, &dashOffset, &dashIndex, 2104 x1, y1, x2, y2, 2105 projectLeft, projectRight, &leftFace, &rightFace); 2106 startIsFg = !(prevDashIndex & 1); 2107 endIsFg = (dashIndex & 1) ^ (dashOffset != 0); 2108 if (pGC->lineStyle == LineDoubleDash || startIsFg) 2109 { 2110 pixel = startIsFg ? pGC->fgPixel : pGC->bgPixel; 2111 if (first || (pGC->lineStyle == LineOnOffDash && !prevIsFg)) 2112 { 2113 if (first && selfJoin) 2114 { 2115 firstFace = leftFace; 2116 firstIsFg = startIsFg; 2117 } 2118 else if (pGC->capStyle == CapRound) 2119 miLineArc (pDrawable, pGC, pixel, spanData, 2120 &leftFace, (LineFacePtr) NULL, 2121 (double)0.0, (double)0.0, TRUE); 2122 } 2123 else 2124 { 2125 miLineJoin (pDrawable, pGC, pixel, spanData, &leftFace, 2126 &prevRightFace); 2127 } 2128 } 2129 prevRightFace = rightFace; 2130 prevIsFg = endIsFg; 2131 first = FALSE; 2132 projectLeft = FALSE; 2133 } 2134 if (npt == 1 && somethingDrawn) 2135 { 2136 if (pGC->lineStyle == LineDoubleDash || endIsFg) 2137 { 2138 pixel = endIsFg ? pGC->fgPixel : pGC->bgPixel; 2139 if (selfJoin && (pGC->lineStyle == LineDoubleDash || firstIsFg)) 2140 { 2141 miLineJoin (pDrawable, pGC, pixel, spanData, &firstFace, 2142 &rightFace); 2143 } 2144 else 2145 { 2146 if (pGC->capStyle == CapRound) 2147 miLineArc (pDrawable, pGC, pixel, spanData, 2148 (LineFacePtr) NULL, &rightFace, 2149 (double)0.0, (double)0.0, TRUE); 2150 } 2151 } 2152 else 2153 { 2154 /* glue a cap to the start of the line if 2155 * we're OnOffDash and ended on odd dash 2156 */ 2157 if (selfJoin && firstIsFg) 2158 { 2159 pixel = pGC->fgPixel; 2160 if (pGC->capStyle == CapProjecting) 2161 miLineProjectingCap (pDrawable, pGC, pixel, spanData, 2162 &firstFace, TRUE, 2163 (double)0.0, (double)0.0, TRUE); 2164 else if (pGC->capStyle == CapRound) 2165 miLineArc (pDrawable, pGC, pixel, spanData, 2166 &firstFace, (LineFacePtr) NULL, 2167 (double)0.0, (double)0.0, TRUE); 2168 } 2169 } 2170 } 2171 } 2172 /* handle crock where all points are coincident */ 2173 if (!somethingDrawn && (pGC->lineStyle == LineDoubleDash || !(dashIndex & 1))) 2174 { 2175 /* not the same as endIsFg computation above */ 2176 pixel = (dashIndex & 1) ? pGC->bgPixel : pGC->fgPixel; 2177 switch (pGC->capStyle) { 2178 case CapRound: 2179 miLineArc (pDrawable, pGC, pixel, spanData, 2180 (LineFacePtr) NULL, (LineFacePtr) NULL, 2181 (double)x2, (double)y2, 2182 FALSE); 2183 break; 2184 case CapProjecting: 2185 x1 = pGC->lineWidth; 2186 miFillRectPolyHelper (pDrawable, pGC, pixel, spanData, 2187 x2 - (x1 >> 1), y2 - (x1 >> 1), x1, x1); 2188 break; 2189 } 2190 } 2191 if (spanData) 2192 miCleanupSpanData (pDrawable, pGC, spanData); 2193} 2194