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