1 /* $XConsortium: miwideline.c /main/58 1996/08/12 21:51:21 dpw $ */
4 Copyright (c) 1988 X Consortium
6 Permission is hereby granted, free of charge, to any person obtaining
7 a copy of this software and associated documentation files (the
8 "Software"), to deal in the Software without restriction, including
9 without limitation the rights to use, copy, modify, merge, publish,
10 distribute, sublicense, and/or sell copies of the Software, and to
11 permit persons to whom the Software is furnished to do so, subject to
12 the following conditions:
14 The above copyright notice and this permission notice shall be included
15 in all copies or substantial portions of the Software.
17 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
20 IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR
21 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
22 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
23 OTHER DEALINGS IN THE SOFTWARE.
25 Except as contained in this notice, the name of the X Consortium shall
26 not be used in advertising or otherwise to promote the sale, use or
27 other dealings in this Software without prior written authorization
28 from the X Consortium.
31 /* $XFree86: xc/programs/Xserver/mi/miwideline.c,v 1.1.1.3.2.2 1998/02/01 22:08:22 robin Exp $ */
33 /* Author: Keith Packard, MIT X Consortium */
36 * Mostly integer wideline code. Uses a technique similar to
37 * bresenham zero-width lines, except walks an X edge
44 #define _XOPEN_SOURCE /* to get prototype for hypot on some systems */
49 #include "windowstr.h"
51 #include "miscstruct.h"
52 #include "miwideline.h"
59 static void miLineArc();
62 * spans-based polygon filler
66 miFillPolyHelper (pDrawable, pGC, pixel, spanData, y, overall_height,
67 left, right, left_count, right_count)
68 DrawablePtr pDrawable;
72 int y; /* start y coordinate */
73 int overall_height; /* height of entire segment */
74 PolyEdgePtr left, right;
75 int left_count, right_count;
77 register int left_x, left_e;
82 register int right_x, right_e;
85 int right_dy, right_dx;
88 int left_height, right_height;
90 register DDXPointPtr ppt;
103 pptInit = (DDXPointPtr) ALLOCATE_LOCAL (overall_height * sizeof(*ppt));
106 pwidthInit = (int *) ALLOCATE_LOCAL (overall_height * sizeof(*pwidth));
109 DEALLOCATE_LOCAL (pptInit);
114 oldPixel = pGC->fgPixel;
115 if (pixel != oldPixel)
117 DoChangeGC (pGC, GCForeground, (XID *)&pixel, FALSE);
118 ValidateGC (pDrawable, pGC);
123 spanRec.points = (DDXPointPtr) xalloc (overall_height * sizeof (*ppt));
126 spanRec.widths = (int *) xalloc (overall_height * sizeof (int));
129 xfree (spanRec.points);
132 ppt = spanRec.points;
133 pwidth = spanRec.widths;
137 if (pGC->miTranslate)
142 while ((left_count || left_height) &&
143 (right_count || right_height))
148 height = left_height;
149 if (height > right_height)
150 height = right_height;
152 left_height -= height;
153 right_height -= height;
155 while (--height >= 0)
157 if (right_x >= left_x)
160 ppt->x = left_x + xorg;
162 *pwidth++ = right_x - left_x + 1;
173 (*pGC->ops->FillSpans) (pDrawable, pGC, ppt - pptInit, pptInit, pwidthInit, TRUE);
174 DEALLOCATE_LOCAL (pwidthInit);
175 DEALLOCATE_LOCAL (pptInit);
176 if (pixel != oldPixel)
178 DoChangeGC (pGC, GCForeground, &oldPixel, FALSE);
179 ValidateGC (pDrawable, pGC);
184 spanRec.count = ppt - spanRec.points;
185 AppendSpanGroup (pGC, pixel, &spanRec, spanData)
190 miFillRectPolyHelper (pDrawable, pGC, pixel, spanData, x, y, w, h)
191 DrawablePtr pDrawable;
194 SpanDataPtr spanData;
197 register DDXPointPtr ppt;
198 register int *pwidth;
209 oldPixel = pGC->fgPixel;
210 if (pixel != oldPixel)
212 DoChangeGC (pGC, GCForeground, (XID *)&pixel, FALSE);
213 ValidateGC (pDrawable, pGC);
215 (*pGC->ops->PolyFillRect) (pDrawable, pGC, 1, &rect);
216 if (pixel != oldPixel)
218 DoChangeGC (pGC, GCForeground, &oldPixel, FALSE);
219 ValidateGC (pDrawable, pGC);
224 spanRec.points = (DDXPointPtr) xalloc (h * sizeof (*ppt));
227 spanRec.widths = (int *) xalloc (h * sizeof (int));
230 xfree (spanRec.points);
233 ppt = spanRec.points;
234 pwidth = spanRec.widths;
236 if (pGC->miTranslate)
249 spanRec.count = ppt - spanRec.points;
250 AppendSpanGroup (pGC, pixel, &spanRec, spanData)
255 miPolyBuildEdge (x0, y0, k, dx, dy, xi, yi, left, edge)
257 double k; /* x0 * dy - y0 * dx */
261 register PolyEdgePtr edge;
275 double realk, kerror;
276 realk = x0 * dy - y0 * dx;
277 kerror = Fabs (realk - k);
279 printf ("realk: %g k: %g\n", realk, k);
283 xady = ICEIL (k) + y * dx;
286 x = - (-xady / dy) - 1;
295 edge->stepx = dx / dy;
301 edge->stepx = - (-dx / dy);
306 edge->x = x + left + xi;
307 edge->e = e - dy; /* bias to compare against 0 instead of dy */
311 #define StepAround(v, incr, max) (((v) + (incr) < 0) ? (max - 1) : ((v) + (incr) == max) ? 0 : ((v) + (incr)))
314 miPolyBuildPoly (vertices, slopes, count, xi, yi, left, right, pnleft, pnright, h)
315 register PolyVertexPtr vertices;
316 register PolySlopePtr slopes;
319 PolyEdgePtr left, right;
320 int *pnleft, *pnright;
330 register int nright, nleft;
331 int y, lasty, bottomy, topy;
333 /* find the top of the polygon */
334 maxy = miny = vertices[0].y;
336 for (i = 1; i < count; i++)
338 if (vertices[i].y < miny)
341 miny = vertices[i].y;
343 if (vertices[i].y >= maxy)
346 maxy = vertices[i].y;
353 j = StepAround (top, -1, count);
355 if (slopes[j].dy * slopes[i].dx > slopes[i].dy * slopes[j].dx)
361 bottomy = ICEIL (maxy) + yi;
365 s = StepAround (top, slopeoff, count);
369 if (slopes[s].dy != 0)
371 y = miPolyBuildEdge (vertices[i].x, vertices[i].y,
373 slopes[s].dx, slopes[s].dy,
377 right[nright-1].height = y - lasty;
384 i = StepAround (i, clockwise, count);
385 s = StepAround (s, clockwise, count);
388 right[nright-1].height = bottomy - lasty;
396 s = StepAround (top, slopeoff, count);
400 if (slopes[s].dy != 0)
402 y = miPolyBuildEdge (vertices[i].x, vertices[i].y,
404 slopes[s].dx, slopes[s].dy, xi, yi, 1,
408 left[nleft-1].height = y - lasty;
412 i = StepAround (i, -clockwise, count);
413 s = StepAround (s, -clockwise, count);
416 left[nleft-1].height = bottomy - lasty;
424 miLineOnePoint (pDrawable, pGC, pixel, spanData, x, y)
425 DrawablePtr pDrawable;
428 SpanDataPtr spanData;
433 unsigned long oldPixel;
435 MILINESETPIXEL (pDrawable, pGC, pixel, oldPixel);
436 if (pGC->fillStyle == FillSolid)
440 (*pGC->ops->PolyPoint) (pDrawable, pGC, CoordModeOrigin, 1, &pt);
445 if (pGC->miTranslate)
452 (*pGC->ops->FillSpans) (pDrawable, pGC, 1, &pt, &wid, TRUE);
454 MILINERESETPIXEL (pDrawable, pGC, pixel, oldPixel);
458 miLineJoin (pDrawable, pGC, pixel, spanData, pLeft, pRight)
459 DrawablePtr pDrawable;
462 SpanDataPtr spanData;
463 register LineFacePtr pLeft, pRight;
467 PolyVertexRec vertices[4];
468 PolySlopeRec slopes[4];
470 PolyEdgeRec left[4], right[4];
474 int joinStyle = pGC->joinStyle;
475 int lw = pGC->lineWidth;
477 if (lw == 1 && !spanData) {
478 /* Lines going in the same direction have no join */
479 if (pLeft->dx >= 0 == pRight->dx <= 0)
481 if (joinStyle != JoinRound) {
482 denom = - pLeft->dx * (double)pRight->dy + pRight->dx * (double)pLeft->dy;
484 return; /* no join to draw */
486 if (joinStyle != JoinMiter) {
487 miLineOnePoint (pDrawable, pGC, pixel, spanData, pLeft->x, pLeft->y);
491 if (joinStyle == JoinRound)
493 miLineArc(pDrawable, pGC, pixel, spanData,
495 (double)0.0, (double)0.0, TRUE);
498 denom = - pLeft->dx * (double)pRight->dy + pRight->dx * (double)pLeft->dy;
500 return; /* no join to draw */
506 pLeft->xa = -pLeft->xa;
507 pLeft->ya = -pLeft->ya;
508 pLeft->dx = -pLeft->dx;
509 pLeft->dy = -pLeft->dy;
514 pRight->xa = -pRight->xa;
515 pRight->ya = -pRight->ya;
516 pRight->dx = -pRight->dx;
517 pRight->dy = -pRight->dy;
520 vertices[0].x = pRight->xa;
521 vertices[0].y = pRight->ya;
522 slopes[0].dx = -pRight->dy;
523 slopes[0].dy = pRight->dx;
528 slopes[1].dx = pLeft->dy;
529 slopes[1].dy = -pLeft->dx;
532 vertices[2].x = pLeft->xa;
533 vertices[2].y = pLeft->ya;
535 if (joinStyle == JoinMiter)
537 my = (pLeft->dy * (pRight->xa * pRight->dy - pRight->ya * pRight->dx) -
538 pRight->dy * (pLeft->xa * pLeft->dy - pLeft->ya * pLeft->dx )) /
542 mx = pLeft->xa + (my - pLeft->ya) *
543 (double) pLeft->dx / (double) pLeft->dy;
547 mx = pRight->xa + (my - pRight->ya) *
548 (double) pRight->dx / (double) pRight->dy;
550 /* check miter limit */
551 if ((mx * mx + my * my) * 4 > SQSECANT * lw * lw)
552 joinStyle = JoinBevel;
555 if (joinStyle == JoinMiter)
557 slopes[2].dx = pLeft->dx;
558 slopes[2].dy = pLeft->dy;
559 slopes[2].k = pLeft->k;
562 slopes[2].dx = -slopes[2].dx;
563 slopes[2].dy = -slopes[2].dy;
564 slopes[2].k = -slopes[2].k;
568 slopes[3].dx = pRight->dx;
569 slopes[3].dy = pRight->dy;
570 slopes[3].k = pRight->k;
573 slopes[3].dx = -slopes[3].dx;
574 slopes[3].dy = -slopes[3].dy;
575 slopes[3].k = -slopes[3].k;
581 double scale, dx, dy, adx, ady;
583 adx = dx = pRight->xa - pLeft->xa;
584 ady = dy = pRight->ya - pLeft->ya;
592 slopes[2].dx = (dx * 65536) / scale;
593 slopes[2].dy = (dy * 65536) / scale;
594 slopes[2].k = ((pLeft->xa + pRight->xa) * slopes[2].dy -
595 (pLeft->ya + pRight->ya) * slopes[2].dx) / 2.0;
599 y = miPolyBuildPoly (vertices, slopes, edgecount, pLeft->x, pLeft->y,
600 left, right, &nleft, &nright, &height);
601 miFillPolyHelper (pDrawable, pGC, pixel, spanData, y, height, left, right, nleft, nright);
605 miLineArcI (pDraw, pGC, xorg, yorg, points, widths)
612 register DDXPointPtr tpts, bpts;
613 register int *twids, *bwids;
614 register int x, y, e, ex, slw;
618 if (pGC->miTranslate)
623 slw = pGC->lineWidth;
635 e = - ((y << 2) + 3);
646 e += (ex = -((x << 3) + 4));
650 if ((e == ex) && (slw > 1))
656 if ((y != 0) && ((slw > 1) || (e != ex)))
664 return (pGC->lineWidth);
667 #define CLIPSTEPEDGE(edgey,edge,edgeleft) \
668 if (ybase == edgey) \
681 edge->x += edge->stepx; \
682 edge->e += edge->dx; \
685 edge->x += edge->signdx; \
686 edge->e -= edge->dy; \
691 miLineArcD (pDraw, pGC, xorg, yorg, points, widths,
692 edge1, edgey1, edgeleft1, edge2, edgey2, edgeleft2)
698 PolyEdgePtr edge1, edge2;
700 Bool edgeleft1, edgeleft2;
702 register DDXPointPtr pts;
704 double radius, x0, y0, el, er, yk, xlk, xrk, k;
705 int xbase, ybase, y, boty, xl, xr, xcl, xcr;
707 Bool edge1IsMin, edge2IsMin;
714 ybase = ICEIL (yorg);
716 if (pGC->miTranslate)
720 edge1->x += pDraw->x;
721 edge2->x += pDraw->x;
728 radius = ((double)pGC->lineWidth) / 2.0;
729 y = floor(radius - y0 + 1.0);
747 if ((edge1->signdx < 0) == edgeleft1)
765 if ((edge2->signdx < 0) == edgeleft2)
772 if (edge2IsMin && ymin1 > ymin2)
774 } else if (edge2IsMin)
776 el = radius * radius - ((y + y0) * (y + y0)) - (x0 * x0);
785 boty = (y0 < -0.5) ? 1 : 0;
786 if (ybase + y - boty > ymax)
787 boty = ymax - ybase - y;
795 er += xrk - (xr << 1);
801 el += (xl << 1) - xlk;
809 CLIPSTEPEDGE(edgey1, edge1, edgeleft1);
810 CLIPSTEPEDGE(edgey2, edge2, edgeleft2);
816 *wids++ = xcr - xcl + 1;
819 er = xrk - (xr << 1) - er;
820 el = (xl << 1) - xlk - el;
821 boty = floor(-y0 - radius + 1.0);
822 if (ybase + y - boty > ymax)
823 boty = ymax - ybase - y;
828 while ((er >= 0.0) && (xr >= 0))
831 er += xrk - (xr << 1);
834 while ((el > 0.0) && (xl <= 0))
837 el += (xl << 1) - xlk;
845 CLIPSTEPEDGE(edgey1, edge1, edgeleft1);
846 CLIPSTEPEDGE(edgey2, edge2, edgeleft2);
852 *wids++ = xcr - xcl + 1;
855 return (pts - points);
859 miRoundJoinFace (face, edge, leftEdge)
860 register LineFacePtr face;
861 register PolyEdgePtr edge;
879 if (dy < 0 || dy == 0 && dx > 0)
885 if (dx == 0 && dy == 0)
889 y = ICEIL (face->ya) + face->y;
900 y = miPolyBuildEdge (xa, ya, 0.0, dx, dy, face->x, face->y, !left, edge);
901 edge->height = 32767;
908 miRoundJoinClip (pLeft, pRight, edge1, edge2, y1, y2, left1, left2)
909 register LineFacePtr pLeft, pRight;
910 PolyEdgePtr edge1, edge2;
916 denom = - pLeft->dx * (double)pRight->dy + pRight->dx * (double)pLeft->dy;
920 pLeft->xa = -pLeft->xa;
921 pLeft->ya = -pLeft->ya;
925 pRight->xa = -pRight->xa;
926 pRight->ya = -pRight->ya;
928 *y1 = miRoundJoinFace (pLeft, edge1, left1);
929 *y2 = miRoundJoinFace (pRight, edge2, left2);
933 miRoundCapClip (face, isInt, edge, leftEdge)
934 register LineFacePtr face;
936 register PolyEdgePtr edge;
952 if (dy < 0 || dy == 0 && dx > 0)
960 if (dx == 0 && dy == 0)
964 y = ICEIL (face->ya) + face->y;
975 y = miPolyBuildEdge (xa, ya, k, dx, dy, face->x, face->y, !left, edge);
976 edge->height = 32767;
983 miLineArc (pDraw, pGC, pixel, spanData, leftFace, rightFace, xorg, yorg, isInt)
987 SpanDataPtr spanData;
988 register LineFacePtr leftFace, rightFace;
998 PolyEdgeRec edge1, edge2;
1000 Bool edgeleft1, edgeleft2;
1004 xorgi = leftFace ? leftFace->x : rightFace->x;
1005 yorgi = leftFace ? leftFace->y : rightFace->y;
1009 edge1.x = 0; /* not used, keep memory checkers happy */
1011 edge2.x = 0; /* not used, keep memory checkers happy */
1015 if ((pGC->lineStyle != LineSolid || pGC->lineWidth > 2) &&
1016 (pGC->capStyle == CapRound && pGC->joinStyle != JoinRound ||
1017 pGC->joinStyle == JoinRound && pGC->capStyle == CapButt))
1021 xorg = (double) xorgi;
1022 yorg = (double) yorgi;
1024 if (leftFace && rightFace)
1026 miRoundJoinClip (leftFace, rightFace, &edge1, &edge2,
1027 &edgey1, &edgey2, &edgeleft1, &edgeleft2);
1031 edgey1 = miRoundCapClip (leftFace, isInt, &edge1, &edgeleft1);
1035 edgey2 = miRoundCapClip (rightFace, isInt, &edge2, &edgeleft2);
1041 points = (DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec) * pGC->lineWidth);
1044 widths = (int *)ALLOCATE_LOCAL(sizeof(int) * pGC->lineWidth);
1047 DEALLOCATE_LOCAL(points);
1050 oldPixel = pGC->fgPixel;
1051 if (pixel != oldPixel)
1053 DoChangeGC(pGC, GCForeground, (XID *)&pixel, FALSE);
1054 ValidateGC (pDraw, pGC);
1059 points = (DDXPointPtr) xalloc (pGC->lineWidth * sizeof (DDXPointRec));
1062 widths = (int *) xalloc (pGC->lineWidth * sizeof (int));
1068 spanRec.points = points;
1069 spanRec.widths = widths;
1072 n = miLineArcI(pDraw, pGC, xorgi, yorgi, points, widths);
1074 n = miLineArcD(pDraw, pGC, xorg, yorg, points, widths,
1075 &edge1, edgey1, edgeleft1,
1076 &edge2, edgey2, edgeleft2);
1080 (*pGC->ops->FillSpans)(pDraw, pGC, n, points, widths, TRUE);
1081 DEALLOCATE_LOCAL(widths);
1082 DEALLOCATE_LOCAL(points);
1083 if (pixel != oldPixel)
1085 DoChangeGC(pGC, GCForeground, &oldPixel, FALSE);
1086 ValidateGC (pDraw, pGC);
1092 AppendSpanGroup (pGC, pixel, &spanRec, spanData)
1097 miLineProjectingCap (pDrawable, pGC, pixel, spanData, face, isLeft, xorg, yorg, isInt)
1098 DrawablePtr pDrawable;
1100 unsigned long pixel;
1101 SpanDataPtr spanData;
1102 register LineFacePtr face;
1109 PolyEdgeRec lefts[2], rights[2];
1110 int lefty, righty, topy, bottomy;
1111 PolyEdgePtr left, right;
1112 PolyEdgePtr top, bottom;
1117 double projectXoff, projectYoff;
1126 lw = pGC->lineWidth;
1132 lefts[0].height = lw;
1135 lefts[0].x -= (lw >> 1);
1137 lefts[0].signdx = 1;
1141 rights[0].height = lw;
1142 rights[0].x = xorgi;
1144 rights[0].x += (lw + 1 >> 1);
1145 rights[0].stepx = 0;
1146 rights[0].signdx = 1;
1150 miFillPolyHelper (pDrawable, pGC, pixel, spanData, yorgi - (lw >> 1), lw,
1151 lefts, rights, 1, 1);
1156 bottomy = yorgi + dy;
1160 bottomy += (lw >> 1);
1161 lefts[0].height = bottomy - topy;
1162 lefts[0].x = xorgi - (lw >> 1);
1164 lefts[0].signdx = 1;
1169 rights[0].height = bottomy - topy;
1170 rights[0].x = lefts[0].x + (lw-1);
1171 rights[0].stepx = 0;
1172 rights[0].signdx = 1;
1176 miFillPolyHelper (pDrawable, pGC, pixel, spanData, topy, bottomy - topy, lefts, rights, 1, 1);
1196 bottom = &rights[1];
1200 righty = miPolyBuildEdge (xa, ya,
1201 k, dx, dy, xorgi, yorgi, 0, right);
1206 lefty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff,
1207 k, dx, dy, xorgi, yorgi, 1, left);
1213 xap = xa - projectXoff;
1214 yap = ya - projectYoff;
1215 topy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy,
1216 -dy, dx, xorgi, yorgi, dx > 0, top);
1217 bottomy = miPolyBuildEdge (xa, ya,
1218 0.0, -dy, dx, xorgi, yorgi, dx < 0, bottom);
1223 righty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff,
1224 k, dx, dy, xorgi, yorgi, 0, right);
1229 lefty = miPolyBuildEdge (xa, ya,
1230 k, dx, dy, xorgi, yorgi, 1, left);
1236 xap = xa - projectXoff;
1237 yap = ya - projectYoff;
1238 topy = miPolyBuildEdge (xa, ya, 0.0, -dy, dx, xorgi, xorgi, dx > 0, top);
1239 bottomy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy,
1240 -dy, dx, xorgi, xorgi, dx < 0, bottom);
1241 maxy = -ya + projectYoff;
1243 finaly = ICEIL(maxy) + yorgi;
1246 left->height = bottomy - lefty;
1247 right->height = finaly - righty;
1248 top->height = righty - topy;
1252 right->height = bottomy - righty;
1253 left->height = finaly - lefty;
1254 top->height = lefty - topy;
1256 bottom->height = finaly - bottomy;
1257 miFillPolyHelper (pDrawable, pGC, pixel, spanData, topy,
1258 bottom->height + bottomy - topy, lefts, rights, 2, 2);
1263 miWideSegment (pDrawable, pGC, pixel, spanData,
1264 x1, y1, x2, y2, projectLeft, projectRight, leftFace, rightFace)
1265 DrawablePtr pDrawable;
1267 unsigned long pixel;
1268 SpanDataPtr spanData;
1269 register int x1, y1, x2, y2;
1270 Bool projectLeft, projectRight;
1271 register LineFacePtr leftFace, rightFace;
1275 double projectXoff, projectYoff;
1281 PolyEdgePtr left, right;
1282 PolyEdgePtr top, bottom;
1283 int lefty, righty, topy, bottomy;
1285 PolyEdgeRec lefts[2], rights[2];
1287 int lw = pGC->lineWidth;
1289 /* draw top-to-bottom always */
1290 if (y2 < y1 || y2 == y1 && x2 < x1)
1301 projectLeft = projectRight;
1305 leftFace = rightFace;
1322 rightFace->dx = -dx;
1323 rightFace->dy = -dy;
1328 rightFace->ya = (double) lw / 2.0;
1329 rightFace->k = -(double) (lw * dx) / 2.0;
1331 leftFace->ya = -rightFace->ya;
1332 leftFace->k = rightFace->k;
1339 dx += (lw + 1 >> 1);
1341 miFillRectPolyHelper (pDrawable, pGC, pixel, spanData,
1346 leftFace->xa = (double) lw / 2.0;
1348 leftFace->k = (double) (lw * dy) / 2.0;
1349 rightFace->xa = -leftFace->xa;
1351 rightFace->k = leftFace->k;
1358 dy += (lw + 1 >> 1);
1360 miFillRectPolyHelper (pDrawable, pGC, pixel, spanData,
1365 l = ((double) lw) / 2.0;
1366 L = hypot ((double) dx, (double) dy);
1380 bottom = &rights[1];
1384 /* coord of upper bound at integral y */
1388 if (projectLeft | projectRight)
1394 /* xa * dy - ya * dx */
1400 rightFace->xa = -xa;
1401 rightFace->ya = -ya;
1405 righty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff,
1406 k, dx, dy, x1, y1, 0, right);
1408 righty = miPolyBuildEdge (xa, ya,
1409 k, dx, dy, x1, y1, 0, right);
1411 /* coord of lower bound at integral y */
1415 /* xa * dy - ya * dx */
1419 lefty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff,
1420 k, dx, dy, x1, y1, 1, left);
1422 lefty = miPolyBuildEdge (xa, ya,
1423 k, dx, dy, x1, y1, 1, left);
1425 /* coord of top face at integral y */
1435 double xap = xa - projectXoff;
1436 double yap = ya - projectYoff;
1437 topy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy,
1438 -dy, dx, x1, y1, dx > 0, top);
1441 topy = miPolyBuildEdge (xa, ya, 0.0, -dy, dx, x1, y1, dx > 0, top);
1443 /* coord of bottom face at integral y */
1447 double xap = xa + projectXoff;
1448 double yap = ya + projectYoff;
1449 bottomy = miPolyBuildEdge (xap, yap, xap * dx + yap * dy,
1450 -dy, dx, x2, y2, dx < 0, bottom);
1451 maxy = -ya + projectYoff;
1455 bottomy = miPolyBuildEdge (xa, ya,
1456 0.0, -dy, dx, x2, y2, dx < 0, bottom);
1460 finaly = ICEIL (maxy) + y2;
1464 left->height = bottomy - lefty;
1465 right->height = finaly - righty;
1466 top->height = righty - topy;
1470 right->height = bottomy - righty;
1471 left->height = finaly - lefty;
1472 top->height = lefty - topy;
1474 bottom->height = finaly - bottomy;
1475 miFillPolyHelper (pDrawable, pGC, pixel, spanData, topy,
1476 bottom->height + bottomy - topy, lefts, rights, 2, 2);
1481 miSetupSpanData (pGC, spanData, npt)
1483 SpanDataPtr spanData;
1486 if (npt < 3 && pGC->capStyle != CapRound || miSpansEasyRop(pGC->alu))
1487 return (SpanDataPtr) NULL;
1488 if (pGC->lineStyle == LineDoubleDash)
1489 miInitSpanGroup (&spanData->bgGroup);
1490 miInitSpanGroup (&spanData->fgGroup);
1495 miCleanupSpanData (pDrawable, pGC, spanData)
1496 DrawablePtr pDrawable;
1498 SpanDataPtr spanData;
1500 if (pGC->lineStyle == LineDoubleDash)
1502 XID oldPixel, pixel;
1504 pixel = pGC->bgPixel;
1505 oldPixel = pGC->fgPixel;
1506 if (pixel != oldPixel)
1508 DoChangeGC (pGC, GCForeground, &pixel, FALSE);
1509 ValidateGC (pDrawable, pGC);
1511 miFillUniqueSpanGroup (pDrawable, pGC, &spanData->bgGroup);
1512 miFreeSpanGroup (&spanData->bgGroup);
1513 if (pixel != oldPixel)
1515 DoChangeGC (pGC, GCForeground, &oldPixel, FALSE);
1516 ValidateGC (pDrawable, pGC);
1519 miFillUniqueSpanGroup (pDrawable, pGC, &spanData->fgGroup);
1520 miFreeSpanGroup (&spanData->fgGroup);
1524 miWideLine (pDrawable, pGC, mode, npt, pPts)
1525 DrawablePtr pDrawable;
1529 register DDXPointPtr pPts;
1532 SpanDataRec spanDataRec;
1533 SpanDataPtr spanData;
1534 unsigned long pixel;
1535 Bool projectLeft, projectRight;
1536 LineFaceRec leftFace, rightFace, prevRightFace;
1537 LineFaceRec firstFace;
1539 Bool somethingDrawn = FALSE;
1542 spanData = miSetupSpanData (pGC, &spanDataRec, npt);
1543 pixel = pGC->fgPixel;
1550 if (mode == CoordModePrevious)
1553 DDXPointPtr pPtsTmp;
1565 if (x2 == x1 && y2 == y1)
1568 else if (x2 == pPts[npt-1].x && y2 == pPts[npt-1].y)
1573 projectLeft = pGC->capStyle == CapProjecting && !selfJoin;
1574 projectRight = FALSE;
1582 if (mode == CoordModePrevious)
1587 if (x1 != x2 || y1 != y2)
1589 somethingDrawn = TRUE;
1590 if (npt == 1 && pGC->capStyle == CapProjecting && !selfJoin)
1591 projectRight = TRUE;
1592 miWideSegment (pDrawable, pGC, pixel, spanData, x1, y1, x2, y2,
1593 projectLeft, projectRight, &leftFace, &rightFace);
1597 firstFace = leftFace;
1598 else if (pGC->capStyle == CapRound)
1600 if (pGC->lineWidth == 1 && !spanData)
1601 miLineOnePoint (pDrawable, pGC, pixel, spanData, x1, y1);
1603 miLineArc (pDrawable, pGC, pixel, spanData,
1604 &leftFace, (LineFacePtr) NULL,
1605 (double)0.0, (double)0.0,
1611 miLineJoin (pDrawable, pGC, pixel, spanData, &leftFace,
1614 prevRightFace = rightFace;
1616 projectLeft = FALSE;
1618 if (npt == 1 && somethingDrawn)
1621 miLineJoin (pDrawable, pGC, pixel, spanData, &firstFace,
1623 else if (pGC->capStyle == CapRound)
1625 if (pGC->lineWidth == 1 && !spanData)
1626 miLineOnePoint (pDrawable, pGC, pixel, spanData, x2, y2);
1628 miLineArc (pDrawable, pGC, pixel, spanData,
1629 (LineFacePtr) NULL, &rightFace,
1630 (double)0.0, (double)0.0,
1635 /* handle crock where all points are coincedent */
1636 if (!somethingDrawn)
1638 projectLeft = pGC->capStyle == CapProjecting;
1639 miWideSegment (pDrawable, pGC, pixel, spanData,
1640 x2, y2, x2, y2, projectLeft, projectLeft,
1641 &leftFace, &rightFace);
1642 if (pGC->capStyle == CapRound)
1644 miLineArc (pDrawable, pGC, pixel, spanData,
1645 &leftFace, (LineFacePtr) NULL,
1646 (double)0.0, (double)0.0,
1648 rightFace.dx = -1; /* sleezy hack to make it work */
1649 miLineArc (pDrawable, pGC, pixel, spanData,
1650 (LineFacePtr) NULL, &rightFace,
1651 (double)0.0, (double)0.0,
1656 miCleanupSpanData (pDrawable, pGC, spanData);
1665 miWideDashSegment (pDrawable, pGC, spanData, pDashOffset, pDashIndex,
1666 x1, y1, x2, y2, projectLeft, projectRight, leftFace, rightFace)
1667 DrawablePtr pDrawable;
1669 int *pDashOffset, *pDashIndex;
1670 SpanDataPtr spanData;
1672 Bool projectLeft, projectRight;
1673 LineFacePtr leftFace, rightFace;
1675 int dashIndex, dashRemain;
1676 unsigned char *pDash;
1679 PolyVertexRec vertices[4];
1680 PolyVertexRec saveRight, saveBottom;
1681 PolySlopeRec slopes[4];
1682 PolyEdgeRec left[2], right[2];
1683 LineFaceRec lcapFace, rcapFace;
1688 unsigned long pixel;
1692 double dashDx, dashDy;
1695 double lcenterx, lcentery, rcenterx, rcentery;
1696 unsigned long fgPixel, bgPixel;
1700 dashIndex = *pDashIndex;
1702 dashRemain = pDash[dashIndex] - *pDashOffset;
1703 fgPixel = pGC->fgPixel;
1704 bgPixel = pGC->bgPixel;
1705 if (pGC->fillStyle == FillOpaqueStippled ||
1706 pGC->fillStyle == FillTiled)
1711 l = ((double) pGC->lineWidth) / 2.0;
1736 L = hypot ((double) dx, (double) dy);
1744 /* All position comments are relative to a line with dx and dy > 0,
1745 * but the code does not depend on this */
1747 slopes[V_TOP].dx = dx;
1748 slopes[V_TOP].dy = dy;
1749 slopes[V_TOP].k = k;
1751 slopes[V_RIGHT].dx = -dy;
1752 slopes[V_RIGHT].dy = dx;
1753 slopes[V_RIGHT].k = 0;
1755 slopes[V_BOTTOM].dx = -dx;
1756 slopes[V_BOTTOM].dy = -dy;
1757 slopes[V_BOTTOM].k = k;
1759 slopes[V_LEFT].dx = dy;
1760 slopes[V_LEFT].dy = -dx;
1761 slopes[V_LEFT].k = 0;
1763 /* preload the start coordinates */
1764 vertices[V_RIGHT].x = vertices[V_TOP].x = rdy;
1765 vertices[V_RIGHT].y = vertices[V_TOP].y = -rdx;
1767 vertices[V_BOTTOM].x = vertices[V_LEFT].x = -rdy;
1768 vertices[V_BOTTOM].y = vertices[V_LEFT].y = rdx;
1772 vertices[V_TOP].x -= rdx;
1773 vertices[V_TOP].y -= rdy;
1775 vertices[V_LEFT].x -= rdx;
1776 vertices[V_LEFT].y -= rdy;
1778 slopes[V_LEFT].k = rdx * dx + rdy * dy;
1784 if (pGC->capStyle == CapRound)
1796 while (LRemain > dashRemain)
1798 dashDx = (dashRemain * dx) / L;
1799 dashDy = (dashRemain * dy) / L;
1801 rcenterx = lcenterx + dashDx;
1802 rcentery = lcentery + dashDy;
1804 vertices[V_RIGHT].x += dashDx;
1805 vertices[V_RIGHT].y += dashDy;
1807 vertices[V_BOTTOM].x += dashDx;
1808 vertices[V_BOTTOM].y += dashDy;
1810 slopes[V_RIGHT].k = vertices[V_RIGHT].x * dx + vertices[V_RIGHT].y * dy;
1812 if (pGC->lineStyle == LineDoubleDash || !(dashIndex & 1))
1814 if (pGC->lineStyle == LineOnOffDash &&
1815 pGC->capStyle == CapProjecting)
1817 saveRight = vertices[V_RIGHT];
1818 saveBottom = vertices[V_BOTTOM];
1819 saveK = slopes[V_RIGHT].k;
1823 vertices[V_TOP].x -= rdx;
1824 vertices[V_TOP].y -= rdy;
1826 vertices[V_LEFT].x -= rdx;
1827 vertices[V_LEFT].y -= rdy;
1829 slopes[V_LEFT].k = vertices[V_LEFT].x *
1831 vertices[V_LEFT].y *
1835 vertices[V_RIGHT].x += rdx;
1836 vertices[V_RIGHT].y += rdy;
1838 vertices[V_BOTTOM].x += rdx;
1839 vertices[V_BOTTOM].y += rdy;
1841 slopes[V_RIGHT].k = vertices[V_RIGHT].x *
1842 slopes[V_RIGHT].dy -
1843 vertices[V_RIGHT].y *
1846 y = miPolyBuildPoly (vertices, slopes, 4, x1, y1,
1847 left, right, &nleft, &nright, &h);
1848 pixel = (dashIndex & 1) ? bgPixel : fgPixel;
1849 miFillPolyHelper (pDrawable, pGC, pixel, spanData, y, h, left, right, nleft, nright);
1851 if (pGC->lineStyle == LineOnOffDash)
1853 switch (pGC->capStyle)
1856 vertices[V_BOTTOM] = saveBottom;
1857 vertices[V_RIGHT] = saveRight;
1858 slopes[V_RIGHT].k = saveK;
1865 lcapFace.xa = -vertices[V_LEFT].x;
1866 lcapFace.ya = -vertices[V_LEFT].y;
1867 lcapFace.k = slopes[V_LEFT].k;
1871 lcapFace.xa = vertices[V_TOP].x;
1872 lcapFace.ya = vertices[V_TOP].y;
1873 lcapFace.k = -slopes[V_LEFT].k;
1875 miLineArc (pDrawable, pGC, pixel, spanData,
1876 &lcapFace, (LineFacePtr) NULL,
1877 lcenterx, lcentery, FALSE);
1881 rcapFace.xa = vertices[V_BOTTOM].x;
1882 rcapFace.ya = vertices[V_BOTTOM].y;
1883 rcapFace.k = slopes[V_RIGHT].k;
1887 rcapFace.xa = -vertices[V_RIGHT].x;
1888 rcapFace.ya = -vertices[V_RIGHT].y;
1889 rcapFace.k = -slopes[V_RIGHT].k;
1891 miLineArc (pDrawable, pGC, pixel, spanData,
1892 (LineFacePtr) NULL, &rcapFace,
1893 rcenterx, rcentery, FALSE);
1898 LRemain -= dashRemain;
1900 if (dashIndex == pGC->numInDashList)
1902 dashRemain = pDash[dashIndex];
1904 lcenterx = rcenterx;
1905 lcentery = rcentery;
1907 vertices[V_TOP] = vertices[V_RIGHT];
1908 vertices[V_LEFT] = vertices[V_BOTTOM];
1909 slopes[V_LEFT].k = -slopes[V_RIGHT].k;
1913 if (pGC->lineStyle == LineDoubleDash || !(dashIndex & 1))
1915 vertices[V_TOP].x -= dx;
1916 vertices[V_TOP].y -= dy;
1918 vertices[V_LEFT].x -= dx;
1919 vertices[V_LEFT].y -= dy;
1921 vertices[V_RIGHT].x = rdy;
1922 vertices[V_RIGHT].y = -rdx;
1924 vertices[V_BOTTOM].x = -rdy;
1925 vertices[V_BOTTOM].y = rdx;
1930 vertices[V_RIGHT].x += rdx;
1931 vertices[V_RIGHT].y += rdy;
1933 vertices[V_BOTTOM].x += rdx;
1934 vertices[V_BOTTOM].y += rdy;
1935 slopes[V_RIGHT].k = vertices[V_RIGHT].x *
1936 slopes[V_RIGHT].dy -
1937 vertices[V_RIGHT].y *
1941 slopes[V_RIGHT].k = 0;
1943 if (!first && pGC->lineStyle == LineOnOffDash &&
1944 pGC->capStyle == CapProjecting)
1946 vertices[V_TOP].x -= rdx;
1947 vertices[V_TOP].y -= rdy;
1949 vertices[V_LEFT].x -= rdx;
1950 vertices[V_LEFT].y -= rdy;
1951 slopes[V_LEFT].k = vertices[V_LEFT].x *
1953 vertices[V_LEFT].y *
1957 slopes[V_LEFT].k += dx * dx + dy * dy;
1960 y = miPolyBuildPoly (vertices, slopes, 4, x2, y2,
1961 left, right, &nleft, &nright, &h);
1963 pixel = (dashIndex & 1) ? pGC->bgPixel : pGC->fgPixel;
1964 miFillPolyHelper (pDrawable, pGC, pixel, spanData, y, h, left, right, nleft, nright);
1965 if (!first && pGC->lineStyle == LineOnOffDash &&
1966 pGC->capStyle == CapRound)
1972 lcapFace.xa = -vertices[V_LEFT].x;
1973 lcapFace.ya = -vertices[V_LEFT].y;
1974 lcapFace.k = slopes[V_LEFT].k;
1978 lcapFace.xa = vertices[V_TOP].x;
1979 lcapFace.ya = vertices[V_TOP].y;
1980 lcapFace.k = -slopes[V_LEFT].k;
1982 miLineArc (pDrawable, pGC, pixel, spanData,
1983 &lcapFace, (LineFacePtr) NULL,
1984 rcenterx, rcentery, FALSE);
1987 dashRemain = ((double) dashRemain) - LRemain;
1988 if (dashRemain == 0)
1991 if (dashIndex == pGC->numInDashList)
1993 dashRemain = pDash[dashIndex];
2001 leftFace->ya = -rdx;
2006 rightFace->dx = -dx;
2007 rightFace->dy = -dy;
2008 rightFace->xa = -rdy;
2009 rightFace->ya = rdx;
2012 *pDashIndex = dashIndex;
2013 *pDashOffset = pDash[dashIndex] - dashRemain;
2017 miWideDash (pDrawable, pGC, mode, npt, pPts)
2018 DrawablePtr pDrawable;
2022 register DDXPointPtr pPts;
2025 unsigned long pixel;
2026 Bool projectLeft, projectRight;
2027 LineFaceRec leftFace, rightFace, prevRightFace;
2028 LineFaceRec firstFace;
2030 int dashIndex, dashOffset;
2031 register int prevDashIndex;
2032 SpanDataRec spanDataRec;
2033 SpanDataPtr spanData;
2034 Bool somethingDrawn = FALSE;
2036 Bool endIsFg, startIsFg, firstIsFg = FALSE, prevIsFg;
2038 /* XXX backward compatibility */
2039 if (pGC->lineWidth == 0)
2041 miZeroDashLine (pDrawable, pGC, mode, npt, pPts);
2044 if (pGC->lineStyle == LineDoubleDash &&
2045 (pGC->fillStyle == FillOpaqueStippled || pGC->fillStyle == FillTiled))
2047 miWideLine (pDrawable, pGC, mode, npt, pPts);
2052 spanData = miSetupSpanData (pGC, &spanDataRec, npt);
2057 if (mode == CoordModePrevious)
2060 DDXPointPtr pPtsTmp;
2072 if (x2 == x1 && y2 == y1)
2075 else if (x2 == pPts[npt-1].x && y2 == pPts[npt-1].y)
2079 projectLeft = pGC->capStyle == CapProjecting && !selfJoin;
2080 projectRight = FALSE;
2083 miStepDash ((int)pGC->dashOffset, &dashIndex,
2084 pGC->dash, (int)pGC->numInDashList, &dashOffset);
2092 if (mode == CoordModePrevious)
2097 if (x1 != x2 || y1 != y2)
2099 somethingDrawn = TRUE;
2100 if (npt == 1 && pGC->capStyle == CapProjecting &&
2101 (!selfJoin || !firstIsFg))
2102 projectRight = TRUE;
2103 prevDashIndex = dashIndex;
2104 miWideDashSegment (pDrawable, pGC, spanData, &dashOffset, &dashIndex,
2106 projectLeft, projectRight, &leftFace, &rightFace);
2107 startIsFg = !(prevDashIndex & 1);
2108 endIsFg = (dashIndex & 1) ^ (dashOffset != 0);
2109 if (pGC->lineStyle == LineDoubleDash || startIsFg)
2111 pixel = startIsFg ? pGC->fgPixel : pGC->bgPixel;
2112 if (first || (pGC->lineStyle == LineOnOffDash && !prevIsFg))
2114 if (first && selfJoin)
2116 firstFace = leftFace;
2117 firstIsFg = startIsFg;
2119 else if (pGC->capStyle == CapRound)
2120 miLineArc (pDrawable, pGC, pixel, spanData,
2121 &leftFace, (LineFacePtr) NULL,
2122 (double)0.0, (double)0.0, TRUE);
2126 miLineJoin (pDrawable, pGC, pixel, spanData, &leftFace,
2130 prevRightFace = rightFace;
2133 projectLeft = FALSE;
2135 if (npt == 1 && somethingDrawn)
2137 if (pGC->lineStyle == LineDoubleDash || endIsFg)
2139 pixel = endIsFg ? pGC->fgPixel : pGC->bgPixel;
2140 if (selfJoin && (pGC->lineStyle == LineDoubleDash || firstIsFg))
2142 miLineJoin (pDrawable, pGC, pixel, spanData, &firstFace,
2147 if (pGC->capStyle == CapRound)
2148 miLineArc (pDrawable, pGC, pixel, spanData,
2149 (LineFacePtr) NULL, &rightFace,
2150 (double)0.0, (double)0.0, TRUE);
2155 /* glue a cap to the start of the line if
2156 * we're OnOffDash and ended on odd dash
2158 if (selfJoin && firstIsFg)
2160 pixel = pGC->fgPixel;
2161 if (pGC->capStyle == CapProjecting)
2162 miLineProjectingCap (pDrawable, pGC, pixel, spanData,
2164 (double)0.0, (double)0.0, TRUE);
2165 else if (pGC->capStyle == CapRound)
2166 miLineArc (pDrawable, pGC, pixel, spanData,
2167 &firstFace, (LineFacePtr) NULL,
2168 (double)0.0, (double)0.0, TRUE);
2173 /* handle crock where all points are coincident */
2174 if (!somethingDrawn && (pGC->lineStyle == LineDoubleDash || !(dashIndex & 1)))
2176 /* not the same as endIsFg computation above */
2177 pixel = (dashIndex & 1) ? pGC->bgPixel : pGC->fgPixel;
2178 switch (pGC->capStyle) {
2180 miLineArc (pDrawable, pGC, pixel, spanData,
2181 (LineFacePtr) NULL, (LineFacePtr) NULL,
2182 (double)x2, (double)y2,
2186 x1 = pGC->lineWidth;
2187 miFillRectPolyHelper (pDrawable, pGC, pixel, spanData,
2188 x2 - (x1 >> 1), y2 - (x1 >> 1), x1, x1);
2193 miCleanupSpanData (pDrawable, pGC, spanData);
2196 /* these are stubs to allow old ddx ValidateGCs to work without change */