mi/miwideline.c

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