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         g_free(spdata);
 839         spdata = (miArcSpanData *)g_malloc(sizeof(miArcSpanData) +
 840                                          sizeof(miArcSpan) * (k + 2));
 841         lruent->spdata = spdata;
 842         if (!spdata)
 843         {
 844             lruent->lrustamp = 0;
 845             lruent->lw = 0;
 846             return spdata;
 847         }
 848         spdata->spans = (miArcSpan *)(spdata + 1);
 849         spdata->k = k;
 850     }
 851     spdata->top = !(lw & 1) && !(parc->width & 1);
 852     spdata->bot = !(parc->height & 1);
 853     lruent->lrustamp = ++lrustamp;
 854     lruent->lw = lw;
 855     lruent->width = parc->width;
 856     lruent->height = parc->height;
 857     if (lruent != &fakeent)
 858         lastCacheHit = lruent;
 859     if (parc->width == parc->height)
 860         miComputeCircleSpans(lw, parc, spdata);
 861     else
 862         miComputeEllipseSpans(lw, parc, spdata);
 863     return spdata;
 864 }
 865
 866 static void
 867 miFillWideEllipse(GdkDrawable *pDraw, GdkGC *pGC, miArc *parc)
 868 {
 869     GdkSpan* points;
 870     register GdkSpan* pts;
 871     miArcSpanData *spdata;
 872     gboolean mustFree;
 873     register miArcSpan *span;
 874     register int xorg, yorgu, yorgl;
 875     register int n;
 876
 877     yorgu = parc->height + GDK_GC_FBDATA(pGC)->values.line_width;
 878     points = ALLOCATE_LOCAL(sizeof(GdkSpan) * yorgu * 2);
 879     spdata = miComputeWideEllipse(GDK_GC_FBDATA(pGC)->values.line_width, parc, &mustFree);
 880     if (!spdata)
 881     {
 882         DEALLOCATE_LOCAL(points);
 883         return;
 884     }
 885     pts = points;
 886     span = spdata->spans;
 887     xorg = parc->x + (parc->width >> 1);
 888     yorgu = parc->y + (parc->height >> 1);
 889     yorgl = yorgu + (parc->height & 1);
 890     yorgu -= spdata->k;
 891     yorgl += spdata->k;
 892     if (spdata->top)
 893     {
 894         pts->x = xorg;
 895         pts->y = yorgu - 1;
 896         pts->width = 1;
 897         pts++;
 898         span++;
 899     }
 900     for (n = spdata->count1; --n >= 0; )
 901     {
 902         pts[0].x = xorg + span->lx;
 903         pts[0].y = yorgu;
 904         pts[0].width = span->lw;
 905         pts[1] = pts[0];
 906         pts[1].y = yorgl;
 907         yorgu++;
 908         yorgl--;
 909         pts += 2;
 910         span++;
 911     }
 912     if (spdata->hole)
 913     {
 914         pts[0].x = xorg;
 915         pts[0].y = yorgl;
 916         pts[0].width = 1;
 917         pts++;
 918     }
 919     for (n = spdata->count2; --n >= 0; )
 920     {
 921         pts[0].x = xorg + span->lx;
 922         pts[0].y = yorgu;
 923         pts[0].width = span->lw;
 924
 925         pts[1].x = xorg + span->rx;
 926         pts[1].y = pts[0].y;
 927         pts[1].width = span->rw;
 928
 929         pts[2].x = pts[0].x;
 930         pts[2].y = yorgl;
 931         pts[2].width = pts[0].width;
 932
 933         pts[3].x = pts[1].x;
 934         pts[3].y = pts[2].y;
 935         pts[3].width = pts[1].width;
 936
 937         yorgu++;
 938         yorgl--;
 939         pts += 4;
 940         span++;
 941     }
 942     if (spdata->bot)
 943     {
 944         if (span->rw <= 0)
 945         {
 946             pts[0].x = xorg + span->lx;
 947             pts[0].y = yorgu;
 948             pts[0].width = span->lw;
 949             pts++;
 950         }
 951         else
 952         {
 953             pts[0].x = xorg + span->lx;
 954             pts[0].y = yorgu;
 955             pts[0].width = span->lw;
 956             pts[1].x = xorg + span->rx;
 957             pts[1].y = pts[0].y;
 958             pts[1].width = span->rw;
 959             pts += 2;
 960         }
 961     }
 962     if (mustFree)
 963         g_free(spdata);
 964
 965     gdk_fb_fill_spans(pDraw, pGC, points, pts - points, FALSE);
 966
 967     DEALLOCATE_LOCAL(points);
 968 }
 969
 970 /*
 971  * miPolyArc strategy:
 972  *
 973  * If arc is zero width and solid, we don't have to worry about the rasterop
 974  * or join styles.  For wide solid circles, we use a fast integer algorithm.
 975  * For wide solid ellipses, we use special case floating point code.
 976  * Otherwise, we set up pDrawTo and pGCTo according to the rasterop, then
 977  * draw using pGCTo and pDrawTo.  If the raster-op was "tricky," that is,
 978  * if it involves the destination, then we use PushPixels to move the bits
 979  * from the scratch drawable to pDraw. (See the wide line code for a
 980  * fuller explanation of this.)
 981  */
 982
 983 void
 984 miPolyArc(GdkDrawable *pDraw, GdkGC *pGC, int narcs, miArc *parcs)
 985 {
 986     register int                i;
 987     miArc                       *parc;
 988     int                         xMin, xMax, yMin, yMax;
 989     int                         pixmapWidth = 0, pixmapHeight = 0;
 990     int                         xOrg = 0, yOrg = 0;
 991     int                         width;
 992     gboolean                    fTricky;
 993     GdkDrawable*                pDrawTo;
 994     GdkColor                    fg, bg;
 995     GdkGC*                      pGCTo;
 996     miPolyArcPtr                polyArcs;
 997     int                         cap[2], join[2];
 998     int                         iphase;
 999     int                         halfWidth;
1000     GdkGCValues gcv;
1001
1002     width = GDK_GC_FBDATA(pGC)->values.line_width;
1003     if(width == 0 && GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_SOLID)
1004     {
1005         for(i = narcs, parc = parcs; --i >= 0; parc++)
1006             miArcSegment( pDraw, pGC, *parc,
1007             (miArcFacePtr) 0, (miArcFacePtr) 0 );
1008         fillSpans (pDraw, pGC);
1009     }
1010     else
1011     {
1012         if ((GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_SOLID) && narcs)
1013         {
1014             while (parcs->width && parcs->height &&
1015                    (parcs->angle2 >= FULLCIRCLE ||
1016                     parcs->angle2 <= -FULLCIRCLE))
1017             {
1018                 miFillWideEllipse(pDraw, pGC, parcs);
1019                 if (!--narcs)
1020                     return;
1021                 parcs++;
1022             }
1023         }
1024
1025         /* Set up pDrawTo and pGCTo based on the rasterop */
1026         switch(GDK_GC_FBDATA(pGC)->alu)
1027         {
1028           case GDK_CLEAR:               /* 0 */
1029           case GDK_COPY:                /* src */
1030           case GDK_COPY_INVERT: /* NOT src */
1031           case GDK_SET:         /* 1 */
1032             fTricky = FALSE;
1033             pDrawTo = pDraw;
1034             pGCTo = pGC;
1035             break;
1036           default:
1037             fTricky = TRUE;
1038
1039             /* find bounding box around arcs */
1040             xMin = yMin = SHRT_MAX;
1041             xMax = yMax = SHRT_MIN;
1042
1043             for(i = narcs, parc = parcs; --i >= 0; parc++)
1044             {
1045                 xMin = MIN (xMin, parc->x);
1046                 yMin = MIN (yMin, parc->y);
1047                 xMax = MAX (xMax, (parc->x + (int) parc->width));
1048                 yMax = MAX (yMax, (parc->y + (int) parc->height));
1049             }
1050
1051             /* expand box to deal with line widths */
1052             halfWidth = (width + 1)/2;
1053             xMin -= halfWidth;
1054             yMin -= halfWidth;
1055             xMax += halfWidth;
1056             yMax += halfWidth;
1057
1058             /* compute pixmap size; limit it to size of drawable */
1059             xOrg = MAX(xMin, 0);
1060             yOrg = MAX(yMin, 0);
1061             pixmapWidth = MIN(xMax, GDK_DRAWABLE_FBDATA(pDraw)->width) - xOrg;
1062             pixmapHeight = MIN(yMax, GDK_DRAWABLE_FBDATA(pDraw)->height) - yOrg;
1063
1064             /* if nothing left, return */
1065             if ( (pixmapWidth <= 0) || (pixmapHeight <= 0) ) return;
1066
1067             for(i = narcs, parc = parcs; --i >= 0; parc++)
1068             {
1069                 parc->x -= xOrg;
1070                 parc->y -= yOrg;
1071             }
1072
1073             /* set up scratch GC */
1074             /* allocate a 1 bit deep pixmap of the appropriate size, and
1075              * validate it */
1076             pDrawTo = gdk_pixmap_new(NULL, pixmapWidth, pixmapHeight, 1);
1077             if (!pDrawTo)
1078               return;
1079
1080             pGCTo = gdk_gc_new(pDrawTo);
1081             if (!pGCTo)
1082               {
1083                 gdk_pixmap_unref(pDrawTo);
1084                 return;
1085               }
1086             gdk_gc_set_function(pGCTo, GDK_COPY);
1087             memset(&gcv.background, 0, sizeof(GdkColor));
1088             gcv.foreground.pixel = 1;
1089             gcv.foreground.red = gcv.foreground.green = gcv.foreground.blue = 1;
1090             gdk_gc_set_foreground(pGCTo, &gcv.foreground);
1091             gdk_gc_set_background(pGCTo, &gcv.background);
1092             gdk_gc_set_line_attributes(pGCTo,
1093                                        GDK_GC_FBDATA(pGC)->values.line_width,
1094                                        GDK_GC_FBDATA(pGC)->values.line_style,
1095                                        GDK_GC_FBDATA(pGC)->values.cap_style,
1096                                        GDK_GC_FBDATA(pGC)->values.join_style);
1097             gdk_fb_drawable_clear(pDrawTo);
1098         }
1099
1100         fg = GDK_GC_FBDATA(pGC)->values.foreground;
1101         bg = GDK_GC_FBDATA(pGC)->values.background;
1102         if ((GDK_GC_FBDATA(pGC)->values.fill == GDK_TILED) ||
1103             (GDK_GC_FBDATA(pGC)->values.fill == GDK_OPAQUE_STIPPLED))
1104             bg = fg; /* the protocol sez these don't cause color changes */
1105
1106         polyArcs = miComputeArcs (parcs, narcs, pGC);
1107
1108         if (!polyArcs)
1109         {
1110             if (fTricky) {
1111               gdk_pixmap_unref(pDrawTo);
1112               gdk_gc_unref(pGCTo);
1113             }
1114             return;
1115         }
1116
1117         cap[0] = cap[1] = 0;
1118         join[0] = join[1] = 0;
1119         for (iphase = ((GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_DOUBLE_DASH) ? 1 : 0);
1120              iphase >= 0;
1121              iphase--)
1122         {
1123             if (iphase == 1)
1124               gdk_gc_set_foreground(pGC, &bg);
1125             else if (GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_DOUBLE_DASH)
1126               gdk_gc_set_foreground(pGC, &fg);
1127             for (i = 0; i < polyArcs[iphase].narcs; i++) {
1128                 miArcDataPtr    arcData;
1129
1130                 arcData = &polyArcs[iphase].arcs[i];
1131                 miArcSegment(pDrawTo, pGCTo, arcData->arc,
1132                              &arcData->bounds[RIGHT_END],
1133                              &arcData->bounds[LEFT_END]);
1134                 if (polyArcs[iphase].arcs[i].render) {
1135                     fillSpans (pDrawTo, pGCTo);
1136                     /*
1137                      * don't cap self-joining arcs
1138                      */
1139                     if (polyArcs[iphase].arcs[i].selfJoin &&
1140                         cap[iphase] < polyArcs[iphase].arcs[i].cap)
1141                         cap[iphase]++;
1142                     while (cap[iphase] < polyArcs[iphase].arcs[i].cap) {
1143                         int     arcIndex, end;
1144                         miArcDataPtr    arcData0;
1145
1146                         arcIndex = polyArcs[iphase].caps[cap[iphase]].arcIndex;
1147                         end = polyArcs[iphase].caps[cap[iphase]].end;
1148                         arcData0 = &polyArcs[iphase].arcs[arcIndex];
1149                         miArcCap (pDrawTo, pGCTo,
1150                                   &arcData0->bounds[end], end,
1151                                   arcData0->arc.x, arcData0->arc.y,
1152                                   (double) arcData0->arc.width / 2.0,
1153                                   (double) arcData0->arc.height / 2.0);
1154                         ++cap[iphase];
1155                     }
1156                     while (join[iphase] < polyArcs[iphase].arcs[i].join) {
1157                         int     arcIndex0, arcIndex1, end0, end1;
1158                         int     phase0, phase1;
1159                         miArcDataPtr    arcData0, arcData1;
1160                         miArcJoinPtr    joinp;
1161
1162                         joinp = &polyArcs[iphase].joins[join[iphase]];
1163                         arcIndex0 = joinp->arcIndex0;
1164                         end0 = joinp->end0;
1165                         arcIndex1 = joinp->arcIndex1;
1166                         end1 = joinp->end1;
1167                         phase0 = joinp->phase0;
1168                         phase1 = joinp->phase1;
1169                         arcData0 = &polyArcs[phase0].arcs[arcIndex0];
1170                         arcData1 = &polyArcs[phase1].arcs[arcIndex1];
1171                         miArcJoin (pDrawTo, pGCTo,
1172                                   &arcData0->bounds[end0],
1173                                   &arcData1->bounds[end1],
1174                                   arcData0->arc.x, arcData0->arc.y,
1175                                   (double) arcData0->arc.width / 2.0,
1176                                   (double) arcData0->arc.height / 2.0,
1177                                   arcData1->arc.x, arcData1->arc.y,
1178                                   (double) arcData1->arc.width / 2.0,
1179                                   (double) arcData1->arc.height / 2.0);
1180                         ++join[iphase];
1181                     }
1182                     if (fTricky) {
1183                       gdk_fb_draw_drawable(pDraw, pGC, pDrawTo, 0, 0, xOrg, yOrg, pixmapWidth, pixmapHeight);
1184                       gdk_fb_drawable_clear(pDrawTo);
1185                     }
1186                 }
1187             }
1188         }
1189         miFreeArcs(polyArcs, pGC);
1190
1191         if(fTricky)
1192         {
1193           gdk_pixmap_unref(pDrawTo);
1194           gdk_gc_unref(pGCTo);
1195         }
1196     }
1197 }
1198
1199 static double
1200 angleBetween (SppPointRec center, SppPointRec point1, SppPointRec point2)
1201 {
1202         double  a1, a2, a;
1203
1204         /*
1205          * reflect from X coordinates back to ellipse
1206          * coordinates -- y increasing upwards
1207          */
1208         a1 = miDatan2 (- (point1.y - center.y), point1.x - center.x);
1209         a2 = miDatan2 (- (point2.y - center.y), point2.x - center.x);
1210         a = a2 - a1;
1211         if (a <= -180.0)
1212                 a += 360.0;
1213         else if (a > 180.0)
1214                 a -= 360.0;
1215         return a;
1216 }
1217
1218 static void
1219 translateBounds (miArcFacePtr b, int x, int y, double fx, double fy)
1220 {
1221         fx += x;
1222         fy += y;
1223         b->clock.x -= fx;
1224         b->clock.y -= fy;
1225         b->center.x -= fx;
1226         b->center.y -= fy;
1227         b->counterClock.x -= fx;
1228         b->counterClock.y -= fy;
1229 }
1230
1231 static void
1232 miArcJoin (GdkDrawable *pDraw, GdkGC *pGC, miArcFacePtr pLeft, miArcFacePtr pRight,
1233            int xOrgLeft, int yOrgLeft, double xFtransLeft, double yFtransLeft,
1234            int xOrgRight, int yOrgRight, double xFtransRight, double yFtransRight)
1235 {
1236         SppPointRec     center, corner, otherCorner;
1237         SppPointRec     poly[5], e;
1238         SppPointPtr     pArcPts;
1239         int             cpt;
1240         SppArcRec       arc;
1241         miArcFaceRec    Right, Left;
1242         int             polyLen = 0;
1243         int             xOrg, yOrg;
1244         double          xFtrans, yFtrans;
1245         double          a;
1246         double          ae, ac2, ec2, bc2, de;
1247         double          width;
1248
1249         xOrg = (xOrgRight + xOrgLeft) / 2;
1250         yOrg = (yOrgRight + yOrgLeft) / 2;
1251         xFtrans = (xFtransLeft + xFtransRight) / 2;
1252         yFtrans = (yFtransLeft + yFtransRight) / 2;
1253         Right = *pRight;
1254         translateBounds (&Right, xOrg - xOrgRight, yOrg - yOrgRight,
1255                                  xFtrans - xFtransRight, yFtrans - yFtransRight);
1256         Left = *pLeft;
1257         translateBounds (&Left, xOrg - xOrgLeft, yOrg - yOrgLeft,
1258                                  xFtrans - xFtransLeft, yFtrans - yFtransLeft);
1259         pRight = &Right;
1260         pLeft = &Left;
1261
1262         if (pRight->clock.x == pLeft->counterClock.x &&
1263             pRight->clock.y == pLeft->counterClock.y)
1264                 return;
1265         center = pRight->center;
1266         if (0 <= (a = angleBetween (center, pRight->clock, pLeft->counterClock))
1267             && a <= 180.0)
1268         {
1269                 corner = pRight->clock;
1270                 otherCorner = pLeft->counterClock;
1271         } else {
1272                 a = angleBetween (center, pLeft->clock, pRight->counterClock);
1273                 corner = pLeft->clock;
1274                 otherCorner = pRight->counterClock;
1275         }
1276         switch (GDK_GC_FBDATA(pGC)->values.join_style) {
1277         case GDK_JOIN_ROUND:
1278                 width = (GDK_GC_FBDATA(pGC)->values.line_width ? (double)GDK_GC_FBDATA(pGC)->values.line_width : (double)1);
1279
1280                 arc.x = center.x - width/2;
1281                 arc.y = center.y - width/2;
1282                 arc.width = width;
1283                 arc.height = width;
1284                 arc.angle1 = -miDatan2 (corner.y - center.y, corner.x - center.x);
1285                 arc.angle2 = a;
1286                 pArcPts = (SppPointPtr) g_malloc (3 * sizeof (SppPointRec));
1287                 if (!pArcPts)
1288                     return;
1289                 pArcPts[0].x = otherCorner.x;
1290                 pArcPts[0].y = otherCorner.y;
1291                 pArcPts[1].x = center.x;
1292                 pArcPts[1].y = center.y;
1293                 pArcPts[2].x = corner.x;
1294                 pArcPts[2].y = corner.y;
1295                 if( (cpt = miGetArcPts(&arc, 3, &pArcPts)) )
1296                 {
1297                         /* by drawing with miFillSppPoly and setting the endpoints of the arc
1298                          * to be the corners, we assure that the cap will meet up with the
1299                          * rest of the line */
1300                         miFillSppPoly(pDraw, pGC, cpt, pArcPts, xOrg, yOrg, xFtrans, yFtrans);
1301                 }
1302                 g_free(pArcPts);
1303                 return;
1304         case GDK_JOIN_MITER:
1305                 /*
1306                  * don't miter arcs with less than 11 degrees between them
1307                  */
1308                 if (a < 169.0) {
1309                         poly[0] = corner;
1310                         poly[1] = center;
1311                         poly[2] = otherCorner;
1312                         bc2 = (corner.x - otherCorner.x) * (corner.x - otherCorner.x) +
1313                               (corner.y - otherCorner.y) * (corner.y - otherCorner.y);
1314                         ec2 = bc2 / 4;
1315                         ac2 = (corner.x - center.x) * (corner.x - center.x) +
1316                               (corner.y - center.y) * (corner.y - center.y);
1317                         ae = sqrt (ac2 - ec2);
1318                         de = ec2 / ae;
1319                         e.x = (corner.x + otherCorner.x) / 2;
1320                         e.y = (corner.y + otherCorner.y) / 2;
1321                         poly[3].x = e.x + de * (e.x - center.x) / ae;
1322                         poly[3].y = e.y + de * (e.y - center.y) / ae;
1323                         poly[4] = corner;
1324                         polyLen = 5;
1325                         break;
1326                 }
1327         case GDK_JOIN_BEVEL:
1328                 poly[0] = corner;
1329                 poly[1] = center;
1330                 poly[2] = otherCorner;
1331                 poly[3] = corner;
1332                 polyLen = 4;
1333                 break;
1334         }
1335         miFillSppPoly (pDraw, pGC, polyLen, poly, xOrg, yOrg, xFtrans, yFtrans);
1336 }
1337
1338 /*ARGSUSED*/
1339 static void
1340 miArcCap (GdkDrawable *pDraw, GdkGC *pGC, miArcFacePtr pFace, int end,
1341           int xOrg, int yOrg, double xFtrans, double yFtrans)
1342 {
1343         SppPointRec     corner, otherCorner, center, endPoint, poly[5];
1344
1345         corner = pFace->clock;
1346         otherCorner = pFace->counterClock;
1347         center = pFace->center;
1348         switch (GDK_GC_FBDATA(pGC)->values.cap_style) {
1349         case GDK_CAP_PROJECTING:
1350                 poly[0].x = otherCorner.x;
1351                 poly[0].y = otherCorner.y;
1352                 poly[1].x = corner.x;
1353                 poly[1].y = corner.y;
1354                 poly[2].x = corner.x -
1355                                 (center.y - corner.y);
1356                 poly[2].y = corner.y +
1357                                 (center.x - corner.x);
1358                 poly[3].x = otherCorner.x -
1359                                 (otherCorner.y - center.y);
1360                 poly[3].y = otherCorner.y +
1361                                 (otherCorner.x - center.x);
1362                 poly[4].x = otherCorner.x;
1363                 poly[4].y = otherCorner.y;
1364                 miFillSppPoly (pDraw, pGC, 5, poly, xOrg, yOrg, xFtrans, yFtrans);
1365                 break;
1366         case GDK_CAP_ROUND:
1367                 /*
1368                  * miRoundCap just needs these to be unequal.
1369                  */
1370                 endPoint = center;
1371                 endPoint.x = endPoint.x + 100;
1372                 miRoundCap (pDraw, pGC, center, endPoint, corner, otherCorner, 0,
1373                             -xOrg, -yOrg, xFtrans, yFtrans);
1374                 break;
1375         default:
1376           break;
1377         }
1378 }
1379
1380 /* MIROUNDCAP -- a private helper function
1381  * Put Rounded cap on end. pCenter is the center of this end of the line
1382  * pEnd is the center of the other end of the line. pCorner is one of the
1383  * two corners at this end of the line.
1384  * NOTE:  pOtherCorner must be counter-clockwise from pCorner.
1385  */
1386 /*ARGSUSED*/
1387 static void miRoundCap(GdkDrawable *pDraw, GdkGC *pGC, SppPointRec pCenter, SppPointRec pEnd, SppPointRec pCorner,
1388                        SppPointRec pOtherCorner, int fLineEnd, int xOrg, int yOrg,
1389                        double xFtrans, double yFtrans)
1390 {
1391     int         cpt;
1392     double      width;
1393     SppArcRec   arc;
1394     SppPointPtr pArcPts;
1395
1396     width = (GDK_GC_FBDATA(pGC)->values.line_width ? (double)GDK_GC_FBDATA(pGC)->values.line_width : (double)1);
1397
1398     arc.x = pCenter.x - width/2;
1399     arc.y = pCenter.y - width/2;
1400     arc.width = width;
1401     arc.height = width;
1402     arc.angle1 = -(miDatan2 (pCorner.y - pCenter.y, pCorner.x - pCenter.x));
1403     if(PTISEQUAL(pCenter, pEnd))
1404         arc.angle2 = - 180.0;
1405     else {
1406         arc.angle2 = -miDatan2 (pOtherCorner.y - pCenter.y, pOtherCorner.x - pCenter.x) - arc.angle1;
1407         if (arc.angle2 < 0)
1408             arc.angle2 += 360.0;
1409     }
1410     pArcPts = (SppPointPtr) NULL;
1411     if( (cpt = miGetArcPts(&arc, 0, &pArcPts)) )
1412     {
1413         /* by drawing with miFillSppPoly and setting the endpoints of the arc
1414          * to be the corners, we assure that the cap will meet up with the
1415          * rest of the line */
1416         miFillSppPoly(pDraw, pGC, cpt, pArcPts, -xOrg, -yOrg, xFtrans, yFtrans);
1417     }
1418     g_free(pArcPts);
1419 }
1420
1421 /*
1422  * To avoid inaccuracy at the cardinal points, use trig functions
1423  * which are exact for those angles
1424  */
1425
1426 #ifndef M_PI
1427 #define M_PI    3.14159265358979323846
1428 #endif
1429 #ifndef M_PI_2
1430 #define M_PI_2  1.57079632679489661923
1431 #endif
1432
1433 # define Dsin(d)        ((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))
1434 # define Dcos(d)        ((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))
1435 # define mod(a,b)       ((a) >= 0 ? (a) % (b) : (b) - (-a) % (b))
1436
1437 static double
1438 miDcos (double a)
1439 {
1440         int     i;
1441
1442         if (floor (a/90) == a/90) {
1443                 i = (int) (a/90.0);
1444                 switch (mod (i, 4)) {
1445                 case 0: return 1;
1446                 case 1: return 0;
1447                 case 2: return -1;
1448                 case 3: return 0;
1449                 }
1450         }
1451         return cos (a * M_PI / 180.0);
1452 }
1453
1454 static double
1455 miDsin (double a)
1456 {
1457         int     i;
1458
1459         if (floor (a/90) == a/90) {
1460                 i = (int) (a/90.0);
1461                 switch (mod (i, 4)) {
1462                 case 0: return 0;
1463                 case 1: return 1;
1464                 case 2: return 0;
1465                 case 3: return -1;
1466                 }
1467         }
1468         return sin (a * M_PI / 180.0);
1469 }
1470
1471 static double
1472 miDasin (double v)
1473 {
1474     if (v == 0)
1475         return 0.0;
1476     if (v == 1.0)
1477         return 90.0;
1478     if (v == -1.0)
1479         return -90.0;
1480     return asin(v) * (180.0 / M_PI);
1481 }
1482
1483 static double
1484 miDatan2 (double dy, double dx)
1485 {
1486     if (dy == 0) {
1487         if (dx >= 0)
1488             return 0.0;
1489         return 180.0;
1490     } else if (dx == 0) {
1491         if (dy > 0)
1492             return 90.0;
1493         return -90.0;
1494     } else if (fabs (dy) == fabs (dx)) {
1495         if (dy > 0) {
1496             if (dx > 0)
1497                 return 45.0;
1498             return 135.0;
1499         } else {
1500             if (dx > 0)
1501                 return 315.0;
1502             return 225.0;
1503         }
1504     } else {
1505         return atan2 (dy, dx) * (180.0 / M_PI);
1506     }
1507 }
1508
1509 /* MIGETARCPTS -- Converts an arc into a set of line segments -- a helper
1510  * routine for filled arc and line (round cap) code.
1511  * Returns the number of points in the arc.  Note that it takes a pointer
1512  * to a pointer to where it should put the points and an index (cpt).
1513  * This procedure allocates the space necessary to fit the arc points.
1514  * Sometimes it's convenient for those points to be at the end of an existing
1515  * array. (For example, if we want to leave a spare point to make sectors
1516  * instead of segments.)  So we pass in the g_malloc()ed chunk that contains the
1517  * array and an index saying where we should start stashing the points.
1518  * If there isn't an array already, we just pass in a null pointer and
1519  * count on g_realloc() to handle the null pointer correctly.
1520  */
1521 static int
1522 miGetArcPts(SppArcPtr parc, int cpt, SppPointPtr *ppPts)
1523 #if 0
1524     SppArcPtr   parc;   /* points to an arc */
1525     int         cpt;    /* number of points already in arc list */
1526     SppPointPtr *ppPts; /* pointer to pointer to arc-list -- modified */
1527 #endif
1528 {
1529     double      st,     /* Start Theta, start angle */
1530                 et,     /* End Theta, offset from start theta */
1531                 dt,     /* Delta Theta, angle to sweep ellipse */
1532                 cdt,    /* Cos Delta Theta, actually 2 cos(dt) */
1533                 x0, y0, /* the recurrence formula needs two points to start */
1534                 x1, y1,
1535                 x2, y2, /* this will be the new point generated */
1536                 xc, yc; /* the center point */
1537     int         count, i;
1538     SppPointPtr poly;
1539     GdkPoint last;              /* last point on integer boundaries */
1540
1541     /* The spec says that positive angles indicate counterclockwise motion.
1542      * Given our coordinate system (with 0,0 in the upper left corner),
1543      * the screen appears flipped in Y.  The easiest fix is to negate the
1544      * angles given */
1545
1546     st = - parc->angle1;
1547
1548     et = - parc->angle2;
1549
1550     /* Try to get a delta theta that is within 1/2 pixel.  Then adjust it
1551      * so that it divides evenly into the total.
1552      * I'm just using cdt 'cause I'm lazy.
1553      */
1554     cdt = parc->width;
1555     if (parc->height > cdt)
1556         cdt = parc->height;
1557     cdt /= 2.0;
1558     if(cdt <= 0)
1559         return 0;
1560     if (cdt < 1.0)
1561         cdt = 1.0;
1562     dt = miDasin ( 1.0 / cdt ); /* minimum step necessary */
1563     count = et/dt;
1564     count = abs(count) + 1;
1565     dt = et/count;
1566     count++;
1567
1568     cdt = 2 * miDcos(dt);
1569     if (!(poly = (SppPointPtr) g_realloc((gpointer)*ppPts,
1570                                         (cpt + count) * sizeof(SppPointRec))))
1571         return(0);
1572     *ppPts = poly;
1573
1574     xc = parc->width/2.0;               /* store half width and half height */
1575     yc = parc->height/2.0;
1576
1577     x0 = xc * miDcos(st);
1578     y0 = yc * miDsin(st);
1579     x1 = xc * miDcos(st + dt);
1580     y1 = yc * miDsin(st + dt);
1581     xc += parc->x;              /* by adding initial point, these become */
1582     yc += parc->y;              /* the center point */
1583
1584     poly[cpt].x = (xc + x0);
1585     poly[cpt].y = (yc + y0);
1586     last.x = ROUNDTOINT( poly[cpt + 1].x = (xc + x1) );
1587     last.y = ROUNDTOINT( poly[cpt + 1].y = (yc + y1) );
1588
1589     for(i = 2; i < count; i++)
1590     {
1591         x2 = cdt * x1 - x0;
1592         y2 = cdt * y1 - y0;
1593
1594         poly[cpt + i].x = (xc + x2);
1595         poly[cpt + i].y = (yc + y2);
1596
1597         x0 = x1; y0 = y1;
1598         x1 = x2; y1 = y2;
1599     }
1600     /* adjust the last point */
1601     if (fabs(parc->angle2) >= 360.0)
1602         poly[cpt +i -1] = poly[0];
1603     else {
1604         poly[cpt +i -1].x = (miDcos(st + et) * parc->width/2.0 + xc);
1605         poly[cpt +i -1].y = (miDsin(st + et) * parc->height/2.0 + yc);
1606     }
1607
1608     return(count);
1609 }
1610
1611 struct arcData {
1612         double  x0, y0, x1, y1;
1613         int     selfJoin;
1614 };
1615
1616 # define ADD_REALLOC_STEP       20
1617
1618 static void
1619 addCap (miArcCapPtr *capsp, int *ncapsp, int *sizep, int end, int arcIndex)
1620 {
1621         int newsize;
1622         miArcCapPtr     cap;
1623
1624         if (*ncapsp == *sizep)
1625         {
1626             newsize = *sizep + ADD_REALLOC_STEP;
1627             cap = (miArcCapPtr) g_realloc (*capsp,
1628                                           newsize * sizeof (**capsp));
1629             if (!cap)
1630                 return;
1631             *sizep = newsize;
1632             *capsp = cap;
1633         }
1634         cap = &(*capsp)[*ncapsp];
1635         cap->end = end;
1636         cap->arcIndex = arcIndex;
1637         ++*ncapsp;
1638 }
1639
1640 static void
1641 addJoin (miArcJoinPtr *joinsp, int *njoinsp, int *sizep, int end0, int index0,
1642          int phase0, int end1, int index1, int phase1)
1643 {
1644         int newsize;
1645         miArcJoinPtr    join;
1646
1647         if (*njoinsp == *sizep)
1648         {
1649             newsize = *sizep + ADD_REALLOC_STEP;
1650             join = (miArcJoinPtr) g_realloc (*joinsp,
1651                                             newsize * sizeof (**joinsp));
1652             if (!join)
1653                 return;
1654             *sizep = newsize;
1655             *joinsp = join;
1656         }
1657         join = &(*joinsp)[*njoinsp];
1658         join->end0 = end0;
1659         join->arcIndex0 = index0;
1660         join->phase0 = phase0;
1661         join->end1 = end1;
1662         join->arcIndex1 = index1;
1663         join->phase1 = phase1;
1664         ++*njoinsp;
1665 }
1666
1667 static miArcDataPtr
1668 addArc (miArcDataPtr *arcsp, int *narcsp, int *sizep, miArc *xarc)
1669 {
1670         int newsize;
1671         miArcDataPtr    arc;
1672
1673         if (*narcsp == *sizep)
1674         {
1675             newsize = *sizep + ADD_REALLOC_STEP;
1676             arc = (miArcDataPtr) g_realloc (*arcsp,
1677                                            newsize * sizeof (**arcsp));
1678             if (!arc)
1679                 return (miArcDataPtr)NULL;
1680             *sizep = newsize;
1681             *arcsp = arc;
1682         }
1683         arc = &(*arcsp)[*narcsp];
1684         arc->arc = *xarc;
1685         ++*narcsp;
1686         return arc;
1687 }
1688
1689 static void
1690 miFreeArcs(miPolyArcPtr arcs, GdkGC *pGC)
1691 {
1692         int iphase;
1693
1694         for (iphase = ((GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_DOUBLE_DASH) ? 1 : 0);
1695              iphase >= 0;
1696              iphase--)
1697         {
1698             if (arcs[iphase].narcs > 0)
1699                 g_free(arcs[iphase].arcs);
1700             if (arcs[iphase].njoins > 0)
1701                 g_free(arcs[iphase].joins);
1702             if (arcs[iphase].ncaps > 0)
1703                 g_free(arcs[iphase].caps);
1704         }
1705         g_free(arcs);
1706 }
1707
1708 /*
1709  * map angles to radial distance.  This only deals with the first quadrant
1710  */
1711
1712 /*
1713  * a polygonal approximation to the arc for computing arc lengths
1714  */
1715
1716 # define dashIndexToAngle(di)   ((((double) (di)) * 90.0) / ((double) DASH_MAP_SIZE - 1))
1717 # define xAngleToDashIndex(xa)  ((((long) (xa)) * (DASH_MAP_SIZE - 1)) / (90 * 64))
1718 # define dashIndexToXAngle(di)  ((((long) (di)) * (90 * 64)) / (DASH_MAP_SIZE - 1))
1719 # define dashXAngleStep (((double) (90 * 64)) / ((double) (DASH_MAP_SIZE - 1)))
1720
1721 static void
1722 computeDashMap (miArc *arcp, dashMap *map)
1723 {
1724         int     di;
1725         double  a, x, y, prevx = 0.0, prevy = 0.0, dist;
1726
1727         for (di = 0; di < DASH_MAP_SIZE; di++) {
1728                 a = dashIndexToAngle (di);
1729                 x = ((double) arcp->width / 2.0) * miDcos (a);
1730                 y = ((double) arcp->height / 2.0) * miDsin (a);
1731                 if (di == 0) {
1732                         map->map[di] = 0.0;
1733                 } else {
1734                         dist = hypot (x - prevx, y - prevy);
1735                         map->map[di] = map->map[di - 1] + dist;
1736                 }
1737                 prevx = x;
1738                 prevy = y;
1739         }
1740 }
1741
1742 typedef enum {HORIZONTAL, VERTICAL, OTHER} arcTypes;
1743
1744 /* this routine is a bit gory */
1745
1746 static miPolyArcPtr
1747 miComputeArcs (miArc *parcs, int narcs, GdkGC *pGC)
1748 {
1749         int             isDashed, isDoubleDash;
1750         int             dashOffset;
1751         miPolyArcPtr    arcs;
1752         int             start, i, j, k = 0, nexti, nextk = 0;
1753         int             joinSize[2];
1754         int             capSize[2];
1755         int             arcSize[2];
1756         int             angle2;
1757         double          a0, a1;
1758         struct arcData  *data;
1759         miArcDataPtr    arc;
1760         miArc           xarc;
1761         int             iphase, prevphase = 0, joinphase;
1762         int             arcsJoin;
1763         int             selfJoin;
1764
1765         int             iDash = 0, dashRemaining;
1766         int             iDashStart = 0, dashRemainingStart = 0, iphaseStart;
1767         int             startAngle, spanAngle, endAngle, backwards = 0;
1768         int             prevDashAngle, dashAngle;
1769         dashMap         map;
1770
1771         isDashed = !(GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_SOLID);
1772         isDoubleDash = (GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_DOUBLE_DASH);
1773         dashOffset = GDK_GC_FBDATA(pGC)->dash_offset;
1774
1775         data = (struct arcData *) ALLOCATE_LOCAL (narcs * sizeof (struct arcData));
1776         if (!data)
1777             return (miPolyArcPtr)NULL;
1778         arcs = (miPolyArcPtr) g_malloc (sizeof (*arcs) * (isDoubleDash ? 2 : 1));
1779         if (!arcs)
1780         {
1781             DEALLOCATE_LOCAL(data);
1782             return (miPolyArcPtr)NULL;
1783         }
1784         for (i = 0; i < narcs; i++) {
1785                 a0 = todeg (parcs[i].angle1);
1786                 angle2 = parcs[i].angle2;
1787                 if (angle2 > FULLCIRCLE)
1788                         angle2 = FULLCIRCLE;
1789                 else if (angle2 < -FULLCIRCLE)
1790                         angle2 = -FULLCIRCLE;
1791                 data[i].selfJoin = angle2 == FULLCIRCLE || angle2 == -FULLCIRCLE;
1792                 a1 = todeg (parcs[i].angle1 + angle2);
1793                 data[i].x0 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a0));
1794                 data[i].y0 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a0));
1795                 data[i].x1 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a1));
1796                 data[i].y1 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a1));
1797         }
1798
1799         for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++) {
1800                 arcs[iphase].njoins = 0;
1801                 arcs[iphase].joins = NULL;
1802                 joinSize[iphase] = 0;
1803
1804                 arcs[iphase].ncaps = 0;
1805                 arcs[iphase].caps = NULL;
1806                 capSize[iphase] = 0;
1807
1808                 arcs[iphase].narcs = 0;
1809                 arcs[iphase].arcs = NULL;
1810                 arcSize[iphase] = 0;
1811         }
1812
1813         iphase = 0;
1814         if (isDashed) {
1815                 iDash = 0;
1816                 dashRemaining = GDK_GC_FBDATA(pGC)->dash_list[0];
1817                 while (dashOffset > 0) {
1818                         if (dashOffset >= dashRemaining) {
1819                                 dashOffset -= dashRemaining;
1820                                 iphase = iphase ? 0 : 1;
1821                                 iDash++;
1822                                 if (iDash == GDK_GC_FBDATA(pGC)->dash_list_len)
1823                                     iDash = 0;
1824                                 dashRemaining = GDK_GC_FBDATA(pGC)->dash_list[iDash];
1825                         } else {
1826                                 dashRemaining -= dashOffset;
1827                                 dashOffset = 0;
1828                         }
1829                 }
1830                 iDashStart = iDash;
1831                 dashRemainingStart = dashRemaining;
1832         }
1833         iphaseStart = iphase;
1834
1835         for (i = narcs - 1; i >= 0; i--) {
1836                 j = i + 1;
1837                 if (j == narcs)
1838                         j = 0;
1839                 if (data[i].selfJoin || i == j ||
1840                      (UNEQUAL (data[i].x1, data[j].x0) ||
1841                       UNEQUAL (data[i].y1, data[j].y0)))
1842                 {
1843                         if (iphase == 0 || isDoubleDash)
1844                                 addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
1845                                         &capSize[iphase], RIGHT_END, 0);
1846                         break;
1847                 }
1848         }
1849         start = i + 1;
1850         if (start == narcs)
1851                 start = 0;
1852         i = start;
1853         for (;;) {
1854                 j = i + 1;
1855                 if (j == narcs)
1856                         j = 0;
1857                 nexti = i+1;
1858                 if (nexti == narcs)
1859                         nexti = 0;
1860                 if (isDashed) {
1861                         /*
1862                         ** deal with dashed arcs.  Use special rules for certain 0 area arcs.
1863                         ** Presumably, the other 0 area arcs still aren't done right.
1864                         */
1865                         arcTypes        arcType = OTHER;
1866                         guint16         thisLength;
1867
1868                         if (parcs[i].height == 0
1869                             && (parcs[i].angle1 % FULLCIRCLE) == 0x2d00
1870                             && parcs[i].angle2 == 0x2d00)
1871                                 arcType = HORIZONTAL;
1872                         else if (parcs[i].width == 0
1873                             && (parcs[i].angle1 % FULLCIRCLE) == 0x1680
1874                             && parcs[i].angle2 == 0x2d00)
1875                                 arcType = VERTICAL;
1876                         if (arcType == OTHER) {
1877                                 /*
1878                                  * precompute an approximation map
1879                                  */
1880                                 computeDashMap (&parcs[i], &map);
1881                                 /*
1882                                  * compute each individual dash segment using the path
1883                                  * length function
1884                                  */
1885                                 startAngle = parcs[i].angle1;
1886                                 spanAngle = parcs[i].angle2;
1887                                 if (spanAngle > FULLCIRCLE)
1888                                         spanAngle = FULLCIRCLE;
1889                                 else if (spanAngle < -FULLCIRCLE)
1890                                         spanAngle = -FULLCIRCLE;
1891                                 if (startAngle < 0)
1892                                         startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
1893                                 if (startAngle >= FULLCIRCLE)
1894                                         startAngle = startAngle % FULLCIRCLE;
1895                                 endAngle = startAngle + spanAngle;
1896                                 backwards = spanAngle < 0;
1897                         } else {
1898                                 xarc = parcs[i];
1899                                 if (arcType == VERTICAL) {
1900                                         xarc.angle1 = 0x1680;
1901                                         startAngle = parcs[i].y;
1902                                         endAngle = startAngle + parcs[i].height;
1903                                 } else {
1904                                         xarc.angle1 = 0x2d00;
1905                                         startAngle = parcs[i].x;
1906                                         endAngle = startAngle + parcs[i].width;
1907                                 }
1908                         }
1909                         dashAngle = startAngle;
1910                         selfJoin = data[i].selfJoin &&
1911                                     (iphase == 0 || isDoubleDash);
1912                         /*
1913                          * add dashed arcs to each bucket
1914                          */
1915                         arc = NULL;
1916                         while (dashAngle != endAngle) {
1917                                 prevDashAngle = dashAngle;
1918                                 if (arcType == OTHER) {
1919                                         dashAngle = computeAngleFromPath (prevDashAngle, endAngle,
1920                                                                 &map, &dashRemaining, backwards);
1921                                         /* avoid troubles with huge arcs and small dashes */
1922                                         if (dashAngle == prevDashAngle) {
1923                                                 if (backwards)
1924                                                         dashAngle--;
1925                                                 else
1926                                                         dashAngle++;
1927                                         }
1928                                 } else {
1929                                         thisLength = (dashAngle + dashRemaining <= endAngle) ?
1930                                             dashRemaining : endAngle - dashAngle;
1931                                         if (arcType == VERTICAL) {
1932                                                 xarc.y = dashAngle;
1933                                                 xarc.height = thisLength;
1934                                         } else {
1935                                                 xarc.x = dashAngle;
1936                                                 xarc.width = thisLength;
1937                                         }
1938                                         dashAngle += thisLength;
1939                                         dashRemaining -= thisLength;
1940                                 }
1941                                 if (iphase == 0 || isDoubleDash) {
1942                                         if (arcType == OTHER) {
1943                                                 xarc = parcs[i];
1944                                                 spanAngle = prevDashAngle;
1945                                                 if (spanAngle < 0)
1946                                                     spanAngle = FULLCIRCLE - (-spanAngle) % FULLCIRCLE;
1947                                                 if (spanAngle >= FULLCIRCLE)
1948                                                     spanAngle = spanAngle % FULLCIRCLE;
1949                                                 xarc.angle1 = spanAngle;
1950                                                 spanAngle = dashAngle - prevDashAngle;
1951                                                 if (backwards) {
1952                                                         if (dashAngle > prevDashAngle)
1953                                                                 spanAngle = - FULLCIRCLE + spanAngle;
1954                                                 } else {
1955                                                         if (dashAngle < prevDashAngle)
1956                                                                 spanAngle = FULLCIRCLE + spanAngle;
1957                                                 }
1958                                                 if (spanAngle > FULLCIRCLE)
1959                                                     spanAngle = FULLCIRCLE;
1960                                                 if (spanAngle < -FULLCIRCLE)
1961                                                     spanAngle = -FULLCIRCLE;
1962                                                 xarc.angle2 = spanAngle;
1963                                         }
1964                                         arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
1965                                                         &arcSize[iphase], &xarc);
1966                                         if (!arc)
1967                                             goto arcfail;
1968                                         /*
1969                                          * cap each end of an on/off dash
1970                                          */
1971                                         if (!isDoubleDash) {
1972                                                 if (prevDashAngle != startAngle) {
1973                                                         addCap (&arcs[iphase].caps,
1974                                                                 &arcs[iphase].ncaps,
1975                                                                 &capSize[iphase], RIGHT_END,
1976                                                                 arc - arcs[iphase].arcs);
1977
1978                                                 }
1979                                                 if (dashAngle != endAngle) {
1980                                                         addCap (&arcs[iphase].caps,
1981                                                                 &arcs[iphase].ncaps,
1982                                                                 &capSize[iphase], LEFT_END,
1983                                                                 arc - arcs[iphase].arcs);
1984                                                 }
1985                                         }
1986                                         arc->cap = arcs[iphase].ncaps;
1987                                         arc->join = arcs[iphase].njoins;
1988                                         arc->render = 0;
1989                                         arc->selfJoin = 0;
1990                                         if (dashAngle == endAngle)
1991                                                 arc->selfJoin = selfJoin;
1992                                 }
1993                                 prevphase = iphase;
1994                                 if (dashRemaining <= 0) {
1995                                         ++iDash;
1996                                         if (iDash == GDK_GC_FBDATA(pGC)->dash_list_len)
1997                                                 iDash = 0;
1998                                         iphase = iphase ? 0:1;
1999                                         dashRemaining = GDK_GC_FBDATA(pGC)->dash_list[iDash];
2000                                 }
2001                         }
2002                         /*
2003                          * make sure a place exists for the position data when
2004                          * drawing a zero-length arc
2005                          */
2006                         if (startAngle == endAngle) {
2007                                 prevphase = iphase;
2008                                 if (!isDoubleDash && iphase == 1)
2009                                         prevphase = 0;
2010                                 arc = addArc (&arcs[prevphase].arcs, &arcs[prevphase].narcs,
2011                                               &arcSize[prevphase], &parcs[i]);
2012                                 if (!arc)
2013                                     goto arcfail;
2014                                 arc->join = arcs[prevphase].njoins;
2015                                 arc->cap = arcs[prevphase].ncaps;
2016                                 arc->selfJoin = data[i].selfJoin;
2017                         }
2018                 } else {
2019                         arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
2020                                       &arcSize[iphase], &parcs[i]);
2021                         if (!arc)
2022                             goto arcfail;
2023                         arc->join = arcs[iphase].njoins;
2024                         arc->cap = arcs[iphase].ncaps;
2025                         arc->selfJoin = data[i].selfJoin;
2026                         prevphase = iphase;
2027                 }
2028                 if (prevphase == 0 || isDoubleDash)
2029                         k = arcs[prevphase].narcs - 1;
2030                 if (iphase == 0 || isDoubleDash)
2031                         nextk = arcs[iphase].narcs;
2032                 if (nexti == start) {
2033                         nextk = 0;
2034                         if (isDashed) {
2035                                 iDash = iDashStart;
2036                                 iphase = iphaseStart;
2037                                 dashRemaining = dashRemainingStart;
2038                         }
2039                 }
2040                 arcsJoin = narcs > 1 && i != j &&
2041                             ISEQUAL (data[i].x1, data[j].x0) &&
2042                             ISEQUAL (data[i].y1, data[j].y0) &&
2043                             !data[i].selfJoin && !data[j].selfJoin;
2044                 if (arc)
2045                 {
2046                         if (arcsJoin)
2047                                 arc->render = 0;
2048                         else
2049                                 arc->render = 1;
2050                 }
2051                 if (arcsJoin &&
2052                     (prevphase == 0 || isDoubleDash) &&
2053                     (iphase == 0 || isDoubleDash))
2054                 {
2055                         joinphase = iphase;
2056                         if (isDoubleDash) {
2057                                 if (nexti == start)
2058                                         joinphase = iphaseStart;
2059                                 /*
2060                                  * if the join is right at the dash,
2061                                  * draw the join in foreground
2062                                  * This is because the foreground
2063                                  * arcs are computed second, the results
2064                                  * of which are needed to draw the join
2065                                  */
2066                                 if (joinphase != prevphase)
2067                                         joinphase = 0;
2068                         }
2069                         if (joinphase == 0 || isDoubleDash) {
2070                                 addJoin (&arcs[joinphase].joins,
2071                                          &arcs[joinphase].njoins,
2072                                          &joinSize[joinphase],
2073                                          LEFT_END, k, prevphase,
2074                                          RIGHT_END, nextk, iphase);
2075                                 arc->join = arcs[prevphase].njoins;
2076                         }
2077                 } else {
2078                         /*
2079                          * cap the left end of this arc
2080                          * unless it joins itself
2081                          */
2082                         if ((prevphase == 0 || isDoubleDash) &&
2083                             !arc->selfJoin)
2084                         {
2085                                 addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
2086                                         &capSize[prevphase], LEFT_END, k);
2087                                 arc->cap = arcs[prevphase].ncaps;
2088                         }
2089                         if (isDashed && !arcsJoin) {
2090                                 iDash = iDashStart;
2091                                 iphase = iphaseStart;
2092                                 dashRemaining = dashRemainingStart;
2093                         }
2094                         nextk = arcs[iphase].narcs;
2095                         if (nexti == start) {
2096                                 nextk = 0;
2097                                 iDash = iDashStart;
2098                                 iphase = iphaseStart;
2099                                 dashRemaining = dashRemainingStart;
2100                         }
2101                         /*
2102                          * cap the right end of the next arc.  If the
2103                          * next arc is actually the first arc, only
2104                          * cap it if it joins with this arc.  This
2105                          * case will occur when the final dash segment
2106                          * of an on/off dash is off.  Of course, this
2107                          * cap will be drawn at a strange time, but that
2108                          * hardly matters...
2109                          */
2110                         if ((iphase == 0 || isDoubleDash) &&
2111                             (nexti != start || (arcsJoin && isDashed)))
2112                                 addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
2113                                         &capSize[iphase], RIGHT_END, nextk);
2114                 }
2115                 i = nexti;
2116                 if (i == start)
2117                         break;
2118         }
2119         /*
2120          * make sure the last section is rendered
2121          */
2122         for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++)
2123                 if (arcs[iphase].narcs > 0) {
2124                         arcs[iphase].arcs[arcs[iphase].narcs-1].render = 1;
2125                         arcs[iphase].arcs[arcs[iphase].narcs-1].join =
2126                                  arcs[iphase].njoins;
2127                         arcs[iphase].arcs[arcs[iphase].narcs-1].cap =
2128                                  arcs[iphase].ncaps;
2129                 }
2130         DEALLOCATE_LOCAL(data);
2131         return arcs;
2132 arcfail:
2133         miFreeArcs(arcs, pGC);
2134         DEALLOCATE_LOCAL(data);
2135         return (miPolyArcPtr)NULL;
2136 }
2137
2138 static double
2139 angleToLength (int angle, dashMap *map)
2140 {
2141         double  len, excesslen, sidelen = map->map[DASH_MAP_SIZE - 1], totallen;
2142         int     di;
2143         int     excess;
2144         gboolean        oddSide = FALSE;
2145
2146         totallen = 0;
2147         if (angle >= 0) {
2148                 while (angle >= 90 * 64) {
2149                         angle -= 90 * 64;
2150                         totallen += sidelen;
2151                         oddSide = !oddSide;
2152                 }
2153         } else {
2154                 while (angle < 0) {
2155                         angle += 90 * 64;
2156                         totallen -= sidelen;
2157                         oddSide = !oddSide;
2158                 }
2159         }
2160         if (oddSide)
2161                 angle = 90 * 64 - angle;
2162
2163         di = xAngleToDashIndex (angle);
2164         excess = angle - dashIndexToXAngle (di);
2165
2166         len = map->map[di];
2167         /*
2168          * linearly interpolate between this point and the next
2169          */
2170         if (excess > 0) {
2171                 excesslen = (map->map[di + 1] - map->map[di]) *
2172                                 ((double) excess) / dashXAngleStep;
2173                 len += excesslen;
2174         }
2175         if (oddSide)
2176                 totallen += (sidelen - len);
2177         else
2178                 totallen += len;
2179         return totallen;
2180 }
2181
2182 /*
2183  * len is along the arc, but may be more than one rotation
2184  */
2185
2186 static int
2187 lengthToAngle (double len, dashMap *map)
2188 {
2189         double  sidelen = map->map[DASH_MAP_SIZE - 1];
2190         int     angle, angleexcess;
2191         gboolean        oddSide = FALSE;
2192         int     a0, a1, a;
2193
2194         angle = 0;
2195         /*
2196          * step around the ellipse, subtracting sidelens and
2197          * adding 90 degrees.  oddSide will tell if the
2198          * map should be interpolated in reverse
2199          */
2200         if (len >= 0) {
2201                 if (sidelen == 0)
2202                         return 2 * FULLCIRCLE;  /* infinity */
2203                 while (len >= sidelen) {
2204                         angle += 90 * 64;
2205                         len -= sidelen;
2206                         oddSide = !oddSide;
2207                 }
2208         } else {
2209                 if (sidelen == 0)
2210                         return -2 * FULLCIRCLE; /* infinity */
2211                 while (len < 0) {
2212                         angle -= 90 * 64;
2213                         len += sidelen;
2214                         oddSide = !oddSide;
2215                 }
2216         }
2217         if (oddSide)
2218                 len = sidelen - len;
2219         a0 = 0;
2220         a1 = DASH_MAP_SIZE - 1;
2221         /*
2222          * binary search for the closest pre-computed length
2223          */
2224         while (a1 - a0 > 1) {
2225                 a = (a0 + a1) / 2;
2226                 if (len > map->map[a])
2227                         a0 = a;
2228                 else
2229                         a1 = a;
2230         }
2231         angleexcess = dashIndexToXAngle (a0);
2232         /*
2233          * linearly interpolate to the next point
2234          */
2235         angleexcess += (len - map->map[a0]) /
2236                         (map->map[a0+1] - map->map[a0]) * dashXAngleStep;
2237         if (oddSide)
2238                 angle += (90 * 64) - angleexcess;
2239         else
2240                 angle += angleexcess;
2241         return angle;
2242 }
2243
2244 /*
2245  * compute the angle of an ellipse which cooresponds to
2246  * the given path length.  Note that the correct solution
2247  * to this problem is an eliptic integral, we'll punt and
2248  * approximate (it's only for dashes anyway).  This
2249  * approximation uses a polygon.
2250  *
2251  * The remaining portion of len is stored in *lenp -
2252  * this will be negative if the arc extends beyond
2253  * len and positive if len extends beyond the arc.
2254  */
2255
2256 static int computeAngleFromPath(int startAngle, int endAngle, dashMap *map, int *lenp, int backwards)
2257 /*      int     startAngle, endAngle;   *//* normalized absolute angles in *64 degrees */
2258 {
2259         int     a0, a1, a;
2260         double  len0;
2261         int     len;
2262
2263         a0 = startAngle;
2264         a1 = endAngle;
2265         len = *lenp;
2266         if (backwards) {
2267                 /*
2268                  * flip the problem around to always be
2269                  * forwards
2270                  */
2271                 a0 = FULLCIRCLE - a0;
2272                 a1 = FULLCIRCLE - a1;
2273         }
2274         if (a1 < a0)
2275                 a1 += FULLCIRCLE;
2276         len0 = angleToLength (a0, map);
2277         a = lengthToAngle (len0 + len, map);
2278         if (a > a1) {
2279                 a = a1;
2280                 len -= angleToLength (a1, map) - len0;
2281         } else
2282                 len = 0;
2283         if (backwards)
2284                 a = FULLCIRCLE - a;
2285         *lenp = len;
2286         return a;
2287 }
2288
2289 /*
2290  * scan convert wide arcs.
2291  */
2292
2293 /*
2294  * draw zero width/height arcs
2295  */
2296
2297 static void
2298 drawZeroArc (GdkDrawable *pDraw, GdkGC *pGC, miArc *tarc, int lw,
2299              miArcFacePtr left, miArcFacePtr right)
2300 {
2301         double  x0 = 0.0, y0 = 0.0, x1 = 0.0, y1 = 0.0, w, h, x, y;
2302         double  xmax, ymax, xmin, ymin;
2303         int     a0, a1;
2304         double  a, startAngle, endAngle;
2305         double  l, lx, ly;
2306
2307         l = lw / 2.0;
2308         a0 = tarc->angle1;
2309         a1 = tarc->angle2;
2310         if (a1 > FULLCIRCLE)
2311                 a1 = FULLCIRCLE;
2312         else if (a1 < -FULLCIRCLE)
2313                 a1 = -FULLCIRCLE;
2314         w = (double)tarc->width / 2.0;
2315         h = (double)tarc->height / 2.0;
2316         /*
2317          * play in X coordinates right away
2318          */
2319         startAngle = - ((double) a0 / 64.0);
2320         endAngle = - ((double) (a0 + a1) / 64.0);
2321
2322         xmax = -w;
2323         xmin = w;
2324         ymax = -h;
2325         ymin = h;
2326         a = startAngle;
2327         for (;;)
2328         {
2329                 x = w * miDcos(a);
2330                 y = h * miDsin(a);
2331                 if (a == startAngle)
2332                 {
2333                         x0 = x;
2334                         y0 = y;
2335                 }
2336                 if (a == endAngle)
2337                 {
2338                         x1 = x;
2339                         y1 = y;
2340                 }
2341                 if (x > xmax)
2342                         xmax = x;
2343                 if (x < xmin)
2344                         xmin = x;
2345                 if (y > ymax)
2346                         ymax = y;
2347                 if (y < ymin)
2348                         ymin = y;
2349                 if (a == endAngle)
2350                         break;
2351                 if (a1 < 0)     /* clockwise */
2352                 {
2353                         if (floor (a / 90.0) == floor (endAngle / 90.0))
2354                                 a = endAngle;
2355                         else
2356                                 a = 90 * (floor (a/90.0) + 1);
2357                 }
2358                 else
2359                 {
2360                         if (ceil (a / 90.0) == ceil (endAngle / 90.0))
2361                                 a = endAngle;
2362                         else
2363                                 a = 90 * (ceil (a/90.0) - 1);
2364                 }
2365         }
2366         lx = ly = l;
2367         if ((x1 - x0) + (y1 - y0) < 0)
2368             lx = ly = -l;
2369         if (h)
2370         {
2371             ly = 0.0;
2372             lx = -lx;
2373         }
2374         else
2375             lx = 0.0;
2376         if (right)
2377         {
2378             right->center.x = x0;
2379             right->center.y = y0;
2380             right->clock.x = x0 - lx;
2381             right->clock.y = y0 - ly;
2382             right->counterClock.x = x0 + lx;
2383             right->counterClock.y = y0 + ly;
2384         }
2385         if (left)
2386         {
2387             left->center.x = x1;
2388             left->center.y = y1;
2389             left->clock.x = x1 + lx;
2390             left->clock.y = y1 + ly;
2391             left->counterClock.x = x1 - lx;
2392             left->counterClock.y = y1 - ly;
2393         }
2394
2395         x0 = xmin;
2396         x1 = xmax;
2397         y0 = ymin;
2398         y1 = ymax;
2399         if (ymin != y1) {
2400                 xmin = -l;
2401                 xmax = l;
2402         } else {
2403                 ymin = -l;
2404                 ymax = l;
2405         }
2406         if (xmax != xmin && ymax != ymin) {
2407                 int     minx, maxx, miny, maxy;
2408
2409                 minx = ICEIL (xmin + w) + tarc->x;
2410                 maxx = ICEIL (xmax + w) + tarc->x;
2411                 miny = ICEIL (ymin + h) + tarc->y;
2412                 maxy = ICEIL (ymax + h) + tarc->y;
2413
2414                 gdk_fb_draw_rectangle(pDraw, pGC, TRUE, minx, miny, maxx - minx, maxy - miny);
2415         }
2416 }
2417
2418 /*
2419  * this computes the ellipse y value associated with the
2420  * bottom of the tail.
2421  */
2422
2423 static void
2424 tailEllipseY (struct arc_def *def, struct accelerators *acc)
2425 {
2426         double          t;
2427
2428         acc->tail_y = 0.0;
2429         if (def->w == def->h)
2430             return;
2431         t = def->l * def->w;
2432         if (def->w > def->h) {
2433             if (t < acc->h2)
2434                 return;
2435         } else {
2436             if (t > acc->h2)
2437                 return;
2438         }
2439         t = 2.0 * def->h * t;
2440         t = (CUBED_ROOT_4 * acc->h2 - cbrt(t * t)) / acc->h2mw2;
2441         if (t > 0.0)
2442             acc->tail_y = def->h / CUBED_ROOT_2 * sqrt(t);
2443 }
2444
2445 /*
2446  * inverse functions -- compute edge coordinates
2447  * from the ellipse
2448  */
2449
2450 static double
2451 outerXfromXY (double x, double y,
2452               struct arc_def *def, struct accelerators *acc)
2453 {
2454         return x + (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2455 }
2456
2457 static double
2458 outerYfromXY (double x, double y,
2459               struct arc_def *def, struct accelerators *acc)
2460 {
2461         return y + (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2462 }
2463
2464 static double
2465 innerXfromXY (double x, double y,
2466               struct arc_def *def, struct accelerators *acc)
2467 {
2468         return x - (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2469 }
2470
2471 static double
2472 innerYfromXY (double x, double y,
2473               struct arc_def *def, struct accelerators *acc)
2474 {
2475         return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2476 }
2477
2478 static double
2479 innerYfromY (double y, struct arc_def *def, struct accelerators *acc)
2480 {
2481         double  x;
2482
2483         x = (def->w / def->h) * sqrt (acc->h2 - y*y);
2484
2485         return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2486 }
2487
2488 static void
2489 computeLine (double x1, double y1, double x2, double y2, struct line *line)
2490 {
2491         if (y1 == y2)
2492                 line->valid = 0;
2493         else {
2494                 line->m = (x1 - x2) / (y1 - y2);
2495                 line->b = x1  - y1 * line->m;
2496                 line->valid = 1;
2497         }
2498 }
2499
2500 /*
2501  * compute various accelerators for an ellipse.  These
2502  * are simply values that are used repeatedly in
2503  * the computations
2504  */
2505
2506 static void
2507 computeAcc (miArc *tarc, int lw, struct arc_def *def, struct accelerators *acc)
2508 {
2509         def->w = ((double) tarc->width) / 2.0;
2510         def->h = ((double) tarc->height) / 2.0;
2511         def->l = ((double) lw) / 2.0;
2512         acc->h2 = def->h * def->h;
2513         acc->w2 = def->w * def->w;
2514         acc->h4 = acc->h2 * acc->h2;
2515         acc->w4 = acc->w2 * acc->w2;
2516         acc->h2l = acc->h2 * def->l;
2517         acc->w2l = acc->w2 * def->l;
2518         acc->h2mw2 = acc->h2 - acc->w2;
2519         acc->fromIntX = (tarc->width & 1) ? 0.5 : 0.0;
2520         acc->fromIntY = (tarc->height & 1) ? 0.5 : 0.0;
2521         acc->xorg = tarc->x + (tarc->width >> 1);
2522         acc->yorgu = tarc->y + (tarc->height >> 1);
2523         acc->yorgl = acc->yorgu + (tarc->height & 1);
2524         tailEllipseY (def, acc);
2525 }
2526
2527 /*
2528  * compute y value bounds of various portions of the arc,
2529  * the outer edge, the ellipse and the inner edge.
2530  */
2531
2532 static void
2533 computeBound (struct arc_def *def, struct arc_bound *bound,
2534               struct accelerators *acc, miArcFacePtr right, miArcFacePtr left)
2535 {
2536         double          t;
2537         double          innerTaily;
2538         double          tail_y;
2539         struct bound    innerx, outerx;
2540         struct bound    ellipsex;
2541
2542         bound->ellipse.min = Dsin (def->a0) * def->h;
2543         bound->ellipse.max = Dsin (def->a1) * def->h;
2544         if (def->a0 == 45 && def->w == def->h)
2545                 ellipsex.min = bound->ellipse.min;
2546         else
2547                 ellipsex.min = Dcos (def->a0) * def->w;
2548         if (def->a1 == 45 && def->w == def->h)
2549                 ellipsex.max = bound->ellipse.max;
2550         else
2551                 ellipsex.max = Dcos (def->a1) * def->w;
2552         bound->outer.min = outerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2553         bound->outer.max = outerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2554         bound->inner.min = innerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2555         bound->inner.max = innerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2556
2557         outerx.min = outerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2558         outerx.max = outerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2559         innerx.min = innerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2560         innerx.max = innerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2561
2562         /*
2563          * save the line end points for the
2564          * cap code to use.  Careful here, these are
2565          * in cartesean coordinates (y increasing upwards)
2566          * while the cap code uses inverted coordinates
2567          * (y increasing downwards)
2568          */
2569
2570         if (right) {
2571                 right->counterClock.y = bound->outer.min;
2572                 right->counterClock.x = outerx.min;
2573                 right->center.y = bound->ellipse.min;
2574                 right->center.x = ellipsex.min;
2575                 right->clock.y = bound->inner.min;
2576                 right->clock.x = innerx.min;
2577         }
2578
2579         if (left) {
2580                 left->clock.y = bound->outer.max;
2581                 left->clock.x = outerx.max;
2582                 left->center.y = bound->ellipse.max;
2583                 left->center.x = ellipsex.max;
2584                 left->counterClock.y = bound->inner.max;
2585                 left->counterClock.x = innerx.max;
2586         }
2587
2588         bound->left.min = bound->inner.max;
2589         bound->left.max = bound->outer.max;
2590         bound->right.min = bound->inner.min;
2591         bound->right.max = bound->outer.min;
2592
2593         computeLine (innerx.min, bound->inner.min, outerx.min, bound->outer.min,
2594                       &acc->right);
2595         computeLine (innerx.max, bound->inner.max, outerx.max, bound->outer.max,
2596                      &acc->left);
2597
2598         if (bound->inner.min > bound->inner.max) {
2599                 t = bound->inner.min;
2600                 bound->inner.min = bound->inner.max;
2601                 bound->inner.max = t;
2602         }
2603         tail_y = acc->tail_y;
2604         if (tail_y > bound->ellipse.max)
2605                 tail_y = bound->ellipse.max;
2606         else if (tail_y < bound->ellipse.min)
2607                 tail_y = bound->ellipse.min;
2608         innerTaily = innerYfromY (tail_y, def, acc);
2609         if (bound->inner.min > innerTaily)
2610                 bound->inner.min = innerTaily;
2611         if (bound->inner.max < innerTaily)
2612                 bound->inner.max = innerTaily;
2613         bound->inneri.min = ICEIL(bound->inner.min - acc->fromIntY);
2614         bound->inneri.max = floor(bound->inner.max - acc->fromIntY);
2615         bound->outeri.min = ICEIL(bound->outer.min - acc->fromIntY);
2616         bound->outeri.max = floor(bound->outer.max - acc->fromIntY);
2617 }
2618
2619 /*
2620  * this section computes the x value of the span at y
2621  * intersected with the specified face of the ellipse.
2622  *
2623  * this is the min/max X value over the set of normal
2624  * lines to the entire ellipse,  the equation of the
2625  * normal lines is:
2626  *
2627  *     ellipse_x h^2                   h^2
2628  * x = ------------ y + ellipse_x (1 - --- )
2629  *     ellipse_y w^2                   w^2
2630  *
2631  * compute the derivative with-respect-to ellipse_y and solve
2632  * for zero:
2633  *
2634  *       (w^2 - h^2) ellipse_y^3 + h^4 y
2635  * 0 = - ----------------------------------
2636  *       h w ellipse_y^2 sqrt (h^2 - ellipse_y^2)
2637  *
2638  *             (   h^4 y     )
2639  * ellipse_y = ( ----------  ) ^ (1/3)
2640  *             ( (h^2 - w^2) )
2641  *
2642  * The other two solutions to the equation are imaginary.
2643  *
2644  * This gives the position on the ellipse which generates
2645  * the normal with the largest/smallest x intersection point.
2646  *
2647  * Now compute the second derivative to check whether
2648  * the intersection is a minimum or maximum:
2649  *
2650  *    h (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2651  * -  -------------------------------------------
2652  *          w y0^3 (sqrt (h^2 - y^2)) ^ 3
2653  *
2654  * as we only care about the sign,
2655  *
2656  * - (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2657  *
2658  * or (to use accelerators),
2659  *
2660  * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2)
2661  *
2662  */
2663
2664 /*
2665  * computes the position on the ellipse whose normal line
2666  * intersects the given scan line maximally
2667  */
2668
2669 static double
2670 hookEllipseY (double scan_y, struct arc_bound *bound,
2671               struct accelerators *acc, int left)
2672 {
2673         double  ret;
2674
2675         if (acc->h2mw2 == 0) {
2676                 if ( (scan_y > 0 && !left) || (scan_y < 0 && left) )
2677                         return bound->ellipse.min;
2678                 return bound->ellipse.max;
2679         }
2680         ret = (acc->h4 * scan_y) / (acc->h2mw2);
2681         if (ret >= 0)
2682                 return cbrt (ret);
2683         else
2684                 return -cbrt (-ret);
2685 }
2686
2687 /*
2688  * computes the X value of the intersection of the
2689  * given scan line with the right side of the lower hook
2690  */
2691
2692 static double
2693 hookX (double scan_y, struct arc_def *def,
2694        struct arc_bound *bound, struct accelerators *acc, int left)
2695 {
2696         double  ellipse_y, x;
2697         double  maxMin;
2698
2699         if (def->w != def->h) {
2700                 ellipse_y = hookEllipseY (scan_y, bound, acc, left);
2701                 if (boundedLe (ellipse_y, bound->ellipse)) {
2702                         /*
2703                          * compute the value of the second
2704                          * derivative
2705                          */
2706                         maxMin = ellipse_y*ellipse_y*ellipse_y * acc->h2mw2 -
2707                          acc->h2 * scan_y * (3 * ellipse_y*ellipse_y - 2*acc->h2);
2708                         if ((left && maxMin > 0) || (!left && maxMin < 0)) {
2709                                 if (ellipse_y == 0)
2710                                         return def->w + left ? -def->l : def->l;
2711                                 x = (acc->h2 * scan_y - ellipse_y * acc->h2mw2) *
2712                                         sqrt (acc->h2 - ellipse_y * ellipse_y) /
2713                                         (def->h * def->w * ellipse_y);
2714                                 return x;
2715                         }
2716                 }
2717         }
2718         if (left) {
2719                 if (acc->left.valid && boundedLe (scan_y, bound->left)) {
2720                         x = intersectLine (scan_y, acc->left);
2721                 } else {
2722                         if (acc->right.valid)
2723                                 x = intersectLine (scan_y, acc->right);
2724                         else
2725                                 x = def->w - def->l;
2726                 }
2727         } else {
2728                 if (acc->right.valid && boundedLe (scan_y, bound->right)) {
2729                         x = intersectLine (scan_y, acc->right);
2730                 } else {
2731                         if (acc->left.valid)
2732                                 x = intersectLine (scan_y, acc->left);
2733                         else
2734                                 x = def->w - def->l;
2735                 }
2736         }
2737         return x;
2738 }
2739
2740 /*
2741  * generate the set of spans with
2742  * the given y coordinate
2743  */
2744
2745 static void
2746 arcSpan (int y, int lx, int lw, int rx, int rw,
2747          struct arc_def *def, struct arc_bound *bounds,
2748          struct accelerators *acc, int mask)
2749 {
2750         int linx, loutx, rinx, routx;
2751         double x, altx;
2752
2753         if (boundedLe (y, bounds->inneri)) {
2754             linx = -(lx + lw);
2755             rinx = rx;
2756         } else {
2757             /*
2758              * intersection with left face
2759              */
2760             x = hookX (y + acc->fromIntY, def, bounds, acc, 1);
2761             if (acc->right.valid &&
2762                 boundedLe (y + acc->fromIntY, bounds->right))
2763             {
2764                 altx = intersectLine (y + acc->fromIntY, acc->right);
2765                 if (altx < x)
2766                     x = altx;
2767             }
2768             linx = -ICEIL(acc->fromIntX - x);
2769             rinx = ICEIL(acc->fromIntX + x);
2770         }
2771         if (boundedLe (y, bounds->outeri)) {
2772             loutx = -lx;
2773             routx = rx + rw;
2774         } else {
2775             /*
2776              * intersection with right face
2777              */
2778             x = hookX (y + acc->fromIntY, def, bounds, acc, 0);
2779             if (acc->left.valid &&
2780                 boundedLe (y + acc->fromIntY, bounds->left))
2781             {
2782                 altx = x;
2783                 x = intersectLine (y + acc->fromIntY, acc->left);
2784                 if (x < altx)
2785                     x = altx;
2786             }
2787             loutx = -ICEIL(acc->fromIntX - x);
2788             routx = ICEIL(acc->fromIntX + x);
2789         }
2790         if (routx > rinx) {
2791             if (mask & 1)
2792                 newFinalSpan (acc->yorgu - y,
2793                               acc->xorg + rinx, acc->xorg + routx);
2794             if (mask & 8)
2795                 newFinalSpan (acc->yorgl + y,
2796                               acc->xorg + rinx, acc->xorg + routx);
2797         }
2798         if (loutx > linx) {
2799             if (mask & 2)
2800                 newFinalSpan (acc->yorgu - y,
2801                               acc->xorg - loutx, acc->xorg - linx);
2802             if (mask & 4)
2803                 newFinalSpan (acc->yorgl + y,
2804                               acc->xorg - loutx, acc->xorg - linx);
2805         }
2806 }
2807
2808 static void
2809 arcSpan0 (int lx, int lw, int rx, int rw,
2810           struct arc_def *def, struct arc_bound *bounds,
2811           struct accelerators *acc, int mask)
2812 {
2813     double x;
2814
2815     if (boundedLe (0, bounds->inneri) &&
2816         acc->left.valid && boundedLe (0, bounds->left) &&
2817         acc->left.b > 0)
2818     {
2819         x = def->w - def->l;
2820         if (acc->left.b < x)
2821             x = acc->left.b;
2822         lw = ICEIL(acc->fromIntX - x) - lx;
2823         rw += rx;
2824         rx = ICEIL(acc->fromIntX + x);
2825         rw -= rx;
2826     }
2827     arcSpan (0, lx, lw, rx, rw, def, bounds, acc, mask);
2828 }
2829
2830 static void
2831 tailSpan (int y, int lw, int rw,
2832           struct arc_def *def, struct arc_bound *bounds,
2833           struct accelerators *acc, int mask)
2834 {
2835     double yy, xalt, x, lx, rx;
2836     int n;
2837
2838     if (boundedLe(y, bounds->outeri))
2839         arcSpan (y, 0, lw, -rw, rw, def, bounds, acc, mask);
2840     else if (def->w != def->h) {
2841         yy = y + acc->fromIntY;
2842         x = tailX(yy, def, bounds, acc);
2843         if (yy == 0.0 && x == -rw - acc->fromIntX)
2844             return;
2845         if (acc->right.valid && boundedLe (yy, bounds->right)) {
2846             rx = x;
2847             lx = -x;
2848             xalt = intersectLine (yy, acc->right);
2849             if (xalt >= -rw - acc->fromIntX && xalt <= rx)
2850                 rx = xalt;
2851             n = ICEIL(acc->fromIntX + lx);
2852             if (lw > n) {
2853                 if (mask & 2)
2854                     newFinalSpan (acc->yorgu - y,
2855                                   acc->xorg + n, acc->xorg + lw);
2856                 if (mask & 4)
2857                     newFinalSpan (acc->yorgl + y,
2858                                   acc->xorg + n, acc->xorg + lw);
2859             }
2860             n = ICEIL(acc->fromIntX + rx);
2861             if (n > -rw) {
2862                 if (mask & 1)
2863                     newFinalSpan (acc->yorgu - y,
2864                                   acc->xorg - rw, acc->xorg + n);
2865                 if (mask & 8)
2866                     newFinalSpan (acc->yorgl + y,
2867                                   acc->xorg - rw, acc->xorg + n);
2868             }
2869         }
2870         arcSpan (y,
2871                  ICEIL(acc->fromIntX - x), 0,
2872                  ICEIL(acc->fromIntX + x), 0,
2873                  def, bounds, acc, mask);
2874     }
2875 }
2876
2877 /*
2878  * create whole arcs out of pieces.  This code is
2879  * very bad.
2880  */
2881
2882 static struct finalSpan **finalSpans = NULL;
2883 static int              finalMiny = 0, finalMaxy = -1;
2884 static int              finalSize = 0;
2885
2886 static int              nspans = 0;     /* total spans, not just y coords */
2887
2888 struct finalSpan {
2889         struct finalSpan        *next;
2890         int                     min, max;       /* x values */
2891 };
2892
2893 static struct finalSpan    *freeFinalSpans, *tmpFinalSpan;
2894
2895 # define allocFinalSpan()   (freeFinalSpans ?\
2896                                 ((tmpFinalSpan = freeFinalSpans), \
2897                                  (freeFinalSpans = freeFinalSpans->next), \
2898                                  (tmpFinalSpan->next = NULL), \
2899                                  tmpFinalSpan) : \
2900                              realAllocSpan ())
2901
2902 # define SPAN_CHUNK_SIZE    128
2903
2904 struct finalSpanChunk {
2905         struct finalSpan        data[SPAN_CHUNK_SIZE];
2906         struct finalSpanChunk   *next;
2907 };
2908
2909 static struct finalSpanChunk    *chunks;
2910
2911 struct finalSpan *
2912 realAllocSpan (void)
2913 {
2914         register struct finalSpanChunk  *newChunk;
2915         register struct finalSpan       *span;
2916         register int                    i;
2917
2918         newChunk = (struct finalSpanChunk *) g_malloc (sizeof (struct finalSpanChunk));
2919         if (!newChunk)
2920                 return (struct finalSpan *) NULL;
2921         newChunk->next = chunks;
2922         chunks = newChunk;
2923         freeFinalSpans = span = newChunk->data + 1;
2924         for (i = 1; i < SPAN_CHUNK_SIZE-1; i++) {
2925                 span->next = span+1;
2926                 span++;
2927         }
2928         span->next = NULL;
2929         span = newChunk->data;
2930         span->next = NULL;
2931         return span;
2932 }
2933
2934 static void
2935 disposeFinalSpans (void)
2936 {
2937         struct finalSpanChunk   *chunk, *next;
2938
2939         for (chunk = chunks; chunk; chunk = next) {
2940                 next = chunk->next;
2941                 g_free (chunk);
2942         }
2943         chunks = NULL;
2944         freeFinalSpans = NULL;
2945         g_free(finalSpans);
2946         finalSpans = NULL;
2947 }
2948
2949 static void
2950 fillSpans (GdkDrawable *pDrawable, GdkGC *pGC)
2951 {
2952         register struct finalSpan       *span;
2953         register GdkSpan*               xSpan;
2954         register int                    i;
2955         register struct finalSpan       **f;
2956         register int                    spany;
2957         GdkSpan*                        xSpans;
2958
2959         if (nspans == 0)
2960                 return;
2961         xSpan = xSpans = (GdkSpan*) ALLOCATE_LOCAL (nspans * sizeof (GdkSpan));
2962         if (xSpans)
2963         {
2964             i = 0;
2965             f = finalSpans;
2966             for (spany = finalMiny; spany <= finalMaxy; spany++, f++) {
2967                     for (span = *f; span; span=span->next) {
2968                             if (span->max <= span->min)
2969                                     continue;
2970                             xSpan->x = span->min;
2971                             xSpan->y = spany;
2972                             xSpan->width = span->max - span->min;
2973                             ++xSpan;
2974                             ++i;
2975                     }
2976             }
2977
2978             gdk_fb_fill_spans(pDrawable, pGC, xSpans, i, TRUE);
2979         }
2980         disposeFinalSpans ();
2981         if (xSpans)
2982             DEALLOCATE_LOCAL (xSpans);
2983         finalMiny = 0;
2984         finalMaxy = -1;
2985         finalSize = 0;
2986         nspans = 0;
2987 }
2988
2989 # define SPAN_REALLOC   100
2990
2991 # define findSpan(y) ((finalMiny <= (y) && (y) <= finalMaxy) ? \
2992                           &finalSpans[(y) - finalMiny] : \
2993                           realFindSpan (y))
2994
2995 static struct finalSpan **
2996 realFindSpan (int y)
2997 {
2998         struct finalSpan        **newSpans;
2999         int                     newSize, newMiny, newMaxy;
3000         int                     change;
3001         int                     i;
3002
3003         if (y < finalMiny || y > finalMaxy) {
3004                 if (!finalSize) {
3005                         finalMiny = y;
3006                         finalMaxy = y - 1;
3007                 }
3008                 if (y < finalMiny)
3009                         change = finalMiny - y;
3010                 else
3011                         change = y - finalMaxy;
3012                 if (change >= SPAN_REALLOC)
3013                         change += SPAN_REALLOC;
3014                 else
3015                         change = SPAN_REALLOC;
3016                 newSize = finalSize + change;
3017                 newSpans = (struct finalSpan **) g_malloc
3018                                         (newSize * sizeof (struct finalSpan *));
3019                 if (!newSpans)
3020                     return (struct finalSpan **)NULL;
3021                 newMiny = finalMiny;
3022                 newMaxy = finalMaxy;
3023                 if (y < finalMiny)
3024                         newMiny = finalMiny - change;
3025                 else
3026                         newMaxy = finalMaxy + change;
3027                 if (finalSpans) {
3028                         g_memmove(((char *) newSpans) + (finalMiny-newMiny) * sizeof (struct finalSpan *),
3029                                   (char *) finalSpans,
3030                                finalSize * sizeof (struct finalSpan *));
3031                         g_free (finalSpans);
3032                 }
3033                 if ((i = finalMiny - newMiny) > 0)
3034                         memset ((char *)newSpans, 0, i * sizeof (struct finalSpan *));
3035                 if ((i = newMaxy - finalMaxy) > 0)
3036                         memset ((char *)(newSpans + newSize - i), 0,
3037                                i * sizeof (struct finalSpan *));
3038                 finalSpans = newSpans;
3039                 finalMaxy = newMaxy;
3040                 finalMiny = newMiny;
3041                 finalSize = newSize;
3042         }
3043         return &finalSpans[y - finalMiny];
3044 }
3045
3046 static void
3047 newFinalSpan (int y, register int xmin, register int xmax)
3048 {
3049         register struct finalSpan       *x;
3050         register struct finalSpan       **f;
3051         struct finalSpan                *oldx;
3052         struct finalSpan                *prev;
3053
3054         f = findSpan (y);
3055         if (!f)
3056             return;
3057         oldx = NULL;
3058         for (;;) {
3059                 prev = NULL;
3060                 for (x = *f; x; x=x->next) {
3061                         if (x == oldx) {
3062                                 prev = x;
3063                                 continue;
3064                         }
3065                         if (x->min <= xmax && xmin <= x->max) {
3066                                 if (oldx) {
3067                                         oldx->min = MIN (x->min, xmin);
3068                                         oldx->max = MAX (x->max, xmax);
3069                                         if (prev)
3070                                                 prev->next = x->next;
3071                                         else
3072                                                 *f = x->next;
3073                                         --nspans;
3074                                 } else {
3075                                         x->min = MIN (x->min, xmin);
3076                                         x->max = MAX (x->max, xmax);
3077                                         oldx = x;
3078                                 }
3079                                 xmin = oldx->min;
3080                                 xmax = oldx->max;
3081                                 break;
3082                         }
3083                         prev = x;
3084                 }
3085                 if (!x)
3086                         break;
3087         }
3088         if (!oldx) {
3089                 x = allocFinalSpan ();
3090                 if (x)
3091                 {
3092                     x->min = xmin;
3093                     x->max = xmax;
3094                     x->next = *f;
3095                     *f = x;
3096                     ++nspans;
3097                 }
3098         }
3099 }
3100
3101 static void
3102 mirrorSppPoint (int quadrant, SppPointPtr sppPoint)
3103 {
3104         switch (quadrant) {
3105         case 0:
3106                 break;
3107         case 1:
3108                 sppPoint->x = -sppPoint->x;
3109                 break;
3110         case 2:
3111                 sppPoint->x = -sppPoint->x;
3112                 sppPoint->y = -sppPoint->y;
3113                 break;
3114         case 3:
3115                 sppPoint->y = -sppPoint->y;
3116                 break;
3117         }
3118         /*
3119          * and translate to X coordinate system
3120          */
3121         sppPoint->y = -sppPoint->y;
3122 }
3123
3124 /*
3125  * split an arc into pieces which are scan-converted
3126  * in the first-quadrant and mirrored into position.
3127  * This is necessary as the scan-conversion code can
3128  * only deal with arcs completely contained in the
3129  * first quadrant.
3130  */
3131
3132 static void
3133 drawArc (miArc *tarc, int l, int a0, int a1, miArcFacePtr right, miArcFacePtr left)
3134      /* miArcFacePtr    right, left;    */ /* save end line points */
3135 {
3136         struct arc_def          def;
3137         struct accelerators     acc;
3138         int                     startq, endq, curq;
3139         int                     rightq, leftq = 0, righta = 0, lefta = 0;
3140         miArcFacePtr            passRight, passLeft;
3141         int                     q0 = 0, q1 = 0, mask;
3142         struct band {
3143                 int     a0, a1;
3144                 int     mask;
3145         }       band[5], sweep[20];
3146         int                     bandno, sweepno;
3147         int                     i, j;
3148         int                     flipRight = 0, flipLeft = 0;
3149         int                     copyEnd = 0;
3150         miArcSpanData           *spdata;
3151         gboolean                        mustFree;
3152
3153         spdata = miComputeWideEllipse(l, tarc, &mustFree);
3154         if (!spdata)
3155             return;
3156
3157         if (a1 < a0)
3158                 a1 += 360 * 64;
3159         startq = a0 / (90 * 64);
3160         if (a0 == a1)
3161             endq = startq;
3162         else
3163             endq = (a1-1) / (90 * 64);
3164         bandno = 0;
3165         curq = startq;
3166         rightq = -1;
3167         for (;;) {
3168                 switch (curq) {
3169                 case 0:
3170                         if (a0 > 90 * 64)
3171                                 q0 = 0;
3172                         else
3173                                 q0 = a0;
3174                         if (a1 < 360 * 64)
3175                                 q1 = MIN (a1, 90 * 64);
3176                         else
3177                                 q1 = 90 * 64;
3178                         if (curq == startq && a0 == q0 && rightq < 0) {
3179                                 righta = q0;
3180                                 rightq = curq;
3181                         }
3182                         if (curq == endq && a1 == q1) {
3183                                 lefta = q1;
3184                                 leftq = curq;
3185                         }
3186                         break;
3187                 case 1:
3188                         if (a1 < 90 * 64)
3189                                 q0 = 0;
3190                         else
3191                                 q0 = 180 * 64 - MIN (a1, 180 * 64);
3192                         if (a0 > 180 * 64)
3193                                 q1 = 90 * 64;
3194                         else
3195                                 q1 = 180 * 64 - MAX (a0, 90 * 64);
3196                         if (curq == startq && 180 * 64 - a0 == q1) {
3197                                 righta = q1;
3198                                 rightq = curq;
3199                         }
3200                         if (curq == endq && 180 * 64 - a1 == q0) {
3201                                 lefta = q0;
3202                                 leftq = curq;
3203                         }
3204                         break;
3205                 case 2:
3206                         if (a0 > 270 * 64)
3207                                 q0 = 0;
3208                         else
3209                                 q0 = MAX (a0, 180 * 64) - 180 * 64;
3210                         if (a1 < 180 * 64)
3211                                 q1 = 90 * 64;
3212                         else
3213                                 q1 = MIN (a1, 270 * 64) - 180 * 64;
3214                         if (curq == startq && a0 - 180*64 == q0) {
3215                                 righta = q0;
3216                                 rightq = curq;
3217                         }
3218                         if (curq == endq && a1 - 180 * 64 == q1) {
3219                                 lefta = q1;
3220                                 leftq = curq;
3221                         }
3222                         break;
3223                 case 3:
3224                         if (a1 < 270 * 64)
3225                                 q0 = 0;
3226                         else
3227                                 q0 = 360 * 64 - MIN (a1, 360 * 64);
3228                         q1 = 360 * 64 - MAX (a0, 270 * 64);
3229                         if (curq == startq && 360 * 64 - a0 == q1) {
3230                                 righta = q1;
3231                                 rightq = curq;
3232                         }
3233                         if (curq == endq && 360 * 64 - a1 == q0) {
3234                                 lefta = q0;
3235                                 leftq = curq;
3236                         }
3237                         break;
3238                 }
3239                 band[bandno].a0 = q0;
3240                 band[bandno].a1 = q1;
3241                 band[bandno].mask = 1 << curq;
3242                 bandno++;
3243                 if (curq == endq)
3244                         break;
3245                 curq++;
3246                 if (curq == 4) {
3247                         a0 = 0;
3248                         a1 -= 360 * 64;
3249                         curq = 0;
3250                         endq -= 4;
3251                 }
3252         }
3253         sweepno = 0;
3254         for (;;) {
3255                 q0 = 90 * 64;
3256                 mask = 0;
3257                 /*
3258                  * find left-most point
3259                  */
3260                 for (i = 0; i < bandno; i++)
3261                         if (band[i].a0 <= q0) {
3262                                 q0 = band[i].a0;
3263                                 q1 = band[i].a1;
3264                                 mask = band[i].mask;
3265                         }
3266                 if (!mask)
3267                         break;
3268                 /*
3269                  * locate next point of change
3270                  */
3271                 for (i = 0; i < bandno; i++)
3272                         if (!(mask & band[i].mask)) {
3273                                 if (band[i].a0 == q0) {
3274                                         if (band[i].a1 < q1)
3275                                                 q1 = band[i].a1;
3276                                         mask |= band[i].mask;
3277                                 } else if (band[i].a0 < q1)
3278                                         q1 = band[i].a0;
3279                         }
3280                 /*
3281                  * create a new sweep
3282                  */
3283                 sweep[sweepno].a0 = q0;
3284                 sweep[sweepno].a1 = q1;
3285                 sweep[sweepno].mask = mask;
3286                 sweepno++;
3287                 /*
3288                  * subtract the sweep from the affected bands
3289                  */
3290                 for (i = 0; i < bandno; i++)
3291                         if (band[i].a0 == q0) {
3292                                 band[i].a0 = q1;
3293                                 /*
3294                                  * check if this band is empty
3295                                  */
3296                                 if (band[i].a0 == band[i].a1)
3297                                         band[i].a1 = band[i].a0 = 90 * 64 + 1;
3298                         }
3299         }
3300         computeAcc (tarc, l, &def, &acc);
3301         for (j = 0; j < sweepno; j++) {
3302                 mask = sweep[j].mask;
3303                 passRight = passLeft = NULL;
3304                 if (mask & (1 << rightq)) {
3305                         if (sweep[j].a0 == righta)
3306                                 passRight = right;
3307                         else if (sweep[j].a1 == righta) {
3308                                 passLeft = right;
3309                                 flipRight = 1;
3310                         }
3311                 }
3312                 if (mask & (1 << leftq)) {
3313                         if (sweep[j].a1 == lefta)
3314                         {
3315                                 if (passLeft)
3316                                         copyEnd = 1;
3317                                 passLeft = left;
3318                         }
3319                         else if (sweep[j].a0 == lefta) {
3320                                 if (passRight)
3321                                         copyEnd = 1;
3322                                 passRight = left;
3323                                 flipLeft = 1;
3324                         }
3325                 }
3326                 drawQuadrant (&def, &acc, sweep[j].a0, sweep[j].a1, mask,
3327                               passRight, passLeft, spdata);
3328         }
3329         /*
3330          * when copyEnd is set, both ends of the arc were computed
3331          * at the same time; drawQuadrant only takes one end though,
3332          * so the left end will be the only one holding the data.  Copy
3333          * it from there.
3334          */
3335         if (copyEnd)
3336                 *right = *left;
3337         /*
3338          * mirror the coordinates generated for the
3339          * faces of the arc
3340          */
3341         if (right) {
3342                 mirrorSppPoint (rightq, &right->clock);
3343                 mirrorSppPoint (rightq, &right->center);
3344                 mirrorSppPoint (rightq, &right->counterClock);
3345                 if (flipRight) {
3346                         SppPointRec     temp;
3347
3348                         temp = right->clock;
3349                         right->clock = right->counterClock;
3350                         right->counterClock = temp;
3351                 }
3352         }
3353         if (left) {
3354                 mirrorSppPoint (leftq,  &left->counterClock);
3355                 mirrorSppPoint (leftq,  &left->center);
3356                 mirrorSppPoint (leftq,  &left->clock);
3357                 if (flipLeft) {
3358                         SppPointRec     temp;
3359
3360                         temp = left->clock;
3361                         left->clock = left->counterClock;
3362                         left->counterClock = temp;
3363                 }
3364         }
3365         if (mustFree)
3366             g_free(spdata);
3367 }
3368
3369 static void
3370 drawQuadrant (struct arc_def *def, struct accelerators *acc,
3371               int a0, int a1, int mask, miArcFacePtr right,
3372               miArcFacePtr left, miArcSpanData *spdata)
3373 {
3374         struct arc_bound        bound;
3375         double                  yy, x, xalt;
3376         int                     y, miny, maxy;
3377         int                     n;
3378         miArcSpan               *span;
3379
3380         def->a0 = ((double) a0) / 64.0;
3381         def->a1 = ((double) a1) / 64.0;
3382         computeBound (def, &bound, acc, right, left);
3383         yy = bound.inner.min;
3384         if (bound.outer.min < yy)
3385             yy = bound.outer.min;
3386         miny = ICEIL(yy - acc->fromIntY);
3387         yy = bound.inner.max;
3388         if (bound.outer.max > yy)
3389             yy = bound.outer.max;
3390         maxy = floor(yy - acc->fromIntY);
3391         y = spdata->k;
3392         span = spdata->spans;
3393         if (spdata->top)
3394         {
3395             if (a1 == 90 * 64 && (mask & 1))
3396                 newFinalSpan (acc->yorgu - y - 1, acc->xorg, acc->xorg + 1);
3397             span++;
3398         }
3399         for (n = spdata->count1; --n >= 0; )
3400         {
3401             if (y < miny)
3402                 return;
3403             if (y <= maxy) {
3404                 arcSpan (y,
3405                          span->lx, -span->lx, 0, span->lx + span->lw,
3406                          def, &bound, acc, mask);
3407                 if (span->rw + span->rx)
3408                     tailSpan (y, -span->rw, -span->rx, def, &bound, acc, mask);
3409             }
3410             y--;
3411             span++;
3412         }
3413         if (y < miny)
3414             return;
3415         if (spdata->hole)
3416         {
3417             if (y <= maxy)
3418                 arcSpan (y, 0, 0, 0, 1, def, &bound, acc, mask & 0xc);
3419         }
3420         for (n = spdata->count2; --n >= 0; )
3421         {
3422             if (y < miny)
3423                 return;
3424             if (y <= maxy)
3425                 arcSpan (y, span->lx, span->lw, span->rx, span->rw,
3426                          def, &bound, acc, mask);
3427             y--;
3428             span++;
3429         }
3430         if (spdata->bot && miny <= y && y <= maxy)
3431         {
3432             n = mask;
3433             if (y == miny)
3434                 n &= 0xc;
3435             if (span->rw <= 0) {
3436                 arcSpan0 (span->lx, -span->lx, 0, span->lx + span->lw,
3437                           def, &bound, acc, n);
3438                 if (span->rw + span->rx)
3439                     tailSpan (y, -span->rw, -span->rx, def, &bound, acc, n);
3440             }
3441             else
3442                 arcSpan0 (span->lx, span->lw, span->rx, span->rw,
3443                           def, &bound, acc, n);
3444             y--;
3445         }
3446         while (y >= miny) {
3447             yy = y + acc->fromIntY;
3448             if (def->w == def->h) {
3449                 xalt = def->w - def->l;
3450                 x = -sqrt(xalt * xalt - yy * yy);
3451             } else {
3452                 x = tailX(yy, def, &bound, acc);
3453                 if (acc->left.valid && boundedLe (yy, bound.left)) {
3454                     xalt = intersectLine (yy, acc->left);
3455                     if (xalt < x)
3456                         x = xalt;
3457                 }
3458                 if (acc->right.valid && boundedLe (yy, bound.right)) {
3459                     xalt = intersectLine (yy, acc->right);
3460                     if (xalt < x)
3461                         x = xalt;
3462                 }
3463             }
3464             arcSpan (y,
3465                      ICEIL(acc->fromIntX - x), 0,
3466                      ICEIL(acc->fromIntX + x), 0,
3467                      def, &bound, acc, mask);
3468             y--;
3469         }
3470 }