1 /* $XFree86: xc/programs/Xserver/mi/miarc.c,v 3.7 1999/12/27 00:39:56 robin Exp $ */
2 /***********************************************************
4 Copyright 1987, 1998 The Open Group
8 The above copyright notice and this permission notice shall be included in
9 all copies or substantial portions of the Software.
11 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
12 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
13 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
14 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
15 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
16 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18 Except as contained in this notice, the name of The Open Group shall not be
19 used in advertising or otherwise to promote the sale, use or other dealings
20 in this Software without prior written authorization from The Open Group.
23 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
27 Permission to use, copy, modify, and distribute this software and its
28 documentation for any purpose and without fee is hereby granted,
29 provided that the above copyright notice appear in all copies and that
30 both that copyright notice and this permission notice appear in
31 supporting documentation, and that the name of Digital not be
32 used in advertising or publicity pertaining to distribution of the
33 software without specific, written prior permission.
35 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
36 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
37 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
38 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
39 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
40 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
43 ******************************************************************/
44 /* $TOG: miarc.c /main/91 1998/02/09 14:45:57 kaleb $ */
45 /* Author: Keith Packard and Bob Scheifler */
46 /* Warning: this code is toxic, do not dally very long here. */
48 #define _XOPEN_SOURCE_EXTENDED /* to get prototype for cbrt on some systems */
49 #define _XOPEN_SOURCE /* to get prototype for hypot on some systems */
51 #include <string.h> /* memmove */
57 #include "gdkprivate-fb.h"
59 static double miDsin(double a), miDcos(double a), miDasin(double a), miDatan2(double x, double y);
66 * some interesting sematic interpretation of the protocol:
68 * Self intersecting arcs (i.e. those spanning 360 degrees)
69 * never join with other arcs, and are drawn without caps
70 * (unless on/off dashed, in which case each dash segment
71 * is capped, except when the last segment meets the
72 * first segment, when no caps are drawn)
74 * double dash arcs are drawn in two parts, first the
75 * odd dashes (drawn in background) then the even dashes
76 * (drawn in foreground). This means that overlapping
77 * sections of foreground/background are drawn twice,
78 * first in background then in foreground. The double-draw
79 * occurs even when the function uses the destination values
80 * (e.g. xor mode). This is the same way the wide-line
81 * code works and should be "fixed".
88 #if defined (__GNUC__) && defined (__STDC__) && !defined (__STRICT_ANSI__)
100 #define boundedLe(value, bounds)\
101 ((bounds).min <= (value) && (value) <= (bounds).max)
108 #define intersectLine(y,line) (line.m * (y) + line.b)
111 * these are all y value bounds
115 struct bound ellipse;
120 struct ibound inneri;
121 struct ibound outeri;
124 struct accelerators {
135 struct line left, right;
146 # define todeg(xAngle) (((double) (xAngle)) / 64.0)
151 typedef struct _miArcJoin {
152 int arcIndex0, arcIndex1;
155 } miArcJoinRec, *miArcJoinPtr;
157 typedef struct _miArcCap {
160 } miArcCapRec, *miArcCapPtr;
162 typedef struct _miArcFace {
165 SppPointRec counterClock;
166 } miArcFaceRec, *miArcFacePtr;
168 typedef struct _miArcData {
170 int render; /* non-zero means render after drawing */
171 int join; /* related join */
172 int cap; /* related cap */
173 int selfJoin; /* final dash meets first dash */
174 miArcFaceRec bounds[2];
175 double x0, y0, x1, y1;
176 } miArcDataRec, *miArcDataPtr;
179 * This is an entire sequence of arcs, computed and categorized according
180 * to operation. miDashArcs generates either one or two of these.
183 typedef struct _miPolyArc {
190 } miPolyArcRec, *miPolyArcPtr;
193 short lx, lw, rx, rw;
198 int count1, count2, k;
203 unsigned long lrustamp;
205 unsigned short width, height;
206 miArcSpanData *spdata;
209 # define DASH_MAP_SIZE 91
212 double map[DASH_MAP_SIZE];
215 static void fillSpans(GdkDrawable *pDrawable, GdkGC *pGC);
216 static void newFinalSpan(int y, int xmin, int xmax);
217 static void drawArc (miArc *tarc, int l, int a0, int a1, miArcFacePtr right, miArcFacePtr left);
218 static void drawQuadrant(struct arc_def *def, struct accelerators *acc,
219 int a0, int a1, int mask, miArcFacePtr right, miArcFacePtr left,
220 miArcSpanData *spdata);
221 static void drawZeroArc(GdkDrawable *pDraw, GdkGC *pGC, miArc *tarc, int lw, miArcFacePtr right, miArcFacePtr left);
222 static void miArcJoin(GdkDrawable *pDraw, GdkGC *pGC, miArcFacePtr pRight, miArcFacePtr pLeft, int xOrgRight, int yOrgRight,
223 double xFtransRight, double yFtransRight,
224 int xOrgLeft, int yOrgLeft,
225 double xFtransLeft, double yFtransLeft);
226 static void miArcCap(GdkDrawable *pDraw, GdkGC *pGC, miArcFacePtr pFace, int end, int xOrg, int yOrg,
227 double xFtrans, double yFtrans);
228 static void miRoundCap(GdkDrawable *pDraw, GdkGC *pGC, SppPointRec pCenter, SppPointRec pEnd, SppPointRec pCorner,
229 SppPointRec pOtherCorner, int fLineEnd, int xOrg, int yOrg,
230 double xFtrans, double yFtrans);
231 static void miFreeArcs(miPolyArcPtr arcs, GdkGC *pGC);
232 static int computeAngleFromPath(int startAngle, int endAngle, dashMap *map, int *lenp, int backwards);
233 static miPolyArcPtr miComputeArcs (miArc *parcs, int narcs, GdkGC *gc);
234 static int miGetArcPts(SppArcPtr parc, int cpt, SppPointPtr *ppPts);
236 # define CUBED_ROOT_2 1.2599210498948732038115849718451499938964
237 # define CUBED_ROOT_4 1.5874010519681993173435330390930175781250
240 * draw one segment of the arc using the arc spans generation routines
244 miArcSegment(GdkDrawable *pDraw, GdkGC *pGC, miArc tarc, miArcFacePtr right, miArcFacePtr left)
246 int l = GDK_GC_FBDATA(pGC)->values.line_width;
247 int a0, a1, startAngle, endAngle;
253 if (tarc.width == 0 || tarc.height == 0) {
254 drawZeroArc (pDraw, pGC, &tarc, l, left, right);
262 else if (a1 < -FULLCIRCLE)
265 startAngle = a0 + a1;
275 * bounds check the two angles
278 startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
279 if (startAngle >= FULLCIRCLE)
280 startAngle = startAngle % FULLCIRCLE;
282 endAngle = FULLCIRCLE - (-endAngle) % FULLCIRCLE;
283 if (endAngle > FULLCIRCLE)
284 endAngle = (endAngle-1) % FULLCIRCLE + 1;
285 if ((startAngle == endAngle) && a1) {
287 endAngle = FULLCIRCLE;
290 drawArc (&tarc, l, startAngle, endAngle, right, left);
295 Three equations combine to describe the boundaries of the arc
297 x^2/w^2 + y^2/h^2 = 1 ellipse itself
298 (X-x)^2 + (Y-y)^2 = r^2 circle at (x, y) on the ellipse
299 (Y-y) = (X-x)*w^2*y/(h^2*x) normal at (x, y) on the ellipse
301 These lead to a quartic relating Y and y
303 y^4 - (2Y)y^3 + (Y^2 + (h^4 - w^2*r^2)/(w^2 - h^2))y^2
304 - (2Y*h^4/(w^2 - h^2))y + (Y^2*h^4)/(w^2 - h^2) = 0
306 The reducible cubic obtained from this quartic is
308 z^3 - (3N)z^2 - 2V = 0
312 N = (Y^2 + (h^4 - w^2*r^2/(w^2 - h^2)))/6
313 V = w^2*r^2*Y^2*h^4/(4 *(w^2 - h^2)^2)
325 The discriminant of this cubic is
329 When D > 0, a real root is obtained as
331 z = N + cbrt(-q+sqrt(D)) + cbrt(-q-sqrt(D))
333 When D < 0, a real root is obtained as
335 z = N - 2m*cos(acos(-q/m^3)/3)
339 m = sqrt(|p|) * sign(q)
341 Given a real root Z of the cubic, the roots of the quartic are the roots
342 of the two quadratics
344 y^2 + ((b+A)/2)y + (Z + (bZ - d)/A) = 0
348 A = +/- sqrt(8Z + b^2 - 4c)
349 b, c, d are the cubic, quadratic, and linear coefficients of the quartic
351 Some experimentation is then required to determine which solutions
352 correspond to the inner and outer boundaries.
358 static arcCacheRec arcCache[CACHESIZE];
359 static unsigned long lrustamp;
360 static arcCacheRec *lastCacheHit = &arcCache[0];
363 static RESTYPE cacheType;
366 * External so it can be called when low on memory.
367 * Call with a zero ID in that case.
371 miFreeArcCache (data, id)
381 for (k = CACHESIZE, cent = &arcCache[0]; --k >= 0; cent++)
387 g_free(cent->spdata);
397 miComputeCircleSpans(int lw, miArc *parc, miArcSpanData *spdata)
399 register miArcSpan *span;
401 register int x, y, e;
402 int xk, yk, xm, ym, dx, dy;
403 register int slw, inslw;
405 int inxk, inyk, inxm, inym;
408 slw = parc->width - doinner;
409 y = parc->height >> 1;
410 dy = parc->height & 1;
412 MIWIDEARCSETUP(x, y, dy, slw, e, xk, xm, yk, ym);
413 inslw = parc->width + doinner;
416 spdata->hole = spdata->top;
417 MIWIDEARCSETUP(inx, iny, dy, inslw, ine, inxk, inxm, inyk, inym);
421 spdata->hole = FALSE;
424 spdata->count1 = -doinner - spdata->top;
425 spdata->count2 = y + doinner;
426 span = spdata->spans;
435 span->rw = span->lx + slw;
439 MIFILLINARCSTEP(inslw);
441 span->rx = dy - inx + inslw;
442 span->rw = inx - x + slw - inslw;
452 if (lw > (int)parc->height)
453 span[-1].rx = span[-1].rw = -((lw - (int)parc->height) >> 1);
462 miComputeEllipseSpans(int lw, miArc *parc, miArcSpanData *spdata)
464 register miArcSpan *span;
465 double w, h, r, xorg;
466 double Hs, Hf, WH, K, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
467 double A, T, b, d, x, y, t, inx, outx, hepp, hepm;
470 w = (double)parc->width / 2.0;
471 h = (double)parc->height / 2.0;
477 Vk = (Nk * Hs) / (WH + WH);
479 Nk = (Hf - Nk * Nk) / WH;
483 K = h + ((lw - 1) >> 1);
484 span = spdata->spans;
497 spdata->hole = (spdata->top &&
498 (int)parc->height * lw <= (int)(parc->width * parc->width) &&
499 lw < (int)parc->height);
500 for (; K > 0.0; K -= 1.0)
502 N = (K * K + Nk) / 6.0;
510 if ( (b < 0.0) == (t < 0.0) )
515 Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
516 if ( (Z < 0.0) == (Vr < 0.0) )
524 Z = N + cbrt(t + d) + cbrt(t - d);
527 A = sqrt((Z + Z) - Nk);
528 T = (Fk - Z) * K / A;
532 d = b * b - 4 * (Z + T);
537 if ((y >= 0.0) && (y < hepp))
543 x = w * sqrt(1 - (t * t));
545 if (rs - (t * t) >= 0)
546 t = sqrt(rs - (t * t));
556 d = b * b - 4 * (Z - T);
557 /* Because of the large magnitudes involved, we lose enough precision
558 * that sometimes we end up with a negative value near the axis, when
559 * it should be positive. This is a workaround.
561 if (d < 0 && !solution)
571 x = w * sqrt(1 - (t * t));
573 if (rs - (t * t) >= 0)
574 inx = x - sqrt(rs - (t * t));
584 x = w * sqrt(1 - (t * t));
586 if (rs - (t * t) >= 0)
587 t = sqrt(rs - (t * t));
596 span->lx = ICEIL(xorg - outx);
600 span->lw = ICEIL(xorg + outx) - span->lx;
601 span->rx = ICEIL(xorg + inx);
602 span->rw = -ICEIL(xorg - inx);
607 span->lw = ICEIL(xorg - inx) - span->lx;
608 span->rx = ICEIL(xorg + inx);
609 span->rw = ICEIL(xorg + outx) - span->rx;
616 if (r >= h && r <= w)
618 else if (Nk < 0.0 && -Nk < Hs)
620 inx = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
626 span->lx = ICEIL(xorg - outx);
629 span->lw = ICEIL(xorg + outx) - span->lx;
630 span->rx = ICEIL(xorg + inx);
631 span->rw = -ICEIL(xorg - inx);
635 span->lw = ICEIL(xorg - inx) - span->lx;
636 span->rx = ICEIL(xorg + inx);
637 span->rw = ICEIL(xorg + outx) - span->rx;
642 span = &spdata->spans[spdata->count1];
643 span->lw = -span->lx;
652 tailX(double K, struct arc_def *def, struct arc_bound *bounds, struct accelerators *acc)
655 double Hs, Hf, WH, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
656 double A, T, b, d, x, y, t, hepp, hepm;
668 Vk = (Nk * Hs) / (WH + WH);
670 Nk = (Hf - Nk * Nk) / WH;
672 if (Nk < 0.0 && -Nk < Hs) {
673 xs[0] = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
675 if (acc->left.valid && boundedLe(K, bounds->left) &&
676 !boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
678 if (acc->right.valid && boundedLe(K, bounds->right) &&
679 !boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
688 N = (K * K + Nk) / 6.0;
698 if ( (b < 0.0) == (t < 0.0) )
703 Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
704 if ( (Z < 0.0) == (Vr < 0.0) )
712 Z = N + cbrt(t + d) + cbrt(t - d);
715 A = sqrt((Z + Z) - Nk);
716 T = (Fk - Z) * K / A;
719 d = b * b - 4 * (Z + T);
720 if (d >= 0 && flip == 2)
724 if ((y >= 0.0) && (y < hepp))
730 x = w * sqrt(1 - (t * t));
732 if (rs - (t * t) >= 0)
733 t = sqrt(rs - (t * t));
740 d = b * b - 4 * (Z - T);
741 /* Because of the large magnitudes involved, we lose enough precision
742 * that sometimes we end up with a negative value near the axis, when
743 * it should be positive. This is a workaround.
745 if (d < 0 && !solution)
755 x = w * sqrt(1 - (t * t));
757 if (rs - (t * t) >= 0)
758 *xp++ = x - sqrt(rs - (t * t));
763 if (y >= 0.0 && flip == 1)
768 x = w * sqrt(1 - (t * t));
770 if (rs - (t * t) >= 0)
771 t = sqrt(rs - (t * t));
778 if (acc->left.valid && boundedLe(K, bounds->left) &&
779 !boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
781 if (acc->right.valid && boundedLe(K, bounds->right) &&
782 !boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
788 static miArcSpanData *
789 miComputeWideEllipse(int lw, miArc *parc, gboolean *mustFree)
791 register miArcSpanData *spdata;
792 register arcCacheRec *cent, *lruent;
798 if (parc->height <= 1500)
802 if (cent->lw == lw &&
803 cent->width == parc->width && cent->height == parc->height)
805 cent->lrustamp = ++lrustamp;
808 lruent = &arcCache[0];
809 for (k = CACHESIZE, cent = lruent; --k >= 0; cent++)
811 if (cent->lw == lw &&
812 cent->width == parc->width && cent->height == parc->height)
814 cent->lrustamp = ++lrustamp;
818 if (cent->lrustamp < lruent->lrustamp)
824 cacheType = CreateNewResourceType(miFreeArcCache);
825 (void) AddResource(FakeClientID(0), cacheType, NULL);
830 lruent->spdata = NULL;
833 k = (parc->height >> 1) + ((lw - 1) >> 1);
834 spdata = lruent->spdata;
835 if (!spdata || spdata->k != k)
839 spdata = (miArcSpanData *)g_malloc(sizeof(miArcSpanData) +
840 sizeof(miArcSpan) * (k + 2));
841 lruent->spdata = spdata;
844 lruent->lrustamp = 0;
848 spdata->spans = (miArcSpan *)(spdata + 1);
851 spdata->top = !(lw & 1) && !(parc->width & 1);
852 spdata->bot = !(parc->height & 1);
853 lruent->lrustamp = ++lrustamp;
855 lruent->width = parc->width;
856 lruent->height = parc->height;
857 if (lruent != &fakeent)
858 lastCacheHit = lruent;
859 if (parc->width == parc->height)
860 miComputeCircleSpans(lw, parc, spdata);
862 miComputeEllipseSpans(lw, parc, spdata);
867 miFillWideEllipse(GdkDrawable *pDraw, GdkGC *pGC, miArc *parc)
869 GdkRectangle* points;
870 register GdkRectangle* pts;
871 miArcSpanData *spdata;
873 register miArcSpan *span;
874 register int xorg, yorgu, yorgl;
877 yorgu = parc->height + GDK_GC_FBDATA(pGC)->values.line_width;
878 points = ALLOCATE_LOCAL(sizeof(GdkRectangle) * yorgu * 2);
879 spdata = miComputeWideEllipse(GDK_GC_FBDATA(pGC)->values.line_width, parc, &mustFree);
882 DEALLOCATE_LOCAL(points);
886 span = spdata->spans;
887 xorg = parc->x + (parc->width >> 1);
888 yorgu = parc->y + (parc->height >> 1);
889 yorgl = yorgu + (parc->height & 1);
896 pts->width = pts->height = 1;
900 for (n = spdata->count1; --n >= 0; )
902 pts[0].x = xorg + span->lx;
905 pts[0].width = span->lw;
917 pts[0].width = pts[0].height = 1;
920 for (n = spdata->count2; --n >= 0; )
922 pts[0].x = xorg + span->lx;
924 pts[0].width = span->lw;
927 pts[1].x = xorg + span->rx;
929 pts[1].width = span->rw;
935 pts[2].width = pts[0].width;
939 pts[3].width = pts[1].width;
951 pts[0].x = xorg + span->lx;
953 pts[0].width = span->lw;
959 pts[0].x = xorg + span->lx;
961 pts[0].width = span->lw;
963 pts[1].x = xorg + span->rx;
965 pts[1].width = span->rw;
973 gdk_fb_fill_spans(pDraw, pGC, points, pts - points);
975 DEALLOCATE_LOCAL(points);
979 * miPolyArc strategy:
981 * If arc is zero width and solid, we don't have to worry about the rasterop
982 * or join styles. For wide solid circles, we use a fast integer algorithm.
983 * For wide solid ellipses, we use special case floating point code.
984 * Otherwise, we set up pDrawTo and pGCTo according to the rasterop, then
985 * draw using pGCTo and pDrawTo. If the raster-op was "tricky," that is,
986 * if it involves the destination, then we use PushPixels to move the bits
987 * from the scratch drawable to pDraw. (See the wide line code for a
988 * fuller explanation of this.)
992 miPolyArc(GdkDrawable *pDraw, GdkGC *pGC, int narcs, miArc *parcs)
996 int xMin, xMax, yMin, yMax;
997 int pixmapWidth, pixmapHeight;
1001 GdkDrawable* pDrawTo;
1004 miPolyArcPtr polyArcs;
1005 int cap[2], join[2];
1010 width = GDK_GC_FBDATA(pGC)->values.line_width;
1011 if(width == 0 && GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_SOLID)
1013 for(i = narcs, parc = parcs; --i >= 0; parc++)
1014 miArcSegment( pDraw, pGC, *parc,
1015 (miArcFacePtr) 0, (miArcFacePtr) 0 );
1016 fillSpans (pDraw, pGC);
1020 if ((GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_SOLID) && narcs)
1022 while (parcs->width && parcs->height &&
1023 (parcs->angle2 >= FULLCIRCLE ||
1024 parcs->angle2 <= -FULLCIRCLE))
1026 miFillWideEllipse(pDraw, pGC, parcs);
1033 /* Set up pDrawTo and pGCTo based on the rasterop */
1034 switch(GDK_GC_FBDATA(pGC)->alu)
1036 case GDK_CLEAR: /* 0 */
1037 case GDK_COPY: /* src */
1038 case GDK_COPY_INVERT: /* NOT src */
1039 case GDK_SET: /* 1 */
1047 /* find bounding box around arcs */
1048 xMin = yMin = SHRT_MAX;
1049 xMax = yMax = SHRT_MIN;
1051 for(i = narcs, parc = parcs; --i >= 0; parc++)
1053 xMin = MIN (xMin, parc->x);
1054 yMin = MIN (yMin, parc->y);
1055 xMax = MAX (xMax, (parc->x + (int) parc->width));
1056 yMax = MAX (yMax, (parc->y + (int) parc->height));
1059 /* expand box to deal with line widths */
1060 halfWidth = (width + 1)/2;
1066 /* compute pixmap size; limit it to size of drawable */
1067 xOrg = MAX(xMin, 0);
1068 yOrg = MAX(yMin, 0);
1069 pixmapWidth = MIN(xMax, GDK_DRAWABLE_FBDATA(pDraw)->width) - xOrg;
1070 pixmapHeight = MIN(yMax, GDK_DRAWABLE_FBDATA(pDraw)->height) - yOrg;
1072 /* if nothing left, return */
1073 if ( (pixmapWidth <= 0) || (pixmapHeight <= 0) ) return;
1075 for(i = narcs, parc = parcs; --i >= 0; parc++)
1081 /* set up scratch GC */
1082 /* allocate a 1 bit deep pixmap of the appropriate size, and
1084 pDrawTo = gdk_pixmap_new(NULL, pixmapWidth, pixmapHeight, 1);
1088 pGCTo = gdk_gc_new(pDrawTo);
1091 gdk_pixmap_unref(pDrawTo);
1094 gdk_gc_set_function(pGCTo, GDK_COPY);
1095 memset(&gcv.background, 0, sizeof(GdkColor));
1096 gcv.foreground.pixel = 1;
1097 gcv.foreground.red = gcv.foreground.green = gcv.foreground.blue = 1;
1098 gdk_gc_set_foreground(pGCTo, &gcv.foreground);
1099 gdk_gc_set_background(pGCTo, &gcv.background);
1100 gdk_gc_set_line_attributes(pGCTo,
1101 GDK_GC_FBDATA(pGC)->values.line_width,
1102 GDK_GC_FBDATA(pGC)->values.line_style,
1103 GDK_GC_FBDATA(pGC)->values.cap_style,
1104 GDK_GC_FBDATA(pGC)->values.join_style);
1105 gdk_fb_drawable_clear(pDrawTo);
1108 fg = GDK_GC_FBDATA(pGC)->values.foreground;
1109 bg = GDK_GC_FBDATA(pGC)->values.background;
1110 if ((GDK_GC_FBDATA(pGC)->values.fill == GDK_TILED) ||
1111 (GDK_GC_FBDATA(pGC)->values.fill == GDK_OPAQUE_STIPPLED))
1112 bg = fg; /* the protocol sez these don't cause color changes */
1114 polyArcs = miComputeArcs (parcs, narcs, pGC);
1119 gdk_pixmap_unref(pDrawTo);
1120 gdk_gc_unref(pGCTo);
1125 cap[0] = cap[1] = 0;
1126 join[0] = join[1] = 0;
1127 for (iphase = ((GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_DOUBLE_DASH) ? 1 : 0);
1132 gdk_gc_set_foreground(pGC, &bg);
1133 else if (GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_DOUBLE_DASH)
1134 gdk_gc_set_foreground(pGC, &fg);
1135 for (i = 0; i < polyArcs[iphase].narcs; i++) {
1136 miArcDataPtr arcData;
1138 arcData = &polyArcs[iphase].arcs[i];
1139 miArcSegment(pDrawTo, pGCTo, arcData->arc,
1140 &arcData->bounds[RIGHT_END],
1141 &arcData->bounds[LEFT_END]);
1142 if (polyArcs[iphase].arcs[i].render) {
1143 fillSpans (pDrawTo, pGCTo);
1145 * don't cap self-joining arcs
1147 if (polyArcs[iphase].arcs[i].selfJoin &&
1148 cap[iphase] < polyArcs[iphase].arcs[i].cap)
1150 while (cap[iphase] < polyArcs[iphase].arcs[i].cap) {
1152 miArcDataPtr arcData0;
1154 arcIndex = polyArcs[iphase].caps[cap[iphase]].arcIndex;
1155 end = polyArcs[iphase].caps[cap[iphase]].end;
1156 arcData0 = &polyArcs[iphase].arcs[arcIndex];
1157 miArcCap (pDrawTo, pGCTo,
1158 &arcData0->bounds[end], end,
1159 arcData0->arc.x, arcData0->arc.y,
1160 (double) arcData0->arc.width / 2.0,
1161 (double) arcData0->arc.height / 2.0);
1164 while (join[iphase] < polyArcs[iphase].arcs[i].join) {
1165 int arcIndex0, arcIndex1, end0, end1;
1167 miArcDataPtr arcData0, arcData1;
1170 joinp = &polyArcs[iphase].joins[join[iphase]];
1171 arcIndex0 = joinp->arcIndex0;
1173 arcIndex1 = joinp->arcIndex1;
1175 phase0 = joinp->phase0;
1176 phase1 = joinp->phase1;
1177 arcData0 = &polyArcs[phase0].arcs[arcIndex0];
1178 arcData1 = &polyArcs[phase1].arcs[arcIndex1];
1179 miArcJoin (pDrawTo, pGCTo,
1180 &arcData0->bounds[end0],
1181 &arcData1->bounds[end1],
1182 arcData0->arc.x, arcData0->arc.y,
1183 (double) arcData0->arc.width / 2.0,
1184 (double) arcData0->arc.height / 2.0,
1185 arcData1->arc.x, arcData1->arc.y,
1186 (double) arcData1->arc.width / 2.0,
1187 (double) arcData1->arc.height / 2.0);
1191 gdk_fb_draw_drawable(pDraw, pGC, pDrawTo, 0, 0, xOrg, yOrg, pixmapWidth, pixmapHeight);
1192 gdk_fb_drawable_clear(pDrawTo);
1197 miFreeArcs(polyArcs, pGC);
1201 gdk_pixmap_unref(pDrawTo);
1202 gdk_gc_unref(pGCTo);
1208 angleBetween (center, point1, point2)
1209 SppPointRec center, point1, point2;
1214 * reflect from X coordinates back to ellipse
1215 * coordinates -- y increasing upwards
1217 a1 = miDatan2 (- (point1.y - center.y), point1.x - center.x);
1218 a2 = miDatan2 (- (point2.y - center.y), point2.x - center.x);
1228 translateBounds (b, x, y, fx, fy)
1239 b->counterClock.x -= fx;
1240 b->counterClock.y -= fy;
1244 miArcJoin (GdkDrawable *pDraw, GdkGC *pGC, miArcFacePtr pLeft, miArcFacePtr pRight,
1245 int xOrgLeft, int yOrgLeft, double xFtransLeft, double yFtransLeft,
1246 int xOrgRight, int yOrgRight, double xFtransRight, double yFtransRight)
1248 SppPointRec center, corner, otherCorner;
1249 SppPointRec poly[5], e;
1250 SppPointPtr pArcPts;
1253 miArcFaceRec Right, Left;
1256 double xFtrans, yFtrans;
1258 double ae, ac2, ec2, bc2, de;
1261 xOrg = (xOrgRight + xOrgLeft) / 2;
1262 yOrg = (yOrgRight + yOrgLeft) / 2;
1263 xFtrans = (xFtransLeft + xFtransRight) / 2;
1264 yFtrans = (yFtransLeft + yFtransRight) / 2;
1266 translateBounds (&Right, xOrg - xOrgRight, yOrg - yOrgRight,
1267 xFtrans - xFtransRight, yFtrans - yFtransRight);
1269 translateBounds (&Left, xOrg - xOrgLeft, yOrg - yOrgLeft,
1270 xFtrans - xFtransLeft, yFtrans - yFtransLeft);
1274 if (pRight->clock.x == pLeft->counterClock.x &&
1275 pRight->clock.y == pLeft->counterClock.y)
1277 center = pRight->center;
1278 if (0 <= (a = angleBetween (center, pRight->clock, pLeft->counterClock))
1281 corner = pRight->clock;
1282 otherCorner = pLeft->counterClock;
1284 a = angleBetween (center, pLeft->clock, pRight->counterClock);
1285 corner = pLeft->clock;
1286 otherCorner = pRight->counterClock;
1288 switch (GDK_GC_FBDATA(pGC)->values.join_style) {
1289 case GDK_JOIN_ROUND:
1290 width = (GDK_GC_FBDATA(pGC)->values.line_width ? (double)GDK_GC_FBDATA(pGC)->values.line_width : (double)1);
1292 arc.x = center.x - width/2;
1293 arc.y = center.y - width/2;
1296 arc.angle1 = -miDatan2 (corner.y - center.y, corner.x - center.x);
1298 pArcPts = (SppPointPtr) g_malloc (3 * sizeof (SppPointRec));
1301 pArcPts[0].x = otherCorner.x;
1302 pArcPts[0].y = otherCorner.y;
1303 pArcPts[1].x = center.x;
1304 pArcPts[1].y = center.y;
1305 pArcPts[2].x = corner.x;
1306 pArcPts[2].y = corner.y;
1307 if( (cpt = miGetArcPts(&arc, 3, &pArcPts)) )
1309 /* by drawing with miFillSppPoly and setting the endpoints of the arc
1310 * to be the corners, we assure that the cap will meet up with the
1311 * rest of the line */
1312 miFillSppPoly(pDraw, pGC, cpt, pArcPts, xOrg, yOrg, xFtrans, yFtrans);
1316 case GDK_JOIN_MITER:
1318 * don't miter arcs with less than 11 degrees between them
1323 poly[2] = otherCorner;
1324 bc2 = (corner.x - otherCorner.x) * (corner.x - otherCorner.x) +
1325 (corner.y - otherCorner.y) * (corner.y - otherCorner.y);
1327 ac2 = (corner.x - center.x) * (corner.x - center.x) +
1328 (corner.y - center.y) * (corner.y - center.y);
1329 ae = sqrt (ac2 - ec2);
1331 e.x = (corner.x + otherCorner.x) / 2;
1332 e.y = (corner.y + otherCorner.y) / 2;
1333 poly[3].x = e.x + de * (e.x - center.x) / ae;
1334 poly[3].y = e.y + de * (e.y - center.y) / ae;
1339 case GDK_JOIN_BEVEL:
1342 poly[2] = otherCorner;
1347 miFillSppPoly (pDraw, pGC, polyLen, poly, xOrg, yOrg, xFtrans, yFtrans);
1352 miArcCap (pDraw, pGC, pFace, end, xOrg, yOrg, xFtrans, yFtrans)
1358 double xFtrans, yFtrans;
1360 SppPointRec corner, otherCorner, center, endPoint, poly[5];
1362 corner = pFace->clock;
1363 otherCorner = pFace->counterClock;
1364 center = pFace->center;
1365 switch (GDK_GC_FBDATA(pGC)->values.cap_style) {
1366 case GDK_CAP_PROJECTING:
1367 poly[0].x = otherCorner.x;
1368 poly[0].y = otherCorner.y;
1369 poly[1].x = corner.x;
1370 poly[1].y = corner.y;
1371 poly[2].x = corner.x -
1372 (center.y - corner.y);
1373 poly[2].y = corner.y +
1374 (center.x - corner.x);
1375 poly[3].x = otherCorner.x -
1376 (otherCorner.y - center.y);
1377 poly[3].y = otherCorner.y +
1378 (otherCorner.x - center.x);
1379 poly[4].x = otherCorner.x;
1380 poly[4].y = otherCorner.y;
1381 miFillSppPoly (pDraw, pGC, 5, poly, xOrg, yOrg, xFtrans, yFtrans);
1385 * miRoundCap just needs these to be unequal.
1388 endPoint.x = endPoint.x + 100;
1389 miRoundCap (pDraw, pGC, center, endPoint, corner, otherCorner, 0,
1390 -xOrg, -yOrg, xFtrans, yFtrans);
1397 /* MIROUNDCAP -- a private helper function
1398 * Put Rounded cap on end. pCenter is the center of this end of the line
1399 * pEnd is the center of the other end of the line. pCorner is one of the
1400 * two corners at this end of the line.
1401 * NOTE: pOtherCorner must be counter-clockwise from pCorner.
1404 static void miRoundCap(GdkDrawable *pDraw, GdkGC *pGC, SppPointRec pCenter, SppPointRec pEnd, SppPointRec pCorner,
1405 SppPointRec pOtherCorner, int fLineEnd, int xOrg, int yOrg,
1406 double xFtrans, double yFtrans)
1412 SppPointPtr pArcPts;
1414 width = (GDK_GC_FBDATA(pGC)->values.line_width ? (double)GDK_GC_FBDATA(pGC)->values.line_width : (double)1);
1416 arc.x = pCenter.x - width/2;
1417 arc.y = pCenter.y - width/2;
1420 arc.angle1 = -miDatan2 (pCorner.y - pCenter.y, pCorner.x - pCenter.x);
1421 if(PTISEQUAL(pCenter, pEnd))
1422 arc.angle2 = - 180.0;
1424 arc.angle2 = -miDatan2 (pOtherCorner.y - pCenter.y, pOtherCorner.x - pCenter.x) - arc.angle1;
1426 arc.angle2 += 360.0;
1428 pArcPts = (SppPointPtr) NULL;
1429 if( (cpt = miGetArcPts(&arc, 0, &pArcPts)) )
1431 /* by drawing with miFillSppPoly and setting the endpoints of the arc
1432 * to be the corners, we assure that the cap will meet up with the
1433 * rest of the line */
1434 miFillSppPoly(pDraw, pGC, cpt, pArcPts, -xOrg, -yOrg, xFtrans, yFtrans);
1440 * To avoid inaccuracy at the cardinal points, use trig functions
1441 * which are exact for those angles
1445 #define M_PI 3.14159265358979323846
1448 #define M_PI_2 1.57079632679489661923
1451 # define Dsin(d) ((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))
1452 # define Dcos(d) ((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))
1453 # define mod(a,b) ((a) >= 0 ? (a) % (b) : (b) - (-a) % (b))
1461 if (floor (a/90) == a/90) {
1463 switch (mod (i, 4)) {
1470 return cos (a * M_PI / 180.0);
1479 if (floor (a/90) == a/90) {
1481 switch (mod (i, 4)) {
1488 return sin (a * M_PI / 180.0);
1501 return asin(v) * (180.0 / M_PI);
1512 } else if (dx == 0) {
1516 } else if (fabs (dy) == fabs (dx)) {
1527 return atan2 (dy, dx) * (180.0 / M_PI);
1531 /* MIGETARCPTS -- Converts an arc into a set of line segments -- a helper
1532 * routine for filled arc and line (round cap) code.
1533 * Returns the number of points in the arc. Note that it takes a pointer
1534 * to a pointer to where it should put the points and an index (cpt).
1535 * This procedure allocates the space necessary to fit the arc points.
1536 * Sometimes it's convenient for those points to be at the end of an existing
1537 * array. (For example, if we want to leave a spare point to make sectors
1538 * instead of segments.) So we pass in the g_malloc()ed chunk that contains the
1539 * array and an index saying where we should start stashing the points.
1540 * If there isn't an array already, we just pass in a null pointer and
1541 * count on g_realloc() to handle the null pointer correctly.
1544 miGetArcPts(SppArcPtr parc, int cpt, SppPointPtr *ppPts)
1546 SppArcPtr parc; /* points to an arc */
1547 int cpt; /* number of points already in arc list */
1548 SppPointPtr *ppPts; /* pointer to pointer to arc-list -- modified */
1551 double st, /* Start Theta, start angle */
1552 et, /* End Theta, offset from start theta */
1553 dt, /* Delta Theta, angle to sweep ellipse */
1554 cdt, /* Cos Delta Theta, actually 2 cos(dt) */
1555 x0, y0, /* the recurrence formula needs two points to start */
1557 x2, y2, /* this will be the new point generated */
1558 xc, yc; /* the center point */
1561 GdkPoint last; /* last point on integer boundaries */
1563 /* The spec says that positive angles indicate counterclockwise motion.
1564 * Given our coordinate system (with 0,0 in the upper left corner),
1565 * the screen appears flipped in Y. The easiest fix is to negate the
1568 st = - parc->angle1;
1570 et = - parc->angle2;
1572 /* Try to get a delta theta that is within 1/2 pixel. Then adjust it
1573 * so that it divides evenly into the total.
1574 * I'm just using cdt 'cause I'm lazy.
1577 if (parc->height > cdt)
1584 dt = miDasin ( 1.0 / cdt ); /* minimum step necessary */
1586 count = abs(count) + 1;
1590 cdt = 2 * miDcos(dt);
1591 if (!(poly = (SppPointPtr) g_realloc((gpointer)*ppPts,
1592 (cpt + count) * sizeof(SppPointRec))))
1596 xc = parc->width/2.0; /* store half width and half height */
1597 yc = parc->height/2.0;
1599 x0 = xc * miDcos(st);
1600 y0 = yc * miDsin(st);
1601 x1 = xc * miDcos(st + dt);
1602 y1 = yc * miDsin(st + dt);
1603 xc += parc->x; /* by adding initial point, these become */
1604 yc += parc->y; /* the center point */
1606 poly[cpt].x = (xc + x0);
1607 poly[cpt].y = (yc + y0);
1608 last.x = ROUNDTOINT( poly[cpt + 1].x = (xc + x1) );
1609 last.y = ROUNDTOINT( poly[cpt + 1].y = (yc + y1) );
1611 for(i = 2; i < count; i++)
1616 poly[cpt + i].x = (xc + x2);
1617 poly[cpt + i].y = (yc + y2);
1622 /* adjust the last point */
1623 if (abs(parc->angle2) >= 360.0)
1624 poly[cpt +i -1] = poly[0];
1626 poly[cpt +i -1].x = (miDcos(st + et) * parc->width/2.0 + xc);
1627 poly[cpt +i -1].y = (miDsin(st + et) * parc->height/2.0 + yc);
1634 double x0, y0, x1, y1;
1638 # define ADD_REALLOC_STEP 20
1641 addCap (capsp, ncapsp, sizep, end, arcIndex)
1643 int *ncapsp, *sizep;
1649 if (*ncapsp == *sizep)
1651 newsize = *sizep + ADD_REALLOC_STEP;
1652 cap = (miArcCapPtr) g_realloc (*capsp,
1653 newsize * sizeof (**capsp));
1659 cap = &(*capsp)[*ncapsp];
1661 cap->arcIndex = arcIndex;
1666 addJoin (joinsp, njoinsp, sizep, end0, index0, phase0, end1, index1, phase1)
1667 miArcJoinPtr *joinsp;
1668 int *njoinsp, *sizep;
1669 int end0, index0, phase0, end1, index1, phase1;
1674 if (*njoinsp == *sizep)
1676 newsize = *sizep + ADD_REALLOC_STEP;
1677 join = (miArcJoinPtr) g_realloc (*joinsp,
1678 newsize * sizeof (**joinsp));
1684 join = &(*joinsp)[*njoinsp];
1686 join->arcIndex0 = index0;
1687 join->phase0 = phase0;
1689 join->arcIndex1 = index1;
1690 join->phase1 = phase1;
1695 addArc (arcsp, narcsp, sizep, xarc)
1696 miArcDataPtr *arcsp;
1697 int *narcsp, *sizep;
1703 if (*narcsp == *sizep)
1705 newsize = *sizep + ADD_REALLOC_STEP;
1706 arc = (miArcDataPtr) g_realloc (*arcsp,
1707 newsize * sizeof (**arcsp));
1709 return (miArcDataPtr)NULL;
1713 arc = &(*arcsp)[*narcsp];
1720 miFreeArcs(miPolyArcPtr arcs, GdkGC *pGC)
1724 for (iphase = ((GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_DOUBLE_DASH) ? 1 : 0);
1728 if (arcs[iphase].narcs > 0)
1729 g_free(arcs[iphase].arcs);
1730 if (arcs[iphase].njoins > 0)
1731 g_free(arcs[iphase].joins);
1732 if (arcs[iphase].ncaps > 0)
1733 g_free(arcs[iphase].caps);
1739 * map angles to radial distance. This only deals with the first quadrant
1743 * a polygonal approximation to the arc for computing arc lengths
1746 # define dashIndexToAngle(di) ((((double) (di)) * 90.0) / ((double) DASH_MAP_SIZE - 1))
1747 # define xAngleToDashIndex(xa) ((((long) (xa)) * (DASH_MAP_SIZE - 1)) / (90 * 64))
1748 # define dashIndexToXAngle(di) ((((long) (di)) * (90 * 64)) / (DASH_MAP_SIZE - 1))
1749 # define dashXAngleStep (((double) (90 * 64)) / ((double) (DASH_MAP_SIZE - 1)))
1752 computeDashMap (arcp, map)
1757 double a, x, y, prevx, prevy, dist;
1759 for (di = 0; di < DASH_MAP_SIZE; di++) {
1760 a = dashIndexToAngle (di);
1761 x = ((double) arcp->width / 2.0) * miDcos (a);
1762 y = ((double) arcp->height / 2.0) * miDsin (a);
1766 dist = hypot (x - prevx, y - prevy);
1767 map->map[di] = map->map[di - 1] + dist;
1774 typedef enum {HORIZONTAL, VERTICAL, OTHER} arcTypes;
1776 /* this routine is a bit gory */
1779 miComputeArcs (miArc *parcs, int narcs, GdkGC *pGC)
1781 int isDashed, isDoubleDash;
1784 int start, i, j, k, nexti, nextk;
1790 struct arcData *data;
1793 int iphase, prevphase, joinphase;
1797 int iDash, dashRemaining;
1798 int iDashStart, dashRemainingStart, iphaseStart;
1799 int startAngle, spanAngle, endAngle, backwards;
1800 int prevDashAngle, dashAngle;
1803 isDashed = !(GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_SOLID);
1804 isDoubleDash = (GDK_GC_FBDATA(pGC)->values.line_style == GDK_LINE_DOUBLE_DASH);
1805 dashOffset = GDK_GC_FBDATA(pGC)->dash_offset;
1807 data = (struct arcData *) ALLOCATE_LOCAL (narcs * sizeof (struct arcData));
1809 return (miPolyArcPtr)NULL;
1810 arcs = (miPolyArcPtr) g_malloc (sizeof (*arcs) * (isDoubleDash ? 2 : 1));
1813 DEALLOCATE_LOCAL(data);
1814 return (miPolyArcPtr)NULL;
1816 for (i = 0; i < narcs; i++) {
1817 a0 = todeg (parcs[i].angle1);
1818 angle2 = parcs[i].angle2;
1819 if (angle2 > FULLCIRCLE)
1820 angle2 = FULLCIRCLE;
1821 else if (angle2 < -FULLCIRCLE)
1822 angle2 = -FULLCIRCLE;
1823 data[i].selfJoin = angle2 == FULLCIRCLE || angle2 == -FULLCIRCLE;
1824 a1 = todeg (parcs[i].angle1 + angle2);
1825 data[i].x0 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a0));
1826 data[i].y0 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a0));
1827 data[i].x1 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a1));
1828 data[i].y1 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a1));
1831 for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++) {
1832 arcs[iphase].njoins = 0;
1833 arcs[iphase].joins = 0;
1834 joinSize[iphase] = 0;
1836 arcs[iphase].ncaps = 0;
1837 arcs[iphase].caps = 0;
1838 capSize[iphase] = 0;
1840 arcs[iphase].narcs = 0;
1841 arcs[iphase].arcs = 0;
1842 arcSize[iphase] = 0;
1848 dashRemaining = GDK_GC_FBDATA(pGC)->dash_list[0];
1849 while (dashOffset > 0) {
1850 if (dashOffset >= dashRemaining) {
1851 dashOffset -= dashRemaining;
1852 iphase = iphase ? 0 : 1;
1854 if (iDash == GDK_GC_FBDATA(pGC)->dash_list_len)
1856 dashRemaining = GDK_GC_FBDATA(pGC)->dash_list[iDash];
1858 dashRemaining -= dashOffset;
1863 dashRemainingStart = dashRemaining;
1865 iphaseStart = iphase;
1867 for (i = narcs - 1; i >= 0; i--) {
1871 if (data[i].selfJoin || i == j ||
1872 (UNEQUAL (data[i].x1, data[j].x0) ||
1873 UNEQUAL (data[i].y1, data[j].y0)))
1875 if (iphase == 0 || isDoubleDash)
1876 addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
1877 &capSize[iphase], RIGHT_END, 0);
1894 ** deal with dashed arcs. Use special rules for certain 0 area arcs.
1895 ** Presumably, the other 0 area arcs still aren't done right.
1897 arcTypes arcType = OTHER;
1900 if (parcs[i].height == 0
1901 && (parcs[i].angle1 % FULLCIRCLE) == 0x2d00
1902 && parcs[i].angle2 == 0x2d00)
1903 arcType = HORIZONTAL;
1904 else if (parcs[i].width == 0
1905 && (parcs[i].angle1 % FULLCIRCLE) == 0x1680
1906 && parcs[i].angle2 == 0x2d00)
1908 if (arcType == OTHER) {
1910 * precompute an approximation map
1912 computeDashMap (&parcs[i], &map);
1914 * compute each individual dash segment using the path
1917 startAngle = parcs[i].angle1;
1918 spanAngle = parcs[i].angle2;
1919 if (spanAngle > FULLCIRCLE)
1920 spanAngle = FULLCIRCLE;
1921 else if (spanAngle < -FULLCIRCLE)
1922 spanAngle = -FULLCIRCLE;
1924 startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
1925 if (startAngle >= FULLCIRCLE)
1926 startAngle = startAngle % FULLCIRCLE;
1927 endAngle = startAngle + spanAngle;
1928 backwards = spanAngle < 0;
1931 if (arcType == VERTICAL) {
1932 xarc.angle1 = 0x1680;
1933 startAngle = parcs[i].y;
1934 endAngle = startAngle + parcs[i].height;
1936 xarc.angle1 = 0x2d00;
1937 startAngle = parcs[i].x;
1938 endAngle = startAngle + parcs[i].width;
1941 dashAngle = startAngle;
1942 selfJoin = data[i].selfJoin &&
1943 (iphase == 0 || isDoubleDash);
1945 * add dashed arcs to each bucket
1948 while (dashAngle != endAngle) {
1949 prevDashAngle = dashAngle;
1950 if (arcType == OTHER) {
1951 dashAngle = computeAngleFromPath (prevDashAngle, endAngle,
1952 &map, &dashRemaining, backwards);
1953 /* avoid troubles with huge arcs and small dashes */
1954 if (dashAngle == prevDashAngle) {
1961 thisLength = (dashAngle + dashRemaining <= endAngle) ?
1962 dashRemaining : endAngle - dashAngle;
1963 if (arcType == VERTICAL) {
1965 xarc.height = thisLength;
1968 xarc.width = thisLength;
1970 dashAngle += thisLength;
1971 dashRemaining -= thisLength;
1973 if (iphase == 0 || isDoubleDash) {
1974 if (arcType == OTHER) {
1976 spanAngle = prevDashAngle;
1978 spanAngle = FULLCIRCLE - (-spanAngle) % FULLCIRCLE;
1979 if (spanAngle >= FULLCIRCLE)
1980 spanAngle = spanAngle % FULLCIRCLE;
1981 xarc.angle1 = spanAngle;
1982 spanAngle = dashAngle - prevDashAngle;
1984 if (dashAngle > prevDashAngle)
1985 spanAngle = - FULLCIRCLE + spanAngle;
1987 if (dashAngle < prevDashAngle)
1988 spanAngle = FULLCIRCLE + spanAngle;
1990 if (spanAngle > FULLCIRCLE)
1991 spanAngle = FULLCIRCLE;
1992 if (spanAngle < -FULLCIRCLE)
1993 spanAngle = -FULLCIRCLE;
1994 xarc.angle2 = spanAngle;
1996 arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
1997 &arcSize[iphase], &xarc);
2001 * cap each end of an on/off dash
2003 if (!isDoubleDash) {
2004 if (prevDashAngle != startAngle) {
2005 addCap (&arcs[iphase].caps,
2006 &arcs[iphase].ncaps,
2007 &capSize[iphase], RIGHT_END,
2008 arc - arcs[iphase].arcs);
2011 if (dashAngle != endAngle) {
2012 addCap (&arcs[iphase].caps,
2013 &arcs[iphase].ncaps,
2014 &capSize[iphase], LEFT_END,
2015 arc - arcs[iphase].arcs);
2018 arc->cap = arcs[iphase].ncaps;
2019 arc->join = arcs[iphase].njoins;
2022 if (dashAngle == endAngle)
2023 arc->selfJoin = selfJoin;
2026 if (dashRemaining <= 0) {
2028 if (iDash == GDK_GC_FBDATA(pGC)->dash_list_len)
2030 iphase = iphase ? 0:1;
2031 dashRemaining = GDK_GC_FBDATA(pGC)->dash_list[iDash];
2035 * make sure a place exists for the position data when
2036 * drawing a zero-length arc
2038 if (startAngle == endAngle) {
2040 if (!isDoubleDash && iphase == 1)
2042 arc = addArc (&arcs[prevphase].arcs, &arcs[prevphase].narcs,
2043 &arcSize[prevphase], &parcs[i]);
2046 arc->join = arcs[prevphase].njoins;
2047 arc->cap = arcs[prevphase].ncaps;
2048 arc->selfJoin = data[i].selfJoin;
2051 arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
2052 &arcSize[iphase], &parcs[i]);
2055 arc->join = arcs[iphase].njoins;
2056 arc->cap = arcs[iphase].ncaps;
2057 arc->selfJoin = data[i].selfJoin;
2060 if (prevphase == 0 || isDoubleDash)
2061 k = arcs[prevphase].narcs - 1;
2062 if (iphase == 0 || isDoubleDash)
2063 nextk = arcs[iphase].narcs;
2064 if (nexti == start) {
2068 iphase = iphaseStart;
2069 dashRemaining = dashRemainingStart;
2072 arcsJoin = narcs > 1 && i != j &&
2073 ISEQUAL (data[i].x1, data[j].x0) &&
2074 ISEQUAL (data[i].y1, data[j].y0) &&
2075 !data[i].selfJoin && !data[j].selfJoin;
2084 (prevphase == 0 || isDoubleDash) &&
2085 (iphase == 0 || isDoubleDash))
2090 joinphase = iphaseStart;
2092 * if the join is right at the dash,
2093 * draw the join in foreground
2094 * This is because the foreground
2095 * arcs are computed second, the results
2096 * of which are needed to draw the join
2098 if (joinphase != prevphase)
2101 if (joinphase == 0 || isDoubleDash) {
2102 addJoin (&arcs[joinphase].joins,
2103 &arcs[joinphase].njoins,
2104 &joinSize[joinphase],
2105 LEFT_END, k, prevphase,
2106 RIGHT_END, nextk, iphase);
2107 arc->join = arcs[prevphase].njoins;
2111 * cap the left end of this arc
2112 * unless it joins itself
2114 if ((prevphase == 0 || isDoubleDash) &&
2117 addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
2118 &capSize[prevphase], LEFT_END, k);
2119 arc->cap = arcs[prevphase].ncaps;
2121 if (isDashed && !arcsJoin) {
2123 iphase = iphaseStart;
2124 dashRemaining = dashRemainingStart;
2126 nextk = arcs[iphase].narcs;
2127 if (nexti == start) {
2130 iphase = iphaseStart;
2131 dashRemaining = dashRemainingStart;
2134 * cap the right end of the next arc. If the
2135 * next arc is actually the first arc, only
2136 * cap it if it joins with this arc. This
2137 * case will occur when the final dash segment
2138 * of an on/off dash is off. Of course, this
2139 * cap will be drawn at a strange time, but that
2142 if ((iphase == 0 || isDoubleDash) &&
2143 (nexti != start || (arcsJoin && isDashed)))
2144 addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
2145 &capSize[iphase], RIGHT_END, nextk);
2152 * make sure the last section is rendered
2154 for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++)
2155 if (arcs[iphase].narcs > 0) {
2156 arcs[iphase].arcs[arcs[iphase].narcs-1].render = 1;
2157 arcs[iphase].arcs[arcs[iphase].narcs-1].join =
2158 arcs[iphase].njoins;
2159 arcs[iphase].arcs[arcs[iphase].narcs-1].cap =
2162 DEALLOCATE_LOCAL(data);
2165 miFreeArcs(arcs, pGC);
2166 DEALLOCATE_LOCAL(data);
2167 return (miPolyArcPtr)NULL;
2171 angleToLength (angle, map)
2175 double len, excesslen, sidelen = map->map[DASH_MAP_SIZE - 1], totallen;
2178 gboolean oddSide = FALSE;
2182 while (angle >= 90 * 64) {
2184 totallen += sidelen;
2190 totallen -= sidelen;
2195 angle = 90 * 64 - angle;
2197 di = xAngleToDashIndex (angle);
2198 excess = angle - dashIndexToXAngle (di);
2202 * linearly interpolate between this point and the next
2205 excesslen = (map->map[di + 1] - map->map[di]) *
2206 ((double) excess) / dashXAngleStep;
2210 totallen += (sidelen - len);
2217 * len is along the arc, but may be more than one rotation
2221 lengthToAngle (len, map)
2225 double sidelen = map->map[DASH_MAP_SIZE - 1];
2226 int angle, angleexcess;
2227 gboolean oddSide = FALSE;
2232 * step around the ellipse, subtracting sidelens and
2233 * adding 90 degrees. oddSide will tell if the
2234 * map should be interpolated in reverse
2238 return 2 * FULLCIRCLE; /* infinity */
2239 while (len >= sidelen) {
2246 return -2 * FULLCIRCLE; /* infinity */
2254 len = sidelen - len;
2256 a1 = DASH_MAP_SIZE - 1;
2258 * binary search for the closest pre-computed length
2260 while (a1 - a0 > 1) {
2262 if (len > map->map[a])
2267 angleexcess = dashIndexToXAngle (a0);
2269 * linearly interpolate to the next point
2271 angleexcess += (len - map->map[a0]) /
2272 (map->map[a0+1] - map->map[a0]) * dashXAngleStep;
2274 angle += (90 * 64) - angleexcess;
2276 angle += angleexcess;
2281 * compute the angle of an ellipse which cooresponds to
2282 * the given path length. Note that the correct solution
2283 * to this problem is an eliptic integral, we'll punt and
2284 * approximate (it's only for dashes anyway). This
2285 * approximation uses a polygon.
2287 * The remaining portion of len is stored in *lenp -
2288 * this will be negative if the arc extends beyond
2289 * len and positive if len extends beyond the arc.
2292 static int computeAngleFromPath(int startAngle, int endAngle, dashMap *map, int *lenp, int backwards)
2293 /* int startAngle, endAngle; *//* normalized absolute angles in *64 degrees */
2304 * flip the problem around to always be
2307 a0 = FULLCIRCLE - a0;
2308 a1 = FULLCIRCLE - a1;
2312 len0 = angleToLength (a0, map);
2313 a = lengthToAngle (len0 + len, map);
2316 len -= angleToLength (a1, map) - len0;
2326 * scan convert wide arcs.
2330 * draw zero width/height arcs
2334 drawZeroArc (pDraw, pGC, tarc, lw, left, right)
2339 miArcFacePtr right, left;
2341 double x0, y0, x1, y1, w, h, x, y;
2342 double xmax, ymax, xmin, ymin;
2344 double a, startAngle, endAngle;
2350 if (a1 > FULLCIRCLE)
2352 else if (a1 < -FULLCIRCLE)
2354 w = (double)tarc->width / 2.0;
2355 h = (double)tarc->height / 2.0;
2357 * play in X coordinates right away
2359 startAngle = - ((double) a0 / 64.0);
2360 endAngle = - ((double) (a0 + a1) / 64.0);
2371 if (a == startAngle)
2391 if (a1 < 0) /* clockwise */
2393 if (floor (a / 90.0) == floor (endAngle / 90.0))
2396 a = 90 * (floor (a/90.0) + 1);
2400 if (ceil (a / 90.0) == ceil (endAngle / 90.0))
2403 a = 90 * (ceil (a/90.0) - 1);
2407 if ((x1 - x0) + (y1 - y0) < 0)
2418 right->center.x = x0;
2419 right->center.y = y0;
2420 right->clock.x = x0 - lx;
2421 right->clock.y = y0 - ly;
2422 right->counterClock.x = x0 + lx;
2423 right->counterClock.y = y0 + ly;
2427 left->center.x = x1;
2428 left->center.y = y1;
2429 left->clock.x = x1 + lx;
2430 left->clock.y = y1 + ly;
2431 left->counterClock.x = x1 - lx;
2432 left->counterClock.y = y1 - ly;
2446 if (xmax != xmin && ymax != ymin) {
2447 int minx, maxx, miny, maxy;
2449 minx = ICEIL (xmin + w) + tarc->x;
2450 maxx = ICEIL (xmax + w) + tarc->x;
2451 miny = ICEIL (ymin + h) + tarc->y;
2452 maxy = ICEIL (ymax + h) + tarc->y;
2454 gdk_fb_draw_rectangle(pDraw, pGC, TRUE, minx, miny, maxx - minx, maxy - miny);
2459 * this computes the ellipse y value associated with the
2460 * bottom of the tail.
2464 tailEllipseY (def, acc)
2465 struct arc_def *def;
2466 struct accelerators *acc;
2471 if (def->w == def->h)
2473 t = def->l * def->w;
2474 if (def->w > def->h) {
2481 t = 2.0 * def->h * t;
2482 t = (CUBED_ROOT_4 * acc->h2 - cbrt(t * t)) / acc->h2mw2;
2484 acc->tail_y = def->h / CUBED_ROOT_2 * sqrt(t);
2488 * inverse functions -- compute edge coordinates
2493 outerXfromXY (x, y, def, acc)
2495 struct arc_def *def;
2496 struct accelerators *acc;
2498 return x + (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2502 outerYfromXY (x, y, def, acc)
2504 struct arc_def *def;
2505 struct accelerators *acc;
2507 return y + (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2511 innerXfromXY (x, y, def, acc)
2513 struct arc_def *def;
2514 struct accelerators *acc;
2516 return x - (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2520 innerYfromXY (x, y, def, acc)
2522 struct arc_def *def;
2523 struct accelerators *acc;
2525 return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2529 innerYfromY (y, def, acc)
2531 struct arc_def *def;
2532 struct accelerators *acc;
2536 x = (def->w / def->h) * sqrt (acc->h2 - y*y);
2538 return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2542 computeLine (x1, y1, x2, y2, line)
2543 double x1, y1, x2, y2;
2549 line->m = (x1 - x2) / (y1 - y2);
2550 line->b = x1 - y1 * line->m;
2556 * compute various accelerators for an ellipse. These
2557 * are simply values that are used repeatedly in
2562 computeAcc (tarc, lw, def, acc)
2565 struct arc_def *def;
2566 struct accelerators *acc;
2568 def->w = ((double) tarc->width) / 2.0;
2569 def->h = ((double) tarc->height) / 2.0;
2570 def->l = ((double) lw) / 2.0;
2571 acc->h2 = def->h * def->h;
2572 acc->w2 = def->w * def->w;
2573 acc->h4 = acc->h2 * acc->h2;
2574 acc->w4 = acc->w2 * acc->w2;
2575 acc->h2l = acc->h2 * def->l;
2576 acc->w2l = acc->w2 * def->l;
2577 acc->h2mw2 = acc->h2 - acc->w2;
2578 acc->fromIntX = (tarc->width & 1) ? 0.5 : 0.0;
2579 acc->fromIntY = (tarc->height & 1) ? 0.5 : 0.0;
2580 acc->xorg = tarc->x + (tarc->width >> 1);
2581 acc->yorgu = tarc->y + (tarc->height >> 1);
2582 acc->yorgl = acc->yorgu + (tarc->height & 1);
2583 tailEllipseY (def, acc);
2587 * compute y value bounds of various portions of the arc,
2588 * the outer edge, the ellipse and the inner edge.
2592 computeBound (def, bound, acc, right, left)
2593 struct arc_def *def;
2594 struct arc_bound *bound;
2595 struct accelerators *acc;
2596 miArcFacePtr right, left;
2601 struct bound innerx, outerx;
2602 struct bound ellipsex;
2604 bound->ellipse.min = Dsin (def->a0) * def->h;
2605 bound->ellipse.max = Dsin (def->a1) * def->h;
2606 if (def->a0 == 45 && def->w == def->h)
2607 ellipsex.min = bound->ellipse.min;
2609 ellipsex.min = Dcos (def->a0) * def->w;
2610 if (def->a1 == 45 && def->w == def->h)
2611 ellipsex.max = bound->ellipse.max;
2613 ellipsex.max = Dcos (def->a1) * def->w;
2614 bound->outer.min = outerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2615 bound->outer.max = outerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2616 bound->inner.min = innerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2617 bound->inner.max = innerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2619 outerx.min = outerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2620 outerx.max = outerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2621 innerx.min = innerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2622 innerx.max = innerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2625 * save the line end points for the
2626 * cap code to use. Careful here, these are
2627 * in cartesean coordinates (y increasing upwards)
2628 * while the cap code uses inverted coordinates
2629 * (y increasing downwards)
2633 right->counterClock.y = bound->outer.min;
2634 right->counterClock.x = outerx.min;
2635 right->center.y = bound->ellipse.min;
2636 right->center.x = ellipsex.min;
2637 right->clock.y = bound->inner.min;
2638 right->clock.x = innerx.min;
2642 left->clock.y = bound->outer.max;
2643 left->clock.x = outerx.max;
2644 left->center.y = bound->ellipse.max;
2645 left->center.x = ellipsex.max;
2646 left->counterClock.y = bound->inner.max;
2647 left->counterClock.x = innerx.max;
2650 bound->left.min = bound->inner.max;
2651 bound->left.max = bound->outer.max;
2652 bound->right.min = bound->inner.min;
2653 bound->right.max = bound->outer.min;
2655 computeLine (innerx.min, bound->inner.min, outerx.min, bound->outer.min,
2657 computeLine (innerx.max, bound->inner.max, outerx.max, bound->outer.max,
2660 if (bound->inner.min > bound->inner.max) {
2661 t = bound->inner.min;
2662 bound->inner.min = bound->inner.max;
2663 bound->inner.max = t;
2665 tail_y = acc->tail_y;
2666 if (tail_y > bound->ellipse.max)
2667 tail_y = bound->ellipse.max;
2668 else if (tail_y < bound->ellipse.min)
2669 tail_y = bound->ellipse.min;
2670 innerTaily = innerYfromY (tail_y, def, acc);
2671 if (bound->inner.min > innerTaily)
2672 bound->inner.min = innerTaily;
2673 if (bound->inner.max < innerTaily)
2674 bound->inner.max = innerTaily;
2675 bound->inneri.min = ICEIL(bound->inner.min - acc->fromIntY);
2676 bound->inneri.max = floor(bound->inner.max - acc->fromIntY);
2677 bound->outeri.min = ICEIL(bound->outer.min - acc->fromIntY);
2678 bound->outeri.max = floor(bound->outer.max - acc->fromIntY);
2682 * this section computes the x value of the span at y
2683 * intersected with the specified face of the ellipse.
2685 * this is the min/max X value over the set of normal
2686 * lines to the entire ellipse, the equation of the
2690 * x = ------------ y + ellipse_x (1 - --- )
2693 * compute the derivative with-respect-to ellipse_y and solve
2696 * (w^2 - h^2) ellipse_y^3 + h^4 y
2697 * 0 = - ----------------------------------
2698 * h w ellipse_y^2 sqrt (h^2 - ellipse_y^2)
2701 * ellipse_y = ( ---------- ) ^ (1/3)
2704 * The other two solutions to the equation are imaginary.
2706 * This gives the position on the ellipse which generates
2707 * the normal with the largest/smallest x intersection point.
2709 * Now compute the second derivative to check whether
2710 * the intersection is a minimum or maximum:
2712 * h (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2713 * - -------------------------------------------
2714 * w y0^3 (sqrt (h^2 - y^2)) ^ 3
2716 * as we only care about the sign,
2718 * - (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2720 * or (to use accelerators),
2722 * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2)
2727 * computes the position on the ellipse whose normal line
2728 * intersects the given scan line maximally
2732 hookEllipseY (scan_y, bound, acc, left)
2734 struct arc_bound *bound;
2735 struct accelerators *acc;
2740 if (acc->h2mw2 == 0) {
2741 if ( (scan_y > 0 && !left) || (scan_y < 0 && left) )
2742 return bound->ellipse.min;
2743 return bound->ellipse.max;
2745 ret = (acc->h4 * scan_y) / (acc->h2mw2);
2749 return -cbrt (-ret);
2753 * computes the X value of the intersection of the
2754 * given scan line with the right side of the lower hook
2758 hookX (scan_y, def, bound, acc, left)
2760 struct arc_def *def;
2761 struct arc_bound *bound;
2762 struct accelerators *acc;
2765 double ellipse_y, x;
2768 if (def->w != def->h) {
2769 ellipse_y = hookEllipseY (scan_y, bound, acc, left);
2770 if (boundedLe (ellipse_y, bound->ellipse)) {
2772 * compute the value of the second
2775 maxMin = ellipse_y*ellipse_y*ellipse_y * acc->h2mw2 -
2776 acc->h2 * scan_y * (3 * ellipse_y*ellipse_y - 2*acc->h2);
2777 if ((left && maxMin > 0) || (!left && maxMin < 0)) {
2779 return def->w + left ? -def->l : def->l;
2780 x = (acc->h2 * scan_y - ellipse_y * acc->h2mw2) *
2781 sqrt (acc->h2 - ellipse_y * ellipse_y) /
2782 (def->h * def->w * ellipse_y);
2788 if (acc->left.valid && boundedLe (scan_y, bound->left)) {
2789 x = intersectLine (scan_y, acc->left);
2791 if (acc->right.valid)
2792 x = intersectLine (scan_y, acc->right);
2794 x = def->w - def->l;
2797 if (acc->right.valid && boundedLe (scan_y, bound->right)) {
2798 x = intersectLine (scan_y, acc->right);
2800 if (acc->left.valid)
2801 x = intersectLine (scan_y, acc->left);
2803 x = def->w - def->l;
2810 * generate the set of spans with
2811 * the given y coordinate
2815 arcSpan (y, lx, lw, rx, rw, def, bounds, acc, mask)
2821 struct arc_def *def;
2822 struct arc_bound *bounds;
2823 struct accelerators *acc;
2826 int linx, loutx, rinx, routx;
2829 if (boundedLe (y, bounds->inneri)) {
2834 * intersection with left face
2836 x = hookX (y + acc->fromIntY, def, bounds, acc, 1);
2837 if (acc->right.valid &&
2838 boundedLe (y + acc->fromIntY, bounds->right))
2840 altx = intersectLine (y + acc->fromIntY, acc->right);
2844 linx = -ICEIL(acc->fromIntX - x);
2845 rinx = ICEIL(acc->fromIntX + x);
2847 if (boundedLe (y, bounds->outeri)) {
2852 * intersection with right face
2854 x = hookX (y + acc->fromIntY, def, bounds, acc, 0);
2855 if (acc->left.valid &&
2856 boundedLe (y + acc->fromIntY, bounds->left))
2859 x = intersectLine (y + acc->fromIntY, acc->left);
2863 loutx = -ICEIL(acc->fromIntX - x);
2864 routx = ICEIL(acc->fromIntX + x);
2868 newFinalSpan (acc->yorgu - y,
2869 acc->xorg + rinx, acc->xorg + routx);
2871 newFinalSpan (acc->yorgl + y,
2872 acc->xorg + rinx, acc->xorg + routx);
2876 newFinalSpan (acc->yorgu - y,
2877 acc->xorg - loutx, acc->xorg - linx);
2879 newFinalSpan (acc->yorgl + y,
2880 acc->xorg - loutx, acc->xorg - linx);
2885 arcSpan0 (lx, lw, rx, rw, def, bounds, acc, mask)
2890 struct arc_def *def;
2891 struct arc_bound *bounds;
2892 struct accelerators *acc;
2897 if (boundedLe (0, bounds->inneri) &&
2898 acc->left.valid && boundedLe (0, bounds->left) &&
2901 x = def->w - def->l;
2902 if (acc->left.b < x)
2904 lw = ICEIL(acc->fromIntX - x) - lx;
2906 rx = ICEIL(acc->fromIntX + x);
2909 arcSpan (0, lx, lw, rx, rw, def, bounds, acc, mask);
2913 tailSpan (y, lw, rw, def, bounds, acc, mask)
2917 struct arc_def *def;
2918 struct arc_bound *bounds;
2919 struct accelerators *acc;
2922 double yy, xalt, x, lx, rx;
2925 if (boundedLe(y, bounds->outeri))
2926 arcSpan (y, 0, lw, -rw, rw, def, bounds, acc, mask);
2927 else if (def->w != def->h) {
2928 yy = y + acc->fromIntY;
2929 x = tailX(yy, def, bounds, acc);
2930 if (yy == 0.0 && x == -rw - acc->fromIntX)
2932 if (acc->right.valid && boundedLe (yy, bounds->right)) {
2935 xalt = intersectLine (yy, acc->right);
2936 if (xalt >= -rw - acc->fromIntX && xalt <= rx)
2938 n = ICEIL(acc->fromIntX + lx);
2941 newFinalSpan (acc->yorgu - y,
2942 acc->xorg + n, acc->xorg + lw);
2944 newFinalSpan (acc->yorgl + y,
2945 acc->xorg + n, acc->xorg + lw);
2947 n = ICEIL(acc->fromIntX + rx);
2950 newFinalSpan (acc->yorgu - y,
2951 acc->xorg - rw, acc->xorg + n);
2953 newFinalSpan (acc->yorgl + y,
2954 acc->xorg - rw, acc->xorg + n);
2958 ICEIL(acc->fromIntX - x), 0,
2959 ICEIL(acc->fromIntX + x), 0,
2960 def, bounds, acc, mask);
2965 * create whole arcs out of pieces. This code is
2969 static struct finalSpan **finalSpans = NULL;
2970 static int finalMiny = 0, finalMaxy = -1;
2971 static int finalSize = 0;
2973 static int nspans = 0; /* total spans, not just y coords */
2976 struct finalSpan *next;
2977 int min, max; /* x values */
2980 static struct finalSpan *freeFinalSpans, *tmpFinalSpan;
2982 # define allocFinalSpan() (freeFinalSpans ?\
2983 ((tmpFinalSpan = freeFinalSpans), \
2984 (freeFinalSpans = freeFinalSpans->next), \
2985 (tmpFinalSpan->next = 0), \
2989 # define SPAN_CHUNK_SIZE 128
2991 struct finalSpanChunk {
2992 struct finalSpan data[SPAN_CHUNK_SIZE];
2993 struct finalSpanChunk *next;
2996 static struct finalSpanChunk *chunks;
3001 register struct finalSpanChunk *newChunk;
3002 register struct finalSpan *span;
3005 newChunk = (struct finalSpanChunk *) g_malloc (sizeof (struct finalSpanChunk));
3007 return (struct finalSpan *) NULL;
3008 newChunk->next = chunks;
3010 freeFinalSpans = span = newChunk->data + 1;
3011 for (i = 1; i < SPAN_CHUNK_SIZE-1; i++) {
3012 span->next = span+1;
3016 span = newChunk->data;
3022 disposeFinalSpans ()
3024 struct finalSpanChunk *chunk, *next;
3026 for (chunk = chunks; chunk; chunk = next) {
3037 fillSpans (pDrawable, pGC)
3038 GdkDrawable* pDrawable;
3041 register struct finalSpan *span;
3042 register GdkRectangle* xSpan;
3044 register struct finalSpan **f;
3046 GdkRectangle* xSpans;
3050 xSpan = xSpans = (GdkRectangle*) ALLOCATE_LOCAL (nspans * sizeof (GdkRectangle));
3055 for (spany = finalMiny; spany <= finalMaxy; spany++, f++) {
3056 for (span = *f; span; span=span->next) {
3057 if (span->max <= span->min)
3059 xSpan->x = span->min;
3061 xSpan->width = span->max - span->min;
3068 gdk_fb_fill_spans(pDrawable, pGC, xSpans, i);
3070 disposeFinalSpans ();
3072 DEALLOCATE_LOCAL (xSpans);
3079 # define SPAN_REALLOC 100
3081 # define findSpan(y) ((finalMiny <= (y) && (y) <= finalMaxy) ? \
3082 &finalSpans[(y) - finalMiny] : \
3085 static struct finalSpan **
3089 struct finalSpan **newSpans;
3090 int newSize, newMiny, newMaxy;
3094 if (y < finalMiny || y > finalMaxy) {
3100 change = finalMiny - y;
3102 change = y - finalMaxy;
3103 if (change >= SPAN_REALLOC)
3104 change += SPAN_REALLOC;
3106 change = SPAN_REALLOC;
3107 newSize = finalSize + change;
3108 newSpans = (struct finalSpan **) g_malloc
3109 (newSize * sizeof (struct finalSpan *));
3111 return (struct finalSpan **)NULL;
3112 newMiny = finalMiny;
3113 newMaxy = finalMaxy;
3115 newMiny = finalMiny - change;
3117 newMaxy = finalMaxy + change;
3119 g_memmove(((char *) newSpans) + (finalMiny-newMiny) * sizeof (struct finalSpan *),
3120 (char *) finalSpans,
3121 finalSize * sizeof (struct finalSpan *));
3122 g_free (finalSpans);
3124 if ((i = finalMiny - newMiny) > 0)
3125 memset ((char *)newSpans, 0, i * sizeof (struct finalSpan *));
3126 if ((i = newMaxy - finalMaxy) > 0)
3127 memset ((char *)(newSpans + newSize - i), 0,
3128 i * sizeof (struct finalSpan *));
3129 finalSpans = newSpans;
3130 finalMaxy = newMaxy;
3131 finalMiny = newMiny;
3132 finalSize = newSize;
3134 return &finalSpans[y - finalMiny];
3138 newFinalSpan (y, xmin, xmax)
3140 register int xmin, xmax;
3142 register struct finalSpan *x;
3143 register struct finalSpan **f;
3144 struct finalSpan *oldx;
3145 struct finalSpan *prev;
3153 for (x = *f; x; x=x->next) {
3158 if (x->min <= xmax && xmin <= x->max) {
3160 oldx->min = MIN (x->min, xmin);
3161 oldx->max = MAX (x->max, xmax);
3163 prev->next = x->next;
3168 x->min = MIN (x->min, xmin);
3169 x->max = MAX (x->max, xmax);
3182 x = allocFinalSpan ();
3195 mirrorSppPoint (quadrant, sppPoint)
3197 SppPointPtr sppPoint;
3203 sppPoint->x = -sppPoint->x;
3206 sppPoint->x = -sppPoint->x;
3207 sppPoint->y = -sppPoint->y;
3210 sppPoint->y = -sppPoint->y;
3214 * and translate to X coordinate system
3216 sppPoint->y = -sppPoint->y;
3220 * split an arc into pieces which are scan-converted
3221 * in the first-quadrant and mirrored into position.
3222 * This is necessary as the scan-conversion code can
3223 * only deal with arcs completely contained in the
3228 drawArc (miArc *tarc, int l, int a0, int a1, miArcFacePtr right, miArcFacePtr left)
3229 /* miArcFacePtr right, left; */ /* save end line points */
3232 struct accelerators acc;
3233 int startq, endq, curq;
3234 int rightq, leftq, righta, lefta;
3235 miArcFacePtr passRight, passLeft;
3240 } band[5], sweep[20];
3241 int bandno, sweepno;
3243 int flipRight = 0, flipLeft = 0;
3245 miArcSpanData *spdata;
3248 spdata = miComputeWideEllipse(l, tarc, &mustFree);
3254 startq = a0 / (90 * 64);
3258 endq = (a1-1) / (90 * 64);
3270 q1 = MIN (a1, 90 * 64);
3273 if (curq == startq && a0 == q0 && rightq < 0) {
3277 if (curq == endq && a1 == q1) {
3286 q0 = 180 * 64 - MIN (a1, 180 * 64);
3290 q1 = 180 * 64 - MAX (a0, 90 * 64);
3291 if (curq == startq && 180 * 64 - a0 == q1) {
3295 if (curq == endq && 180 * 64 - a1 == q0) {
3304 q0 = MAX (a0, 180 * 64) - 180 * 64;
3308 q1 = MIN (a1, 270 * 64) - 180 * 64;
3309 if (curq == startq && a0 - 180*64 == q0) {
3313 if (curq == endq && a1 - 180 * 64 == q1) {
3322 q0 = 360 * 64 - MIN (a1, 360 * 64);
3323 q1 = 360 * 64 - MAX (a0, 270 * 64);
3324 if (curq == startq && 360 * 64 - a0 == q1) {
3328 if (curq == endq && 360 * 64 - a1 == q0) {
3334 band[bandno].a0 = q0;
3335 band[bandno].a1 = q1;
3336 band[bandno].mask = 1 << curq;
3353 * find left-most point
3355 for (i = 0; i < bandno; i++)
3356 if (band[i].a0 <= q0) {
3359 mask = band[i].mask;
3364 * locate next point of change
3366 for (i = 0; i < bandno; i++)
3367 if (!(mask & band[i].mask)) {
3368 if (band[i].a0 == q0) {
3369 if (band[i].a1 < q1)
3371 mask |= band[i].mask;
3372 } else if (band[i].a0 < q1)
3376 * create a new sweep
3378 sweep[sweepno].a0 = q0;
3379 sweep[sweepno].a1 = q1;
3380 sweep[sweepno].mask = mask;
3383 * subtract the sweep from the affected bands
3385 for (i = 0; i < bandno; i++)
3386 if (band[i].a0 == q0) {
3389 * check if this band is empty
3391 if (band[i].a0 == band[i].a1)
3392 band[i].a1 = band[i].a0 = 90 * 64 + 1;
3395 computeAcc (tarc, l, &def, &acc);
3396 for (j = 0; j < sweepno; j++) {
3397 mask = sweep[j].mask;
3398 passRight = passLeft = 0;
3399 if (mask & (1 << rightq)) {
3400 if (sweep[j].a0 == righta)
3402 else if (sweep[j].a1 == righta) {
3407 if (mask & (1 << leftq)) {
3408 if (sweep[j].a1 == lefta)
3414 else if (sweep[j].a0 == lefta) {
3421 drawQuadrant (&def, &acc, sweep[j].a0, sweep[j].a1, mask,
3422 passRight, passLeft, spdata);
3425 * when copyEnd is set, both ends of the arc were computed
3426 * at the same time; drawQuadrant only takes one end though,
3427 * so the left end will be the only one holding the data. Copy
3433 * mirror the coordinates generated for the
3437 mirrorSppPoint (rightq, &right->clock);
3438 mirrorSppPoint (rightq, &right->center);
3439 mirrorSppPoint (rightq, &right->counterClock);
3443 temp = right->clock;
3444 right->clock = right->counterClock;
3445 right->counterClock = temp;
3449 mirrorSppPoint (leftq, &left->counterClock);
3450 mirrorSppPoint (leftq, &left->center);
3451 mirrorSppPoint (leftq, &left->clock);
3456 left->clock = left->counterClock;
3457 left->counterClock = temp;
3465 drawQuadrant (def, acc, a0, a1, mask, right, left, spdata)
3466 struct arc_def *def;
3467 struct accelerators *acc;
3470 miArcFacePtr right, left;
3471 miArcSpanData *spdata;
3473 struct arc_bound bound;
3479 def->a0 = ((double) a0) / 64.0;
3480 def->a1 = ((double) a1) / 64.0;
3481 computeBound (def, &bound, acc, right, left);
3482 yy = bound.inner.min;
3483 if (bound.outer.min < yy)
3484 yy = bound.outer.min;
3485 miny = ICEIL(yy - acc->fromIntY);
3486 yy = bound.inner.max;
3487 if (bound.outer.max > yy)
3488 yy = bound.outer.max;
3489 maxy = floor(yy - acc->fromIntY);
3491 span = spdata->spans;
3494 if (a1 == 90 * 64 && (mask & 1))
3495 newFinalSpan (acc->yorgu - y - 1, acc->xorg, acc->xorg + 1);
3498 for (n = spdata->count1; --n >= 0; )
3504 span->lx, -span->lx, 0, span->lx + span->lw,
3505 def, &bound, acc, mask);
3506 if (span->rw + span->rx)
3507 tailSpan (y, -span->rw, -span->rx, def, &bound, acc, mask);
3517 arcSpan (y, 0, 0, 0, 1, def, &bound, acc, mask & 0xc);
3519 for (n = spdata->count2; --n >= 0; )
3524 arcSpan (y, span->lx, span->lw, span->rx, span->rw,
3525 def, &bound, acc, mask);
3529 if (spdata->bot && miny <= y && y <= maxy)
3534 if (span->rw <= 0) {
3535 arcSpan0 (span->lx, -span->lx, 0, span->lx + span->lw,
3536 def, &bound, acc, n);
3537 if (span->rw + span->rx)
3538 tailSpan (y, -span->rw, -span->rx, def, &bound, acc, n);
3541 arcSpan0 (span->lx, span->lw, span->rx, span->rw,
3542 def, &bound, acc, n);
3546 yy = y + acc->fromIntY;
3547 if (def->w == def->h) {
3548 xalt = def->w - def->l;
3549 x = -sqrt(xalt * xalt - yy * yy);
3551 x = tailX(yy, def, &bound, acc);
3552 if (acc->left.valid && boundedLe (yy, bound.left)) {
3553 xalt = intersectLine (yy, acc->left);
3557 if (acc->right.valid && boundedLe (yy, bound.right)) {
3558 xalt = intersectLine (yy, acc->right);
3564 ICEIL(acc->fromIntX - x), 0,
3565 ICEIL(acc->fromIntX + x), 0,
3566 def, &bound, acc, mask);