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