Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/source/fitz/draw-path.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 // Copyright (C) 2004-2025 Artifex Software, Inc.
2 //
3 // This file is part of MuPDF.
4 //
5 // MuPDF is free software: you can redistribute it and/or modify it under the
6 // terms of the GNU Affero General Public License as published by the Free
7 // Software Foundation, either version 3 of the License, or (at your option)
8 // any later version.
9 //
10 // MuPDF is distributed in the hope that it will be useful, but WITHOUT ANY
11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 // FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
13 // details.
14 //
15 // You should have received a copy of the GNU Affero General Public License
16 // along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>
17 //
18 // Alternative licensing terms are available from the licensor.
19 // For commercial licensing, see <https://www.artifex.com/> or contact
20 // Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
21 // CA 94129, USA, for further information.
22
23 #include "mupdf/fitz.h"
24 #include "draw-imp.h"
25
26 #include <math.h>
27 #include <float.h>
28 #include <assert.h>
29
30 #define MAX_DEPTH 8
31
32 /*
33 When stroking/filling, we now label the edges as we emit them.
34
35 For filling, we walk the outline of the shape in order, so everything
36 is labelled as '0'.
37
38 For stroking, we walk up both sides of the stroke at once; the forward
39 side (0), and the reverse side (1). When we get to the top, either
40 both sides join back to where they started, or we cap them.
41
42 The start cap is labelled 2, the end cap is labelled 0.
43
44 These labels are ignored for edge based rasterization, but are required
45 for edgebuffer based rasterization.
46
47 Consider the following simplified ascii art diagram of a stroke from
48 left to right with 3 sections.
49
50 | 0 0 0
51 | +----->-----+----->-----+----->-----+
52 | | |
53 | ^ 2 A B C v 0
54 | | |
55 | +-----<-----+-----<-----+-----<-----+
56 | 1 1 1
57
58 Edge 0 is sent in order (the top edge of A then B then C, left to right
59 in the above diagram). Edge 1 is sent in reverse order (the bottom edge
60 of A then B then C, still left to right in the above diagram, even though
61 the sense of the line is right to left).
62
63 Finally any caps required are sent, 0 and 2.
64
65 It would be nicer if we could roll edge 2 into edge 1, but to do that
66 we'd need to know in advance if a stroke was closed or not, so we have
67 special case code in the edgebuffer based rasterizer to cope with this.
68 */
69
70 static void
71 line(fz_context *ctx, fz_rasterizer *rast, fz_matrix ctm, float x0, float y0, float x1, float y1)
72 {
73 float tx0 = ctm.a * x0 + ctm.c * y0 + ctm.e;
74 float ty0 = ctm.b * x0 + ctm.d * y0 + ctm.f;
75 float tx1 = ctm.a * x1 + ctm.c * y1 + ctm.e;
76 float ty1 = ctm.b * x1 + ctm.d * y1 + ctm.f;
77 fz_insert_rasterizer(ctx, rast, tx0, ty0, tx1, ty1, 0);
78 }
79
80 static void
81 bezier(fz_context *ctx, fz_rasterizer *rast, fz_matrix ctm, float flatness,
82 float xa, float ya,
83 float xb, float yb,
84 float xc, float yc,
85 float xd, float yd, int depth)
86 {
87 float dmax;
88 float xab, yab;
89 float xbc, ybc;
90 float xcd, ycd;
91 float xabc, yabc;
92 float xbcd, ybcd;
93 float xabcd, yabcd;
94
95 /* termination check */
96 dmax = fz_abs(xa - xb);
97 dmax = fz_max(dmax, fz_abs(ya - yb));
98 dmax = fz_max(dmax, fz_abs(xd - xc));
99 dmax = fz_max(dmax, fz_abs(yd - yc));
100 if (dmax < flatness || depth >= MAX_DEPTH)
101 {
102 line(ctx, rast, ctm, xa, ya, xd, yd);
103 return;
104 }
105
106 xab = xa + xb;
107 yab = ya + yb;
108 xbc = xb + xc;
109 ybc = yb + yc;
110 xcd = xc + xd;
111 ycd = yc + yd;
112
113 xabc = xab + xbc;
114 yabc = yab + ybc;
115 xbcd = xbc + xcd;
116 ybcd = ybc + ycd;
117
118 xabcd = xabc + xbcd;
119 yabcd = yabc + ybcd;
120
121 xab *= 0.5f; yab *= 0.5f;
122 /* xbc *= 0.5f; ybc *= 0.5f; */
123 xcd *= 0.5f; ycd *= 0.5f;
124
125 xabc *= 0.25f; yabc *= 0.25f;
126 xbcd *= 0.25f; ybcd *= 0.25f;
127
128 xabcd *= 0.125f; yabcd *= 0.125f;
129
130 bezier(ctx, rast, ctm, flatness, xa, ya, xab, yab, xabc, yabc, xabcd, yabcd, depth + 1);
131 bezier(ctx, rast, ctm, flatness, xabcd, yabcd, xbcd, ybcd, xcd, ycd, xd, yd, depth + 1);
132 }
133
134 static void
135 quad(fz_context *ctx, fz_rasterizer *rast, fz_matrix ctm, float flatness,
136 float xa, float ya,
137 float xb, float yb,
138 float xc, float yc, int depth)
139 {
140 float dmax;
141 float xab, yab;
142 float xbc, ybc;
143 float xabc, yabc;
144
145 /* termination check */
146 dmax = fz_abs(xa - xb);
147 dmax = fz_max(dmax, fz_abs(ya - yb));
148 dmax = fz_max(dmax, fz_abs(xc - xb));
149 dmax = fz_max(dmax, fz_abs(yc - yb));
150 if (dmax < flatness || depth >= MAX_DEPTH)
151 {
152 line(ctx, rast, ctm, xa, ya, xc, yc);
153 return;
154 }
155
156 xab = xa + xb;
157 yab = ya + yb;
158 xbc = xb + xc;
159 ybc = yb + yc;
160
161 xabc = xab + xbc;
162 yabc = yab + ybc;
163
164 xab *= 0.5f; yab *= 0.5f;
165 xbc *= 0.5f; ybc *= 0.5f;
166
167 xabc *= 0.25f; yabc *= 0.25f;
168
169 quad(ctx, rast, ctm, flatness, xa, ya, xab, yab, xabc, yabc, depth + 1);
170 quad(ctx, rast, ctm, flatness, xabc, yabc, xbc, ybc, xc, yc, depth + 1);
171 }
172
173 typedef struct
174 {
175 fz_rasterizer *rast;
176 fz_matrix ctm;
177 float flatness;
178 fz_point b;
179 fz_point c;
180 }
181 flatten_arg;
182
183 static void
184 flatten_moveto(fz_context *ctx, void *arg_, float x, float y)
185 {
186 flatten_arg *arg = (flatten_arg *)arg_;
187
188 /* implicit closepath before moveto */
189 if (arg->c.x != arg->b.x || arg->c.y != arg->b.y)
190 line(ctx, arg->rast, arg->ctm, arg->c.x, arg->c.y, arg->b.x, arg->b.y);
191 arg->c.x = arg->b.x = x;
192 arg->c.y = arg->b.y = y;
193
194 fz_gap_rasterizer(ctx, arg->rast);
195 }
196
197 static void
198 flatten_lineto(fz_context *ctx, void *arg_, float x, float y)
199 {
200 flatten_arg *arg = (flatten_arg *)arg_;
201
202 line(ctx, arg->rast, arg->ctm, arg->c.x, arg->c.y, x, y);
203 arg->c.x = x;
204 arg->c.y = y;
205 }
206
207 static void
208 flatten_curveto(fz_context *ctx, void *arg_, float x1, float y1, float x2, float y2, float x3, float y3)
209 {
210 flatten_arg *arg = (flatten_arg *)arg_;
211
212 bezier(ctx, arg->rast, arg->ctm, arg->flatness, arg->c.x, arg->c.y, x1, y1, x2, y2, x3, y3, 0);
213 arg->c.x = x3;
214 arg->c.y = y3;
215 }
216
217 static void
218 flatten_quadto(fz_context *ctx, void *arg_, float x1, float y1, float x2, float y2)
219 {
220 flatten_arg *arg = (flatten_arg *)arg_;
221
222 quad(ctx, arg->rast, arg->ctm, arg->flatness, arg->c.x, arg->c.y, x1, y1, x2, y2, 0);
223 arg->c.x = x2;
224 arg->c.y = y2;
225 }
226
227 static void
228 flatten_close(fz_context *ctx, void *arg_)
229 {
230 flatten_arg *arg = (flatten_arg *)arg_;
231
232 line(ctx, arg->rast, arg->ctm, arg->c.x, arg->c.y, arg->b.x, arg->b.y);
233 arg->c.x = arg->b.x;
234 arg->c.y = arg->b.y;
235 }
236
237 static void
238 flatten_rectto(fz_context *ctx, void *arg_, float x0, float y0, float x1, float y1)
239 {
240 flatten_arg *arg = (flatten_arg *)arg_;
241 fz_matrix ctm = arg->ctm;
242
243 flatten_moveto(ctx, arg_, x0, y0);
244
245 if (fz_antidropout_rasterizer(ctx, arg->rast))
246 {
247 /* In the case where we have an axis aligned rectangle, do some
248 * horrid antidropout stuff. */
249 if (ctm.b == 0 && ctm.c == 0)
250 {
251 float tx0 = ctm.a * x0 + ctm.e;
252 float ty0 = ctm.d * y0 + ctm.f;
253 float tx1 = ctm.a * x1 + ctm.e;
254 float ty1 = ctm.d * y1 + ctm.f;
255 fz_insert_rasterizer_rect(ctx, arg->rast, tx0, ty0, tx1, ty1);
256 return;
257 }
258 else if (ctm.a == 0 && ctm.d == 0)
259 {
260 float tx0 = ctm.c * y0 + ctm.e;
261 float ty0 = ctm.b * x0 + ctm.f;
262 float tx1 = ctm.c * y1 + ctm.e;
263 float ty1 = ctm.b * x1 + ctm.f;
264 fz_insert_rasterizer_rect(ctx, arg->rast, tx0, ty1, tx1, ty0);
265 return;
266 }
267 }
268
269 flatten_lineto(ctx, arg_, x1, y0);
270 flatten_lineto(ctx, arg_, x1, y1);
271 flatten_lineto(ctx, arg_, x0, y1);
272 flatten_close(ctx, arg_);
273 }
274
275 static const fz_path_walker flatten_proc =
276 {
277 flatten_moveto,
278 flatten_lineto,
279 flatten_curveto,
280 flatten_close,
281 flatten_quadto,
282 NULL,
283 NULL,
284 flatten_rectto
285 };
286
287 static int
288 do_flatten_fill(fz_context *ctx, fz_rasterizer *rast, const fz_path *path, fz_matrix ctm, float flatness)
289 {
290 flatten_arg arg;
291
292 arg.rast = rast;
293 arg.ctm = ctm;
294 arg.flatness = flatness;
295 arg.b.x = arg.b.y = arg.c.x = arg.c.y = 0;
296
297 fz_walk_path(ctx, path, &flatten_proc, &arg);
298 if (arg.c.x != arg.b.x || arg.c.y != arg.b.y)
299 line(ctx, rast, ctm, arg.c.x, arg.c.y, arg.b.x, arg.b.y);
300
301 fz_gap_rasterizer(ctx, rast);
302
303 return fz_is_empty_irect(fz_bound_rasterizer(ctx, rast));
304 }
305
306 int
307 fz_flatten_fill_path(fz_context *ctx, fz_rasterizer *rast, const fz_path *path, fz_matrix ctm, float flatness, fz_irect scissor, fz_irect *bbox)
308 {
309 int empty;
310 fz_irect local_bbox;
311 if (!bbox)
312 bbox = &local_bbox;
313
314 /* If we're given an empty scissor, sanitize it. This makes life easier
315 * down the line. */
316 if (fz_is_empty_irect(scissor))
317 scissor.x1 = scissor.x0, scissor.y1 = scissor.y0;
318
319 if (fz_reset_rasterizer(ctx, rast, scissor))
320 {
321 empty = do_flatten_fill(ctx, rast, path, ctm, flatness);
322 if (empty)
323 return *bbox = fz_empty_irect, 1;
324 fz_postindex_rasterizer(ctx, rast);
325 }
326
327 empty = do_flatten_fill(ctx, rast, path, ctm, flatness);
328 if (empty)
329 return *bbox = fz_empty_irect, 1;
330
331 *bbox = fz_intersect_irect(scissor, fz_bound_rasterizer(ctx, rast));
332 return fz_is_empty_irect(*bbox);
333 }
334
335 typedef struct sctx
336 {
337 fz_rasterizer *rast;
338 fz_matrix ctm;
339 float flatness;
340 const fz_stroke_state *stroke;
341
342 int linejoin;
343 float linewidth;
344 float miterlimit;
345 fz_point beg[2];
346 fz_point seg[2];
347 int sn;
348 int not_just_moves;
349 int from_bezier;
350 fz_point cur;
351
352 fz_rect rect;
353 const float *dash_list;
354 float dash_phase;
355 int dash_len;
356 float dash_total;
357 int toggle, cap;
358 int offset;
359 float phase;
360 fz_point dash_cur;
361 fz_point dash_beg;
362
363 float dirn_x;
364 float dirn_y;
365 } sctx;
366
367 static void
368 fz_add_line(fz_context *ctx, sctx *s, float x0, float y0, float x1, float y1, int rev)
369 {
370 float tx0 = s->ctm.a * x0 + s->ctm.c * y0 + s->ctm.e;
371 float ty0 = s->ctm.b * x0 + s->ctm.d * y0 + s->ctm.f;
372 float tx1 = s->ctm.a * x1 + s->ctm.c * y1 + s->ctm.e;
373 float ty1 = s->ctm.b * x1 + s->ctm.d * y1 + s->ctm.f;
374
375 fz_insert_rasterizer(ctx, s->rast, tx0, ty0, tx1, ty1, rev);
376 }
377
378 static void
379 fz_add_horiz_rect(fz_context *ctx, sctx *s, float x0, float y0, float x1, float y1)
380 {
381 if (fz_antidropout_rasterizer(ctx, s->rast)) {
382 if (s->ctm.b == 0 && s->ctm.c == 0)
383 {
384 float tx0 = s->ctm.a * x0 + s->ctm.e;
385 float ty0 = s->ctm.d * y0 + s->ctm.f;
386 float tx1 = s->ctm.a * x1 + s->ctm.e;
387 float ty1 = s->ctm.d * y1 + s->ctm.f;
388 fz_insert_rasterizer_rect(ctx, s->rast, tx1, ty1, tx0, ty0);
389 return;
390 }
391 else if (s->ctm.a == 0 && s->ctm.d == 0)
392 {
393 float tx0 = s->ctm.c * y0 + s->ctm.e;
394 float ty0 = s->ctm.b * x0 + s->ctm.f;
395 float tx1 = s->ctm.c * y1 + s->ctm.e;
396 float ty1 = s->ctm.b * x1 + s->ctm.f;
397 fz_insert_rasterizer_rect(ctx, s->rast, tx1, ty0, tx0, ty1);
398 return;
399 }
400 }
401
402 fz_add_line(ctx, s, x0, y0, x1, y0, 0);
403 fz_add_line(ctx, s, x1, y1, x0, y1, 1);
404 }
405
406 static void
407 fz_add_vert_rect(fz_context *ctx, sctx *s, float x0, float y0, float x1, float y1)
408 {
409 if (fz_antidropout_rasterizer(ctx, s->rast))
410 {
411 if (s->ctm.b == 0 && s->ctm.c == 0)
412 {
413 float tx0 = s->ctm.a * x0 + s->ctm.e;
414 float ty0 = s->ctm.d * y0 + s->ctm.f;
415 float tx1 = s->ctm.a * x1 + s->ctm.e;
416 float ty1 = s->ctm.d * y1 + s->ctm.f;
417 fz_insert_rasterizer_rect(ctx, s->rast, tx0, ty1, tx1, ty0);
418 return;
419 }
420 else if (s->ctm.a == 0 && s->ctm.d == 0)
421 {
422 float tx0 = s->ctm.c * y0 + s->ctm.e;
423 float ty0 = s->ctm.b * x0 + s->ctm.f;
424 float tx1 = s->ctm.c * y1 + s->ctm.e;
425 float ty1 = s->ctm.b * x1 + s->ctm.f;
426 fz_insert_rasterizer_rect(ctx, s->rast, tx0, ty0, tx1, ty1);
427 return;
428 }
429 }
430
431 fz_add_line(ctx, s, x1, y0, x0, y0, 0);
432 fz_add_line(ctx, s, x0, y1, x1, y1, 1);
433 }
434
435 static void
436 fz_add_arc(fz_context *ctx, sctx *s,
437 float xc, float yc,
438 float x0, float y0,
439 float x1, float y1,
440 int rev)
441 {
442 float th0, th1, r;
443 float theta;
444 float ox, oy, nx, ny;
445 int n, i;
446
447 r = fabsf(s->linewidth);
448 theta = 2 * FZ_SQRT2 * sqrtf(s->flatness / r);
449 th0 = atan2f(y0, x0);
450 th1 = atan2f(y1, x1);
451
452 if (r > 0)
453 {
454 if (th0 < th1)
455 th0 += FZ_PI * 2;
456 n = ceilf((th0 - th1) / theta);
457 }
458 else
459 {
460 if (th1 < th0)
461 th1 += FZ_PI * 2;
462 n = ceilf((th1 - th0) / theta);
463 }
464
465 if (rev)
466 {
467 ox = x1;
468 oy = y1;
469 for (i = n-1; i > 0; i--)
470 {
471 theta = th0 + (th1 - th0) * i / n;
472 nx = cosf(theta) * r;
473 ny = sinf(theta) * r;
474 fz_add_line(ctx, s, xc + nx, yc + ny, xc + ox, yc + oy, rev);
475 ox = nx;
476 oy = ny;
477 }
478
479 fz_add_line(ctx, s, xc + x0, yc + y0, xc + ox, yc + oy, rev);
480 }
481 else
482 {
483 ox = x0;
484 oy = y0;
485 for (i = 1; i < n; i++)
486 {
487 theta = th0 + (th1 - th0) * i / n;
488 nx = cosf(theta) * r;
489 ny = sinf(theta) * r;
490 fz_add_line(ctx, s, xc + ox, yc + oy, xc + nx, yc + ny, rev);
491 ox = nx;
492 oy = ny;
493 }
494
495 fz_add_line(ctx, s, xc + ox, yc + oy, xc + x1, yc + y1, rev);
496 }
497 }
498
499 /* FLT_TINY * FLT_TINY is approximately FLT_EPSILON */
500 #define FLT_TINY 3.4e-4F
501 static int find_normal_vectors(float dx, float dy, float linewidth, float *dlx, float *dly)
502 {
503 if (dx == 0)
504 {
505 if (dy < FLT_TINY && dy > - FLT_TINY)
506 goto tiny;
507 else if (dy > 0)
508 *dlx = linewidth;
509 else
510 *dlx = -linewidth;
511 *dly = 0;
512 }
513 else if (dy == 0)
514 {
515 if (dx < FLT_TINY && dx > - FLT_TINY)
516 goto tiny;
517 else if (dx > 0)
518 *dly = -linewidth;
519 else
520 *dly = linewidth;
521 *dlx = 0;
522 }
523 else
524 {
525 float sq = dx * dx + dy * dy;
526 float scale;
527
528 if (sq < FLT_EPSILON)
529 goto tiny;
530 scale = linewidth / sqrtf(sq);
531 *dlx = dy * scale;
532 *dly = -dx * scale;
533 }
534 return 0;
535 tiny:
536 *dlx = 0;
537 *dly = 0;
538 return 1;
539 }
540
541 static void
542 fz_add_line_join(fz_context *ctx, sctx *s, float ax, float ay, float bx, float by, float cx, float cy, int join_under)
543 {
544 float miterlimit = s->miterlimit;
545 float linewidth = s->linewidth;
546 fz_linejoin linejoin = s->linejoin;
547 float dx0, dy0;
548 float dx1, dy1;
549 float dlx0, dly0;
550 float dlx1, dly1;
551 float dmx, dmy;
552 float dmr2;
553 float scale;
554 float cross;
555 int rev = 0;
556
557 dx0 = bx - ax;
558 dy0 = by - ay;
559
560 dx1 = cx - bx;
561 dy1 = cy - by;
562
563 cross = dx1 * dy0 - dx0 * dy1;
564 /* Ensure that cross >= 0 */
565 if (cross < 0)
566 {
567 float tmp;
568 tmp = dx1; dx1 = -dx0; dx0 = -tmp;
569 tmp = dy1; dy1 = -dy0; dy0 = -tmp;
570 cross = -cross;
571 rev = !rev;
572 }
573
574 if (find_normal_vectors(dx0, dy0, linewidth, &dlx0, &dly0))
575 linejoin = FZ_LINEJOIN_BEVEL;
576
577 if (find_normal_vectors(dx1, dy1, linewidth, &dlx1, &dly1))
578 linejoin = FZ_LINEJOIN_BEVEL;
579
580 dmx = (dlx0 + dlx1) * 0.5f;
581 dmy = (dly0 + dly1) * 0.5f;
582 dmr2 = dmx * dmx + dmy * dmy;
583
584 if (cross * cross < FLT_EPSILON && dx0 * dx1 + dy0 * dy1 >= 0)
585 linejoin = FZ_LINEJOIN_BEVEL;
586
587 /* XPS miter joins are clipped at miterlength, rather than simply
588 * being converted to bevelled joins. */
589 if (linejoin == FZ_LINEJOIN_MITER_XPS)
590 {
591 if (cross == 0)
592 linejoin = FZ_LINEJOIN_BEVEL;
593 else if (dmr2 * miterlimit * miterlimit >= linewidth * linewidth)
594 linejoin = FZ_LINEJOIN_MITER;
595 }
596 else if (linejoin == FZ_LINEJOIN_MITER)
597 if (dmr2 * miterlimit * miterlimit < linewidth * linewidth)
598 linejoin = FZ_LINEJOIN_BEVEL;
599
600 if (join_under)
601 {
602 fz_add_line(ctx, s, bx + dlx1, by + dly1, bx + dlx0, by + dly0, !rev);
603 }
604 else if (rev)
605 {
606 fz_add_line(ctx, s, bx + dlx1, by + dly1, bx, by, 0);
607 fz_add_line(ctx, s, bx, by, bx + dlx0, by + dly0, 0);
608 }
609 else
610 {
611 fz_add_line(ctx, s, bx, by, bx + dlx0, by + dly0, 1);
612 fz_add_line(ctx, s, bx + dlx1, by + dly1, bx, by, 1);
613 }
614
615 switch (linejoin)
616 {
617 case FZ_LINEJOIN_MITER_XPS:
618 {
619 float k, t0x, t0y, t1x, t1y;
620
621 scale = linewidth * linewidth / dmr2;
622 dmx *= scale;
623 dmy *= scale;
624 k = (scale - linewidth * miterlimit / sqrtf(dmr2)) / (scale - 1);
625 t0x = bx - dmx + k * (dmx - dlx0);
626 t0y = by - dmy + k * (dmy - dly0);
627 t1x = bx - dmx + k * (dmx - dlx1);
628 t1y = by - dmy + k * (dmy - dly1);
629
630 if (rev)
631 {
632 fz_add_line(ctx, s, t1x, t1y, bx - dlx1, by - dly1, 1);
633 fz_add_line(ctx, s, t0x, t0y, t1x, t1y, 1);
634 fz_add_line(ctx, s, bx - dlx0, by - dly0, t0x, t0y, 1);
635 }
636 else
637 {
638 fz_add_line(ctx, s, bx - dlx0, by - dly0, t0x, t0y, 0);
639 fz_add_line(ctx, s, t0x, t0y, t1x, t1y, 0);
640 fz_add_line(ctx, s, t1x, t1y, bx - dlx1, by - dly1, 0);
641 }
642 break;
643 }
644 case FZ_LINEJOIN_MITER:
645 scale = linewidth * linewidth / dmr2;
646 dmx *= scale;
647 dmy *= scale;
648
649 if (rev)
650 {
651 fz_add_line(ctx, s, bx - dmx, by - dmy, bx - dlx1, by - dly1, 1);
652 fz_add_line(ctx, s, bx - dlx0, by - dly0, bx - dmx, by - dmy, 1);
653 }
654 else
655 {
656 fz_add_line(ctx, s, bx - dlx0, by - dly0, bx - dmx, by - dmy, 0);
657 fz_add_line(ctx, s, bx - dmx, by - dmy, bx - dlx1, by - dly1, 0);
658 }
659 break;
660
661 case FZ_LINEJOIN_BEVEL:
662 fz_add_line(ctx, s, bx - dlx0, by - dly0, bx - dlx1, by - dly1, rev);
663 break;
664
665 case FZ_LINEJOIN_ROUND:
666 fz_add_arc(ctx, s, bx, by, -dlx0, -dly0, -dlx1, -dly1, rev);
667 break;
668
669 default:
670 assert("Invalid line join" == NULL);
671 }
672 }
673
674 static void
675 do_linecap(fz_context *ctx, sctx *s, float bx, float by, fz_linecap linecap, int rev, float dlx, float dly)
676 {
677 float flatness = s->flatness;
678 float linewidth = s->linewidth;
679
680 switch (linecap)
681 {
682 case FZ_LINECAP_BUTT:
683 fz_add_line(ctx, s, bx - dlx, by - dly, bx + dlx, by + dly, rev);
684 break;
685
686 case FZ_LINECAP_ROUND:
687 {
688 int i;
689 int n = ceilf(FZ_PI / (2.0f * FZ_SQRT2 * sqrtf(flatness / linewidth)));
690 float ox = bx - dlx;
691 float oy = by - dly;
692 for (i = 1; i < n; i++)
693 {
694 float theta = FZ_PI * i / n;
695 float cth = cosf(theta);
696 float sth = sinf(theta);
697 float nx = bx - dlx * cth - dly * sth;
698 float ny = by - dly * cth + dlx * sth;
699 fz_add_line(ctx, s, ox, oy, nx, ny, rev);
700 ox = nx;
701 oy = ny;
702 }
703 fz_add_line(ctx, s, ox, oy, bx + dlx, by + dly, rev);
704 break;
705 }
706
707 case FZ_LINECAP_SQUARE:
708 fz_add_line(ctx, s, bx - dlx, by - dly,
709 bx - dlx - dly, by - dly + dlx, rev);
710 fz_add_line(ctx, s, bx - dlx - dly, by - dly + dlx,
711 bx + dlx - dly, by + dly + dlx, rev);
712 fz_add_line(ctx, s, bx + dlx - dly, by + dly + dlx,
713 bx + dlx, by + dly, rev);
714 break;
715
716 case FZ_LINECAP_TRIANGLE:
717 {
718 float mx = -dly;
719 float my = dlx;
720 fz_add_line(ctx, s, bx - dlx, by - dly, bx + mx, by + my, rev);
721 fz_add_line(ctx, s, bx + mx, by + my, bx + dlx, by + dly, rev);
722 break;
723 }
724
725 default:
726 assert("Invalid line cap" == NULL);
727 }
728 }
729
730 static void
731 fz_add_line_cap(fz_context *ctx, sctx *s, float ax, float ay, float bx, float by, fz_linecap linecap, int rev)
732 {
733 float linewidth = s->linewidth;
734 float dx = bx - ax;
735 float dy = by - ay;
736
737 float scale = linewidth / sqrtf(dx * dx + dy * dy);
738 float dlx = dy * scale;
739 float dly = -dx * scale;
740
741 do_linecap(ctx, s, bx, by, linecap, rev, dlx, dly);
742 }
743
744 static void
745 fz_add_zero_len_cap(fz_context *ctx, sctx *s, float ax, float ay, fz_linecap linecap, int rev)
746 {
747 float linewidth = s->linewidth;
748 float dx = rev ? -s->dirn_x : s->dirn_x;
749 float dy = rev ? -s->dirn_y : s->dirn_y;
750 float scale, dlx, dly;
751
752 if (dx == 0 && dy == 0)
753 return;
754
755 scale = linewidth / sqrtf(dx * dx + dy * dy);
756 dlx = dy * scale;
757 dly = -dx * scale;
758
759 do_linecap(ctx, s, ax, ay, linecap, rev, dlx, dly);
760 }
761
762 static void
763 fz_add_line_dot(fz_context *ctx, sctx *s, float ax, float ay)
764 {
765 float flatness = s->flatness;
766 float linewidth = s->linewidth;
767 int n = ceilf(FZ_PI / (FZ_SQRT2 * sqrtf(flatness / linewidth)));
768 float ox = ax - linewidth;
769 float oy = ay;
770 int i;
771
772 if (n < 3)
773 n = 3;
774 for (i = 1; i < n; i++)
775 {
776 float theta = FZ_PI * 2 * i / n;
777 float cth = cosf(theta);
778 float sth = sinf(theta);
779 float nx = ax - cth * linewidth;
780 float ny = ay + sth * linewidth;
781 fz_add_line(ctx, s, ox, oy, nx, ny, 0);
782 ox = nx;
783 oy = ny;
784 }
785
786 fz_add_line(ctx, s, ox, oy, ax - linewidth, ay, 0);
787 }
788
789 static void
790 fz_stroke_flush(fz_context *ctx, sctx *s, fz_linecap start_cap, fz_linecap end_cap)
791 {
792 if (s->sn == 1)
793 {
794 fz_add_line_cap(ctx, s, s->beg[1].x, s->beg[1].y, s->beg[0].x, s->beg[0].y, start_cap, 2);
795 fz_add_line_cap(ctx, s, s->seg[0].x, s->seg[0].y, s->seg[1].x, s->seg[1].y, end_cap, 0);
796 }
797 else if (s->not_just_moves)
798 {
799 if (s->cap == FZ_LINECAP_ROUND)
800 {
801 fz_add_line_dot(ctx, s, s->beg[0].x, s->beg[0].y);
802 }
803 else
804 {
805 fz_add_zero_len_cap(ctx, s, s->beg[0].x, s->beg[0].y, s->cap, 2);
806 fz_add_zero_len_cap(ctx, s, s->beg[0].x, s->beg[0].y, s->cap, 0);
807 }
808 }
809
810 fz_gap_rasterizer(ctx, s->rast);
811 }
812
813 static void
814 fz_stroke_moveto(fz_context *ctx, void *s_, float x, float y)
815 {
816 struct sctx *s = (struct sctx *)s_;
817
818 s->seg[0].x = s->beg[0].x = x;
819 s->seg[0].y = s->beg[0].y = y;
820 s->sn = 0;
821 s->not_just_moves = 0;
822 s->from_bezier = 0;
823 s->dirn_x = 0;
824 s->dirn_y = 0;
825 }
826
827 static void
828 fz_stroke_lineto_aux(fz_context *ctx, sctx *s, float x, float y, int from_bezier, float dirn_x, float dirn_y)
829 {
830 float ox = s->seg[s->sn].x;
831 float oy = s->seg[s->sn].y;
832 float dx = x - ox;
833 float dy = y - oy;
834 float dlx, dly;
835
836 s->not_just_moves = 1;
837
838 /* We store the direction (as used for the alignment of caps etc) based on the
839 * direction we are passed in. */
840 s->dirn_x = dirn_x;
841 s->dirn_y = dirn_y;
842
843 /* We calculate the normal vectors from the delta that we have just moved. */
844 if (find_normal_vectors(dx, dy, s->linewidth, &dlx, &dly))
845 {
846 return;
847 }
848
849 if (s->sn == 1)
850 fz_add_line_join(ctx, s, s->seg[0].x, s->seg[0].y, ox, oy, x, y, s->from_bezier & from_bezier);
851
852 #if 1
853 if (0 && dx == 0)
854 {
855 fz_add_vert_rect(ctx, s, ox - dlx, oy, x + dlx, y);
856 }
857 else if (dy == 0)
858 {
859 fz_add_horiz_rect(ctx, s, ox, oy - dly, x, y + dly);
860 }
861 else
862 #endif
863 {
864
865 fz_add_line(ctx, s, ox - dlx, oy - dly, x - dlx, y - dly, 0);
866 fz_add_line(ctx, s, x + dlx, y + dly, ox + dlx, oy + dly, 1);
867 }
868
869 if (s->sn)
870 {
871 s->seg[0] = s->seg[1];
872 s->seg[1].x = x;
873 s->seg[1].y = y;
874 }
875 else
876 {
877 s->seg[1].x = s->beg[1].x = x;
878 s->seg[1].y = s->beg[1].y = y;
879 s->sn = 1;
880 }
881 s->from_bezier = from_bezier;
882 }
883
884 static void
885 fz_stroke_lineto(fz_context *ctx, sctx *s, float x, float y, int from_bezier)
886 {
887 float ox = s->seg[s->sn].x;
888 float oy = s->seg[s->sn].y;
889 float dx = x - ox;
890 float dy = y - oy;
891 fz_stroke_lineto_aux(ctx, s, x, y, from_bezier, dx, dy);
892 }
893
894 static void
895 fz_stroke_closepath(fz_context *ctx, sctx *s)
896 {
897 if (s->sn == 1)
898 {
899 fz_stroke_lineto(ctx, s, s->beg[0].x, s->beg[0].y, 0);
900 /* fz_stroke_lineto will *normally* end up with s->seg[1] being the x,y coords passed in.
901 * As such, the following line should draw a linejoin between the closing segment of this
902 * subpath (seg[0]->seg[1]) == (seg[0]->beg[0]) and the first segment of this subpath
903 * (beg[0]->beg[1]).
904 * In cases where the line was already at an x,y infinitesimally close to s->beg[0],
905 * fz_stroke_lineto may exit without doing any processing. This leaves seg[0]->seg[1]
906 * pointing at the penultimate line segment. Thus this draws a linejoin between that
907 * penultimate segment and the end segment. This is what we want. */
908 fz_add_line_join(ctx, s, s->seg[0].x, s->seg[0].y, s->beg[0].x, s->beg[0].y, s->beg[1].x, s->beg[1].y, 0);
909 }
910 else if (s->not_just_moves && s->cap == FZ_LINECAP_ROUND)
911 fz_add_line_dot(ctx, s, s->beg[0].x, s->beg[0].y);
912
913 s->seg[0] = s->beg[0];
914 s->sn = 0;
915 s->not_just_moves = 0;
916 s->from_bezier = 0;
917 s->dirn_x = 0;
918 s->dirn_y = 0;
919
920 fz_gap_rasterizer(ctx, s->rast);
921 }
922
923 static void
924 fz_stroke_bezier(fz_context *ctx, struct sctx *s,
925 float xa, float ya,
926 float xb, float yb,
927 float xc, float yc,
928 float xd, float yd, int depth)
929 {
930 float dmax;
931 float xab, yab;
932 float xbc, ybc;
933 float xcd, ycd;
934 float xabc, yabc;
935 float xbcd, ybcd;
936 float xabcd, yabcd;
937
938 /* termination check */
939 dmax = fz_abs(xa - xb);
940 dmax = fz_max(dmax, fz_abs(ya - yb));
941 dmax = fz_max(dmax, fz_abs(xd - xc));
942 dmax = fz_max(dmax, fz_abs(yd - yc));
943 if (dmax < s->flatness || depth >= MAX_DEPTH)
944 {
945 fz_stroke_lineto(ctx, s, xd, yd, 1);
946 return;
947 }
948
949 xab = xa + xb;
950 yab = ya + yb;
951 xbc = xb + xc;
952 ybc = yb + yc;
953 xcd = xc + xd;
954 ycd = yc + yd;
955
956 xabc = xab + xbc;
957 yabc = yab + ybc;
958 xbcd = xbc + xcd;
959 ybcd = ybc + ycd;
960
961 xabcd = xabc + xbcd;
962 yabcd = yabc + ybcd;
963
964 xab *= 0.5f; yab *= 0.5f;
965 /* xbc *= 0.5f; ybc *= 0.5f; */
966 xcd *= 0.5f; ycd *= 0.5f;
967
968 xabc *= 0.25f; yabc *= 0.25f;
969 xbcd *= 0.25f; ybcd *= 0.25f;
970
971 xabcd *= 0.125f; yabcd *= 0.125f;
972
973 fz_stroke_bezier(ctx, s, xa, ya, xab, yab, xabc, yabc, xabcd, yabcd, depth + 1);
974 fz_stroke_bezier(ctx, s, xabcd, yabcd, xbcd, ybcd, xcd, ycd, xd, yd, depth + 1);
975 }
976
977 static void
978 fz_stroke_quad(fz_context *ctx, struct sctx *s,
979 float xa, float ya,
980 float xb, float yb,
981 float xc, float yc, int depth)
982 {
983 float dmax;
984 float xab, yab;
985 float xbc, ybc;
986 float xabc, yabc;
987
988 /* termination check */
989 dmax = fz_abs(xa - xb);
990 dmax = fz_max(dmax, fz_abs(ya - yb));
991 dmax = fz_max(dmax, fz_abs(xc - xb));
992 dmax = fz_max(dmax, fz_abs(yc - yb));
993 if (dmax < s->flatness || depth >= MAX_DEPTH)
994 {
995 fz_stroke_lineto(ctx, s, xc, yc, 1);
996 return;
997 }
998
999 xab = xa + xb;
1000 yab = ya + yb;
1001 xbc = xb + xc;
1002 ybc = yb + yc;
1003
1004 xabc = xab + xbc;
1005 yabc = yab + ybc;
1006
1007 xab *= 0.5f; yab *= 0.5f;
1008 xbc *= 0.5f; ybc *= 0.5f;
1009
1010 xabc *= 0.25f; yabc *= 0.25f;
1011
1012 fz_stroke_quad(ctx, s, xa, ya, xab, yab, xabc, yabc, depth + 1);
1013 fz_stroke_quad(ctx, s, xabc, yabc, xbc, ybc, xc, yc, depth + 1);
1014 }
1015
1016 static void
1017 stroke_moveto(fz_context *ctx, void *s_, float x, float y)
1018 {
1019 sctx *s = (sctx *)s_;
1020
1021 fz_stroke_flush(ctx, s, s->stroke->start_cap, s->stroke->end_cap);
1022 fz_stroke_moveto(ctx, s, x, y);
1023 s->cur.x = x;
1024 s->cur.y = y;
1025 }
1026
1027 static void
1028 stroke_lineto(fz_context *ctx, void *s_, float x, float y)
1029 {
1030 sctx *s = (sctx *)s_;
1031
1032 fz_stroke_lineto(ctx, s, x, y, 0);
1033 s->cur.x = x;
1034 s->cur.y = y;
1035 }
1036
1037 static void
1038 stroke_curveto(fz_context *ctx, void *s_, float x1, float y1, float x2, float y2, float x3, float y3)
1039 {
1040 sctx *s = (sctx *)s_;
1041
1042 fz_stroke_bezier(ctx, s, s->cur.x, s->cur.y, x1, y1, x2, y2, x3, y3, 0);
1043 s->cur.x = x3;
1044 s->cur.y = y3;
1045 }
1046
1047 static void
1048 stroke_quadto(fz_context *ctx, void *s_, float x1, float y1, float x2, float y2)
1049 {
1050 sctx *s = (sctx *)s_;
1051
1052 fz_stroke_quad(ctx, s, s->cur.x, s->cur.y, x1, y1, x2, y2, 0);
1053 s->cur.x = x2;
1054 s->cur.y = y2;
1055 }
1056
1057 static void
1058 stroke_close(fz_context *ctx, void *s_)
1059 {
1060 sctx *s = (sctx *)s_;
1061
1062 fz_stroke_closepath(ctx, s);
1063 }
1064
1065 static const fz_path_walker stroke_proc =
1066 {
1067 stroke_moveto,
1068 stroke_lineto,
1069 stroke_curveto,
1070 stroke_close,
1071 stroke_quadto
1072 };
1073
1074 static void
1075 fz_dash_moveto(fz_context *ctx, struct sctx *s, float x, float y)
1076 {
1077 s->toggle = 1;
1078 s->offset = 0;
1079 s->phase = s->dash_phase;
1080
1081 while (s->phase > 0 && s->phase >= s->dash_list[s->offset])
1082 {
1083 s->toggle = !s->toggle;
1084 s->phase -= s->dash_list[s->offset];
1085 s->offset ++;
1086 if (s->offset == s->dash_len)
1087 s->offset = 0;
1088 }
1089
1090 s->dash_cur.x = x;
1091 s->dash_cur.y = y;
1092
1093 if (s->toggle)
1094 {
1095 fz_stroke_flush(ctx, s, s->cap, s->stroke->end_cap);
1096 s->cap = s->stroke->start_cap;
1097 fz_stroke_moveto(ctx, s, x, y);
1098 }
1099 }
1100
1101 /*
1102 Performs: a += (b-a) * i/n
1103 allowing for FP inaccuracies that can cause a to "overrun" b.
1104 */
1105 static float advance(float a, float b, float i, float n)
1106 {
1107 float d = b - a;
1108 float target = a + d * i/n;
1109
1110 if (d < 0 && target < b)
1111 target = b;
1112 else if (d > 0 && target > b)
1113 target = b;
1114
1115 return target;
1116 }
1117
1118 static void
1119 fz_dash_lineto(fz_context *ctx, struct sctx *s, float bx, float by, int from_bezier)
1120 {
1121 float dx, dy, d;
1122 float total, used, ratio, tail;
1123 float ax, ay;
1124 float mx, my;
1125 float old_bx = 0, old_by = 0;
1126 int n;
1127 int dash_cap = s->stroke->dash_cap;
1128
1129 ax = s->dash_cur.x;
1130 ay = s->dash_cur.y;
1131 dx = bx - ax;
1132 dy = by - ay;
1133 used = 0;
1134 tail = 0;
1135 total = sqrtf(dx * dx + dy * dy);
1136
1137 /* If a is off screen, bring it onto the screen. First
1138 * horizontally... */
1139 if ((d = s->rect.x0 - ax) > 0)
1140 {
1141 if (bx < s->rect.x0)
1142 {
1143 /* Entirely off screen */
1144 tail = total;
1145 old_bx = bx;
1146 old_by = by;
1147 goto adjust_for_tail;
1148 }
1149 ax = s->rect.x0; /* d > 0, dx > 0 */
1150 goto a_moved_horizontally;
1151 }
1152 else if (d < 0 && (d = (s->rect.x1 - ax)) < 0)
1153 {
1154 if (bx > s->rect.x1)
1155 {
1156 /* Entirely off screen */
1157 tail = total;
1158 old_bx = bx;
1159 old_by = by;
1160 goto adjust_for_tail;
1161 }
1162 ax = s->rect.x1; /* d < 0, dx < 0 */
1163 a_moved_horizontally: /* d and dx have the same sign */
1164 assert((d > 0 && dx > 0) || (d < 0 && dx < 0));
1165 assert(dx != 0);
1166 ay = advance(ay, by, d, dx);
1167 used = total * d/dx;
1168 total -= used;
1169 dx = bx - ax;
1170 dy = by - ay;
1171 }
1172 /* Then vertically... */
1173 if ((d = s->rect.y0 - ay) > 0)
1174 {
1175 if (by < s->rect.y0)
1176 {
1177 /* Entirely off screen */
1178 tail = total;
1179 old_bx = bx;
1180 old_by = by;
1181 goto adjust_for_tail;
1182 }
1183 ay = s->rect.y0; /* d > 0, dy > 0 */
1184 goto a_moved_vertically;
1185 }
1186 else if (d < 0 && (d = (s->rect.y1 - ay)) < 0)
1187 {
1188 if (by > s->rect.y1)
1189 {
1190 /* Entirely off screen */
1191 tail = total;
1192 old_bx = bx;
1193 old_by = by;
1194 goto adjust_for_tail;
1195 }
1196 ay = s->rect.y1; /* d < 0, dy < 0 */
1197 a_moved_vertically: /* d and dy have the same sign */
1198 assert((d > 0 && dy > 0) || (d < 0 && dy < 0));
1199 assert(dy != 0);
1200 ax = advance(ax, bx, d, dy);
1201 d = total * d/dy;
1202 total -= d;
1203 used += d;
1204 dx = bx - ax;
1205 dy = by - ay;
1206 }
1207 if (used != 0.0f)
1208 {
1209 /* Update the position in the dash array */
1210 if (s->toggle)
1211 {
1212 fz_stroke_lineto(ctx, s, ax, ay, from_bezier);
1213 }
1214 else
1215 {
1216 fz_stroke_flush(ctx, s, s->cap, s->stroke->dash_cap);
1217 s->cap = s->stroke->dash_cap;
1218 fz_stroke_moveto(ctx, s, ax, ay);
1219 }
1220 used += s->phase;
1221 n = used/s->dash_total;
1222 used -= n*s->dash_total;
1223 if (n & s->dash_len & 1)
1224 s->toggle = !s->toggle;
1225 while (used >= s->dash_list[s->offset])
1226 {
1227 used -= s->dash_list[s->offset];
1228 s->offset++;
1229 if (s->offset == s->dash_len)
1230 s->offset = 0;
1231 s->toggle = !s->toggle;
1232 }
1233 if (s->toggle)
1234 {
1235 fz_stroke_lineto(ctx, s, ax, ay, from_bezier);
1236 }
1237 else
1238 {
1239 fz_stroke_flush(ctx, s, s->cap, s->stroke->dash_cap);
1240 s->cap = s->stroke->dash_cap;
1241 fz_stroke_moveto(ctx, s, ax, ay);
1242 }
1243 s->phase = used;
1244 used = 0;
1245 }
1246
1247 /* Now if bx is off screen, bring it back */
1248 if (dx == 0)
1249 {
1250 /* Earlier stages can have moved a to be b, while leaving it completely off screen. */
1251 }
1252 else if ((d = bx - s->rect.x0) < 0)
1253 {
1254 old_bx = bx;
1255 old_by = by;
1256 bx = s->rect.x0; /* d < 0, dx < 0 */
1257 goto b_moved_horizontally;
1258 }
1259 else if (d > 0 && (d = (bx - s->rect.x1)) > 0)
1260 {
1261 old_bx = bx;
1262 old_by = by;
1263 bx = s->rect.x1; /* d > 0, dx > 0 */
1264 b_moved_horizontally: /* d and dx have the same sign */
1265 assert((d > 0 && dx > 0) || (d < 0 && dx < 0));
1266 assert(dx != 0);
1267 by = advance(by, ay, d, dx);
1268 tail = total * d/dx;
1269 total -= tail;
1270 dx = bx - ax;
1271 dy = by - ay;
1272 }
1273 /* Then vertically... */
1274 if (dy == 0)
1275 {
1276 /* Earlier stages can have moved a to be b, while leaving it completely off screen. */
1277 }
1278 else if ((d = by - s->rect.y0) < 0)
1279 {
1280 old_bx = bx;
1281 old_by = by;
1282 by = s->rect.y0; /* d < 0, dy < 0 */
1283 goto b_moved_vertically;
1284 }
1285 else if (d > 0 && (d = (by - s->rect.y1)) > 0)
1286 {
1287 float t;
1288 old_bx = bx;
1289 old_by = by;
1290 by = s->rect.y1; /* d > 0, dy > 0 */
1291 b_moved_vertically: /* d and dy have the same sign */
1292 assert((d > 0 && dy > 0) || (d < 0 && dy < 0));
1293 assert(dy != 0);
1294 bx = advance(bx, ax, d, dy);
1295 t = total * d/dy;
1296 tail += t;
1297 total -= t;
1298 dx = bx - ax;
1299 dy = by - ay;
1300 }
1301
1302 while (total - used > s->dash_list[s->offset] - s->phase)
1303 {
1304 used += s->dash_list[s->offset] - s->phase;
1305 ratio = used / total;
1306 mx = ax + ratio * dx;
1307 my = ay + ratio * dy;
1308
1309 if (s->toggle)
1310 {
1311 fz_stroke_lineto_aux(ctx, s, mx, my, from_bezier, dx, dy);
1312 }
1313 else
1314 {
1315 fz_stroke_flush(ctx, s, s->cap, dash_cap);
1316 s->cap = dash_cap;
1317 fz_stroke_moveto(ctx, s, mx, my);
1318 }
1319
1320 s->toggle = !s->toggle;
1321 s->phase = 0;
1322 s->offset ++;
1323 if (s->offset == s->dash_len)
1324 s->offset = 0;
1325 }
1326
1327 s->phase += total - used;
1328
1329 if (tail == 0.0f)
1330 {
1331 s->dash_cur.x = bx;
1332 s->dash_cur.y = by;
1333
1334 if (s->toggle)
1335 {
1336 fz_stroke_lineto_aux(ctx, s, bx, by, from_bezier, dx, dy);
1337 }
1338 }
1339 else
1340 {
1341 adjust_for_tail:
1342 s->dash_cur.x = old_bx;
1343 s->dash_cur.y = old_by;
1344 /* Update the position in the dash array */
1345 if (s->toggle)
1346 {
1347 fz_stroke_lineto_aux(ctx, s, old_bx, old_by, from_bezier, dx, dy);
1348 }
1349 else
1350 {
1351 fz_stroke_flush(ctx, s, s->cap, dash_cap);
1352 s->cap = dash_cap;
1353 fz_stroke_moveto(ctx, s, old_bx, old_by);
1354 }
1355 tail += s->phase;
1356 n = tail/s->dash_total;
1357 tail -= n*s->dash_total;
1358 if (n & s->dash_len & 1)
1359 s->toggle = !s->toggle;
1360 while (tail > s->dash_list[s->offset])
1361 {
1362 tail -= s->dash_list[s->offset];
1363 s->offset++;
1364 if (s->offset == s->dash_len)
1365 s->offset = 0;
1366 s->toggle = !s->toggle;
1367 }
1368 if (s->toggle)
1369 {
1370 fz_stroke_lineto_aux(ctx, s, old_bx, old_by, from_bezier, dx, dy);
1371 }
1372 else
1373 {
1374 fz_stroke_flush(ctx, s, s->cap, dash_cap);
1375 s->cap = dash_cap;
1376 fz_stroke_moveto(ctx, s, old_bx, old_by);
1377 }
1378 s->phase = tail;
1379 }
1380 }
1381
1382 static void
1383 fz_dash_bezier(fz_context *ctx, struct sctx *s,
1384 float xa, float ya,
1385 float xb, float yb,
1386 float xc, float yc,
1387 float xd, float yd, int depth)
1388 {
1389 float dmax;
1390 float xab, yab;
1391 float xbc, ybc;
1392 float xcd, ycd;
1393 float xabc, yabc;
1394 float xbcd, ybcd;
1395 float xabcd, yabcd;
1396
1397 /* termination check */
1398 dmax = fz_abs(xa - xb);
1399 dmax = fz_max(dmax, fz_abs(ya - yb));
1400 dmax = fz_max(dmax, fz_abs(xd - xc));
1401 dmax = fz_max(dmax, fz_abs(yd - yc));
1402 if (dmax < s->flatness || depth >= MAX_DEPTH)
1403 {
1404 fz_dash_lineto(ctx, s, xd, yd, 1);
1405 return;
1406 }
1407
1408 xab = xa + xb;
1409 yab = ya + yb;
1410 xbc = xb + xc;
1411 ybc = yb + yc;
1412 xcd = xc + xd;
1413 ycd = yc + yd;
1414
1415 xabc = xab + xbc;
1416 yabc = yab + ybc;
1417 xbcd = xbc + xcd;
1418 ybcd = ybc + ycd;
1419
1420 xabcd = xabc + xbcd;
1421 yabcd = yabc + ybcd;
1422
1423 xab *= 0.5f; yab *= 0.5f;
1424 /* xbc *= 0.5f; ybc *= 0.5f; */
1425 xcd *= 0.5f; ycd *= 0.5f;
1426
1427 xabc *= 0.25f; yabc *= 0.25f;
1428 xbcd *= 0.25f; ybcd *= 0.25f;
1429
1430 xabcd *= 0.125f; yabcd *= 0.125f;
1431
1432 fz_dash_bezier(ctx, s, xa, ya, xab, yab, xabc, yabc, xabcd, yabcd, depth + 1);
1433 fz_dash_bezier(ctx, s, xabcd, yabcd, xbcd, ybcd, xcd, ycd, xd, yd, depth + 1);
1434 }
1435
1436 static void
1437 fz_dash_quad(fz_context *ctx, struct sctx *s,
1438 float xa, float ya,
1439 float xb, float yb,
1440 float xc, float yc, int depth)
1441 {
1442 float dmax;
1443 float xab, yab;
1444 float xbc, ybc;
1445 float xabc, yabc;
1446
1447 /* termination check */
1448 dmax = fz_abs(xa - xb);
1449 dmax = fz_max(dmax, fz_abs(ya - yb));
1450 dmax = fz_max(dmax, fz_abs(xc - xb));
1451 dmax = fz_max(dmax, fz_abs(yc - yb));
1452 if (dmax < s->flatness || depth >= MAX_DEPTH)
1453 {
1454 fz_dash_lineto(ctx, s, xc, yc, 1);
1455 return;
1456 }
1457
1458 xab = xa + xb;
1459 yab = ya + yb;
1460 xbc = xb + xc;
1461 ybc = yb + yc;
1462
1463 xabc = xab + xbc;
1464 yabc = yab + ybc;
1465
1466 xab *= 0.5f; yab *= 0.5f;
1467 xbc *= 0.5f; ybc *= 0.5f;
1468
1469 xabc *= 0.25f; yabc *= 0.25f;
1470
1471 fz_dash_quad(ctx, s, xa, ya, xab, yab, xabc, yabc, depth + 1);
1472 fz_dash_quad(ctx, s, xabc, yabc, xbc, ybc, xc, yc, depth + 1);
1473 }
1474
1475 static void
1476 dash_moveto(fz_context *ctx, void *s_, float x, float y)
1477 {
1478 sctx *s = (sctx *)s_;
1479
1480 fz_dash_moveto(ctx, s, x, y);
1481 s->dash_beg.x = s->cur.x = x;
1482 s->dash_beg.y = s->cur.y = y;
1483 }
1484
1485 static void
1486 dash_lineto(fz_context *ctx, void *s_, float x, float y)
1487 {
1488 sctx *s = (sctx *)s_;
1489
1490 fz_dash_lineto(ctx, s, x, y, 0);
1491 s->cur.x = x;
1492 s->cur.y = y;
1493 }
1494
1495 static void
1496 dash_curveto(fz_context *ctx, void *s_, float x1, float y1, float x2, float y2, float x3, float y3)
1497 {
1498 sctx *s = (sctx *)s_;
1499
1500 fz_dash_bezier(ctx, s, s->cur.x, s->cur.y, x1, y1, x2, y2, x3, y3, 0);
1501 s->cur.x = x3;
1502 s->cur.y = y3;
1503 }
1504
1505 static void
1506 dash_quadto(fz_context *ctx, void *s_, float x1, float y1, float x2, float y2)
1507 {
1508 sctx *s = (sctx *)s_;
1509
1510 fz_dash_quad(ctx, s, s->cur.x, s->cur.y, x1, y1, x2, y2, 0);
1511 s->cur.x = x2;
1512 s->cur.y = y2;
1513 }
1514
1515 static void
1516 dash_close(fz_context *ctx, void *s_)
1517 {
1518 sctx *s = (sctx *)s_;
1519
1520 fz_dash_lineto(ctx, s, s->dash_beg.x, s->dash_beg.y, 0);
1521 s->cur.x = s->dash_beg.x;
1522 s->cur.y = s->dash_beg.y;
1523 }
1524
1525 static const fz_path_walker dash_proc =
1526 {
1527 dash_moveto,
1528 dash_lineto,
1529 dash_curveto,
1530 dash_close,
1531 dash_quadto
1532 };
1533
1534 static int
1535 do_flatten_stroke(fz_context *ctx, fz_rasterizer *rast, const fz_path *path, const fz_stroke_state *stroke, fz_matrix ctm, float flatness, float linewidth)
1536 {
1537 struct sctx s;
1538 const fz_path_walker *proc = &stroke_proc;
1539
1540 s.stroke = stroke;
1541 s.rast = rast;
1542 s.ctm = ctm;
1543 s.flatness = flatness;
1544 s.linejoin = stroke->linejoin;
1545 s.linewidth = linewidth * 0.5f; /* hairlines use a different value from the path value */
1546 s.miterlimit = stroke->miterlimit;
1547 s.sn = 0;
1548 s.not_just_moves = 0;
1549 s.toggle = 0;
1550 s.offset = 0;
1551 s.phase = 0;
1552 s.dirn_x = 0;
1553 s.dirn_y = 0;
1554
1555 s.cap = stroke->start_cap;
1556
1557 s.dash_list = NULL;
1558 s.dash_len = stroke->dash_len;
1559 if (s.dash_len > 0)
1560 {
1561 int i;
1562 fz_matrix inv;
1563 float max_expand;
1564 const float *list = stroke->dash_list;
1565
1566 s.dash_total = 0;
1567 for (i = 0; i < s.dash_len; i++)
1568 s.dash_total += list[i];
1569 if (s.dash_total == 0)
1570 return 1;
1571
1572 s.rect = fz_scissor_rasterizer(ctx, rast);
1573 if (fz_try_invert_matrix(&inv, ctm))
1574 return 1;
1575 s.rect = fz_transform_rect(s.rect, inv);
1576 s.rect.x0 -= linewidth;
1577 s.rect.x1 += linewidth;
1578 s.rect.y0 -= linewidth;
1579 s.rect.y1 += linewidth;
1580
1581 max_expand = fz_matrix_max_expansion(ctm);
1582 if (s.dash_total >= 0.01f && s.dash_total * max_expand >= 0.5f)
1583 {
1584 proc = &dash_proc;
1585 s.dash_phase = fmodf(stroke->dash_phase, s.dash_total);
1586 s.dash_list = list;
1587 }
1588 }
1589
1590 s.cur.x = s.cur.y = 0;
1591 fz_walk_path(ctx, path, proc, &s);
1592 fz_stroke_flush(ctx, &s, s.cap, stroke->end_cap);
1593
1594 return fz_is_empty_irect(fz_bound_rasterizer(ctx, rast));
1595 }
1596
1597 int
1598 fz_flatten_stroke_path(fz_context *ctx, fz_rasterizer *rast, const fz_path *path, const fz_stroke_state *stroke, fz_matrix ctm, float flatness, float linewidth, fz_irect scissor, fz_irect *bbox)
1599 {
1600 int empty;
1601 fz_irect local_bbox;
1602 if (!bbox)
1603 bbox = &local_bbox;
1604
1605 if (fz_reset_rasterizer(ctx, rast, scissor))
1606 {
1607 empty = do_flatten_stroke(ctx, rast, path, stroke, ctm, flatness, linewidth);
1608 if (empty)
1609 return *bbox = fz_empty_irect, 1;
1610 fz_postindex_rasterizer(ctx, rast);
1611 }
1612
1613 empty = do_flatten_stroke(ctx, rast, path, stroke, ctm, flatness, linewidth);
1614 if (empty)
1615 return *bbox = fz_empty_irect, 1;
1616
1617 *bbox = fz_intersect_irect(scissor, fz_bound_rasterizer(ctx, rast));
1618 return fz_is_empty_irect(*bbox);
1619 }