diff options
Diffstat (limited to 'xorg-server/mi/miarc.c')
| -rw-r--r-- | xorg-server/mi/miarc.c | 244 |
1 files changed, 217 insertions, 27 deletions
diff --git a/xorg-server/mi/miarc.c b/xorg-server/mi/miarc.c index e55108a44..e8bc87e3e 100644 --- a/xorg-server/mi/miarc.c +++ b/xorg-server/mi/miarc.c @@ -26,13 +26,13 @@ Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. All Rights Reserved -Permission to use, copy, modify, and distribute this software and its -documentation for any purpose and without fee is hereby granted, +Permission to use, copy, modify, and distribute this software and its +documentation for any purpose and without fee is hereby granted, provided that the above copyright notice appear in all copies and that -both that copyright notice and this permission notice appear in +both that copyright notice and this permission notice appear in supporting documentation, and that the name of Digital not be used in advertising or publicity pertaining to distribution of the -software without specific, written prior permission. +software without specific, written prior permission. DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL @@ -63,6 +63,22 @@ SOFTWARE. #include "mifillarc.h" #include <X11/Xfuncproto.h> +#define EPSILON 0.000001 +#define ISEQUAL(a,b) (fabs((a) - (b)) <= EPSILON) +#define UNEQUAL(a,b) (fabs((a) - (b)) > EPSILON) +#define PTISEQUAL(a,b) (ISEQUAL(a.x,b.x) && ISEQUAL(a.y,b.y)) +#define SQSECANT 108.856472512142 /* 1/sin^2(11/2) - for 11o miter cutoff */ + +/* Point with sub-pixel positioning. */ +typedef struct _SppPoint { + double x, y; +} SppPointRec, *SppPointPtr; + +typedef struct _SppArc { + double x, y, width, height; + double angle1, angle2; +} SppArcRec, *SppArcPtr; + static double miDsin(double a); static double miDcos(double a); static double miDasin(double v); @@ -82,7 +98,7 @@ cbrt(double x) /* * some interesting sematic interpretation of the protocol: * - * Self intersecting arcs (i.e. those spanning 360 degrees) + * Self intersecting arcs (i.e. those spanning 360 degrees) * never join with other arcs, and are drawn without caps * (unless on/off dashed, in which case each dash segment * is capped, except when the last segment meets the @@ -99,21 +115,6 @@ cbrt(double x) * */ -#undef max -#undef min - -_X_INLINE static int -max(const int x, const int y) -{ - return x > y ? x : y; -} - -_X_INLINE static int -min(const int x, const int y) -{ - return x < y ? x : y; -} - struct bound { double min, max; }; @@ -353,7 +354,7 @@ of the two quadratics y^2 + ((b+A)/2)y + (Z + (bZ - d)/A) = 0 -where +where A = +/- sqrt(8Z + b^2 - 4c) b, c, d are the cubic, quadratic, and linear coefficients of the quartic @@ -1110,6 +1111,195 @@ miWideArc(DrawablePtr pDraw, GCPtr pGC, int narcs, xArc * parcs) } } +/* Find the index of the point with the smallest y.also return the + * smallest and largest y */ +static int +GetFPolyYBounds(SppPointPtr pts, int n, double yFtrans, int *by, int *ty) +{ + SppPointPtr ptMin; + double ymin, ymax; + SppPointPtr ptsStart = pts; + + ptMin = pts; + ymin = ymax = (pts++)->y; + + while (--n > 0) { + if (pts->y < ymin) { + ptMin = pts; + ymin = pts->y; + } + if (pts->y > ymax) + ymax = pts->y; + + pts++; + } + + *by = ICEIL(ymin + yFtrans); + *ty = ICEIL(ymax + yFtrans - 1); + return ptMin - ptsStart; +} + +/* + * miFillSppPoly written by Todd Newman; April. 1987. + * + * Fill a convex polygon. If the given polygon + * is not convex, then the result is undefined. + * The algorithm is to order the edges from smallest + * y to largest by partitioning the array into a left + * edge list and a right edge list. The algorithm used + * to traverse each edge is digital differencing analyzer + * line algorithm with y as the major axis. There's some funny linear + * interpolation involved because of the subpixel postioning. + */ +static void +miFillSppPoly(DrawablePtr dst, GCPtr pgc, int count, /* number of points */ + SppPointPtr ptsIn, /* the points */ + int xTrans, int yTrans, /* Translate each point by this */ + double xFtrans, double yFtrans /* translate before conversion + by this amount. This provides + a mechanism to match rounding + errors with any shape that must + meet the polygon exactly. + */ + ) +{ + double xl = 0.0, xr = 0.0, /* x vals of left and right edges */ + ml = 0.0, /* left edge slope */ + mr = 0.0, /* right edge slope */ + dy, /* delta y */ + i; /* loop counter */ + int y, /* current scanline */ + j, imin, /* index of vertex with smallest y */ + ymin, /* y-extents of polygon */ + ymax, *width, *FirstWidth, /* output buffer */ + *Marked; /* set if this vertex has been used */ + int left, right, /* indices to first endpoints */ + nextleft, nextright; /* indices to second endpoints */ + DDXPointPtr ptsOut, FirstPoint; /* output buffer */ + + if (pgc->miTranslate) { + xTrans += dst->x; + yTrans += dst->y; + } + + imin = GetFPolyYBounds(ptsIn, count, yFtrans, &ymin, &ymax); + + y = ymax - ymin + 1; + if ((count < 3) || (y <= 0)) + return; + ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * y); + width = FirstWidth = malloc(sizeof(int) * y); + Marked = malloc(sizeof(int) * count); + + if (!ptsOut || !width || !Marked) { + free(Marked); + free(width); + free(ptsOut); + return; + } + + for (j = 0; j < count; j++) + Marked[j] = 0; + nextleft = nextright = imin; + Marked[imin] = -1; + y = ICEIL(ptsIn[nextleft].y + yFtrans); + + /* + * loop through all edges of the polygon + */ + do { + /* add a left edge if we need to */ + if ((y > (ptsIn[nextleft].y + yFtrans) || + ISEQUAL(y, ptsIn[nextleft].y + yFtrans)) && + Marked[nextleft] != 1) { + Marked[nextleft]++; + left = nextleft++; + + /* find the next edge, considering the end conditions */ + if (nextleft >= count) + nextleft = 0; + + /* now compute the starting point and slope */ + dy = ptsIn[nextleft].y - ptsIn[left].y; + if (dy != 0.0) { + ml = (ptsIn[nextleft].x - ptsIn[left].x) / dy; + dy = y - (ptsIn[left].y + yFtrans); + xl = (ptsIn[left].x + xFtrans) + ml * max(dy, 0); + } + } + + /* add a right edge if we need to */ + if ((y > ptsIn[nextright].y + yFtrans) || + (ISEQUAL(y, ptsIn[nextright].y + yFtrans) + && Marked[nextright] != 1)) { + Marked[nextright]++; + right = nextright--; + + /* find the next edge, considering the end conditions */ + if (nextright < 0) + nextright = count - 1; + + /* now compute the starting point and slope */ + dy = ptsIn[nextright].y - ptsIn[right].y; + if (dy != 0.0) { + mr = (ptsIn[nextright].x - ptsIn[right].x) / dy; + dy = y - (ptsIn[right].y + yFtrans); + xr = (ptsIn[right].x + xFtrans) + mr * max(dy, 0); + } + } + + /* + * generate scans to fill while we still have + * a right edge as well as a left edge. + */ + i = (min(ptsIn[nextleft].y, ptsIn[nextright].y) + yFtrans) - y; + + if (i < EPSILON) { + if (Marked[nextleft] && Marked[nextright]) { + /* Arrgh, we're trapped! (no more points) + * Out, we've got to get out of here before this decadence saps + * our will completely! */ + break; + } + continue; + } + else { + j = (int) i; + if (!j) + j++; + } + while (j > 0) { + int cxl, cxr; + + ptsOut->y = (y) + yTrans; + + cxl = ICEIL(xl); + cxr = ICEIL(xr); + /* reverse the edges if necessary */ + if (xl < xr) { + *(width++) = cxr - cxl; + (ptsOut++)->x = cxl + xTrans; + } + else { + *(width++) = cxl - cxr; + (ptsOut++)->x = cxr + xTrans; + } + y++; + + /* increment down the edges */ + xl += ml; + xr += mr; + j--; + } + } while (y <= ymax); + + /* Finally, fill the spans we've collected */ + (*pgc->ops->FillSpans) (dst, pgc, + ptsOut - FirstPoint, FirstPoint, FirstWidth, 1); + free(Marked); + free(FirstWidth); + free(FirstPoint); +} static double angleBetween(SppPointRec center, SppPointRec point1, SppPointRec point2) { @@ -1291,7 +1481,7 @@ miArcCap(DrawablePtr pDraw, /* MIROUNDCAP -- a private helper function * Put Rounded cap on end. pCenter is the center of this end of the line * pEnd is the center of the other end of the line. pCorner is one of the - * two corners at this end of the line. + * two corners at this end of the line. * NOTE: pOtherCorner must be counter-clockwise from pCorner. */ /*ARGSUSED*/ static void @@ -1443,7 +1633,7 @@ miDatan2(double dy, double dx) * array. (For example, if we want to leave a spare point to make sectors * instead of segments.) So we pass in the malloc()ed chunk that contains the * array and an index saying where we should start stashing the points. - * If there isn't an array already, we just pass in a null pointer and + * If there isn't an array already, we just pass in a null pointer and * count on realloc() to handle the null pointer correctly. */ static int @@ -1462,7 +1652,7 @@ miGetArcPts(SppArcPtr parc, /* points to an arc */ SppPointPtr poly; /* The spec says that positive angles indicate counterclockwise motion. - * Given our coordinate system (with 0,0 in the upper left corner), + * Given our coordinate system (with 0,0 in the upper left corner), * the screen appears flipped in Y. The easiest fix is to negate the * angles given */ @@ -2548,7 +2738,7 @@ computeBound(struct arc_def *def, } /* - * this section computes the x value of the span at y + * this section computes the x value of the span at y * intersected with the specified face of the ellipse. * * this is the min/max X value over the set of normal @@ -2561,7 +2751,7 @@ computeBound(struct arc_def *def, * * compute the derivative with-respect-to ellipse_y and solve * for zero: - * + * * (w^2 - h^2) ellipse_y^3 + h^4 y * 0 = - ---------------------------------- * h w ellipse_y^2 sqrt (h^2 - ellipse_y^2) @@ -2588,7 +2778,7 @@ computeBound(struct arc_def *def, * * or (to use accelerators), * - * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2) + * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2) * */ |