Pileus Git - ~andy/gtk/blob - gdk/linux-fb/miarc.c

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