/* This file is part of the GNU libxmi package. Copyright (C) 1985, 1986, 1987, 1988, 1989, X Consortium. For an associated permission notice, see the accompanying file README-X. GNU enhancements Copyright (C) 1998, 1999, 2000, 2005, Free Software Foundation, Inc. The GNU libxmi package is free software. You may redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software foundation; either version 2, or (at your option) any later version. The GNU libxmi package is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with the GNU plotutils package; see the file COPYING. If not, write to the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor, Boston, MA 02110-1301, USA. */ #include "sys-defines.h" #include "extern.h" /* Original author: Keith Packard, MIT X Consortium. Hacked by Robert S. Maier, 1998-99. */ /* This module contains the miWideLine() and miWideDash() functions. They rasterize wide polylines (usually just called `wide lines'), either solid or dashed. Any wide line is treated as a polygon to be painted. (If it is dashed, each dash is treated as a polygon.) The painting follows libxmi's policy on painting of `edge' pixels, i.e., pixels that lie exactly on a boundary. A pixel is not painted if it lies on a `right' or `bottom' edge of a polygon. All painting goes through the low-level MI_PAINT_SPANS() macro. */ #include "xmi.h" #include "mi_spans.h" #include "mi_gc.h" #include "mi_api.h" #include "mi_widelin.h" /* undefine if hypot is available (it's X_OPEN, but not ANSI or POSIX) */ #define hypot(x, y) sqrt((x)*(x) + (y)*(y)) /* internal functions that do painting of pixels */ static void miFillPolyHelper (miPaintedSet *paintedSet, miPixel pixel, int y, unsigned int overall_height, PolyEdge *left, PolyEdge *right, int left_count, int right_count); static void miFillRectPolyHelper (miPaintedSet *paintedSet, miPixel pixel, int x, int y, unsigned int w, unsigned int h); static void miLineArc (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, LineFace *leftFace, LineFace *rightFace, double xorg, double yorg, bool isInt); static void miLineJoin (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, LineFace *pLeft, LineFace *pRight); static void miLineProjectingCap (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, const LineFace *face, bool isLeft, bool isInt); static void miWideDashSegment (miPaintedSet *paintedSet, const miGC *pGC, int *pDashNum, int *pDashIndex, int *pDashOffset, int x1, int y1, int x2, int y2, bool projectLeft, bool projectRight, LineFace *leftFace, LineFace *rightFace); static void miWideSegment (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, int x1, int y1, int x2, int y2, bool projectLeft, bool projectRight, LineFace *leftFace, LineFace *rightFace); /* internal functions that don't do painting of pixels */ static int miLineArcD (const miGC *pGC, double xorg, double yorg, miPoint *points, unsigned int *widths, PolyEdge *edge1, int edgey1, bool edgeleft1, PolyEdge *edge2, int edgey2, bool edgeleft2); static int miLineArcI (const miGC *pGC, int xorg, int yorg, miPoint *points, unsigned int *widths); static int miPolyBuildEdge (double x0, double y0, double k, int dx, int dy, int xi, int yi, bool left, PolyEdge *edge); static int miPolyBuildPoly (const PolyVertex *vertices, const PolySlope *slopes, int count, int xi, int yi, PolyEdge *left, PolyEdge *right, int *pnleft, int *pnright, unsigned int *h); static int miRoundCapClip (const LineFace *face, bool isInt, PolyEdge *edge, bool *leftEdge); static int miRoundJoinFace (const LineFace *face, PolyEdge *edge, bool *leftEdge); static void miRoundJoinClip (LineFace *pLeft, LineFace *pRight, PolyEdge *edge1, PolyEdge *edge2, int *y1, int *y2, bool *left1, bool *left2); /* Spans-based convex polygon filler. Paints a convex polygon, supplied as lists of `left' and `right' edges. Used for painting polygonal line caps and line joins. This implements libxmi's policy on painting `edge' pixels, i.e., pixels that lie exactly on the boundary of a polygon. A pixel is not painted if it lies on a `right' or `bottom' edge of the polygon. */ /* ARGS: y = starting y coor, overall_height = height of entire segment */ static void miFillPolyHelper (miPaintedSet *paintedSet, miPixel pixel, int y, unsigned int overall_height, PolyEdge *left, PolyEdge *right, int left_count, int right_count) { int left_x = 0, left_e = 0; int left_stepx = 0; int left_signdx = 0; int left_dy = 0, left_dx = 0; int right_x = 0, right_e = 0; int right_stepx = 0; int right_signdx = 0; int right_dy = 0, right_dx = 0; unsigned int left_height = 0, right_height = 0; miPoint *ppt; miPoint *pptInit = (miPoint *)NULL; unsigned int *pwidth; unsigned int *pwidthInit = (unsigned int *)NULL; pptInit = (miPoint *)mi_xmalloc(overall_height * sizeof(miPoint)); pwidthInit = (unsigned int *)mi_xmalloc(overall_height * sizeof(unsigned int)); ppt = pptInit; pwidth = pwidthInit; while ((left_count || left_height) && (right_count || right_height)) { unsigned int height; /* load fields from next left edge, right edge */ MIPOLYRELOADLEFT MIPOLYRELOADRIGHT height = UMIN (left_height, right_height); left_height -= height; right_height -= height; /* walk down to end of left or right edge, whichever comes first */ while (height--) { if (right_x >= left_x) /* generate a span (omitting point on right end, see above) */ { ppt->x = left_x; ppt->y = y; ppt++; *pwidth++ = (unsigned int)(right_x - left_x + 1); } y++; /* update left_x, right_x by stepping along left and right edges, using midpoint line algorithm */ MIPOLYSTEPLEFT MIPOLYSTEPRIGHT } } MI_PAINT_SPANS(paintedSet, pixel, ppt - pptInit, pptInit, pwidthInit) } /* Rectangle filler. Policy mentioned above (no painting of right or bottom edges) is followed. */ static void miFillRectPolyHelper (miPaintedSet *paintedSet, miPixel pixel, int x, int y, unsigned int w, unsigned int h) { miPoint *ppt, *pptInit; unsigned int *pwidth, *pwidthInit; pptInit = (miPoint *)mi_xmalloc (h * sizeof(miPoint)); pwidthInit = (unsigned int *)mi_xmalloc (h * sizeof(unsigned int)); ppt = pptInit; pwidth = pwidthInit; while (h--) { *pwidth++ = w; ppt->x = x; ppt->y = y; ppt++; y++; } MI_PAINT_SPANS(paintedSet, pixel, ppt - pptInit, pptInit, pwidthInit) } /* Build a single polygon edge (either a left edge or a right edge). I.e. compute integer edge data that can be used by the midpoint line algorithm. The edge will be traversed downward (on entry, dy != 0 is assumed). Returns starting value for y, i.e. integer y-value for top of edge. */ /* Supplied: an integer offset (xi,yi), the exact floating-point edge start (x0,y0), its (rational) slope dy/dx, and the quantity k = x0*dy-y0*dx, which is a measure of distance of (x0,y0) from the parallel line segment that passes through (0,0). k will be transformed into the initial value for e, the integer decision variable for the midpoint line algorithm. */ /* The integer edge data that are computed do not include the `height' field, i.e. the number of scanlines to process. */ /* ARGS: x0,y0 = starting point of edge (rel. to x1,y1) k = x0 * dy - y0 * dx dx,dy specify rational slope dy/dx xi,yi = integer offsets for coor system left = left edge, not right edge? edge = integer edge data, to be filled in */ /*ARGSUSED*/ static int miPolyBuildEdge (double x0, double y0, double k, int dx, int dy, int xi, int yi, bool left, PolyEdge *edge) { int x, y, e; int xady; /* make dy positive, since edge will be traversed downward */ if (dy < 0) { dy = -dy; dx = -dx; k = -k; } #if 0 { double realk, kerror; realk = x0 * dy - y0 * dx; kerror = fabs (realk - k); if (kerror > .1) printf ("realk: %g\t k: %g\n", realk, k); } #endif /* integer starting value for y: round up the floating-point value */ y = ICEIL (y0); /* work out integer starting value for x */ xady = ICEIL (k) + y * dx; if (xady <= 0) x = - (-xady / dy) - 1; else x = (xady - 1) / dy; /* start working out initial value of decision variable */ e = xady - x * dy; /* i.e. ICEIL(k) - (x * dy - y * dx) */ /* work out optional and non-optional x increment, for algorithm */ if (dx >= 0) { edge->signdx = 1; /* optional step */ edge->stepx = dx / dy; /* non-optional step, 0 if dxdx = dx % dy; } else { edge->signdx = -1; /* optional step */ edge->stepx = - (-dx / dy); /* non-optional step, 0 if dxdx = -dx % dy; e = dy - e + 1; } edge->dy = dy; edge->x = x + (left == true ? 1 : 0) + xi; /* starting value for x */ edge->e = e - dy; /* bias: initial value for e */ /* return integer starting value for y, i.e. top of edge */ return y + yi; } /* add incr to v, cyclically; always stay in range 0..max */ #define StepAround(v, incr, max) (((v) + (incr) < 0) ? (max - 1) : ((v) + (incr) == max) ? 0 : ((v) + (incr))) /* Build lists of right and left polygon edges, from an array of vertex coordinates (floating-point), a precomputed array of PolySlopes (including a `k' value for each edge), and an integer offset vector. Also return overall vertical range and top (starting) y value. */ /* ARGS: xi,yi = integer offset for polygon */ static int miPolyBuildPoly (const PolyVertex *vertices, const PolySlope *slopes, int count, int xi, int yi, PolyEdge *left, PolyEdge *right, int *pnleft, int *pnright, unsigned int *h) { int top, bottom; double miny, maxy; int i; int j; int clockwise; int slopeoff; int s; int nright, nleft; int y, lasty = 0, bottomy, topy = 0; /* compute min, max y values for polygon (floating-point); also location of corresponding vertices in vertex array */ maxy = miny = vertices[0].y; bottom = top = 0; for (i = 1; i < count; i++) { if (vertices[i].y < miny) { top = i; miny = vertices[i].y; } if (vertices[i].y >= maxy) { bottom = i; maxy = vertices[i].y; } } /* compute integer y-value for bottom of polygon (round up) */ bottomy = ICEIL (maxy) + yi; /* determine whether should go `clockwise' or `counterclockwise' to move down the right side of the polygon */ i = top; j = StepAround (top, -1, count); clockwise = 1; slopeoff = 0; if (slopes[j].dy * slopes[i].dx > slopes[i].dy * slopes[j].dx) { clockwise = -1; slopeoff = -1; } /* step around right side of polygon from top to bottom, building array of `right' edges (horizontal edges are ignored) */ i = top; s = StepAround (top, slopeoff, count); nright = 0; while (i != bottom) { if (slopes[s].dy != 0) { y = miPolyBuildEdge (vertices[i].x, vertices[i].y, slopes[s].k, slopes[s].dx, slopes[s].dy, xi, yi, false, &right[nright]); if (nright != 0) right[nright-1].height = y - lasty; else /* y is top of first edge */ topy = y; nright++; lasty = y; } i = StepAround (i, clockwise, count); s = StepAround (s, clockwise, count); } if (nright != 0) right[nright-1].height = bottomy - lasty; /* step around left side of polygon from top to bottom, building array of `left' edges (horizontal edges are ignored) */ if (slopeoff == 0) slopeoff = -1; else slopeoff = 0; i = top; s = StepAround (top, slopeoff, count); nleft = 0; while (i != bottom) { if (slopes[s].dy != 0) { y = miPolyBuildEdge (vertices[i].x, vertices[i].y, slopes[s].k, slopes[s].dx, slopes[s].dy, xi, yi, true, &left[nleft]); if (nleft != 0) left[nleft-1].height = y - lasty; nleft++; lasty = y; } i = StepAround (i, -clockwise, count); s = StepAround (s, -clockwise, count); } if (nleft != 0) left[nleft-1].height = bottomy - lasty; /* return number of left-side and right-side edges; also height (vertical range, an unsigned int) and the vertical location of the top vertex (an integer) */ *pnleft = nleft; *pnright = nright; *h = bottomy - topy; return topy; } /* Paint all types of line join: round/miter/bevel/triangular. Called by both miWideLine() and miWideDash(). Left and right line faces are supplied, each with its own value of k. They may be modified. */ static void miLineJoin (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, LineFace *pLeft, LineFace *pRight) { double mx = 0.0, my = 0.0; int denom = 0; /* avoid compiler warnings */ PolyVertex vertices[4]; PolySlope slopes[4]; int edgecount; PolyEdge left[4], right[4]; int nleft, nright; int y; unsigned int height; bool swapslopes; int joinStyle = (int)pGC->joinStyle; int lw = (int)(pGC->lineWidth); if (joinStyle == (int)MI_JOIN_ROUND) { /* invoke miLineArc to fill the round join, isInt = true */ miLineArc (paintedSet, pixel, pGC, pLeft, pRight, (double)0.0, (double)0.0, true); return; } denom = - pLeft->dx * pRight->dy + pRight->dx * pLeft->dy; if (denom == 0) return; /* no join to draw */ /* Now must handle cases where line join is a small polygon to be filled; specify its vertices clockwise. */ /* swap slopes if cross product of line faces has wrong sign */ if (denom > 0) { swapslopes = false; pLeft->xa = -pLeft->xa; pLeft->ya = -pLeft->ya; pLeft->dx = -pLeft->dx; pLeft->dy = -pLeft->dy; } else { swapslopes = true; pRight->xa = -pRight->xa; pRight->ya = -pRight->ya; pRight->dx = -pRight->dx; pRight->dy = -pRight->dy; } /* vertex #0 is at the right end of the right face */ vertices[0].x = pRight->xa; vertices[0].y = pRight->ya; slopes[0].dx = -pRight->dy; slopes[0].dy = pRight->dx; slopes[0].k = 0; /* vertex #1 is the nominal join point (i.e. halfway across both the right face and the left face) */ vertices[1].x = 0; vertices[1].y = 0; slopes[1].dx = pLeft->dy; slopes[1].dy = -pLeft->dx; slopes[1].k = 0; /* vertex #2 is at the left end of the left face */ vertices[2].x = pLeft->xa; vertices[2].y = pLeft->ya; if (joinStyle == (int)MI_JOIN_MITER) { double miterlimit = pGC->miterLimit; /* compute vertex (mx,my) of miter quadrilateral */ my = (pLeft->dy * (pRight->xa * pRight->dy - pRight->ya * pRight->dx) - pRight->dy * (pLeft->xa * pLeft->dy - pLeft->ya * pLeft->dx )) / (double) denom; if (pLeft->dy != 0) mx = pLeft->xa + (my - pLeft->ya) * (double) pLeft->dx / (double) pLeft->dy; else mx = pRight->xa + (my - pRight->ya) * (double) pRight->dx / (double) pRight->dy; /* if miter limit violated, switch to bevelled join */ if ((mx * mx + my * my) * 4 > miterlimit * miterlimit * lw * lw) joinStyle = (int)MI_JOIN_BEVEL; } switch ((int)joinStyle) { double scale, dx, dy, adx, ady; case (int)MI_JOIN_MITER: default: /* join by adding a quadrilateral */ edgecount = 4; slopes[2].dx = pLeft->dx; slopes[2].dy = pLeft->dy; slopes[2].k = pLeft->k; if (swapslopes) { slopes[2].dx = -slopes[2].dx; slopes[2].dy = -slopes[2].dy; slopes[2].k = -slopes[2].k; } /* vertex #3 is miter vertex (mx,my) */ vertices[3].x = mx; vertices[3].y = my; slopes[3].dx = pRight->dx; slopes[3].dy = pRight->dy; slopes[3].k = pRight->k; if (swapslopes) { slopes[3].dx = -slopes[3].dx; slopes[3].dy = -slopes[3].dy; slopes[3].k = -slopes[3].k; } break; case (int)MI_JOIN_BEVEL: /* join by adding a triangle */ { PolyVertex midpoint; edgecount = 3; /* third edge of triangle will pass through midpoint */ midpoint.x = 0.5 * (pLeft->xa + pRight->xa); midpoint.y = 0.5 * (pLeft->ya + pRight->ya); /* vector along third edge of triangle */ dx = pRight->xa - pLeft->xa; dy = pRight->ya - pLeft->ya; /* compute scale = max(|dx|,|dy|) */ adx = dx; ady = dy; if (adx < 0) adx = -adx; if (ady < 0) ady = -ady; scale = ady; if (adx > ady) scale = adx; /* use integer dx, dy in range -65536..65536 */ slopes[2].dx = (int)((dx * 65536) / scale); slopes[2].dy = (int)((dy * 65536) / scale); slopes[2].k = midpoint.x * slopes[2].dy - midpoint.y * slopes[2].dx; } break; case (int)MI_JOIN_TRIANGULAR: /* join by adding a stubby quadrilateral */ { PolyVertex midpoint, newpoint; double mid2, mid, dx2, dy2, dx3, dy3; edgecount = 4; /* compute additional vertex, offset by linewidth/2 */ midpoint.x = 0.5 * (pLeft->xa + pRight->xa); midpoint.y = 0.5 * (pLeft->ya + pRight->ya); mid2 = midpoint.x * midpoint.x + midpoint.y * midpoint.y; mid = sqrt (mid2); newpoint.x = 0.5 * lw * midpoint.x / mid; newpoint.y = 0.5 * lw * midpoint.y / mid; vertices[3] = newpoint; /* offset from vertices[2] to vertices[3] */ dx2 = vertices[3].x - vertices[2].x; dy2 = vertices[3].y - vertices[2].y; /* offset from vertices[3] back to vertices[0] */ dx3 = vertices[0].x - vertices[3].x; dy3 = vertices[0].y - vertices[3].y; /* compute scale = max(|dx|,|dy|), where (dx,dy) is offset between the two corners, i.e. vertices[0] and vertices[2] */ dx = pRight->xa - pLeft->xa; dy = pRight->ya - pLeft->ya; adx = dx; ady = dy; if (adx < 0) adx = -adx; if (ady < 0) ady = -ady; scale = ady; if (adx > ady) scale = adx; /* use integer dx, dy in range -65536..65536 */ slopes[2].dx = (int)((dx2 * 65536) / scale); slopes[2].dy = (int)((dy2 * 65536) / scale); slopes[2].k = newpoint.x * slopes[2].dy - newpoint.y * slopes[2].dx; /* use integer dx, dy in range -65536..65536 */ slopes[3].dx = (int)((dx3 * 65536) / scale); slopes[3].dy = (int)((dy3 * 65536) / scale); slopes[3].k = newpoint.x * slopes[3].dy - newpoint.y * slopes[3].dx; } break; } /* end of switch */ /* compute lists of left and right edges for the small polygon, using the just-computed slopes array */ y = miPolyBuildPoly (vertices, slopes, edgecount, pLeft->x, pLeft->y, left, right, &nleft, &nright, &height); /* fill the small polygon */ miFillPolyHelper (paintedSet, pixel, y, height, left, right, nleft, nright); } /* Paint either (1) a round cap on a line face or (2) a pie-wedge between two line faces. Used for round capping and round joining respectively. One or two line faces are supplied. They may be modified. */ static void miLineArc (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, LineFace *leftFace, LineFace *rightFace, double xorg, double yorg, bool isInt) { miPoint *points; unsigned int *widths; int xorgi = 0, yorgi = 0; int n; PolyEdge edge1, edge2; int edgey1, edgey2; bool edgeleft1, edgeleft2; if (isInt) /* in integer case, take (xorgi,yorgi) from face; otherwise (0,0) */ { xorgi = leftFace ? leftFace->x : rightFace->x; yorgi = leftFace ? leftFace->y : rightFace->y; } edgey1 = INT_MAX; edgey2 = INT_MAX; edge1.x = 0; /* not used, keep memory checkers happy */ edge1.dy = -1; edge2.x = 0; /* not used, keep memory checkers happy */ edge2.dy = -1; edgeleft1 = false; edgeleft2 = false; if ((pGC->lineStyle != (int)MI_LINE_SOLID || pGC->lineWidth > 2) && ((pGC->capStyle == (int)MI_CAP_ROUND && pGC->joinStyle != (int)MI_JOIN_ROUND) || (pGC->joinStyle == (int)MI_JOIN_ROUND && pGC->capStyle == (int)MI_CAP_BUTT))) /* construct clipping edges from the passed line faces (otherwise, ignore them; will just draw a disk) */ { if (isInt) { xorg = (double) xorgi; yorg = (double) yorgi; } if (leftFace && rightFace) /* have two faces, so construct clipping edges for pie wedge */ miRoundJoinClip (leftFace, rightFace, &edge1, &edge2, &edgey1, &edgey2, &edgeleft1, &edgeleft2); else if (leftFace) /* will draw half-disk on left face, so construct clipping edge */ edgey1 = miRoundCapClip (leftFace, isInt, &edge1, &edgeleft1); else if (rightFace) /* will draw half-disk on right face, so construct clipping edge */ edgey2 = miRoundCapClip (rightFace, isInt, &edge2, &edgeleft2); /* due to clipping, switch to using floating-point coordinates */ isInt = false; } points = (miPoint *)mi_xmalloc(sizeof(miPoint) * pGC->lineWidth); widths = (unsigned int *)mi_xmalloc(sizeof(unsigned int) * pGC->lineWidth); /* construct a Spans by calling integer or floating point routine */ if (isInt) /* integer routine, no clipping: just draw a disk */ n = miLineArcI (pGC, xorgi, yorgi, points, widths); else /* call floating point routine, supporting clipping by edge(s) */ n = miLineArcD (pGC, xorg, yorg, points, widths, &edge1, edgey1, edgeleft1, &edge2, edgey2, edgeleft2); MI_PAINT_SPANS(paintedSet, pixel, n, points, widths) } /* Draw a filled disk, of diameter equal to the linewidth, as a Spans. This is used for round caps or round joins, if the clipping by one or two edges can be ignored. Integer coordinates only are used. Returns number of spans in the Spans. */ static int miLineArcI (const miGC *pGC, int xorg, int yorg, miPoint *points, unsigned int *widths) { miPoint *tpts, *bpts; unsigned int *twids, *bwids; int x, y, e, ex; int slw; tpts = points; twids = widths; slw = (int)(pGC->lineWidth); if (slw == 1) /* `disk' is a single pixel */ { tpts->x = xorg; tpts->y = yorg; *twids = 1; return 1; } /* otherwise, draw the disk scanline by scanline */ bpts = tpts + slw; bwids = twids + slw; y = (slw >> 1) + 1; if (slw & 1) e = - ((y << 2) + 3); else e = - (y << 3); ex = -4; x = 0; while (y) { e += (y << 3) - 4; while (e >= 0) { x++; e += (ex = -((x << 3) + 4)); } y--; slw = (x << 1) + 1; if ((e == ex) && (slw > 1)) slw--; tpts->x = xorg - x; tpts->y = yorg - y; tpts++; *twids++ = slw; if ((y != 0) && ((slw > 1) || (e != ex))) { bpts--; bpts->x = xorg - x; bpts->y = yorg + y; *--bwids = slw; } } /* return linewidth (no. of spans in the Spans) */ return (int)(pGC->lineWidth); } #define CLIPSTEPEDGE(edgey,edge,edgeleft) \ if (ybase == edgey) \ { \ if (edgeleft) \ { \ if (edge->x > xcl) \ xcl = edge->x; \ } \ else \ { \ if (edge->x < xcr) \ xcr = edge->x; \ } \ edgey++; \ edge->x += edge->stepx; \ edge->e += edge->dx; \ if (edge->e > 0) \ { \ edge->x += edge->signdx; \ edge->e -= edge->dy; \ } \ } /* Draw as a Spans a filled disk of diameter equal to the linewidth, paying attention to one or two clipping edges. This is used for round caps and round joins, respectively (it respectively yields a half-disk or a pie wedge). Floating point coordinates are used. Returns number of spans in the Spans. The clipping edges may be modified. */ static int miLineArcD (const miGC *pGC, double xorg, double yorg, miPoint *points, unsigned int *widths, PolyEdge *edge1, int edgey1, bool edgeleft1, PolyEdge *edge2, int edgey2, bool edgeleft2) { miPoint *pts; unsigned int *wids; double radius, x0, y0, el, er, yk, xlk, xrk, k; int xbase, ybase, y, boty, xl, xr, xcl, xcr; int ymin, ymax; bool edge1IsMin, edge2IsMin; int ymin1, ymin2; pts = points; wids = widths; xbase = (int)(floor(xorg)); x0 = xorg - xbase; ybase = ICEIL (yorg); y0 = yorg - ybase; xlk = x0 + x0 + 1.0; xrk = x0 + x0 - 1.0; yk = y0 + y0 - 1.0; radius = 0.5 * ((double)pGC->lineWidth); y = (int)(floor(radius - y0 + 1.0)); ybase -= y; ymin = ybase; ymax = INT_MAX; edge1IsMin = false; ymin1 = edgey1; if (edge1->dy >= 0) { if (!edge1->dy) { if (edgeleft1) edge1IsMin = true; else ymax = edgey1; edgey1 = INT_MAX; } else { if ((edge1->signdx < 0) == edgeleft1) edge1IsMin = true; } } edge2IsMin = false; ymin2 = edgey2; if (edge2->dy >= 0) { if (!edge2->dy) { if (edgeleft2) edge2IsMin = true; else ymax = edgey2; edgey2 = INT_MAX; } else { if ((edge2->signdx < 0) == edgeleft2) edge2IsMin = true; } } if (edge1IsMin) { ymin = ymin1; if (edge2IsMin && ymin1 > ymin2) ymin = ymin2; } else if (edge2IsMin) ymin = ymin2; el = radius * radius - ((y + y0) * (y + y0)) - (x0 * x0); er = el + xrk; xl = 1; xr = 0; if (x0 < 0.5) { xl = 0; el -= xlk; } boty = (y0 < -0.5) ? 1 : 0; if (ybase + y - boty > ymax) boty = ymax - ybase - y; while (y > boty) { k = (y << 1) + yk; er += k; while (er > 0.0) { xr++; er += xrk - (xr << 1); } el += k; while (el >= 0.0) { xl--; el += (xl << 1) - xlk; } y--; ybase++; if (ybase < ymin) continue; xcl = xl + xbase; xcr = xr + xbase; CLIPSTEPEDGE(edgey1, edge1, edgeleft1); CLIPSTEPEDGE(edgey2, edge2, edgeleft2); if (xcr >= xcl) { pts->x = xcl; pts->y = ybase; pts++; *wids++ = (unsigned int)(xcr - xcl + 1); } } er = xrk - (xr << 1) - er; el = (xl << 1) - xlk - el; boty = (int)(floor(-y0 - radius + 1.0)); if (ybase + y - boty > ymax) boty = ymax - ybase - y; while (y > boty) { k = (y << 1) + yk; er -= k; while ((er >= 0.0) && (xr >= 0)) { xr--; er += xrk - (xr << 1); } el -= k; while ((el > 0.0) && (xl <= 0)) { xl++; el += (xl << 1) - xlk; } y--; ybase++; if (ybase < ymin) continue; xcl = xl + xbase; xcr = xr + xbase; CLIPSTEPEDGE(edgey1, edge1, edgeleft1); CLIPSTEPEDGE(edgey2, edge2, edgeleft2); if (xcr >= xcl) { pts->x = xcl; pts->y = ybase; pts++; *wids++ = (unsigned int)(xcr - xcl + 1); } } /* return number of spans in the Spans */ return (pts - points); } /* From two line faces, construct clipping edges that will be used by miLineArcD when drawing a pie wedge. The line faces may be modified. */ static void miRoundJoinClip (LineFace *pLeft, LineFace *pRight, PolyEdge *edge1, PolyEdge *edge2, int *y1, int *y2, bool *left1, bool *left2) { int denom; denom = - pLeft->dx * pRight->dy + pRight->dx * pLeft->dy; if (denom >= 0) { pLeft->xa = -pLeft->xa; pLeft->ya = -pLeft->ya; } else { pRight->xa = -pRight->xa; pRight->ya = -pRight->ya; } *y1 = miRoundJoinFace (pLeft, edge1, left1); *y2 = miRoundJoinFace (pRight, edge2, left2); } /* helper function called by the preceding */ static int miRoundJoinFace (const LineFace *face, PolyEdge *edge, bool *leftEdge) { int y; int dx, dy; double xa, ya; bool left; dx = -face->dy; dy = face->dx; xa = face->xa; ya = face->ya; left = true; if (ya > 0) { ya = 0.0; xa = 0.0; } if (dy < 0 || (dy == 0 && dx > 0)) { dx = -dx; dy = -dy; left = (left ? false : true); } if (dx == 0 && dy == 0) dy = 1; if (dy == 0) { y = ICEIL (face->ya) + face->y; edge->x = INT_MIN; edge->stepx = 0; edge->signdx = 0; edge->e = -1; edge->dy = 0; edge->dx = 0; edge->height = 0; } else { y = miPolyBuildEdge (xa, ya, 0.0, dx, dy, face->x, face->y, (left ? false : true), edge); edge->height = UINT_MAX; /* number of scanlines to process */ } *leftEdge = (left ? false : true); return y; } /* From a line face, construct a clipping edge that will be used by miLineArcD when drawing a half-disk. */ static int miRoundCapClip (const LineFace *face, bool isInt, PolyEdge *edge, bool *leftEdge) { int y; int dx, dy; double xa, ya, k; bool left; dx = -face->dy; dy = face->dx; xa = face->xa; ya = face->ya; k = 0.0; if (!isInt) k = face->k; left = true; if (dy < 0 || (dy == 0 && dx > 0)) { dx = -dx; dy = -dy; xa = -xa; ya = -ya; left = (left ? false : true); } if (dx == 0 && dy == 0) dy = 1; if (dy == 0) { y = ICEIL (face->ya) + face->y; edge->x = INT_MIN; edge->stepx = 0; edge->signdx = 0; edge->e = -1; edge->dy = 0; edge->dx = 0; edge->height = 0; } else { y = miPolyBuildEdge (xa, ya, k, dx, dy, face->x, face->y, (left ? false : true), edge); edge->height = UINT_MAX; /* number of scanlines to process */ } *leftEdge = (left ? false : true); return y; } /* Paint a projecting rectangular cap on a line face. Called only by miWideDash (with isInt = true); not by miWideLine. */ static void miLineProjectingCap (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, const LineFace *face, bool isLeft, bool isInt) { int dx, dy; int topy, bottomy; int xorgi = 0, yorgi = 0; int lw = (int)(pGC->lineWidth); PolyEdge lefts[2], rights[2]; if (isInt) /* in integer case, take (xorgi,yorgi) from face; otherwise (0,0) */ { xorgi = face->x; yorgi = face->y; } dx = face->dx; dy = face->dy; if (dy == 0) /* special case: line face is horizontal */ { lefts[0].height = (unsigned int)lw; lefts[0].x = xorgi; if (isLeft) lefts[0].x -= (lw >> 1); lefts[0].stepx = 0; lefts[0].signdx = 1; lefts[0].e = -lw; lefts[0].dx = 0; lefts[0].dy = lw; rights[0].height = (unsigned int)lw; rights[0].x = xorgi; if (!isLeft) rights[0].x += ((lw + 1) >> 1); rights[0].stepx = 0; rights[0].signdx = 1; rights[0].e = -lw; rights[0].dx = 0; rights[0].dy = lw; /* fill the rectangle (1 left edge, 1 right edge) */ miFillPolyHelper (paintedSet, pixel, yorgi - (lw >> 1), (unsigned int)lw, lefts, rights, 1, 1); } else if (dx == 0) /* special case: line face is vertical */ { topy = yorgi; bottomy = yorgi + dy; if (isLeft) topy -= (lw >> 1); else bottomy += (lw >> 1); lefts[0].height = (unsigned int)(bottomy - topy); lefts[0].x = xorgi - (lw >> 1); lefts[0].stepx = 0; lefts[0].signdx = 1; lefts[0].e = -dy; lefts[0].dx = dx; lefts[0].dy = dy; rights[0].height = (unsigned int)(bottomy - topy); rights[0].x = lefts[0].x + (lw - 1); rights[0].stepx = 0; rights[0].signdx = 1; rights[0].e = -dy; rights[0].dx = dx; rights[0].dy = dy; /* fill the rectangle (1 left edge, 1 right edge) */ miFillPolyHelper (paintedSet, pixel, topy, (unsigned int)(bottomy - topy), lefts, rights, 1, 1); } else /* general case: line face is neither horizontal nor vertical */ { int lefty, righty; int finaly; double xa,ya; double xap, yap; double maxy; double projectXoff, projectYoff; double k; PolyEdge *left, *right; PolyEdge *top, *bottom; k = face->k; xa = face->xa; ya = face->ya; projectXoff = -ya; projectYoff = xa; if (dx < 0) { right = &rights[1]; left = &lefts[0]; top = &rights[0]; bottom = &lefts[1]; } else { right = &rights[0]; left = &lefts[1]; top = &lefts[0]; bottom = &rights[1]; } if (isLeft) /* cap goes left; build four edges */ { righty = miPolyBuildEdge (xa, ya, k, dx, dy, xorgi, yorgi, false, right); xa = -xa; ya = -ya; k = -k; lefty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff, k, dx, dy, xorgi, yorgi, true, left); if (dx > 0) { ya = -ya; xa = -xa; } xap = xa - projectXoff; yap = ya - projectYoff; topy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy, -dy, dx, xorgi, yorgi, (dx > 0 ? true : false), top); bottomy = miPolyBuildEdge (xa, ya, 0.0, -dy, dx, xorgi, yorgi, (dx < 0 ? true : false), bottom); maxy = -ya; } else /* cap goes right; build four edges */ { righty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff, k, dx, dy, xorgi, yorgi, false, right); xa = -xa; ya = -ya; k = -k; lefty = miPolyBuildEdge (xa, ya, k, dx, dy, xorgi, yorgi, true, left); if (dx > 0) { ya = -ya; xa = -xa; } xap = xa - projectXoff; yap = ya - projectYoff; topy = miPolyBuildEdge (xa, ya, 0.0, -dy, dx, xorgi, xorgi, (dx > 0 ? true : false), top); bottomy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy, -dy, dx, xorgi, xorgi, (dx < 0 ? true : false), bottom); maxy = -ya + projectYoff; } finaly = ICEIL(maxy) + yorgi; if (dx < 0) { left->height = (unsigned int)(bottomy - lefty); right->height = (unsigned int)(finaly - righty); top->height = (unsigned int)(righty - topy); } else { right->height = (unsigned int)(bottomy - righty); left->height = (unsigned int)(finaly - lefty); top->height = (unsigned int)(lefty - topy); } bottom->height = (unsigned int)(finaly - bottomy); /* fill the rectangle (2 left edges, 2 right edges) */ miFillPolyHelper (paintedSet, pixel, topy, (unsigned int)(bottom->height + bottomy - topy), lefts, rights, 2, 2); } } /* Draw a wide, dashed polyline, by dashing each line segment and joining appropriately. miWideDashSegment() is called to dash each line segment. */ void miWideDash (miPaintedSet *paintedSet, const miGC *pGC, miCoordMode mode, int npt, const miPoint *pPts) { int x1, y1, x2, y2; int dashNum; /* absolute number of dash, starts with 0 */ int dashIndex; /* index into array (i.e. dashNum % length) */ int dashOffset; /* offset into selected dash */ int startPaintType, endPaintType = 0, prevEndPaintType = 0; int firstPaintType = 0; /* used only for closed polylines; will be 1 */ int numPixels; bool selfJoin; /* polyline is closed? */ bool first; /* first line segment of polyline */ bool somethingDrawn = false; bool projectLeft, projectRight; LineFace leftFace, rightFace, prevRightFace; LineFace firstFace; miPixel pixel; /* ensure we have >=1 points */ if (npt <= 0) return; /* width 0 lines are handled specially; invoke Bresenham routine in mi_zerolin.c */ if (pGC->lineWidth == 0) { miZeroDash (paintedSet, pGC, mode, npt, pPts); return; } x2 = pPts->x; y2 = pPts->y; first = true; /* first line segment of polyline */ /* determine whether polyline is closed */ selfJoin = false; if (mode == MI_COORD_MODE_PREVIOUS) { int nptTmp; const miPoint *pPtsTmp; x1 = x2; y1 = y2; nptTmp = npt; pPtsTmp = pPts + 1; while (--nptTmp) { x1 += pPtsTmp->x; y1 += pPtsTmp->y; ++pPtsTmp; } if (x2 == x1 && y2 == y1) selfJoin = true; } else if (x2 == pPts[npt-1].x && y2 == pPts[npt-1].y) selfJoin = true; /* dash segments (except for the last) will not project right; and (except for the first) will not project left */ projectLeft = (pGC->capStyle == (int)MI_CAP_PROJECTING && !selfJoin) ? true : false; projectRight = false; /* perform initial offsetting into the dash sequence */ dashNum = 0; /* absolute number of dash */ dashIndex = 0; /* index into dash array */ dashOffset = 0; /* index into selected dash */ miStepDash (pGC->dashOffset, &dashNum, &dashIndex, pGC->dash, pGC->numInDashList, &dashOffset); /* How many paint types? (Will cycle through 0..numPixels-1, beginning with 1, with `off' dashes defined as those with paint type #0.) */ numPixels = pGC->numPixels; /* iterate through points, drawing a dashed segment for each line segment of nonzero length */ while (--npt) { x1 = x2; y1 = y2; ++pPts; x2 = pPts->x; y2 = pPts->y; if (mode == MI_COORD_MODE_PREVIOUS) { x2 += x1; y2 += y1; } if (x1 != x2 || y1 != y2) /* have a line segment of nonzero length */ { int prevDashNum, lastPaintedDashNum; if (npt == 1 && pGC->capStyle == (int)MI_CAP_PROJECTING && (!selfJoin || (firstPaintType == 0))) /* final point; and need a projecting cap here */ projectRight = true; prevDashNum = dashNum; /* draw dashed segment, updating dashNum, dashIndex and dashOffset, returning faces */ miWideDashSegment (paintedSet, pGC, &dashNum, &dashIndex, &dashOffset, x1, y1, x2, y2, projectLeft, projectRight, &leftFace, &rightFace); /* determine paint types used at start and end of just-drawn segment */ startPaintType = ((dashNum & 1) ? 0 : 1 + ((dashNum / 2) % (numPixels - 1))); lastPaintedDashNum = (dashOffset != 0 ? dashNum : dashNum - 1); endPaintType = ((lastPaintedDashNum & 1) ? 0 : 1 + ((dashNum / 2) % (numPixels - 1))); /* add round cap or line join at left end of just-drawn segment; if OnOffDash, do so only if segment began with an `on' dash */ if (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || (startPaintType != 0)) { pixel = pGC->pixels[startPaintType]; if (first || (pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH && prevEndPaintType == 0)) /* draw cap at left end, unless this is first segment of a closed polyline */ { if (first && selfJoin) { firstFace = leftFace; firstPaintType = startPaintType; } else if (pGC->capStyle == (int)MI_CAP_ROUND || pGC->capStyle == (int)MI_CAP_TRIANGULAR) /* invoke miLineArc to draw round cap, isInt = true */ miLineArc (paintedSet, pixel, pGC, &leftFace, (LineFace *)NULL, (double)0.0, (double)0.0, true); } else /* draw join at left end */ miLineJoin (paintedSet, pixel, pGC, &leftFace, &prevRightFace); } somethingDrawn = true; first = false; prevRightFace = rightFace; prevEndPaintType = endPaintType; projectLeft = false; } if (npt == 1 && somethingDrawn) /* last point of a nonempty polyline, so add line join or round cap if appropriate, i.e. if we're doing OnOffDash and ended on an `on' dash, or if we're doing DoubleDash */ { if (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || (endPaintType != 0)) { pixel = pGC->pixels[endPaintType]; if (selfJoin && (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || (firstPaintType != 0))) /* closed, so draw a join */ miLineJoin (paintedSet, pixel, pGC, &firstFace, &rightFace); else { if (pGC->capStyle == (int)MI_CAP_ROUND || pGC->capStyle == (int)MI_CAP_TRIANGULAR) /* invoke miLineArc, isInt = true, to draw a round cap */ miLineArc (paintedSet, pixel, pGC, (LineFace *)NULL, &rightFace, (double)0.0, (double)0.0, true); } } else /* we're doing OnOffDash, and final segment of polyline ended with an (undrawn) `off' dash */ { if (selfJoin && (firstPaintType != 0)) /* closed; if projecting or round caps are being used, draw one on the first face */ { pixel = pGC->pixels[firstPaintType]; if (pGC->capStyle == (int)MI_CAP_PROJECTING) miLineProjectingCap (paintedSet, pixel, pGC, &firstFace, true, true); else if (pGC->capStyle == (int)MI_CAP_ROUND || pGC->capStyle == (int)MI_CAP_TRIANGULAR) /* invoke miLineArc, isInt = true, to draw a round cap */ miLineArc (paintedSet, pixel, pGC, &firstFace, (LineFace *)NULL, (double)0.0, (double)0.0, true); } } } } /* handle `all points coincident' crock, nothing yet drawn */ if (!somethingDrawn && (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || !(dashNum & 1))) { unsigned int w1; pixel = (dashNum & 1) ? pGC->pixels[0] : pGC->pixels[1]; switch ((int)pGC->capStyle) { case (int)MI_CAP_ROUND: case (int)MI_CAP_TRIANGULAR: /* invoke miLineArc, isInt = false, to draw a round disk */ miLineArc (paintedSet, pixel, pGC, (LineFace *)NULL, (LineFace *)NULL, (double)x2, (double)y2, false); break; case (int)MI_CAP_PROJECTING: /* draw a square box with edge size equal to line width */ w1 = pGC->lineWidth; miFillRectPolyHelper (paintedSet, pixel, (int)(x2 - (w1 >> 1)), (int)(y2 - (w1 >> 1)), w1, w1); break; case (int)MI_CAP_BUTT: default: break; } } } #define V_TOP 0 #define V_RIGHT 1 #define V_BOTTOM 2 #define V_LEFT 3 /* Helper function, called by miWideDash(). Draw a single dashed line segment, i.e. a sequence of dashes including a possible final incomplete dash, and step DashNum, DashIndex and DashOffset appropriately. Also pass back left and right faces for the line segment, for possible use in adding caps or joins. If the LineOnOffDash line style is used, each dash will be given a round cap if lines are drawn in the rounded cap style, and a projecting cap if lines are drawn in the projecting cap style. */ /* ARGS: pDashNum = absolute number of dash pDashIndex = index into array (i.e. dashNum % length) pDashOffset = offset into selected dash */ static void miWideDashSegment (miPaintedSet *paintedSet, const miGC *pGC, int *pDashNum, int *pDashIndex, int *pDashOffset, int x1, int y1, int x2, int y2, bool projectLeft, bool projectRight, LineFace *leftFace, LineFace *rightFace) { int dashNum, dashIndex, dashRemain; unsigned int *pDash; double L, l; double k; PolyVertex vertices[4]; PolyVertex saveRight, saveBottom; PolySlope slopes[4]; PolyEdge left[2], right[2]; LineFace lcapFace, rcapFace; int nleft, nright; unsigned int h; int y; int dy, dx; double LRemain; double r; double rdx, rdy; double dashDx, dashDy; double saveK = 0.0; bool first = true; double lcenterx, lcentery, rcenterx = 0.0, rcentery = 0.0; miPixel pixel; int numPixels, paintType; dx = x2 - x1; dy = y2 - y1; dashNum = *pDashNum; dashIndex = *pDashIndex; pDash = pGC->dash; /* determine portion of current dash remaining (i.e. the portion after the current offset */ dashRemain = (int)(pDash[dashIndex]) - *pDashOffset; /* compute color of current dash */ numPixels = pGC->numPixels; paintType = (dashNum & 1) ? 0 : 1 + ((dashNum / 2) % (numPixels - 1)); pixel = pGC->pixels[paintType]; /* compute e.g. L, the distance to go (for dashing) */ l = 0.5 * ((double) pGC->lineWidth); if (dx == 0) /* vertical segment */ { L = dy; rdx = 0; rdy = l; if (dy < 0) { L = -dy; rdy = -l; } } else if (dy == 0) /* horizontal segment */ { L = dx; rdx = l; rdy = 0; if (dx < 0) { L = -dx; rdx = -l; } } else /* neither horizontal nor vertical */ { L = hypot ((double) dx, (double) dy); r = l / L; /* this is ell / L, not 1 / L */ rdx = r * dx; rdy = r * dy; } k = l * L; /* this is ell * L, not 1 * L */ /* All position comments are relative to a line with dx and dy > 0, * but the code does not depend on this. */ /* top */ slopes[V_TOP].dx = dx; slopes[V_TOP].dy = dy; slopes[V_TOP].k = k; /* right */ slopes[V_RIGHT].dx = -dy; slopes[V_RIGHT].dy = dx; slopes[V_RIGHT].k = 0; /* bottom */ slopes[V_BOTTOM].dx = -dx; slopes[V_BOTTOM].dy = -dy; slopes[V_BOTTOM].k = k; /* left */ slopes[V_LEFT].dx = dy; slopes[V_LEFT].dy = -dx; slopes[V_LEFT].k = 0; /* preload the start coordinates */ vertices[V_RIGHT].x = vertices[V_TOP].x = rdy; vertices[V_RIGHT].y = vertices[V_TOP].y = -rdx; vertices[V_BOTTOM].x = vertices[V_LEFT].x = -rdy; vertices[V_BOTTOM].y = vertices[V_LEFT].y = rdx; if (projectLeft) /* offset the vertices appropriately */ { vertices[V_TOP].x -= rdx; vertices[V_TOP].y -= rdy; vertices[V_LEFT].x -= rdx; vertices[V_LEFT].y -= rdy; slopes[V_LEFT].k = rdx * dx + rdy * dy; } /* starting point for first dash (floating point) */ lcenterx = x1; lcentery = y1; if (pGC->capStyle == (int)MI_CAP_ROUND || pGC->capStyle == (int)MI_CAP_TRIANGULAR) /* keep track of starting face (need only in OnOff case) */ { lcapFace.dx = dx; lcapFace.dy = dy; lcapFace.x = x1; lcapFace.y = y1; rcapFace.dx = -dx; rcapFace.dy = -dy; rcapFace.x = x1; rcapFace.y = y1; } /* draw dashes until end of line segment is reached, and no additional (complete) dash can be drawn */ LRemain = L; while (LRemain > dashRemain) { dashDx = (dashRemain * dx) / L; dashDy = (dashRemain * dy) / L; /* ending point for dash */ rcenterx = lcenterx + dashDx; rcentery = lcentery + dashDy; vertices[V_RIGHT].x += dashDx; vertices[V_RIGHT].y += dashDy; vertices[V_BOTTOM].x += dashDx; vertices[V_BOTTOM].y += dashDy; slopes[V_RIGHT].k = vertices[V_RIGHT].x * dx + vertices[V_RIGHT].y * dy; /* draw dash (if OnOffDash, don't draw `off' dashes) */ if (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || !(paintType == 0)) { if (pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH && pGC->capStyle == (int)MI_CAP_PROJECTING) /* will draw projecting caps, so save vertices for later use */ { saveRight = vertices[V_RIGHT]; saveBottom = vertices[V_BOTTOM]; saveK = slopes[V_RIGHT].k; if (!first) { vertices[V_TOP].x -= rdx; vertices[V_TOP].y -= rdy; vertices[V_LEFT].x -= rdx; vertices[V_LEFT].y -= rdy; slopes[V_LEFT].k = vertices[V_LEFT].x * slopes[V_LEFT].dy - vertices[V_LEFT].y * slopes[V_LEFT].dx; } vertices[V_RIGHT].x += rdx; vertices[V_RIGHT].y += rdy; vertices[V_BOTTOM].x += rdx; vertices[V_BOTTOM].y += rdy; slopes[V_RIGHT].k = vertices[V_RIGHT].x * slopes[V_RIGHT].dy - vertices[V_RIGHT].y * slopes[V_RIGHT].dx; } /* build lists of left and right edges for the dash, using the just-computed array of slopes */ y = miPolyBuildPoly (vertices, slopes, 4, x1, y1, left, right, &nleft, &nright, &h); /* fill the dash, with either fg or bg color (alternates) */ miFillPolyHelper (paintedSet, pixel, y, h, left, right, nleft, nright); if (pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH) /* if doing OnOffDash, add caps if any */ { switch ((int)pGC->capStyle) { case (int)MI_CAP_BUTT: default: break; case (int)MI_CAP_PROJECTING: /* use saved vertices */ vertices[V_BOTTOM] = saveBottom; vertices[V_RIGHT] = saveRight; slopes[V_RIGHT].k = saveK; break; case (int)MI_CAP_ROUND: case (int)MI_CAP_TRIANGULAR: if (!first) { if (dx < 0) { lcapFace.xa = -vertices[V_LEFT].x; lcapFace.ya = -vertices[V_LEFT].y; lcapFace.k = slopes[V_LEFT].k; } else { lcapFace.xa = vertices[V_TOP].x; lcapFace.ya = vertices[V_TOP].y; lcapFace.k = -slopes[V_LEFT].k; } /* invoke miLineArc, isInt = false, to draw half-disk on left end of dash (only if dash is not first) */ miLineArc (paintedSet, pixel, pGC, &lcapFace, (LineFace *) NULL, lcenterx, lcentery, false); } if (dx < 0) { rcapFace.xa = vertices[V_BOTTOM].x; rcapFace.ya = vertices[V_BOTTOM].y; rcapFace.k = slopes[V_RIGHT].k; } else { rcapFace.xa = -vertices[V_RIGHT].x; rcapFace.ya = -vertices[V_RIGHT].y; rcapFace.k = -slopes[V_RIGHT].k; } /* invoke miLineArc, isInt = false, to draw half-disk on right end of dash */ miLineArc (paintedSet, pixel, pGC, (LineFace *)NULL, &rcapFace, rcenterx, rcentery, false); break; } } } /* we just drew a dash, or (in the OnOff case) we either drew a dash or we didn't */ LRemain -= dashRemain; /* decrement float by int (distance over which we just drew, i.e. the remainder of current dash) */ /* bump absolute dash number, and index of dash in array (cyclically) */ ++dashNum; ++dashIndex; if (dashIndex == pGC->numInDashList) dashIndex = 0; dashRemain = (int)(pDash[dashIndex]); /* whole new dash now `remains' */ /* compute color of next dash */ paintType = (dashNum & 1) ? 0 : 1 + ((dashNum / 2) % (numPixels - 1)); pixel = pGC->pixels[paintType]; /* next dash will start where previous one ended */ lcenterx = rcenterx; lcentery = rcentery; vertices[V_TOP] = vertices[V_RIGHT]; vertices[V_LEFT] = vertices[V_BOTTOM]; slopes[V_LEFT].k = -slopes[V_RIGHT].k; first = false; /* no longer first dash of line segment */ } /* final portion of segment is dashed specially, with an incomplete dash */ if (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || !(paintType == 0)) { vertices[V_TOP].x -= dx; vertices[V_TOP].y -= dy; vertices[V_LEFT].x -= dx; vertices[V_LEFT].y -= dy; vertices[V_RIGHT].x = rdy; vertices[V_RIGHT].y = -rdx; vertices[V_BOTTOM].x = -rdy; vertices[V_BOTTOM].y = rdx; if (projectRight) /* offset appropriately */ { vertices[V_RIGHT].x += rdx; vertices[V_RIGHT].y += rdy; vertices[V_BOTTOM].x += rdx; vertices[V_BOTTOM].y += rdy; slopes[V_RIGHT].k = vertices[V_RIGHT].x * slopes[V_RIGHT].dy - vertices[V_RIGHT].y * slopes[V_RIGHT].dx; } else slopes[V_RIGHT].k = 0; /* if OnOffDash line style and cap mode is projecting, offset the face, so as to draw a projecting cap */ if (!first && pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH && pGC->capStyle == (int)MI_CAP_PROJECTING) { vertices[V_TOP].x -= rdx; vertices[V_TOP].y -= rdy; vertices[V_LEFT].x -= rdx; vertices[V_LEFT].y -= rdy; slopes[V_LEFT].k = vertices[V_LEFT].x * slopes[V_LEFT].dy - vertices[V_LEFT].y * slopes[V_LEFT].dx; } else slopes[V_LEFT].k += dx * dx + dy * dy; /* build lists of left and right edges for the final incomplete dash, using the just-computed vertices and slopes */ y = miPolyBuildPoly (vertices, slopes, 4, x2, y2, left, right, &nleft, &nright, &h); /* fill the final dash */ miFillPolyHelper (paintedSet, pixel, y, h, left, right, nleft, nright); /* if OnOffDash line style and cap mode is round, draw a round cap */ if (!first && pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH && (pGC->capStyle == (int)MI_CAP_ROUND || pGC->capStyle == (int)MI_CAP_TRIANGULAR)) { lcapFace.x = x2; lcapFace.y = y2; if (dx < 0) { lcapFace.xa = -vertices[V_LEFT].x; lcapFace.ya = -vertices[V_LEFT].y; lcapFace.k = slopes[V_LEFT].k; } else { lcapFace.xa = vertices[V_TOP].x; lcapFace.ya = vertices[V_TOP].y; lcapFace.k = -slopes[V_LEFT].k; } /* invoke miLineArc, isInt = false, to draw disk on end */ miLineArc (paintedSet, pixel, pGC, &lcapFace, (LineFace *) NULL, rcenterx, rcentery, false); } } /* work out left and right faces of the dashed segment, to pass back */ leftFace->x = x1; leftFace->y = y1; leftFace->dx = dx; leftFace->dy = dy; leftFace->xa = rdy; leftFace->ya = -rdx; leftFace->k = k; rightFace->x = x2; rightFace->y = y2; rightFace->dx = -dx; rightFace->dy = -dy; rightFace->xa = -rdy; rightFace->ya = rdx; rightFace->k = k; /* update absolute dash number, dash index, dash offset */ dashRemain = (int)(((double) dashRemain) - LRemain); if (dashRemain == 0) /* on to next dash in array */ { dashNum++; /* bump absolute dash number */ dashIndex++; if (dashIndex == pGC->numInDashList) /* wrap */ dashIndex = 0; dashRemain = (int)(pDash[dashIndex]); } *pDashNum = dashNum; *pDashIndex = dashIndex; *pDashOffset = (int)(pDash[dashIndex]) - dashRemain; } /* Helper function, called by miWideDash() above and also by miZeroPolyArc (in mi_zerarc.c) and miZeroDash (in mi_zerolin.c) to perform initial offsetting into the dash array, before dash #0 is drawn. In all cases, dashNum=0, dashIndex=0 and dashOffset=0. */ /* FIXME: a negative offset is not supported, and if it is, then some places elsewhere in the code, which assume dashNum>=0, may need to be fixed too. */ /* ARGS: dist = add'l offset (assumed >= 0) pDashNum = dash number pDashIndex = current dash pDash = dash list numInDashList = dashlist length pDashOffset = offset into current dash */ void miStepDash (int dist, int *pDashNum, int *pDashIndex, const unsigned int *pDash, int numInDashList, int *pDashOffset) { int dashNum, dashIndex, dashOffset; int totallen; int i; dashNum = *pDashNum; dashIndex = *pDashIndex; dashOffset = *pDashOffset; if (dashOffset + dist < (int)(pDash[dashIndex])) /* offset won't take us beyond end of present dash */ { *pDashOffset = dashOffset + dist; return; } /* move to next dash */ dist -= (int)(pDash[dashIndex]) - dashOffset; dashNum++; dashIndex++; if (dashIndex == numInDashList) /* wrap to beginning of dash list */ dashIndex = 0; /* make it easy on ourselves: work modulo iteration interval */ totallen = 0; for (i = 0; i < numInDashList; i++) totallen += (int)(pDash[i]); if (totallen <= dist) dist = dist % totallen; while (dist >= (int)(pDash[dashIndex])) { dist -= (int)(pDash[dashIndex]); dashNum++; dashIndex++; if (dashIndex == numInDashList) /* wrap to beginning of dash list */ dashIndex = 0; } *pDashNum = dashNum; *pDashIndex = dashIndex; *pDashOffset = dist; } /* Draw a wide polyline, undashed (if width=0, this simply calls miZeroLine) */ void miWideLine (miPaintedSet *paintedSet, const miGC *pGC, miCoordMode mode, int npt, const miPoint *pPts) { int x1, y1, x2, y2; bool projectLeft, projectRight; LineFace leftFace, rightFace, prevRightFace; LineFace firstFace; int first; bool somethingDrawn = false; bool selfJoin; /* ensure we have >=1 points */ if (npt <= 0) return; /* width 0 lines are handled specially */ if (pGC->lineWidth == 0) { miZeroLine (paintedSet, pGC, mode, npt, pPts); return; } x2 = pPts->x; y2 = pPts->y; first = true; /* determine whether polyline is closed */ selfJoin = false; if (npt > 1) { if (mode == MI_COORD_MODE_PREVIOUS) { int nptTmp; const miPoint *pPtsTmp; x1 = x2; y1 = y2; nptTmp = npt; pPtsTmp = pPts + 1; while (--nptTmp) { x1 += pPtsTmp->x; y1 += pPtsTmp->y; ++pPtsTmp; } if (x2 == x1 && y2 == y1) selfJoin = true; } else if (x2 == pPts[npt-1].x && y2 == pPts[npt-1].y) selfJoin = true; } /* line segments (except for the last) will not project right; they'll project left if the cap mode is "projecting" */ projectLeft = (pGC->capStyle == (int)MI_CAP_PROJECTING && !selfJoin) ? true : false; projectRight = false; /* iterate through points, drawing all line segments of nonzero length */ while (--npt) { x1 = x2; y1 = y2; ++pPts; x2 = pPts->x; y2 = pPts->y; if (mode == MI_COORD_MODE_PREVIOUS) { x2 += x1; y2 += y1; } if (x1 != x2 || y1 != y2) /* nonzero length */ { somethingDrawn = true; if (npt == 1 && pGC->capStyle == (int)MI_CAP_PROJECTING && !selfJoin) /* last point; and need a projecting cap here */ projectRight = true; /* draw segment (pixel=1), returning faces */ miWideSegment (paintedSet, pGC->pixels[1], pGC, x1, y1, x2, y2, projectLeft, projectRight, &leftFace, &rightFace); if (first) /* first line segment, draw round cap if needed */ { if (selfJoin) firstFace = leftFace; else if (pGC->capStyle == (int)MI_CAP_ROUND || pGC->capStyle == (int)MI_CAP_TRIANGULAR) /* invoke miLineArc, isInt = true, to draw a round cap on left face in paint type #1 */ miLineArc (paintedSet, pGC->pixels[1], pGC, &leftFace, (LineFace *)NULL, (double)0.0, (double)0.0, true); } else /* general case: draw join at beginning of segment (pixel=1) */ miLineJoin (paintedSet, pGC->pixels[1], pGC, &leftFace, &prevRightFace); prevRightFace = rightFace; first = false; projectLeft = false; } /* final point of polyline */ if (npt == 1 && somethingDrawn) { if (selfJoin) /* add line join to close the polyline, pixel=1 */ miLineJoin (paintedSet, pGC->pixels[1], pGC, &firstFace, &rightFace); else if (pGC->capStyle == (int)MI_CAP_ROUND || pGC->capStyle == (int)MI_CAP_TRIANGULAR) /* invoke miLineArc, isInt = true, to draw round cap on right face, pixel=1 */ miLineArc (paintedSet, pGC->pixels[1], pGC, (LineFace *)NULL, &rightFace, (double)0.0, (double)0.0, true); } } /* handle crock where all points are coincident */ if (!somethingDrawn) { projectLeft = (pGC->capStyle == (int)MI_CAP_PROJECTING) ? true : false; miWideSegment (paintedSet, pGC->pixels[1], pGC, /* pixel=1 */ x2, y2, x2, y2, projectLeft, projectLeft, &leftFace, &rightFace); if (pGC->capStyle == (int)MI_CAP_ROUND || pGC->capStyle == (int)MI_CAP_TRIANGULAR) { /* invoke miLineArc, isInt = true, to draw round cap in paint type #1 */ miLineArc (paintedSet, pGC->pixels[1], pGC, &leftFace, (LineFace *)NULL, (double)0.0, (double)0.0, true); /* invoke miLineArc, isInt = true, to draw other round cap in paint type #1 */ rightFace.dx = -1; /* sleazy hack to make it work */ miLineArc (paintedSet, pGC->pixels[1], pGC, (LineFace *) NULL, &rightFace, (double)0.0, (double)0.0, true); } } } /* Helper function, called by miWideLine() with pixel=1. Draw a single segment of a wide polyline, taking into account projecting caps, but not round caps. Also pass back left and right faces for the line segment, for possible use in adding caps or joins. */ static void miWideSegment (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, int x1, int y1, int x2, int y2, bool projectLeft, bool projectRight, LineFace *leftFace, LineFace *rightFace) { int dx, dy; int x, y; int signdx; int lw = (int)(pGC->lineWidth); if (y2 < y1 || (y2 == y1 && x2 < x1)) /* interchange, so as always to draw top-to-bottom, or left-to-right if horizontal */ { int tx, ty; bool tbool; LineFace *tface; tx = x1; x1 = x2; x2 = tx; ty = y1; y1 = y2; y2 = ty; tbool = projectLeft; projectLeft = projectRight; projectRight = tbool; tface = leftFace; leftFace = rightFace; rightFace = tface; } dy = y2 - y1; signdx = 1; dx = x2 - x1; if (dx < 0) signdx = -1; leftFace->x = x1; leftFace->y = y1; leftFace->dx = dx; leftFace->dy = dy; rightFace->x = x2; rightFace->y = y2; rightFace->dx = -dx; /* for faces, (dx,dy) points _into_ line */ rightFace->dy = -dy; if (dy == 0) /* segment is horizontal */ { rightFace->xa = 0; rightFace->ya = 0.5 * (double)lw; rightFace->k = -0.5 * (double)(lw * dx); /* k = xa * dy - ya * dx */ leftFace->xa = 0; leftFace->ya = -rightFace->ya; leftFace->k = rightFace->k; /* k = xa * dy - ya * dx */ x = x1; if (projectLeft) x -= (lw >> 1); y = y1 - (lw >> 1); dx = x2 - x; if (projectRight) dx += ((lw + 1) >> 1); dy = lw; miFillRectPolyHelper (paintedSet, pixel, x, y, (unsigned int)dx, (unsigned int)dy); } else if (dx == 0) /* segment is vertical */ { leftFace->xa = 0.5 * (double)lw; leftFace->ya = 0; leftFace->k = 0.5 * (double)(lw * dy); /* k = xa * dy - ya * dx */ rightFace->xa = -leftFace->xa; rightFace->ya = 0; rightFace->k = leftFace->k; /* k = xa * dy - ya * dx */ y = y1; if (projectLeft) y -= lw >> 1; x = x1 - (lw >> 1); dy = y2 - y; if (projectRight) dy += ((lw + 1) >> 1); dx = lw; miFillRectPolyHelper (paintedSet, pixel, x, y, (unsigned int)dx, (unsigned int)dy); } else /* general case: segment is neither horizontal nor vertical */ { double l, L, r; double xa, ya; double projectXoff = 0.0, projectYoff = 0.0; double k; double maxy; int finaly; int lefty, righty, topy, bottomy; PolyEdge lefts[2], rights[2]; PolyEdge *left, *right; PolyEdge *top, *bottom; l = 0.5 * ((double) lw); L = hypot ((double) dx, (double) dy); if (dx < 0) { right = &rights[1]; left = &lefts[0]; top = &rights[0]; bottom = &lefts[1]; } else { right = &rights[0]; left = &lefts[1]; top = &lefts[0]; bottom = &rights[1]; } r = l / L; /* this is ell / L, not 1 / L */ ya = -r * dx; xa = r * dy; if (projectLeft | projectRight) { projectXoff = -ya; projectYoff = xa; } /* build first long edge */ k = l * L; /* xa * dy - ya * dx */ leftFace->xa = xa; leftFace->ya = ya; leftFace->k = k; rightFace->xa = -xa; rightFace->ya = -ya; rightFace->k = k; if (projectLeft) righty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff, k, dx, dy, x1, y1, false, right); else righty = miPolyBuildEdge (xa, ya, k, dx, dy, x1, y1, false, right); /* build second long edge */ ya = -ya; xa = -xa; k = -k; /* xa * dy - ya * dx */ if (projectLeft) lefty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff, k, dx, dy, x1, y1, true, left); else lefty = miPolyBuildEdge (xa, ya, k, dx, dy, x1, y1, true, left); /* build first short edge, on left end */ if (signdx > 0) { ya = -ya; xa = -xa; } if (projectLeft) { double xap = xa - projectXoff; double yap = ya - projectYoff; topy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy, -dy, dx, x1, y1, (dx > 0 ? true : false), top); } else topy = miPolyBuildEdge (xa, ya, 0.0, -dy, dx, x1, y1, (dx > 0 ? true : false), top); /* build second short edge, on right end */ if (projectRight) { double xap = xa + projectXoff; double yap = ya + projectYoff; bottomy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy, -dy, dx, x2, y2, (dx < 0 ? true : false), bottom); maxy = -ya + projectYoff; } else { bottomy = miPolyBuildEdge (xa, ya, 0.0, -dy, dx, x2, y2, (dx < 0 ? true : false), bottom); maxy = -ya; } finaly = ICEIL (maxy) + y2; if (dx < 0) { left->height = (unsigned int)(bottomy - lefty); right->height = (unsigned int)(finaly - righty); top->height = (unsigned int)(righty - topy); } else { right->height = (unsigned int)(bottomy - righty); left->height = (unsigned int)(finaly - lefty); top->height = (unsigned int)(lefty - topy); } bottom->height = (unsigned int)(finaly - bottomy); /* fill the rectangle (2 left edges, 2 right edges) */ miFillPolyHelper (paintedSet, pixel, topy, (unsigned int)(bottom->height + bottomy - topy), lefts, rights, 2, 2); } }