Commit | Line | Data |
---|---|---|
a09e091a JB |
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 | } |