git.sesse.net Git - rdpsrv/blob - Xserver/programs/Xserver/mi/miarc.c

   1 /***********************************************************
   2
   3 Copyright (c) 1987  X Consortium
   4
   5 Permission is hereby granted, free of charge, to any person obtaining a copy
   6 of this software and associated documentation files (the "Software"), to deal
   7 in the Software without restriction, including without limitation the rights
   8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9 copies of the Software, and to permit persons to whom the Software is
  10 furnished to do so, subject to the following conditions:
  11
  12 The above copyright notice and this permission notice shall be included in
  13 all copies or substantial portions of the Software.
  14
  15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  18 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  19 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  20 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21
  22 Except as contained in this notice, the name of the X Consortium shall not be
  23 used in advertising or otherwise to promote the sale, use or other dealings
  24 in this Software without prior written authorization from the X Consortium.
  25
  26
  27 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
  28
  29                         All Rights Reserved
  30
  31 Permission to use, copy, modify, and distribute this software and its
  32 documentation for any purpose and without fee is hereby granted,
  33 provided that the above copyright notice appear in all copies and that
  34 both that copyright notice and this permission notice appear in
  35 supporting documentation, and that the name of Digital not be
  36 used in advertising or publicity pertaining to distribution of the
  37 software without specific, written prior permission.
  38
  39 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  40 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  41 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  42 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  43 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  44 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  45 SOFTWARE.
  46
  47 ******************************************************************/
  48 /* $XConsortium: miarc.c /main/90 1996/08/01 19:25:10 dpw $ */
  49 /* Author: Keith Packard and Bob Scheifler */
  50 /* Warning: this code is toxic, do not dally very long here. */
  51
  52 /* $XFree86: xc/programs/Xserver/mi/miarc.c,v 3.4.2.1 1997/07/13 14:45:05 dawes Exp $ */
  53
  54 #ifdef _XOPEN_SOURCE
  55 #include <math.h>
  56 #else
  57 #define _XOPEN_SOURCE   /* to get prototype for hypot on some systems */
  58 #include <math.h>
  59 #undef _XOPEN_SOURCE
  60 #endif
  61 #include "X.h"
  62 #include "Xprotostr.h"
  63 #include "misc.h"
  64 #include "gcstruct.h"
  65 #include "scrnintstr.h"
  66 #include "pixmapstr.h"
  67 #include "windowstr.h"
  68 #include "mifpoly.h"
  69 #include "mi.h"
  70 #include "mifillarc.h"
  71 #include "Xfuncproto.h"
  72
  73 static double miDsin(), miDcos(), miDasin(), miDatan2();
  74 double  cbrt(
  75 #if NeedFunctionPrototypes
  76              double
  77 #endif
  78 );
  79
  80 #ifdef ICEILTEMPDECL
  81 ICEILTEMPDECL
  82 #endif
  83
  84 /*
  85  * some interesting sematic interpretation of the protocol:
  86  *
  87  * Self intersecting arcs (i.e. those spanning 360 degrees)
  88  *  never join with other arcs, and are drawn without caps
  89  *  (unless on/off dashed, in which case each dash segment
  90  *  is capped, except when the last segment meets the
  91  *  first segment, when no caps are drawn)
  92  *
  93  * double dash arcs are drawn in two parts, first the
  94  *  odd dashes (drawn in background) then the even dashes
  95  *  (drawn in foreground).  This means that overlapping
  96  *  sections of foreground/background are drawn twice,
  97  *  first in background then in foreground.  The double-draw
  98  *  occurs even when the function uses the destination values
  99  *  (e.g. xor mode).  This is the same way the wide-line
 100  *  code works and should be "fixed".
 101  *
 102  */
 103
 104 #undef max
 105 #undef min
 106
 107 #if defined (__GNUC__) && defined (__STDC__) && !defined (__STRICT_ANSI__)
 108 #define USE_INLINE
 109 #endif
 110
 111 #ifdef USE_INLINE
 112 inline static const int max (const int x, const int y)
 113 {
 114         return x>y? x:y;
 115 }
 116
 117 inline static const int min (const int x, const int y)
 118 {
 119         return x<y? x:y;
 120 }
 121
 122 #else
 123
 124 static int
 125 max (x, y)
 126 {
 127         return x>y? x:y;
 128 }
 129
 130 static int
 131 min (x, y)
 132 {
 133         return x<y? x:y;
 134 }
 135
 136 #endif
 137
 138 struct bound {
 139         double  min, max;
 140 };
 141
 142 struct ibound {
 143         int     min, max;
 144 };
 145
 146 #define boundedLe(value, bounds)\
 147         ((bounds).min <= (value) && (value) <= (bounds).max)
 148
 149 struct line {
 150         double  m, b;
 151         int     valid;
 152 };
 153
 154 #define intersectLine(y,line) (line.m * (y) + line.b)
 155
 156 /*
 157  * these are all y value bounds
 158  */
 159
 160 struct arc_bound {
 161         struct bound    ellipse;
 162         struct bound    inner;
 163         struct bound    outer;
 164         struct bound    right;
 165         struct bound    left;
 166         struct ibound   inneri;
 167         struct ibound   outeri;
 168 };
 169
 170 struct accelerators {
 171         double          tail_y;
 172         double          h2;
 173         double          w2;
 174         double          h4;
 175         double          w4;
 176         double          h2mw2;
 177         double          h2l;
 178         double          w2l;
 179         double          fromIntX;
 180         double          fromIntY;
 181         struct line     left, right;
 182         int             yorgu;
 183         int             yorgl;
 184         int             xorg;
 185 };
 186
 187 struct arc_def {
 188         double  w, h, l;
 189         double  a0, a1;
 190 };
 191
 192 # define todeg(xAngle)  (((double) (xAngle)) / 64.0)
 193
 194 # define RIGHT_END      0
 195 # define LEFT_END       1
 196
 197 typedef struct _miArcJoin {
 198         int     arcIndex0, arcIndex1;
 199         int     phase0, phase1;
 200         int     end0, end1;
 201 } miArcJoinRec, *miArcJoinPtr;
 202
 203 typedef struct _miArcCap {
 204         int             arcIndex;
 205         int             end;
 206 } miArcCapRec, *miArcCapPtr;
 207
 208 typedef struct _miArcFace {
 209         SppPointRec     clock;
 210         SppPointRec     center;
 211         SppPointRec     counterClock;
 212 } miArcFaceRec, *miArcFacePtr;
 213
 214 typedef struct _miArcData {
 215         xArc            arc;
 216         int             render;         /* non-zero means render after drawing */
 217         int             join;           /* related join */
 218         int             cap;            /* related cap */
 219         int             selfJoin;       /* final dash meets first dash */
 220         miArcFaceRec    bounds[2];
 221         double          x0, y0, x1, y1;
 222 } miArcDataRec, *miArcDataPtr;
 223
 224 /*
 225  * This is an entire sequence of arcs, computed and categorized according
 226  * to operation.  miDashArcs generates either one or two of these.
 227  */
 228
 229 typedef struct _miPolyArc {
 230         int             narcs;
 231         miArcDataPtr    arcs;
 232         int             ncaps;
 233         miArcCapPtr     caps;
 234         int             njoins;
 235         miArcJoinPtr    joins;
 236 } miPolyArcRec, *miPolyArcPtr;
 237
 238 #define GCValsFunction          0
 239 #define GCValsForeground        1
 240 #define GCValsBackground        2
 241 #define GCValsLineWidth         3
 242 #define GCValsCapStyle          4
 243 #define GCValsJoinStyle         5
 244 #define GCValsMask              (GCFunction | GCForeground | GCBackground | \
 245                                  GCLineWidth | GCCapStyle | GCJoinStyle)
 246 static CARD32 gcvals[6];
 247
 248 static void fillSpans(), newFinalSpan();
 249 static void drawArc(), drawQuadrant(), drawZeroArc();
 250 static void miArcJoin(), miArcCap(), miRoundCap(), miFreeArcs();
 251 static int computeAngleFromPath();
 252 static miPolyArcPtr miComputeArcs ();
 253 static int miGetArcPts();
 254
 255 # define CUBED_ROOT_2   1.2599210498948732038115849718451499938964
 256 # define CUBED_ROOT_4   1.5874010519681993173435330390930175781250
 257
 258 /*
 259  * draw one segment of the arc using the arc spans generation routines
 260  */
 261
 262 static void
 263 miArcSegment(pDraw, pGC, tarc, right, left)
 264     DrawablePtr   pDraw;
 265     GCPtr         pGC;
 266     xArc          tarc;
 267     miArcFacePtr        right, left;
 268 {
 269     int l = pGC->lineWidth;
 270     int a0, a1, startAngle, endAngle;
 271     miArcFacePtr        temp;
 272
 273     if (!l)
 274         l = 1;
 275
 276     if (tarc.width == 0 || tarc.height == 0) {
 277         drawZeroArc (pDraw, pGC, &tarc, l, left, right);
 278         return;
 279     }
 280
 281     if (pGC->miTranslate) {
 282         tarc.x += pDraw->x;
 283         tarc.y += pDraw->y;
 284     }
 285
 286     a0 = tarc.angle1;
 287     a1 = tarc.angle2;
 288     if (a1 > FULLCIRCLE)
 289         a1 = FULLCIRCLE;
 290     else if (a1 < -FULLCIRCLE)
 291         a1 = -FULLCIRCLE;
 292     if (a1 < 0) {
 293         startAngle = a0 + a1;
 294         endAngle = a0;
 295         temp = right;
 296         right = left;
 297         left = temp;
 298     } else {
 299         startAngle = a0;
 300         endAngle = a0 + a1;
 301     }
 302     /*
 303      * bounds check the two angles
 304      */
 305     if (startAngle < 0)
 306         startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
 307     if (startAngle >= FULLCIRCLE)
 308         startAngle = startAngle % FULLCIRCLE;
 309     if (endAngle < 0)
 310         endAngle = FULLCIRCLE - (-endAngle) % FULLCIRCLE;
 311     if (endAngle > FULLCIRCLE)
 312         endAngle = (endAngle-1) % FULLCIRCLE + 1;
 313     if ((startAngle == endAngle) && a1) {
 314         startAngle = 0;
 315         endAngle = FULLCIRCLE;
 316     }
 317
 318     drawArc (&tarc, l, startAngle, endAngle, right, left);
 319 }
 320
 321 /*
 322
 323 Three equations combine to describe the boundaries of the arc
 324
 325 x^2/w^2 + y^2/h^2 = 1                   ellipse itself
 326 (X-x)^2 + (Y-y)^2 = r^2                 circle at (x, y) on the ellipse
 327 (Y-y) = (X-x)*w^2*y/(h^2*x)             normal at (x, y) on the ellipse
 328
 329 These lead to a quartic relating Y and y
 330
 331 y^4 - (2Y)y^3 + (Y^2 + (h^4 - w^2*r^2)/(w^2 - h^2))y^2
 332     - (2Y*h^4/(w^2 - h^2))y + (Y^2*h^4)/(w^2 - h^2) = 0
 333
 334 The reducible cubic obtained from this quartic is
 335
 336 z^3 - (3N)z^2 - 2V = 0
 337
 338 where
 339
 340 N = (Y^2 + (h^4 - w^2*r^2/(w^2 - h^2)))/6
 341 V = w^2*r^2*Y^2*h^4/(4 *(w^2 - h^2)^2)
 342
 343 Let
 344
 345 t = z - N
 346 p = -N^2
 347 q = -N^3 - V
 348
 349 Then we get
 350
 351 t^3 + 3pt + 2q = 0
 352
 353 The discriminant of this cubic is
 354
 355 D = q^2 + p^3
 356
 357 When D > 0, a real root is obtained as
 358
 359 z = N + cbrt(-q+sqrt(D)) + cbrt(-q-sqrt(D))
 360
 361 When D < 0, a real root is obtained as
 362
 363 z = N - 2m*cos(acos(-q/m^3)/3)
 364
 365 where
 366
 367 m = sqrt(|p|) * sign(q)
 368
 369 Given a real root Z of the cubic, the roots of the quartic are the roots
 370 of the two quadratics
 371
 372 y^2 + ((b+A)/2)y + (Z + (bZ - d)/A) = 0
 373
 374 where
 375
 376 A = +/- sqrt(8Z + b^2 - 4c)
 377 b, c, d are the cubic, quadratic, and linear coefficients of the quartic
 378
 379 Some experimentation is then required to determine which solutions
 380 correspond to the inner and outer boundaries.
 381
 382 */
 383
 384 typedef struct {
 385     short lx, lw, rx, rw;
 386 } miArcSpan;
 387
 388 typedef struct {
 389     miArcSpan *spans;
 390     int count1, count2, k;
 391     char top, bot, hole;
 392 } miArcSpanData;
 393
 394 typedef struct {
 395     unsigned long lrustamp;
 396     unsigned short lw;
 397     unsigned short width, height;
 398     miArcSpanData *spdata;
 399 } arcCacheRec;
 400
 401 #define CACHESIZE 25
 402
 403 static arcCacheRec arcCache[CACHESIZE];
 404 static unsigned long lrustamp;
 405 static arcCacheRec *lastCacheHit = &arcCache[0];
 406 static RESTYPE cacheType;
 407
 408 /*
 409  * External so it can be called when low on memory.
 410  * Call with a zero ID in that case.
 411  */
 412 /*ARGSUSED*/
 413 int
 414 miFreeArcCache (data, id)
 415     pointer         data;
 416     XID             id;
 417 {
 418     int k;
 419     arcCacheRec *cent;
 420
 421     if (id)
 422         cacheType = 0;
 423
 424     for (k = CACHESIZE, cent = &arcCache[0]; --k >= 0; cent++)
 425     {
 426         if (cent->spdata)
 427         {
 428             cent->lrustamp = 0;
 429             cent->lw = 0;
 430             xfree(cent->spdata);
 431             cent->spdata = NULL;
 432         }
 433     }
 434     lrustamp = 0;
 435     return Success;
 436 }
 437
 438 static void
 439 miComputeCircleSpans(lw, parc, spdata)
 440     int lw;
 441     xArc *parc;
 442     miArcSpanData *spdata;
 443 {
 444     register miArcSpan *span;
 445     int doinner;
 446     register int x, y, e;
 447     int xk, yk, xm, ym, dx, dy;
 448     register int slw, inslw;
 449     int inx, iny, ine;
 450     int inxk, inyk, inxm, inym;
 451
 452     doinner = -lw;
 453     slw = parc->width - doinner;
 454     y = parc->height >> 1;
 455     dy = parc->height & 1;
 456     dx = 1 - dy;
 457     MIWIDEARCSETUP(x, y, dy, slw, e, xk, xm, yk, ym);
 458     inslw = parc->width + doinner;
 459     if (inslw > 0)
 460     {
 461         spdata->hole = spdata->top;
 462         MIWIDEARCSETUP(inx, iny, dy, inslw, ine, inxk, inxm, inyk, inym);
 463     }
 464     else
 465     {
 466         spdata->hole = FALSE;
 467         doinner = -y;
 468     }
 469     spdata->count1 = -doinner - spdata->top;
 470     spdata->count2 = y + doinner;
 471     span = spdata->spans;
 472     while (y)
 473     {
 474         MIFILLARCSTEP(slw);
 475         span->lx = dy - x;
 476         if (++doinner <= 0)
 477         {
 478             span->lw = slw;
 479             span->rx = 0;
 480             span->rw = span->lx + slw;
 481         }
 482         else
 483         {
 484             MIFILLINARCSTEP(inslw);
 485             span->lw = x - inx;
 486             span->rx = dy - inx + inslw;
 487             span->rw = inx - x + slw - inslw;
 488         }
 489         span++;
 490     }
 491     if (spdata->bot)
 492     {
 493         if (spdata->count2)
 494             spdata->count2--;
 495         else
 496         {
 497             if (lw > (int)parc->height)
 498                 span[-1].rx = span[-1].rw = -((lw - (int)parc->height) >> 1);
 499             else
 500                 span[-1].rw = 0;
 501             spdata->count1--;
 502         }
 503     }
 504 }
 505
 506 static void
 507 miComputeEllipseSpans(lw, parc, spdata)
 508     int lw;
 509     xArc *parc;
 510     miArcSpanData *spdata;
 511 {
 512     register miArcSpan *span;
 513     double w, h, r, xorg;
 514     double Hs, Hf, WH, K, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
 515     double A, T, b, d, x, y, t, inx, outx, hepp, hepm;
 516     int flip, solution;
 517
 518     w = (double)parc->width / 2.0;
 519     h = (double)parc->height / 2.0;
 520     r = lw / 2.0;
 521     rs = r * r;
 522     Hs = h * h;
 523     WH = w * w - Hs;
 524     Nk = w * r;
 525     Vk = (Nk * Hs) / (WH + WH);
 526     Hf = Hs * Hs;
 527     Nk = (Hf - Nk * Nk) / WH;
 528     Fk = Hf / WH;
 529     hepp = h + EPSILON;
 530     hepm = h - EPSILON;
 531     K = h + ((lw - 1) >> 1);
 532     span = spdata->spans;
 533     if (parc->width & 1)
 534         xorg = .5;
 535     else
 536         xorg = 0.0;
 537     if (spdata->top)
 538     {
 539         span->lx = 0;
 540         span->lw = 1;
 541         span++;
 542     }
 543     spdata->count1 = 0;
 544     spdata->count2 = 0;
 545     spdata->hole = (spdata->top &&
 546                  (int)parc->height * lw <= (int)(parc->width * parc->width) &&
 547                     lw < (int)parc->height);
 548     for (; K > 0.0; K -= 1.0)
 549     {
 550         N = (K * K + Nk) / 6.0;
 551         Nc = N * N * N;
 552         Vr = Vk * K;
 553         t = Nc + Vr * Vr;
 554         d = Nc + t;
 555         if (d < 0.0) {
 556             d = Nc;
 557             b = N;
 558             if ( (b < 0.0) == (t < 0.0) )
 559             {
 560                 b = -b;
 561                 d = -d;
 562             }
 563             Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
 564             if ( (Z < 0.0) == (Vr < 0.0) )
 565                 flip = 2;
 566             else
 567                 flip = 1;
 568         }
 569         else
 570         {
 571             d = Vr * sqrt(d);
 572             Z = N + cbrt(t + d) + cbrt(t - d);
 573             flip = 0;
 574         }
 575         A = sqrt((Z + Z) - Nk);
 576         T = (Fk - Z) * K / A;
 577         inx = 0.0;
 578         solution = FALSE;
 579         b = -A + K;
 580         d = b * b - 4 * (Z + T);
 581         if (d >= 0)
 582         {
 583             d = sqrt(d);
 584             y = (b + d) / 2;
 585             if ((y >= 0.0) && (y < hepp))
 586             {
 587                 solution = TRUE;
 588                 if (y > hepm)
 589                     y = h;
 590                 t = y / h;
 591                 x = w * sqrt(1 - (t * t));
 592                 t = K - y;
 593                 if (rs - (t * t) >= 0)
 594                    t = sqrt(rs - (t * t));
 595                 else
 596                    t = 0;
 597                 if (flip == 2)
 598                     inx = x - t;
 599                 else
 600                     outx = x + t;
 601             }
 602         }
 603         b = A + K;
 604         d = b * b - 4 * (Z - T);
 605         /* Because of the large magnitudes involved, we lose enough precision
 606          * that sometimes we end up with a negative value near the axis, when
 607          * it should be positive.  This is a workaround.
 608          */
 609         if (d < 0 && !solution)
 610             d = 0.0;
 611         if (d >= 0) {
 612             d = sqrt(d);
 613             y = (b + d) / 2;
 614             if (y < hepp)
 615             {
 616                 if (y > hepm)
 617                     y = h;
 618                 t = y / h;
 619                 x = w * sqrt(1 - (t * t));
 620                 t = K - y;
 621                 if (rs - (t * t) >= 0)
 622                    inx = x - sqrt(rs - (t * t));
 623                 else
 624                    inx = x;
 625             }
 626             y = (b - d) / 2;
 627             if (y >= 0.0)
 628             {
 629                 if (y > hepm)
 630                     y = h;
 631                 t = y / h;
 632                 x = w * sqrt(1 - (t * t));
 633                 t = K - y;
 634                 if (rs - (t * t) >= 0)
 635                    t = sqrt(rs - (t * t));
 636                 else
 637                    t = 0;
 638                 if (flip == 1)
 639                     inx = x - t;
 640                 else
 641                     outx = x + t;
 642             }
 643         }
 644         span->lx = ICEIL(xorg - outx);
 645         if (inx <= 0.0)
 646         {
 647             spdata->count1++;
 648             span->lw = ICEIL(xorg + outx) - span->lx;
 649             span->rx = ICEIL(xorg + inx);
 650             span->rw = -ICEIL(xorg - inx);
 651         }
 652         else
 653         {
 654             spdata->count2++;
 655             span->lw = ICEIL(xorg - inx) - span->lx;
 656             span->rx = ICEIL(xorg + inx);
 657             span->rw = ICEIL(xorg + outx) - span->rx;
 658         }
 659         span++;
 660     }
 661     if (spdata->bot)
 662     {
 663         outx = w + r;
 664         if (r >= h && r <= w)
 665             inx = 0.0;
 666         else if (Nk < 0.0 && -Nk < Hs)
 667         {
 668             inx = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
 669             if (inx > w - r)
 670                 inx = w - r;
 671         }
 672         else
 673             inx = w - r;
 674         span->lx = ICEIL(xorg - outx);
 675         if (inx <= 0.0)
 676         {
 677             span->lw = ICEIL(xorg + outx) - span->lx;
 678             span->rx = ICEIL(xorg + inx);
 679             span->rw = -ICEIL(xorg - inx);
 680         }
 681         else
 682         {
 683             span->lw = ICEIL(xorg - inx) - span->lx;
 684             span->rx = ICEIL(xorg + inx);
 685             span->rw = ICEIL(xorg + outx) - span->rx;
 686         }
 687     }
 688     if (spdata->hole)
 689     {
 690         span = &spdata->spans[spdata->count1];
 691         span->lw = -span->lx;
 692         span->rx = 1;
 693         span->rw = span->lw;
 694         spdata->count1--;
 695         spdata->count2++;
 696     }
 697 }
 698
 699 static double
 700 tailX(K, def, bounds, acc)
 701     double K;
 702     struct arc_def *def;
 703     struct arc_bound *bounds;
 704     struct accelerators *acc;
 705 {
 706     double w, h, r;
 707     double Hs, Hf, WH, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
 708     double A, T, b, d, x, y, t, hepp, hepm;
 709     int flip, solution;
 710     double xs[2];
 711     double *xp;
 712
 713     w = def->w;
 714     h = def->h;
 715     r = def->l;
 716     rs = r * r;
 717     Hs = acc->h2;
 718     WH = -acc->h2mw2;
 719     Nk = def->w * r;
 720     Vk = (Nk * Hs) / (WH + WH);
 721     Hf = acc->h4;
 722     Nk = (Hf - Nk * Nk) / WH;
 723     if (K == 0.0) {
 724         if (Nk < 0.0 && -Nk < Hs) {
 725             xs[0] = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
 726             xs[1] = w - r;
 727             if (acc->left.valid && boundedLe(K, bounds->left) &&
 728                 !boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
 729                 return xs[1];
 730             if (acc->right.valid && boundedLe(K, bounds->right) &&
 731                 !boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
 732                 return xs[1];
 733             return xs[0];
 734         }
 735         return w - r;
 736     }
 737     Fk = Hf / WH;
 738     hepp = h + EPSILON;
 739     hepm = h - EPSILON;
 740     N = (K * K + Nk) / 6.0;
 741     Nc = N * N * N;
 742     Vr = Vk * K;
 743     xp = xs;
 744     xs[0] = 0.0;
 745     t = Nc + Vr * Vr;
 746     d = Nc + t;
 747     if (d < 0.0) {
 748         d = Nc;
 749         b = N;
 750         if ( (b < 0.0) == (t < 0.0) )
 751         {
 752             b = -b;
 753             d = -d;
 754         }
 755         Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
 756         if ( (Z < 0.0) == (Vr < 0.0) )
 757             flip = 2;
 758         else
 759             flip = 1;
 760     }
 761     else
 762     {
 763         d = Vr * sqrt(d);
 764         Z = N + cbrt(t + d) + cbrt(t - d);
 765         flip = 0;
 766     }
 767     A = sqrt((Z + Z) - Nk);
 768     T = (Fk - Z) * K / A;
 769     solution = FALSE;
 770     b = -A + K;
 771     d = b * b - 4 * (Z + T);
 772     if (d >= 0 && flip == 2)
 773     {
 774         d = sqrt(d);
 775         y = (b + d) / 2;
 776         if ((y >= 0.0) && (y < hepp))
 777         {
 778             solution = TRUE;
 779             if (y > hepm)
 780                 y = h;
 781             t = y / h;
 782             x = w * sqrt(1 - (t * t));
 783             t = K - y;
 784             if (rs - (t * t) >= 0)
 785                t = sqrt(rs - (t * t));
 786             else
 787                t = 0;
 788             *xp++ = x - t;
 789         }
 790     }
 791     b = A + K;
 792     d = b * b - 4 * (Z - T);
 793     /* Because of the large magnitudes involved, we lose enough precision
 794      * that sometimes we end up with a negative value near the axis, when
 795      * it should be positive.  This is a workaround.
 796      */
 797     if (d < 0 && !solution)
 798         d = 0.0;
 799     if (d >= 0) {
 800         d = sqrt(d);
 801         y = (b + d) / 2;
 802         if (y < hepp)
 803         {
 804             if (y > hepm)
 805                 y = h;
 806             t = y / h;
 807             x = w * sqrt(1 - (t * t));
 808             t = K - y;
 809             if (rs - (t * t) >= 0)
 810                *xp++ = x - sqrt(rs - (t * t));
 811             else
 812                *xp++ = x;
 813         }
 814         y = (b - d) / 2;
 815         if (y >= 0.0 && flip == 1)
 816         {
 817             if (y > hepm)
 818                 y = h;
 819             t = y / h;
 820             x = w * sqrt(1 - (t * t));
 821             t = K - y;
 822             if (rs - (t * t) >= 0)
 823                t = sqrt(rs - (t * t));
 824             else
 825                t = 0;
 826             *xp++ = x - t;
 827         }
 828     }
 829     if (xp > &xs[1]) {
 830         if (acc->left.valid && boundedLe(K, bounds->left) &&
 831             !boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
 832             return xs[1];
 833         if (acc->right.valid && boundedLe(K, bounds->right) &&
 834             !boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
 835             return xs[1];
 836     }
 837     return xs[0];
 838 }
 839
 840 static miArcSpanData *
 841 miComputeWideEllipse(lw, parc, mustFree)
 842     int            lw;
 843     register xArc *parc;
 844     Bool          *mustFree;
 845 {
 846     register miArcSpanData *spdata;
 847     register arcCacheRec *cent, *lruent;
 848     register int k;
 849     arcCacheRec fakeent;
 850
 851     if (!lw)
 852         lw = 1;
 853     if (parc->height <= 1500)
 854     {
 855         *mustFree = FALSE;
 856         cent = lastCacheHit;
 857         if (cent->lw == lw &&
 858             cent->width == parc->width && cent->height == parc->height)
 859         {
 860             cent->lrustamp = ++lrustamp;
 861             return cent->spdata;
 862         }
 863         lruent = &arcCache[0];
 864         for (k = CACHESIZE, cent = lruent; --k >= 0; cent++)
 865         {
 866             if (cent->lw == lw &&
 867                 cent->width == parc->width && cent->height == parc->height)
 868             {
 869                 cent->lrustamp = ++lrustamp;
 870                 lastCacheHit = cent;
 871                 return cent->spdata;
 872             }
 873             if (cent->lrustamp < lruent->lrustamp)
 874                 lruent = cent;
 875         }
 876         if (!cacheType)
 877         {
 878             cacheType = CreateNewResourceType(miFreeArcCache);
 879             (void) AddResource(FakeClientID(0), cacheType, NULL);
 880         }
 881     } else {
 882         lruent = &fakeent;
 883         lruent->spdata = NULL;
 884         *mustFree = TRUE;
 885     }
 886     k = (parc->height >> 1) + ((lw - 1) >> 1);
 887     spdata = lruent->spdata;
 888     if (!spdata || spdata->k != k)
 889     {
 890         if (spdata)
 891             xfree(spdata);
 892         spdata = (miArcSpanData *)xalloc(sizeof(miArcSpanData) +
 893                                          sizeof(miArcSpan) * (k + 2));
 894         lruent->spdata = spdata;
 895         if (!spdata)
 896         {
 897             lruent->lrustamp = 0;
 898             lruent->lw = 0;
 899             return spdata;
 900         }
 901         spdata->spans = (miArcSpan *)(spdata + 1);
 902         spdata->k = k;
 903     }
 904     spdata->top = !(lw & 1) && !(parc->width & 1);
 905     spdata->bot = !(parc->height & 1);
 906     lruent->lrustamp = ++lrustamp;
 907     lruent->lw = lw;
 908     lruent->width = parc->width;
 909     lruent->height = parc->height;
 910     if (lruent != &fakeent)
 911         lastCacheHit = lruent;
 912     if (parc->width == parc->height)
 913         miComputeCircleSpans(lw, parc, spdata);
 914     else
 915         miComputeEllipseSpans(lw, parc, spdata);
 916     return spdata;
 917 }
 918
 919 static void
 920 miFillWideEllipse(pDraw, pGC, parc)
 921     DrawablePtr pDraw;
 922     GCPtr       pGC;
 923     xArc        *parc;
 924 {
 925     DDXPointPtr points;
 926     register DDXPointPtr pts;
 927     int *widths;
 928     register int *wids;
 929     miArcSpanData *spdata;
 930     Bool mustFree;
 931     register miArcSpan *span;
 932     register int xorg, yorgu, yorgl;
 933     register int n;
 934
 935     yorgu = parc->height + pGC->lineWidth;
 936     n = (sizeof(int) * 2) * yorgu;
 937     widths = (int *)ALLOCATE_LOCAL(n + (sizeof(DDXPointRec) * 2) * yorgu);
 938     if (!widths)
 939         return;
 940     points = (DDXPointPtr)((char *)widths + n);
 941     spdata = miComputeWideEllipse((int)pGC->lineWidth, parc, &mustFree);
 942     if (!spdata)
 943     {
 944         DEALLOCATE_LOCAL(widths);
 945         return;
 946     }
 947     pts = points;
 948     wids = widths;
 949     span = spdata->spans;
 950     xorg = parc->x + (parc->width >> 1);
 951     yorgu = parc->y + (parc->height >> 1);
 952     yorgl = yorgu + (parc->height & 1);
 953     if (pGC->miTranslate)
 954     {
 955         xorg += pDraw->x;
 956         yorgu += pDraw->y;
 957         yorgl += pDraw->y;
 958     }
 959     yorgu -= spdata->k;
 960     yorgl += spdata->k;
 961     if (spdata->top)
 962     {
 963         pts->x = xorg;
 964         pts->y = yorgu - 1;
 965         pts++;
 966         *wids++ = 1;
 967         span++;
 968     }
 969     for (n = spdata->count1; --n >= 0; )
 970     {
 971         pts[0].x = xorg + span->lx;
 972         pts[0].y = yorgu;
 973         wids[0] = span->lw;
 974         pts[1].x = pts[0].x;
 975         pts[1].y = yorgl;
 976         wids[1] = wids[0];
 977         yorgu++;
 978         yorgl--;
 979         pts += 2;
 980         wids += 2;
 981         span++;
 982     }
 983     if (spdata->hole)
 984     {
 985         pts[0].x = xorg;
 986         pts[0].y = yorgl;
 987         wids[0] = 1;
 988         pts++;
 989         wids++;
 990     }
 991     for (n = spdata->count2; --n >= 0; )
 992     {
 993         pts[0].x = xorg + span->lx;
 994         pts[0].y = yorgu;
 995         wids[0] = span->lw;
 996         pts[1].x = xorg + span->rx;
 997         pts[1].y = pts[0].y;
 998         wids[1] = span->rw;
 999         pts[2].x = pts[0].x;
1000         pts[2].y = yorgl;
1001         wids[2] = wids[0];
1002         pts[3].x = pts[1].x;
1003         pts[3].y = pts[2].y;
1004         wids[3] = wids[1];
1005         yorgu++;
1006         yorgl--;
1007         pts += 4;
1008         wids += 4;
1009         span++;
1010     }
1011     if (spdata->bot)
1012     {
1013         if (span->rw <= 0)
1014         {
1015             pts[0].x = xorg + span->lx;
1016             pts[0].y = yorgu;
1017             wids[0] = span->lw;
1018             pts++;
1019             wids++;
1020         }
1021         else
1022         {
1023             pts[0].x = xorg + span->lx;
1024             pts[0].y = yorgu;
1025             wids[0] = span->lw;
1026             pts[1].x = xorg + span->rx;
1027             pts[1].y = pts[0].y;
1028             wids[1] = span->rw;
1029             pts += 2;
1030             wids += 2;
1031         }
1032     }
1033     if (mustFree)
1034         xfree(spdata);
1035     (*pGC->ops->FillSpans)(pDraw, pGC, pts - points, points, widths, FALSE);
1036
1037     DEALLOCATE_LOCAL(widths);
1038 }
1039
1040 /*
1041  * miPolyArc strategy:
1042  *
1043  * If arc is zero width and solid, we don't have to worry about the rasterop
1044  * or join styles.  For wide solid circles, we use a fast integer algorithm.
1045  * For wide solid ellipses, we use special case floating point code.
1046  * Otherwise, we set up pDrawTo and pGCTo according to the rasterop, then
1047  * draw using pGCTo and pDrawTo.  If the raster-op was "tricky," that is,
1048  * if it involves the destination, then we use PushPixels to move the bits
1049  * from the scratch drawable to pDraw. (See the wide line code for a
1050  * fuller explanation of this.)
1051  */
1052
1053 void
1054 miPolyArc(pDraw, pGC, narcs, parcs)
1055     DrawablePtr pDraw;
1056     GCPtr       pGC;
1057     int         narcs;
1058     xArc        *parcs;
1059 {
1060     register int                i;
1061     xArc                        *parc;
1062     int                         xMin, xMax, yMin, yMax;
1063     int                         pixmapWidth, pixmapHeight;
1064     int                         xOrg, yOrg;
1065     int                         width;
1066     Bool                        fTricky;
1067     DrawablePtr                 pDrawTo;
1068     CARD32                      fg, bg;
1069     GCPtr                       pGCTo;
1070     miPolyArcPtr                polyArcs;
1071     int                         cap[2], join[2];
1072     int                         iphase;
1073     int                         halfWidth;
1074
1075     width = pGC->lineWidth;
1076     if(width == 0 && pGC->lineStyle == LineSolid)
1077     {
1078         for(i = narcs, parc = parcs; --i >= 0; parc++)
1079             miArcSegment( pDraw, pGC, *parc,
1080             (miArcFacePtr) 0, (miArcFacePtr) 0 );
1081         fillSpans (pDraw, pGC);
1082     }
1083     else
1084     {
1085         if ((pGC->lineStyle == LineSolid) && narcs)
1086         {
1087             while (parcs->width && parcs->height &&
1088                    (parcs->angle2 >= FULLCIRCLE ||
1089                     parcs->angle2 <= -FULLCIRCLE))
1090             {
1091                 miFillWideEllipse(pDraw, pGC, parcs);
1092                 if (!--narcs)
1093                     return;
1094                 parcs++;
1095             }
1096         }
1097
1098         /* Set up pDrawTo and pGCTo based on the rasterop */
1099         switch(pGC->alu)
1100         {
1101           case GXclear:         /* 0 */
1102           case GXcopy:          /* src */
1103           case GXcopyInverted:  /* NOT src */
1104           case GXset:           /* 1 */
1105             fTricky = FALSE;
1106             pDrawTo = pDraw;
1107             pGCTo = pGC;
1108             break;
1109           default:
1110             fTricky = TRUE;
1111
1112             /* find bounding box around arcs */
1113             xMin = yMin = MAXSHORT;
1114             xMax = yMax = MINSHORT;
1115
1116             for(i = narcs, parc = parcs; --i >= 0; parc++)
1117             {
1118                 xMin = min (xMin, parc->x);
1119                 yMin = min (yMin, parc->y);
1120                 xMax = max (xMax, (parc->x + (int) parc->width));
1121                 yMax = max (yMax, (parc->y + (int) parc->height));
1122             }
1123
1124             /* expand box to deal with line widths */
1125             halfWidth = (width + 1)/2;
1126             xMin -= halfWidth;
1127             yMin -= halfWidth;
1128             xMax += halfWidth;
1129             yMax += halfWidth;
1130
1131             /* compute pixmap size; limit it to size of drawable */
1132             xOrg = max(xMin, 0);
1133             yOrg = max(yMin, 0);
1134             pixmapWidth = min(xMax, pDraw->width) - xOrg;
1135             pixmapHeight = min(yMax, pDraw->height) - yOrg;
1136
1137             /* if nothing left, return */
1138             if ( (pixmapWidth <= 0) || (pixmapHeight <= 0) ) return;
1139
1140             for(i = narcs, parc = parcs; --i >= 0; parc++)
1141             {
1142                 parc->x -= xOrg;
1143                 parc->y -= yOrg;
1144             }
1145             if (pGC->miTranslate)
1146             {
1147                 xOrg += pDraw->x;
1148                 yOrg += pDraw->y;
1149             }
1150
1151             /* set up scratch GC */
1152
1153             pGCTo = GetScratchGC(1, pDraw->pScreen);
1154             if (!pGCTo)
1155                 return;
1156             gcvals[GCValsFunction] = GXcopy;
1157             gcvals[GCValsForeground] = 1;
1158             gcvals[GCValsBackground] = 0;
1159             gcvals[GCValsLineWidth] = pGC->lineWidth;
1160             gcvals[GCValsCapStyle] = pGC->capStyle;
1161             gcvals[GCValsJoinStyle] = pGC->joinStyle;
1162             dixChangeGC(NullClient, pGCTo, GCValsMask, gcvals, NULL);
1163
1164             /* allocate a 1 bit deep pixmap of the appropriate size, and
1165              * validate it */
1166             pDrawTo = (DrawablePtr)(*pDraw->pScreen->CreatePixmap)
1167                                 (pDraw->pScreen, pixmapWidth, pixmapHeight, 1);
1168             if (!pDrawTo)
1169             {
1170                 FreeScratchGC(pGCTo);
1171                 return;
1172             }
1173             ValidateGC(pDrawTo, pGCTo);
1174             miClearDrawable(pDrawTo, pGCTo);
1175         }
1176
1177         fg = pGC->fgPixel;
1178         bg = pGC->bgPixel;
1179         if ((pGC->fillStyle == FillTiled) ||
1180             (pGC->fillStyle == FillOpaqueStippled))
1181             bg = fg; /* the protocol sez these don't cause color changes */
1182
1183         polyArcs = miComputeArcs (parcs, narcs, pGC);
1184
1185         if (!polyArcs)
1186         {
1187             if (fTricky) {
1188                 (*pDraw->pScreen->DestroyPixmap) ((PixmapPtr)pDrawTo);
1189                 FreeScratchGC (pGCTo);
1190             }
1191             return;
1192         }
1193
1194         cap[0] = cap[1] = 0;
1195         join[0] = join[1] = 0;
1196         for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);
1197              iphase >= 0;
1198              iphase--)
1199         {
1200             if (iphase == 1) {
1201                 dixChangeGC (NullClient, pGC, GCForeground, &bg, NULL);
1202                 ValidateGC (pDraw, pGC);
1203             } else if (pGC->lineStyle == LineDoubleDash) {
1204                 dixChangeGC (NullClient, pGC, GCForeground, &fg, NULL);
1205                 ValidateGC (pDraw, pGC);
1206             }
1207             for (i = 0; i < polyArcs[iphase].narcs; i++) {
1208                 miArcDataPtr    arcData;
1209
1210                 arcData = &polyArcs[iphase].arcs[i];
1211                 miArcSegment(pDrawTo, pGCTo, arcData->arc,
1212                              &arcData->bounds[RIGHT_END],
1213                              &arcData->bounds[LEFT_END]);
1214                 if (polyArcs[iphase].arcs[i].render) {
1215                     fillSpans (pDrawTo, pGCTo);
1216                     /*
1217                      * don't cap self-joining arcs
1218                      */
1219                     if (polyArcs[iphase].arcs[i].selfJoin &&
1220                         cap[iphase] < polyArcs[iphase].arcs[i].cap)
1221                         cap[iphase]++;
1222                     while (cap[iphase] < polyArcs[iphase].arcs[i].cap) {
1223                         int     arcIndex, end;
1224                         miArcDataPtr    arcData0;
1225
1226                         arcIndex = polyArcs[iphase].caps[cap[iphase]].arcIndex;
1227                         end = polyArcs[iphase].caps[cap[iphase]].end;
1228                         arcData0 = &polyArcs[iphase].arcs[arcIndex];
1229                         miArcCap (pDrawTo, pGCTo,
1230                                   &arcData0->bounds[end], end,
1231                                   arcData0->arc.x, arcData0->arc.y,
1232                                   (double) arcData0->arc.width / 2.0,
1233                                   (double) arcData0->arc.height / 2.0);
1234                         ++cap[iphase];
1235                     }
1236                     while (join[iphase] < polyArcs[iphase].arcs[i].join) {
1237                         int     arcIndex0, arcIndex1, end0, end1;
1238                         int     phase0, phase1;
1239                         miArcDataPtr    arcData0, arcData1;
1240                         miArcJoinPtr    joinp;
1241
1242                         joinp = &polyArcs[iphase].joins[join[iphase]];
1243                         arcIndex0 = joinp->arcIndex0;
1244                         end0 = joinp->end0;
1245                         arcIndex1 = joinp->arcIndex1;
1246                         end1 = joinp->end1;
1247                         phase0 = joinp->phase0;
1248                         phase1 = joinp->phase1;
1249                         arcData0 = &polyArcs[phase0].arcs[arcIndex0];
1250                         arcData1 = &polyArcs[phase1].arcs[arcIndex1];
1251                         miArcJoin (pDrawTo, pGCTo,
1252                                   &arcData0->bounds[end0],
1253                                   &arcData1->bounds[end1],
1254                                   arcData0->arc.x, arcData0->arc.y,
1255                                   (double) arcData0->arc.width / 2.0,
1256                                   (double) arcData0->arc.height / 2.0,
1257                                   arcData1->arc.x, arcData1->arc.y,
1258                                   (double) arcData1->arc.width / 2.0,
1259                                   (double) arcData1->arc.height / 2.0);
1260                         ++join[iphase];
1261                     }
1262                     if (fTricky) {
1263                         if (pGC->serialNumber != pDraw->serialNumber)
1264                             ValidateGC (pDraw, pGC);
1265                         (*pGC->ops->PushPixels) (pGC, (PixmapPtr)pDrawTo,
1266                                  pDraw, pixmapWidth, pixmapHeight, xOrg, yOrg);
1267                         miClearDrawable ((DrawablePtr) pDrawTo, pGCTo);
1268                     }
1269                 }
1270             }
1271         }
1272         miFreeArcs(polyArcs, pGC);
1273
1274         if(fTricky)
1275         {
1276             (*pGCTo->pScreen->DestroyPixmap)((PixmapPtr)pDrawTo);
1277             FreeScratchGC(pGCTo);
1278         }
1279     }
1280 }
1281
1282 static double
1283 angleBetween (center, point1, point2)
1284         SppPointRec     center, point1, point2;
1285 {
1286         double  a1, a2, a;
1287
1288         /*
1289          * reflect from X coordinates back to ellipse
1290          * coordinates -- y increasing upwards
1291          */
1292         a1 = miDatan2 (- (point1.y - center.y), point1.x - center.x);
1293         a2 = miDatan2 (- (point2.y - center.y), point2.x - center.x);
1294         a = a2 - a1;
1295         if (a <= -180.0)
1296                 a += 360.0;
1297         else if (a > 180.0)
1298                 a -= 360.0;
1299         return a;
1300 }
1301
1302 static void
1303 translateBounds (b, x, y, fx, fy)
1304 miArcFacePtr    b;
1305 int             x, y;
1306 double          fx, fy;
1307 {
1308         fx += x;
1309         fy += y;
1310         b->clock.x -= fx;
1311         b->clock.y -= fy;
1312         b->center.x -= fx;
1313         b->center.y -= fy;
1314         b->counterClock.x -= fx;
1315         b->counterClock.y -= fy;
1316 }
1317
1318 static void
1319 miArcJoin (pDraw, pGC, pLeft, pRight,
1320            xOrgLeft, yOrgLeft, xFtransLeft, yFtransLeft,
1321            xOrgRight, yOrgRight, xFtransRight, yFtransRight)
1322         DrawablePtr     pDraw;
1323         GCPtr           pGC;
1324         miArcFacePtr    pRight, pLeft;
1325         int             xOrgRight, yOrgRight;
1326         double          xFtransRight, yFtransRight;
1327         int             xOrgLeft, yOrgLeft;
1328         double          xFtransLeft, yFtransLeft;
1329 {
1330         SppPointRec     center, corner, otherCorner;
1331         SppPointRec     poly[5], e;
1332         SppPointPtr     pArcPts;
1333         int             cpt;
1334         SppArcRec       arc;
1335         miArcFaceRec    Right, Left;
1336         int             polyLen;
1337         int             xOrg, yOrg;
1338         double          xFtrans, yFtrans;
1339         double          a;
1340         double          ae, ac2, ec2, bc2, de;
1341         double          width;
1342
1343         xOrg = (xOrgRight + xOrgLeft) / 2;
1344         yOrg = (yOrgRight + yOrgLeft) / 2;
1345         xFtrans = (xFtransLeft + xFtransRight) / 2;
1346         yFtrans = (yFtransLeft + yFtransRight) / 2;
1347         Right = *pRight;
1348         translateBounds (&Right, xOrg - xOrgRight, yOrg - yOrgRight,
1349                                  xFtrans - xFtransRight, yFtrans - yFtransRight);
1350         Left = *pLeft;
1351         translateBounds (&Left, xOrg - xOrgLeft, yOrg - yOrgLeft,
1352                                  xFtrans - xFtransLeft, yFtrans - yFtransLeft);
1353         pRight = &Right;
1354         pLeft = &Left;
1355
1356         if (pRight->clock.x == pLeft->counterClock.x &&
1357             pRight->clock.y == pLeft->counterClock.y)
1358                 return;
1359         center = pRight->center;
1360         if (0 <= (a = angleBetween (center, pRight->clock, pLeft->counterClock))
1361             && a <= 180.0)
1362         {
1363                 corner = pRight->clock;
1364                 otherCorner = pLeft->counterClock;
1365         } else {
1366                 a = angleBetween (center, pLeft->clock, pRight->counterClock);
1367                 corner = pLeft->clock;
1368                 otherCorner = pRight->counterClock;
1369         }
1370         switch (pGC->joinStyle) {
1371         case JoinRound:
1372                 width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);
1373
1374                 arc.x = center.x - width/2;
1375                 arc.y = center.y - width/2;
1376                 arc.width = width;
1377                 arc.height = width;
1378                 arc.angle1 = -miDatan2 (corner.y - center.y, corner.x - center.x);
1379                 arc.angle2 = a;
1380                 pArcPts = (SppPointPtr) xalloc (3 * sizeof (SppPointRec));
1381                 if (!pArcPts)
1382                     return;
1383                 pArcPts[0].x = otherCorner.x;
1384                 pArcPts[0].y = otherCorner.y;
1385                 pArcPts[1].x = center.x;
1386                 pArcPts[1].y = center.y;
1387                 pArcPts[2].x = corner.x;
1388                 pArcPts[2].y = corner.y;
1389                 if( (cpt = miGetArcPts(&arc, 3, &pArcPts)) )
1390                 {
1391                         /* by drawing with miFillSppPoly and setting the endpoints of the arc
1392                          * to be the corners, we assure that the cap will meet up with the
1393                          * rest of the line */
1394                         miFillSppPoly(pDraw, pGC, cpt, pArcPts, xOrg, yOrg, xFtrans, yFtrans);
1395                 }
1396                 xfree(pArcPts);
1397                 return;
1398         case JoinMiter:
1399                 /*
1400                  * don't miter arcs with less than 11 degrees between them
1401                  */
1402                 if (a < 169.0) {
1403                         poly[0] = corner;
1404                         poly[1] = center;
1405                         poly[2] = otherCorner;
1406                         bc2 = (corner.x - otherCorner.x) * (corner.x - otherCorner.x) +
1407                               (corner.y - otherCorner.y) * (corner.y - otherCorner.y);
1408                         ec2 = bc2 / 4;
1409                         ac2 = (corner.x - center.x) * (corner.x - center.x) +
1410                               (corner.y - center.y) * (corner.y - center.y);
1411                         ae = sqrt (ac2 - ec2);
1412                         de = ec2 / ae;
1413                         e.x = (corner.x + otherCorner.x) / 2;
1414                         e.y = (corner.y + otherCorner.y) / 2;
1415                         poly[3].x = e.x + de * (e.x - center.x) / ae;
1416                         poly[3].y = e.y + de * (e.y - center.y) / ae;
1417                         poly[4] = corner;
1418                         polyLen = 5;
1419                         break;
1420                 }
1421         case JoinBevel:
1422                 poly[0] = corner;
1423                 poly[1] = center;
1424                 poly[2] = otherCorner;
1425                 poly[3] = corner;
1426                 polyLen = 4;
1427                 break;
1428         }
1429         miFillSppPoly (pDraw, pGC, polyLen, poly, xOrg, yOrg, xFtrans, yFtrans);
1430 }
1431
1432 /*ARGSUSED*/
1433 static void
1434 miArcCap (pDraw, pGC, pFace, end, xOrg, yOrg, xFtrans, yFtrans)
1435         DrawablePtr     pDraw;
1436         GCPtr           pGC;
1437         miArcFacePtr    pFace;
1438         int             end;
1439         int             xOrg, yOrg;
1440         double          xFtrans, yFtrans;
1441 {
1442         SppPointRec     corner, otherCorner, center, endPoint, poly[5];
1443
1444         corner = pFace->clock;
1445         otherCorner = pFace->counterClock;
1446         center = pFace->center;
1447         switch (pGC->capStyle) {
1448         case CapProjecting:
1449                 poly[0].x = otherCorner.x;
1450                 poly[0].y = otherCorner.y;
1451                 poly[1].x = corner.x;
1452                 poly[1].y = corner.y;
1453                 poly[2].x = corner.x -
1454                                 (center.y - corner.y);
1455                 poly[2].y = corner.y +
1456                                 (center.x - corner.x);
1457                 poly[3].x = otherCorner.x -
1458                                 (otherCorner.y - center.y);
1459                 poly[3].y = otherCorner.y +
1460                                 (otherCorner.x - center.x);
1461                 poly[4].x = otherCorner.x;
1462                 poly[4].y = otherCorner.y;
1463                 miFillSppPoly (pDraw, pGC, 5, poly, xOrg, yOrg, xFtrans, yFtrans);
1464                 break;
1465         case CapRound:
1466                 /*
1467                  * miRoundCap just needs these to be unequal.
1468                  */
1469                 endPoint = center;
1470                 endPoint.x = endPoint.x + 100;
1471                 miRoundCap (pDraw, pGC, center, endPoint, corner, otherCorner, 0,
1472                             -xOrg, -yOrg, xFtrans, yFtrans);
1473                 break;
1474         }
1475 }
1476
1477 /* MIROUNDCAP -- a private helper function
1478  * Put Rounded cap on end. pCenter is the center of this end of the line
1479  * pEnd is the center of the other end of the line. pCorner is one of the
1480  * two corners at this end of the line.
1481  * NOTE:  pOtherCorner must be counter-clockwise from pCorner.
1482  */
1483 /*ARGSUSED*/
1484 static void
1485 miRoundCap(pDraw, pGC, pCenter, pEnd, pCorner, pOtherCorner, fLineEnd,
1486      xOrg, yOrg, xFtrans, yFtrans)
1487     DrawablePtr pDraw;
1488     GCPtr       pGC;
1489     SppPointRec pCenter, pEnd;
1490     SppPointRec pCorner, pOtherCorner;
1491     int         fLineEnd, xOrg, yOrg;
1492     double      xFtrans, yFtrans;
1493 {
1494     int         cpt;
1495     double      width;
1496     double      miDatan2 ();
1497     SppArcRec   arc;
1498     SppPointPtr pArcPts;
1499
1500     width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);
1501
1502     arc.x = pCenter.x - width/2;
1503     arc.y = pCenter.y - width/2;
1504     arc.width = width;
1505     arc.height = width;
1506     arc.angle1 = -miDatan2 (pCorner.y - pCenter.y, pCorner.x - pCenter.x);
1507     if(PTISEQUAL(pCenter, pEnd))
1508         arc.angle2 = - 180.0;
1509     else {
1510         arc.angle2 = -miDatan2 (pOtherCorner.y - pCenter.y, pOtherCorner.x - pCenter.x) - arc.angle1;
1511         if (arc.angle2 < 0)
1512             arc.angle2 += 360.0;
1513     }
1514     pArcPts = (SppPointPtr) NULL;
1515     if( (cpt = miGetArcPts(&arc, 0, &pArcPts)) )
1516     {
1517         /* by drawing with miFillSppPoly and setting the endpoints of the arc
1518          * to be the corners, we assure that the cap will meet up with the
1519          * rest of the line */
1520         miFillSppPoly(pDraw, pGC, cpt, pArcPts, -xOrg, -yOrg, xFtrans, yFtrans);
1521     }
1522     xfree(pArcPts);
1523 }
1524
1525 /*
1526  * To avoid inaccuracy at the cardinal points, use trig functions
1527  * which are exact for those angles
1528  */
1529
1530 #ifndef M_PI
1531 #define M_PI    3.14159265358979323846
1532 #endif
1533 #ifndef M_PI_2
1534 #define M_PI_2  1.57079632679489661923
1535 #endif
1536
1537 # define Dsin(d)        ((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))
1538 # define Dcos(d)        ((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))
1539 # define mod(a,b)       ((a) >= 0 ? (a) % (b) : (b) - (-a) % (b))
1540
1541 static double
1542 miDcos (a)
1543 double  a;
1544 {
1545         int     i;
1546
1547         if (floor (a/90) == a/90) {
1548                 i = (int) (a/90.0);
1549                 switch (mod (i, 4)) {
1550                 case 0: return 1;
1551                 case 1: return 0;
1552                 case 2: return -1;
1553                 case 3: return 0;
1554                 }
1555         }
1556         return cos (a * M_PI / 180.0);
1557 }
1558
1559 static double
1560 miDsin (a)
1561 double  a;
1562 {
1563         int     i;
1564
1565         if (floor (a/90) == a/90) {
1566                 i = (int) (a/90.0);
1567                 switch (mod (i, 4)) {
1568                 case 0: return 0;
1569                 case 1: return 1;
1570                 case 2: return 0;
1571                 case 3: return -1;
1572                 }
1573         }
1574         return sin (a * M_PI / 180.0);
1575 }
1576
1577 static double
1578 miDasin (v)
1579 double  v;
1580 {
1581     if (v == 0)
1582         return 0.0;
1583     if (v == 1.0)
1584         return 90.0;
1585     if (v == -1.0)
1586         return -90.0;
1587     return asin(v) * (180.0 / M_PI);
1588 }
1589
1590 static double
1591 miDatan2 (dy, dx)
1592 double  dy, dx;
1593 {
1594     if (dy == 0) {
1595         if (dx >= 0)
1596             return 0.0;
1597         return 180.0;
1598     } else if (dx == 0) {
1599         if (dy > 0)
1600             return 90.0;
1601         return -90.0;
1602     } else if (Fabs (dy) == Fabs (dx)) {
1603         if (dy > 0) {
1604             if (dx > 0)
1605                 return 45.0;
1606             return 135.0;
1607         } else {
1608             if (dx > 0)
1609                 return 315.0;
1610             return 225.0;
1611         }
1612     } else {
1613         return atan2 (dy, dx) * (180.0 / M_PI);
1614     }
1615 }
1616
1617 /* MIGETARCPTS -- Converts an arc into a set of line segments -- a helper
1618  * routine for filled arc and line (round cap) code.
1619  * Returns the number of points in the arc.  Note that it takes a pointer
1620  * to a pointer to where it should put the points and an index (cpt).
1621  * This procedure allocates the space necessary to fit the arc points.
1622  * Sometimes it's convenient for those points to be at the end of an existing
1623  * array. (For example, if we want to leave a spare point to make sectors
1624  * instead of segments.)  So we pass in the xalloc()ed chunk that contains the
1625  * array and an index saying where we should start stashing the points.
1626  * If there isn't an array already, we just pass in a null pointer and
1627  * count on xrealloc() to handle the null pointer correctly.
1628  */
1629 static int
1630 miGetArcPts(parc, cpt, ppPts)
1631     SppArcPtr   parc;   /* points to an arc */
1632     int         cpt;    /* number of points already in arc list */
1633     SppPointPtr *ppPts; /* pointer to pointer to arc-list -- modified */
1634 {
1635     double      st,     /* Start Theta, start angle */
1636                 et,     /* End Theta, offset from start theta */
1637                 dt,     /* Delta Theta, angle to sweep ellipse */
1638                 cdt,    /* Cos Delta Theta, actually 2 cos(dt) */
1639                 x0, y0, /* the recurrence formula needs two points to start */
1640                 x1, y1,
1641                 x2, y2, /* this will be the new point generated */
1642                 xc, yc; /* the center point */
1643     int         count, i;
1644     SppPointPtr poly;
1645     DDXPointRec last;           /* last point on integer boundaries */
1646
1647     /* The spec says that positive angles indicate counterclockwise motion.
1648      * Given our coordinate system (with 0,0 in the upper left corner),
1649      * the screen appears flipped in Y.  The easiest fix is to negate the
1650      * angles given */
1651
1652     st = - parc->angle1;
1653
1654     et = - parc->angle2;
1655
1656     /* Try to get a delta theta that is within 1/2 pixel.  Then adjust it
1657      * so that it divides evenly into the total.
1658      * I'm just using cdt 'cause I'm lazy.
1659      */
1660     cdt = parc->width;
1661     if (parc->height > cdt)
1662         cdt = parc->height;
1663     cdt /= 2.0;
1664     if(cdt <= 0)
1665         return 0;
1666     if (cdt < 1.0)
1667         cdt = 1.0;
1668     dt = miDasin ( 1.0 / cdt ); /* minimum step necessary */
1669     count = et/dt;
1670     count = abs(count) + 1;
1671     dt = et/count;
1672     count++;
1673
1674     cdt = 2 * miDcos(dt);
1675     if (!(poly = (SppPointPtr) xrealloc((pointer)*ppPts,
1676                                         (cpt + count) * sizeof(SppPointRec))))
1677         return(0);
1678     *ppPts = poly;
1679
1680     xc = parc->width/2.0;               /* store half width and half height */
1681     yc = parc->height/2.0;
1682
1683     x0 = xc * miDcos(st);
1684     y0 = yc * miDsin(st);
1685     x1 = xc * miDcos(st + dt);
1686     y1 = yc * miDsin(st + dt);
1687     xc += parc->x;              /* by adding initial point, these become */
1688     yc += parc->y;              /* the center point */
1689
1690     poly[cpt].x = (xc + x0);
1691     poly[cpt].y = (yc + y0);
1692     last.x = ROUNDTOINT( poly[cpt + 1].x = (xc + x1) );
1693     last.y = ROUNDTOINT( poly[cpt + 1].y = (yc + y1) );
1694
1695     for(i = 2; i < count; i++)
1696     {
1697         x2 = cdt * x1 - x0;
1698         y2 = cdt * y1 - y0;
1699
1700         poly[cpt + i].x = (xc + x2);
1701         poly[cpt + i].y = (yc + y2);
1702
1703         x0 = x1; y0 = y1;
1704         x1 = x2; y1 = y2;
1705     }
1706     /* adjust the last point */
1707     if (abs(parc->angle2) >= 360.0)
1708         poly[cpt +i -1] = poly[0];
1709     else {
1710         poly[cpt +i -1].x = (miDcos(st + et) * parc->width/2.0 + xc);
1711         poly[cpt +i -1].y = (miDsin(st + et) * parc->height/2.0 + yc);
1712     }
1713
1714     return(count);
1715 }
1716
1717 struct arcData {
1718         double  x0, y0, x1, y1;
1719         int     selfJoin;
1720 };
1721
1722 # define ADD_REALLOC_STEP       20
1723
1724 static void
1725 addCap (capsp, ncapsp, sizep, end, arcIndex)
1726         miArcCapPtr     *capsp;
1727         int             *ncapsp, *sizep;
1728         int             end, arcIndex;
1729 {
1730         int newsize;
1731         miArcCapPtr     cap;
1732
1733         if (*ncapsp == *sizep)
1734         {
1735             newsize = *sizep + ADD_REALLOC_STEP;
1736             cap = (miArcCapPtr) xrealloc (*capsp,
1737                                           newsize * sizeof (**capsp));
1738             if (!cap)
1739                 return;
1740             *sizep = newsize;
1741             *capsp = cap;
1742         }
1743         cap = &(*capsp)[*ncapsp];
1744         cap->end = end;
1745         cap->arcIndex = arcIndex;
1746         ++*ncapsp;
1747 }
1748
1749 static void
1750 addJoin (joinsp, njoinsp, sizep, end0, index0, phase0, end1, index1, phase1)
1751         miArcJoinPtr    *joinsp;
1752         int             *njoinsp, *sizep;
1753         int             end0, index0, phase0, end1, index1, phase1;
1754 {
1755         int newsize;
1756         miArcJoinPtr    join;
1757
1758         if (*njoinsp == *sizep)
1759         {
1760             newsize = *sizep + ADD_REALLOC_STEP;
1761             join = (miArcJoinPtr) xrealloc (*joinsp,
1762                                             newsize * sizeof (**joinsp));
1763             if (!join)
1764                 return;
1765             *sizep = newsize;
1766             *joinsp = join;
1767         }
1768         join = &(*joinsp)[*njoinsp];
1769         join->end0 = end0;
1770         join->arcIndex0 = index0;
1771         join->phase0 = phase0;
1772         join->end1 = end1;
1773         join->arcIndex1 = index1;
1774         join->phase1 = phase1;
1775         ++*njoinsp;
1776 }
1777
1778 static miArcDataPtr
1779 addArc (arcsp, narcsp, sizep, xarc)
1780         miArcDataPtr    *arcsp;
1781         int             *narcsp, *sizep;
1782         xArc            *xarc;
1783 {
1784         int newsize;
1785         miArcDataPtr    arc;
1786
1787         if (*narcsp == *sizep)
1788         {
1789             newsize = *sizep + ADD_REALLOC_STEP;
1790             arc = (miArcDataPtr) xrealloc (*arcsp,
1791                                            newsize * sizeof (**arcsp));
1792             if (!arc)
1793                 return (miArcDataPtr)NULL;
1794             *sizep = newsize;
1795             *arcsp = arc;
1796         }
1797         arc = &(*arcsp)[*narcsp];
1798         arc->arc = *xarc;
1799         ++*narcsp;
1800         return arc;
1801 }
1802
1803 static void
1804 miFreeArcs(arcs, pGC)
1805     miPolyArcPtr arcs;
1806     GCPtr pGC;
1807 {
1808         int iphase;
1809
1810         for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);
1811              iphase >= 0;
1812              iphase--)
1813         {
1814             if (arcs[iphase].narcs > 0)
1815                 xfree(arcs[iphase].arcs);
1816             if (arcs[iphase].njoins > 0)
1817                 xfree(arcs[iphase].joins);
1818             if (arcs[iphase].ncaps > 0)
1819                 xfree(arcs[iphase].caps);
1820         }
1821         xfree(arcs);
1822 }
1823
1824 /*
1825  * map angles to radial distance.  This only deals with the first quadrant
1826  */
1827
1828 /*
1829  * a polygonal approximation to the arc for computing arc lengths
1830  */
1831
1832 # define DASH_MAP_SIZE  91
1833
1834 # define dashIndexToAngle(di)   ((((double) (di)) * 90.0) / ((double) DASH_MAP_SIZE - 1))
1835 # define xAngleToDashIndex(xa)  ((((long) (xa)) * (DASH_MAP_SIZE - 1)) / (90 * 64))
1836 # define dashIndexToXAngle(di)  ((((long) (di)) * (90 * 64)) / (DASH_MAP_SIZE - 1))
1837 # define dashXAngleStep (((double) (90 * 64)) / ((double) (DASH_MAP_SIZE - 1)))
1838
1839 typedef struct {
1840         double  map[DASH_MAP_SIZE];
1841 } dashMap;
1842
1843 static void
1844 computeDashMap (arcp, map)
1845         xArc    *arcp;
1846         dashMap *map;
1847 {
1848         int     di;
1849         double  a, x, y, prevx, prevy, dist;
1850
1851         for (di = 0; di < DASH_MAP_SIZE; di++) {
1852                 a = dashIndexToAngle (di);
1853                 x = ((double) arcp->width / 2.0) * miDcos (a);
1854                 y = ((double) arcp->height / 2.0) * miDsin (a);
1855                 if (di == 0) {
1856                         map->map[di] = 0.0;
1857                 } else {
1858                         dist = hypot (x - prevx, y - prevy);
1859                         map->map[di] = map->map[di - 1] + dist;
1860                 }
1861                 prevx = x;
1862                 prevy = y;
1863         }
1864 }
1865
1866 typedef enum {HORIZONTAL, VERTICAL, OTHER} arcTypes;
1867
1868 /* this routine is a bit gory */
1869
1870 static miPolyArcPtr
1871 miComputeArcs (parcs, narcs, pGC)
1872         xArc    *parcs;
1873         int     narcs;
1874         GCPtr   pGC;
1875 {
1876         int             isDashed, isDoubleDash;
1877         int             dashOffset;
1878         miPolyArcPtr    arcs;
1879         int             start, i, j, k, nexti, nextk;
1880         int             joinSize[2];
1881         int             capSize[2];
1882         int             arcSize[2];
1883         int             angle2;
1884         double          a0, a1;
1885         struct arcData  *data;
1886         miArcDataPtr    arc;
1887         xArc            xarc;
1888         int             iphase, prevphase, joinphase;
1889         int             arcsJoin;
1890         int             selfJoin;
1891
1892         int             iDash, dashRemaining;
1893         int             iDashStart, dashRemainingStart, iphaseStart;
1894         int             startAngle, spanAngle, endAngle, backwards;
1895         int             prevDashAngle, dashAngle;
1896         dashMap         map;
1897
1898         isDashed = !(pGC->lineStyle == LineSolid);
1899         isDoubleDash = (pGC->lineStyle == LineDoubleDash);
1900         dashOffset = pGC->dashOffset;
1901
1902         data = (struct arcData *) ALLOCATE_LOCAL (narcs * sizeof (struct arcData));
1903         if (!data)
1904             return (miPolyArcPtr)NULL;
1905         arcs = (miPolyArcPtr) xalloc (sizeof (*arcs) * (isDoubleDash ? 2 : 1));
1906         if (!arcs)
1907         {
1908             DEALLOCATE_LOCAL(data);
1909             return (miPolyArcPtr)NULL;
1910         }
1911         for (i = 0; i < narcs; i++) {
1912                 a0 = todeg (parcs[i].angle1);
1913                 angle2 = parcs[i].angle2;
1914                 if (angle2 > FULLCIRCLE)
1915                         angle2 = FULLCIRCLE;
1916                 else if (angle2 < -FULLCIRCLE)
1917                         angle2 = -FULLCIRCLE;
1918                 data[i].selfJoin = angle2 == FULLCIRCLE || angle2 == -FULLCIRCLE;
1919                 a1 = todeg (parcs[i].angle1 + angle2);
1920                 data[i].x0 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a0));
1921                 data[i].y0 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a0));
1922                 data[i].x1 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a1));
1923                 data[i].y1 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a1));
1924         }
1925
1926         for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++) {
1927                 arcs[iphase].njoins = 0;
1928                 arcs[iphase].joins = 0;
1929                 joinSize[iphase] = 0;
1930
1931                 arcs[iphase].ncaps = 0;
1932                 arcs[iphase].caps = 0;
1933                 capSize[iphase] = 0;
1934
1935                 arcs[iphase].narcs = 0;
1936                 arcs[iphase].arcs = 0;
1937                 arcSize[iphase] = 0;
1938         }
1939
1940         iphase = 0;
1941         if (isDashed) {
1942                 iDash = 0;
1943                 dashRemaining = pGC->dash[0];
1944                 while (dashOffset > 0) {
1945                         if (dashOffset >= dashRemaining) {
1946                                 dashOffset -= dashRemaining;
1947                                 iphase = iphase ? 0 : 1;
1948                                 iDash++;
1949                                 if (iDash == pGC->numInDashList)
1950                                     iDash = 0;
1951                                 dashRemaining = pGC->dash[iDash];
1952                         } else {
1953                                 dashRemaining -= dashOffset;
1954                                 dashOffset = 0;
1955                         }
1956                 }
1957                 iDashStart = iDash;
1958                 dashRemainingStart = dashRemaining;
1959         }
1960         iphaseStart = iphase;
1961
1962         for (i = narcs - 1; i >= 0; i--) {
1963                 j = i + 1;
1964                 if (j == narcs)
1965                         j = 0;
1966                 if (data[i].selfJoin || i == j ||
1967                      (UNEQUAL (data[i].x1, data[j].x0) ||
1968                       UNEQUAL (data[i].y1, data[j].y0)))
1969                 {
1970                         if (iphase == 0 || isDoubleDash)
1971                                 addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
1972                                         &capSize[iphase], RIGHT_END, 0);
1973                         break;
1974                 }
1975         }
1976         start = i + 1;
1977         if (start == narcs)
1978                 start = 0;
1979         i = start;
1980         for (;;) {
1981                 j = i + 1;
1982                 if (j == narcs)
1983                         j = 0;
1984                 nexti = i+1;
1985                 if (nexti == narcs)
1986                         nexti = 0;
1987                 if (isDashed) {
1988                         /*
1989                         ** deal with dashed arcs.  Use special rules for certain 0 area arcs.
1990                         ** Presumably, the other 0 area arcs still aren't done right.
1991                         */
1992                         arcTypes        arcType = OTHER;
1993                         CARD16          thisLength;
1994
1995                         if (parcs[i].height == 0
1996                             && (parcs[i].angle1 % FULLCIRCLE) == 0x2d00
1997                             && parcs[i].angle2 == 0x2d00)
1998                                 arcType = HORIZONTAL;
1999                         else if (parcs[i].width == 0
2000                             && (parcs[i].angle1 % FULLCIRCLE) == 0x1680
2001                             && parcs[i].angle2 == 0x2d00)
2002                                 arcType = VERTICAL;
2003                         if (arcType == OTHER) {
2004                                 /*
2005                                  * precompute an approximation map
2006                                  */
2007                                 computeDashMap (&parcs[i], &map);
2008                                 /*
2009                                  * compute each individual dash segment using the path
2010                                  * length function
2011                                  */
2012                                 startAngle = parcs[i].angle1;
2013                                 spanAngle = parcs[i].angle2;
2014                                 if (spanAngle > FULLCIRCLE)
2015                                         spanAngle = FULLCIRCLE;
2016                                 else if (spanAngle < -FULLCIRCLE)
2017                                         spanAngle = -FULLCIRCLE;
2018                                 if (startAngle < 0)
2019                                         startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
2020                                 if (startAngle >= FULLCIRCLE)
2021                                         startAngle = startAngle % FULLCIRCLE;
2022                                 endAngle = startAngle + spanAngle;
2023                                 backwards = spanAngle < 0;
2024                         } else {
2025                                 xarc = parcs[i];
2026                                 if (arcType == VERTICAL) {
2027                                         xarc.angle1 = 0x1680;
2028                                         startAngle = parcs[i].y;
2029                                         endAngle = startAngle + parcs[i].height;
2030                                 } else {
2031                                         xarc.angle1 = 0x2d00;
2032                                         startAngle = parcs[i].x;
2033                                         endAngle = startAngle + parcs[i].width;
2034                                 }
2035                         }
2036                         dashAngle = startAngle;
2037                         selfJoin = data[i].selfJoin &&
2038                                     (iphase == 0 || isDoubleDash);
2039                         /*
2040                          * add dashed arcs to each bucket
2041                          */
2042                         arc = 0;
2043                         while (dashAngle != endAngle) {
2044                                 prevDashAngle = dashAngle;
2045                                 if (arcType == OTHER) {
2046                                         dashAngle = computeAngleFromPath (prevDashAngle, endAngle,
2047                                                                 &map, &dashRemaining, backwards);
2048                                         /* avoid troubles with huge arcs and small dashes */
2049                                         if (dashAngle == prevDashAngle) {
2050                                                 if (backwards)
2051                                                         dashAngle--;
2052                                                 else
2053                                                         dashAngle++;
2054                                         }
2055                                 } else {
2056                                         thisLength = (dashAngle + dashRemaining <= endAngle) ?
2057                                             dashRemaining : endAngle - dashAngle;
2058                                         if (arcType == VERTICAL) {
2059                                                 xarc.y = dashAngle;
2060                                                 xarc.height = thisLength;
2061                                         } else {
2062                                                 xarc.x = dashAngle;
2063                                                 xarc.width = thisLength;
2064                                         }
2065                                         dashAngle += thisLength;
2066                                         dashRemaining -= thisLength;
2067                                 }
2068                                 if (iphase == 0 || isDoubleDash) {
2069                                         if (arcType == OTHER) {
2070                                                 xarc = parcs[i];
2071                                                 spanAngle = prevDashAngle;
2072                                                 if (spanAngle < 0)
2073                                                     spanAngle = FULLCIRCLE - (-spanAngle) % FULLCIRCLE;
2074                                                 if (spanAngle >= FULLCIRCLE)
2075                                                     spanAngle = spanAngle % FULLCIRCLE;
2076                                                 xarc.angle1 = spanAngle;
2077                                                 spanAngle = dashAngle - prevDashAngle;
2078                                                 if (backwards) {
2079                                                         if (dashAngle > prevDashAngle)
2080                                                                 spanAngle = - FULLCIRCLE + spanAngle;
2081                                                 } else {
2082                                                         if (dashAngle < prevDashAngle)
2083                                                                 spanAngle = FULLCIRCLE + spanAngle;
2084                                                 }
2085                                                 if (spanAngle > FULLCIRCLE)
2086                                                     spanAngle = FULLCIRCLE;
2087                                                 if (spanAngle < -FULLCIRCLE)
2088                                                     spanAngle = -FULLCIRCLE;
2089                                                 xarc.angle2 = spanAngle;
2090                                         }
2091                                         arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
2092                                                         &arcSize[iphase], &xarc);
2093                                         if (!arc)
2094                                             goto arcfail;
2095                                         /*
2096                                          * cap each end of an on/off dash
2097                                          */
2098                                         if (!isDoubleDash) {
2099                                                 if (prevDashAngle != startAngle) {
2100                                                         addCap (&arcs[iphase].caps,
2101                                                                 &arcs[iphase].ncaps,
2102                                                                 &capSize[iphase], RIGHT_END,
2103                                                                 arc - arcs[iphase].arcs);
2104
2105                                                 }
2106                                                 if (dashAngle != endAngle) {
2107                                                         addCap (&arcs[iphase].caps,
2108                                                                 &arcs[iphase].ncaps,
2109                                                                 &capSize[iphase], LEFT_END,
2110                                                                 arc - arcs[iphase].arcs);
2111                                                 }
2112                                         }
2113                                         arc->cap = arcs[iphase].ncaps;
2114                                         arc->join = arcs[iphase].njoins;
2115                                         arc->render = 0;
2116                                         arc->selfJoin = 0;
2117                                         if (dashAngle == endAngle)
2118                                                 arc->selfJoin = selfJoin;
2119                                 }
2120                                 prevphase = iphase;
2121                                 if (dashRemaining <= 0) {
2122                                         ++iDash;
2123                                         if (iDash == pGC->numInDashList)
2124                                                 iDash = 0;
2125                                         iphase = iphase ? 0:1;
2126                                         dashRemaining = pGC->dash[iDash];
2127                                 }
2128                         }
2129                         /*
2130                          * make sure a place exists for the position data when
2131                          * drawing a zero-length arc
2132                          */
2133                         if (startAngle == endAngle) {
2134                                 prevphase = iphase;
2135                                 if (!isDoubleDash && iphase == 1)
2136                                         prevphase = 0;
2137                                 arc = addArc (&arcs[prevphase].arcs, &arcs[prevphase].narcs,
2138                                               &arcSize[prevphase], &parcs[i]);
2139                                 if (!arc)
2140                                     goto arcfail;
2141                                 arc->join = arcs[prevphase].njoins;
2142                                 arc->cap = arcs[prevphase].ncaps;
2143                                 arc->selfJoin = data[i].selfJoin;
2144                         }
2145                 } else {
2146                         arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
2147                                       &arcSize[iphase], &parcs[i]);
2148                         if (!arc)
2149                             goto arcfail;
2150                         arc->join = arcs[iphase].njoins;
2151                         arc->cap = arcs[iphase].ncaps;
2152                         arc->selfJoin = data[i].selfJoin;
2153                         prevphase = iphase;
2154                 }
2155                 if (prevphase == 0 || isDoubleDash)
2156                         k = arcs[prevphase].narcs - 1;
2157                 if (iphase == 0 || isDoubleDash)
2158                         nextk = arcs[iphase].narcs;
2159                 if (nexti == start) {
2160                         nextk = 0;
2161                         if (isDashed) {
2162                                 iDash = iDashStart;
2163                                 iphase = iphaseStart;
2164                                 dashRemaining = dashRemainingStart;
2165                         }
2166                 }
2167                 arcsJoin = narcs > 1 && i != j &&
2168                             ISEQUAL (data[i].x1, data[j].x0) &&
2169                             ISEQUAL (data[i].y1, data[j].y0) &&
2170                             !data[i].selfJoin && !data[j].selfJoin;
2171                 if (arc)
2172                 {
2173                         if (arcsJoin)
2174                                 arc->render = 0;
2175                         else
2176                                 arc->render = 1;
2177                 }
2178                 if (arcsJoin &&
2179                     (prevphase == 0 || isDoubleDash) &&
2180                     (iphase == 0 || isDoubleDash))
2181                 {
2182                         joinphase = iphase;
2183                         if (isDoubleDash) {
2184                                 if (nexti == start)
2185                                         joinphase = iphaseStart;
2186                                 /*
2187                                  * if the join is right at the dash,
2188                                  * draw the join in foreground
2189                                  * This is because the foreground
2190                                  * arcs are computed second, the results
2191                                  * of which are needed to draw the join
2192                                  */
2193                                 if (joinphase != prevphase)
2194                                         joinphase = 0;
2195                         }
2196                         if (joinphase == 0 || isDoubleDash) {
2197                                 addJoin (&arcs[joinphase].joins,
2198                                          &arcs[joinphase].njoins,
2199                                          &joinSize[joinphase],
2200                                          LEFT_END, k, prevphase,
2201                                          RIGHT_END, nextk, iphase);
2202                                 arc->join = arcs[prevphase].njoins;
2203                         }
2204                 } else {
2205                         /*
2206                          * cap the left end of this arc
2207                          * unless it joins itself
2208                          */
2209                         if ((prevphase == 0 || isDoubleDash) &&
2210                             !arc->selfJoin)
2211                         {
2212                                 addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
2213                                         &capSize[prevphase], LEFT_END, k);
2214                                 arc->cap = arcs[prevphase].ncaps;
2215                         }
2216                         if (isDashed && !arcsJoin) {
2217                                 iDash = iDashStart;
2218                                 iphase = iphaseStart;
2219                                 dashRemaining = dashRemainingStart;
2220                         }
2221                         nextk = arcs[iphase].narcs;
2222                         if (nexti == start) {
2223                                 nextk = 0;
2224                                 iDash = iDashStart;
2225                                 iphase = iphaseStart;
2226                                 dashRemaining = dashRemainingStart;
2227                         }
2228                         /*
2229                          * cap the right end of the next arc.  If the
2230                          * next arc is actually the first arc, only
2231                          * cap it if it joins with this arc.  This
2232                          * case will occur when the final dash segment
2233                          * of an on/off dash is off.  Of course, this
2234                          * cap will be drawn at a strange time, but that
2235                          * hardly matters...
2236                          */
2237                         if ((iphase == 0 || isDoubleDash) &&
2238                             (nexti != start || (arcsJoin && isDashed)))
2239                                 addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
2240                                         &capSize[iphase], RIGHT_END, nextk);
2241                 }
2242                 i = nexti;
2243                 if (i == start)
2244                         break;
2245         }
2246         /*
2247          * make sure the last section is rendered
2248          */
2249         for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++)
2250                 if (arcs[iphase].narcs > 0) {
2251                         arcs[iphase].arcs[arcs[iphase].narcs-1].render = 1;
2252                         arcs[iphase].arcs[arcs[iphase].narcs-1].join =
2253                                  arcs[iphase].njoins;
2254                         arcs[iphase].arcs[arcs[iphase].narcs-1].cap =
2255                                  arcs[iphase].ncaps;
2256                 }
2257         DEALLOCATE_LOCAL(data);
2258         return arcs;
2259 arcfail:
2260         miFreeArcs(arcs, pGC);
2261         DEALLOCATE_LOCAL(data);
2262         return (miPolyArcPtr)NULL;
2263 }
2264
2265 static double
2266 angleToLength (angle, map)
2267         int     angle;
2268         dashMap *map;
2269 {
2270         double  len, excesslen, sidelen = map->map[DASH_MAP_SIZE - 1], totallen;
2271         int     di;
2272         int     excess;
2273         Bool    oddSide = FALSE;
2274
2275         totallen = 0;
2276         if (angle >= 0) {
2277                 while (angle >= 90 * 64) {
2278                         angle -= 90 * 64;
2279                         totallen += sidelen;
2280                         oddSide = !oddSide;
2281                 }
2282         } else {
2283                 while (angle < 0) {
2284                         angle += 90 * 64;
2285                         totallen -= sidelen;
2286                         oddSide = !oddSide;
2287                 }
2288         }
2289         if (oddSide)
2290                 angle = 90 * 64 - angle;
2291
2292         di = xAngleToDashIndex (angle);
2293         excess = angle - dashIndexToXAngle (di);
2294
2295         len = map->map[di];
2296         /*
2297          * linearly interpolate between this point and the next
2298          */
2299         if (excess > 0) {
2300                 excesslen = (map->map[di + 1] - map->map[di]) *
2301                                 ((double) excess) / dashXAngleStep;
2302                 len += excesslen;
2303         }
2304         if (oddSide)
2305                 totallen += (sidelen - len);
2306         else
2307                 totallen += len;
2308         return totallen;
2309 }
2310
2311 /*
2312  * len is along the arc, but may be more than one rotation
2313  */
2314
2315 static int
2316 lengthToAngle (len, map)
2317         double  len;
2318         dashMap *map;
2319 {
2320         double  sidelen = map->map[DASH_MAP_SIZE - 1];
2321         int     angle, angleexcess;
2322         Bool    oddSide = FALSE;
2323         int     a0, a1, a;
2324
2325         angle = 0;
2326         /*
2327          * step around the ellipse, subtracting sidelens and
2328          * adding 90 degrees.  oddSide will tell if the
2329          * map should be interpolated in reverse
2330          */
2331         if (len >= 0) {
2332                 if (sidelen == 0)
2333                         return 2 * FULLCIRCLE;  /* infinity */
2334                 while (len >= sidelen) {
2335                         angle += 90 * 64;
2336                         len -= sidelen;
2337                         oddSide = !oddSide;
2338                 }
2339         } else {
2340                 if (sidelen == 0)
2341                         return -2 * FULLCIRCLE; /* infinity */
2342                 while (len < 0) {
2343                         angle -= 90 * 64;
2344                         len += sidelen;
2345                         oddSide = !oddSide;
2346                 }
2347         }
2348         if (oddSide)
2349                 len = sidelen - len;
2350         a0 = 0;
2351         a1 = DASH_MAP_SIZE - 1;
2352         /*
2353          * binary search for the closest pre-computed length
2354          */
2355         while (a1 - a0 > 1) {
2356                 a = (a0 + a1) / 2;
2357                 if (len > map->map[a])
2358                         a0 = a;
2359                 else
2360                         a1 = a;
2361         }
2362         angleexcess = dashIndexToXAngle (a0);
2363         /*
2364          * linearly interpolate to the next point
2365          */
2366         angleexcess += (len - map->map[a0]) /
2367                         (map->map[a0+1] - map->map[a0]) * dashXAngleStep;
2368         if (oddSide)
2369                 angle += (90 * 64) - angleexcess;
2370         else
2371                 angle += angleexcess;
2372         return angle;
2373 }
2374
2375 /*
2376  * compute the angle of an ellipse which cooresponds to
2377  * the given path length.  Note that the correct solution
2378  * to this problem is an eliptic integral, we'll punt and
2379  * approximate (it's only for dashes anyway).  This
2380  * approximation uses a polygon.
2381  *
2382  * The remaining portion of len is stored in *lenp -
2383  * this will be negative if the arc extends beyond
2384  * len and positive if len extends beyond the arc.
2385  */
2386
2387 static int
2388 computeAngleFromPath (startAngle, endAngle, map, lenp, backwards)
2389         int     startAngle, endAngle;   /* normalized absolute angles in *64 degrees */
2390         dashMap *map;
2391         int     *lenp;
2392         int     backwards;
2393 {
2394         int     a0, a1, a;
2395         double  len0;
2396         int     len;
2397
2398         a0 = startAngle;
2399         a1 = endAngle;
2400         len = *lenp;
2401         if (backwards) {
2402                 /*
2403                  * flip the problem around to always be
2404                  * forwards
2405                  */
2406                 a0 = FULLCIRCLE - a0;
2407                 a1 = FULLCIRCLE - a1;
2408         }
2409         if (a1 < a0)
2410                 a1 += FULLCIRCLE;
2411         len0 = angleToLength (a0, map);
2412         a = lengthToAngle (len0 + len, map);
2413         if (a > a1) {
2414                 a = a1;
2415                 len -= angleToLength (a1, map) - len0;
2416         } else
2417                 len = 0;
2418         if (backwards)
2419                 a = FULLCIRCLE - a;
2420         *lenp = len;
2421         return a;
2422 }
2423
2424 /*
2425  * scan convert wide arcs.
2426  */
2427
2428 /*
2429  * draw zero width/height arcs
2430  */
2431
2432 static void
2433 drawZeroArc (pDraw, pGC, tarc, lw, left, right)
2434     DrawablePtr   pDraw;
2435     GCPtr         pGC;
2436     xArc          *tarc;
2437     int           lw;
2438     miArcFacePtr        right, left;
2439 {
2440         double  x0, y0, x1, y1, w, h, x, y;
2441         double  xmax, ymax, xmin, ymin;
2442         int     a0, a1;
2443         double  a, startAngle, endAngle;
2444         double  l, lx, ly;
2445
2446         l = lw / 2.0;
2447         a0 = tarc->angle1;
2448         a1 = tarc->angle2;
2449         if (a1 > FULLCIRCLE)
2450                 a1 = FULLCIRCLE;
2451         else if (a1 < -FULLCIRCLE)
2452                 a1 = -FULLCIRCLE;
2453         w = (double)tarc->width / 2.0;
2454         h = (double)tarc->height / 2.0;
2455         /*
2456          * play in X coordinates right away
2457          */
2458         startAngle = - ((double) a0 / 64.0);
2459         endAngle = - ((double) (a0 + a1) / 64.0);
2460
2461         xmax = -w;
2462         xmin = w;
2463         ymax = -h;
2464         ymin = h;
2465         a = startAngle;
2466         for (;;)
2467         {
2468                 x = w * miDcos(a);
2469                 y = h * miDsin(a);
2470                 if (a == startAngle)
2471                 {
2472                         x0 = x;
2473                         y0 = y;
2474                 }
2475                 if (a == endAngle)
2476                 {
2477                         x1 = x;
2478                         y1 = y;
2479                 }
2480                 if (x > xmax)
2481                         xmax = x;
2482                 if (x < xmin)
2483                         xmin = x;
2484                 if (y > ymax)
2485                         ymax = y;
2486                 if (y < ymin)
2487                         ymin = y;
2488                 if (a == endAngle)
2489                         break;
2490                 if (a1 < 0)     /* clockwise */
2491                 {
2492                         if (floor (a / 90.0) == floor (endAngle / 90.0))
2493                                 a = endAngle;
2494                         else
2495                                 a = 90 * (floor (a/90.0) + 1);
2496                 }
2497                 else
2498                 {
2499                         if (ceil (a / 90.0) == ceil (endAngle / 90.0))
2500                                 a = endAngle;
2501                         else
2502                                 a = 90 * (ceil (a/90.0) - 1);
2503                 }
2504         }
2505         lx = ly = l;
2506         if ((x1 - x0) + (y1 - y0) < 0)
2507             lx = ly = -l;
2508         if (h)
2509         {
2510             ly = 0.0;
2511             lx = -lx;
2512         }
2513         else
2514             lx = 0.0;
2515         if (right)
2516         {
2517             right->center.x = x0;
2518             right->center.y = y0;
2519             right->clock.x = x0 - lx;
2520             right->clock.y = y0 - ly;
2521             right->counterClock.x = x0 + lx;
2522             right->counterClock.y = y0 + ly;
2523         }
2524         if (left)
2525         {
2526             left->center.x = x1;
2527             left->center.y = y1;
2528             left->clock.x = x1 + lx;
2529             left->clock.y = y1 + ly;
2530             left->counterClock.x = x1 - lx;
2531             left->counterClock.y = y1 - ly;
2532         }
2533
2534         x0 = xmin;
2535         x1 = xmax;
2536         y0 = ymin;
2537         y1 = ymax;
2538         if (ymin != y1) {
2539                 xmin = -l;
2540                 xmax = l;
2541         } else {
2542                 ymin = -l;
2543                 ymax = l;
2544         }
2545         if (xmax != xmin && ymax != ymin) {
2546                 int     minx, maxx, miny, maxy;
2547                 xRectangle  rect;
2548
2549                 minx = ICEIL (xmin + w) + tarc->x;
2550                 maxx = ICEIL (xmax + w) + tarc->x;
2551                 miny = ICEIL (ymin + h) + tarc->y;
2552                 maxy = ICEIL (ymax + h) + tarc->y;
2553                 rect.x = minx;
2554                 rect.y = miny;
2555                 rect.width = maxx - minx;
2556                 rect.height = maxy - miny;
2557                 (*pGC->ops->PolyFillRect) (pDraw, pGC, 1, &rect);
2558         }
2559 }
2560
2561 /*
2562  * this computes the ellipse y value associated with the
2563  * bottom of the tail.
2564  */
2565
2566 static void
2567 tailEllipseY (def, acc)
2568         struct arc_def          *def;
2569         struct accelerators     *acc;
2570 {
2571         double          t;
2572
2573         acc->tail_y = 0.0;
2574         if (def->w == def->h)
2575             return;
2576         t = def->l * def->w;
2577         if (def->w > def->h) {
2578             if (t < acc->h2)
2579                 return;
2580         } else {
2581             if (t > acc->h2)
2582                 return;
2583         }
2584         t = 2.0 * def->h * t;
2585         t = (CUBED_ROOT_4 * acc->h2 - cbrt(t * t)) / acc->h2mw2;
2586         if (t > 0.0)
2587             acc->tail_y = def->h / CUBED_ROOT_2 * sqrt(t);
2588 }
2589
2590 /*
2591  * inverse functions -- compute edge coordinates
2592  * from the ellipse
2593  */
2594
2595 static double
2596 outerXfromXY (x, y, def, acc)
2597         double                  x, y;
2598         struct arc_def          *def;
2599         struct accelerators     *acc;
2600 {
2601         return x + (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2602 }
2603
2604 static double
2605 outerYfromXY (x, y, def, acc)
2606         double          x, y;
2607         struct arc_def          *def;
2608         struct accelerators     *acc;
2609 {
2610         return y + (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2611 }
2612
2613 static double
2614 innerXfromXY (x, y, def, acc)
2615         double                  x, y;
2616         struct arc_def          *def;
2617         struct accelerators     *acc;
2618 {
2619         return x - (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2620 }
2621
2622 static double
2623 innerYfromXY (x, y, def, acc)
2624         double                  x, y;
2625         struct arc_def          *def;
2626         struct accelerators     *acc;
2627 {
2628         return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2629 }
2630
2631 static double
2632 innerYfromY (y, def, acc)
2633         double  y;
2634         struct arc_def          *def;
2635         struct accelerators     *acc;
2636 {
2637         double  x;
2638
2639         x = (def->w / def->h) * sqrt (acc->h2 - y*y);
2640
2641         return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2642 }
2643
2644 static void
2645 computeLine (x1, y1, x2, y2, line)
2646         double          x1, y1, x2, y2;
2647         struct line     *line;
2648 {
2649         if (y1 == y2)
2650                 line->valid = 0;
2651         else {
2652                 line->m = (x1 - x2) / (y1 - y2);
2653                 line->b = x1  - y1 * line->m;
2654                 line->valid = 1;
2655         }
2656 }
2657
2658 /*
2659  * compute various accelerators for an ellipse.  These
2660  * are simply values that are used repeatedly in
2661  * the computations
2662  */
2663
2664 static void
2665 computeAcc (tarc, lw, def, acc)
2666         xArc                    *tarc;
2667         int                     lw;
2668         struct arc_def          *def;
2669         struct accelerators     *acc;
2670 {
2671         def->w = ((double) tarc->width) / 2.0;
2672         def->h = ((double) tarc->height) / 2.0;
2673         def->l = ((double) lw) / 2.0;
2674         acc->h2 = def->h * def->h;
2675         acc->w2 = def->w * def->w;
2676         acc->h4 = acc->h2 * acc->h2;
2677         acc->w4 = acc->w2 * acc->w2;
2678         acc->h2l = acc->h2 * def->l;
2679         acc->w2l = acc->w2 * def->l;
2680         acc->h2mw2 = acc->h2 - acc->w2;
2681         acc->fromIntX = (tarc->width & 1) ? 0.5 : 0.0;
2682         acc->fromIntY = (tarc->height & 1) ? 0.5 : 0.0;
2683         acc->xorg = tarc->x + (tarc->width >> 1);
2684         acc->yorgu = tarc->y + (tarc->height >> 1);
2685         acc->yorgl = acc->yorgu + (tarc->height & 1);
2686         tailEllipseY (def, acc);
2687 }
2688
2689 /*
2690  * compute y value bounds of various portions of the arc,
2691  * the outer edge, the ellipse and the inner edge.
2692  */
2693
2694 static void
2695 computeBound (def, bound, acc, right, left)
2696         struct arc_def          *def;
2697         struct arc_bound        *bound;
2698         struct accelerators     *acc;
2699         miArcFacePtr            right, left;
2700 {
2701         double          t;
2702         double          innerTaily;
2703         double          tail_y;
2704         struct bound    innerx, outerx;
2705         struct bound    ellipsex;
2706
2707         bound->ellipse.min = Dsin (def->a0) * def->h;
2708         bound->ellipse.max = Dsin (def->a1) * def->h;
2709         if (def->a0 == 45 && def->w == def->h)
2710                 ellipsex.min = bound->ellipse.min;
2711         else
2712                 ellipsex.min = Dcos (def->a0) * def->w;
2713         if (def->a1 == 45 && def->w == def->h)
2714                 ellipsex.max = bound->ellipse.max;
2715         else
2716                 ellipsex.max = Dcos (def->a1) * def->w;
2717         bound->outer.min = outerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2718         bound->outer.max = outerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2719         bound->inner.min = innerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2720         bound->inner.max = innerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2721
2722         outerx.min = outerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2723         outerx.max = outerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2724         innerx.min = innerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2725         innerx.max = innerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2726
2727         /*
2728          * save the line end points for the
2729          * cap code to use.  Careful here, these are
2730          * in cartesean coordinates (y increasing upwards)
2731          * while the cap code uses inverted coordinates
2732          * (y increasing downwards)
2733          */
2734
2735         if (right) {
2736                 right->counterClock.y = bound->outer.min;
2737                 right->counterClock.x = outerx.min;
2738                 right->center.y = bound->ellipse.min;
2739                 right->center.x = ellipsex.min;
2740                 right->clock.y = bound->inner.min;
2741                 right->clock.x = innerx.min;
2742         }
2743
2744         if (left) {
2745                 left->clock.y = bound->outer.max;
2746                 left->clock.x = outerx.max;
2747                 left->center.y = bound->ellipse.max;
2748                 left->center.x = ellipsex.max;
2749                 left->counterClock.y = bound->inner.max;
2750                 left->counterClock.x = innerx.max;
2751         }
2752
2753         bound->left.min = bound->inner.max;
2754         bound->left.max = bound->outer.max;
2755         bound->right.min = bound->inner.min;
2756         bound->right.max = bound->outer.min;
2757
2758         computeLine (innerx.min, bound->inner.min, outerx.min, bound->outer.min,
2759                       &acc->right);
2760         computeLine (innerx.max, bound->inner.max, outerx.max, bound->outer.max,
2761                      &acc->left);
2762
2763         if (bound->inner.min > bound->inner.max) {
2764                 t = bound->inner.min;
2765                 bound->inner.min = bound->inner.max;
2766                 bound->inner.max = t;
2767         }
2768         tail_y = acc->tail_y;
2769         if (tail_y > bound->ellipse.max)
2770                 tail_y = bound->ellipse.max;
2771         else if (tail_y < bound->ellipse.min)
2772                 tail_y = bound->ellipse.min;
2773         innerTaily = innerYfromY (tail_y, def, acc);
2774         if (bound->inner.min > innerTaily)
2775                 bound->inner.min = innerTaily;
2776         if (bound->inner.max < innerTaily)
2777                 bound->inner.max = innerTaily;
2778         bound->inneri.min = ICEIL(bound->inner.min - acc->fromIntY);
2779         bound->inneri.max = floor(bound->inner.max - acc->fromIntY);
2780         bound->outeri.min = ICEIL(bound->outer.min - acc->fromIntY);
2781         bound->outeri.max = floor(bound->outer.max - acc->fromIntY);
2782 }
2783
2784 /*
2785  * this section computes the x value of the span at y
2786  * intersected with the specified face of the ellipse.
2787  *
2788  * this is the min/max X value over the set of normal
2789  * lines to the entire ellipse,  the equation of the
2790  * normal lines is:
2791  *
2792  *     ellipse_x h^2                   h^2
2793  * x = ------------ y + ellipse_x (1 - --- )
2794  *     ellipse_y w^2                   w^2
2795  *
2796  * compute the derivative with-respect-to ellipse_y and solve
2797  * for zero:
2798  *
2799  *       (w^2 - h^2) ellipse_y^3 + h^4 y
2800  * 0 = - ----------------------------------
2801  *       h w ellipse_y^2 sqrt (h^2 - ellipse_y^2)
2802  *
2803  *             (   h^4 y     )
2804  * ellipse_y = ( ----------  ) ^ (1/3)
2805  *             ( (h^2 - w^2) )
2806  *
2807  * The other two solutions to the equation are imaginary.
2808  *
2809  * This gives the position on the ellipse which generates
2810  * the normal with the largest/smallest x intersection point.
2811  *
2812  * Now compute the second derivative to check whether
2813  * the intersection is a minimum or maximum:
2814  *
2815  *    h (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2816  * -  -------------------------------------------
2817  *          w y0^3 (sqrt (h^2 - y^2)) ^ 3
2818  *
2819  * as we only care about the sign,
2820  *
2821  * - (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2822  *
2823  * or (to use accelerators),
2824  *
2825  * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2)
2826  *
2827  */
2828
2829 /*
2830  * computes the position on the ellipse whose normal line
2831  * intersects the given scan line maximally
2832  */
2833
2834 static double
2835 hookEllipseY (scan_y, bound, acc, left)
2836         double                  scan_y;
2837         struct arc_bound        *bound;
2838         struct accelerators     *acc;
2839         int                     left;
2840 {
2841         double  ret;
2842
2843         if (acc->h2mw2 == 0) {
2844                 if ( (scan_y > 0 && !left) || (scan_y < 0 && left) )
2845                         return bound->ellipse.min;
2846                 return bound->ellipse.max;
2847         }
2848         ret = (acc->h4 * scan_y) / (acc->h2mw2);
2849         if (ret >= 0)
2850                 return cbrt (ret);
2851         else
2852                 return -cbrt (-ret);
2853 }
2854
2855 /*
2856  * computes the X value of the intersection of the
2857  * given scan line with the right side of the lower hook
2858  */
2859
2860 static double
2861 hookX (scan_y, def, bound, acc, left)
2862         double                  scan_y;
2863         struct arc_def          *def;
2864         struct arc_bound        *bound;
2865         struct accelerators     *acc;
2866         int                     left;
2867 {
2868         double  ellipse_y, x;
2869         double  maxMin;
2870
2871         if (def->w != def->h) {
2872                 ellipse_y = hookEllipseY (scan_y, bound, acc, left);
2873                 if (boundedLe (ellipse_y, bound->ellipse)) {
2874                         /*
2875                          * compute the value of the second
2876                          * derivative
2877                          */
2878                         maxMin = ellipse_y*ellipse_y*ellipse_y * acc->h2mw2 -
2879                          acc->h2 * scan_y * (3 * ellipse_y*ellipse_y - 2*acc->h2);
2880                         if ((left && maxMin > 0) || (!left && maxMin < 0)) {
2881                                 if (ellipse_y == 0)
2882                                         return def->w + left ? -def->l : def->l;
2883                                 x = (acc->h2 * scan_y - ellipse_y * acc->h2mw2) *
2884                                         sqrt (acc->h2 - ellipse_y * ellipse_y) /
2885                                         (def->h * def->w * ellipse_y);
2886                                 return x;
2887                         }
2888                 }
2889         }
2890         if (left) {
2891                 if (acc->left.valid && boundedLe (scan_y, bound->left)) {
2892                         x = intersectLine (scan_y, acc->left);
2893                 } else {
2894                         if (acc->right.valid)
2895                                 x = intersectLine (scan_y, acc->right);
2896                         else
2897                                 x = def->w - def->l;
2898                 }
2899         } else {
2900                 if (acc->right.valid && boundedLe (scan_y, bound->right)) {
2901                         x = intersectLine (scan_y, acc->right);
2902                 } else {
2903                         if (acc->left.valid)
2904                                 x = intersectLine (scan_y, acc->left);
2905                         else
2906                                 x = def->w - def->l;
2907                 }
2908         }
2909         return x;
2910 }
2911
2912 /*
2913  * generate the set of spans with
2914  * the given y coordinate
2915  */
2916
2917 static void
2918 arcSpan (y, lx, lw, rx, rw, def, bounds, acc, mask)
2919         int                     y;
2920         int                     lx;
2921         int                     lw;
2922         int                     rx;
2923         int                     rw;
2924         struct arc_def          *def;
2925         struct arc_bound        *bounds;
2926         struct accelerators     *acc;
2927         int                     mask;
2928 {
2929         int linx, loutx, rinx, routx;
2930         double x, altx;
2931
2932         if (boundedLe (y, bounds->inneri)) {
2933             linx = -(lx + lw);
2934             rinx = rx;
2935         } else {
2936             /*
2937              * intersection with left face
2938              */
2939             x = hookX (y + acc->fromIntY, def, bounds, acc, 1);
2940             if (acc->right.valid &&
2941                 boundedLe (y + acc->fromIntY, bounds->right))
2942             {
2943                 altx = intersectLine (y + acc->fromIntY, acc->right);
2944                 if (altx < x)
2945                     x = altx;
2946             }
2947             linx = -ICEIL(acc->fromIntX - x);
2948             rinx = ICEIL(acc->fromIntX + x);
2949         }
2950         if (boundedLe (y, bounds->outeri)) {
2951             loutx = -lx;
2952             routx = rx + rw;
2953         } else {
2954             /*
2955              * intersection with right face
2956              */
2957             x = hookX (y + acc->fromIntY, def, bounds, acc, 0);
2958             if (acc->left.valid &&
2959                 boundedLe (y + acc->fromIntY, bounds->left))
2960             {
2961                 altx = x;
2962                 x = intersectLine (y + acc->fromIntY, acc->left);
2963                 if (x < altx)
2964                     x = altx;
2965             }
2966             loutx = -ICEIL(acc->fromIntX - x);
2967             routx = ICEIL(acc->fromIntX + x);
2968         }
2969         if (routx > rinx) {
2970             if (mask & 1)
2971                 newFinalSpan (acc->yorgu - y,
2972                               acc->xorg + rinx, acc->xorg + routx);
2973             if (mask & 8)
2974                 newFinalSpan (acc->yorgl + y,
2975                               acc->xorg + rinx, acc->xorg + routx);
2976         }
2977         if (loutx > linx) {
2978             if (mask & 2)
2979                 newFinalSpan (acc->yorgu - y,
2980                               acc->xorg - loutx, acc->xorg - linx);
2981             if (mask & 4)
2982                 newFinalSpan (acc->yorgl + y,
2983                               acc->xorg - loutx, acc->xorg - linx);
2984         }
2985 }
2986
2987 static void
2988 arcSpan0 (lx, lw, rx, rw, def, bounds, acc, mask)
2989         int                     lx;
2990         int                     lw;
2991         int                     rx;
2992         int                     rw;
2993         struct arc_def          *def;
2994         struct arc_bound        *bounds;
2995         struct accelerators     *acc;
2996         int                     mask;
2997 {
2998     double x;
2999
3000     if (boundedLe (0, bounds->inneri) &&
3001         acc->left.valid && boundedLe (0, bounds->left) &&
3002         acc->left.b > 0)
3003     {
3004         x = def->w - def->l;
3005         if (acc->left.b < x)
3006             x = acc->left.b;
3007         lw = ICEIL(acc->fromIntX - x) - lx;
3008         rw += rx;
3009         rx = ICEIL(acc->fromIntX + x);
3010         rw -= rx;
3011     }
3012     arcSpan (0, lx, lw, rx, rw, def, bounds, acc, mask);
3013 }
3014
3015 static void
3016 tailSpan (y, lw, rw, def, bounds, acc, mask)
3017         int                     y;
3018         int                     lw;
3019         int                     rw;
3020         struct arc_def          *def;
3021         struct arc_bound        *bounds;
3022         struct accelerators     *acc;
3023         int                     mask;
3024 {
3025     double yy, xalt, x, lx, rx;
3026     int n;
3027
3028     if (boundedLe(y, bounds->outeri))
3029         arcSpan (y, 0, lw, -rw, rw, def, bounds, acc, mask);
3030     else if (def->w != def->h) {
3031         yy = y + acc->fromIntY;
3032         x = tailX(yy, def, bounds, acc);
3033         if (yy == 0.0 && x == -rw - acc->fromIntX)
3034             return;
3035         if (acc->right.valid && boundedLe (yy, bounds->right)) {
3036             rx = x;
3037             lx = -x;
3038             xalt = intersectLine (yy, acc->right);
3039             if (xalt >= -rw - acc->fromIntX && xalt <= rx)
3040                 rx = xalt;
3041             n = ICEIL(acc->fromIntX + lx);
3042             if (lw > n) {
3043                 if (mask & 2)
3044                     newFinalSpan (acc->yorgu - y,
3045                                   acc->xorg + n, acc->xorg + lw);
3046                 if (mask & 4)
3047                     newFinalSpan (acc->yorgl + y,
3048                                   acc->xorg + n, acc->xorg + lw);
3049             }
3050             n = ICEIL(acc->fromIntX + rx);
3051             if (n > -rw) {
3052                 if (mask & 1)
3053                     newFinalSpan (acc->yorgu - y,
3054                                   acc->xorg - rw, acc->xorg + n);
3055                 if (mask & 8)
3056                     newFinalSpan (acc->yorgl + y,
3057                                   acc->xorg - rw, acc->xorg + n);
3058             }
3059         }
3060         arcSpan (y,
3061                  ICEIL(acc->fromIntX - x), 0,
3062                  ICEIL(acc->fromIntX + x), 0,
3063                  def, bounds, acc, mask);
3064     }
3065 }
3066
3067 /*
3068  * create whole arcs out of pieces.  This code is
3069  * very bad.
3070  */
3071
3072 static struct finalSpan **finalSpans = NULL;
3073 static int              finalMiny = 0, finalMaxy = -1;
3074 static int              finalSize = 0;
3075
3076 static int              nspans = 0;     /* total spans, not just y coords */
3077
3078 struct finalSpan {
3079         struct finalSpan        *next;
3080         int                     min, max;       /* x values */
3081 };
3082
3083 static struct finalSpan    *freeFinalSpans, *tmpFinalSpan;
3084
3085 # define allocFinalSpan()   (freeFinalSpans ?\
3086                                 ((tmpFinalSpan = freeFinalSpans), \
3087                                  (freeFinalSpans = freeFinalSpans->next), \
3088                                  (tmpFinalSpan->next = 0), \
3089                                  tmpFinalSpan) : \
3090                              realAllocSpan ())
3091
3092 # define SPAN_CHUNK_SIZE    128
3093
3094 struct finalSpanChunk {
3095         struct finalSpan        data[SPAN_CHUNK_SIZE];
3096         struct finalSpanChunk   *next;
3097 };
3098
3099 static struct finalSpanChunk    *chunks;
3100
3101 struct finalSpan *
3102 realAllocSpan ()
3103 {
3104         register struct finalSpanChunk  *newChunk;
3105         register struct finalSpan       *span;
3106         register int                    i;
3107
3108         newChunk = (struct finalSpanChunk *) xalloc (sizeof (struct finalSpanChunk));
3109         if (!newChunk)
3110                 return (struct finalSpan *) NULL;
3111         newChunk->next = chunks;
3112         chunks = newChunk;
3113         freeFinalSpans = span = newChunk->data + 1;
3114         for (i = 1; i < SPAN_CHUNK_SIZE-1; i++) {
3115                 span->next = span+1;
3116                 span++;
3117         }
3118         span->next = 0;
3119         span = newChunk->data;
3120         span->next = 0;
3121         return span;
3122 }
3123
3124 static void
3125 disposeFinalSpans ()
3126 {
3127         struct finalSpanChunk   *chunk, *next;
3128
3129         for (chunk = chunks; chunk; chunk = next) {
3130                 next = chunk->next;
3131                 xfree (chunk);
3132         }
3133         chunks = 0;
3134         freeFinalSpans = 0;
3135         xfree(finalSpans);
3136         finalSpans = 0;
3137 }
3138
3139 static void
3140 fillSpans (pDrawable, pGC)
3141     DrawablePtr pDrawable;
3142     GCPtr       pGC;
3143 {
3144         register struct finalSpan       *span;
3145         register DDXPointPtr            xSpan;
3146         register int                    *xWidth;
3147         register int                    i;
3148         register struct finalSpan       **f;
3149         register int                    spany;
3150         DDXPointPtr                     xSpans;
3151         int                             *xWidths;
3152
3153         if (nspans == 0)
3154                 return;
3155         xSpan = xSpans = (DDXPointPtr) ALLOCATE_LOCAL (nspans * sizeof (DDXPointRec));
3156         xWidth = xWidths = (int *) ALLOCATE_LOCAL (nspans * sizeof (int));
3157         if (xSpans && xWidths)
3158         {
3159             i = 0;
3160             f = finalSpans;
3161             for (spany = finalMiny; spany <= finalMaxy; spany++, f++) {
3162                     for (span = *f; span; span=span->next) {
3163                             if (span->max <= span->min)
3164                                     continue;
3165                             xSpan->x = span->min;
3166                             xSpan->y = spany;
3167                             ++xSpan;
3168                             *xWidth++ = span->max - span->min;
3169                             ++i;
3170                     }
3171             }
3172             (*pGC->ops->FillSpans) (pDrawable, pGC, i, xSpans, xWidths, TRUE);
3173         }
3174         disposeFinalSpans ();
3175         if (xSpans)
3176             DEALLOCATE_LOCAL (xSpans);
3177         if (xWidths)
3178             DEALLOCATE_LOCAL (xWidths);
3179         finalMiny = 0;
3180         finalMaxy = -1;
3181         finalSize = 0;
3182         nspans = 0;
3183 }
3184
3185 # define SPAN_REALLOC   100
3186
3187 # define findSpan(y) ((finalMiny <= (y) && (y) <= finalMaxy) ? \
3188                           &finalSpans[(y) - finalMiny] : \
3189                           realFindSpan (y))
3190
3191 static struct finalSpan **
3192 realFindSpan (y)
3193     int y;
3194 {
3195         struct finalSpan        **newSpans;
3196         int                     newSize, newMiny, newMaxy;
3197         int                     change;
3198         int                     i;
3199
3200         if (y < finalMiny || y > finalMaxy) {
3201                 if (!finalSize) {
3202                         finalMiny = y;
3203                         finalMaxy = y - 1;
3204                 }
3205                 if (y < finalMiny)
3206                         change = finalMiny - y;
3207                 else
3208                         change = y - finalMaxy;
3209                 if (change >= SPAN_REALLOC)
3210                         change += SPAN_REALLOC;
3211                 else
3212                         change = SPAN_REALLOC;
3213                 newSize = finalSize + change;
3214                 newSpans = (struct finalSpan **) xalloc
3215                                         (newSize * sizeof (struct finalSpan *));
3216                 if (!newSpans)
3217                     return (struct finalSpan **)NULL;
3218                 newMiny = finalMiny;
3219                 newMaxy = finalMaxy;
3220                 if (y < finalMiny)
3221                         newMiny = finalMiny - change;
3222                 else
3223                         newMaxy = finalMaxy + change;
3224                 if (finalSpans) {
3225                         memmove(((char *) newSpans) + (finalMiny-newMiny) * sizeof (struct finalSpan *),
3226                                 (char *) finalSpans,
3227                                finalSize * sizeof (struct finalSpan *));
3228                         xfree (finalSpans);
3229                 }
3230                 if ((i = finalMiny - newMiny) > 0)
3231                         bzero ((char *)newSpans, i * sizeof (struct finalSpan *));
3232                 if ((i = newMaxy - finalMaxy) > 0)
3233                         bzero ((char *)(newSpans + newSize - i),
3234                                i * sizeof (struct finalSpan *));
3235                 finalSpans = newSpans;
3236                 finalMaxy = newMaxy;
3237                 finalMiny = newMiny;
3238                 finalSize = newSize;
3239         }
3240         return &finalSpans[y - finalMiny];
3241 }
3242
3243 static void
3244 newFinalSpan (y, xmin, xmax)
3245     int         y;
3246     register int        xmin, xmax;
3247 {
3248         register struct finalSpan       *x;
3249         register struct finalSpan       **f;
3250         struct finalSpan                *oldx;
3251         struct finalSpan                *prev;
3252
3253         f = findSpan (y);
3254         if (!f)
3255             return;
3256         oldx = 0;
3257         for (;;) {
3258                 prev = 0;
3259                 for (x = *f; x; x=x->next) {
3260                         if (x == oldx) {
3261                                 prev = x;
3262                                 continue;
3263                         }
3264                         if (x->min <= xmax && xmin <= x->max) {
3265                                 if (oldx) {
3266                                         oldx->min = min (x->min, xmin);
3267                                         oldx->max = max (x->max, xmax);
3268                                         if (prev)
3269                                                 prev->next = x->next;
3270                                         else
3271                                                 *f = x->next;
3272                                         --nspans;
3273                                 } else {
3274                                         x->min = min (x->min, xmin);
3275                                         x->max = max (x->max, xmax);
3276                                         oldx = x;
3277                                 }
3278                                 xmin = oldx->min;
3279                                 xmax = oldx->max;
3280                                 break;
3281                         }
3282                         prev = x;
3283                 }
3284                 if (!x)
3285                         break;
3286         }
3287         if (!oldx) {
3288                 x = allocFinalSpan ();
3289                 if (x)
3290                 {
3291                     x->min = xmin;
3292                     x->max = xmax;
3293                     x->next = *f;
3294                     *f = x;
3295                     ++nspans;
3296                 }
3297         }
3298 }
3299
3300 static void
3301 mirrorSppPoint (quadrant, sppPoint)
3302         int             quadrant;
3303         SppPointPtr     sppPoint;
3304 {
3305         switch (quadrant) {
3306         case 0:
3307                 break;
3308         case 1:
3309                 sppPoint->x = -sppPoint->x;
3310                 break;
3311         case 2:
3312                 sppPoint->x = -sppPoint->x;
3313                 sppPoint->y = -sppPoint->y;
3314                 break;
3315         case 3:
3316                 sppPoint->y = -sppPoint->y;
3317                 break;
3318         }
3319         /*
3320          * and translate to X coordinate system
3321          */
3322         sppPoint->y = -sppPoint->y;
3323 }
3324
3325 /*
3326  * split an arc into pieces which are scan-converted
3327  * in the first-quadrant and mirrored into position.
3328  * This is necessary as the scan-conversion code can
3329  * only deal with arcs completely contained in the
3330  * first quadrant.
3331  */
3332
3333 static void
3334 drawArc (tarc, l, a0, a1, right, left)
3335         xArc *tarc;
3336         int     l, a0, a1;
3337         miArcFacePtr    right, left;    /* save end line points */
3338 {
3339         struct arc_def          def;
3340         struct accelerators     acc;
3341         int                     startq, endq, curq;
3342         int                     rightq, leftq, righta, lefta;
3343         miArcFacePtr            passRight, passLeft;
3344         int                     q0, q1, mask;
3345         struct band {
3346                 int     a0, a1;
3347                 int     mask;
3348         }       band[5], sweep[20];
3349         int                     bandno, sweepno;
3350         int                     i, j;
3351         int                     flipRight = 0, flipLeft = 0;
3352         int                     copyEnd = 0;
3353         miArcSpanData           *spdata;
3354         Bool                    mustFree;
3355
3356         spdata = miComputeWideEllipse(l, tarc, &mustFree);
3357         if (!spdata)
3358             return;
3359
3360         if (a1 < a0)
3361                 a1 += 360 * 64;
3362         startq = a0 / (90 * 64);
3363         if (a0 == a1)
3364             endq = startq;
3365         else
3366             endq = (a1-1) / (90 * 64);
3367         bandno = 0;
3368         curq = startq;
3369         rightq = -1;
3370         for (;;) {
3371                 switch (curq) {
3372                 case 0:
3373                         if (a0 > 90 * 64)
3374                                 q0 = 0;
3375                         else
3376                                 q0 = a0;
3377                         if (a1 < 360 * 64)
3378                                 q1 = min (a1, 90 * 64);
3379                         else
3380                                 q1 = 90 * 64;
3381                         if (curq == startq && a0 == q0 && rightq < 0) {
3382                                 righta = q0;
3383                                 rightq = curq;
3384                         }
3385                         if (curq == endq && a1 == q1) {
3386                                 lefta = q1;
3387                                 leftq = curq;
3388                         }
3389                         break;
3390                 case 1:
3391                         if (a1 < 90 * 64)
3392                                 q0 = 0;
3393                         else
3394                                 q0 = 180 * 64 - min (a1, 180 * 64);
3395                         if (a0 > 180 * 64)
3396                                 q1 = 90 * 64;
3397                         else
3398                                 q1 = 180 * 64 - max (a0, 90 * 64);
3399                         if (curq == startq && 180 * 64 - a0 == q1) {
3400                                 righta = q1;
3401                                 rightq = curq;
3402                         }
3403                         if (curq == endq && 180 * 64 - a1 == q0) {
3404                                 lefta = q0;
3405                                 leftq = curq;
3406                         }
3407                         break;
3408                 case 2:
3409                         if (a0 > 270 * 64)
3410                                 q0 = 0;
3411                         else
3412                                 q0 = max (a0, 180 * 64) - 180 * 64;
3413                         if (a1 < 180 * 64)
3414                                 q1 = 90 * 64;
3415                         else
3416                                 q1 = min (a1, 270 * 64) - 180 * 64;
3417                         if (curq == startq && a0 - 180*64 == q0) {
3418                                 righta = q0;
3419                                 rightq = curq;
3420                         }
3421                         if (curq == endq && a1 - 180 * 64 == q1) {
3422                                 lefta = q1;
3423                                 leftq = curq;
3424                         }
3425                         break;
3426                 case 3:
3427                         if (a1 < 270 * 64)
3428                                 q0 = 0;
3429                         else
3430                                 q0 = 360 * 64 - min (a1, 360 * 64);
3431                         q1 = 360 * 64 - max (a0, 270 * 64);
3432                         if (curq == startq && 360 * 64 - a0 == q1) {
3433                                 righta = q1;
3434                                 rightq = curq;
3435                         }
3436                         if (curq == endq && 360 * 64 - a1 == q0) {
3437                                 lefta = q0;
3438                                 leftq = curq;
3439                         }
3440                         break;
3441                 }
3442                 band[bandno].a0 = q0;
3443                 band[bandno].a1 = q1;
3444                 band[bandno].mask = 1 << curq;
3445                 bandno++;
3446                 if (curq == endq)
3447                         break;
3448                 curq++;
3449                 if (curq == 4) {
3450                         a0 = 0;
3451                         a1 -= 360 * 64;
3452                         curq = 0;
3453                         endq -= 4;
3454                 }
3455         }
3456         sweepno = 0;
3457         for (;;) {
3458                 q0 = 90 * 64;
3459                 mask = 0;
3460                 /*
3461                  * find left-most point
3462                  */
3463                 for (i = 0; i < bandno; i++)
3464                         if (band[i].a0 <= q0) {
3465                                 q0 = band[i].a0;
3466                                 q1 = band[i].a1;
3467                                 mask = band[i].mask;
3468                         }
3469                 if (!mask)
3470                         break;
3471                 /*
3472                  * locate next point of change
3473                  */
3474                 for (i = 0; i < bandno; i++)
3475                         if (!(mask & band[i].mask)) {
3476                                 if (band[i].a0 == q0) {
3477                                         if (band[i].a1 < q1)
3478                                                 q1 = band[i].a1;
3479                                         mask |= band[i].mask;
3480                                 } else if (band[i].a0 < q1)
3481                                         q1 = band[i].a0;
3482                         }
3483                 /*
3484                  * create a new sweep
3485                  */
3486                 sweep[sweepno].a0 = q0;
3487                 sweep[sweepno].a1 = q1;
3488                 sweep[sweepno].mask = mask;
3489                 sweepno++;
3490                 /*
3491                  * subtract the sweep from the affected bands
3492                  */
3493                 for (i = 0; i < bandno; i++)
3494                         if (band[i].a0 == q0) {
3495                                 band[i].a0 = q1;
3496                                 /*
3497                                  * check if this band is empty
3498                                  */
3499                                 if (band[i].a0 == band[i].a1)
3500                                         band[i].a1 = band[i].a0 = 90 * 64 + 1;
3501                         }
3502         }
3503         computeAcc (tarc, l, &def, &acc);
3504         for (j = 0; j < sweepno; j++) {
3505                 mask = sweep[j].mask;
3506                 passRight = passLeft = 0;
3507                 if (mask & (1 << rightq)) {
3508                         if (sweep[j].a0 == righta)
3509                                 passRight = right;
3510                         else if (sweep[j].a1 == righta) {
3511                                 passLeft = right;
3512                                 flipRight = 1;
3513                         }
3514                 }
3515                 if (mask & (1 << leftq)) {
3516                         if (sweep[j].a1 == lefta)
3517                         {
3518                                 if (passLeft)
3519                                         copyEnd = 1;
3520                                 passLeft = left;
3521                         }
3522                         else if (sweep[j].a0 == lefta) {
3523                                 if (passRight)
3524                                         copyEnd = 1;
3525                                 passRight = left;
3526                                 flipLeft = 1;
3527                         }
3528                 }
3529                 drawQuadrant (&def, &acc, sweep[j].a0, sweep[j].a1, mask,
3530                               passRight, passLeft, spdata);
3531         }
3532         /*
3533          * when copyEnd is set, both ends of the arc were computed
3534          * at the same time; drawQuadrant only takes one end though,
3535          * so the left end will be the only one holding the data.  Copy
3536          * it from there.
3537          */
3538         if (copyEnd)
3539                 *right = *left;
3540         /*
3541          * mirror the coordinates generated for the
3542          * faces of the arc
3543          */
3544         if (right) {
3545                 mirrorSppPoint (rightq, &right->clock);
3546                 mirrorSppPoint (rightq, &right->center);
3547                 mirrorSppPoint (rightq, &right->counterClock);
3548                 if (flipRight) {
3549                         SppPointRec     temp;
3550
3551                         temp = right->clock;
3552                         right->clock = right->counterClock;
3553                         right->counterClock = temp;
3554                 }
3555         }
3556         if (left) {
3557                 mirrorSppPoint (leftq,  &left->counterClock);
3558                 mirrorSppPoint (leftq,  &left->center);
3559                 mirrorSppPoint (leftq,  &left->clock);
3560                 if (flipLeft) {
3561                         SppPointRec     temp;
3562
3563                         temp = left->clock;
3564                         left->clock = left->counterClock;
3565                         left->counterClock = temp;
3566                 }
3567         }
3568         if (mustFree)
3569             xfree(spdata);
3570 }
3571
3572 static void
3573 drawQuadrant (def, acc, a0, a1, mask, right, left, spdata)
3574         struct arc_def          *def;
3575         struct accelerators     *acc;
3576         int                     a0, a1;
3577         int                     mask;
3578         miArcFacePtr            right, left;
3579         miArcSpanData           *spdata;
3580 {
3581         struct arc_bound        bound;
3582         double                  yy, x, xalt;
3583         int                     y, miny, maxy;
3584         int                     n;
3585         miArcSpan               *span;
3586
3587         def->a0 = ((double) a0) / 64.0;
3588         def->a1 = ((double) a1) / 64.0;
3589         computeBound (def, &bound, acc, right, left);
3590         yy = bound.inner.min;
3591         if (bound.outer.min < yy)
3592             yy = bound.outer.min;
3593         miny = ICEIL(yy - acc->fromIntY);
3594         yy = bound.inner.max;
3595         if (bound.outer.max > yy)
3596             yy = bound.outer.max;
3597         maxy = floor(yy - acc->fromIntY);
3598         y = spdata->k;
3599         span = spdata->spans;
3600         if (spdata->top)
3601         {
3602             if (a1 == 90 * 64 && (mask & 1))
3603                 newFinalSpan (acc->yorgu - y - 1, acc->xorg, acc->xorg + 1);
3604             span++;
3605         }
3606         for (n = spdata->count1; --n >= 0; )
3607         {
3608             if (y < miny)
3609                 return;
3610             if (y <= maxy) {
3611                 arcSpan (y,
3612                          span->lx, -span->lx, 0, span->lx + span->lw,
3613                          def, &bound, acc, mask);
3614                 if (span->rw + span->rx)
3615                     tailSpan (y, -span->rw, -span->rx, def, &bound, acc, mask);
3616             }
3617             y--;
3618             span++;
3619         }
3620         if (y < miny)
3621             return;
3622         if (spdata->hole)
3623         {
3624             if (y <= maxy)
3625                 arcSpan (y, 0, 0, 0, 1, def, &bound, acc, mask & 0xc);
3626         }
3627         for (n = spdata->count2; --n >= 0; )
3628         {
3629             if (y < miny)
3630                 return;
3631             if (y <= maxy)
3632                 arcSpan (y, span->lx, span->lw, span->rx, span->rw,
3633                          def, &bound, acc, mask);
3634             y--;
3635             span++;
3636         }
3637         if (spdata->bot && miny <= y && y <= maxy)
3638         {
3639             n = mask;
3640             if (y == miny)
3641                 n &= 0xc;
3642             if (span->rw <= 0) {
3643                 arcSpan0 (span->lx, -span->lx, 0, span->lx + span->lw,
3644                           def, &bound, acc, n);
3645                 if (span->rw + span->rx)
3646                     tailSpan (y, -span->rw, -span->rx, def, &bound, acc, n);
3647             }
3648             else
3649                 arcSpan0 (span->lx, span->lw, span->rx, span->rw,
3650                           def, &bound, acc, n);
3651             y--;
3652         }
3653         while (y >= miny) {
3654             yy = y + acc->fromIntY;
3655             if (def->w == def->h) {
3656                 xalt = def->w - def->l;
3657                 x = -sqrt(xalt * xalt - yy * yy);
3658             } else {
3659                 x = tailX(yy, def, &bound, acc);
3660                 if (acc->left.valid && boundedLe (yy, bound.left)) {
3661                     xalt = intersectLine (yy, acc->left);
3662                     if (xalt < x)
3663                         x = xalt;
3664                 }
3665                 if (acc->right.valid && boundedLe (yy, bound.right)) {
3666                     xalt = intersectLine (yy, acc->right);
3667                     if (xalt < x)
3668                         x = xalt;
3669                 }
3670             }
3671             arcSpan (y,
3672                      ICEIL(acc->fromIntX - x), 0,
3673                      ICEIL(acc->fromIntX + x), 0,
3674                      def, &bound, acc, mask);
3675             y--;
3676         }
3677 }