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