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