1 /***********************************************************
3 Copyright (c) 1987 X Consortium
5 Permission is hereby granted, free of charge, to any person obtaining a copy
6 of this software and associated documentation files (the "Software"), to deal
7 in the Software without restriction, including without limitation the rights
8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 copies of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
12 The above copyright notice and this permission notice shall be included in
13 all copies or substantial portions of the Software.
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
19 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 Except as contained in this notice, the name of the X Consortium shall not be
23 used in advertising or otherwise to promote the sale, use or other dealings
24 in this Software without prior written authorization from the X Consortium.
27 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
31 Permission to use, copy, modify, and distribute this software and its
32 documentation for any purpose and without fee is hereby granted,
33 provided that the above copyright notice appear in all copies and that
34 both that copyright notice and this permission notice appear in
35 supporting documentation, and that the name of Digital not be
36 used in advertising or publicity pertaining to distribution of the
37 software without specific, written prior permission.
39 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
40 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
41 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
42 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
43 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
44 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
47 ******************************************************************/
48 /* $XConsortium: miarc.c /main/90 1996/08/01 19:25:10 dpw $ */
49 /* Author: Keith Packard and Bob Scheifler */
50 /* Warning: this code is toxic, do not dally very long here. */
52 /* $XFree86: xc/programs/Xserver/mi/miarc.c,v 3.4.2.1 1997/07/13 14:45:05 dawes Exp $ */
57 #define _XOPEN_SOURCE /* to get prototype for hypot on some systems */
62 #include "Xprotostr.h"
65 #include "scrnintstr.h"
66 #include "pixmapstr.h"
67 #include "windowstr.h"
70 #include "mifillarc.h"
71 #include "Xfuncproto.h"
73 static double miDsin(), miDcos(), miDasin(), miDatan2();
75 #if NeedFunctionPrototypes
85 * some interesting sematic interpretation of the protocol:
87 * Self intersecting arcs (i.e. those spanning 360 degrees)
88 * never join with other arcs, and are drawn without caps
89 * (unless on/off dashed, in which case each dash segment
90 * is capped, except when the last segment meets the
91 * first segment, when no caps are drawn)
93 * double dash arcs are drawn in two parts, first the
94 * odd dashes (drawn in background) then the even dashes
95 * (drawn in foreground). This means that overlapping
96 * sections of foreground/background are drawn twice,
97 * first in background then in foreground. The double-draw
98 * occurs even when the function uses the destination values
99 * (e.g. xor mode). This is the same way the wide-line
100 * code works and should be "fixed".
107 #if defined (__GNUC__) && defined (__STDC__) && !defined (__STRICT_ANSI__)
112 inline static const int max (const int x, const int y)
117 inline static const int min (const int x, const int y)
146 #define boundedLe(value, bounds)\
147 ((bounds).min <= (value) && (value) <= (bounds).max)
154 #define intersectLine(y,line) (line.m * (y) + line.b)
157 * these are all y value bounds
161 struct bound ellipse;
166 struct ibound inneri;
167 struct ibound outeri;
170 struct accelerators {
181 struct line left, right;
192 # define todeg(xAngle) (((double) (xAngle)) / 64.0)
197 typedef struct _miArcJoin {
198 int arcIndex0, arcIndex1;
201 } miArcJoinRec, *miArcJoinPtr;
203 typedef struct _miArcCap {
206 } miArcCapRec, *miArcCapPtr;
208 typedef struct _miArcFace {
211 SppPointRec counterClock;
212 } miArcFaceRec, *miArcFacePtr;
214 typedef struct _miArcData {
216 int render; /* non-zero means render after drawing */
217 int join; /* related join */
218 int cap; /* related cap */
219 int selfJoin; /* final dash meets first dash */
220 miArcFaceRec bounds[2];
221 double x0, y0, x1, y1;
222 } miArcDataRec, *miArcDataPtr;
225 * This is an entire sequence of arcs, computed and categorized according
226 * to operation. miDashArcs generates either one or two of these.
229 typedef struct _miPolyArc {
236 } miPolyArcRec, *miPolyArcPtr;
238 #define GCValsFunction 0
239 #define GCValsForeground 1
240 #define GCValsBackground 2
241 #define GCValsLineWidth 3
242 #define GCValsCapStyle 4
243 #define GCValsJoinStyle 5
244 #define GCValsMask (GCFunction | GCForeground | GCBackground | \
245 GCLineWidth | GCCapStyle | GCJoinStyle)
246 static CARD32 gcvals[6];
248 static void fillSpans(), newFinalSpan();
249 static void drawArc(), drawQuadrant(), drawZeroArc();
250 static void miArcJoin(), miArcCap(), miRoundCap(), miFreeArcs();
251 static int computeAngleFromPath();
252 static miPolyArcPtr miComputeArcs ();
253 static int miGetArcPts();
255 # define CUBED_ROOT_2 1.2599210498948732038115849718451499938964
256 # define CUBED_ROOT_4 1.5874010519681993173435330390930175781250
259 * draw one segment of the arc using the arc spans generation routines
263 miArcSegment(pDraw, pGC, tarc, right, left)
267 miArcFacePtr right, left;
269 int l = pGC->lineWidth;
270 int a0, a1, startAngle, endAngle;
276 if (tarc.width == 0 || tarc.height == 0) {
277 drawZeroArc (pDraw, pGC, &tarc, l, left, right);
281 if (pGC->miTranslate) {
290 else if (a1 < -FULLCIRCLE)
293 startAngle = a0 + a1;
303 * bounds check the two angles
306 startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
307 if (startAngle >= FULLCIRCLE)
308 startAngle = startAngle % FULLCIRCLE;
310 endAngle = FULLCIRCLE - (-endAngle) % FULLCIRCLE;
311 if (endAngle > FULLCIRCLE)
312 endAngle = (endAngle-1) % FULLCIRCLE + 1;
313 if ((startAngle == endAngle) && a1) {
315 endAngle = FULLCIRCLE;
318 drawArc (&tarc, l, startAngle, endAngle, right, left);
323 Three equations combine to describe the boundaries of the arc
325 x^2/w^2 + y^2/h^2 = 1 ellipse itself
326 (X-x)^2 + (Y-y)^2 = r^2 circle at (x, y) on the ellipse
327 (Y-y) = (X-x)*w^2*y/(h^2*x) normal at (x, y) on the ellipse
329 These lead to a quartic relating Y and y
331 y^4 - (2Y)y^3 + (Y^2 + (h^4 - w^2*r^2)/(w^2 - h^2))y^2
332 - (2Y*h^4/(w^2 - h^2))y + (Y^2*h^4)/(w^2 - h^2) = 0
334 The reducible cubic obtained from this quartic is
336 z^3 - (3N)z^2 - 2V = 0
340 N = (Y^2 + (h^4 - w^2*r^2/(w^2 - h^2)))/6
341 V = w^2*r^2*Y^2*h^4/(4 *(w^2 - h^2)^2)
353 The discriminant of this cubic is
357 When D > 0, a real root is obtained as
359 z = N + cbrt(-q+sqrt(D)) + cbrt(-q-sqrt(D))
361 When D < 0, a real root is obtained as
363 z = N - 2m*cos(acos(-q/m^3)/3)
367 m = sqrt(|p|) * sign(q)
369 Given a real root Z of the cubic, the roots of the quartic are the roots
370 of the two quadratics
372 y^2 + ((b+A)/2)y + (Z + (bZ - d)/A) = 0
376 A = +/- sqrt(8Z + b^2 - 4c)
377 b, c, d are the cubic, quadratic, and linear coefficients of the quartic
379 Some experimentation is then required to determine which solutions
380 correspond to the inner and outer boundaries.
385 short lx, lw, rx, rw;
390 int count1, count2, k;
395 unsigned long lrustamp;
397 unsigned short width, height;
398 miArcSpanData *spdata;
403 static arcCacheRec arcCache[CACHESIZE];
404 static unsigned long lrustamp;
405 static arcCacheRec *lastCacheHit = &arcCache[0];
406 static RESTYPE cacheType;
409 * External so it can be called when low on memory.
410 * Call with a zero ID in that case.
414 miFreeArcCache (data, id)
424 for (k = CACHESIZE, cent = &arcCache[0]; --k >= 0; cent++)
439 miComputeCircleSpans(lw, parc, spdata)
442 miArcSpanData *spdata;
444 register miArcSpan *span;
446 register int x, y, e;
447 int xk, yk, xm, ym, dx, dy;
448 register int slw, inslw;
450 int inxk, inyk, inxm, inym;
453 slw = parc->width - doinner;
454 y = parc->height >> 1;
455 dy = parc->height & 1;
457 MIWIDEARCSETUP(x, y, dy, slw, e, xk, xm, yk, ym);
458 inslw = parc->width + doinner;
461 spdata->hole = spdata->top;
462 MIWIDEARCSETUP(inx, iny, dy, inslw, ine, inxk, inxm, inyk, inym);
466 spdata->hole = FALSE;
469 spdata->count1 = -doinner - spdata->top;
470 spdata->count2 = y + doinner;
471 span = spdata->spans;
480 span->rw = span->lx + slw;
484 MIFILLINARCSTEP(inslw);
486 span->rx = dy - inx + inslw;
487 span->rw = inx - x + slw - inslw;
497 if (lw > (int)parc->height)
498 span[-1].rx = span[-1].rw = -((lw - (int)parc->height) >> 1);
507 miComputeEllipseSpans(lw, parc, spdata)
510 miArcSpanData *spdata;
512 register miArcSpan *span;
513 double w, h, r, xorg;
514 double Hs, Hf, WH, K, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
515 double A, T, b, d, x, y, t, inx, outx, hepp, hepm;
518 w = (double)parc->width / 2.0;
519 h = (double)parc->height / 2.0;
525 Vk = (Nk * Hs) / (WH + WH);
527 Nk = (Hf - Nk * Nk) / WH;
531 K = h + ((lw - 1) >> 1);
532 span = spdata->spans;
545 spdata->hole = (spdata->top &&
546 (int)parc->height * lw <= (int)(parc->width * parc->width) &&
547 lw < (int)parc->height);
548 for (; K > 0.0; K -= 1.0)
550 N = (K * K + Nk) / 6.0;
558 if ( (b < 0.0) == (t < 0.0) )
563 Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
564 if ( (Z < 0.0) == (Vr < 0.0) )
572 Z = N + cbrt(t + d) + cbrt(t - d);
575 A = sqrt((Z + Z) - Nk);
576 T = (Fk - Z) * K / A;
580 d = b * b - 4 * (Z + T);
585 if ((y >= 0.0) && (y < hepp))
591 x = w * sqrt(1 - (t * t));
593 if (rs - (t * t) >= 0)
594 t = sqrt(rs - (t * t));
604 d = b * b - 4 * (Z - T);
605 /* Because of the large magnitudes involved, we lose enough precision
606 * that sometimes we end up with a negative value near the axis, when
607 * it should be positive. This is a workaround.
609 if (d < 0 && !solution)
619 x = w * sqrt(1 - (t * t));
621 if (rs - (t * t) >= 0)
622 inx = x - sqrt(rs - (t * t));
632 x = w * sqrt(1 - (t * t));
634 if (rs - (t * t) >= 0)
635 t = sqrt(rs - (t * t));
644 span->lx = ICEIL(xorg - outx);
648 span->lw = ICEIL(xorg + outx) - span->lx;
649 span->rx = ICEIL(xorg + inx);
650 span->rw = -ICEIL(xorg - inx);
655 span->lw = ICEIL(xorg - inx) - span->lx;
656 span->rx = ICEIL(xorg + inx);
657 span->rw = ICEIL(xorg + outx) - span->rx;
664 if (r >= h && r <= w)
666 else if (Nk < 0.0 && -Nk < Hs)
668 inx = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
674 span->lx = ICEIL(xorg - outx);
677 span->lw = ICEIL(xorg + outx) - span->lx;
678 span->rx = ICEIL(xorg + inx);
679 span->rw = -ICEIL(xorg - inx);
683 span->lw = ICEIL(xorg - inx) - span->lx;
684 span->rx = ICEIL(xorg + inx);
685 span->rw = ICEIL(xorg + outx) - span->rx;
690 span = &spdata->spans[spdata->count1];
691 span->lw = -span->lx;
700 tailX(K, def, bounds, acc)
703 struct arc_bound *bounds;
704 struct accelerators *acc;
707 double Hs, Hf, WH, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
708 double A, T, b, d, x, y, t, hepp, hepm;
720 Vk = (Nk * Hs) / (WH + WH);
722 Nk = (Hf - Nk * Nk) / WH;
724 if (Nk < 0.0 && -Nk < Hs) {
725 xs[0] = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
727 if (acc->left.valid && boundedLe(K, bounds->left) &&
728 !boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
730 if (acc->right.valid && boundedLe(K, bounds->right) &&
731 !boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
740 N = (K * K + Nk) / 6.0;
750 if ( (b < 0.0) == (t < 0.0) )
755 Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
756 if ( (Z < 0.0) == (Vr < 0.0) )
764 Z = N + cbrt(t + d) + cbrt(t - d);
767 A = sqrt((Z + Z) - Nk);
768 T = (Fk - Z) * K / A;
771 d = b * b - 4 * (Z + T);
772 if (d >= 0 && flip == 2)
776 if ((y >= 0.0) && (y < hepp))
782 x = w * sqrt(1 - (t * t));
784 if (rs - (t * t) >= 0)
785 t = sqrt(rs - (t * t));
792 d = b * b - 4 * (Z - T);
793 /* Because of the large magnitudes involved, we lose enough precision
794 * that sometimes we end up with a negative value near the axis, when
795 * it should be positive. This is a workaround.
797 if (d < 0 && !solution)
807 x = w * sqrt(1 - (t * t));
809 if (rs - (t * t) >= 0)
810 *xp++ = x - sqrt(rs - (t * t));
815 if (y >= 0.0 && flip == 1)
820 x = w * sqrt(1 - (t * t));
822 if (rs - (t * t) >= 0)
823 t = sqrt(rs - (t * t));
830 if (acc->left.valid && boundedLe(K, bounds->left) &&
831 !boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
833 if (acc->right.valid && boundedLe(K, bounds->right) &&
834 !boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
840 static miArcSpanData *
841 miComputeWideEllipse(lw, parc, mustFree)
846 register miArcSpanData *spdata;
847 register arcCacheRec *cent, *lruent;
853 if (parc->height <= 1500)
857 if (cent->lw == lw &&
858 cent->width == parc->width && cent->height == parc->height)
860 cent->lrustamp = ++lrustamp;
863 lruent = &arcCache[0];
864 for (k = CACHESIZE, cent = lruent; --k >= 0; cent++)
866 if (cent->lw == lw &&
867 cent->width == parc->width && cent->height == parc->height)
869 cent->lrustamp = ++lrustamp;
873 if (cent->lrustamp < lruent->lrustamp)
878 cacheType = CreateNewResourceType(miFreeArcCache);
879 (void) AddResource(FakeClientID(0), cacheType, NULL);
883 lruent->spdata = NULL;
886 k = (parc->height >> 1) + ((lw - 1) >> 1);
887 spdata = lruent->spdata;
888 if (!spdata || spdata->k != k)
892 spdata = (miArcSpanData *)xalloc(sizeof(miArcSpanData) +
893 sizeof(miArcSpan) * (k + 2));
894 lruent->spdata = spdata;
897 lruent->lrustamp = 0;
901 spdata->spans = (miArcSpan *)(spdata + 1);
904 spdata->top = !(lw & 1) && !(parc->width & 1);
905 spdata->bot = !(parc->height & 1);
906 lruent->lrustamp = ++lrustamp;
908 lruent->width = parc->width;
909 lruent->height = parc->height;
910 if (lruent != &fakeent)
911 lastCacheHit = lruent;
912 if (parc->width == parc->height)
913 miComputeCircleSpans(lw, parc, spdata);
915 miComputeEllipseSpans(lw, parc, spdata);
920 miFillWideEllipse(pDraw, pGC, parc)
926 register DDXPointPtr pts;
929 miArcSpanData *spdata;
931 register miArcSpan *span;
932 register int xorg, yorgu, yorgl;
935 yorgu = parc->height + pGC->lineWidth;
936 n = (sizeof(int) * 2) * yorgu;
937 widths = (int *)ALLOCATE_LOCAL(n + (sizeof(DDXPointRec) * 2) * yorgu);
940 points = (DDXPointPtr)((char *)widths + n);
941 spdata = miComputeWideEllipse((int)pGC->lineWidth, parc, &mustFree);
944 DEALLOCATE_LOCAL(widths);
949 span = spdata->spans;
950 xorg = parc->x + (parc->width >> 1);
951 yorgu = parc->y + (parc->height >> 1);
952 yorgl = yorgu + (parc->height & 1);
953 if (pGC->miTranslate)
969 for (n = spdata->count1; --n >= 0; )
971 pts[0].x = xorg + span->lx;
991 for (n = spdata->count2; --n >= 0; )
993 pts[0].x = xorg + span->lx;
996 pts[1].x = xorg + span->rx;
1002 pts[3].x = pts[1].x;
1003 pts[3].y = pts[2].y;
1015 pts[0].x = xorg + span->lx;
1023 pts[0].x = xorg + span->lx;
1026 pts[1].x = xorg + span->rx;
1027 pts[1].y = pts[0].y;
1035 (*pGC->ops->FillSpans)(pDraw, pGC, pts - points, points, widths, FALSE);
1037 DEALLOCATE_LOCAL(widths);
1041 * miPolyArc strategy:
1043 * If arc is zero width and solid, we don't have to worry about the rasterop
1044 * or join styles. For wide solid circles, we use a fast integer algorithm.
1045 * For wide solid ellipses, we use special case floating point code.
1046 * Otherwise, we set up pDrawTo and pGCTo according to the rasterop, then
1047 * draw using pGCTo and pDrawTo. If the raster-op was "tricky," that is,
1048 * if it involves the destination, then we use PushPixels to move the bits
1049 * from the scratch drawable to pDraw. (See the wide line code for a
1050 * fuller explanation of this.)
1054 miPolyArc(pDraw, pGC, narcs, parcs)
1062 int xMin, xMax, yMin, yMax;
1063 int pixmapWidth, pixmapHeight;
1067 DrawablePtr pDrawTo;
1070 miPolyArcPtr polyArcs;
1071 int cap[2], join[2];
1075 width = pGC->lineWidth;
1076 if(width == 0 && pGC->lineStyle == LineSolid)
1078 for(i = narcs, parc = parcs; --i >= 0; parc++)
1079 miArcSegment( pDraw, pGC, *parc,
1080 (miArcFacePtr) 0, (miArcFacePtr) 0 );
1081 fillSpans (pDraw, pGC);
1085 if ((pGC->lineStyle == LineSolid) && narcs)
1087 while (parcs->width && parcs->height &&
1088 (parcs->angle2 >= FULLCIRCLE ||
1089 parcs->angle2 <= -FULLCIRCLE))
1091 miFillWideEllipse(pDraw, pGC, parcs);
1098 /* Set up pDrawTo and pGCTo based on the rasterop */
1101 case GXclear: /* 0 */
1102 case GXcopy: /* src */
1103 case GXcopyInverted: /* NOT src */
1112 /* find bounding box around arcs */
1113 xMin = yMin = MAXSHORT;
1114 xMax = yMax = MINSHORT;
1116 for(i = narcs, parc = parcs; --i >= 0; parc++)
1118 xMin = min (xMin, parc->x);
1119 yMin = min (yMin, parc->y);
1120 xMax = max (xMax, (parc->x + (int) parc->width));
1121 yMax = max (yMax, (parc->y + (int) parc->height));
1124 /* expand box to deal with line widths */
1125 halfWidth = (width + 1)/2;
1131 /* compute pixmap size; limit it to size of drawable */
1132 xOrg = max(xMin, 0);
1133 yOrg = max(yMin, 0);
1134 pixmapWidth = min(xMax, pDraw->width) - xOrg;
1135 pixmapHeight = min(yMax, pDraw->height) - yOrg;
1137 /* if nothing left, return */
1138 if ( (pixmapWidth <= 0) || (pixmapHeight <= 0) ) return;
1140 for(i = narcs, parc = parcs; --i >= 0; parc++)
1145 if (pGC->miTranslate)
1151 /* set up scratch GC */
1153 pGCTo = GetScratchGC(1, pDraw->pScreen);
1156 gcvals[GCValsFunction] = GXcopy;
1157 gcvals[GCValsForeground] = 1;
1158 gcvals[GCValsBackground] = 0;
1159 gcvals[GCValsLineWidth] = pGC->lineWidth;
1160 gcvals[GCValsCapStyle] = pGC->capStyle;
1161 gcvals[GCValsJoinStyle] = pGC->joinStyle;
1162 dixChangeGC(NullClient, pGCTo, GCValsMask, gcvals, NULL);
1164 /* allocate a 1 bit deep pixmap of the appropriate size, and
1166 pDrawTo = (DrawablePtr)(*pDraw->pScreen->CreatePixmap)
1167 (pDraw->pScreen, pixmapWidth, pixmapHeight, 1);
1170 FreeScratchGC(pGCTo);
1173 ValidateGC(pDrawTo, pGCTo);
1174 miClearDrawable(pDrawTo, pGCTo);
1179 if ((pGC->fillStyle == FillTiled) ||
1180 (pGC->fillStyle == FillOpaqueStippled))
1181 bg = fg; /* the protocol sez these don't cause color changes */
1183 polyArcs = miComputeArcs (parcs, narcs, pGC);
1188 (*pDraw->pScreen->DestroyPixmap) ((PixmapPtr)pDrawTo);
1189 FreeScratchGC (pGCTo);
1194 cap[0] = cap[1] = 0;
1195 join[0] = join[1] = 0;
1196 for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);
1201 dixChangeGC (NullClient, pGC, GCForeground, &bg, NULL);
1202 ValidateGC (pDraw, pGC);
1203 } else if (pGC->lineStyle == LineDoubleDash) {
1204 dixChangeGC (NullClient, pGC, GCForeground, &fg, NULL);
1205 ValidateGC (pDraw, pGC);
1207 for (i = 0; i < polyArcs[iphase].narcs; i++) {
1208 miArcDataPtr arcData;
1210 arcData = &polyArcs[iphase].arcs[i];
1211 miArcSegment(pDrawTo, pGCTo, arcData->arc,
1212 &arcData->bounds[RIGHT_END],
1213 &arcData->bounds[LEFT_END]);
1214 if (polyArcs[iphase].arcs[i].render) {
1215 fillSpans (pDrawTo, pGCTo);
1217 * don't cap self-joining arcs
1219 if (polyArcs[iphase].arcs[i].selfJoin &&
1220 cap[iphase] < polyArcs[iphase].arcs[i].cap)
1222 while (cap[iphase] < polyArcs[iphase].arcs[i].cap) {
1224 miArcDataPtr arcData0;
1226 arcIndex = polyArcs[iphase].caps[cap[iphase]].arcIndex;
1227 end = polyArcs[iphase].caps[cap[iphase]].end;
1228 arcData0 = &polyArcs[iphase].arcs[arcIndex];
1229 miArcCap (pDrawTo, pGCTo,
1230 &arcData0->bounds[end], end,
1231 arcData0->arc.x, arcData0->arc.y,
1232 (double) arcData0->arc.width / 2.0,
1233 (double) arcData0->arc.height / 2.0);
1236 while (join[iphase] < polyArcs[iphase].arcs[i].join) {
1237 int arcIndex0, arcIndex1, end0, end1;
1239 miArcDataPtr arcData0, arcData1;
1242 joinp = &polyArcs[iphase].joins[join[iphase]];
1243 arcIndex0 = joinp->arcIndex0;
1245 arcIndex1 = joinp->arcIndex1;
1247 phase0 = joinp->phase0;
1248 phase1 = joinp->phase1;
1249 arcData0 = &polyArcs[phase0].arcs[arcIndex0];
1250 arcData1 = &polyArcs[phase1].arcs[arcIndex1];
1251 miArcJoin (pDrawTo, pGCTo,
1252 &arcData0->bounds[end0],
1253 &arcData1->bounds[end1],
1254 arcData0->arc.x, arcData0->arc.y,
1255 (double) arcData0->arc.width / 2.0,
1256 (double) arcData0->arc.height / 2.0,
1257 arcData1->arc.x, arcData1->arc.y,
1258 (double) arcData1->arc.width / 2.0,
1259 (double) arcData1->arc.height / 2.0);
1263 if (pGC->serialNumber != pDraw->serialNumber)
1264 ValidateGC (pDraw, pGC);
1265 (*pGC->ops->PushPixels) (pGC, (PixmapPtr)pDrawTo,
1266 pDraw, pixmapWidth, pixmapHeight, xOrg, yOrg);
1267 miClearDrawable ((DrawablePtr) pDrawTo, pGCTo);
1272 miFreeArcs(polyArcs, pGC);
1276 (*pGCTo->pScreen->DestroyPixmap)((PixmapPtr)pDrawTo);
1277 FreeScratchGC(pGCTo);
1283 angleBetween (center, point1, point2)
1284 SppPointRec center, point1, point2;
1289 * reflect from X coordinates back to ellipse
1290 * coordinates -- y increasing upwards
1292 a1 = miDatan2 (- (point1.y - center.y), point1.x - center.x);
1293 a2 = miDatan2 (- (point2.y - center.y), point2.x - center.x);
1303 translateBounds (b, x, y, fx, fy)
1314 b->counterClock.x -= fx;
1315 b->counterClock.y -= fy;
1319 miArcJoin (pDraw, pGC, pLeft, pRight,
1320 xOrgLeft, yOrgLeft, xFtransLeft, yFtransLeft,
1321 xOrgRight, yOrgRight, xFtransRight, yFtransRight)
1324 miArcFacePtr pRight, pLeft;
1325 int xOrgRight, yOrgRight;
1326 double xFtransRight, yFtransRight;
1327 int xOrgLeft, yOrgLeft;
1328 double xFtransLeft, yFtransLeft;
1330 SppPointRec center, corner, otherCorner;
1331 SppPointRec poly[5], e;
1332 SppPointPtr pArcPts;
1335 miArcFaceRec Right, Left;
1338 double xFtrans, yFtrans;
1340 double ae, ac2, ec2, bc2, de;
1343 xOrg = (xOrgRight + xOrgLeft) / 2;
1344 yOrg = (yOrgRight + yOrgLeft) / 2;
1345 xFtrans = (xFtransLeft + xFtransRight) / 2;
1346 yFtrans = (yFtransLeft + yFtransRight) / 2;
1348 translateBounds (&Right, xOrg - xOrgRight, yOrg - yOrgRight,
1349 xFtrans - xFtransRight, yFtrans - yFtransRight);
1351 translateBounds (&Left, xOrg - xOrgLeft, yOrg - yOrgLeft,
1352 xFtrans - xFtransLeft, yFtrans - yFtransLeft);
1356 if (pRight->clock.x == pLeft->counterClock.x &&
1357 pRight->clock.y == pLeft->counterClock.y)
1359 center = pRight->center;
1360 if (0 <= (a = angleBetween (center, pRight->clock, pLeft->counterClock))
1363 corner = pRight->clock;
1364 otherCorner = pLeft->counterClock;
1366 a = angleBetween (center, pLeft->clock, pRight->counterClock);
1367 corner = pLeft->clock;
1368 otherCorner = pRight->counterClock;
1370 switch (pGC->joinStyle) {
1372 width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);
1374 arc.x = center.x - width/2;
1375 arc.y = center.y - width/2;
1378 arc.angle1 = -miDatan2 (corner.y - center.y, corner.x - center.x);
1380 pArcPts = (SppPointPtr) xalloc (3 * sizeof (SppPointRec));
1383 pArcPts[0].x = otherCorner.x;
1384 pArcPts[0].y = otherCorner.y;
1385 pArcPts[1].x = center.x;
1386 pArcPts[1].y = center.y;
1387 pArcPts[2].x = corner.x;
1388 pArcPts[2].y = corner.y;
1389 if( (cpt = miGetArcPts(&arc, 3, &pArcPts)) )
1391 /* by drawing with miFillSppPoly and setting the endpoints of the arc
1392 * to be the corners, we assure that the cap will meet up with the
1393 * rest of the line */
1394 miFillSppPoly(pDraw, pGC, cpt, pArcPts, xOrg, yOrg, xFtrans, yFtrans);
1400 * don't miter arcs with less than 11 degrees between them
1405 poly[2] = otherCorner;
1406 bc2 = (corner.x - otherCorner.x) * (corner.x - otherCorner.x) +
1407 (corner.y - otherCorner.y) * (corner.y - otherCorner.y);
1409 ac2 = (corner.x - center.x) * (corner.x - center.x) +
1410 (corner.y - center.y) * (corner.y - center.y);
1411 ae = sqrt (ac2 - ec2);
1413 e.x = (corner.x + otherCorner.x) / 2;
1414 e.y = (corner.y + otherCorner.y) / 2;
1415 poly[3].x = e.x + de * (e.x - center.x) / ae;
1416 poly[3].y = e.y + de * (e.y - center.y) / ae;
1424 poly[2] = otherCorner;
1429 miFillSppPoly (pDraw, pGC, polyLen, poly, xOrg, yOrg, xFtrans, yFtrans);
1434 miArcCap (pDraw, pGC, pFace, end, xOrg, yOrg, xFtrans, yFtrans)
1440 double xFtrans, yFtrans;
1442 SppPointRec corner, otherCorner, center, endPoint, poly[5];
1444 corner = pFace->clock;
1445 otherCorner = pFace->counterClock;
1446 center = pFace->center;
1447 switch (pGC->capStyle) {
1449 poly[0].x = otherCorner.x;
1450 poly[0].y = otherCorner.y;
1451 poly[1].x = corner.x;
1452 poly[1].y = corner.y;
1453 poly[2].x = corner.x -
1454 (center.y - corner.y);
1455 poly[2].y = corner.y +
1456 (center.x - corner.x);
1457 poly[3].x = otherCorner.x -
1458 (otherCorner.y - center.y);
1459 poly[3].y = otherCorner.y +
1460 (otherCorner.x - center.x);
1461 poly[4].x = otherCorner.x;
1462 poly[4].y = otherCorner.y;
1463 miFillSppPoly (pDraw, pGC, 5, poly, xOrg, yOrg, xFtrans, yFtrans);
1467 * miRoundCap just needs these to be unequal.
1470 endPoint.x = endPoint.x + 100;
1471 miRoundCap (pDraw, pGC, center, endPoint, corner, otherCorner, 0,
1472 -xOrg, -yOrg, xFtrans, yFtrans);
1477 /* MIROUNDCAP -- a private helper function
1478 * Put Rounded cap on end. pCenter is the center of this end of the line
1479 * pEnd is the center of the other end of the line. pCorner is one of the
1480 * two corners at this end of the line.
1481 * NOTE: pOtherCorner must be counter-clockwise from pCorner.
1485 miRoundCap(pDraw, pGC, pCenter, pEnd, pCorner, pOtherCorner, fLineEnd,
1486 xOrg, yOrg, xFtrans, yFtrans)
1489 SppPointRec pCenter, pEnd;
1490 SppPointRec pCorner, pOtherCorner;
1491 int fLineEnd, xOrg, yOrg;
1492 double xFtrans, yFtrans;
1498 SppPointPtr pArcPts;
1500 width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);
1502 arc.x = pCenter.x - width/2;
1503 arc.y = pCenter.y - width/2;
1506 arc.angle1 = -miDatan2 (pCorner.y - pCenter.y, pCorner.x - pCenter.x);
1507 if(PTISEQUAL(pCenter, pEnd))
1508 arc.angle2 = - 180.0;
1510 arc.angle2 = -miDatan2 (pOtherCorner.y - pCenter.y, pOtherCorner.x - pCenter.x) - arc.angle1;
1512 arc.angle2 += 360.0;
1514 pArcPts = (SppPointPtr) NULL;
1515 if( (cpt = miGetArcPts(&arc, 0, &pArcPts)) )
1517 /* by drawing with miFillSppPoly and setting the endpoints of the arc
1518 * to be the corners, we assure that the cap will meet up with the
1519 * rest of the line */
1520 miFillSppPoly(pDraw, pGC, cpt, pArcPts, -xOrg, -yOrg, xFtrans, yFtrans);
1526 * To avoid inaccuracy at the cardinal points, use trig functions
1527 * which are exact for those angles
1531 #define M_PI 3.14159265358979323846
1534 #define M_PI_2 1.57079632679489661923
1537 # define Dsin(d) ((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))
1538 # define Dcos(d) ((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))
1539 # define mod(a,b) ((a) >= 0 ? (a) % (b) : (b) - (-a) % (b))
1547 if (floor (a/90) == a/90) {
1549 switch (mod (i, 4)) {
1556 return cos (a * M_PI / 180.0);
1565 if (floor (a/90) == a/90) {
1567 switch (mod (i, 4)) {
1574 return sin (a * M_PI / 180.0);
1587 return asin(v) * (180.0 / M_PI);
1598 } else if (dx == 0) {
1602 } else if (Fabs (dy) == Fabs (dx)) {
1613 return atan2 (dy, dx) * (180.0 / M_PI);
1617 /* MIGETARCPTS -- Converts an arc into a set of line segments -- a helper
1618 * routine for filled arc and line (round cap) code.
1619 * Returns the number of points in the arc. Note that it takes a pointer
1620 * to a pointer to where it should put the points and an index (cpt).
1621 * This procedure allocates the space necessary to fit the arc points.
1622 * Sometimes it's convenient for those points to be at the end of an existing
1623 * array. (For example, if we want to leave a spare point to make sectors
1624 * instead of segments.) So we pass in the xalloc()ed chunk that contains the
1625 * array and an index saying where we should start stashing the points.
1626 * If there isn't an array already, we just pass in a null pointer and
1627 * count on xrealloc() to handle the null pointer correctly.
1630 miGetArcPts(parc, cpt, ppPts)
1631 SppArcPtr parc; /* points to an arc */
1632 int cpt; /* number of points already in arc list */
1633 SppPointPtr *ppPts; /* pointer to pointer to arc-list -- modified */
1635 double st, /* Start Theta, start angle */
1636 et, /* End Theta, offset from start theta */
1637 dt, /* Delta Theta, angle to sweep ellipse */
1638 cdt, /* Cos Delta Theta, actually 2 cos(dt) */
1639 x0, y0, /* the recurrence formula needs two points to start */
1641 x2, y2, /* this will be the new point generated */
1642 xc, yc; /* the center point */
1645 DDXPointRec last; /* last point on integer boundaries */
1647 /* The spec says that positive angles indicate counterclockwise motion.
1648 * Given our coordinate system (with 0,0 in the upper left corner),
1649 * the screen appears flipped in Y. The easiest fix is to negate the
1652 st = - parc->angle1;
1654 et = - parc->angle2;
1656 /* Try to get a delta theta that is within 1/2 pixel. Then adjust it
1657 * so that it divides evenly into the total.
1658 * I'm just using cdt 'cause I'm lazy.
1661 if (parc->height > cdt)
1668 dt = miDasin ( 1.0 / cdt ); /* minimum step necessary */
1670 count = abs(count) + 1;
1674 cdt = 2 * miDcos(dt);
1675 if (!(poly = (SppPointPtr) xrealloc((pointer)*ppPts,
1676 (cpt + count) * sizeof(SppPointRec))))
1680 xc = parc->width/2.0; /* store half width and half height */
1681 yc = parc->height/2.0;
1683 x0 = xc * miDcos(st);
1684 y0 = yc * miDsin(st);
1685 x1 = xc * miDcos(st + dt);
1686 y1 = yc * miDsin(st + dt);
1687 xc += parc->x; /* by adding initial point, these become */
1688 yc += parc->y; /* the center point */
1690 poly[cpt].x = (xc + x0);
1691 poly[cpt].y = (yc + y0);
1692 last.x = ROUNDTOINT( poly[cpt + 1].x = (xc + x1) );
1693 last.y = ROUNDTOINT( poly[cpt + 1].y = (yc + y1) );
1695 for(i = 2; i < count; i++)
1700 poly[cpt + i].x = (xc + x2);
1701 poly[cpt + i].y = (yc + y2);
1706 /* adjust the last point */
1707 if (abs(parc->angle2) >= 360.0)
1708 poly[cpt +i -1] = poly[0];
1710 poly[cpt +i -1].x = (miDcos(st + et) * parc->width/2.0 + xc);
1711 poly[cpt +i -1].y = (miDsin(st + et) * parc->height/2.0 + yc);
1718 double x0, y0, x1, y1;
1722 # define ADD_REALLOC_STEP 20
1725 addCap (capsp, ncapsp, sizep, end, arcIndex)
1727 int *ncapsp, *sizep;
1733 if (*ncapsp == *sizep)
1735 newsize = *sizep + ADD_REALLOC_STEP;
1736 cap = (miArcCapPtr) xrealloc (*capsp,
1737 newsize * sizeof (**capsp));
1743 cap = &(*capsp)[*ncapsp];
1745 cap->arcIndex = arcIndex;
1750 addJoin (joinsp, njoinsp, sizep, end0, index0, phase0, end1, index1, phase1)
1751 miArcJoinPtr *joinsp;
1752 int *njoinsp, *sizep;
1753 int end0, index0, phase0, end1, index1, phase1;
1758 if (*njoinsp == *sizep)
1760 newsize = *sizep + ADD_REALLOC_STEP;
1761 join = (miArcJoinPtr) xrealloc (*joinsp,
1762 newsize * sizeof (**joinsp));
1768 join = &(*joinsp)[*njoinsp];
1770 join->arcIndex0 = index0;
1771 join->phase0 = phase0;
1773 join->arcIndex1 = index1;
1774 join->phase1 = phase1;
1779 addArc (arcsp, narcsp, sizep, xarc)
1780 miArcDataPtr *arcsp;
1781 int *narcsp, *sizep;
1787 if (*narcsp == *sizep)
1789 newsize = *sizep + ADD_REALLOC_STEP;
1790 arc = (miArcDataPtr) xrealloc (*arcsp,
1791 newsize * sizeof (**arcsp));
1793 return (miArcDataPtr)NULL;
1797 arc = &(*arcsp)[*narcsp];
1804 miFreeArcs(arcs, pGC)
1810 for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);
1814 if (arcs[iphase].narcs > 0)
1815 xfree(arcs[iphase].arcs);
1816 if (arcs[iphase].njoins > 0)
1817 xfree(arcs[iphase].joins);
1818 if (arcs[iphase].ncaps > 0)
1819 xfree(arcs[iphase].caps);
1825 * map angles to radial distance. This only deals with the first quadrant
1829 * a polygonal approximation to the arc for computing arc lengths
1832 # define DASH_MAP_SIZE 91
1834 # define dashIndexToAngle(di) ((((double) (di)) * 90.0) / ((double) DASH_MAP_SIZE - 1))
1835 # define xAngleToDashIndex(xa) ((((long) (xa)) * (DASH_MAP_SIZE - 1)) / (90 * 64))
1836 # define dashIndexToXAngle(di) ((((long) (di)) * (90 * 64)) / (DASH_MAP_SIZE - 1))
1837 # define dashXAngleStep (((double) (90 * 64)) / ((double) (DASH_MAP_SIZE - 1)))
1840 double map[DASH_MAP_SIZE];
1844 computeDashMap (arcp, map)
1849 double a, x, y, prevx, prevy, dist;
1851 for (di = 0; di < DASH_MAP_SIZE; di++) {
1852 a = dashIndexToAngle (di);
1853 x = ((double) arcp->width / 2.0) * miDcos (a);
1854 y = ((double) arcp->height / 2.0) * miDsin (a);
1858 dist = hypot (x - prevx, y - prevy);
1859 map->map[di] = map->map[di - 1] + dist;
1866 typedef enum {HORIZONTAL, VERTICAL, OTHER} arcTypes;
1868 /* this routine is a bit gory */
1871 miComputeArcs (parcs, narcs, pGC)
1876 int isDashed, isDoubleDash;
1879 int start, i, j, k, nexti, nextk;
1885 struct arcData *data;
1888 int iphase, prevphase, joinphase;
1892 int iDash, dashRemaining;
1893 int iDashStart, dashRemainingStart, iphaseStart;
1894 int startAngle, spanAngle, endAngle, backwards;
1895 int prevDashAngle, dashAngle;
1898 isDashed = !(pGC->lineStyle == LineSolid);
1899 isDoubleDash = (pGC->lineStyle == LineDoubleDash);
1900 dashOffset = pGC->dashOffset;
1902 data = (struct arcData *) ALLOCATE_LOCAL (narcs * sizeof (struct arcData));
1904 return (miPolyArcPtr)NULL;
1905 arcs = (miPolyArcPtr) xalloc (sizeof (*arcs) * (isDoubleDash ? 2 : 1));
1908 DEALLOCATE_LOCAL(data);
1909 return (miPolyArcPtr)NULL;
1911 for (i = 0; i < narcs; i++) {
1912 a0 = todeg (parcs[i].angle1);
1913 angle2 = parcs[i].angle2;
1914 if (angle2 > FULLCIRCLE)
1915 angle2 = FULLCIRCLE;
1916 else if (angle2 < -FULLCIRCLE)
1917 angle2 = -FULLCIRCLE;
1918 data[i].selfJoin = angle2 == FULLCIRCLE || angle2 == -FULLCIRCLE;
1919 a1 = todeg (parcs[i].angle1 + angle2);
1920 data[i].x0 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a0));
1921 data[i].y0 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a0));
1922 data[i].x1 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a1));
1923 data[i].y1 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a1));
1926 for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++) {
1927 arcs[iphase].njoins = 0;
1928 arcs[iphase].joins = 0;
1929 joinSize[iphase] = 0;
1931 arcs[iphase].ncaps = 0;
1932 arcs[iphase].caps = 0;
1933 capSize[iphase] = 0;
1935 arcs[iphase].narcs = 0;
1936 arcs[iphase].arcs = 0;
1937 arcSize[iphase] = 0;
1943 dashRemaining = pGC->dash[0];
1944 while (dashOffset > 0) {
1945 if (dashOffset >= dashRemaining) {
1946 dashOffset -= dashRemaining;
1947 iphase = iphase ? 0 : 1;
1949 if (iDash == pGC->numInDashList)
1951 dashRemaining = pGC->dash[iDash];
1953 dashRemaining -= dashOffset;
1958 dashRemainingStart = dashRemaining;
1960 iphaseStart = iphase;
1962 for (i = narcs - 1; i >= 0; i--) {
1966 if (data[i].selfJoin || i == j ||
1967 (UNEQUAL (data[i].x1, data[j].x0) ||
1968 UNEQUAL (data[i].y1, data[j].y0)))
1970 if (iphase == 0 || isDoubleDash)
1971 addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
1972 &capSize[iphase], RIGHT_END, 0);
1989 ** deal with dashed arcs. Use special rules for certain 0 area arcs.
1990 ** Presumably, the other 0 area arcs still aren't done right.
1992 arcTypes arcType = OTHER;
1995 if (parcs[i].height == 0
1996 && (parcs[i].angle1 % FULLCIRCLE) == 0x2d00
1997 && parcs[i].angle2 == 0x2d00)
1998 arcType = HORIZONTAL;
1999 else if (parcs[i].width == 0
2000 && (parcs[i].angle1 % FULLCIRCLE) == 0x1680
2001 && parcs[i].angle2 == 0x2d00)
2003 if (arcType == OTHER) {
2005 * precompute an approximation map
2007 computeDashMap (&parcs[i], &map);
2009 * compute each individual dash segment using the path
2012 startAngle = parcs[i].angle1;
2013 spanAngle = parcs[i].angle2;
2014 if (spanAngle > FULLCIRCLE)
2015 spanAngle = FULLCIRCLE;
2016 else if (spanAngle < -FULLCIRCLE)
2017 spanAngle = -FULLCIRCLE;
2019 startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
2020 if (startAngle >= FULLCIRCLE)
2021 startAngle = startAngle % FULLCIRCLE;
2022 endAngle = startAngle + spanAngle;
2023 backwards = spanAngle < 0;
2026 if (arcType == VERTICAL) {
2027 xarc.angle1 = 0x1680;
2028 startAngle = parcs[i].y;
2029 endAngle = startAngle + parcs[i].height;
2031 xarc.angle1 = 0x2d00;
2032 startAngle = parcs[i].x;
2033 endAngle = startAngle + parcs[i].width;
2036 dashAngle = startAngle;
2037 selfJoin = data[i].selfJoin &&
2038 (iphase == 0 || isDoubleDash);
2040 * add dashed arcs to each bucket
2043 while (dashAngle != endAngle) {
2044 prevDashAngle = dashAngle;
2045 if (arcType == OTHER) {
2046 dashAngle = computeAngleFromPath (prevDashAngle, endAngle,
2047 &map, &dashRemaining, backwards);
2048 /* avoid troubles with huge arcs and small dashes */
2049 if (dashAngle == prevDashAngle) {
2056 thisLength = (dashAngle + dashRemaining <= endAngle) ?
2057 dashRemaining : endAngle - dashAngle;
2058 if (arcType == VERTICAL) {
2060 xarc.height = thisLength;
2063 xarc.width = thisLength;
2065 dashAngle += thisLength;
2066 dashRemaining -= thisLength;
2068 if (iphase == 0 || isDoubleDash) {
2069 if (arcType == OTHER) {
2071 spanAngle = prevDashAngle;
2073 spanAngle = FULLCIRCLE - (-spanAngle) % FULLCIRCLE;
2074 if (spanAngle >= FULLCIRCLE)
2075 spanAngle = spanAngle % FULLCIRCLE;
2076 xarc.angle1 = spanAngle;
2077 spanAngle = dashAngle - prevDashAngle;
2079 if (dashAngle > prevDashAngle)
2080 spanAngle = - FULLCIRCLE + spanAngle;
2082 if (dashAngle < prevDashAngle)
2083 spanAngle = FULLCIRCLE + spanAngle;
2085 if (spanAngle > FULLCIRCLE)
2086 spanAngle = FULLCIRCLE;
2087 if (spanAngle < -FULLCIRCLE)
2088 spanAngle = -FULLCIRCLE;
2089 xarc.angle2 = spanAngle;
2091 arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
2092 &arcSize[iphase], &xarc);
2096 * cap each end of an on/off dash
2098 if (!isDoubleDash) {
2099 if (prevDashAngle != startAngle) {
2100 addCap (&arcs[iphase].caps,
2101 &arcs[iphase].ncaps,
2102 &capSize[iphase], RIGHT_END,
2103 arc - arcs[iphase].arcs);
2106 if (dashAngle != endAngle) {
2107 addCap (&arcs[iphase].caps,
2108 &arcs[iphase].ncaps,
2109 &capSize[iphase], LEFT_END,
2110 arc - arcs[iphase].arcs);
2113 arc->cap = arcs[iphase].ncaps;
2114 arc->join = arcs[iphase].njoins;
2117 if (dashAngle == endAngle)
2118 arc->selfJoin = selfJoin;
2121 if (dashRemaining <= 0) {
2123 if (iDash == pGC->numInDashList)
2125 iphase = iphase ? 0:1;
2126 dashRemaining = pGC->dash[iDash];
2130 * make sure a place exists for the position data when
2131 * drawing a zero-length arc
2133 if (startAngle == endAngle) {
2135 if (!isDoubleDash && iphase == 1)
2137 arc = addArc (&arcs[prevphase].arcs, &arcs[prevphase].narcs,
2138 &arcSize[prevphase], &parcs[i]);
2141 arc->join = arcs[prevphase].njoins;
2142 arc->cap = arcs[prevphase].ncaps;
2143 arc->selfJoin = data[i].selfJoin;
2146 arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
2147 &arcSize[iphase], &parcs[i]);
2150 arc->join = arcs[iphase].njoins;
2151 arc->cap = arcs[iphase].ncaps;
2152 arc->selfJoin = data[i].selfJoin;
2155 if (prevphase == 0 || isDoubleDash)
2156 k = arcs[prevphase].narcs - 1;
2157 if (iphase == 0 || isDoubleDash)
2158 nextk = arcs[iphase].narcs;
2159 if (nexti == start) {
2163 iphase = iphaseStart;
2164 dashRemaining = dashRemainingStart;
2167 arcsJoin = narcs > 1 && i != j &&
2168 ISEQUAL (data[i].x1, data[j].x0) &&
2169 ISEQUAL (data[i].y1, data[j].y0) &&
2170 !data[i].selfJoin && !data[j].selfJoin;
2179 (prevphase == 0 || isDoubleDash) &&
2180 (iphase == 0 || isDoubleDash))
2185 joinphase = iphaseStart;
2187 * if the join is right at the dash,
2188 * draw the join in foreground
2189 * This is because the foreground
2190 * arcs are computed second, the results
2191 * of which are needed to draw the join
2193 if (joinphase != prevphase)
2196 if (joinphase == 0 || isDoubleDash) {
2197 addJoin (&arcs[joinphase].joins,
2198 &arcs[joinphase].njoins,
2199 &joinSize[joinphase],
2200 LEFT_END, k, prevphase,
2201 RIGHT_END, nextk, iphase);
2202 arc->join = arcs[prevphase].njoins;
2206 * cap the left end of this arc
2207 * unless it joins itself
2209 if ((prevphase == 0 || isDoubleDash) &&
2212 addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
2213 &capSize[prevphase], LEFT_END, k);
2214 arc->cap = arcs[prevphase].ncaps;
2216 if (isDashed && !arcsJoin) {
2218 iphase = iphaseStart;
2219 dashRemaining = dashRemainingStart;
2221 nextk = arcs[iphase].narcs;
2222 if (nexti == start) {
2225 iphase = iphaseStart;
2226 dashRemaining = dashRemainingStart;
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
2237 if ((iphase == 0 || isDoubleDash) &&
2238 (nexti != start || (arcsJoin && isDashed)))
2239 addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
2240 &capSize[iphase], RIGHT_END, nextk);
2247 * make sure the last section is rendered
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 =
2257 DEALLOCATE_LOCAL(data);
2260 miFreeArcs(arcs, pGC);
2261 DEALLOCATE_LOCAL(data);
2262 return (miPolyArcPtr)NULL;
2266 angleToLength (angle, map)
2270 double len, excesslen, sidelen = map->map[DASH_MAP_SIZE - 1], totallen;
2273 Bool oddSide = FALSE;
2277 while (angle >= 90 * 64) {
2279 totallen += sidelen;
2285 totallen -= sidelen;
2290 angle = 90 * 64 - angle;
2292 di = xAngleToDashIndex (angle);
2293 excess = angle - dashIndexToXAngle (di);
2297 * linearly interpolate between this point and the next
2300 excesslen = (map->map[di + 1] - map->map[di]) *
2301 ((double) excess) / dashXAngleStep;
2305 totallen += (sidelen - len);
2312 * len is along the arc, but may be more than one rotation
2316 lengthToAngle (len, map)
2320 double sidelen = map->map[DASH_MAP_SIZE - 1];
2321 int angle, angleexcess;
2322 Bool oddSide = FALSE;
2327 * step around the ellipse, subtracting sidelens and
2328 * adding 90 degrees. oddSide will tell if the
2329 * map should be interpolated in reverse
2333 return 2 * FULLCIRCLE; /* infinity */
2334 while (len >= sidelen) {
2341 return -2 * FULLCIRCLE; /* infinity */
2349 len = sidelen - len;
2351 a1 = DASH_MAP_SIZE - 1;
2353 * binary search for the closest pre-computed length
2355 while (a1 - a0 > 1) {
2357 if (len > map->map[a])
2362 angleexcess = dashIndexToXAngle (a0);
2364 * linearly interpolate to the next point
2366 angleexcess += (len - map->map[a0]) /
2367 (map->map[a0+1] - map->map[a0]) * dashXAngleStep;
2369 angle += (90 * 64) - angleexcess;
2371 angle += angleexcess;
2376 * compute the angle of an ellipse which cooresponds to
2377 * the given path length. Note that the correct solution
2378 * to this problem is an eliptic integral, we'll punt and
2379 * approximate (it's only for dashes anyway). This
2380 * approximation uses a polygon.
2382 * The remaining portion of len is stored in *lenp -
2383 * this will be negative if the arc extends beyond
2384 * len and positive if len extends beyond the arc.
2388 computeAngleFromPath (startAngle, endAngle, map, lenp, backwards)
2389 int startAngle, endAngle; /* normalized absolute angles in *64 degrees */
2403 * flip the problem around to always be
2406 a0 = FULLCIRCLE - a0;
2407 a1 = FULLCIRCLE - a1;
2411 len0 = angleToLength (a0, map);
2412 a = lengthToAngle (len0 + len, map);
2415 len -= angleToLength (a1, map) - len0;
2425 * scan convert wide arcs.
2429 * draw zero width/height arcs
2433 drawZeroArc (pDraw, pGC, tarc, lw, left, right)
2438 miArcFacePtr right, left;
2440 double x0, y0, x1, y1, w, h, x, y;
2441 double xmax, ymax, xmin, ymin;
2443 double a, startAngle, endAngle;
2449 if (a1 > FULLCIRCLE)
2451 else if (a1 < -FULLCIRCLE)
2453 w = (double)tarc->width / 2.0;
2454 h = (double)tarc->height / 2.0;
2456 * play in X coordinates right away
2458 startAngle = - ((double) a0 / 64.0);
2459 endAngle = - ((double) (a0 + a1) / 64.0);
2470 if (a == startAngle)
2490 if (a1 < 0) /* clockwise */
2492 if (floor (a / 90.0) == floor (endAngle / 90.0))
2495 a = 90 * (floor (a/90.0) + 1);
2499 if (ceil (a / 90.0) == ceil (endAngle / 90.0))
2502 a = 90 * (ceil (a/90.0) - 1);
2506 if ((x1 - x0) + (y1 - y0) < 0)
2517 right->center.x = x0;
2518 right->center.y = y0;
2519 right->clock.x = x0 - lx;
2520 right->clock.y = y0 - ly;
2521 right->counterClock.x = x0 + lx;
2522 right->counterClock.y = y0 + ly;
2526 left->center.x = x1;
2527 left->center.y = y1;
2528 left->clock.x = x1 + lx;
2529 left->clock.y = y1 + ly;
2530 left->counterClock.x = x1 - lx;
2531 left->counterClock.y = y1 - ly;
2545 if (xmax != xmin && ymax != ymin) {
2546 int minx, maxx, miny, maxy;
2549 minx = ICEIL (xmin + w) + tarc->x;
2550 maxx = ICEIL (xmax + w) + tarc->x;
2551 miny = ICEIL (ymin + h) + tarc->y;
2552 maxy = ICEIL (ymax + h) + tarc->y;
2555 rect.width = maxx - minx;
2556 rect.height = maxy - miny;
2557 (*pGC->ops->PolyFillRect) (pDraw, pGC, 1, &rect);
2562 * this computes the ellipse y value associated with the
2563 * bottom of the tail.
2567 tailEllipseY (def, acc)
2568 struct arc_def *def;
2569 struct accelerators *acc;
2574 if (def->w == def->h)
2576 t = def->l * def->w;
2577 if (def->w > def->h) {
2584 t = 2.0 * def->h * t;
2585 t = (CUBED_ROOT_4 * acc->h2 - cbrt(t * t)) / acc->h2mw2;
2587 acc->tail_y = def->h / CUBED_ROOT_2 * sqrt(t);
2591 * inverse functions -- compute edge coordinates
2596 outerXfromXY (x, y, def, acc)
2598 struct arc_def *def;
2599 struct accelerators *acc;
2601 return x + (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2605 outerYfromXY (x, y, def, acc)
2607 struct arc_def *def;
2608 struct accelerators *acc;
2610 return y + (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2614 innerXfromXY (x, y, def, acc)
2616 struct arc_def *def;
2617 struct accelerators *acc;
2619 return x - (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2623 innerYfromXY (x, y, def, acc)
2625 struct arc_def *def;
2626 struct accelerators *acc;
2628 return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2632 innerYfromY (y, def, acc)
2634 struct arc_def *def;
2635 struct accelerators *acc;
2639 x = (def->w / def->h) * sqrt (acc->h2 - y*y);
2641 return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2645 computeLine (x1, y1, x2, y2, line)
2646 double x1, y1, x2, y2;
2652 line->m = (x1 - x2) / (y1 - y2);
2653 line->b = x1 - y1 * line->m;
2659 * compute various accelerators for an ellipse. These
2660 * are simply values that are used repeatedly in
2665 computeAcc (tarc, lw, def, acc)
2668 struct arc_def *def;
2669 struct accelerators *acc;
2671 def->w = ((double) tarc->width) / 2.0;
2672 def->h = ((double) tarc->height) / 2.0;
2673 def->l = ((double) lw) / 2.0;
2674 acc->h2 = def->h * def->h;
2675 acc->w2 = def->w * def->w;
2676 acc->h4 = acc->h2 * acc->h2;
2677 acc->w4 = acc->w2 * acc->w2;
2678 acc->h2l = acc->h2 * def->l;
2679 acc->w2l = acc->w2 * def->l;
2680 acc->h2mw2 = acc->h2 - acc->w2;
2681 acc->fromIntX = (tarc->width & 1) ? 0.5 : 0.0;
2682 acc->fromIntY = (tarc->height & 1) ? 0.5 : 0.0;
2683 acc->xorg = tarc->x + (tarc->width >> 1);
2684 acc->yorgu = tarc->y + (tarc->height >> 1);
2685 acc->yorgl = acc->yorgu + (tarc->height & 1);
2686 tailEllipseY (def, acc);
2690 * compute y value bounds of various portions of the arc,
2691 * the outer edge, the ellipse and the inner edge.
2695 computeBound (def, bound, acc, right, left)
2696 struct arc_def *def;
2697 struct arc_bound *bound;
2698 struct accelerators *acc;
2699 miArcFacePtr right, left;
2704 struct bound innerx, outerx;
2705 struct bound ellipsex;
2707 bound->ellipse.min = Dsin (def->a0) * def->h;
2708 bound->ellipse.max = Dsin (def->a1) * def->h;
2709 if (def->a0 == 45 && def->w == def->h)
2710 ellipsex.min = bound->ellipse.min;
2712 ellipsex.min = Dcos (def->a0) * def->w;
2713 if (def->a1 == 45 && def->w == def->h)
2714 ellipsex.max = bound->ellipse.max;
2716 ellipsex.max = Dcos (def->a1) * def->w;
2717 bound->outer.min = outerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2718 bound->outer.max = outerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2719 bound->inner.min = innerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2720 bound->inner.max = innerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2722 outerx.min = outerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2723 outerx.max = outerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2724 innerx.min = innerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2725 innerx.max = innerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2728 * save the line end points for the
2729 * cap code to use. Careful here, these are
2730 * in cartesean coordinates (y increasing upwards)
2731 * while the cap code uses inverted coordinates
2732 * (y increasing downwards)
2736 right->counterClock.y = bound->outer.min;
2737 right->counterClock.x = outerx.min;
2738 right->center.y = bound->ellipse.min;
2739 right->center.x = ellipsex.min;
2740 right->clock.y = bound->inner.min;
2741 right->clock.x = innerx.min;
2745 left->clock.y = bound->outer.max;
2746 left->clock.x = outerx.max;
2747 left->center.y = bound->ellipse.max;
2748 left->center.x = ellipsex.max;
2749 left->counterClock.y = bound->inner.max;
2750 left->counterClock.x = innerx.max;
2753 bound->left.min = bound->inner.max;
2754 bound->left.max = bound->outer.max;
2755 bound->right.min = bound->inner.min;
2756 bound->right.max = bound->outer.min;
2758 computeLine (innerx.min, bound->inner.min, outerx.min, bound->outer.min,
2760 computeLine (innerx.max, bound->inner.max, outerx.max, bound->outer.max,
2763 if (bound->inner.min > bound->inner.max) {
2764 t = bound->inner.min;
2765 bound->inner.min = bound->inner.max;
2766 bound->inner.max = t;
2768 tail_y = acc->tail_y;
2769 if (tail_y > bound->ellipse.max)
2770 tail_y = bound->ellipse.max;
2771 else if (tail_y < bound->ellipse.min)
2772 tail_y = bound->ellipse.min;
2773 innerTaily = innerYfromY (tail_y, def, acc);
2774 if (bound->inner.min > innerTaily)
2775 bound->inner.min = innerTaily;
2776 if (bound->inner.max < innerTaily)
2777 bound->inner.max = innerTaily;
2778 bound->inneri.min = ICEIL(bound->inner.min - acc->fromIntY);
2779 bound->inneri.max = floor(bound->inner.max - acc->fromIntY);
2780 bound->outeri.min = ICEIL(bound->outer.min - acc->fromIntY);
2781 bound->outeri.max = floor(bound->outer.max - acc->fromIntY);
2785 * this section computes the x value of the span at y
2786 * intersected with the specified face of the ellipse.
2788 * this is the min/max X value over the set of normal
2789 * lines to the entire ellipse, the equation of the
2793 * x = ------------ y + ellipse_x (1 - --- )
2796 * compute the derivative with-respect-to ellipse_y and solve
2799 * (w^2 - h^2) ellipse_y^3 + h^4 y
2800 * 0 = - ----------------------------------
2801 * h w ellipse_y^2 sqrt (h^2 - ellipse_y^2)
2804 * ellipse_y = ( ---------- ) ^ (1/3)
2807 * The other two solutions to the equation are imaginary.
2809 * This gives the position on the ellipse which generates
2810 * the normal with the largest/smallest x intersection point.
2812 * Now compute the second derivative to check whether
2813 * the intersection is a minimum or maximum:
2815 * h (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2816 * - -------------------------------------------
2817 * w y0^3 (sqrt (h^2 - y^2)) ^ 3
2819 * as we only care about the sign,
2821 * - (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2823 * or (to use accelerators),
2825 * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2)
2830 * computes the position on the ellipse whose normal line
2831 * intersects the given scan line maximally
2835 hookEllipseY (scan_y, bound, acc, left)
2837 struct arc_bound *bound;
2838 struct accelerators *acc;
2843 if (acc->h2mw2 == 0) {
2844 if ( (scan_y > 0 && !left) || (scan_y < 0 && left) )
2845 return bound->ellipse.min;
2846 return bound->ellipse.max;
2848 ret = (acc->h4 * scan_y) / (acc->h2mw2);
2852 return -cbrt (-ret);
2856 * computes the X value of the intersection of the
2857 * given scan line with the right side of the lower hook
2861 hookX (scan_y, def, bound, acc, left)
2863 struct arc_def *def;
2864 struct arc_bound *bound;
2865 struct accelerators *acc;
2868 double ellipse_y, x;
2871 if (def->w != def->h) {
2872 ellipse_y = hookEllipseY (scan_y, bound, acc, left);
2873 if (boundedLe (ellipse_y, bound->ellipse)) {
2875 * compute the value of the second
2878 maxMin = ellipse_y*ellipse_y*ellipse_y * acc->h2mw2 -
2879 acc->h2 * scan_y * (3 * ellipse_y*ellipse_y - 2*acc->h2);
2880 if ((left && maxMin > 0) || (!left && maxMin < 0)) {
2882 return def->w + left ? -def->l : def->l;
2883 x = (acc->h2 * scan_y - ellipse_y * acc->h2mw2) *
2884 sqrt (acc->h2 - ellipse_y * ellipse_y) /
2885 (def->h * def->w * ellipse_y);
2891 if (acc->left.valid && boundedLe (scan_y, bound->left)) {
2892 x = intersectLine (scan_y, acc->left);
2894 if (acc->right.valid)
2895 x = intersectLine (scan_y, acc->right);
2897 x = def->w - def->l;
2900 if (acc->right.valid && boundedLe (scan_y, bound->right)) {
2901 x = intersectLine (scan_y, acc->right);
2903 if (acc->left.valid)
2904 x = intersectLine (scan_y, acc->left);
2906 x = def->w - def->l;
2913 * generate the set of spans with
2914 * the given y coordinate
2918 arcSpan (y, lx, lw, rx, rw, def, bounds, acc, mask)
2924 struct arc_def *def;
2925 struct arc_bound *bounds;
2926 struct accelerators *acc;
2929 int linx, loutx, rinx, routx;
2932 if (boundedLe (y, bounds->inneri)) {
2937 * intersection with left face
2939 x = hookX (y + acc->fromIntY, def, bounds, acc, 1);
2940 if (acc->right.valid &&
2941 boundedLe (y + acc->fromIntY, bounds->right))
2943 altx = intersectLine (y + acc->fromIntY, acc->right);
2947 linx = -ICEIL(acc->fromIntX - x);
2948 rinx = ICEIL(acc->fromIntX + x);
2950 if (boundedLe (y, bounds->outeri)) {
2955 * intersection with right face
2957 x = hookX (y + acc->fromIntY, def, bounds, acc, 0);
2958 if (acc->left.valid &&
2959 boundedLe (y + acc->fromIntY, bounds->left))
2962 x = intersectLine (y + acc->fromIntY, acc->left);
2966 loutx = -ICEIL(acc->fromIntX - x);
2967 routx = ICEIL(acc->fromIntX + x);
2971 newFinalSpan (acc->yorgu - y,
2972 acc->xorg + rinx, acc->xorg + routx);
2974 newFinalSpan (acc->yorgl + y,
2975 acc->xorg + rinx, acc->xorg + routx);
2979 newFinalSpan (acc->yorgu - y,
2980 acc->xorg - loutx, acc->xorg - linx);
2982 newFinalSpan (acc->yorgl + y,
2983 acc->xorg - loutx, acc->xorg - linx);
2988 arcSpan0 (lx, lw, rx, rw, def, bounds, acc, mask)
2993 struct arc_def *def;
2994 struct arc_bound *bounds;
2995 struct accelerators *acc;
3000 if (boundedLe (0, bounds->inneri) &&
3001 acc->left.valid && boundedLe (0, bounds->left) &&
3004 x = def->w - def->l;
3005 if (acc->left.b < x)
3007 lw = ICEIL(acc->fromIntX - x) - lx;
3009 rx = ICEIL(acc->fromIntX + x);
3012 arcSpan (0, lx, lw, rx, rw, def, bounds, acc, mask);
3016 tailSpan (y, lw, rw, def, bounds, acc, mask)
3020 struct arc_def *def;
3021 struct arc_bound *bounds;
3022 struct accelerators *acc;
3025 double yy, xalt, x, lx, rx;
3028 if (boundedLe(y, bounds->outeri))
3029 arcSpan (y, 0, lw, -rw, rw, def, bounds, acc, mask);
3030 else if (def->w != def->h) {
3031 yy = y + acc->fromIntY;
3032 x = tailX(yy, def, bounds, acc);
3033 if (yy == 0.0 && x == -rw - acc->fromIntX)
3035 if (acc->right.valid && boundedLe (yy, bounds->right)) {
3038 xalt = intersectLine (yy, acc->right);
3039 if (xalt >= -rw - acc->fromIntX && xalt <= rx)
3041 n = ICEIL(acc->fromIntX + lx);
3044 newFinalSpan (acc->yorgu - y,
3045 acc->xorg + n, acc->xorg + lw);
3047 newFinalSpan (acc->yorgl + y,
3048 acc->xorg + n, acc->xorg + lw);
3050 n = ICEIL(acc->fromIntX + rx);
3053 newFinalSpan (acc->yorgu - y,
3054 acc->xorg - rw, acc->xorg + n);
3056 newFinalSpan (acc->yorgl + y,
3057 acc->xorg - rw, acc->xorg + n);
3061 ICEIL(acc->fromIntX - x), 0,
3062 ICEIL(acc->fromIntX + x), 0,
3063 def, bounds, acc, mask);
3068 * create whole arcs out of pieces. This code is
3072 static struct finalSpan **finalSpans = NULL;
3073 static int finalMiny = 0, finalMaxy = -1;
3074 static int finalSize = 0;
3076 static int nspans = 0; /* total spans, not just y coords */
3079 struct finalSpan *next;
3080 int min, max; /* x values */
3083 static struct finalSpan *freeFinalSpans, *tmpFinalSpan;
3085 # define allocFinalSpan() (freeFinalSpans ?\
3086 ((tmpFinalSpan = freeFinalSpans), \
3087 (freeFinalSpans = freeFinalSpans->next), \
3088 (tmpFinalSpan->next = 0), \
3092 # define SPAN_CHUNK_SIZE 128
3094 struct finalSpanChunk {
3095 struct finalSpan data[SPAN_CHUNK_SIZE];
3096 struct finalSpanChunk *next;
3099 static struct finalSpanChunk *chunks;
3104 register struct finalSpanChunk *newChunk;
3105 register struct finalSpan *span;
3108 newChunk = (struct finalSpanChunk *) xalloc (sizeof (struct finalSpanChunk));
3110 return (struct finalSpan *) NULL;
3111 newChunk->next = chunks;
3113 freeFinalSpans = span = newChunk->data + 1;
3114 for (i = 1; i < SPAN_CHUNK_SIZE-1; i++) {
3115 span->next = span+1;
3119 span = newChunk->data;
3125 disposeFinalSpans ()
3127 struct finalSpanChunk *chunk, *next;
3129 for (chunk = chunks; chunk; chunk = next) {
3140 fillSpans (pDrawable, pGC)
3141 DrawablePtr pDrawable;
3144 register struct finalSpan *span;
3145 register DDXPointPtr xSpan;
3146 register int *xWidth;
3148 register struct finalSpan **f;
3155 xSpan = xSpans = (DDXPointPtr) ALLOCATE_LOCAL (nspans * sizeof (DDXPointRec));
3156 xWidth = xWidths = (int *) ALLOCATE_LOCAL (nspans * sizeof (int));
3157 if (xSpans && xWidths)
3161 for (spany = finalMiny; spany <= finalMaxy; spany++, f++) {
3162 for (span = *f; span; span=span->next) {
3163 if (span->max <= span->min)
3165 xSpan->x = span->min;
3168 *xWidth++ = span->max - span->min;
3172 (*pGC->ops->FillSpans) (pDrawable, pGC, i, xSpans, xWidths, TRUE);
3174 disposeFinalSpans ();
3176 DEALLOCATE_LOCAL (xSpans);
3178 DEALLOCATE_LOCAL (xWidths);
3185 # define SPAN_REALLOC 100
3187 # define findSpan(y) ((finalMiny <= (y) && (y) <= finalMaxy) ? \
3188 &finalSpans[(y) - finalMiny] : \
3191 static struct finalSpan **
3195 struct finalSpan **newSpans;
3196 int newSize, newMiny, newMaxy;
3200 if (y < finalMiny || y > finalMaxy) {
3206 change = finalMiny - y;
3208 change = y - finalMaxy;
3209 if (change >= SPAN_REALLOC)
3210 change += SPAN_REALLOC;
3212 change = SPAN_REALLOC;
3213 newSize = finalSize + change;
3214 newSpans = (struct finalSpan **) xalloc
3215 (newSize * sizeof (struct finalSpan *));
3217 return (struct finalSpan **)NULL;
3218 newMiny = finalMiny;
3219 newMaxy = finalMaxy;
3221 newMiny = finalMiny - change;
3223 newMaxy = finalMaxy + change;
3225 memmove(((char *) newSpans) + (finalMiny-newMiny) * sizeof (struct finalSpan *),
3226 (char *) finalSpans,
3227 finalSize * sizeof (struct finalSpan *));
3230 if ((i = finalMiny - newMiny) > 0)
3231 bzero ((char *)newSpans, i * sizeof (struct finalSpan *));
3232 if ((i = newMaxy - finalMaxy) > 0)
3233 bzero ((char *)(newSpans + newSize - i),
3234 i * sizeof (struct finalSpan *));
3235 finalSpans = newSpans;
3236 finalMaxy = newMaxy;
3237 finalMiny = newMiny;
3238 finalSize = newSize;
3240 return &finalSpans[y - finalMiny];
3244 newFinalSpan (y, xmin, xmax)
3246 register int xmin, xmax;
3248 register struct finalSpan *x;
3249 register struct finalSpan **f;
3250 struct finalSpan *oldx;
3251 struct finalSpan *prev;
3259 for (x = *f; x; x=x->next) {
3264 if (x->min <= xmax && xmin <= x->max) {
3266 oldx->min = min (x->min, xmin);
3267 oldx->max = max (x->max, xmax);
3269 prev->next = x->next;
3274 x->min = min (x->min, xmin);
3275 x->max = max (x->max, xmax);
3288 x = allocFinalSpan ();
3301 mirrorSppPoint (quadrant, sppPoint)
3303 SppPointPtr sppPoint;
3309 sppPoint->x = -sppPoint->x;
3312 sppPoint->x = -sppPoint->x;
3313 sppPoint->y = -sppPoint->y;
3316 sppPoint->y = -sppPoint->y;
3320 * and translate to X coordinate system
3322 sppPoint->y = -sppPoint->y;
3326 * split an arc into pieces which are scan-converted
3327 * in the first-quadrant and mirrored into position.
3328 * This is necessary as the scan-conversion code can
3329 * only deal with arcs completely contained in the
3334 drawArc (tarc, l, a0, a1, right, left)
3337 miArcFacePtr right, left; /* save end line points */
3340 struct accelerators acc;
3341 int startq, endq, curq;
3342 int rightq, leftq, righta, lefta;
3343 miArcFacePtr passRight, passLeft;
3348 } band[5], sweep[20];
3349 int bandno, sweepno;
3351 int flipRight = 0, flipLeft = 0;
3353 miArcSpanData *spdata;
3356 spdata = miComputeWideEllipse(l, tarc, &mustFree);
3362 startq = a0 / (90 * 64);
3366 endq = (a1-1) / (90 * 64);
3378 q1 = min (a1, 90 * 64);
3381 if (curq == startq && a0 == q0 && rightq < 0) {
3385 if (curq == endq && a1 == q1) {
3394 q0 = 180 * 64 - min (a1, 180 * 64);
3398 q1 = 180 * 64 - max (a0, 90 * 64);
3399 if (curq == startq && 180 * 64 - a0 == q1) {
3403 if (curq == endq && 180 * 64 - a1 == q0) {
3412 q0 = max (a0, 180 * 64) - 180 * 64;
3416 q1 = min (a1, 270 * 64) - 180 * 64;
3417 if (curq == startq && a0 - 180*64 == q0) {
3421 if (curq == endq && a1 - 180 * 64 == q1) {
3430 q0 = 360 * 64 - min (a1, 360 * 64);
3431 q1 = 360 * 64 - max (a0, 270 * 64);
3432 if (curq == startq && 360 * 64 - a0 == q1) {
3436 if (curq == endq && 360 * 64 - a1 == q0) {
3442 band[bandno].a0 = q0;
3443 band[bandno].a1 = q1;
3444 band[bandno].mask = 1 << curq;
3461 * find left-most point
3463 for (i = 0; i < bandno; i++)
3464 if (band[i].a0 <= q0) {
3467 mask = band[i].mask;
3472 * locate next point of change
3474 for (i = 0; i < bandno; i++)
3475 if (!(mask & band[i].mask)) {
3476 if (band[i].a0 == q0) {
3477 if (band[i].a1 < q1)
3479 mask |= band[i].mask;
3480 } else if (band[i].a0 < q1)
3484 * create a new sweep
3486 sweep[sweepno].a0 = q0;
3487 sweep[sweepno].a1 = q1;
3488 sweep[sweepno].mask = mask;
3491 * subtract the sweep from the affected bands
3493 for (i = 0; i < bandno; i++)
3494 if (band[i].a0 == q0) {
3497 * check if this band is empty
3499 if (band[i].a0 == band[i].a1)
3500 band[i].a1 = band[i].a0 = 90 * 64 + 1;
3503 computeAcc (tarc, l, &def, &acc);
3504 for (j = 0; j < sweepno; j++) {
3505 mask = sweep[j].mask;
3506 passRight = passLeft = 0;
3507 if (mask & (1 << rightq)) {
3508 if (sweep[j].a0 == righta)
3510 else if (sweep[j].a1 == righta) {
3515 if (mask & (1 << leftq)) {
3516 if (sweep[j].a1 == lefta)
3522 else if (sweep[j].a0 == lefta) {
3529 drawQuadrant (&def, &acc, sweep[j].a0, sweep[j].a1, mask,
3530 passRight, passLeft, spdata);
3533 * when copyEnd is set, both ends of the arc were computed
3534 * at the same time; drawQuadrant only takes one end though,
3535 * so the left end will be the only one holding the data. Copy
3541 * mirror the coordinates generated for the
3545 mirrorSppPoint (rightq, &right->clock);
3546 mirrorSppPoint (rightq, &right->center);
3547 mirrorSppPoint (rightq, &right->counterClock);
3551 temp = right->clock;
3552 right->clock = right->counterClock;
3553 right->counterClock = temp;
3557 mirrorSppPoint (leftq, &left->counterClock);
3558 mirrorSppPoint (leftq, &left->center);
3559 mirrorSppPoint (leftq, &left->clock);
3564 left->clock = left->counterClock;
3565 left->counterClock = temp;
3573 drawQuadrant (def, acc, a0, a1, mask, right, left, spdata)
3574 struct arc_def *def;
3575 struct accelerators *acc;
3578 miArcFacePtr right, left;
3579 miArcSpanData *spdata;
3581 struct arc_bound bound;
3587 def->a0 = ((double) a0) / 64.0;
3588 def->a1 = ((double) a1) / 64.0;
3589 computeBound (def, &bound, acc, right, left);
3590 yy = bound.inner.min;
3591 if (bound.outer.min < yy)
3592 yy = bound.outer.min;
3593 miny = ICEIL(yy - acc->fromIntY);
3594 yy = bound.inner.max;
3595 if (bound.outer.max > yy)
3596 yy = bound.outer.max;
3597 maxy = floor(yy - acc->fromIntY);
3599 span = spdata->spans;
3602 if (a1 == 90 * 64 && (mask & 1))
3603 newFinalSpan (acc->yorgu - y - 1, acc->xorg, acc->xorg + 1);
3606 for (n = spdata->count1; --n >= 0; )
3612 span->lx, -span->lx, 0, span->lx + span->lw,
3613 def, &bound, acc, mask);
3614 if (span->rw + span->rx)
3615 tailSpan (y, -span->rw, -span->rx, def, &bound, acc, mask);
3625 arcSpan (y, 0, 0, 0, 1, def, &bound, acc, mask & 0xc);
3627 for (n = spdata->count2; --n >= 0; )
3632 arcSpan (y, span->lx, span->lw, span->rx, span->rw,
3633 def, &bound, acc, mask);
3637 if (spdata->bot && miny <= y && y <= maxy)
3642 if (span->rw <= 0) {
3643 arcSpan0 (span->lx, -span->lx, 0, span->lx + span->lw,
3644 def, &bound, acc, n);
3645 if (span->rw + span->rx)
3646 tailSpan (y, -span->rw, -span->rx, def, &bound, acc, n);
3649 arcSpan0 (span->lx, span->lw, span->rx, span->rw,
3650 def, &bound, acc, n);
3654 yy = y + acc->fromIntY;
3655 if (def->w == def->h) {
3656 xalt = def->w - def->l;
3657 x = -sqrt(xalt * xalt - yy * yy);
3659 x = tailX(yy, def, &bound, acc);
3660 if (acc->left.valid && boundedLe (yy, bound.left)) {
3661 xalt = intersectLine (yy, acc->left);
3665 if (acc->right.valid && boundedLe (yy, bound.right)) {
3666 xalt = intersectLine (yy, acc->right);
3672 ICEIL(acc->fromIntX - x), 0,
3673 ICEIL(acc->fromIntX + x), 0,
3674 def, &bound, acc, mask);