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