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

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