1 /* Copyright (C) 2001-2012 Artifex Software, Inc.
2 All Rights Reserved.
3
4 This software is provided AS-IS with no warranty, either express or
5 implied.
6
7 This software is distributed under license and may not be copied,
8 modified or distributed except as expressly authorized under the terms
9 of the license contained in the file LICENSE in this distribution.
10
11 Refer to licensing information at http://www.artifex.com or contact
12 Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134, San Rafael,
13 CA 94903, U.S.A., +1(415)492-9861, for further information.
14 */
15
16
17 /* Path stroking procedures for Ghostscript library */
18 #include "math_.h"
19 #include <stdlib.h> /* abs() */
20 #include "gx.h"
21 #include "gpcheck.h"
22 #include "gserrors.h"
23 #include "gsdcolor.h"
24 #include "gsptype1.h"
25 #include "gxfixed.h"
26 #include "gxfarith.h"
27 #include "gxmatrix.h"
28 #include "gscoord.h"
29 #include "gsdevice.h"
30 #include "gxdevice.h"
31 #include "gxhttile.h"
32 #include "gxistate.h"
33 #include "gzline.h"
34 #include "gzpath.h"
35 #include "gzcpath.h"
36 #include "gxpaint.h"
37 #include "vdtrace.h"
38 #include "gsstate.h" /* for gs_currentcpsimode */
39
40 /* RJW: There appears to be a difference in the xps and postscript models
41 * (at least in as far as Microsofts implementation of xps and Acrobats of
42 * postscript). Acrobat (and ghostscript) are happy to join a line segment
43 * around a corner, even when the next segment is a dash gap. Microsofts
44 * implementation of XPS does not.
45 *
46 * A test file that shows this up is tests_private/comparefiles/298-05.ps
47 *
48 * Enabling the following define would emulate xps behaviour here.
49 */
50 #undef AVOID_JOINING_TO_DASH_GAPS
51
52 /*
53 * We don't really know whether it's a good idea to take fill adjustment
54 * into account for stroking. Disregarding it means that strokes
55 * come out thinner than fills; observing it produces heavy-looking
56 * strokes at low resolutions. But in any case, we must disregard it
57 * when stroking zero-width lines.
58 */
59 #define USE_FILL_ADJUSTMENT
60
61 #ifdef USE_FILL_ADJUSTMENT
62 # define STROKE_ADJUSTMENT(thin, pis, xy)\
63 (thin ? fixed_0 : (pis)->fill_adjust.xy)
64 #else
65 # define STROKE_ADJUSTMENT(thin, pis, xy) fixed_0
66 #endif
67
68 /*
69 * For some reason, we commented out the optimization for portrait,
70 * landscape, and uniform (non-scaled) transformations. We have no record
71 * of why we did this, and we don't know what bugs re-enabling it may
72 * introduce.
73 */
74 #define OPTIMIZE_ORIENTATION
75
76 /*
77 * Compute the amount by which to expand a stroked bounding box to account
78 * for line width, caps and joins. Return 0 if the result is exact, 1 if
79 * it may be conservative, or gs_error_limitcheck if the result is too
80 * large to fit in a gs_fixed_point.
81 *
82 * Because of square caps and miter and triangular joins, the maximum
83 * expansion on each side (in user space) is
84 * K * line_width/2
85 * where K is determined as follows:
86 * For round or butt caps, E = 1
87 * For square caps, E = sqrt(2)
88 * If the path is only a single line segment, K = E;
89 * if triangular joins, K = 2;
90 * if miter joins, K = max(miter_limit, E);
91 * otherwise, K = E.
92 *
93 * If the following conditions apply, K = E yields an exact result:
94 * - The CTM is of the form [X 0 0 Y] or [0 X Y 0].
95 * - Square or round caps are used, or all subpaths are closed.
96 * - All segments (including the implicit segment created by
97 * closepath) are vertical or horizontal lines.
98 *
99 * Note that these conditions are sufficient, but not necessary, to get an
100 * exact result. We choose this set of conditions because it is easy to
101 * check and covers many common cases. Clients that care always have the
102 * option of using strokepath to get an exact result.
103 */
104 static float join_expansion_factor(const gs_imager_state *, gs_line_join);
105 int
gx_stroke_path_expansion(const gs_imager_state * pis,const gx_path * ppath,gs_fixed_point * ppt)106 gx_stroke_path_expansion(const gs_imager_state * pis, const gx_path * ppath,
107 gs_fixed_point * ppt)
108 {
109 const subpath *psub = ppath->first_subpath;
110 const segment *pseg;
111 double cx = fabs(pis->ctm.xx) + fabs(pis->ctm.yx);
112 double cy = fabs(pis->ctm.xy) + fabs(pis->ctm.yy);
113 double expand = pis->line_params.half_width;
114 int result = 1;
115
116 /* Adjust the expansion (E) for square caps, if needed */
117 if (pis->line_params.start_cap == gs_cap_square ||
118 pis->line_params.end_cap == gs_cap_square)
119 expand *= 1.414213562;
120
121 /* Check for whether an exact result can be computed easily. */
122 if (is_fzero2(pis->ctm.xy, pis->ctm.yx) ||
123 is_fzero2(pis->ctm.xx, pis->ctm.yy)
124 ) {
125 bool must_be_closed =
126 !(pis->line_params.start_cap == gs_cap_square ||
127 pis->line_params.start_cap == gs_cap_round ||
128 pis->line_params.end_cap == gs_cap_square ||
129 pis->line_params.end_cap == gs_cap_round ||
130 pis->line_params.dash_cap == gs_cap_square ||
131 pis->line_params.dash_cap == gs_cap_round);
132 gs_fixed_point prev;
133
134 prev.x = prev.y = 0; /* Quiet gcc warning. */
135 for (pseg = (const segment *)psub; pseg;
136 prev = pseg->pt, pseg = pseg->next
137 )
138 switch (pseg->type) {
139 case s_start:
140 if (((const subpath *)pseg)->curve_count ||
141 (must_be_closed && !((const subpath *)pseg)->is_closed)
142 )
143 goto not_exact;
144 break;
145 case s_line:
146 case s_dash:
147 case s_line_close:
148 if (!(pseg->pt.x == prev.x || pseg->pt.y == prev.y))
149 goto not_exact;
150 break;
151 case s_gap:
152 default: /* other/unknown segment type */
153 goto not_exact;
154 }
155 result = 0; /* exact result */
156 }
157 not_exact:
158 if (result) {
159 if (!gx_path_has_curves(ppath) && gx_path_subpath_count(ppath) <= 1 &&
160 (psub == 0 || (pseg = psub->next) == 0 ||
161 (pseg = pseg->next) == 0 || pseg->type == s_line_close))
162 DO_NOTHING;
163 else {
164 float factor = join_expansion_factor(pis, pis->line_params.join);
165
166 if (pis->line_params.curve_join >= 0)
167 factor = max(factor, join_expansion_factor(pis,
168 (gs_line_join)pis->line_params.curve_join));
169 expand *= factor;
170 }
171 }
172
173 /* Short-cut gs_bbox_transform. */
174 {
175 float exx = expand * cx;
176 float exy = expand * cy;
177 int code = set_float2fixed_vars(ppt->x, exx);
178
179 if (code < 0)
180 return code;
181 code = set_float2fixed_vars(ppt->y, exy);
182 if (code < 0)
183 return code;
184 }
185
186 return result;
187 }
188 static float
join_expansion_factor(const gs_imager_state * pis,gs_line_join join)189 join_expansion_factor(const gs_imager_state *pis, gs_line_join join)
190 {
191 switch (join) {
192 case gs_join_miter: return pis->line_params.miter_limit;
193 case gs_join_triangle: return 2.0;
194 default: return 1.0;
195 }
196 }
197
198 /*
199 * Structure for a partial line (passed to the drawing routine).
200 * Two of these are required to do joins right.
201 * Each endpoint includes the two ends of the cap as well,
202 * and the deltas for square, round, and triangular cap computation.
203 *
204 * The two base values for computing the caps of a partial line are the
205 * width and the end cap delta. The width value is one-half the line
206 * width (suitably transformed) at 90 degrees counter-clockwise
207 * (in device space, but with "90 degrees" interpreted in *user*
208 * coordinates) at the end (as opposed to the origin) of the line.
209 * The cdelta value is one-half the transformed line width in the same
210 * direction as the line. From these, we compute two other values at each
211 * end of the line: co and ce, which are the ends of the cap.
212 * Note that the cdelta values at o are the negatives of the values at e,
213 * as are the offsets from p to co and ce.
214 *
215 * Initially, only o.p, e.p, e.cdelta, width, and thin are set.
216 * compute_caps fills in the rest.
217 */
218 typedef gs_fixed_point *p_ptr;
219 typedef struct endpoint_s {
220 gs_fixed_point p; /* the end of the line */
221 gs_fixed_point co, ce; /* ends of the cap, p +/- width */
222 gs_fixed_point cdelta; /* +/- cap length */
223 } endpoint;
224 typedef endpoint *ep_ptr;
225 typedef const endpoint *const_ep_ptr;
226 typedef struct partial_line_s {
227 endpoint o; /* starting coordinate */
228 endpoint e; /* ending coordinate */
229 gs_fixed_point width; /* one-half line width, see above */
230 gs_fixed_point vector; /* The line segment direction */
231 bool thin; /* true if minimum-width line */
232 } partial_line;
233 typedef partial_line *pl_ptr;
234
235 /* As we stroke a path, we run through the line segments that make it up.
236 * We gather each line segment together with any degenerate line segments
237 * that follow it (call this set "prev"), and then 'join them' to the next
238 * line segment (and any degenerate line segments that follow it) (if there
239 * is one) (call this "current").
240 *
241 * In order to get the joins right we need to keep flags about both
242 * prev and current, and whether they originally came from arcs.
243 */
244 typedef enum note_flags {
245
246 /* If set, all the line segments that make up current come from arcs. */
247 nf_all_from_arc = 1,
248
249 /* If set, at least one of the line segments that make up current, come
250 * from arcs. */
251 nf_some_from_arc = 2,
252
253 /* If set then this segment should have a dash cap on the start rather
254 * than a start cap. */
255 nf_dash_head = 4,
256
257 /* If set then this segment should have a dash cap on the end rather
258 * than an end cap. */
259 nf_dash_tail = 8,
260
261 /* If set, all the line segments that make up prev come from arcs. */
262 nf_prev_all_from_arc = 16,
263
264 /* If set, at least one of the line segment that make up prev, come from
265 * arcs. */
266 nf_prev_some_from_arc = 32,
267
268 /* If set then prev should have a dash cap on the start rather
269 * than a start cap. */
270 nf_prev_dash_head = 64,
271
272 /* If set then prev should have a dash cap on the end rather
273 * than an end cap. */
274 nf_prev_dash_tail = 128
275
276 } note_flags;
277
278 /* Macro to combine the prev and current arc_flags. After applying this
279 * macro, the bits in the result have the following meanings:
280 * nf_all_from_arc set if all the components of current and prev
281 * come from an Arc.
282 * nf_some_from_arc set if any of the components of current and
283 * prev come from an Arc.
284 * nf_dash_head set if prev should have a dash cap rather than
285 * a start cap.
286 * nf_dash_tail set if prev should have a dash cap rather than
287 * an end cap.
288 */
289 #define COMBINE_FLAGS(F) \
290 (((F>>4) | ((F) & nf_some_from_arc)) & \
291 (((F) & nf_all_from_arc) ? ~0 : ~nf_all_from_arc))
292
293 /* Assign a point. Some compilers would do this with very slow code */
294 /* if we simply implemented it as an assignment. */
295 #define ASSIGN_POINT(pp, p)\
296 ((pp)->x = (p).x, (pp)->y = (p).y)
297
298 /* Other forward declarations */
299 static bool width_is_thin(pl_ptr);
300 static void adjust_stroke(gx_device *, pl_ptr, const gs_imager_state *, bool, bool, note_flags);
301 static int line_join_points(const gx_line_params * pgs_lp,
302 pl_ptr plp, pl_ptr nplp,
303 gs_fixed_point * join_points,
304 const gs_matrix * pmat, gs_line_join join,
305 bool reflected);
306 static int line_join_points_fast_cw(const gx_line_params * pgs_lp,
307 pl_ptr plp, pl_ptr nplp,
308 gs_fixed_point * rjoin_points,
309 const gs_matrix * pmat,
310 gs_line_join join);
311 static int line_join_points_fast_ccw(const gx_line_params * pgs_lp,
312 pl_ptr plp, pl_ptr nplp,
313 gs_fixed_point * join_points,
314 const gs_matrix * pmat,
315 gs_line_join join);
316 static void compute_caps(pl_ptr);
317 static int add_points(gx_path *, const gs_fixed_point *,
318 int, bool);
319 static int add_pie_join(gx_path *, pl_ptr, pl_ptr, bool, bool);
320 static int add_pie_join_fast_cw(gx_path *, pl_ptr, pl_ptr, bool);
321 static int add_pie_join_fast_ccw(gx_path *, pl_ptr, pl_ptr, bool);
322 static int add_round_cap(gx_path *, const_ep_ptr);
323 static int add_pie_cap(gx_path *, const_ep_ptr);
324 static int cap_points(gs_line_cap, const_ep_ptr,
325 gs_fixed_point * /*[3] */ );
326 static int join_under_pie(gx_path *, pl_ptr, pl_ptr, bool);
327
328 /* Define the default implementation of the device stroke_path procedure. */
329 int
gx_default_stroke_path(gx_device * dev,const gs_imager_state * pis,gx_path * ppath,const gx_stroke_params * params,const gx_drawing_color * pdcolor,const gx_clip_path * pcpath)330 gx_default_stroke_path(gx_device * dev, const gs_imager_state * pis,
331 gx_path * ppath, const gx_stroke_params * params,
332 const gx_drawing_color * pdcolor,
333 const gx_clip_path * pcpath)
334 {
335 return gx_stroke_path_only(ppath, (gx_path *) 0, dev, pis, params,
336 pdcolor, pcpath);
337 }
338
339 /* Fill a partial stroked path. Free variables: */
340 /* to_path, stroke_path_body, fill_params, always_thin, pis, dev, pdevc, */
341 /* code, ppath, exit(label). */
342 #define FILL_STROKE_PATH(dev, thin, pcpath, final)\
343 if(to_path==&stroke_path_body && !gx_path_is_void(&stroke_path_body) &&\
344 (final || lop_is_idempotent(pis->log_op))) {\
345 fill_params.adjust.x = STROKE_ADJUSTMENT(thin, pis, x);\
346 fill_params.adjust.y = STROKE_ADJUSTMENT(thin, pis, y);\
347 if (to_path_reverse != NULL) {\
348 code = gx_join_path_and_reverse(to_path, to_path_reverse);\
349 if(code < 0) goto exit;\
350 }\
351 code = gx_fill_path_only(to_path, dev, pis, &fill_params, pdevc, pcpath);\
352 gx_path_free(&stroke_path_body, "fill_stroke_path");\
353 if ( code < 0 ) goto exit;\
354 gx_path_init_local(&stroke_path_body, ppath->memory);\
355 }
356
357 /*
358 * Define the internal procedures that stroke a partial_line
359 * (the first pl_ptr argument). If both partial_lines are non-null,
360 * the procedure creates an appropriate join; otherwise, the procedure
361 * creates an end cap. If the first int is 0, the procedure also starts
362 * with an appropriate cap.
363 */
364 #define stroke_line_proc(proc)\
365 int proc(gx_path *, gx_path *, bool ensure_closed, int, pl_ptr, pl_ptr,\
366 const gx_device_color *, gx_device *, const gs_imager_state *,\
367 const gx_stroke_params *, const gs_fixed_rect *, int,\
368 gs_line_join, bool, note_flags)
369 typedef stroke_line_proc((*stroke_line_proc_t));
370
371 static stroke_line_proc(stroke_add);
372 static stroke_line_proc(stroke_add_compat);
373 static stroke_line_proc(stroke_add_fast);
374 static stroke_line_proc(stroke_fill);
375 static int stroke_add_initial_cap_compat(gx_path * ppath, pl_ptr plp, bool adlust_longitude,
376 const gx_device_color * pdevc, gx_device * dev,
377 const gs_imager_state * pis);
378
379 /* Define the orientations we handle specially. */
380 typedef enum {
381 orient_other = 0,
382 orient_portrait, /* [xx 0 0 yy tx ty] */
383 orient_landscape /* [0 xy yx 0 tx ty] */
384 } orientation;
385
386 /*
387 * Internal function used to merge the 2 sides of a stroked path.
388 * path contains the 'forward' side, rpath contains the 'reversed' side.
389 * Reverse rpath, then append it to path.
390 *
391 * If path is closed, then rpath should be too. If path is open, then the
392 * starting and ending points of both paths should be the same, so as to
393 * guarantee a closed path.
394 */
395 static int
gx_join_path_and_reverse(gx_path * path,gx_path * rpath)396 gx_join_path_and_reverse(gx_path * path, gx_path * rpath)
397 {
398 int code;
399
400 if (gx_path_is_void(rpath))
401 return 0;
402 code = gx_path_append_reversed(rpath, path);
403 if (code < 0)
404 return code;
405
406 gx_path_free(rpath, "gx_join_path_and_reverse");
407 gx_path_init_local(rpath, path->memory);
408
409 return gx_path_close_subpath(path);
410 }
411
412 /*
413 * Stroke a path. If to_path != 0, append the stroke outline to it;
414 * if to_path == 0, draw the strokes on pdev.
415 *
416 * Note that gx_stroke_path_only with to_path != NULL may clip the path to
417 * the clipping path, as for to_path == NULL. This is almost never
418 * what is wanted.
419 */
420 static int
gx_stroke_path_only_aux(gx_path * ppath,gx_path * to_path,gx_device * pdev,const gs_imager_state * pis,const gx_stroke_params * params,const gx_device_color * pdevc,const gx_clip_path * pcpath)421 gx_stroke_path_only_aux(gx_path * ppath, gx_path * to_path, gx_device * pdev,
422 const gs_imager_state * pis, const gx_stroke_params * params,
423 const gx_device_color * pdevc, const gx_clip_path * pcpath)
424 {
425 bool CPSI_mode = gs_currentcpsimode(pis->memory);
426 bool traditional = CPSI_mode | params->traditional;
427 stroke_line_proc_t line_proc =
428 ((to_path == 0 && !gx_dc_is_pattern1_color_clist_based(pdevc))
429 ? stroke_fill :
430 (traditional ? stroke_add_compat : stroke_add_fast));
431 gs_fixed_rect ibox, cbox;
432 gx_device_clip cdev;
433 gx_device *dev = pdev;
434 int code = 0;
435 gx_fill_params fill_params;
436 const gx_line_params *pgs_lp = gs_currentlineparams_inline(pis);
437 int dash_count = pgs_lp->dash.pattern_size;
438 gx_path fpath, dpath;
439 gx_path stroke_path_body;
440 gx_path stroke_path_reverse;
441 gx_path *to_path_reverse = NULL;
442 const gx_path *spath;
443 float xx = pis->ctm.xx, xy = pis->ctm.xy;
444 float yx = pis->ctm.yx, yy = pis->ctm.yy;
445 /*
446 * We are dealing with a reflected coordinate system
447 * if transform(1,0) is counter-clockwise from transform(0,1).
448 * See the note in stroke_add for the algorithm.
449 */
450 int uniform;
451 bool reflected;
452 orientation orient =
453 (
454 #ifdef OPTIMIZE_ORIENTATION
455 is_fzero2(xy, yx) ?
456 (uniform = (xx == yy ? 1 : xx == -yy ? -1 : 0),
457 reflected = (uniform ? uniform < 0 : (xx < 0) != (yy < 0)),
458 orient_portrait) :
459 is_fzero2(xx, yy) ?
460 (uniform = (xy == yx ? -1 : xy == -yx ? 1 : 0),
461 reflected = (uniform ? uniform < 0 : (xy < 0) == (yx < 0)),
462 orient_landscape) :
463 /* We should optimize uniform rotated coordinate systems */
464 /* here as well, but we don't. */
465 #endif
466 (uniform = 0,
467 reflected = xy * yx > xx * yy,
468 orient_other));
469 /*
470 * Formerly, there was a hack here that only treated the joins of
471 * flattened curves specially if the dot length was non-zero.
472 * This was a surrogate to detect use of the library by PCL
473 * interpreters. We have replaced this hack with an explicit
474 * curve join parameter in the graphics state.
475 */
476 #if 0
477 segment_notes not_first =
478 (!is_fzero(pis->line_params.dot_length) ? sn_not_first : sn_none);
479 #else
480 const segment_notes not_first = sn_not_first;
481 #endif
482 gs_line_join curve_join =
483 (pgs_lp->curve_join >= 0 ? (gs_line_join)pgs_lp->curve_join :
484 pgs_lp->join == gs_join_none || pgs_lp->join == gs_join_round ?
485 gs_join_bevel : pgs_lp->join);
486 float line_width = pgs_lp->half_width; /* (*half* the line width) */
487 bool always_thin;
488 double line_width_and_scale;
489 double device_line_width_scale = 0; /* Quiet compiler. */
490 double device_dot_length = pgs_lp->dot_length * fixed_1;
491 const subpath *psub;
492 gs_matrix initial_matrix;
493 bool initial_matrix_reflected;
494 note_flags flags;
495
496 (*dev_proc(pdev, get_initial_matrix)) (pdev, &initial_matrix);
497 initial_matrix_reflected = initial_matrix.xy * initial_matrix.yx >
498 initial_matrix.xx * initial_matrix.yy;
499
500 #ifdef DEBUG
501 if (gs_debug_c('o')) {
502 int count = pgs_lp->dash.pattern_size;
503 int i;
504
505 dlprintf4("[o]half_width=%f, start_cap=%d, end_cap=%d, dash_cap=%d,\n",
506 pgs_lp->half_width, (int)pgs_lp->start_cap,
507 (int)pgs_lp->end_cap, (int)pgs_lp->dash_cap);
508 dlprintf3(" join=%d, miter_limit=%f, miter_check=%f,\n",
509 (int)pgs_lp->join, pgs_lp->miter_limit,
510 pgs_lp->miter_check);
511 dlprintf1(" dash pattern=%d", count);
512 for (i = 0; i < count; i++)
513 dprintf1(",%f", pgs_lp->dash.pattern[i]);
514 dputs(",\n");
515 dlprintf4("\toffset=%f, init(ink_on=%d, index=%d, dist_left=%f)\n",
516 pgs_lp->dash.offset, pgs_lp->dash.init_ink_on,
517 pgs_lp->dash.init_index, pgs_lp->dash.init_dist_left);
518 }
519 #endif
520
521 gx_path_bbox(ppath, &ibox);
522 /* Expand the path bounding box by the scaled line width. */
523 {
524 gs_fixed_point expansion;
525
526 if (gx_stroke_path_expansion(pis, ppath, &expansion) < 0) {
527 /* The expansion is so large it caused a limitcheck. */
528 ibox.p.x = ibox.p.y = min_fixed;
529 ibox.q.x = ibox.q.y = max_fixed;
530 } else {
531 expansion.x += pis->fill_adjust.x;
532 expansion.y += pis->fill_adjust.y;
533 /*
534 * It's theoretically possible for the following computations to
535 * overflow, so we need to check for this.
536 */
537 ibox.p.x = (ibox.p.x < min_fixed + expansion.x ? min_fixed :
538 ibox.p.x - expansion.x);
539 ibox.p.y = (ibox.p.y < min_fixed + expansion.y ? min_fixed :
540 ibox.p.y - expansion.y);
541 ibox.q.x = (ibox.q.x > max_fixed - expansion.x ? max_fixed :
542 ibox.q.x + expansion.x);
543 ibox.q.y = (ibox.q.y > max_fixed - expansion.y ? max_fixed :
544 ibox.q.y + expansion.y);
545 }
546 }
547 /* Check the expanded bounding box against the clipping regions. */
548 if (pcpath)
549 gx_cpath_inner_box(pcpath, &cbox);
550 else if (pdevc)
551 (*dev_proc(pdev, get_clipping_box)) (pdev, &cbox);
552 else {
553 /* This is strokepath, not stroke. Don't clip. */
554 cbox = ibox;
555 }
556 if (!rect_within(ibox, cbox)) {
557 /* Intersect the path box and the clip bounding box. */
558 /* If the intersection is empty, this call is a no-op. */
559 gs_fixed_rect bbox;
560
561 if (pcpath) {
562 gx_cpath_outer_box(pcpath, &bbox);
563 if_debug4('f', " outer_box=(%g,%g),(%g,%g)\n",
564 fixed2float(bbox.p.x), fixed2float(bbox.p.y),
565 fixed2float(bbox.q.x), fixed2float(bbox.q.y));
566 rect_intersect(ibox, bbox);
567 } else
568 rect_intersect(ibox, cbox);
569 if (ibox.p.x >= ibox.q.x || ibox.p.y >= ibox.q.y) {
570 /* Intersection of boxes is empty! */
571 return 0;
572 }
573 /*
574 * The path is neither entirely inside the inner clip box
575 * nor entirely outside the outer clip box.
576 * If we had to flatten the path, this is where we would
577 * recompute its bbox and make the tests again,
578 * but we don't bother right now.
579 */
580 /*
581 * If there is a clipping path, set up a clipping device.
582 * for stroke_fill because, because the latter uses low level methods
583 * which don't accept a clipping path.
584 * Note that in some cases stroke_fill appends the path to stroke_path_body
585 * instead a real painting, and it is painted with FILL_STROKE_PATH.
586 *
587 * Contrary to that, FILL_STROKE_PATH paints a path with
588 * the fill_path method, which handles a clipping path,
589 * so we don't pass the clipper device to FILL_STROKE_PATH
590 * to prevent an appearence of superposing clippers.
591 */
592 if (pcpath && line_proc == stroke_fill) {
593 gx_make_clip_device_on_stack(&cdev, pcpath, pdev);
594 cdev.max_fill_band = pdev->max_fill_band;
595 dev = (gx_device *)&cdev;
596 }
597 }
598 fill_params.rule = gx_rule_winding_number;
599 fill_params.flatness = pis->flatness;
600 if (line_width < 0)
601 line_width = -line_width;
602 line_width_and_scale = line_width * (double)int2fixed(1);
603 if (is_fzero(line_width))
604 always_thin = true;
605 else {
606 float xa, ya;
607
608 switch (orient) {
609 case orient_portrait:
610 xa = xx, ya = yy;
611 goto sat;
612 case orient_landscape:
613 xa = xy, ya = yx;
614 sat:
615 if (xa < 0)
616 xa = -xa;
617 if (ya < 0)
618 ya = -ya;
619 always_thin = (max(xa, ya) * line_width < 0.5);
620 if (!always_thin && uniform) { /* Precompute a value we'll need later. */
621 device_line_width_scale = line_width_and_scale * xa;
622 }
623 break;
624 default:
625 {
626 /* The check is more complicated, but it's worth it. */
627 /* Compute radii of the transformed round brush. */
628 /* Let x = [a, sqrt(1-a^2)]'
629 radius^2 is an extremum of :
630 rr(a)=(CTM*x)^2 = (a*xx + sqrt(1 - a^2)*xy)^2 + (a*yx + sqrt(1 - a^2)*yy)^2
631 With solving D(rr(a),a)==0, got :
632 max_rr = (xx^2 + xy^2 + yx^2 + yy^2 + sqrt(((xy + yx)^2 + (xx - yy)^2)*((xy - yx)^2 + (xx + yy)^2)))/2.
633 r = sqrt(max_rr);
634 Well we could use eigenvalues of the quadratic form,
635 but it gives same result with a bigger calculus.
636 */
637 double max_rr = (xx*xx + xy*xy + yx*yx + yy*yy +
638 sqrt( ((xy + yx)*(xy + yx) + (xx - yy)*(xx - yy)) *
639 ((xy - yx)*(xy - yx) + (xx + yy)*(xx + yy))
640 )
641 )/2;
642
643 always_thin = max_rr * line_width * line_width < 0.25;
644 }
645 }
646 }
647 if_debug7('o', "[o]ctm=(%g,%g,%g,%g,%g,%g) thin=%d\n",
648 xx, xy, yx, yy, pis->ctm.tx, pis->ctm.ty, always_thin);
649 if (device_dot_length != 0) {
650 /*
651 * Compute the dot length in device space. We can't do this
652 * quite right for non-uniform coordinate systems; too bad.
653 */
654 gs_matrix mat;
655 const gs_matrix *pmat;
656
657 if (pgs_lp->dot_length_absolute) {
658 gs_deviceinitialmatrix(pdev, &mat);
659 pmat = &mat;
660 } else
661 pmat = (const gs_matrix *)&pis->ctm;
662 device_dot_length *= fabs(pmat->xy) + fabs(pmat->yy);
663 }
664 /* Start by flattening the path. We should do this on-the-fly.... */
665 if (!gx_path_has_curves(ppath) && !gx_path_has_long_segments(ppath)) {
666 /* don't need to flatten */
667 if (!ppath->first_subpath)
668 return 0;
669 spath = ppath;
670 } else {
671 gx_path_init_local(&fpath, ppath->memory);
672 if ((code = gx_path_add_flattened_for_stroke(ppath, &fpath,
673 params->flatness, pis)) < 0
674 )
675 return code;
676 spath = &fpath;
677 }
678 if (dash_count) {
679 gx_path_init_local(&dpath, ppath->memory);
680 code = gx_path_add_dash_expansion(spath, &dpath, pis);
681 if (code < 0)
682 goto exf;
683 spath = &dpath;
684 }
685 if (to_path == 0) {
686 /* We might try to defer this if it's expensive.... */
687 to_path = &stroke_path_body;
688 gx_path_init_local(&stroke_path_body, ppath->memory);
689 }
690 if (line_proc == stroke_add_fast) {
691 to_path_reverse = &stroke_path_reverse;
692 gx_path_init_local(&stroke_path_reverse, ppath->memory);
693 }
694 for (psub = spath->first_subpath; psub != 0;) {
695 int index = 0;
696 const segment *pseg = (const segment *)psub;
697 fixed x = pseg->pt.x;
698 fixed y = pseg->pt.y;
699 bool is_closed = ((const subpath *)pseg)->is_closed;
700 partial_line pl, pl_prev, pl_first;
701 bool zero_length = true;
702
703 flags = nf_all_from_arc;
704
705 /* Run through each segment in the current path, drawing each segment
706 * delayed by 1 - that is, when we're looking at segment n, we draw
707 * (or not) segment n-1. This delay allows us to always know whether
708 * to join or cap the line. */
709 while ((pseg = pseg->next) != 0 &&
710 pseg->type != s_start
711 ) {
712 /* Compute the width parameters in device space. */
713 /* We work with unscaled values, for speed. */
714 fixed sx, udx, sy, udy;
715 bool is_dash_segment = false;
716
717 d1:if (pseg->type != s_dash && pseg->type != s_gap) {
718 sx = pseg->pt.x;
719 sy = pseg->pt.y;
720 udx = sx - x;
721 udy = sy - y;
722 } else {
723 dash_segment *pd = (dash_segment *)pseg;
724
725 sx = pd->pt.x;
726 sy = pd->pt.y;
727 udx = pd->tangent.x;
728 udy = pd->tangent.y;
729 is_dash_segment = true;
730 }
731 zero_length &= ((udx | udy) == 0);
732 pl.o.p.x = x, pl.o.p.y = y;
733 d:flags = (((pseg->notes & sn_not_first) ?
734 ((flags & nf_all_from_arc) | nf_some_from_arc) : 0) |
735 ((pseg->notes & sn_dash_head) ? nf_dash_head : 0) |
736 ((pseg->notes & sn_dash_tail) ? nf_dash_tail : 0) |
737 (flags & ~nf_all_from_arc));
738 pl.e.p.x = sx, pl.e.p.y = sy;
739 if (!(udx | udy) || pseg->type == s_dash || pseg->type == s_gap) { /* degenerate or short */
740 /*
741 * If this is the first segment of the subpath,
742 * check the entire subpath for degeneracy.
743 * Otherwise, ignore the degenerate segment.
744 */
745 if (index != 0 && pseg->type != s_dash && pseg->type != s_gap)
746 continue;
747 /* Check for a degenerate subpath. */
748 while ((pseg = pseg->next) != 0 &&
749 pseg->type != s_start
750 ) {
751 if (is_dash_segment)
752 break;
753 if (pseg->type == s_dash || pseg->type == s_gap)
754 goto d1;
755 sx = pseg->pt.x, udx = sx - x;
756 sy = pseg->pt.y, udy = sy - y;
757 if (udx | udy) {
758 zero_length = false;
759 goto d;
760 }
761 }
762 if (pgs_lp->dot_length == 0 &&
763 pgs_lp->start_cap != gs_cap_round &&
764 pgs_lp->end_cap != gs_cap_round &&
765 !is_dash_segment) {
766 /* From PLRM, stroke operator :
767 If a subpath is degenerate (consists of a single-point closed path
768 or of two or more points at the same coordinates),
769 stroke paints it only if round line caps have been specified */
770 break;
771 }
772 /*
773 * If the subpath is a dash, take the orientation from the dash segment.
774 * Otherwise orient the dot according to the previous segment if
775 * any, or else the next segment if any, or else
776 * according to the specified dot orientation.
777 */
778 {
779 /* When passing here, either pseg == NULL or it points to the
780 start of the next subpaph. So we can't use pseg
781 for determining the segment direction.
782 In same time, psub->last may help, so use it. */
783 const segment *end = psub->last;
784
785 if (is_dash_segment) {
786 /* Nothing. */
787 } else if (end != 0 && (end->pt.x != x || end->pt.y != y))
788 sx = end->pt.x, sy = end->pt.y, udx = sx - x, udy = sy - y;
789 }
790 /*
791 * Compute the properly oriented dot length, and then
792 * draw the dot like a very short line.
793 */
794 if ((udx | udy) == 0) {
795 if (is_fzero(pgs_lp->dot_orientation.xy)) {
796 /* Portrait orientation, dot length = X */
797 udx = fixed_1;
798 } else {
799 /* Landscape orientation, dot length = Y */
800 udy = fixed_1;
801 }
802 }
803 if (sx == x && sy == y && (pseg == NULL || pseg->type == s_start)) {
804 double scale = device_dot_length /
805 hypot((double)udx, (double)udy);
806 fixed udx1, udy1;
807 /*
808 * If we're using butt caps, make sure the "line" is
809 * long enough to show up.
810 * Don't apply this with always_thin, becase
811 * draw thin line always rounds the length up.
812 */
813 if (!always_thin && (pgs_lp->start_cap == gs_cap_butt ||
814 pgs_lp->end_cap == gs_cap_butt ||
815 pgs_lp->dash_cap == gs_cap_butt)) {
816 fixed dmax = max(any_abs(udx), any_abs(udy));
817
818 if (dmax * scale < fixed_1)
819 scale = (float)fixed_1 / dmax;
820 }
821 udx1 = (fixed) (udx * scale);
822 udy1 = (fixed) (udy * scale);
823 sx = x + udx1;
824 sy = y + udy1;
825 }
826 /*
827 * Back up 1 segment to keep the bookkeeping straight.
828 */
829 pseg = (pseg != 0 ? pseg->prev : psub->last);
830 if (!is_dash_segment)
831 goto d;
832 pl.e.p.x = sx;
833 pl.e.p.y = sy;
834 }
835 pl.vector.x = udx;
836 pl.vector.y = udy;
837 if (always_thin) {
838 pl.e.cdelta.x = pl.e.cdelta.y = 0;
839 pl.width.x = pl.width.y = 0;
840 pl.thin = true;
841 } else {
842 if (uniform != 0) {
843 /* We can save a lot of work in this case. */
844 /* We know orient != orient_other. */
845 double dpx = udx, dpy = udy;
846 double wl = device_line_width_scale /
847 hypot(dpx, dpy);
848
849 pl.e.cdelta.x = (fixed) (dpx * wl);
850 pl.e.cdelta.y = (fixed) (dpy * wl);
851 /* The width is the cap delta rotated by */
852 /* 90 degrees. */
853 if (initial_matrix_reflected)
854 pl.width.x = pl.e.cdelta.y, pl.width.y = -pl.e.cdelta.x;
855 else
856 pl.width.x = -pl.e.cdelta.y, pl.width.y = pl.e.cdelta.x;
857 pl.thin = false; /* if not always_thin, */
858 /* then never thin. */
859
860 } else {
861 gs_point dpt; /* unscaled */
862 float wl;
863
864 gs_imager_idtransform(pis,
865 (float)udx, (float)udy, &dpt);
866 wl = line_width_and_scale /
867 hypot(dpt.x, dpt.y);
868 /* Construct the width vector in */
869 /* user space, still unscaled. */
870 dpt.x *= wl;
871 dpt.y *= wl;
872
873 /*
874 * We now compute both perpendicular
875 * and (optionally) parallel half-widths,
876 * as deltas in device space. We use
877 * a fixed-point, unscaled version of
878 * gs_dtransform. The second computation
879 * folds in a 90-degree rotation (in user
880 * space, before transforming) in the
881 * direction that corresponds to counter-
882 * clockwise in device space.
883 */
884 pl.e.cdelta.x = (fixed) (dpt.x * xx);
885 pl.e.cdelta.y = (fixed) (dpt.y * yy);
886 if (orient != orient_portrait)
887 pl.e.cdelta.x += (fixed) (dpt.y * yx),
888 pl.e.cdelta.y += (fixed) (dpt.x * xy);
889 if (!reflected ^ initial_matrix_reflected)
890 dpt.x = -dpt.x, dpt.y = -dpt.y;
891 pl.width.x = (fixed) (dpt.y * xx),
892 pl.width.y = -(fixed) (dpt.x * yy);
893 if (orient != orient_portrait)
894 pl.width.x -= (fixed) (dpt.x * yx),
895 pl.width.y += (fixed) (dpt.y * xy);
896 pl.thin = width_is_thin(&pl);
897 }
898 if (!pl.thin) {
899 if (index)
900 dev->sgr.stroke_stored = false;
901 adjust_stroke(dev, &pl, pis, false,
902 (pseg->prev == 0 || pseg->prev->type == s_start) &&
903 (pseg->next == 0 || pseg->next->type == s_start) &&
904 (zero_length || !is_closed),
905 COMBINE_FLAGS(flags));
906 compute_caps(&pl);
907 }
908 }
909 if (index++) {
910 gs_line_join join =
911 (pseg->notes & not_first ? curve_join : pgs_lp->join);
912 int first;
913 pl_ptr lptr;
914 bool ensure_closed;
915
916 if (join == gs_join_none) {
917 /* Fake the end of a subpath so we get */
918 /* caps instead of joins. */
919 first = 0;
920 lptr = 0;
921 index = 1;
922 } else {
923 first = (is_closed ? 1 : index - 2);
924 lptr = &pl;
925 }
926 #ifdef AVOID_JOINING_TO_DASH_GAPS
927 if (is_dash_segment) /* Never join to a dash segment */
928 lptr = NULL;
929 #endif
930 if (pseg->type == s_gap)
931 {
932 lptr = NULL;
933 /* We are always drawing one line segment behind, so make
934 * sure we don't draw the next one. */
935 index = 0;
936 }
937
938 ensure_closed = ((to_path == &stroke_path_body &&
939 lop_is_idempotent(pis->log_op)) ||
940 (lptr == NULL ? true : lptr->thin));
941 /* Draw the PREVIOUS line segment, joining it to lptr (or
942 * capping if lptr == NULL. */
943 code = (*line_proc) (to_path, to_path_reverse, ensure_closed,
944 first, &pl_prev, lptr,
945 pdevc, dev, pis, params, &cbox,
946 uniform, join, initial_matrix_reflected,
947 COMBINE_FLAGS(flags));
948 if (code < 0)
949 goto exit;
950 FILL_STROKE_PATH(pdev, always_thin, pcpath, false);
951 } else if (pseg->type == s_gap) {
952 /* If this segment is a gap, then we don't want to draw it
953 * next time! */
954 index = 0;
955 } else
956 pl_first = pl;
957 pl_prev = pl;
958 x = sx, y = sy;
959 flags = (flags<<4) | nf_all_from_arc;
960 }
961 if (index) {
962 /* If closed, join back to start, else cap. */
963 segment_notes notes = (pseg == 0 ?
964 (const segment *)spath->first_subpath :
965 pseg)->notes;
966 gs_line_join join = (notes & not_first ? curve_join :
967 pgs_lp->join);
968 gs_line_cap cap;
969 /* For some reason, the Borland compiler requires the cast */
970 /* in the following statement. */
971 pl_ptr lptr =
972 (!is_closed || join == gs_join_none || zero_length ?
973 (pl_ptr) 0 : (pl_ptr) & pl_first);
974
975 #ifdef AVOID_JOINING_TO_DASH_GAPS
976 if (lptr && psub->type == s_dash)
977 lptr = NULL;
978 #endif
979 /* If the subpath starts with a gap, then cap, don't join! */
980 if (lptr && psub->type == s_start && psub->next && psub->next->type == s_gap)
981 lptr = NULL;
982
983 flags = (((notes & sn_not_first) ?
984 ((flags & nf_all_from_arc) | nf_some_from_arc) : 0) |
985 ((notes & sn_dash_head) ? nf_dash_head : 0) |
986 ((notes & sn_dash_tail) ? nf_dash_tail : 0) |
987 (flags & ~nf_all_from_arc));
988 code = (*line_proc) (to_path, to_path_reverse, true,
989 index - 1, &pl_prev, lptr, pdevc,
990 dev, pis, params, &cbox, uniform, join,
991 initial_matrix_reflected,
992 COMBINE_FLAGS(flags));
993 if (code < 0)
994 goto exit;
995 FILL_STROKE_PATH(pdev, always_thin, pcpath, false);
996 cap = ((flags & nf_prev_dash_head) ?
997 pgs_lp->start_cap : pgs_lp->dash_cap);
998 if (traditional && lptr == 0 && cap != gs_cap_butt) {
999 /* Create the initial cap at last. */
1000 code = stroke_add_initial_cap_compat(to_path, &pl_first, index == 1, pdevc, dev, pis);
1001 if (code < 0)
1002 goto exit;
1003 FILL_STROKE_PATH(pdev, always_thin, pcpath, false);
1004 }
1005 }
1006 psub = (const subpath *)pseg;
1007 }
1008 if (to_path_reverse != NULL)
1009 code = gx_join_path_and_reverse(to_path, to_path_reverse);
1010 FILL_STROKE_PATH(pdev, always_thin, pcpath, true);
1011 exit:
1012 if (dev == (gx_device *)&cdev)
1013 cdev.target->sgr = cdev.sgr;
1014 if (to_path == &stroke_path_body)
1015 gx_path_free(&stroke_path_body, "gx_stroke_path_only error"); /* (only needed if error) */
1016 if (to_path_reverse == &stroke_path_reverse)
1017 gx_path_free(&stroke_path_reverse, "gx_stroke_path_only error");
1018 if (dash_count)
1019 gx_path_free(&dpath, "gx_stroke_path exit(dash path)");
1020 exf:
1021 if (ppath->curve_count)
1022 gx_path_free(&fpath, "gx_stroke_path exit(flattened path)");
1023 return code;
1024 }
1025
1026 int
gx_stroke_path_only(gx_path * ppath,gx_path * to_path,gx_device * pdev,const gs_imager_state * pis,const gx_stroke_params * params,const gx_device_color * pdevc,const gx_clip_path * pcpath)1027 gx_stroke_path_only(gx_path * ppath, gx_path * to_path, gx_device * pdev,
1028 const gs_imager_state * pis, const gx_stroke_params * params,
1029 const gx_device_color * pdevc, const gx_clip_path * pcpath)
1030 {
1031 int code;
1032
1033 if (vd_allowed('S')) {
1034 vd_get_dc('S');
1035 if (vd_enabled) {
1036 vd_set_shift(0, 100);
1037 vd_set_scale(0.03);
1038 vd_set_origin(0, 0);
1039 vd_erase(RGB(192, 192, 192));
1040 }
1041 }
1042 if (vd_enabled)
1043 vd_setcolor(pdevc->colors.pure);
1044 code = gx_stroke_path_only_aux(ppath, to_path, pdev, pis, params, pdevc, pcpath);
1045 if (vd_allowed('S'))
1046 vd_release_dc;
1047 return code;
1048 }
1049
1050 /* ------ Internal routines ------ */
1051
1052 /*
1053 * Test whether a line is thin, i.e., whether the half-width, measured
1054 * perpendicular to the line in device space, is less than 0.5 pixel.
1055 * Unfortunately, the width values we computed are perpendicular to the
1056 * line in *user* space, so we may have to do some extra work.
1057 */
1058 static bool
width_is_thin(pl_ptr plp)1059 width_is_thin(pl_ptr plp)
1060 {
1061 fixed dx, dy, wx = plp->width.x, wy = plp->width.y;
1062
1063 /* If the line is horizontal or vertical, things are easy. */
1064 if ((dy = plp->vector.y) == 0)
1065 return any_abs(wy) < fixed_half;
1066 if ((dx = plp->vector.x) == 0)
1067 return any_abs(wx) < fixed_half;
1068
1069 /*
1070 * If both horizontal and vertical widths are less than
1071 * 0.5, the line is thin.
1072 */
1073 if (any_abs(wx) < fixed_half && any_abs(wy) < fixed_half)
1074 return true;
1075
1076 /*
1077 * We have to do this the hard way, by actually computing the
1078 * perpendicular distance. The distance from the point (U,V)
1079 * from a line from (0,0) to (C,D) is
1080 * abs(C*V - D*U) / sqrt(C^2 + D^2)
1081 * In this case, (U,V) is plp->width, and (C,D) is (dx,dy).
1082 */
1083 {
1084 double C = dx, D = dy;
1085 double num = C * wy - D * wx;
1086 double denom = hypot(C, D);
1087
1088 /* both num and denom are scaled by fixed_scale^2, */
1089 /* so we don't need to do any de-scaling for the test. */
1090 return fabs(num) < denom * 0.5;
1091 }
1092 }
1093
1094 /* Adjust the endpoints and width of a stroke segment along a specified axis */
1095 static void
adjust_stroke_transversal(pl_ptr plp,const gs_imager_state * pis,bool thin,bool horiz)1096 adjust_stroke_transversal(pl_ptr plp, const gs_imager_state * pis, bool thin, bool horiz)
1097 {
1098 fixed *pw;
1099 fixed *pov;
1100 fixed *pev;
1101 fixed w, w2;
1102 fixed adj2;
1103
1104 if (horiz) {
1105 /* More horizontal stroke */
1106 pw = &plp->width.y, pov = &plp->o.p.y, pev = &plp->e.p.y;
1107 adj2 = STROKE_ADJUSTMENT(thin, pis, y) << 1;
1108 } else {
1109 /* More vertical stroke */
1110 pw = &plp->width.x, pov = &plp->o.p.x, pev = &plp->e.p.x;
1111 adj2 = STROKE_ADJUSTMENT(thin, pis, x) << 1;
1112 }
1113 /* Round the larger component of the width up or down, */
1114 /* whichever way produces a result closer to the correct width. */
1115 /* Note that just rounding the larger component */
1116 /* may not produce the correct result. */
1117 w = *pw;
1118 if (w > 0)
1119 w2 = fixed_rounded(w << 1); /* full line width */
1120 else
1121 w2 = -fixed_rounded(-w << 1); /* full line width */
1122 if (w2 == 0 && *pw != 0) {
1123 /* Make sure thin lines don't disappear. */
1124 w2 = (*pw < 0 ? -fixed_1 + adj2 : fixed_1 - adj2);
1125 *pw = arith_rshift_1(w2);
1126 }
1127 /* Only adjust the endpoints if the line is horizontal or vertical. */
1128 if (*pov == *pev) {
1129 /* We're going to round the endpoint coordinates, so */
1130 /* take the fill adjustment into account now. */
1131 if (w >= 0)
1132 w2 += adj2;
1133 else
1134 w2 = adj2 - w2;
1135 if (w2 & fixed_1) /* odd width, move to half-pixel */
1136 *pov = *pev = fixed_floor(*pov) + fixed_half;
1137 else /* even width, move to pixel */
1138 *pov = *pev = fixed_rounded(*pov);
1139
1140 }
1141 }
1142
1143 static void
adjust_stroke_longitude(pl_ptr plp,const gs_imager_state * pis,bool thin,bool horiz,gs_line_cap start_cap,gs_line_cap end_cap)1144 adjust_stroke_longitude(pl_ptr plp, const gs_imager_state * pis,
1145 bool thin, bool horiz,
1146 gs_line_cap start_cap, gs_line_cap end_cap)
1147 {
1148
1149 fixed *pow = (horiz ? &plp->o.p.y : &plp->o.p.x);
1150 fixed *pew = (horiz ? &plp->e.p.y : &plp->e.p.x);
1151
1152 /* Only adjust the endpoints if the line is horizontal or vertical.
1153 Debugged with pdfwrite->ppmraw 72dpi file2.pdf */
1154 if (*pow == *pew) {
1155 fixed *pov = (horiz ? &plp->o.p.x : &plp->o.p.y);
1156 fixed *pev = (horiz ? &plp->e.p.x : &plp->e.p.y);
1157 fixed length = any_abs(*pov - *pev);
1158 fixed length_r, length_r_2;
1159 fixed mv = (*pov + *pev) / 2, mv_r;
1160 fixed adj2 = (horiz ? STROKE_ADJUSTMENT(thin, pis, x)
1161 : STROKE_ADJUSTMENT(thin, pis, y)) << 1;
1162
1163 /* fixme :
1164 The best value for adjust_longitude is whether
1165 the dash is isolated and doesn't cover entire segment.
1166 The current data structure can't pass this info.
1167 Therefore we restrict adjust_stroke_longitude with 1 pixel length.
1168 */
1169 if (length > fixed_1) /* comparefiles/file2.pdf */
1170 return;
1171 if (start_cap == gs_cap_butt || end_cap == gs_cap_butt) {
1172 length_r = fixed_rounded(length);
1173 if (length_r < fixed_1)
1174 length_r = fixed_1;
1175 length_r_2 = length_r / 2;
1176 } else {
1177 /* Account width for proper placing cap centers. */
1178 fixed width = any_abs(horiz ? plp->width.y : plp->width.x);
1179
1180 length_r = fixed_rounded(length + width * 2 + adj2);
1181 length_r_2 = fixed_rounded(length) / 2;
1182 }
1183 if (length_r & fixed_1)
1184 mv_r = fixed_floor(mv) + fixed_half;
1185 else
1186 mv_r = fixed_floor(mv);
1187 if (*pov < *pev) {
1188 *pov = mv_r - length_r_2;
1189 *pev = mv_r + length_r_2;
1190 } else {
1191 *pov = mv_r + length_r_2;
1192 *pev = mv_r - length_r_2;
1193 }
1194 }
1195 }
1196
1197 /* Adjust the endpoints and width of a stroke segment */
1198 /* to achieve more uniform rendering. */
1199 /* Only o.p, e.p, e.cdelta, and width have been set. */
1200 static void
adjust_stroke(gx_device * dev,pl_ptr plp,const gs_imager_state * pis,bool thin,bool adjust_longitude,note_flags flags)1201 adjust_stroke(gx_device *dev, pl_ptr plp, const gs_imager_state * pis,
1202 bool thin, bool adjust_longitude, note_flags flags)
1203 {
1204 bool horiz, adjust = true;
1205 gs_line_cap start_cap = (flags & nf_dash_head ?
1206 pis->line_params.dash_cap :
1207 pis->line_params.start_cap);
1208 gs_line_cap end_cap = (flags & nf_dash_tail ?
1209 pis->line_params.dash_cap :
1210 pis->line_params.end_cap);
1211
1212 /* If stroke_adjustment is disabled, or this isn't a horizontal or
1213 * vertical line, then bale. */
1214 if (!pis->stroke_adjust || (plp->width.x != 0 && plp->width.y != 0)) {
1215 dev->sgr.stroke_stored = false;
1216 return; /* don't adjust */
1217 }
1218 /* Recognizing gradients, which some obsolete software
1219 represent as a set of parallel strokes.
1220 Such strokes must not be adjusted - bug 687974. */
1221 if (dev->sgr.stroke_stored &&
1222 (start_cap == gs_cap_butt || end_cap == gs_cap_butt) &&
1223 dev->sgr.orig[3].x == plp->vector.x && dev->sgr.orig[3].y == plp->vector.y) {
1224 /* Parallel. */
1225 if ((int64_t)(plp->o.p.x - dev->sgr.orig[0].x) * plp->vector.x ==
1226 (int64_t)(plp->o.p.y - dev->sgr.orig[0].y) * plp->vector.y &&
1227 (int64_t)(plp->e.p.x - dev->sgr.orig[1].x) * plp->vector.x ==
1228 (int64_t)(plp->e.p.y - dev->sgr.orig[1].y) * plp->vector.y) {
1229 /* Transversal shift. */
1230 if (any_abs(plp->o.p.x - dev->sgr.orig[0].x) <= any_abs(plp->width.x + dev->sgr.orig[2].x) &&
1231 any_abs(plp->o.p.y - dev->sgr.orig[0].y) <= any_abs(plp->width.y + dev->sgr.orig[2].y) &&
1232 any_abs(plp->e.p.x - dev->sgr.orig[1].x) <= any_abs(plp->width.x + dev->sgr.orig[2].x) &&
1233 any_abs(plp->e.p.y - dev->sgr.orig[1].y) <= any_abs(plp->width.y + dev->sgr.orig[2].y)) {
1234 /* The strokes were contacting or overlapping. */
1235 if (any_abs(plp->o.p.x - dev->sgr.orig[0].x) >= any_abs(plp->width.x + dev->sgr.orig[2].x) / 2 &&
1236 any_abs(plp->o.p.y - dev->sgr.orig[0].y) >= any_abs(plp->width.y + dev->sgr.orig[2].y) / 2 &&
1237 any_abs(plp->e.p.x - dev->sgr.orig[1].x) >= any_abs(plp->width.x + dev->sgr.orig[2].x) / 2 &&
1238 any_abs(plp->e.p.y - dev->sgr.orig[1].y) >= any_abs(plp->width.y + dev->sgr.orig[2].y) / 2) {
1239 /* The strokes were not much overlapping. */
1240 if (!(any_abs(plp->o.p.x - dev->sgr.adjusted[0].x) <= any_abs(plp->width.x + dev->sgr.adjusted[2].x) &&
1241 any_abs(plp->o.p.y - dev->sgr.adjusted[0].y) <= any_abs(plp->width.y + dev->sgr.adjusted[2].y) &&
1242 any_abs(plp->e.p.x - dev->sgr.adjusted[1].x) <= any_abs(plp->width.x + dev->sgr.adjusted[2].x) &&
1243 any_abs(plp->e.p.y - dev->sgr.adjusted[1].y) <= any_abs(plp->width.y + dev->sgr.adjusted[2].y))) {
1244 /* they became not contacting.
1245 We should not have adjusted the last stroke. Since if we did,
1246 lets change the current one to restore the contact,
1247 so that we don't leave gaps when rasterising. See bug 687974.
1248 */
1249 fixed delta_w_x = (dev->sgr.adjusted[2].x - dev->sgr.orig[2].x);
1250 fixed delta_w_y = (dev->sgr.adjusted[2].y - dev->sgr.orig[2].y);
1251 fixed shift_o_x = (dev->sgr.adjusted[0].x - dev->sgr.orig[0].x);
1252 fixed shift_o_y = (dev->sgr.adjusted[0].y - dev->sgr.orig[0].y);
1253 fixed shift_e_x = (dev->sgr.adjusted[1].x - dev->sgr.orig[1].x); /* Must be same, but we prefer clarity. */
1254 fixed shift_e_y = (dev->sgr.adjusted[1].y - dev->sgr.orig[1].y);
1255
1256 if (plp->o.p.x < dev->sgr.orig[0].x ||
1257 (plp->o.p.x == dev->sgr.orig[0].x && plp->o.p.y < dev->sgr.orig[0].y)) {
1258 /* Left contact, adjust to keep the contact. */
1259 if_debug4('O', "[O]don't adjust {{%f,%f},{%f,%f}}\n",
1260 fixed2float(plp->o.p.x), fixed2float(plp->o.p.y),
1261 fixed2float(plp->e.p.x), fixed2float(plp->e.p.y));
1262 plp->width.x += (shift_o_x - delta_w_x) / 2;
1263 plp->width.y += (shift_o_y - delta_w_y) / 2;
1264 plp->o.p.x += (shift_o_x - delta_w_x) / 2;
1265 plp->o.p.y += (shift_o_y - delta_w_y) / 2;
1266 plp->e.p.x += (shift_e_x - delta_w_x) / 2;
1267 plp->e.p.y += (shift_e_y - delta_w_y) / 2;
1268 adjust = false;
1269 } else {
1270 /* Right contact, adjust to keep the contact. */
1271 if_debug4('O', "[O]don't adjust {{%f,%f},{%f,%f}}\n",
1272 fixed2float(plp->o.p.x), fixed2float(plp->o.p.y),
1273 fixed2float(plp->e.p.x), fixed2float(plp->e.p.y));
1274 plp->width.x -= (shift_o_x + delta_w_x) / 2;
1275 plp->width.y -= (shift_o_y + delta_w_y) / 2;
1276 plp->o.p.x += (shift_o_x + delta_w_x) / 2;
1277 plp->o.p.y += (shift_o_y + delta_w_y) / 2;
1278 plp->e.p.x += (shift_e_x + delta_w_x) / 2;
1279 plp->e.p.y += (shift_e_y + delta_w_y) / 2;
1280 adjust = false;
1281 }
1282 }
1283 }
1284 }
1285 }
1286 }
1287 if ((start_cap == gs_cap_butt) || (end_cap == gs_cap_butt)) {
1288 dev->sgr.stroke_stored = true;
1289 dev->sgr.orig[0] = plp->o.p;
1290 dev->sgr.orig[1] = plp->e.p;
1291 dev->sgr.orig[2] = plp->width;
1292 dev->sgr.orig[3] = plp->vector;
1293 } else
1294 dev->sgr.stroke_stored = false;
1295 if (adjust) {
1296 horiz = (any_abs(plp->width.x) <= any_abs(plp->width.y));
1297 adjust_stroke_transversal(plp, pis, thin, horiz);
1298 if (adjust_longitude)
1299 adjust_stroke_longitude(plp, pis, thin, horiz, start_cap, end_cap);
1300 }
1301 if ((start_cap == gs_cap_butt) || (end_cap == gs_cap_butt)) {
1302 dev->sgr.adjusted[0] = plp->o.p;
1303 dev->sgr.adjusted[1] = plp->e.p;
1304 dev->sgr.adjusted[2] = plp->width;
1305 dev->sgr.adjusted[3] = plp->vector;
1306 }
1307 }
1308
1309 /* Compute the intersection of two lines. This is a messy algorithm */
1310 /* that somehow ought to be useful in more places than just here.... */
1311 /* If the lines are (nearly) parallel, return -1 without setting *pi; */
1312 /* otherwise, return 0 if the intersection is beyond *pp1 and *pp2 in */
1313 /* the direction determined by *pd1 and *pd2, and 1 otherwise. */
1314 static int
line_intersect(p_ptr pp1,p_ptr pd1,p_ptr pp2,p_ptr pd2,p_ptr pi)1315 line_intersect(
1316 p_ptr pp1, /* point on 1st line */
1317 p_ptr pd1, /* slope of 1st line (dx,dy) */
1318 p_ptr pp2, /* point on 2nd line */
1319 p_ptr pd2, /* slope of 2nd line */
1320 p_ptr pi)
1321 { /* return intersection here */
1322 /* We don't have to do any scaling, the factors all work out right. */
1323 double u1 = pd1->x, v1 = pd1->y;
1324 double u2 = pd2->x, v2 = pd2->y;
1325 double denom = u1 * v2 - u2 * v1;
1326 double xdiff = pp2->x - pp1->x;
1327 double ydiff = pp2->y - pp1->y;
1328 double f1;
1329 double max_result = any_abs(denom) * (double)max_fixed;
1330
1331 #ifdef DEBUG
1332 if (gs_debug_c('O')) {
1333 dlprintf4("[o]Intersect %f,%f(%f/%f)",
1334 fixed2float(pp1->x), fixed2float(pp1->y),
1335 fixed2float(pd1->x), fixed2float(pd1->y));
1336 dlprintf4(" & %f,%f(%f/%f),\n",
1337 fixed2float(pp2->x), fixed2float(pp2->y),
1338 fixed2float(pd2->x), fixed2float(pd2->y));
1339 dlprintf3("\txdiff=%f ydiff=%f denom=%f ->\n",
1340 xdiff, ydiff, denom);
1341 }
1342 #endif
1343 /* Check for degenerate result. */
1344 if (any_abs(xdiff) >= max_result || any_abs(ydiff) >= max_result) {
1345 /* The lines are nearly parallel, */
1346 /* or one of them has zero length. Punt. */
1347 if_debug0('O', "\tdegenerate!\n");
1348 return -1;
1349 }
1350 f1 = (v2 * xdiff - u2 * ydiff) / denom;
1351 pi->x = pp1->x + (fixed) (f1 * u1);
1352 pi->y = pp1->y + (fixed) (f1 * v1);
1353 if_debug2('O', "\t%f,%f\n",
1354 fixed2float(pi->x), fixed2float(pi->y));
1355 return (f1 >= 0 && (v1 * xdiff >= u1 * ydiff ? denom >= 0 : denom < 0) ? 0 : 1);
1356 }
1357
1358 /* Set up the width and delta parameters for a thin line. */
1359 /* We only approximate the width and height. */
1360 static void
set_thin_widths(register pl_ptr plp)1361 set_thin_widths(register pl_ptr plp)
1362 {
1363 fixed dx = plp->e.p.x - plp->o.p.x, dy = plp->e.p.y - plp->o.p.y;
1364
1365 #define TRSIGN(v, c) ((v) >= 0 ? (c) : -(c))
1366 if (any_abs(dx) > any_abs(dy)) {
1367 plp->width.x = plp->e.cdelta.y = 0;
1368 plp->width.y = plp->e.cdelta.x = TRSIGN(dx, fixed_half);
1369 } else {
1370 plp->width.y = plp->e.cdelta.x = 0;
1371 plp->width.x = -(plp->e.cdelta.y = TRSIGN(dy, fixed_half));
1372 }
1373 #undef TRSIGN
1374 }
1375
1376 /* Draw a line on the device. */
1377 /* Treat no join the same as a bevel join. */
1378 /* rpath should always be NULL, hence ensure_closed can be ignored */
1379 static int
stroke_fill(gx_path * ppath,gx_path * rpath,bool ensure_closed,int first,register pl_ptr plp,pl_ptr nplp,const gx_device_color * pdevc,gx_device * dev,const gs_imager_state * pis,const gx_stroke_params * params,const gs_fixed_rect * pbbox,int uniform,gs_line_join join,bool reflected,note_flags flags)1380 stroke_fill(gx_path * ppath, gx_path * rpath, bool ensure_closed, int first,
1381 register pl_ptr plp, pl_ptr nplp, const gx_device_color * pdevc,
1382 gx_device * dev, const gs_imager_state * pis,
1383 const gx_stroke_params * params, const gs_fixed_rect * pbbox,
1384 int uniform, gs_line_join join, bool reflected,
1385 note_flags flags)
1386 {
1387 const fixed lix = plp->o.p.x;
1388 const fixed liy = plp->o.p.y;
1389 const fixed litox = plp->e.p.x;
1390 const fixed litoy = plp->e.p.y;
1391
1392 if (plp->thin) {
1393 /* Minimum-width line, don't have to be careful with caps/joins. */
1394 return (*dev_proc(dev, draw_thin_line))(dev, lix, liy, litox, litoy,
1395 pdevc, pis->log_op,
1396 pis->fill_adjust.x,
1397 pis->fill_adjust.y);
1398 }
1399 /* Check for being able to fill directly. */
1400 {
1401 const gx_line_params *pgs_lp = gs_currentlineparams_inline(pis);
1402 gs_line_cap start_cap = (flags & nf_dash_head ?
1403 pgs_lp->dash_cap : pgs_lp->start_cap);
1404 gs_line_cap end_cap = (flags & nf_dash_tail ?
1405 pgs_lp->dash_cap : pgs_lp->end_cap);
1406
1407 if (first != 0)
1408 start_cap = gs_cap_butt;
1409 if (nplp != 0)
1410 end_cap = gs_cap_butt;
1411 if (!plp->thin && (nplp == 0 || !nplp->thin)
1412 && (start_cap == gs_cap_butt || start_cap == gs_cap_square)
1413 && (end_cap == gs_cap_butt || end_cap == gs_cap_square)
1414 && (join == gs_join_bevel || join == gs_join_miter ||
1415 join == gs_join_none)
1416 && (pis->fill_adjust.x | pis->fill_adjust.y) == 0
1417 && lop_is_idempotent(pis->log_op)
1418 ) {
1419 gs_fixed_point points[6];
1420 int npoints, code;
1421 fixed ax, ay, bx, by;
1422
1423 npoints = cap_points(start_cap, &plp->o, points);
1424 if (nplp == 0)
1425 code = cap_points(end_cap, &plp->e, points + npoints);
1426 else
1427 code = line_join_points(pgs_lp, plp, nplp, points + npoints,
1428 (uniform ? (gs_matrix *) 0 :
1429 &ctm_only(pis)), join, reflected);
1430 if (code < 0)
1431 goto general;
1432 /* Make sure the parallelogram fill won't overflow. */
1433 #define SUB_OVERFLOWS(r, u, v)\
1434 (((r = u - v) ^ u) < 0 && (u ^ v) < 0)
1435 if (SUB_OVERFLOWS(ax, points[0].x, points[1].x) ||
1436 SUB_OVERFLOWS(ay, points[0].y, points[1].y) ||
1437 SUB_OVERFLOWS(bx, points[2].x, points[1].x) ||
1438 SUB_OVERFLOWS(by, points[2].y, points[1].y)
1439 )
1440 goto general;
1441 #undef SUB_OVERFLOWS
1442 if (nplp != 0) {
1443 if (join == gs_join_miter) {
1444 /* Make sure we have a bevel and not a miter. */
1445 if (!(points[2].x == plp->e.co.x &&
1446 points[2].y == plp->e.co.y &&
1447 points[5].x == plp->e.ce.x &&
1448 points[5].y == plp->e.ce.y)
1449 )
1450 goto fill;
1451 } {
1452 const gs_fixed_point *bevel = points + 2;
1453
1454 /* Identify which 3 points define the bevel triangle. */
1455 if (points[3].x == nplp->o.p.x &&
1456 points[3].y == nplp->o.p.y
1457 )
1458 ++bevel;
1459 /* Fill the bevel. */
1460 code = (*dev_proc(dev, fill_triangle)) (dev,
1461 bevel->x, bevel->y,
1462 bevel[1].x - bevel->x, bevel[1].y - bevel->y,
1463 bevel[2].x - bevel->x, bevel[2].y - bevel->y,
1464 pdevc, pis->log_op);
1465 if (code < 0)
1466 return code;
1467 }
1468 }
1469 /* Fill the body of the stroke. */
1470 return (*dev_proc(dev, fill_parallelogram)) (dev,
1471 points[1].x, points[1].y,
1472 ax, ay, bx, by,
1473 pdevc, pis->log_op);
1474 fill:
1475 code = add_points(ppath, points, npoints + code, true);
1476 if (code < 0)
1477 return code;
1478 return gx_path_close_subpath(ppath);
1479 }
1480 }
1481 /* General case: construct a path for the fill algorithm. */
1482 general:
1483 return stroke_add(ppath, rpath, ensure_closed, first, plp, nplp, pdevc,
1484 dev, pis, params, pbbox, uniform, join, reflected,
1485 flags);
1486 }
1487
1488 /* Add a segment to the path. This handles all the complex cases. */
1489 static int
stroke_add(gx_path * ppath,gx_path * rpath,bool ensure_closed,int first,pl_ptr plp,pl_ptr nplp,const gx_device_color * pdevc,gx_device * dev,const gs_imager_state * pis,const gx_stroke_params * params,const gs_fixed_rect * ignore_pbbox,int uniform,gs_line_join join,bool reflected,note_flags flags)1490 stroke_add(gx_path * ppath, gx_path * rpath, bool ensure_closed, int first,
1491 pl_ptr plp, pl_ptr nplp, const gx_device_color * pdevc,
1492 gx_device * dev, const gs_imager_state * pis,
1493 const gx_stroke_params * params,
1494 const gs_fixed_rect * ignore_pbbox, int uniform,
1495 gs_line_join join, bool reflected, note_flags flags)
1496 {
1497 const gx_line_params *pgs_lp = gs_currentlineparams_inline(pis);
1498 gs_fixed_point points[8];
1499 int npoints;
1500 int code;
1501 bool moveto_first = true;
1502 gs_line_cap start_cap = (flags & nf_dash_head ?
1503 pgs_lp->dash_cap : pgs_lp->start_cap);
1504 gs_line_cap end_cap = (flags & nf_dash_tail ?
1505 pgs_lp->dash_cap : pgs_lp->end_cap);
1506
1507 if (plp->thin) {
1508 /* We didn't set up the endpoint parameters before, */
1509 /* because the line was thin. Do it now. */
1510 set_thin_widths(plp);
1511 adjust_stroke(dev, plp, pis, true, first == 0 && nplp == 0, flags);
1512 compute_caps(plp);
1513 }
1514 /* Create an initial cap if desired. */
1515 if (first == 0 && start_cap == gs_cap_round) {
1516 vd_moveto(plp->o.co.x, plp->o.co.y);
1517 if ((code = gx_path_add_point(ppath, plp->o.co.x, plp->o.co.y)) < 0 ||
1518 (code = add_pie_cap(ppath, &plp->o)) < 0)
1519 return code;
1520 npoints = 0;
1521 moveto_first = false;
1522 } else {
1523 if ((npoints = cap_points((first == 0 ? start_cap : gs_cap_butt),
1524 &plp->o, points)) < 0)
1525 return npoints;
1526 }
1527 if (nplp == 0) {
1528 /* Add a final cap. */
1529 if (end_cap == gs_cap_round) {
1530 ASSIGN_POINT(&points[npoints], plp->e.co);
1531 vd_lineto(points[npoints].x, points[npoints].y);
1532 ++npoints;
1533 if ((code = add_points(ppath, points, npoints, moveto_first)) < 0)
1534 return code;
1535 code = add_pie_cap(ppath, &plp->e);
1536 goto done;
1537 }
1538 code = cap_points(end_cap, &plp->e, points + npoints);
1539 } else if (nplp->thin) /* no join */
1540 code = cap_points(gs_cap_butt, &plp->e, points + npoints);
1541 else if (join == gs_join_round) {
1542 ASSIGN_POINT(&points[npoints], plp->e.co);
1543 vd_lineto(points[npoints].x, points[npoints].y);
1544 ++npoints;
1545 if ((code = add_points(ppath, points, npoints, moveto_first)) < 0)
1546 return code;
1547 code = add_pie_join(ppath, plp, nplp, reflected, true);
1548 goto done;
1549 } else if (flags & nf_all_from_arc) {
1550 /* If all the segments in 'prev' and 'current' are from a curve
1551 * then the join should actually be a round one, because it would
1552 * have been round if we had flattened it enough. */
1553 ASSIGN_POINT(&points[npoints], plp->e.co);
1554 vd_lineto(points[npoints].x, points[npoints].y);
1555 ++npoints;
1556 if ((code = add_points(ppath, points, npoints, moveto_first)) < 0)
1557 return code;
1558 code = add_pie_join(ppath, plp, nplp, reflected, false);
1559 goto done;
1560 } else /* non-round join */
1561 code = line_join_points(pgs_lp, plp, nplp, points + npoints,
1562 (uniform ? (gs_matrix *) 0 : &ctm_only(pis)),
1563 join, reflected);
1564 if (code < 0)
1565 return code;
1566 code = add_points(ppath, points, npoints + code, moveto_first);
1567 done:
1568 if (code < 0)
1569 return code;
1570 vd_closepath;
1571 if ((flags & nf_some_from_arc) && (!plp->thin) &&
1572 (nplp != NULL) && (!nplp->thin))
1573 code = join_under_pie(ppath, plp, nplp, reflected);
1574 return gx_path_close_subpath(ppath);
1575 }
1576
1577 /* Add a segment to the path.
1578 * This works by crafting 2 paths, one for each edge, that will later be
1579 * merged together. */
1580 static int
stroke_add_fast(gx_path * ppath,gx_path * rpath,bool ensure_closed,int first,pl_ptr plp,pl_ptr nplp,const gx_device_color * pdevc,gx_device * dev,const gs_imager_state * pis,const gx_stroke_params * params,const gs_fixed_rect * ignore_pbbox,int uniform,gs_line_join join,bool reflected,note_flags flags)1581 stroke_add_fast(gx_path * ppath, gx_path * rpath, bool ensure_closed, int first,
1582 pl_ptr plp, pl_ptr nplp, const gx_device_color * pdevc,
1583 gx_device * dev, const gs_imager_state * pis,
1584 const gx_stroke_params * params,
1585 const gs_fixed_rect * ignore_pbbox, int uniform,
1586 gs_line_join join, bool reflected, note_flags flags)
1587 {
1588 const gx_line_params *pgs_lp = gs_currentlineparams_inline(pis);
1589 gs_fixed_point points[8];
1590 gs_fixed_point rpoints[8];
1591 int npoints = 0;
1592 int nrpoints = 0;
1593 int code;
1594 bool moveto_first = false;
1595 bool rmoveto_first = false;
1596 gs_line_cap start_cap, end_cap;
1597
1598 if (plp->thin) {
1599 /* We didn't set up the endpoint parameters before, */
1600 /* because the line was thin. Do it now. */
1601 set_thin_widths(plp);
1602 adjust_stroke(dev, plp, pis, true, first == 0 && nplp == 0, flags);
1603 compute_caps(plp);
1604 }
1605 start_cap = (flags & nf_dash_head ?
1606 pgs_lp->dash_cap : pgs_lp->start_cap);
1607 end_cap = (flags & nf_dash_tail ?
1608 pgs_lp->dash_cap : pgs_lp->end_cap);
1609 /* If we're starting a new rpath here, we need to fake a new cap.
1610 * Don't interfere if we would have been doing a cap anyway. */
1611 if (gx_path_is_void(rpath) && (first != 0)) {
1612 first = 0;
1613 start_cap = gs_cap_butt;
1614 end_cap = gs_cap_butt;
1615 moveto_first = true;
1616 rmoveto_first = true;
1617 }
1618 if (first == 0) {
1619 /* Create an initial cap. */
1620 if (start_cap == gs_cap_round) {
1621 vd_moveto(plp->o.co.x, plp->o.co.y);
1622 if ((code = gx_path_add_point(ppath, plp->o.co.x, plp->o.co.y)) < 0 ||
1623 (code = add_pie_cap(ppath, &plp->o)) < 0)
1624 return code;
1625 moveto_first = false;
1626 } else {
1627 if ((npoints = cap_points(start_cap, &plp->o, points)) < 0)
1628 return npoints;
1629 moveto_first = true;
1630 }
1631 rmoveto_first = true;
1632 ASSIGN_POINT(&rpoints[0], plp->o.co);
1633 nrpoints = 1;
1634 }
1635 /* Add points to move us along the edges of this stroke */
1636 ASSIGN_POINT(&points [npoints ], plp->e.co);
1637 ASSIGN_POINT(&rpoints[nrpoints], plp->e.ce);
1638 npoints++;
1639 nrpoints++;
1640 if ((code = add_points(ppath, points, npoints, moveto_first)) < 0)
1641 return code;
1642 if ((code = add_points(rpath, rpoints, nrpoints, rmoveto_first)) < 0)
1643 return code;
1644 npoints = 0;
1645 nrpoints = 0;
1646
1647 if (nplp == 0) { /* Add a final cap. */
1648 if (end_cap == gs_cap_round) {
1649 code = add_pie_cap(ppath, &plp->e);
1650 } else {
1651 code = cap_points(end_cap, &plp->e, points);
1652 npoints = code;
1653 }
1654 } else if (nplp->thin) { /* no join */
1655 code = cap_points(gs_cap_butt, &plp->e, points);
1656 npoints = code;
1657 } else {
1658 /* We need to do a join */
1659 double l, r;
1660
1661 l = (double)(plp->width.x) /* x1 */ * (nplp->width.y) /* y2 */;
1662 r = (double)(nplp->width.x) /* x2 */ * (plp->width.y) /* y1 */;
1663
1664 if ((l == r) && (join == gs_join_round)) {
1665 /* Do a cap, and leave the point on the same side as it was
1666 * originally. This is required for paths that come to a stop
1667 * and then reverse themselves, but may produce more complexity
1668 * than we'd really like at the ends of smooth beziers. */
1669 code = add_pie_cap(ppath, &plp->e);
1670 if (code >= 0)
1671 code = gx_path_add_line(ppath, plp->e.co.x, plp->e.co.y);
1672 } else if ((l > r) ^ reflected) {
1673 /* CCW rotation. Join in the forward path. "Underjoin" in the
1674 * reverse path. */
1675 /* RJW: Ideally we should include the "|| flags" clause in
1676 * the following condition. This forces all joins between
1677 * line segments generated from arcs to be round. This would
1678 * solve some flatness issues, but makes some pathological
1679 * cases incredibly slow. */
1680 if ((join == gs_join_round)
1681 /* || (flags & nf_all_from_arc) */) {
1682 code = add_pie_join_fast_ccw(ppath, plp, nplp, reflected);
1683 } else { /* non-round join */
1684 code = line_join_points_fast_ccw(pgs_lp, plp, nplp,
1685 points,
1686 (uniform ? (gs_matrix *) 0 :
1687 &ctm_only(pis)),
1688 join);
1689 npoints = code;
1690 }
1691 if (code < 0)
1692 return code;
1693 /* The underjoin */
1694 if (!(flags & nf_some_from_arc)) {
1695 /* RJW: This is an approximation. We ought to draw a line
1696 * back to nplp->o.p, and then independently fill any exposed
1697 * region under the curve with a round join. Sadly, that's
1698 * a) really hard to do, and b) makes certain pathological
1699 * filling cases MUCH slower due to the greater number of
1700 * "cross-segment" line segments this produces. Instead,
1701 * we just skip the line to the middle, and join across the
1702 * bottom instead. This is akin to what other graphics libs
1703 * do (such as fitz, libart, etc). It's not perfect but in
1704 * most cases it's close, and results in faster to fill
1705 * paths.
1706 */
1707 code = gx_path_add_line(rpath, nplp->o.p.x, nplp->o.p.y);
1708 if (code < 0)
1709 return code;
1710 }
1711 code = gx_path_add_line(rpath, nplp->o.co.x, nplp->o.co.y);
1712 } else {
1713 /* CW rotation. Join in the reverse path. "Underjoin" in the
1714 * forward path. */
1715 /* RJW: Ideally we should include the "|| flags" clause in
1716 * the following condition. This forces all joins between
1717 * line segments generated from arcs to be round. This would
1718 * solve some flatness issues, but makes some pathological
1719 * cases incredibly slow. */
1720 if ((join == gs_join_round)
1721 /* || (flags & nf_all_from_arc) */) {
1722 code = add_pie_join_fast_cw(rpath, plp, nplp, reflected);
1723 } else { /* non-round join */
1724 code = line_join_points_fast_cw(pgs_lp, plp, nplp,
1725 rpoints,
1726 (uniform ? (gs_matrix *) 0 :
1727 &ctm_only(pis)),
1728 join);
1729 nrpoints = code;
1730 }
1731 if (code < 0)
1732 return code;
1733 /* The underjoin */
1734 if (!(flags & nf_some_from_arc)) {
1735 /* RJW: This is an approximation. We ought to draw a line
1736 * back to nplp->o.p, and then independently fill any exposed
1737 * region under the curve with a round join. Sadly, that's
1738 * a) really hard to do, and b) makes certain pathological
1739 * filling cases MUCH slower due to the greater number of
1740 * "cross-segment" line segments this produces. Instead,
1741 * we just skip the line to the middle, and join across the
1742 * bottom instead. This is akin to what other graphics libs
1743 * do (such as fitz, libart, etc). It's not perfect but in
1744 * most cases it's close, and results in faster to fill
1745 * paths.
1746 */
1747 code = gx_path_add_line(ppath, nplp->o.p.x, nplp->o.p.y);
1748 if (code < 0)
1749 return code;
1750 }
1751 code = gx_path_add_line(ppath, nplp->o.ce.x, nplp->o.ce.y);
1752 }
1753 }
1754 if (code < 0)
1755 return code;
1756 if (npoints > 0) {
1757 code = add_points(ppath, points, npoints, false);
1758 if (code < 0)
1759 return code;
1760 }
1761 if (nrpoints > 0) {
1762 code = add_points(rpath, rpoints, nrpoints, false);
1763 if (code < 0)
1764 return code;
1765 }
1766 vd_closepath;
1767 if (ensure_closed)
1768 return gx_join_path_and_reverse(ppath, rpath);
1769 return 0;
1770 }
1771
1772 /* Add a CPSI-compatible segment to the path. This handles all the complex
1773 * cases.
1774 *
1775 * This method doesn't support start/end/dash caps, but it's only used from
1776 * postscript, so it doesn't need to.
1777 */
1778 static int
stroke_add_compat(gx_path * ppath,gx_path * rpath,bool ensure_closed,int first,pl_ptr plp,pl_ptr nplp,const gx_device_color * pdevc,gx_device * dev,const gs_imager_state * pis,const gx_stroke_params * params,const gs_fixed_rect * ignore_pbbox,int uniform,gs_line_join join,bool reflected,note_flags flags)1779 stroke_add_compat(gx_path * ppath, gx_path *rpath, bool ensure_closed,
1780 int first, pl_ptr plp, pl_ptr nplp,
1781 const gx_device_color * pdevc, gx_device * dev,
1782 const gs_imager_state * pis,
1783 const gx_stroke_params * params,
1784 const gs_fixed_rect * ignore_pbbox, int uniform,
1785 gs_line_join join, bool reflected, note_flags flags)
1786 {
1787 /* Actually it adds 2 contours : one for the segment itself,
1788 and another one for line join or for the ending cap.
1789 Note CPSI creates negative contours. */
1790 const gx_line_params *pgs_lp = gs_currentlineparams_inline(pis);
1791 gs_fixed_point points[5];
1792 int npoints;
1793 bool const moveto_first = true; /* Keeping this code closer to "stroke_add". */
1794 int code;
1795
1796 if (plp->thin) {
1797 /* We didn't set up the endpoint parameters before, */
1798 /* because the line was thin. Do it now. */
1799 set_thin_widths(plp);
1800 adjust_stroke(dev, plp, pis, true, first == 0 && nplp == 0, flags);
1801 compute_caps(plp);
1802 }
1803 /* The segment itself : */
1804 ASSIGN_POINT(&points[0], plp->o.ce);
1805 ASSIGN_POINT(&points[1], plp->e.co);
1806 ASSIGN_POINT(&points[2], plp->e.ce);
1807 ASSIGN_POINT(&points[3], plp->o.co);
1808 code = add_points(ppath, points, 4, moveto_first);
1809 if (code < 0)
1810 return code;
1811 code = gx_path_close_subpath(ppath);
1812 if (code < 0)
1813 return code;
1814 vd_closepath;
1815 npoints = 0;
1816 if (nplp == 0) {
1817 /* Add a final cap. */
1818 if (pgs_lp->start_cap == gs_cap_butt)
1819 return 0;
1820 if (pgs_lp->start_cap == gs_cap_round) {
1821 ASSIGN_POINT(&points[npoints], plp->e.co);
1822 vd_lineto(points[npoints].x, points[npoints].y);
1823 ++npoints;
1824 if ((code = add_points(ppath, points, npoints, moveto_first)) < 0)
1825 return code;
1826 return add_round_cap(ppath, &plp->e);
1827 }
1828 ASSIGN_POINT(&points[0], plp->e.ce);
1829 ++npoints;
1830 ASSIGN_POINT(&points[npoints], plp->e.co);
1831 ++npoints;
1832 code = cap_points(pgs_lp->start_cap, &plp->e, points + npoints);
1833 if (code < 0)
1834 return code;
1835 npoints += code;
1836 } else if (join == gs_join_round) {
1837 ASSIGN_POINT(&points[npoints], plp->e.co);
1838 vd_lineto(points[npoints].x, points[npoints].y);
1839 ++npoints;
1840 if ((code = add_points(ppath, points, npoints, moveto_first)) < 0)
1841 return code;
1842 return add_round_cap(ppath, &plp->e);
1843 } else if (nplp->thin) { /* no join */
1844 npoints = 0;
1845 } else { /* non-round join */
1846 bool ccw =
1847 (double)(plp->width.x) /* x1 */ * (nplp->width.y) /* y2 */ >
1848 (double)(nplp->width.x) /* x2 */ * (plp->width.y) /* y1 */;
1849
1850 if (ccw ^ reflected) {
1851 ASSIGN_POINT(&points[0], plp->e.co);
1852 vd_lineto(points[0].x, points[0].y);
1853 ++npoints;
1854 code = line_join_points(pgs_lp, plp, nplp, points + npoints,
1855 (uniform ? (gs_matrix *) 0 : &ctm_only(pis)),
1856 join, reflected);
1857 if (code < 0)
1858 return code;
1859 code--; /* Drop the last point of the non-compatible mode. */
1860 npoints += code;
1861 } else {
1862 code = line_join_points(pgs_lp, plp, nplp, points,
1863 (uniform ? (gs_matrix *) 0 : &ctm_only(pis)),
1864 join, reflected);
1865 if (code < 0)
1866 return code;
1867 ASSIGN_POINT(&points[0], plp->e.ce); /* Replace the starting point of the non-compatible mode. */
1868 npoints = code;
1869 }
1870 }
1871 code = add_points(ppath, points, npoints, moveto_first);
1872 if (code < 0)
1873 return code;
1874 code = gx_path_close_subpath(ppath);
1875 vd_closepath;
1876 return code;
1877 }
1878
1879 /* Add a CPSI-compatible segment to the path. This handles all the complex
1880 * cases.
1881 *
1882 * This method doesn't support start/end/dash caps, but it's only used from
1883 * postscript, so it doesn't need to.
1884 */
1885 static int
stroke_add_initial_cap_compat(gx_path * ppath,pl_ptr plp,bool adlust_longitude,const gx_device_color * pdevc,gx_device * dev,const gs_imager_state * pis)1886 stroke_add_initial_cap_compat(gx_path * ppath, pl_ptr plp, bool adlust_longitude,
1887 const gx_device_color * pdevc, gx_device * dev,
1888 const gs_imager_state * pis)
1889 {
1890 const gx_line_params *pgs_lp = gs_currentlineparams_inline(pis);
1891 gs_fixed_point points[4];
1892 int npoints = 0;
1893 int code;
1894
1895 if (pgs_lp->start_cap == gs_cap_butt)
1896 return 0;
1897 if (plp->thin) {
1898 /* We didn't set up the endpoint parameters before, */
1899 /* because the line was thin. Do it now. */
1900 set_thin_widths(plp);
1901 adjust_stroke(dev, plp, pis, true, adlust_longitude, 0);
1902 compute_caps(plp);
1903 }
1904 /* Create an initial cap if desired. */
1905 if (pgs_lp->start_cap == gs_cap_round) {
1906 vd_moveto(plp->o.co.x, plp->o.co.y);
1907 if ((code = gx_path_add_point(ppath, plp->o.co.x, plp->o.co.y)) < 0 ||
1908 (code = add_round_cap(ppath, &plp->o)) < 0
1909 )
1910 return code;
1911 return 0;
1912 } else {
1913 ASSIGN_POINT(&points[0], plp->o.co);
1914 ++npoints;
1915 if ((code = cap_points(pgs_lp->start_cap, &plp->o, points + npoints)) < 0)
1916 return npoints;
1917 npoints += code;
1918 ASSIGN_POINT(&points[npoints], plp->o.ce);
1919 ++npoints;
1920 code = add_points(ppath, points, npoints, true);
1921 if (code < 0)
1922 return code;
1923 return gx_path_close_subpath(ppath);
1924 }
1925 }
1926
1927 /* Add lines with a possible initial moveto. */
1928 static int
add_points(gx_path * ppath,const gs_fixed_point * points,int npoints,bool moveto_first)1929 add_points(gx_path * ppath, const gs_fixed_point * points, int npoints,
1930 bool moveto_first)
1931 {
1932 int code;
1933
1934 /* vd_setcolor(0); */
1935 vd_setlinewidth(0);
1936 if (moveto_first) {
1937 code = gx_path_add_point(ppath, points[0].x, points[0].y);
1938 vd_moveto(points[0].x, points[0].y);
1939 if (code < 0)
1940 return code;
1941 vd_lineto_multi(points + 1, npoints - 1);
1942 return gx_path_add_lines(ppath, points + 1, npoints - 1);
1943 } else {
1944 vd_lineto_multi(points, npoints);
1945 return gx_path_add_lines(ppath, points, npoints);
1946 }
1947 }
1948
1949 /* ---------------- Join computation ---------------- */
1950
1951 static int
check_miter(const gx_line_params * pgs_lp,pl_ptr plp,pl_ptr nplp,const gs_matrix * pmat,p_ptr outp,p_ptr np,p_ptr mpt,bool ccw0)1952 check_miter(const gx_line_params * pgs_lp, pl_ptr plp, pl_ptr nplp,
1953 const gs_matrix * pmat, p_ptr outp, p_ptr np, p_ptr mpt,
1954 bool ccw0)
1955 {
1956 /*
1957 * Check whether a miter join is appropriate.
1958 * Let a, b be the angles of the two lines.
1959 * We check tan(a-b) against the miter_check
1960 * by using the following formula:
1961 * If tan(a)=u1/v1 and tan(b)=u2/v2, then
1962 * tan(a-b) = (u1*v2 - u2*v1) / (u1*u2 + v1*v2).
1963 *
1964 * We can do all the computations unscaled,
1965 * because we're only concerned with ratios.
1966 * However, if we have a non-uniform coordinate
1967 * system (indicated by pmat != 0), we must do the
1968 * computations in user space.
1969 */
1970 float check = pgs_lp->miter_check;
1971 double u1 = plp->vector.y, v1 = plp->vector.x;
1972 double u2 = -nplp->vector.y, v2 = -nplp->vector.x;
1973 double num, denom;
1974 int code;
1975
1976 if (pmat) {
1977 gs_point pt;
1978
1979 code = gs_distance_transform_inverse(v1, u1, pmat, &pt);
1980 if (code < 0)
1981 return code;
1982 v1 = pt.x, u1 = pt.y;
1983 code = gs_distance_transform_inverse(v2, u2, pmat, &pt);
1984 if (code < 0)
1985 return code;
1986 v2 = pt.x, u2 = pt.y;
1987 /*
1988 * We need to recompute ccw according to the
1989 * relative positions of the lines in user space.
1990 * We repeat the computation described above,
1991 * using the cdelta values instead of the widths.
1992 * Because the definition of ccw above is inverted
1993 * from the intuitive one (for historical reasons),
1994 * we actually have to do the test backwards.
1995 */
1996 ccw0 = v1 * u2 < v2 * u1;
1997 #ifdef DEBUG
1998 {
1999 double a1 = atan2(u1, v1), a2 = atan2(u2, v2), dif = a1 - a2;
2000
2001 if (dif < 0)
2002 dif += 2 * M_PI;
2003 else if (dif >= 2 * M_PI)
2004 dif -= 2 * M_PI;
2005 if (dif != 0 && (dif < M_PI) != ccw0)
2006 lprintf8("ccw wrong: tan(a1=%g)=%g/%g, tan(a2=%g)=%g,%g, dif=%g, ccw0=%d\n",
2007 a1, u1, v1, a2, u2, v2, dif, ccw0);
2008 }
2009 #endif
2010 }
2011 num = u1 * v2 - u2 * v1;
2012 denom = u1 * u2 + v1 * v2;
2013 /*
2014 * We will want either tan(a-b) or tan(b-a)
2015 * depending on the orientations of the lines.
2016 * Fortunately we know the relative orientations already.
2017 */
2018 if (!ccw0) /* have plp - nplp, want vice versa */
2019 num = -num;
2020 #ifdef DEBUG
2021 if (gs_debug_c('O')) {
2022 dlprintf4("[o]Miter check: u1/v1=%f/%f, u2/v2=%f/%f,\n",
2023 u1, v1, u2, v2);
2024 dlprintf3(" num=%f, denom=%f, check=%f\n",
2025 num, denom, check);
2026 }
2027 #endif
2028 /*
2029 * If we define T = num / denom, then we want to use
2030 * a miter join iff arctan(T) >= arctan(check).
2031 * We know that both of these angles are in the 1st
2032 * or 2nd quadrant, and since arctan is monotonic
2033 * within each quadrant, we can do the comparisons
2034 * on T and check directly, taking signs into account
2035 * as follows:
2036 * sign(T) sign(check) atan(T) >= atan(check)
2037 * ------- ----------- ----------------------
2038 * + + T >= check
2039 * - + true
2040 * + - false
2041 * - - T >= check
2042 */
2043 if (num == 0 && denom == 0)
2044 return_error(gs_error_unregistered); /* Must not happen. */
2045 if (denom < 0)
2046 num = -num, denom = -denom;
2047 /* Now denom >= 0, so sign(num) = sign(T). */
2048 if (check > 0 ?
2049 (num < 0 || num >= denom * check) :
2050 (num < 0 && num >= denom * check)
2051 ) {
2052 /* OK to use a miter join. */
2053 gs_fixed_point dirn1, dirn2;
2054
2055 dirn1.x = plp->e.cdelta.x;
2056 dirn1.y = plp->e.cdelta.y;
2057 /* If this direction is small enough that we might have
2058 * underflowed and the vector record is suitable for us
2059 * to use to calculate a better one, then do so. */
2060 if ((abs(dirn1.x) + abs(dirn1.y) < 16) &&
2061 ((plp->vector.x != 0) || (plp->vector.y != 0)))
2062 {
2063 float scale = 65536.0;
2064 if (abs(plp->vector.x) > abs(plp->vector.y))
2065 scale /= abs(plp->vector.x);
2066 else
2067 scale /= abs(plp->vector.y);
2068 dirn1.x = (fixed)(plp->vector.x*scale);
2069 dirn1.y = (fixed)(plp->vector.y*scale);
2070 }
2071 dirn2.x = nplp->o.cdelta.x;
2072 dirn2.y = nplp->o.cdelta.y;
2073 /* If this direction is small enough that we might have
2074 * underflowed and the vector record is suitable for us
2075 * to use to calculate a better one, then do so. */
2076 if ((abs(dirn2.x) + abs(dirn2.y) < 16) &&
2077 ((nplp->vector.x != 0) || (nplp->vector.y != 0)))
2078 {
2079 float scale = 65536.0;
2080 if (abs(nplp->vector.x) > abs(nplp->vector.y))
2081 scale /= abs(nplp->vector.x);
2082 else
2083 scale /= abs(nplp->vector.y);
2084 dirn2.x = (fixed)(-nplp->vector.x*scale);
2085 dirn2.y = (fixed)(-nplp->vector.y*scale);
2086 }
2087 if_debug0('O', " ... passes.\n");
2088 /* Compute the intersection of the extended edge lines. */
2089 if (line_intersect(outp, &dirn1, np, &dirn2, mpt) == 0)
2090 return 0;
2091 }
2092 return 1;
2093 }
2094
2095 /* Compute the points for a bevel, miter, or triangle join. */
2096 /* Treat no join the same as a bevel join. */
2097 /* If pmat != 0, we must inverse-transform the distances for */
2098 /* the miter check. */
2099 static int
line_join_points(const gx_line_params * pgs_lp,pl_ptr plp,pl_ptr nplp,gs_fixed_point * join_points,const gs_matrix * pmat,gs_line_join join,bool reflected)2100 line_join_points(const gx_line_params * pgs_lp, pl_ptr plp, pl_ptr nplp,
2101 gs_fixed_point * join_points, const gs_matrix * pmat,
2102 gs_line_join join, bool reflected)
2103 {
2104 #define jp1 join_points[0]
2105 #define np1 join_points[1]
2106 #define np2 join_points[2]
2107 #define jp2 join_points[3]
2108 #define jpx join_points[4]
2109 /*
2110 * Set np to whichever of nplp->o.co or .ce is outside
2111 * the current line. We observe that the point (x2,y2)
2112 * is counter-clockwise from (x1,y1), relative to the origin,
2113 * iff
2114 * (arctan(y2/x2) - arctan(y1/x1)) mod 2*pi < pi,
2115 * taking the signs of xi and yi into account to determine
2116 * the quadrants of the results. It turns out that
2117 * even though arctan is monotonic only in the 4th/1st
2118 * quadrants and the 2nd/3rd quadrants, case analysis on
2119 * the signs of xi and yi demonstrates that this test
2120 * is equivalent to the much less expensive test
2121 * x1 * y2 > x2 * y1
2122 * in all cases.
2123 *
2124 * In the present instance, x1,y1 are plp->width,
2125 * x2,y2 are nplp->width, and the origin is
2126 * their common point (plp->e.p, nplp->o.p).
2127 * ccw will be true iff nplp.o.co (nplp.o.p + width) is
2128 * counter-clockwise from plp.e.ce (plp.e.p + width),
2129 * in which case we want tan(a-b) rather than tan(b-a).
2130 *
2131 * We make the test using double arithmetic only because
2132 * the !@#&^*% C language doesn't give us access to
2133 * the double-width-result multiplication operation
2134 * that almost all CPUs provide!
2135 */
2136 bool ccw =
2137 (double)(plp->width.x) /* x1 */ * (nplp->width.y) /* y2 */ >
2138 (double)(nplp->width.x) /* x2 */ * (plp->width.y) /* y1 */;
2139 bool ccw0 = ccw;
2140 p_ptr outp, np;
2141 int code;
2142
2143 ccw ^= reflected;
2144
2145 /* Initialize for a bevel join. */
2146 ASSIGN_POINT(&jp1, plp->e.co);
2147 ASSIGN_POINT(&jp2, plp->e.ce);
2148
2149 /*
2150 * Because of stroke adjustment, it is possible that
2151 * plp->e.p != nplp->o.p. For that reason, we must use
2152 * nplp->o.p as np1 or np2.
2153 */
2154 if (!ccw) {
2155 outp = &jp2;
2156 ASSIGN_POINT(&np2, nplp->o.co);
2157 ASSIGN_POINT(&np1, nplp->o.p);
2158 np = &np2;
2159 } else {
2160 outp = &jp1;
2161 ASSIGN_POINT(&np1, nplp->o.ce);
2162 ASSIGN_POINT(&np2, nplp->o.p);
2163 np = &np1;
2164 }
2165 if_debug1('O', "[O]use %s\n", (ccw ? "co (ccw)" : "ce (cw)"));
2166
2167 /* Handle triangular joins now. */
2168 if (join == gs_join_triangle) {
2169 fixed tpx = outp->x - nplp->o.p.x + np->x;
2170 fixed tpy = outp->y - nplp->o.p.y + np->y;
2171
2172 ASSIGN_POINT(&jpx, jp2);
2173 if (!ccw) {
2174 /* Insert tp between np2 and jp2. */
2175 jp2.x = tpx, jp2.y = tpy;
2176 } else {
2177 /* Insert tp between jp1 and np1. */
2178 ASSIGN_POINT(&jp2, np2);
2179 ASSIGN_POINT(&np2, np1);
2180 np1.x = tpx, np1.y = tpy;
2181 }
2182 return 5;
2183 }
2184 /*
2185 * Don't bother with the miter check if the two
2186 * points to be joined are very close together,
2187 * namely, in the same square half-pixel.
2188 */
2189 if (join == gs_join_miter &&
2190 !(fixed2long(outp->x << 1) == fixed2long(np->x << 1) &&
2191 fixed2long(outp->y << 1) == fixed2long(np->y << 1))
2192 ) {
2193 gs_fixed_point mpt;
2194 code = check_miter(pgs_lp, plp, nplp, pmat, outp, np, &mpt, ccw0);
2195 if (code < 0)
2196 return code;
2197 if (code == 0)
2198 ASSIGN_POINT(outp, mpt);
2199 }
2200 return 4;
2201 }
2202
2203 static int
line_join_points_fast_cw(const gx_line_params * pgs_lp,pl_ptr plp,pl_ptr nplp,gs_fixed_point * rjoin_points,const gs_matrix * pmat,gs_line_join join)2204 line_join_points_fast_cw(const gx_line_params * pgs_lp,
2205 pl_ptr plp, pl_ptr nplp,
2206 gs_fixed_point * rjoin_points,
2207 const gs_matrix * pmat,
2208 gs_line_join join)
2209 {
2210 /* rjoin_points will be added to a path that is currently at plp->e.ce.
2211 */
2212
2213 /* Join will be between plp->e.ce and nplp->o.co */
2214 if (join == gs_join_triangle)
2215 {
2216 gs_fixed_point tp;
2217
2218 tp.x = plp->e.ce.x - nplp->o.p.x + nplp->o.co.x;
2219 tp.y = plp->e.ce.y - nplp->o.p.y + nplp->o.co.y;
2220 ASSIGN_POINT(&rjoin_points[0], tp);
2221 ASSIGN_POINT(&rjoin_points[1], nplp->o.co);
2222 return 2;
2223 }
2224
2225 /* Set up for a Bevel join */
2226 ASSIGN_POINT(&rjoin_points[0], nplp->o.co);
2227
2228 /*
2229 * Don't bother with the miter check if the two
2230 * points to be joined are very close together,
2231 * namely, in the same square half-pixel.
2232 */
2233 if (join == gs_join_miter &&
2234 !(fixed2long(plp->e.ce.x << 1) == fixed2long(nplp->o.co.x << 1) &&
2235 fixed2long(plp->e.ce.y << 1) == fixed2long(nplp->o.co.y << 1))
2236 ) {
2237 gs_fixed_point mpt;
2238 int code = check_miter(pgs_lp, plp, nplp, pmat, &plp->e.ce,
2239 &nplp->o.co, &mpt, false);
2240 if (code < 0)
2241 return code;
2242 if (code == 0) {
2243 ASSIGN_POINT(&rjoin_points[0], mpt);
2244 ASSIGN_POINT(&rjoin_points[1], nplp->o.co);
2245 return 2;
2246 }
2247 }
2248 return 1;
2249 }
2250
2251 static int
line_join_points_fast_ccw(const gx_line_params * pgs_lp,pl_ptr plp,pl_ptr nplp,gs_fixed_point * join_points,const gs_matrix * pmat,gs_line_join join)2252 line_join_points_fast_ccw(const gx_line_params * pgs_lp,
2253 pl_ptr plp, pl_ptr nplp,
2254 gs_fixed_point * join_points,
2255 const gs_matrix * pmat,
2256 gs_line_join join)
2257 {
2258 /* join_points will be added to a path that is currently at plp->e.co.
2259 */
2260 /* Join will be between plp->e.co and nplp->o.ce */
2261 if (join == gs_join_triangle)
2262 {
2263 gs_fixed_point tp;
2264
2265 tp.x = plp->e.co.x - nplp->o.p.x + nplp->o.ce.x;
2266 tp.y = plp->e.co.y - nplp->o.p.y + nplp->o.ce.y;
2267 ASSIGN_POINT(&join_points[0], tp);
2268 ASSIGN_POINT(&join_points[1], nplp->o.ce);
2269 return 2;
2270 }
2271
2272 /* Set up for a Bevel join */
2273 ASSIGN_POINT(&join_points[0], nplp->o.ce);
2274
2275 /*
2276 * Don't bother with the miter check if the two
2277 * points to be joined are very close together,
2278 * namely, in the same square half-pixel.
2279 */
2280 if (join == gs_join_miter &&
2281 !(fixed2long(plp->e.co.x << 1) == fixed2long(nplp->o.ce.x << 1) &&
2282 fixed2long(plp->e.co.y << 1) == fixed2long(nplp->o.ce.y << 1))
2283 ) {
2284 gs_fixed_point mpt;
2285 int code = check_miter(pgs_lp, plp, nplp, pmat, &plp->e.co,
2286 &nplp->o.ce, &mpt, true);
2287 if (code < 0)
2288 return code;
2289 if (code == 0) {
2290 ASSIGN_POINT(&join_points[0], mpt);
2291 ASSIGN_POINT(&join_points[1], nplp->o.ce);
2292 return 2;
2293 }
2294 }
2295 return 1;
2296 }
2297 /* ---------------- Cap computations ---------------- */
2298
2299 /* Compute the endpoints of the two caps of a segment. */
2300 /* Only o.p, e.p, width, and cdelta have been set. */
2301 static void
compute_caps(pl_ptr plp)2302 compute_caps(pl_ptr plp)
2303 {
2304 fixed wx2 = plp->width.x;
2305 fixed wy2 = plp->width.y;
2306
2307 plp->o.co.x = plp->o.p.x + wx2, plp->o.co.y = plp->o.p.y + wy2;
2308 plp->o.cdelta.x = -plp->e.cdelta.x,
2309 plp->o.cdelta.y = -plp->e.cdelta.y;
2310 plp->o.ce.x = plp->o.p.x - wx2, plp->o.ce.y = plp->o.p.y - wy2;
2311 plp->e.co.x = plp->e.p.x - wx2, plp->e.co.y = plp->e.p.y - wy2;
2312 plp->e.ce.x = plp->e.p.x + wx2, plp->e.ce.y = plp->e.p.y + wy2;
2313 #ifdef DEBUG
2314 if (gs_debug_c('O')) {
2315 dlprintf4("[o]Stroke o=(%f,%f) e=(%f,%f)\n",
2316 fixed2float(plp->o.p.x), fixed2float(plp->o.p.y),
2317 fixed2float(plp->e.p.x), fixed2float(plp->e.p.y));
2318 dlprintf4("\twxy=(%f,%f) lxy=(%f,%f)\n",
2319 fixed2float(wx2), fixed2float(wy2),
2320 fixed2float(plp->e.cdelta.x),
2321 fixed2float(plp->e.cdelta.y));
2322 }
2323 #endif
2324 }
2325
2326 #define px endp->p.x
2327 #define py endp->p.y
2328 #define xo endp->co.x
2329 #define yo endp->co.y
2330 #define xe endp->ce.x
2331 #define ye endp->ce.y
2332 #define cdx endp->cdelta.x
2333 #define cdy endp->cdelta.y
2334
2335 /* Add a round cap to a path. */
2336 /* Assume the current point is the cap origin (endp->co). */
2337 static int
add_round_cap(gx_path * ppath,const_ep_ptr endp)2338 add_round_cap(gx_path * ppath, const_ep_ptr endp)
2339 {
2340 int code;
2341
2342 /*
2343 * Per the Red Book, we draw a full circle, even though a semicircle
2344 * is sufficient for the join.
2345 */
2346 if ((code = gx_path_add_partial_arc(ppath, px + cdx, py + cdy,
2347 xo + cdx, yo + cdy,
2348 quarter_arc_fraction)) < 0 ||
2349 (code = gx_path_add_partial_arc(ppath, xe, ye, xe + cdx, ye + cdy,
2350 quarter_arc_fraction)) < 0 ||
2351 (code = gx_path_add_partial_arc(ppath, px - cdx, py - cdy,
2352 xe - cdx, ye - cdy,
2353 quarter_arc_fraction)) < 0 ||
2354 (code = gx_path_add_partial_arc(ppath, xo, yo, xo - cdx, yo - cdy,
2355 quarter_arc_fraction)) < 0 ||
2356 /* The final point must be (xe,ye). */
2357 (code = gx_path_add_line(ppath, xe, ye)) < 0
2358 )
2359 return code;
2360 vd_lineto(xe, ye);
2361 return 0;
2362 }
2363
2364 /* Add a semicircular cap to a path. */
2365 /* Assume the current point is the cap origin (endp->co). */
2366 static int
add_pie_cap(gx_path * ppath,const_ep_ptr endp)2367 add_pie_cap(gx_path * ppath, const_ep_ptr endp)
2368 {
2369 int code;
2370
2371 if ((code = gx_path_add_partial_arc(ppath, px + cdx, py + cdy,
2372 xo + cdx, yo + cdy,
2373 quarter_arc_fraction)) < 0 ||
2374 (code = gx_path_add_partial_arc(ppath, xe, ye, xe + cdx, ye + cdy,
2375 quarter_arc_fraction)) < 0 ||
2376 (code = gx_path_add_line(ppath, xe, ye)) < 0)
2377 return code;
2378 vd_lineto(xe, ye);
2379 return 0;
2380 }
2381
2382 static int
do_pie_join(gx_path * ppath,gs_fixed_point * centre,gs_fixed_point * current_orig,gs_fixed_point * current_tangent,gs_fixed_point * final,gs_fixed_point * final_tangent,bool ccw,gs_fixed_point * width)2383 do_pie_join(gx_path * ppath, gs_fixed_point *centre,
2384 gs_fixed_point *current_orig, gs_fixed_point *current_tangent,
2385 gs_fixed_point *final, gs_fixed_point *final_tangent, bool ccw,
2386 gs_fixed_point *width)
2387 {
2388 int code;
2389 double rad_squared, dist_squared, F;
2390 gs_fixed_point current, tangent, tangmeet;
2391
2392 tangent.x = current_tangent->x;
2393 tangent.y = current_tangent->y;
2394 current.x = current_orig->x;
2395 current.y = current_orig->y;
2396
2397 /* Is the join more than 90 degrees? */
2398 if ((double)tangent.x * (double)final_tangent->x +
2399 (double)tangent.y * (double)final_tangent->y > 0) {
2400 /* Yes, so do a quarter turn. */
2401 code = gx_path_add_partial_arc(ppath,
2402 centre->x + tangent.x,
2403 centre->y + tangent.y,
2404 /* Point where tangents meet */
2405 current.x + tangent.x,
2406 current.y + tangent.y,
2407 quarter_arc_fraction);
2408 if (code < 0)
2409 return code;
2410 current.x = centre->x + tangent.x;
2411 current.y = centre->y + tangent.y;
2412 if (ccw) {
2413 int tmp = tangent.x;
2414 tangent.x = -tangent.y;
2415 tangent.y = tmp;
2416 } else {
2417 int tmp = tangent.x;
2418 tangent.x = tangent.y;
2419 tangent.y = -tmp;
2420 }
2421 }
2422
2423 /* Now we are guaranteed that the remaining arc is 90 degrees or
2424 * less. Find where the tangents meet for this final section. */
2425 if (line_intersect(¤t, &tangent,
2426 final, final_tangent, &tangmeet) != 0) {
2427 return gx_path_add_line(ppath, final->x, final->y);
2428 }
2429 current.x -= tangmeet.x;
2430 current.y -= tangmeet.y;
2431 dist_squared = ((double)current.x) * current.x +
2432 ((double)current.y) * current.y;
2433 rad_squared = ((double)width->x) * width->x +
2434 ((double)width->y) * width->y;
2435 dist_squared /= rad_squared;
2436 F = (4.0/3.0)*(1/(1+sqrt(1+dist_squared)));
2437 return gx_path_add_partial_arc(ppath, final->x, final->y,
2438 tangmeet.x, tangmeet.y, F);
2439 }
2440
2441 /* Add a pie shaped join to a path. */
2442 /* Assume the current point is the cap origin (endp->co). */
2443 static int
add_pie_join(gx_path * ppath,pl_ptr plp,pl_ptr nplp,bool reflected,bool cap)2444 add_pie_join(gx_path * ppath, pl_ptr plp, pl_ptr nplp, bool reflected,
2445 bool cap)
2446 {
2447 int code;
2448 gs_fixed_point *current, *final, *tangent, *final_tangent;
2449 double l, r;
2450 bool ccw;
2451
2452 l = (double)(plp->width.x) /* x1 */ * (nplp->width.y) /* y2 */;
2453 r = (double)(nplp->width.x) /* x2 */ * (plp->width.y) /* y1 */;
2454
2455 if (l == r) {
2456 if (cap)
2457 return add_pie_cap(ppath, &plp->e);
2458 else
2459 return gx_path_add_line(ppath, plp->e.ce.x, plp->e.ce.y);
2460 }
2461
2462 ccw = (l > r);
2463
2464 ccw ^= reflected;
2465
2466 /* At this point, the current point is plp->e.co */
2467 if (ccw) {
2468 current = & plp->e.co;
2469 final = &nplp->o.ce;
2470 tangent = & plp->e.cdelta;
2471 final_tangent = &nplp->o.cdelta;
2472 /* Check for no join required */
2473 if (current->x == final->x && current->y == final->y) {
2474 return gx_path_add_line(ppath, plp->e.ce.x, plp->e.ce.y);
2475 }
2476 } else {
2477 current = &nplp->o.co;
2478 final = & plp->e.ce;
2479 tangent = &nplp->o.cdelta;
2480 final_tangent = & plp->e.cdelta;
2481 code = gx_path_add_line(ppath, plp->e.p.x, plp->e.p.y);
2482 if (code < 0)
2483 return code;
2484 code = gx_path_add_line(ppath, current->x, current->y);
2485 if (code < 0)
2486 return code;
2487 if (current->x == final->x && current->y == final->y)
2488 return 0;
2489 }
2490
2491 if ((code = do_pie_join(ppath, &plp->e.p, current, tangent,
2492 final, final_tangent, !reflected, &plp->width)) < 0)
2493 return code;
2494 if (ccw &&
2495 ((code = gx_path_add_line(ppath, plp->e.p.x, plp->e.p.y)) < 0 ||
2496 (code = gx_path_add_line(ppath, plp->e.ce.x, plp->e.ce.y)) < 0))
2497 return code;
2498
2499 vd_lineto(plp->e.ce.x, plp->e.ce.y);
2500 return 0;
2501 }
2502
2503 /* Add a pie shaped join to a path. */
2504 static int
add_pie_join_fast_cw(gx_path * rpath,pl_ptr plp,pl_ptr nplp,bool reflected)2505 add_pie_join_fast_cw(gx_path * rpath, pl_ptr plp, pl_ptr nplp, bool reflected)
2506 {
2507 /* At this point, the current point is plp->e.ce */
2508 if (plp->e.ce.x == nplp->o.co.x && plp->e.ce.y == nplp->o.co.y)
2509 return 0;
2510
2511 return do_pie_join(rpath, &plp->e.p, &plp->e.ce, &plp->e.cdelta,
2512 &nplp->o.co, &nplp->o.cdelta, reflected, &plp->width);
2513 }
2514
2515 static int
add_pie_join_fast_ccw(gx_path * ppath,pl_ptr plp,pl_ptr nplp,bool reflected)2516 add_pie_join_fast_ccw(gx_path * ppath, pl_ptr plp, pl_ptr nplp, bool reflected)
2517 {
2518 /* At this point, the current point is plp->e.co */
2519 /* Check for no join required */
2520 if (plp->e.co.x == nplp->o.ce.x && plp->e.co.y == nplp->o.ce.y)
2521 return 0;
2522
2523 return do_pie_join(ppath, &plp->e.p, &plp->e.co, &plp->e.cdelta,
2524 &nplp->o.ce, &nplp->o.cdelta, !reflected, &plp->width);
2525 }
2526
2527 static int
join_under_pie(gx_path * ppath,pl_ptr plp,pl_ptr nplp,bool reflected)2528 join_under_pie(gx_path * ppath, pl_ptr plp, pl_ptr nplp, bool reflected)
2529 {
2530 int code;
2531 gs_fixed_point dirn1, dirn2, tangmeet;
2532 double l, r;
2533 bool ccw;
2534
2535 l = (double)(plp->width.x) /* x1 */ * (nplp->width.y) /* y2 */;
2536 r = (double)(nplp->width.x) /* x2 */ * (plp->width.y) /* y1 */;
2537
2538 if (l == r)
2539 return 0;
2540
2541 ccw = (l > r);
2542
2543 ccw ^= reflected;
2544
2545 if (ccw) {
2546 dirn1.x = - plp->width.x;
2547 dirn1.y = - plp->width.y;
2548 dirn2.x = -nplp->width.x;
2549 dirn2.y = -nplp->width.y;
2550 if (line_intersect(& plp->o.co, &dirn1,
2551 &nplp->e.ce, &dirn2, &tangmeet) != 0)
2552 return 0;
2553 if ((code = gx_path_close_subpath(ppath)) < 0 ||
2554 (code = gx_path_add_point(ppath, tangmeet.x, tangmeet.y)) < 0 ||
2555 (code = gx_path_add_line(ppath,plp->o.co.x,plp->o.co.y)) < 0 ||
2556 (code = do_pie_join(ppath, &plp->e.p, &plp->o.co, &plp->o.cdelta,
2557 &nplp->e.ce, &nplp->e.cdelta, !reflected,
2558 &plp->width)))
2559 return code;
2560 } else {
2561 if (line_intersect(& plp->o.ce, & plp->width,
2562 &nplp->e.co, &nplp->width, &tangmeet) != 0)
2563 return 0;
2564 if ((code = gx_path_close_subpath(ppath)) < 0 ||
2565 (code = gx_path_add_point(ppath, tangmeet.x, tangmeet.y)) < 0 ||
2566 (code = gx_path_add_line(ppath,nplp->e.co.x,nplp->e.co.y)) < 0 ||
2567 (code = do_pie_join(ppath, &plp->e.p,&nplp->e.co,&nplp->e.cdelta,
2568 &plp->o.ce, &plp->o.cdelta, !reflected,
2569 &plp->width)))
2570 return code;
2571 }
2572 return 0;
2573 }
2574
2575 /* Compute the points for a non-round cap. */
2576 /* Return the number of points. */
2577 static int
cap_points(gs_line_cap type,const_ep_ptr endp,gs_fixed_point * pts)2578 cap_points(gs_line_cap type, const_ep_ptr endp, gs_fixed_point *pts /*[3]*/)
2579 {
2580 #define PUT_POINT(i, px, py)\
2581 pts[i].x = (px), pts[i].y = (py)
2582 switch (type) {
2583 case gs_cap_butt:
2584 PUT_POINT(0, xo, yo);
2585 PUT_POINT(1, xe, ye);
2586 return 2;
2587 case gs_cap_square:
2588 PUT_POINT(0, xo + cdx, yo + cdy);
2589 PUT_POINT(1, xe + cdx, ye + cdy);
2590 return 2;
2591 case gs_cap_triangle: /* (not supported by PostScript) */
2592 PUT_POINT(0, xo, yo);
2593 PUT_POINT(1, px + cdx, py + cdy);
2594 PUT_POINT(2, xe, ye);
2595 return 3;
2596 default: /* can't happen */
2597 return_error(gs_error_unregistered);
2598 }
2599 #undef PUT_POINT
2600 }
2601