1 /* This file is part of the GNU libxmi package.
2
3 Copyright (C) 1985, 1986, 1987, 1988, 1989, X Consortium. For an
4 associated permission notice, see the accompanying file README-X.
5
6 GNU enhancements Copyright (C) 1998, 1999, 2000, 2005, Free Software
7 Foundation, Inc.
8
9 The GNU libxmi package is free software. You may redistribute it
10 and/or modify it under the terms of the GNU General Public License as
11 published by the Free Software foundation; either version 2, or (at your
12 option) any later version.
13
14 The GNU libxmi package is distributed in the hope that it will be
15 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 General Public License for more details.
18
19 You should have received a copy of the GNU General Public License along
20 with the GNU plotutils package; see the file COPYING. If not, write to
21 the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor,
22 Boston, MA 02110-1301, USA. */
23
24 #include "sys-defines.h"
25 #include "extern.h"
26
27 /* Original author: Keith Packard, MIT X Consortium.
28 Hacked by Robert S. Maier, 1998-99. */
29
30 /* This module contains the miWideLine() and miWideDash() functions. They
31 rasterize wide polylines (usually just called `wide lines'), either
32 solid or dashed.
33
34 Any wide line is treated as a polygon to be painted. (If it is dashed,
35 each dash is treated as a polygon.) The painting follows libxmi's
36 policy on painting of `edge' pixels, i.e., pixels that lie exactly on a
37 boundary. A pixel is not painted if it lies on a `right' or `bottom'
38 edge of a polygon.
39
40 All painting goes through the low-level MI_PAINT_SPANS() macro. */
41
42 #include "xmi.h"
43 #include "mi_spans.h"
44 #include "mi_gc.h"
45 #include "mi_api.h"
46 #include "mi_widelin.h"
47
48 /* undefine if hypot is available (it's X_OPEN, but not ANSI or POSIX) */
49 #define hypot(x, y) sqrt((x)*(x) + (y)*(y))
50
51 /* internal functions that do painting of pixels */
52 static void miFillPolyHelper (miPaintedSet *paintedSet, miPixel pixel, int y, unsigned int overall_height, PolyEdge *left, PolyEdge *right, int left_count, int right_count);
53 static void miFillRectPolyHelper (miPaintedSet *paintedSet, miPixel pixel, int x, int y, unsigned int w, unsigned int h);
54 static void miLineArc (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, LineFace *leftFace, LineFace *rightFace, double xorg, double yorg, bool isInt);
55 static void miLineJoin (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, LineFace *pLeft, LineFace *pRight);
56 static void miLineProjectingCap (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, const LineFace *face, bool isLeft, bool isInt);
57 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);
58 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);
59
60 /* internal functions that don't do painting of pixels */
61 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);
62 static int miLineArcI (const miGC *pGC, int xorg, int yorg, miPoint *points, unsigned int *widths);
63 static int miPolyBuildEdge (double x0, double y0, double k, int dx, int dy, int xi, int yi, bool left, PolyEdge *edge);
64 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);
65 static int miRoundCapClip (const LineFace *face, bool isInt, PolyEdge *edge, bool *leftEdge);
66 static int miRoundJoinFace (const LineFace *face, PolyEdge *edge, bool *leftEdge);
67 static void miRoundJoinClip (LineFace *pLeft, LineFace *pRight, PolyEdge *edge1, PolyEdge *edge2, int *y1, int *y2, bool *left1, bool *left2);
68
69 /* Spans-based convex polygon filler. Paints a convex polygon, supplied as
70 lists of `left' and `right' edges. Used for painting polygonal line
71 caps and line joins.
72
73 This implements libxmi's policy on painting `edge' pixels, i.e., pixels
74 that lie exactly on the boundary of a polygon. A pixel is not painted
75 if it lies on a `right' or `bottom' edge of the polygon. */
76
77 /* ARGS: y = starting y coor, overall_height = height of entire segment */
78 static void
miFillPolyHelper(miPaintedSet * paintedSet,miPixel pixel,int y,unsigned int overall_height,PolyEdge * left,PolyEdge * right,int left_count,int right_count)79 miFillPolyHelper (miPaintedSet *paintedSet, miPixel pixel, int y, unsigned int overall_height, PolyEdge *left, PolyEdge *right, int left_count, int right_count)
80 {
81 int left_x = 0, left_e = 0;
82 int left_stepx = 0;
83 int left_signdx = 0;
84 int left_dy = 0, left_dx = 0;
85
86 int right_x = 0, right_e = 0;
87 int right_stepx = 0;
88 int right_signdx = 0;
89 int right_dy = 0, right_dx = 0;
90
91 unsigned int left_height = 0, right_height = 0;
92
93 miPoint *ppt;
94 miPoint *pptInit = (miPoint *)NULL;
95 unsigned int *pwidth;
96 unsigned int *pwidthInit = (unsigned int *)NULL;
97
98 pptInit = (miPoint *)mi_xmalloc(overall_height * sizeof(miPoint));
99 pwidthInit = (unsigned int *)mi_xmalloc(overall_height * sizeof(unsigned int));
100 ppt = pptInit;
101 pwidth = pwidthInit;
102
103 while ((left_count || left_height) && (right_count || right_height))
104 {
105 unsigned int height;
106
107 /* load fields from next left edge, right edge */
108 MIPOLYRELOADLEFT
109 MIPOLYRELOADRIGHT
110
111 height = UMIN (left_height, right_height);
112 left_height -= height;
113 right_height -= height;
114 /* walk down to end of left or right edge, whichever comes first */
115 while (height--)
116 {
117 if (right_x >= left_x)
118 /* generate a span (omitting point on right end, see above) */
119 {
120 ppt->x = left_x;
121 ppt->y = y;
122 ppt++;
123 *pwidth++ = (unsigned int)(right_x - left_x + 1);
124 }
125 y++;
126
127 /* update left_x, right_x by stepping along left and right edges,
128 using midpoint line algorithm */
129 MIPOLYSTEPLEFT
130 MIPOLYSTEPRIGHT
131 }
132 }
133
134 MI_PAINT_SPANS(paintedSet, pixel, ppt - pptInit, pptInit, pwidthInit)
135 }
136
137 /* Rectangle filler. Policy mentioned above (no painting of right or
138 bottom edges) is followed. */
139
140 static void
miFillRectPolyHelper(miPaintedSet * paintedSet,miPixel pixel,int x,int y,unsigned int w,unsigned int h)141 miFillRectPolyHelper (miPaintedSet *paintedSet, miPixel pixel, int x, int y, unsigned int w, unsigned int h)
142 {
143 miPoint *ppt, *pptInit;
144 unsigned int *pwidth, *pwidthInit;
145
146 pptInit = (miPoint *)mi_xmalloc (h * sizeof(miPoint));
147 pwidthInit = (unsigned int *)mi_xmalloc (h * sizeof(unsigned int));
148 ppt = pptInit;
149 pwidth = pwidthInit;
150 while (h--)
151 {
152 *pwidth++ = w;
153 ppt->x = x;
154 ppt->y = y;
155 ppt++;
156 y++;
157 }
158
159 MI_PAINT_SPANS(paintedSet, pixel, ppt - pptInit, pptInit, pwidthInit)
160 }
161
162 /* Build a single polygon edge (either a left edge or a right edge).
163 I.e. compute integer edge data that can be used by the midpoint line
164 algorithm. The edge will be traversed downward (on entry, dy != 0 is
165 assumed). Returns starting value for y, i.e. integer y-value for top of
166 edge. */
167
168 /* Supplied: an integer offset (xi,yi), the exact floating-point edge start
169 (x0,y0), its (rational) slope dy/dx, and the quantity k = x0*dy-y0*dx,
170 which is a measure of distance of (x0,y0) from the parallel line segment
171 that passes through (0,0). k will be transformed into the initial value
172 for e, the integer decision variable for the midpoint line algorithm. */
173
174 /* The integer edge data that are computed do not include the `height'
175 field, i.e. the number of scanlines to process. */
176
177 /* ARGS: x0,y0 = starting point of edge (rel. to x1,y1)
178 k = x0 * dy - y0 * dx
179 dx,dy specify rational slope dy/dx
180 xi,yi = integer offsets for coor system
181 left = left edge, not right edge?
182 edge = integer edge data, to be filled in */
183 /*ARGSUSED*/
184 static int
miPolyBuildEdge(double x0,double y0,double k,int dx,int dy,int xi,int yi,bool left,PolyEdge * edge)185 miPolyBuildEdge (double x0, double y0, double k, int dx, int dy, int xi, int yi, bool left, PolyEdge *edge)
186 {
187 int x, y, e;
188 int xady;
189
190 /* make dy positive, since edge will be traversed downward */
191 if (dy < 0)
192 {
193 dy = -dy;
194 dx = -dx;
195 k = -k;
196 }
197
198 #if 0
199 {
200 double realk, kerror;
201
202 realk = x0 * dy - y0 * dx;
203 kerror = fabs (realk - k);
204 if (kerror > .1)
205 printf ("realk: %g\t k: %g\n", realk, k);
206 }
207 #endif
208
209 /* integer starting value for y: round up the floating-point value */
210 y = ICEIL (y0);
211
212 /* work out integer starting value for x */
213 xady = ICEIL (k) + y * dx;
214 if (xady <= 0)
215 x = - (-xady / dy) - 1;
216 else
217 x = (xady - 1) / dy;
218
219 /* start working out initial value of decision variable */
220 e = xady - x * dy; /* i.e. ICEIL(k) - (x * dy - y * dx) */
221
222 /* work out optional and non-optional x increment, for algorithm */
223 if (dx >= 0)
224 {
225 edge->signdx = 1; /* optional step */
226 edge->stepx = dx / dy; /* non-optional step, 0 if dx<dy in mag. */
227 edge->dx = dx % dy;
228 }
229 else
230 {
231 edge->signdx = -1; /* optional step */
232 edge->stepx = - (-dx / dy); /* non-optional step, 0 if dx<dy in mag. */
233 edge->dx = -dx % dy;
234 e = dy - e + 1;
235 }
236 edge->dy = dy;
237 edge->x = x + (left == true ? 1 : 0) + xi; /* starting value for x */
238 edge->e = e - dy; /* bias: initial value for e */
239
240 /* return integer starting value for y, i.e. top of edge */
241 return y + yi;
242 }
243
244 /* add incr to v, cyclically; always stay in range 0..max */
245 #define StepAround(v, incr, max) (((v) + (incr) < 0) ? (max - 1) : ((v) + (incr) == max) ? 0 : ((v) + (incr)))
246
247 /* Build lists of right and left polygon edges, from an array of vertex
248 coordinates (floating-point), a precomputed array of PolySlopes
249 (including a `k' value for each edge), and an integer offset vector.
250 Also return overall vertical range and top (starting) y value. */
251
252 /* ARGS: xi,yi = integer offset for polygon */
253 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)254 miPolyBuildPoly (const PolyVertex *vertices, const PolySlope *slopes, int count, int xi, int yi, PolyEdge *left, PolyEdge *right, int *pnleft, int *pnright, unsigned int *h)
255 {
256 int top, bottom;
257 double miny, maxy;
258 int i;
259 int j;
260 int clockwise;
261 int slopeoff;
262 int s;
263 int nright, nleft;
264 int y, lasty = 0, bottomy, topy = 0;
265
266 /* compute min, max y values for polygon (floating-point); also location
267 of corresponding vertices in vertex array */
268 maxy = miny = vertices[0].y;
269 bottom = top = 0;
270 for (i = 1; i < count; i++)
271 {
272 if (vertices[i].y < miny)
273 {
274 top = i;
275 miny = vertices[i].y;
276 }
277 if (vertices[i].y >= maxy)
278 {
279 bottom = i;
280 maxy = vertices[i].y;
281 }
282 }
283
284 /* compute integer y-value for bottom of polygon (round up) */
285 bottomy = ICEIL (maxy) + yi;
286
287 /* determine whether should go `clockwise' or `counterclockwise'
288 to move down the right side of the polygon */
289 i = top;
290 j = StepAround (top, -1, count);
291 clockwise = 1;
292 slopeoff = 0;
293 if (slopes[j].dy * slopes[i].dx > slopes[i].dy * slopes[j].dx)
294 {
295 clockwise = -1;
296 slopeoff = -1;
297 }
298
299 /* step around right side of polygon from top to bottom, building array
300 of `right' edges (horizontal edges are ignored) */
301 i = top;
302 s = StepAround (top, slopeoff, count);
303 nright = 0;
304 while (i != bottom)
305 {
306 if (slopes[s].dy != 0)
307 {
308 y = miPolyBuildEdge (vertices[i].x, vertices[i].y,
309 slopes[s].k, slopes[s].dx, slopes[s].dy,
310 xi, yi, false,
311 &right[nright]);
312 if (nright != 0)
313 right[nright-1].height = y - lasty;
314 else /* y is top of first edge */
315 topy = y;
316 nright++;
317 lasty = y;
318 }
319
320 i = StepAround (i, clockwise, count);
321 s = StepAround (s, clockwise, count);
322 }
323 if (nright != 0)
324 right[nright-1].height = bottomy - lasty;
325
326 /* step around left side of polygon from top to bottom, building array of
327 `left' edges (horizontal edges are ignored) */
328 if (slopeoff == 0)
329 slopeoff = -1;
330 else
331 slopeoff = 0;
332 i = top;
333 s = StepAround (top, slopeoff, count);
334 nleft = 0;
335 while (i != bottom)
336 {
337 if (slopes[s].dy != 0)
338 {
339 y = miPolyBuildEdge (vertices[i].x, vertices[i].y,
340 slopes[s].k, slopes[s].dx, slopes[s].dy,
341 xi, yi, true,
342 &left[nleft]);
343
344 if (nleft != 0)
345 left[nleft-1].height = y - lasty;
346 nleft++;
347 lasty = y;
348 }
349
350 i = StepAround (i, -clockwise, count);
351 s = StepAround (s, -clockwise, count);
352 }
353 if (nleft != 0)
354 left[nleft-1].height = bottomy - lasty;
355
356 /* return number of left-side and right-side edges; also height (vertical
357 range, an unsigned int) and the vertical location of the top vertex
358 (an integer) */
359 *pnleft = nleft;
360 *pnright = nright;
361 *h = bottomy - topy;
362
363 return topy;
364 }
365
366 /* Paint all types of line join: round/miter/bevel/triangular. Called by
367 both miWideLine() and miWideDash(). Left and right line faces are
368 supplied, each with its own value of k. They may be modified. */
369 static void
miLineJoin(miPaintedSet * paintedSet,miPixel pixel,const miGC * pGC,LineFace * pLeft,LineFace * pRight)370 miLineJoin (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, LineFace *pLeft, LineFace *pRight)
371 {
372 double mx = 0.0, my = 0.0;
373 int denom = 0; /* avoid compiler warnings */
374 PolyVertex vertices[4];
375 PolySlope slopes[4];
376 int edgecount;
377 PolyEdge left[4], right[4];
378 int nleft, nright;
379 int y;
380 unsigned int height;
381 bool swapslopes;
382 int joinStyle = (int)pGC->joinStyle;
383 int lw = (int)(pGC->lineWidth);
384
385 if (joinStyle == (int)MI_JOIN_ROUND)
386 {
387 /* invoke miLineArc to fill the round join, isInt = true */
388 miLineArc (paintedSet, pixel, pGC,
389 pLeft, pRight, (double)0.0, (double)0.0, true);
390 return;
391 }
392
393 denom = - pLeft->dx * pRight->dy + pRight->dx * pLeft->dy;
394 if (denom == 0)
395 return; /* no join to draw */
396
397 /* Now must handle cases where line join is a small polygon to be filled;
398 specify its vertices clockwise. */
399
400 /* swap slopes if cross product of line faces has wrong sign */
401 if (denom > 0)
402 {
403 swapslopes = false;
404 pLeft->xa = -pLeft->xa;
405 pLeft->ya = -pLeft->ya;
406 pLeft->dx = -pLeft->dx;
407 pLeft->dy = -pLeft->dy;
408 }
409 else
410 {
411 swapslopes = true;
412 pRight->xa = -pRight->xa;
413 pRight->ya = -pRight->ya;
414 pRight->dx = -pRight->dx;
415 pRight->dy = -pRight->dy;
416 }
417
418 /* vertex #0 is at the right end of the right face */
419 vertices[0].x = pRight->xa;
420 vertices[0].y = pRight->ya;
421 slopes[0].dx = -pRight->dy;
422 slopes[0].dy = pRight->dx;
423 slopes[0].k = 0;
424
425 /* vertex #1 is the nominal join point (i.e. halfway across both the
426 right face and the left face) */
427 vertices[1].x = 0;
428 vertices[1].y = 0;
429 slopes[1].dx = pLeft->dy;
430 slopes[1].dy = -pLeft->dx;
431 slopes[1].k = 0;
432
433 /* vertex #2 is at the left end of the left face */
434 vertices[2].x = pLeft->xa;
435 vertices[2].y = pLeft->ya;
436
437 if (joinStyle == (int)MI_JOIN_MITER)
438 {
439 double miterlimit = pGC->miterLimit;
440
441 /* compute vertex (mx,my) of miter quadrilateral */
442 my = (pLeft->dy * (pRight->xa * pRight->dy - pRight->ya * pRight->dx) -
443 pRight->dy * (pLeft->xa * pLeft->dy - pLeft->ya * pLeft->dx )) /
444 (double) denom;
445 if (pLeft->dy != 0)
446 mx = pLeft->xa + (my - pLeft->ya) *
447 (double) pLeft->dx / (double) pLeft->dy;
448 else
449 mx = pRight->xa + (my - pRight->ya) *
450 (double) pRight->dx / (double) pRight->dy;
451 /* if miter limit violated, switch to bevelled join */
452 if ((mx * mx + my * my) * 4 > miterlimit * miterlimit * lw * lw)
453 joinStyle = (int)MI_JOIN_BEVEL;
454 }
455
456 switch ((int)joinStyle)
457 {
458 double scale, dx, dy, adx, ady;
459
460 case (int)MI_JOIN_MITER:
461 default:
462 /* join by adding a quadrilateral */
463 edgecount = 4;
464
465 slopes[2].dx = pLeft->dx;
466 slopes[2].dy = pLeft->dy;
467 slopes[2].k = pLeft->k;
468 if (swapslopes)
469 {
470 slopes[2].dx = -slopes[2].dx;
471 slopes[2].dy = -slopes[2].dy;
472 slopes[2].k = -slopes[2].k;
473 }
474
475 /* vertex #3 is miter vertex (mx,my) */
476 vertices[3].x = mx;
477 vertices[3].y = my;
478 slopes[3].dx = pRight->dx;
479 slopes[3].dy = pRight->dy;
480 slopes[3].k = pRight->k;
481 if (swapslopes)
482 {
483 slopes[3].dx = -slopes[3].dx;
484 slopes[3].dy = -slopes[3].dy;
485 slopes[3].k = -slopes[3].k;
486 }
487 break;
488
489 case (int)MI_JOIN_BEVEL:
490 /* join by adding a triangle */
491 {
492 PolyVertex midpoint;
493
494 edgecount = 3;
495
496 /* third edge of triangle will pass through midpoint */
497 midpoint.x = 0.5 * (pLeft->xa + pRight->xa);
498 midpoint.y = 0.5 * (pLeft->ya + pRight->ya);
499
500 /* vector along third edge of triangle */
501 dx = pRight->xa - pLeft->xa;
502 dy = pRight->ya - pLeft->ya;
503
504 /* compute scale = max(|dx|,|dy|) */
505 adx = dx;
506 ady = dy;
507 if (adx < 0)
508 adx = -adx;
509 if (ady < 0)
510 ady = -ady;
511 scale = ady;
512 if (adx > ady)
513 scale = adx;
514
515 /* use integer dx, dy in range -65536..65536 */
516 slopes[2].dx = (int)((dx * 65536) / scale);
517 slopes[2].dy = (int)((dy * 65536) / scale);
518 slopes[2].k = midpoint.x * slopes[2].dy - midpoint.y * slopes[2].dx;
519 }
520 break;
521
522 case (int)MI_JOIN_TRIANGULAR:
523 /* join by adding a stubby quadrilateral */
524 {
525 PolyVertex midpoint, newpoint;
526 double mid2, mid, dx2, dy2, dx3, dy3;
527
528 edgecount = 4;
529
530 /* compute additional vertex, offset by linewidth/2 */
531 midpoint.x = 0.5 * (pLeft->xa + pRight->xa);
532 midpoint.y = 0.5 * (pLeft->ya + pRight->ya);
533 mid2 = midpoint.x * midpoint.x + midpoint.y * midpoint.y;
534 mid = sqrt (mid2);
535 newpoint.x = 0.5 * lw * midpoint.x / mid;
536 newpoint.y = 0.5 * lw * midpoint.y / mid;
537 vertices[3] = newpoint;
538
539 /* offset from vertices[2] to vertices[3] */
540 dx2 = vertices[3].x - vertices[2].x;
541 dy2 = vertices[3].y - vertices[2].y;
542
543 /* offset from vertices[3] back to vertices[0] */
544 dx3 = vertices[0].x - vertices[3].x;
545 dy3 = vertices[0].y - vertices[3].y;
546
547 /* compute scale = max(|dx|,|dy|), where (dx,dy) is offset between
548 the two corners, i.e. vertices[0] and vertices[2] */
549 dx = pRight->xa - pLeft->xa;
550 dy = pRight->ya - pLeft->ya;
551 adx = dx;
552 ady = dy;
553 if (adx < 0)
554 adx = -adx;
555 if (ady < 0)
556 ady = -ady;
557 scale = ady;
558 if (adx > ady)
559 scale = adx;
560
561 /* use integer dx, dy in range -65536..65536 */
562 slopes[2].dx = (int)((dx2 * 65536) / scale);
563 slopes[2].dy = (int)((dy2 * 65536) / scale);
564 slopes[2].k = newpoint.x * slopes[2].dy - newpoint.y * slopes[2].dx;
565
566 /* use integer dx, dy in range -65536..65536 */
567 slopes[3].dx = (int)((dx3 * 65536) / scale);
568 slopes[3].dy = (int)((dy3 * 65536) / scale);
569 slopes[3].k = newpoint.x * slopes[3].dy - newpoint.y * slopes[3].dx;
570 }
571 break;
572 } /* end of switch */
573
574 /* compute lists of left and right edges for the small polygon, using the
575 just-computed slopes array */
576 y = miPolyBuildPoly (vertices, slopes, edgecount, pLeft->x, pLeft->y,
577 left, right, &nleft, &nright, &height);
578 /* fill the small polygon */
579 miFillPolyHelper (paintedSet, pixel,
580 y, height, left, right, nleft, nright);
581 }
582
583 /* Paint either (1) a round cap on a line face or (2) a pie-wedge between
584 two line faces. Used for round capping and round joining respectively.
585 One or two line faces are supplied. They may be modified. */
586 static void
miLineArc(miPaintedSet * paintedSet,miPixel pixel,const miGC * pGC,LineFace * leftFace,LineFace * rightFace,double xorg,double yorg,bool isInt)587 miLineArc (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, LineFace *leftFace, LineFace *rightFace, double xorg, double yorg, bool isInt)
588 {
589 miPoint *points;
590 unsigned int *widths;
591 int xorgi = 0, yorgi = 0;
592 int n;
593 PolyEdge edge1, edge2;
594 int edgey1, edgey2;
595 bool edgeleft1, edgeleft2;
596
597 if (isInt)
598 /* in integer case, take (xorgi,yorgi) from face; otherwise (0,0) */
599 {
600 xorgi = leftFace ? leftFace->x : rightFace->x;
601 yorgi = leftFace ? leftFace->y : rightFace->y;
602 }
603
604 edgey1 = INT_MAX;
605 edgey2 = INT_MAX;
606 edge1.x = 0; /* not used, keep memory checkers happy */
607 edge1.dy = -1;
608 edge2.x = 0; /* not used, keep memory checkers happy */
609 edge2.dy = -1;
610 edgeleft1 = false;
611 edgeleft2 = false;
612 if ((pGC->lineStyle != (int)MI_LINE_SOLID || pGC->lineWidth > 2)
613 &&
614 ((pGC->capStyle == (int)MI_CAP_ROUND && pGC->joinStyle != (int)MI_JOIN_ROUND)
615 ||
616 (pGC->joinStyle == (int)MI_JOIN_ROUND && pGC->capStyle == (int)MI_CAP_BUTT)))
617 /* construct clipping edges from the passed line faces (otherwise,
618 ignore them; will just draw a disk) */
619 {
620 if (isInt)
621 {
622 xorg = (double) xorgi;
623 yorg = (double) yorgi;
624 }
625 if (leftFace && rightFace)
626 /* have two faces, so construct clipping edges for pie wedge */
627 miRoundJoinClip (leftFace, rightFace, &edge1, &edge2,
628 &edgey1, &edgey2, &edgeleft1, &edgeleft2);
629
630 else if (leftFace)
631 /* will draw half-disk on left face, so construct clipping edge */
632 edgey1 = miRoundCapClip (leftFace, isInt, &edge1, &edgeleft1);
633
634 else if (rightFace)
635 /* will draw half-disk on right face, so construct clipping edge */
636 edgey2 = miRoundCapClip (rightFace, isInt, &edge2, &edgeleft2);
637
638 /* due to clipping, switch to using floating-point coordinates */
639 isInt = false;
640 }
641
642 points = (miPoint *)mi_xmalloc(sizeof(miPoint) * pGC->lineWidth);
643 widths = (unsigned int *)mi_xmalloc(sizeof(unsigned int) * pGC->lineWidth);
644
645 /* construct a Spans by calling integer or floating point routine */
646 if (isInt)
647 /* integer routine, no clipping: just draw a disk */
648 n = miLineArcI (pGC, xorgi, yorgi, points, widths);
649 else
650 /* call floating point routine, supporting clipping by edge(s) */
651 n = miLineArcD (pGC, xorg, yorg, points, widths,
652 &edge1, edgey1, edgeleft1,
653 &edge2, edgey2, edgeleft2);
654
655 MI_PAINT_SPANS(paintedSet, pixel, n, points, widths)
656 }
657
658 /* Draw a filled disk, of diameter equal to the linewidth, as a Spans.
659 This is used for round caps or round joins, if the clipping by one or
660 two edges can be ignored. Integer coordinates only are used. Returns
661 number of spans in the Spans. */
662 static int
miLineArcI(const miGC * pGC,int xorg,int yorg,miPoint * points,unsigned int * widths)663 miLineArcI (const miGC *pGC, int xorg, int yorg, miPoint *points, unsigned int *widths)
664 {
665 miPoint *tpts, *bpts;
666 unsigned int *twids, *bwids;
667 int x, y, e, ex;
668 int slw;
669
670 tpts = points;
671 twids = widths;
672 slw = (int)(pGC->lineWidth);
673 if (slw == 1)
674 /* `disk' is a single pixel */
675 {
676 tpts->x = xorg;
677 tpts->y = yorg;
678 *twids = 1;
679 return 1;
680 }
681
682 /* otherwise, draw the disk scanline by scanline */
683 bpts = tpts + slw;
684 bwids = twids + slw;
685 y = (slw >> 1) + 1;
686 if (slw & 1)
687 e = - ((y << 2) + 3);
688 else
689 e = - (y << 3);
690 ex = -4;
691 x = 0;
692 while (y)
693 {
694 e += (y << 3) - 4;
695 while (e >= 0)
696 {
697 x++;
698 e += (ex = -((x << 3) + 4));
699 }
700 y--;
701 slw = (x << 1) + 1;
702 if ((e == ex) && (slw > 1))
703 slw--;
704 tpts->x = xorg - x;
705 tpts->y = yorg - y;
706 tpts++;
707 *twids++ = slw;
708 if ((y != 0) && ((slw > 1) || (e != ex)))
709 {
710 bpts--;
711 bpts->x = xorg - x;
712 bpts->y = yorg + y;
713 *--bwids = slw;
714 }
715 }
716
717 /* return linewidth (no. of spans in the Spans) */
718 return (int)(pGC->lineWidth);
719 }
720
721 #define CLIPSTEPEDGE(edgey,edge,edgeleft) \
722 if (ybase == edgey) \
723 { \
724 if (edgeleft) \
725 { \
726 if (edge->x > xcl) \
727 xcl = edge->x; \
728 } \
729 else \
730 { \
731 if (edge->x < xcr) \
732 xcr = edge->x; \
733 } \
734 edgey++; \
735 edge->x += edge->stepx; \
736 edge->e += edge->dx; \
737 if (edge->e > 0) \
738 { \
739 edge->x += edge->signdx; \
740 edge->e -= edge->dy; \
741 } \
742 }
743
744 /* Draw as a Spans a filled disk of diameter equal to the linewidth, paying
745 attention to one or two clipping edges. This is used for round caps and
746 round joins, respectively (it respectively yields a half-disk or a pie
747 wedge). Floating point coordinates are used. Returns number of spans
748 in the Spans. The clipping edges may be modified. */
749 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)750 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)
751 {
752 miPoint *pts;
753 unsigned int *wids;
754 double radius, x0, y0, el, er, yk, xlk, xrk, k;
755 int xbase, ybase, y, boty, xl, xr, xcl, xcr;
756 int ymin, ymax;
757 bool edge1IsMin, edge2IsMin;
758 int ymin1, ymin2;
759
760 pts = points;
761 wids = widths;
762 xbase = (int)(floor(xorg));
763 x0 = xorg - xbase;
764 ybase = ICEIL (yorg);
765 y0 = yorg - ybase;
766 xlk = x0 + x0 + 1.0;
767 xrk = x0 + x0 - 1.0;
768 yk = y0 + y0 - 1.0;
769 radius = 0.5 * ((double)pGC->lineWidth);
770 y = (int)(floor(radius - y0 + 1.0));
771 ybase -= y;
772 ymin = ybase;
773 ymax = INT_MAX;
774 edge1IsMin = false;
775 ymin1 = edgey1;
776 if (edge1->dy >= 0)
777 {
778 if (!edge1->dy)
779 {
780 if (edgeleft1)
781 edge1IsMin = true;
782 else
783 ymax = edgey1;
784 edgey1 = INT_MAX;
785 }
786 else
787 {
788 if ((edge1->signdx < 0) == edgeleft1)
789 edge1IsMin = true;
790 }
791 }
792 edge2IsMin = false;
793 ymin2 = edgey2;
794 if (edge2->dy >= 0)
795 {
796 if (!edge2->dy)
797 {
798 if (edgeleft2)
799 edge2IsMin = true;
800 else
801 ymax = edgey2;
802 edgey2 = INT_MAX;
803 }
804 else
805 {
806 if ((edge2->signdx < 0) == edgeleft2)
807 edge2IsMin = true;
808 }
809 }
810 if (edge1IsMin)
811 {
812 ymin = ymin1;
813 if (edge2IsMin && ymin1 > ymin2)
814 ymin = ymin2;
815 }
816 else if (edge2IsMin)
817 ymin = ymin2;
818 el = radius * radius - ((y + y0) * (y + y0)) - (x0 * x0);
819 er = el + xrk;
820 xl = 1;
821 xr = 0;
822 if (x0 < 0.5)
823 {
824 xl = 0;
825 el -= xlk;
826 }
827 boty = (y0 < -0.5) ? 1 : 0;
828 if (ybase + y - boty > ymax)
829 boty = ymax - ybase - y;
830 while (y > boty)
831 {
832 k = (y << 1) + yk;
833 er += k;
834 while (er > 0.0)
835 {
836 xr++;
837 er += xrk - (xr << 1);
838 }
839 el += k;
840 while (el >= 0.0)
841 {
842 xl--;
843 el += (xl << 1) - xlk;
844 }
845 y--;
846 ybase++;
847 if (ybase < ymin)
848 continue;
849 xcl = xl + xbase;
850 xcr = xr + xbase;
851 CLIPSTEPEDGE(edgey1, edge1, edgeleft1);
852 CLIPSTEPEDGE(edgey2, edge2, edgeleft2);
853 if (xcr >= xcl)
854 {
855 pts->x = xcl;
856 pts->y = ybase;
857 pts++;
858 *wids++ = (unsigned int)(xcr - xcl + 1);
859 }
860 }
861 er = xrk - (xr << 1) - er;
862 el = (xl << 1) - xlk - el;
863 boty = (int)(floor(-y0 - radius + 1.0));
864 if (ybase + y - boty > ymax)
865 boty = ymax - ybase - y;
866 while (y > boty)
867 {
868 k = (y << 1) + yk;
869 er -= k;
870 while ((er >= 0.0) && (xr >= 0))
871 {
872 xr--;
873 er += xrk - (xr << 1);
874 }
875 el -= k;
876 while ((el > 0.0) && (xl <= 0))
877 {
878 xl++;
879 el += (xl << 1) - xlk;
880 }
881 y--;
882 ybase++;
883 if (ybase < ymin)
884 continue;
885 xcl = xl + xbase;
886 xcr = xr + xbase;
887 CLIPSTEPEDGE(edgey1, edge1, edgeleft1);
888 CLIPSTEPEDGE(edgey2, edge2, edgeleft2);
889 if (xcr >= xcl)
890 {
891 pts->x = xcl;
892 pts->y = ybase;
893 pts++;
894 *wids++ = (unsigned int)(xcr - xcl + 1);
895 }
896 }
897
898 /* return number of spans in the Spans */
899 return (pts - points);
900 }
901
902 /* From two line faces, construct clipping edges that will be used by
903 miLineArcD when drawing a pie wedge. The line faces may be modified. */
904 static void
miRoundJoinClip(LineFace * pLeft,LineFace * pRight,PolyEdge * edge1,PolyEdge * edge2,int * y1,int * y2,bool * left1,bool * left2)905 miRoundJoinClip (LineFace *pLeft, LineFace *pRight, PolyEdge *edge1, PolyEdge *edge2, int *y1, int *y2, bool *left1, bool *left2)
906 {
907 int denom;
908
909 denom = - pLeft->dx * pRight->dy + pRight->dx * pLeft->dy;
910 if (denom >= 0)
911 {
912 pLeft->xa = -pLeft->xa;
913 pLeft->ya = -pLeft->ya;
914 }
915 else
916 {
917 pRight->xa = -pRight->xa;
918 pRight->ya = -pRight->ya;
919 }
920 *y1 = miRoundJoinFace (pLeft, edge1, left1);
921 *y2 = miRoundJoinFace (pRight, edge2, left2);
922 }
923
924 /* helper function called by the preceding */
925 static int
miRoundJoinFace(const LineFace * face,PolyEdge * edge,bool * leftEdge)926 miRoundJoinFace (const LineFace *face, PolyEdge *edge, bool *leftEdge)
927 {
928 int y;
929 int dx, dy;
930 double xa, ya;
931 bool left;
932
933 dx = -face->dy;
934 dy = face->dx;
935 xa = face->xa;
936 ya = face->ya;
937 left = true;
938 if (ya > 0)
939 {
940 ya = 0.0;
941 xa = 0.0;
942 }
943 if (dy < 0 || (dy == 0 && dx > 0))
944 {
945 dx = -dx;
946 dy = -dy;
947 left = (left ? false : true);
948 }
949 if (dx == 0 && dy == 0)
950 dy = 1;
951 if (dy == 0)
952 {
953 y = ICEIL (face->ya) + face->y;
954 edge->x = INT_MIN;
955 edge->stepx = 0;
956 edge->signdx = 0;
957 edge->e = -1;
958 edge->dy = 0;
959 edge->dx = 0;
960 edge->height = 0;
961 }
962 else
963 {
964 y = miPolyBuildEdge (xa, ya,
965 0.0, dx, dy,
966 face->x, face->y, (left ? false : true), edge);
967 edge->height = UINT_MAX; /* number of scanlines to process */
968 }
969 *leftEdge = (left ? false : true);
970
971 return y;
972 }
973
974 /* From a line face, construct a clipping edge that will be used by
975 miLineArcD when drawing a half-disk. */
976 static int
miRoundCapClip(const LineFace * face,bool isInt,PolyEdge * edge,bool * leftEdge)977 miRoundCapClip (const LineFace *face, bool isInt, PolyEdge *edge, bool *leftEdge)
978 {
979 int y;
980 int dx, dy;
981 double xa, ya, k;
982 bool left;
983
984 dx = -face->dy;
985 dy = face->dx;
986 xa = face->xa;
987 ya = face->ya;
988 k = 0.0;
989 if (!isInt)
990 k = face->k;
991 left = true;
992 if (dy < 0 || (dy == 0 && dx > 0))
993 {
994 dx = -dx;
995 dy = -dy;
996 xa = -xa;
997 ya = -ya;
998 left = (left ? false : true);
999 }
1000 if (dx == 0 && dy == 0)
1001 dy = 1;
1002 if (dy == 0)
1003 {
1004 y = ICEIL (face->ya) + face->y;
1005 edge->x = INT_MIN;
1006 edge->stepx = 0;
1007 edge->signdx = 0;
1008 edge->e = -1;
1009 edge->dy = 0;
1010 edge->dx = 0;
1011 edge->height = 0;
1012 }
1013 else
1014 {
1015 y = miPolyBuildEdge (xa, ya,
1016 k, dx, dy,
1017 face->x, face->y, (left ? false : true), edge);
1018 edge->height = UINT_MAX; /* number of scanlines to process */
1019 }
1020 *leftEdge = (left ? false : true);
1021
1022 return y;
1023 }
1024
1025 /* Paint a projecting rectangular cap on a line face. Called only by
1026 miWideDash (with isInt = true); not by miWideLine. */
1027 static void
miLineProjectingCap(miPaintedSet * paintedSet,miPixel pixel,const miGC * pGC,const LineFace * face,bool isLeft,bool isInt)1028 miLineProjectingCap (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, const LineFace *face, bool isLeft, bool isInt)
1029 {
1030 int dx, dy;
1031 int topy, bottomy;
1032 int xorgi = 0, yorgi = 0;
1033 int lw = (int)(pGC->lineWidth);
1034 PolyEdge lefts[2], rights[2];
1035
1036 if (isInt)
1037 /* in integer case, take (xorgi,yorgi) from face; otherwise (0,0) */
1038 {
1039 xorgi = face->x;
1040 yorgi = face->y;
1041 }
1042 dx = face->dx;
1043 dy = face->dy;
1044
1045 if (dy == 0)
1046 /* special case: line face is horizontal */
1047 {
1048 lefts[0].height = (unsigned int)lw;
1049 lefts[0].x = xorgi;
1050 if (isLeft)
1051 lefts[0].x -= (lw >> 1);
1052 lefts[0].stepx = 0;
1053 lefts[0].signdx = 1;
1054 lefts[0].e = -lw;
1055 lefts[0].dx = 0;
1056 lefts[0].dy = lw;
1057
1058 rights[0].height = (unsigned int)lw;
1059 rights[0].x = xorgi;
1060 if (!isLeft)
1061 rights[0].x += ((lw + 1) >> 1);
1062 rights[0].stepx = 0;
1063 rights[0].signdx = 1;
1064 rights[0].e = -lw;
1065 rights[0].dx = 0;
1066 rights[0].dy = lw;
1067
1068 /* fill the rectangle (1 left edge, 1 right edge) */
1069 miFillPolyHelper (paintedSet, pixel,
1070 yorgi - (lw >> 1), (unsigned int)lw,
1071 lefts, rights, 1, 1);
1072 }
1073 else if (dx == 0)
1074 /* special case: line face is vertical */
1075 {
1076 topy = yorgi;
1077 bottomy = yorgi + dy;
1078 if (isLeft)
1079 topy -= (lw >> 1);
1080 else
1081 bottomy += (lw >> 1);
1082 lefts[0].height = (unsigned int)(bottomy - topy);
1083 lefts[0].x = xorgi - (lw >> 1);
1084 lefts[0].stepx = 0;
1085 lefts[0].signdx = 1;
1086 lefts[0].e = -dy;
1087 lefts[0].dx = dx;
1088 lefts[0].dy = dy;
1089
1090 rights[0].height = (unsigned int)(bottomy - topy);
1091 rights[0].x = lefts[0].x + (lw - 1);
1092 rights[0].stepx = 0;
1093 rights[0].signdx = 1;
1094 rights[0].e = -dy;
1095 rights[0].dx = dx;
1096 rights[0].dy = dy;
1097
1098 /* fill the rectangle (1 left edge, 1 right edge) */
1099 miFillPolyHelper (paintedSet, pixel, topy,
1100 (unsigned int)(bottomy - topy), lefts, rights, 1, 1);
1101 }
1102 else
1103 /* general case: line face is neither horizontal nor vertical */
1104 {
1105 int lefty, righty;
1106 int finaly;
1107 double xa,ya;
1108 double xap, yap;
1109 double maxy;
1110 double projectXoff, projectYoff;
1111 double k;
1112 PolyEdge *left, *right;
1113 PolyEdge *top, *bottom;
1114
1115 k = face->k;
1116 xa = face->xa;
1117 ya = face->ya;
1118 projectXoff = -ya;
1119 projectYoff = xa;
1120
1121 if (dx < 0)
1122 {
1123 right = &rights[1];
1124 left = &lefts[0];
1125 top = &rights[0];
1126 bottom = &lefts[1];
1127 }
1128 else
1129 {
1130 right = &rights[0];
1131 left = &lefts[1];
1132 top = &lefts[0];
1133 bottom = &rights[1];
1134 }
1135
1136 if (isLeft)
1137 /* cap goes left; build four edges */
1138 {
1139 righty = miPolyBuildEdge (xa, ya,
1140 k, dx, dy,
1141 xorgi, yorgi, false, right);
1142
1143 xa = -xa;
1144 ya = -ya;
1145 k = -k;
1146 lefty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff,
1147 k, dx, dy,
1148 xorgi, yorgi, true, left);
1149 if (dx > 0)
1150 {
1151 ya = -ya;
1152 xa = -xa;
1153 }
1154 xap = xa - projectXoff;
1155 yap = ya - projectYoff;
1156 topy = miPolyBuildEdge (xap, yap,
1157 xap * dx + yap * dy, -dy, dx,
1158 xorgi, yorgi, (dx > 0 ? true : false), top);
1159 bottomy = miPolyBuildEdge (xa, ya,
1160 0.0, -dy, dx,
1161 xorgi, yorgi, (dx < 0 ? true : false), bottom);
1162 maxy = -ya;
1163 }
1164 else
1165 /* cap goes right; build four edges */
1166 {
1167 righty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff,
1168 k, dx, dy,
1169 xorgi, yorgi, false, right);
1170
1171 xa = -xa;
1172 ya = -ya;
1173 k = -k;
1174 lefty = miPolyBuildEdge (xa, ya,
1175 k, dx, dy,
1176 xorgi, yorgi, true, left);
1177 if (dx > 0)
1178 {
1179 ya = -ya;
1180 xa = -xa;
1181 }
1182 xap = xa - projectXoff;
1183 yap = ya - projectYoff;
1184 topy = miPolyBuildEdge (xa, ya,
1185 0.0, -dy, dx,
1186 xorgi, xorgi, (dx > 0 ? true : false), top);
1187 bottomy = miPolyBuildEdge (xap, yap,
1188 xap * dx + yap * dy, -dy, dx,
1189 xorgi, xorgi, (dx < 0 ? true : false), bottom);
1190 maxy = -ya + projectYoff;
1191 }
1192
1193 finaly = ICEIL(maxy) + yorgi;
1194 if (dx < 0)
1195 {
1196 left->height = (unsigned int)(bottomy - lefty);
1197 right->height = (unsigned int)(finaly - righty);
1198 top->height = (unsigned int)(righty - topy);
1199 }
1200 else
1201 {
1202 right->height = (unsigned int)(bottomy - righty);
1203 left->height = (unsigned int)(finaly - lefty);
1204 top->height = (unsigned int)(lefty - topy);
1205 }
1206 bottom->height = (unsigned int)(finaly - bottomy);
1207
1208 /* fill the rectangle (2 left edges, 2 right edges) */
1209 miFillPolyHelper (paintedSet, pixel, topy,
1210 (unsigned int)(bottom->height + bottomy - topy),
1211 lefts, rights, 2, 2);
1212 }
1213 }
1214
1215
1216 /* Draw a wide, dashed polyline, by dashing each line segment and joining
1217 appropriately. miWideDashSegment() is called to dash each line
1218 segment. */
1219 void
miWideDash(miPaintedSet * paintedSet,const miGC * pGC,miCoordMode mode,int npt,const miPoint * pPts)1220 miWideDash (miPaintedSet *paintedSet, const miGC *pGC, miCoordMode mode, int npt, const miPoint *pPts)
1221 {
1222 int x1, y1, x2, y2;
1223 int dashNum; /* absolute number of dash, starts with 0 */
1224 int dashIndex; /* index into array (i.e. dashNum % length) */
1225 int dashOffset; /* offset into selected dash */
1226 int startPaintType, endPaintType = 0, prevEndPaintType = 0;
1227 int firstPaintType = 0; /* used only for closed polylines; will be 1 */
1228 int numPixels;
1229 bool selfJoin; /* polyline is closed? */
1230 bool first; /* first line segment of polyline */
1231 bool somethingDrawn = false;
1232 bool projectLeft, projectRight;
1233 LineFace leftFace, rightFace, prevRightFace;
1234 LineFace firstFace;
1235 miPixel pixel;
1236
1237 /* ensure we have >=1 points */
1238 if (npt <= 0)
1239 return;
1240
1241 /* width 0 lines are handled specially; invoke Bresenham routine in
1242 mi_zerolin.c */
1243 if (pGC->lineWidth == 0)
1244 {
1245 miZeroDash (paintedSet, pGC, mode, npt, pPts);
1246 return;
1247 }
1248
1249 x2 = pPts->x;
1250 y2 = pPts->y;
1251 first = true; /* first line segment of polyline */
1252
1253 /* determine whether polyline is closed */
1254 selfJoin = false;
1255 if (mode == MI_COORD_MODE_PREVIOUS)
1256 {
1257 int nptTmp;
1258 const miPoint *pPtsTmp;
1259
1260 x1 = x2;
1261 y1 = y2;
1262 nptTmp = npt;
1263 pPtsTmp = pPts + 1;
1264 while (--nptTmp)
1265 {
1266 x1 += pPtsTmp->x;
1267 y1 += pPtsTmp->y;
1268 ++pPtsTmp;
1269 }
1270 if (x2 == x1 && y2 == y1)
1271 selfJoin = true;
1272 }
1273 else if (x2 == pPts[npt-1].x && y2 == pPts[npt-1].y)
1274 selfJoin = true;
1275
1276 /* dash segments (except for the last) will not project right; and
1277 (except for the first) will not project left */
1278 projectLeft =
1279 (pGC->capStyle == (int)MI_CAP_PROJECTING && !selfJoin) ? true : false;
1280 projectRight = false;
1281
1282 /* perform initial offsetting into the dash sequence */
1283 dashNum = 0; /* absolute number of dash */
1284 dashIndex = 0; /* index into dash array */
1285 dashOffset = 0; /* index into selected dash */
1286 miStepDash (pGC->dashOffset, &dashNum, &dashIndex,
1287 pGC->dash, pGC->numInDashList, &dashOffset);
1288
1289 /* How many paint types? (Will cycle through 0..numPixels-1, beginning
1290 with 1, with `off' dashes defined as those with paint type #0.) */
1291 numPixels = pGC->numPixels;
1292
1293 /* iterate through points, drawing a dashed segment for each line segment
1294 of nonzero length */
1295 while (--npt)
1296 {
1297 x1 = x2;
1298 y1 = y2;
1299 ++pPts;
1300 x2 = pPts->x;
1301 y2 = pPts->y;
1302 if (mode == MI_COORD_MODE_PREVIOUS)
1303 {
1304 x2 += x1;
1305 y2 += y1;
1306 }
1307
1308 if (x1 != x2 || y1 != y2)
1309 /* have a line segment of nonzero length */
1310 {
1311 int prevDashNum, lastPaintedDashNum;
1312
1313 if (npt == 1 && pGC->capStyle == (int)MI_CAP_PROJECTING
1314 && (!selfJoin || (firstPaintType == 0)))
1315 /* final point; and need a projecting cap here */
1316 projectRight = true;
1317 prevDashNum = dashNum;
1318 /* draw dashed segment, updating dashNum, dashIndex and
1319 dashOffset, returning faces */
1320 miWideDashSegment (paintedSet, pGC,
1321 &dashNum, &dashIndex, &dashOffset,
1322 x1, y1, x2, y2,
1323 projectLeft, projectRight, &leftFace, &rightFace);
1324
1325 /* determine paint types used at start and end of just-drawn
1326 segment */
1327 startPaintType = ((dashNum & 1) ?
1328 0 : 1 + ((dashNum / 2) % (numPixels - 1)));
1329 lastPaintedDashNum = (dashOffset != 0 ? dashNum : dashNum - 1);
1330 endPaintType = ((lastPaintedDashNum & 1) ?
1331 0 : 1 + ((dashNum / 2) % (numPixels - 1)));
1332
1333 /* add round cap or line join at left end of just-drawn segment;
1334 if OnOffDash, do so only if segment began with an `on' dash */
1335 if (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || (startPaintType != 0))
1336 {
1337 pixel = pGC->pixels[startPaintType];
1338 if (first || (pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH
1339 && prevEndPaintType == 0))
1340 /* draw cap at left end, unless this is first segment of a
1341 closed polyline */
1342 {
1343 if (first && selfJoin)
1344 {
1345 firstFace = leftFace;
1346 firstPaintType = startPaintType;
1347 }
1348 else if (pGC->capStyle == (int)MI_CAP_ROUND
1349 || pGC->capStyle == (int)MI_CAP_TRIANGULAR)
1350 /* invoke miLineArc to draw round cap, isInt = true */
1351 miLineArc (paintedSet, pixel, pGC,
1352 &leftFace, (LineFace *)NULL,
1353 (double)0.0, (double)0.0, true);
1354 }
1355 else
1356 /* draw join at left end */
1357 miLineJoin (paintedSet, pixel, pGC,
1358 &leftFace, &prevRightFace);
1359 }
1360
1361 somethingDrawn = true;
1362 first = false;
1363 prevRightFace = rightFace;
1364 prevEndPaintType = endPaintType;
1365 projectLeft = false;
1366 }
1367
1368 if (npt == 1 && somethingDrawn)
1369 /* last point of a nonempty polyline, so add line join or round cap
1370 if appropriate, i.e. if we're doing OnOffDash and ended on an
1371 `on' dash, or if we're doing DoubleDash */
1372 {
1373 if (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || (endPaintType != 0))
1374 {
1375 pixel = pGC->pixels[endPaintType];
1376 if (selfJoin && (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH
1377 || (firstPaintType != 0)))
1378 /* closed, so draw a join */
1379 miLineJoin (paintedSet, pixel, pGC,
1380 &firstFace, &rightFace);
1381 else
1382 {
1383 if (pGC->capStyle == (int)MI_CAP_ROUND
1384 || pGC->capStyle == (int)MI_CAP_TRIANGULAR)
1385 /* invoke miLineArc, isInt = true, to draw a round cap */
1386 miLineArc (paintedSet, pixel, pGC,
1387 (LineFace *)NULL, &rightFace,
1388 (double)0.0, (double)0.0, true);
1389 }
1390 }
1391 else
1392 /* we're doing OnOffDash, and final segment of polyline ended
1393 with an (undrawn) `off' dash */
1394 {
1395 if (selfJoin && (firstPaintType != 0))
1396 /* closed; if projecting or round caps are being used, draw
1397 one on the first face */
1398 {
1399 pixel = pGC->pixels[firstPaintType];
1400 if (pGC->capStyle == (int)MI_CAP_PROJECTING)
1401 miLineProjectingCap (paintedSet, pixel, pGC,
1402 &firstFace, true, true);
1403 else if (pGC->capStyle == (int)MI_CAP_ROUND
1404 || pGC->capStyle == (int)MI_CAP_TRIANGULAR)
1405 /* invoke miLineArc, isInt = true, to draw a round cap */
1406 miLineArc (paintedSet, pixel, pGC,
1407 &firstFace, (LineFace *)NULL,
1408 (double)0.0, (double)0.0, true);
1409 }
1410 }
1411 }
1412 }
1413
1414 /* handle `all points coincident' crock, nothing yet drawn */
1415 if (!somethingDrawn
1416 && (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || !(dashNum & 1)))
1417 {
1418 unsigned int w1;
1419
1420 pixel = (dashNum & 1) ? pGC->pixels[0] : pGC->pixels[1];
1421 switch ((int)pGC->capStyle)
1422 {
1423 case (int)MI_CAP_ROUND:
1424 case (int)MI_CAP_TRIANGULAR:
1425 /* invoke miLineArc, isInt = false, to draw a round disk */
1426 miLineArc (paintedSet, pixel, pGC,
1427 (LineFace *)NULL, (LineFace *)NULL,
1428 (double)x2, (double)y2,
1429 false);
1430 break;
1431 case (int)MI_CAP_PROJECTING:
1432 /* draw a square box with edge size equal to line width */
1433 w1 = pGC->lineWidth;
1434 miFillRectPolyHelper (paintedSet, pixel,
1435 (int)(x2 - (w1 >> 1)), (int)(y2 - (w1 >> 1)),
1436 w1, w1);
1437 break;
1438 case (int)MI_CAP_BUTT:
1439 default:
1440 break;
1441 }
1442 }
1443 }
1444
1445
1446 #define V_TOP 0
1447 #define V_RIGHT 1
1448 #define V_BOTTOM 2
1449 #define V_LEFT 3
1450
1451 /* Helper function, called by miWideDash(). Draw a single dashed line
1452 segment, i.e. a sequence of dashes including a possible final incomplete
1453 dash, and step DashNum, DashIndex and DashOffset appropriately. Also
1454 pass back left and right faces for the line segment, for possible use in
1455 adding caps or joins. If the LineOnOffDash line style is used, each
1456 dash will be given a round cap if lines are drawn in the rounded cap
1457 style, and a projecting cap if lines are drawn in the projecting cap
1458 style. */
1459
1460 /* ARGS: pDashNum = absolute number of dash
1461 pDashIndex = index into array (i.e. dashNum % length)
1462 pDashOffset = offset into selected dash */
1463 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)1464 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)
1465 {
1466 int dashNum, dashIndex, dashRemain;
1467 unsigned int *pDash;
1468 double L, l;
1469 double k;
1470 PolyVertex vertices[4];
1471 PolyVertex saveRight, saveBottom;
1472 PolySlope slopes[4];
1473 PolyEdge left[2], right[2];
1474 LineFace lcapFace, rcapFace;
1475 int nleft, nright;
1476 unsigned int h;
1477 int y;
1478 int dy, dx;
1479 double LRemain;
1480 double r;
1481 double rdx, rdy;
1482 double dashDx, dashDy;
1483 double saveK = 0.0;
1484 bool first = true;
1485 double lcenterx, lcentery, rcenterx = 0.0, rcentery = 0.0;
1486 miPixel pixel;
1487 int numPixels, paintType;
1488
1489 dx = x2 - x1;
1490 dy = y2 - y1;
1491 dashNum = *pDashNum;
1492 dashIndex = *pDashIndex;
1493 pDash = pGC->dash;
1494 /* determine portion of current dash remaining (i.e. the portion after
1495 the current offset */
1496 dashRemain = (int)(pDash[dashIndex]) - *pDashOffset;
1497
1498 /* compute color of current dash */
1499 numPixels = pGC->numPixels;
1500 paintType = (dashNum & 1) ? 0 : 1 + ((dashNum / 2) % (numPixels - 1));
1501 pixel = pGC->pixels[paintType];
1502
1503 /* compute e.g. L, the distance to go (for dashing) */
1504 l = 0.5 * ((double) pGC->lineWidth);
1505 if (dx == 0) /* vertical segment */
1506 {
1507 L = dy;
1508 rdx = 0;
1509 rdy = l;
1510 if (dy < 0)
1511 {
1512 L = -dy;
1513 rdy = -l;
1514 }
1515 }
1516 else if (dy == 0) /* horizontal segment */
1517 {
1518 L = dx;
1519 rdx = l;
1520 rdy = 0;
1521 if (dx < 0)
1522 {
1523 L = -dx;
1524 rdx = -l;
1525 }
1526 }
1527 else /* neither horizontal nor vertical */
1528 {
1529 L = hypot ((double) dx, (double) dy);
1530 r = l / L; /* this is ell / L, not 1 / L */
1531 rdx = r * dx;
1532 rdy = r * dy;
1533 }
1534 k = l * L; /* this is ell * L, not 1 * L */
1535
1536 /* All position comments are relative to a line with dx and dy > 0,
1537 * but the code does not depend on this. */
1538 /* top */
1539 slopes[V_TOP].dx = dx;
1540 slopes[V_TOP].dy = dy;
1541 slopes[V_TOP].k = k;
1542 /* right */
1543 slopes[V_RIGHT].dx = -dy;
1544 slopes[V_RIGHT].dy = dx;
1545 slopes[V_RIGHT].k = 0;
1546 /* bottom */
1547 slopes[V_BOTTOM].dx = -dx;
1548 slopes[V_BOTTOM].dy = -dy;
1549 slopes[V_BOTTOM].k = k;
1550 /* left */
1551 slopes[V_LEFT].dx = dy;
1552 slopes[V_LEFT].dy = -dx;
1553 slopes[V_LEFT].k = 0;
1554
1555 /* preload the start coordinates */
1556 vertices[V_RIGHT].x = vertices[V_TOP].x = rdy;
1557 vertices[V_RIGHT].y = vertices[V_TOP].y = -rdx;
1558
1559 vertices[V_BOTTOM].x = vertices[V_LEFT].x = -rdy;
1560 vertices[V_BOTTOM].y = vertices[V_LEFT].y = rdx;
1561
1562 if (projectLeft)
1563 /* offset the vertices appropriately */
1564 {
1565 vertices[V_TOP].x -= rdx;
1566 vertices[V_TOP].y -= rdy;
1567
1568 vertices[V_LEFT].x -= rdx;
1569 vertices[V_LEFT].y -= rdy;
1570
1571 slopes[V_LEFT].k = rdx * dx + rdy * dy;
1572 }
1573
1574 /* starting point for first dash (floating point) */
1575 lcenterx = x1;
1576 lcentery = y1;
1577
1578 if (pGC->capStyle == (int)MI_CAP_ROUND
1579 || pGC->capStyle == (int)MI_CAP_TRIANGULAR)
1580 /* keep track of starting face (need only in OnOff case) */
1581 {
1582 lcapFace.dx = dx;
1583 lcapFace.dy = dy;
1584 lcapFace.x = x1;
1585 lcapFace.y = y1;
1586
1587 rcapFace.dx = -dx;
1588 rcapFace.dy = -dy;
1589 rcapFace.x = x1;
1590 rcapFace.y = y1;
1591 }
1592
1593 /* draw dashes until end of line segment is reached, and no additional
1594 (complete) dash can be drawn */
1595 LRemain = L;
1596 while (LRemain > dashRemain)
1597 {
1598 dashDx = (dashRemain * dx) / L;
1599 dashDy = (dashRemain * dy) / L;
1600
1601 /* ending point for dash */
1602 rcenterx = lcenterx + dashDx;
1603 rcentery = lcentery + dashDy;
1604
1605 vertices[V_RIGHT].x += dashDx;
1606 vertices[V_RIGHT].y += dashDy;
1607
1608 vertices[V_BOTTOM].x += dashDx;
1609 vertices[V_BOTTOM].y += dashDy;
1610
1611 slopes[V_RIGHT].k = vertices[V_RIGHT].x * dx + vertices[V_RIGHT].y * dy;
1612
1613 /* draw dash (if OnOffDash, don't draw `off' dashes) */
1614 if (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || !(paintType == 0))
1615 {
1616 if (pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH &&
1617 pGC->capStyle == (int)MI_CAP_PROJECTING)
1618 /* will draw projecting caps, so save vertices for later use */
1619 {
1620 saveRight = vertices[V_RIGHT];
1621 saveBottom = vertices[V_BOTTOM];
1622 saveK = slopes[V_RIGHT].k;
1623
1624 if (!first)
1625 {
1626 vertices[V_TOP].x -= rdx;
1627 vertices[V_TOP].y -= rdy;
1628
1629 vertices[V_LEFT].x -= rdx;
1630 vertices[V_LEFT].y -= rdy;
1631
1632 slopes[V_LEFT].k = vertices[V_LEFT].x *
1633 slopes[V_LEFT].dy -
1634 vertices[V_LEFT].y *
1635 slopes[V_LEFT].dx;
1636 }
1637
1638 vertices[V_RIGHT].x += rdx;
1639 vertices[V_RIGHT].y += rdy;
1640
1641 vertices[V_BOTTOM].x += rdx;
1642 vertices[V_BOTTOM].y += rdy;
1643
1644 slopes[V_RIGHT].k = vertices[V_RIGHT].x *
1645 slopes[V_RIGHT].dy -
1646 vertices[V_RIGHT].y *
1647 slopes[V_RIGHT].dx;
1648 }
1649
1650 /* build lists of left and right edges for the dash, using the
1651 just-computed array of slopes */
1652 y = miPolyBuildPoly (vertices, slopes, 4, x1, y1,
1653 left, right, &nleft, &nright, &h);
1654
1655 /* fill the dash, with either fg or bg color (alternates) */
1656 miFillPolyHelper (paintedSet, pixel,
1657 y, h, left, right, nleft, nright);
1658
1659 if (pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH)
1660 /* if doing OnOffDash, add caps if any */
1661 {
1662 switch ((int)pGC->capStyle)
1663 {
1664 case (int)MI_CAP_BUTT:
1665 default:
1666 break;
1667 case (int)MI_CAP_PROJECTING:
1668 /* use saved vertices */
1669 vertices[V_BOTTOM] = saveBottom;
1670 vertices[V_RIGHT] = saveRight;
1671 slopes[V_RIGHT].k = saveK;
1672 break;
1673 case (int)MI_CAP_ROUND:
1674 case (int)MI_CAP_TRIANGULAR:
1675 if (!first)
1676 {
1677 if (dx < 0)
1678 {
1679 lcapFace.xa = -vertices[V_LEFT].x;
1680 lcapFace.ya = -vertices[V_LEFT].y;
1681 lcapFace.k = slopes[V_LEFT].k;
1682 }
1683 else
1684 {
1685 lcapFace.xa = vertices[V_TOP].x;
1686 lcapFace.ya = vertices[V_TOP].y;
1687 lcapFace.k = -slopes[V_LEFT].k;
1688 }
1689 /* invoke miLineArc, isInt = false, to draw half-disk
1690 on left end of dash (only if dash is not first) */
1691 miLineArc (paintedSet, pixel, pGC,
1692 &lcapFace, (LineFace *) NULL,
1693 lcenterx, lcentery, false);
1694 }
1695 if (dx < 0)
1696 {
1697 rcapFace.xa = vertices[V_BOTTOM].x;
1698 rcapFace.ya = vertices[V_BOTTOM].y;
1699 rcapFace.k = slopes[V_RIGHT].k;
1700 }
1701 else
1702 {
1703 rcapFace.xa = -vertices[V_RIGHT].x;
1704 rcapFace.ya = -vertices[V_RIGHT].y;
1705 rcapFace.k = -slopes[V_RIGHT].k;
1706 }
1707 /* invoke miLineArc, isInt = false, to draw half-disk on
1708 right end of dash */
1709 miLineArc (paintedSet, pixel, pGC,
1710 (LineFace *)NULL, &rcapFace,
1711 rcenterx, rcentery, false);
1712 break;
1713 }
1714 }
1715 }
1716
1717 /* we just drew a dash, or (in the OnOff case) we either drew a dash
1718 or we didn't */
1719
1720 LRemain -= dashRemain; /* decrement float by int (distance over
1721 which we just drew, i.e. the remainder
1722 of current dash) */
1723
1724 /* bump absolute dash number, and index of dash in array (cyclically) */
1725 ++dashNum;
1726 ++dashIndex;
1727 if (dashIndex == pGC->numInDashList)
1728 dashIndex = 0;
1729 dashRemain = (int)(pDash[dashIndex]); /* whole new dash now `remains' */
1730
1731 /* compute color of next dash */
1732 paintType = (dashNum & 1) ? 0 : 1 + ((dashNum / 2) % (numPixels - 1));
1733 pixel = pGC->pixels[paintType];
1734
1735 /* next dash will start where previous one ended */
1736 lcenterx = rcenterx;
1737 lcentery = rcentery;
1738
1739 vertices[V_TOP] = vertices[V_RIGHT];
1740 vertices[V_LEFT] = vertices[V_BOTTOM];
1741 slopes[V_LEFT].k = -slopes[V_RIGHT].k;
1742 first = false; /* no longer first dash of line segment */
1743 }
1744
1745 /* final portion of segment is dashed specially, with an incomplete dash */
1746 if (pGC->lineStyle == (int)MI_LINE_DOUBLE_DASH || !(paintType == 0))
1747 {
1748 vertices[V_TOP].x -= dx;
1749 vertices[V_TOP].y -= dy;
1750
1751 vertices[V_LEFT].x -= dx;
1752 vertices[V_LEFT].y -= dy;
1753
1754 vertices[V_RIGHT].x = rdy;
1755 vertices[V_RIGHT].y = -rdx;
1756
1757 vertices[V_BOTTOM].x = -rdy;
1758 vertices[V_BOTTOM].y = rdx;
1759
1760 if (projectRight)
1761 /* offset appropriately */
1762 {
1763 vertices[V_RIGHT].x += rdx;
1764 vertices[V_RIGHT].y += rdy;
1765
1766 vertices[V_BOTTOM].x += rdx;
1767 vertices[V_BOTTOM].y += rdy;
1768 slopes[V_RIGHT].k = vertices[V_RIGHT].x *
1769 slopes[V_RIGHT].dy -
1770 vertices[V_RIGHT].y *
1771 slopes[V_RIGHT].dx;
1772 }
1773 else
1774 slopes[V_RIGHT].k = 0;
1775
1776 /* if OnOffDash line style and cap mode is projecting, offset the
1777 face, so as to draw a projecting cap */
1778 if (!first && pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH
1779 && pGC->capStyle == (int)MI_CAP_PROJECTING)
1780 {
1781 vertices[V_TOP].x -= rdx;
1782 vertices[V_TOP].y -= rdy;
1783
1784 vertices[V_LEFT].x -= rdx;
1785 vertices[V_LEFT].y -= rdy;
1786 slopes[V_LEFT].k = vertices[V_LEFT].x *
1787 slopes[V_LEFT].dy -
1788 vertices[V_LEFT].y *
1789 slopes[V_LEFT].dx;
1790 }
1791 else
1792 slopes[V_LEFT].k += dx * dx + dy * dy;
1793
1794 /* build lists of left and right edges for the final incomplete dash,
1795 using the just-computed vertices and slopes */
1796 y = miPolyBuildPoly (vertices, slopes, 4, x2, y2,
1797 left, right, &nleft, &nright, &h);
1798
1799 /* fill the final dash */
1800 miFillPolyHelper (paintedSet, pixel,
1801 y, h, left, right, nleft, nright);
1802
1803 /* if OnOffDash line style and cap mode is round, draw a round cap */
1804 if (!first && pGC->lineStyle == (int)MI_LINE_ON_OFF_DASH
1805 && (pGC->capStyle == (int)MI_CAP_ROUND
1806 || pGC->capStyle == (int)MI_CAP_TRIANGULAR))
1807 {
1808 lcapFace.x = x2;
1809 lcapFace.y = y2;
1810 if (dx < 0)
1811 {
1812 lcapFace.xa = -vertices[V_LEFT].x;
1813 lcapFace.ya = -vertices[V_LEFT].y;
1814 lcapFace.k = slopes[V_LEFT].k;
1815 }
1816 else
1817 {
1818 lcapFace.xa = vertices[V_TOP].x;
1819 lcapFace.ya = vertices[V_TOP].y;
1820 lcapFace.k = -slopes[V_LEFT].k;
1821 }
1822 /* invoke miLineArc, isInt = false, to draw disk on end */
1823 miLineArc (paintedSet, pixel, pGC,
1824 &lcapFace, (LineFace *) NULL,
1825 rcenterx, rcentery, false);
1826 }
1827 }
1828
1829 /* work out left and right faces of the dashed segment, to pass back */
1830 leftFace->x = x1;
1831 leftFace->y = y1;
1832 leftFace->dx = dx;
1833 leftFace->dy = dy;
1834 leftFace->xa = rdy;
1835 leftFace->ya = -rdx;
1836 leftFace->k = k;
1837
1838 rightFace->x = x2;
1839 rightFace->y = y2;
1840 rightFace->dx = -dx;
1841 rightFace->dy = -dy;
1842 rightFace->xa = -rdy;
1843 rightFace->ya = rdx;
1844 rightFace->k = k;
1845
1846 /* update absolute dash number, dash index, dash offset */
1847 dashRemain = (int)(((double) dashRemain) - LRemain);
1848 if (dashRemain == 0) /* on to next dash in array */
1849 {
1850 dashNum++; /* bump absolute dash number */
1851 dashIndex++;
1852 if (dashIndex == pGC->numInDashList) /* wrap */
1853 dashIndex = 0;
1854 dashRemain = (int)(pDash[dashIndex]);
1855 }
1856
1857 *pDashNum = dashNum;
1858 *pDashIndex = dashIndex;
1859 *pDashOffset = (int)(pDash[dashIndex]) - dashRemain;
1860 }
1861
1862 /* Helper function, called by miWideDash() above and also by miZeroPolyArc
1863 (in mi_zerarc.c) and miZeroDash (in mi_zerolin.c) to perform initial
1864 offsetting into the dash array, before dash #0 is drawn. In all cases,
1865 dashNum=0, dashIndex=0 and dashOffset=0. */
1866
1867 /* FIXME: a negative offset is not supported, and if it is, then some
1868 places elsewhere in the code, which assume dashNum>=0, may need to be
1869 fixed too. */
1870
1871 /* ARGS: dist = add'l offset (assumed >= 0)
1872 pDashNum = dash number
1873 pDashIndex = current dash
1874 pDash = dash list
1875 numInDashList = dashlist length
1876 pDashOffset = offset into current dash */
1877 void
miStepDash(int dist,int * pDashNum,int * pDashIndex,const unsigned int * pDash,int numInDashList,int * pDashOffset)1878 miStepDash (int dist, int *pDashNum, int *pDashIndex, const unsigned int *pDash, int numInDashList, int *pDashOffset)
1879 {
1880 int dashNum, dashIndex, dashOffset;
1881 int totallen;
1882 int i;
1883
1884 dashNum = *pDashNum;
1885 dashIndex = *pDashIndex;
1886 dashOffset = *pDashOffset;
1887 if (dashOffset + dist < (int)(pDash[dashIndex]))
1888 /* offset won't take us beyond end of present dash */
1889 {
1890 *pDashOffset = dashOffset + dist;
1891 return;
1892 }
1893
1894 /* move to next dash */
1895 dist -= (int)(pDash[dashIndex]) - dashOffset;
1896 dashNum++;
1897 dashIndex++;
1898 if (dashIndex == numInDashList)
1899 /* wrap to beginning of dash list */
1900 dashIndex = 0;
1901
1902 /* make it easy on ourselves: work modulo iteration interval */
1903 totallen = 0;
1904 for (i = 0; i < numInDashList; i++)
1905 totallen += (int)(pDash[i]);
1906 if (totallen <= dist)
1907 dist = dist % totallen;
1908
1909 while (dist >= (int)(pDash[dashIndex]))
1910 {
1911 dist -= (int)(pDash[dashIndex]);
1912 dashNum++;
1913 dashIndex++;
1914 if (dashIndex == numInDashList)
1915 /* wrap to beginning of dash list */
1916 dashIndex = 0;
1917 }
1918 *pDashNum = dashNum;
1919 *pDashIndex = dashIndex;
1920 *pDashOffset = dist;
1921 }
1922
1923
1924 /* Draw a wide polyline, undashed (if width=0, this simply calls
1925 miZeroLine) */
1926 void
miWideLine(miPaintedSet * paintedSet,const miGC * pGC,miCoordMode mode,int npt,const miPoint * pPts)1927 miWideLine (miPaintedSet *paintedSet, const miGC *pGC, miCoordMode mode, int npt, const miPoint *pPts)
1928 {
1929 int x1, y1, x2, y2;
1930 bool projectLeft, projectRight;
1931 LineFace leftFace, rightFace, prevRightFace;
1932 LineFace firstFace;
1933 int first;
1934 bool somethingDrawn = false;
1935 bool selfJoin;
1936
1937 /* ensure we have >=1 points */
1938 if (npt <= 0)
1939 return;
1940
1941 /* width 0 lines are handled specially */
1942 if (pGC->lineWidth == 0)
1943 {
1944 miZeroLine (paintedSet, pGC, mode, npt, pPts);
1945 return;
1946 }
1947
1948 x2 = pPts->x;
1949 y2 = pPts->y;
1950 first = true;
1951
1952 /* determine whether polyline is closed */
1953 selfJoin = false;
1954 if (npt > 1)
1955 {
1956 if (mode == MI_COORD_MODE_PREVIOUS)
1957 {
1958 int nptTmp;
1959 const miPoint *pPtsTmp;
1960
1961 x1 = x2;
1962 y1 = y2;
1963 nptTmp = npt;
1964 pPtsTmp = pPts + 1;
1965 while (--nptTmp)
1966 {
1967 x1 += pPtsTmp->x;
1968 y1 += pPtsTmp->y;
1969 ++pPtsTmp;
1970 }
1971 if (x2 == x1 && y2 == y1)
1972 selfJoin = true;
1973 }
1974 else if (x2 == pPts[npt-1].x && y2 == pPts[npt-1].y)
1975 selfJoin = true;
1976 }
1977
1978 /* line segments (except for the last) will not project right; they'll
1979 project left if the cap mode is "projecting" */
1980 projectLeft =
1981 (pGC->capStyle == (int)MI_CAP_PROJECTING && !selfJoin) ? true : false;
1982 projectRight = false;
1983 /* iterate through points, drawing all line segments of nonzero length */
1984 while (--npt)
1985 {
1986 x1 = x2;
1987 y1 = y2;
1988 ++pPts;
1989 x2 = pPts->x;
1990 y2 = pPts->y;
1991 if (mode == MI_COORD_MODE_PREVIOUS)
1992 {
1993 x2 += x1;
1994 y2 += y1;
1995 }
1996 if (x1 != x2 || y1 != y2)
1997 /* nonzero length */
1998 {
1999 somethingDrawn = true;
2000 if (npt == 1 && pGC->capStyle == (int)MI_CAP_PROJECTING && !selfJoin)
2001 /* last point; and need a projecting cap here */
2002 projectRight = true;
2003 /* draw segment (pixel=1), returning faces */
2004 miWideSegment (paintedSet, pGC->pixels[1], pGC,
2005 x1, y1, x2, y2,
2006 projectLeft, projectRight, &leftFace, &rightFace);
2007 if (first)
2008 /* first line segment, draw round cap if needed */
2009 {
2010 if (selfJoin)
2011 firstFace = leftFace;
2012 else if (pGC->capStyle == (int)MI_CAP_ROUND
2013 || pGC->capStyle == (int)MI_CAP_TRIANGULAR)
2014 /* invoke miLineArc, isInt = true, to draw a round cap
2015 on left face in paint type #1 */
2016 miLineArc (paintedSet, pGC->pixels[1], pGC,
2017 &leftFace, (LineFace *)NULL,
2018 (double)0.0, (double)0.0,
2019 true);
2020 }
2021 else
2022 /* general case: draw join at beginning of segment (pixel=1) */
2023 miLineJoin (paintedSet, pGC->pixels[1], pGC,
2024 &leftFace, &prevRightFace);
2025
2026 prevRightFace = rightFace;
2027 first = false;
2028 projectLeft = false;
2029 }
2030
2031 /* final point of polyline */
2032 if (npt == 1 && somethingDrawn)
2033 {
2034 if (selfJoin)
2035 /* add line join to close the polyline, pixel=1 */
2036 miLineJoin (paintedSet, pGC->pixels[1], pGC,
2037 &firstFace, &rightFace);
2038 else if (pGC->capStyle == (int)MI_CAP_ROUND
2039 || pGC->capStyle == (int)MI_CAP_TRIANGULAR)
2040 /* invoke miLineArc, isInt = true, to draw round cap
2041 on right face, pixel=1 */
2042 miLineArc (paintedSet, pGC->pixels[1], pGC,
2043 (LineFace *)NULL, &rightFace,
2044 (double)0.0, (double)0.0,
2045 true);
2046 }
2047 }
2048
2049 /* handle crock where all points are coincident */
2050 if (!somethingDrawn)
2051 {
2052 projectLeft = (pGC->capStyle == (int)MI_CAP_PROJECTING) ? true : false;
2053 miWideSegment (paintedSet, pGC->pixels[1], pGC, /* pixel=1 */
2054 x2, y2, x2, y2, projectLeft, projectLeft,
2055 &leftFace, &rightFace);
2056 if (pGC->capStyle == (int)MI_CAP_ROUND
2057 || pGC->capStyle == (int)MI_CAP_TRIANGULAR)
2058 {
2059 /* invoke miLineArc, isInt = true, to draw round cap
2060 in paint type #1 */
2061 miLineArc (paintedSet, pGC->pixels[1], pGC,
2062 &leftFace, (LineFace *)NULL,
2063 (double)0.0, (double)0.0,
2064 true);
2065 /* invoke miLineArc, isInt = true, to draw other round cap
2066 in paint type #1 */
2067 rightFace.dx = -1; /* sleazy hack to make it work */
2068 miLineArc (paintedSet, pGC->pixels[1], pGC,
2069 (LineFace *) NULL, &rightFace,
2070 (double)0.0, (double)0.0,
2071 true);
2072 }
2073 }
2074 }
2075
2076 /* Helper function, called by miWideLine() with pixel=1. Draw a single
2077 segment of a wide polyline, taking into account projecting caps, but not
2078 round caps. Also pass back left and right faces for the line segment,
2079 for possible use in adding caps or joins. */
2080 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)2081 miWideSegment (miPaintedSet *paintedSet, miPixel pixel, const miGC *pGC, int x1, int y1, int x2, int y2, bool projectLeft, bool projectRight, LineFace *leftFace, LineFace *rightFace)
2082 {
2083 int dx, dy;
2084 int x, y;
2085 int signdx;
2086 int lw = (int)(pGC->lineWidth);
2087
2088 if (y2 < y1 || (y2 == y1 && x2 < x1))
2089 /* interchange, so as always to draw top-to-bottom, or left-to-right if
2090 horizontal */
2091 {
2092 int tx, ty;
2093 bool tbool;
2094 LineFace *tface;
2095
2096 tx = x1;
2097 x1 = x2;
2098 x2 = tx;
2099
2100 ty = y1;
2101 y1 = y2;
2102 y2 = ty;
2103
2104 tbool = projectLeft;
2105 projectLeft = projectRight;
2106 projectRight = tbool;
2107
2108 tface = leftFace;
2109 leftFace = rightFace;
2110 rightFace = tface;
2111 }
2112
2113 dy = y2 - y1;
2114 signdx = 1;
2115 dx = x2 - x1;
2116 if (dx < 0)
2117 signdx = -1;
2118
2119 leftFace->x = x1;
2120 leftFace->y = y1;
2121 leftFace->dx = dx;
2122 leftFace->dy = dy;
2123
2124 rightFace->x = x2;
2125 rightFace->y = y2;
2126 rightFace->dx = -dx; /* for faces, (dx,dy) points _into_ line */
2127 rightFace->dy = -dy;
2128
2129 if (dy == 0)
2130 /* segment is horizontal */
2131 {
2132 rightFace->xa = 0;
2133 rightFace->ya = 0.5 * (double)lw;
2134 rightFace->k = -0.5 * (double)(lw * dx); /* k = xa * dy - ya * dx */
2135 leftFace->xa = 0;
2136 leftFace->ya = -rightFace->ya;
2137 leftFace->k = rightFace->k; /* k = xa * dy - ya * dx */
2138 x = x1;
2139 if (projectLeft)
2140 x -= (lw >> 1);
2141 y = y1 - (lw >> 1);
2142 dx = x2 - x;
2143 if (projectRight)
2144 dx += ((lw + 1) >> 1);
2145 dy = lw;
2146 miFillRectPolyHelper (paintedSet, pixel,
2147 x, y, (unsigned int)dx, (unsigned int)dy);
2148 }
2149 else if (dx == 0)
2150 /* segment is vertical */
2151 {
2152 leftFace->xa = 0.5 * (double)lw;
2153 leftFace->ya = 0;
2154 leftFace->k = 0.5 * (double)(lw * dy); /* k = xa * dy - ya * dx */
2155 rightFace->xa = -leftFace->xa;
2156 rightFace->ya = 0;
2157 rightFace->k = leftFace->k; /* k = xa * dy - ya * dx */
2158 y = y1;
2159 if (projectLeft)
2160 y -= lw >> 1;
2161 x = x1 - (lw >> 1);
2162 dy = y2 - y;
2163 if (projectRight)
2164 dy += ((lw + 1) >> 1);
2165 dx = lw;
2166 miFillRectPolyHelper (paintedSet, pixel,
2167 x, y, (unsigned int)dx, (unsigned int)dy);
2168 }
2169 else
2170 /* general case: segment is neither horizontal nor vertical */
2171 {
2172 double l, L, r;
2173 double xa, ya;
2174 double projectXoff = 0.0, projectYoff = 0.0;
2175 double k;
2176 double maxy;
2177 int finaly;
2178 int lefty, righty, topy, bottomy;
2179 PolyEdge lefts[2], rights[2];
2180 PolyEdge *left, *right;
2181 PolyEdge *top, *bottom;
2182
2183 l = 0.5 * ((double) lw);
2184 L = hypot ((double) dx, (double) dy);
2185
2186 if (dx < 0)
2187 {
2188 right = &rights[1];
2189 left = &lefts[0];
2190 top = &rights[0];
2191 bottom = &lefts[1];
2192 }
2193 else
2194 {
2195 right = &rights[0];
2196 left = &lefts[1];
2197 top = &lefts[0];
2198 bottom = &rights[1];
2199 }
2200 r = l / L; /* this is ell / L, not 1 / L */
2201
2202 ya = -r * dx;
2203 xa = r * dy;
2204
2205 if (projectLeft | projectRight)
2206 {
2207 projectXoff = -ya;
2208 projectYoff = xa;
2209 }
2210
2211 /* build first long edge */
2212
2213 k = l * L; /* xa * dy - ya * dx */
2214 leftFace->xa = xa;
2215 leftFace->ya = ya;
2216 leftFace->k = k;
2217 rightFace->xa = -xa;
2218 rightFace->ya = -ya;
2219 rightFace->k = k;
2220
2221 if (projectLeft)
2222 righty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff,
2223 k, dx, dy,
2224 x1, y1, false, right);
2225 else
2226 righty = miPolyBuildEdge (xa, ya,
2227 k, dx, dy,
2228 x1, y1, false, right);
2229
2230 /* build second long edge */
2231
2232 ya = -ya;
2233 xa = -xa;
2234 k = -k; /* xa * dy - ya * dx */
2235
2236 if (projectLeft)
2237 lefty = miPolyBuildEdge (xa - projectXoff, ya - projectYoff,
2238 k, dx, dy,
2239 x1, y1, true, left);
2240 else
2241 lefty = miPolyBuildEdge (xa, ya,
2242 k, dx, dy,
2243 x1, y1, true, left);
2244
2245 /* build first short edge, on left end */
2246
2247 if (signdx > 0)
2248 {
2249 ya = -ya;
2250 xa = -xa;
2251 }
2252
2253 if (projectLeft)
2254 {
2255 double xap = xa - projectXoff;
2256 double yap = ya - projectYoff;
2257 topy = miPolyBuildEdge (xap, yap,
2258 xap * dx + yap * dy, -dy, dx,
2259 x1, y1, (dx > 0 ? true : false), top);
2260 }
2261 else
2262 topy = miPolyBuildEdge (xa, ya,
2263 0.0, -dy, dx,
2264 x1, y1, (dx > 0 ? true : false), top);
2265
2266 /* build second short edge, on right end */
2267
2268 if (projectRight)
2269 {
2270 double xap = xa + projectXoff;
2271 double yap = ya + projectYoff;
2272 bottomy = miPolyBuildEdge (xap, yap,
2273 xap * dx + yap * dy, -dy, dx,
2274 x2, y2, (dx < 0 ? true : false), bottom);
2275 maxy = -ya + projectYoff;
2276 }
2277 else
2278 {
2279 bottomy = miPolyBuildEdge (xa, ya,
2280 0.0, -dy, dx,
2281 x2, y2, (dx < 0 ? true : false), bottom);
2282 maxy = -ya;
2283 }
2284
2285 finaly = ICEIL (maxy) + y2;
2286
2287 if (dx < 0)
2288 {
2289 left->height = (unsigned int)(bottomy - lefty);
2290 right->height = (unsigned int)(finaly - righty);
2291 top->height = (unsigned int)(righty - topy);
2292 }
2293 else
2294 {
2295 right->height = (unsigned int)(bottomy - righty);
2296 left->height = (unsigned int)(finaly - lefty);
2297 top->height = (unsigned int)(lefty - topy);
2298 }
2299 bottom->height = (unsigned int)(finaly - bottomy);
2300
2301 /* fill the rectangle (2 left edges, 2 right edges) */
2302 miFillPolyHelper (paintedSet, pixel, topy,
2303 (unsigned int)(bottom->height + bottomy - topy),
2304 lefts, rights, 2, 2);
2305 }
2306 }
2307