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