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 semantic 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 corresponds 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