aboutsummaryrefslogtreecommitdiff
path: root/xorg-server/mi/miarc.c
diff options
context:
space:
mode:
Diffstat (limited to 'xorg-server/mi/miarc.c')
-rwxr-xr-x[-rw-r--r--]xorg-server/mi/miarc.c244
1 files changed, 217 insertions, 27 deletions
diff --git a/xorg-server/mi/miarc.c b/xorg-server/mi/miarc.c
index e0f09d243..fa7befac1 100644..100755
--- 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
@@ -68,6 +68,22 @@ SOFTWARE.
#define HAVE_CBRT
#endif
+#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);
@@ -87,7 +103,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
@@ -104,21 +120,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;
};
@@ -358,7 +359,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
@@ -1115,6 +1116,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)
{
@@ -1296,7 +1486,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
@@ -1448,7 +1638,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
@@ -1467,7 +1657,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 */
@@ -2553,7 +2743,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
@@ -2566,7 +2756,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)
@@ -2593,7 +2783,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)
*
*/