Skip to main content

pdf2_render/
path.rs

1//! Paths: construction in user space, flattening to device-space polylines,
2//! and turning a stroked polyline into the polygons a fill can paint.
3
4use crate::geom::{Matrix, Point};
5
6/// Line-dash pattern, in user-space lengths.
7#[derive(Debug, Clone, PartialEq)]
8pub struct Dash {
9    /// Alternating on/off lengths; empty means a solid line.
10    pub pattern: Vec<f64>,
11    /// Distance into the pattern at which the path starts.
12    pub phase: f64,
13}
14
15impl Dash {
16    /// A solid line.
17    pub fn solid() -> Self {
18        Self {
19            pattern: Vec::new(),
20            phase: 0.0,
21        }
22    }
23
24    /// Whether the line is solid.
25    pub fn is_solid(&self) -> bool {
26        self.pattern.is_empty() || self.pattern.iter().all(|length| *length <= 0.0)
27    }
28}
29
30/// How a stroked path ends.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum Cap {
33    /// Ends at the endpoint.
34    Butt,
35    /// Rounded end, a disc of half the line width.
36    Round,
37    /// Extends by half the line width.
38    Square,
39}
40
41/// How stroked segments meet, from the `j` operator.
42#[derive(Debug, Clone, Copy, PartialEq, Eq)]
43pub enum Join {
44    /// A sharp join, cut back to a bevel when the miter limit is exceeded.
45    Miter,
46    /// A rounded join.
47    Round,
48    /// A cut-off join.
49    Bevel,
50}
51
52/// One segment of a subpath.
53#[derive(Debug, Clone, Copy, PartialEq)]
54pub enum Segment {
55    /// A straight line to the point.
56    Line(Point),
57    /// A cubic Bézier curve.
58    Cubic {
59        /// First control point.
60        c1: Point,
61        /// Second control point.
62        c2: Point,
63        /// End point.
64        to: Point,
65    },
66}
67
68/// A connected run of segments.
69#[derive(Debug, Clone, PartialEq)]
70pub struct Subpath {
71    /// Where the subpath starts.
72    pub start: Point,
73    /// The segments that follow.
74    pub segments: Vec<Segment>,
75    /// Whether the subpath was closed.
76    pub closed: bool,
77}
78
79/// A path in user space.
80#[derive(Debug, Clone, Default, PartialEq)]
81pub struct Path {
82    /// The subpaths, in the order they were added.
83    pub subpaths: Vec<Subpath>,
84}
85
86impl Path {
87    /// An empty path.
88    pub fn new() -> Self {
89        Self::default()
90    }
91
92    /// Whether the path has no segments.
93    pub fn is_empty(&self) -> bool {
94        self.subpaths
95            .iter()
96            .all(|subpath| subpath.segments.is_empty())
97    }
98
99    /// Start a new subpath.
100    pub fn move_to(&mut self, point: Point) {
101        self.subpaths.push(Subpath {
102            start: point,
103            segments: Vec::new(),
104            closed: false,
105        });
106    }
107
108    /// A line from the current point.
109    pub fn line_to(&mut self, point: Point) {
110        if let Some(subpath) = self.subpaths.last_mut() {
111            subpath.segments.push(Segment::Line(point));
112        } else {
113            self.move_to(point);
114        }
115    }
116
117    /// A cubic curve from the current point.
118    pub fn curve_to(&mut self, c1: Point, c2: Point, to: Point) {
119        if let Some(subpath) = self.subpaths.last_mut() {
120            subpath.segments.push(Segment::Cubic { c1, c2, to });
121        } else {
122            self.move_to(to);
123        }
124    }
125
126    /// Close the current subpath.
127    pub fn close(&mut self) {
128        if let Some(subpath) = self.subpaths.last_mut() {
129            subpath.closed = true;
130        }
131    }
132
133    /// Append a rectangle as its own closed subpath.
134    pub fn add_rect(&mut self, x: f64, y: f64, width: f64, height: f64) {
135        self.move_to(Point::new(x, y));
136        self.line_to(Point::new(x + width, y));
137        self.line_to(Point::new(x + width, y + height));
138        self.line_to(Point::new(x, y + height));
139        self.close();
140    }
141
142    /// Flatten to device-space polylines, applying `ctm`.
143    ///
144    /// Curves are subdivided a fixed number of times: enough that the fixtures
145    /// are visibly round at 1× and cheap to rasterise, and documented as the
146    /// tolerance model until adaptive flattening replaces it.
147    pub fn flatten(&self, ctm: Matrix) -> Vec<Vec<Point>> {
148        const CURVE_STEPS: usize = 24;
149        let mut polylines = Vec::with_capacity(self.subpaths.len());
150        for subpath in &self.subpaths {
151            let mut points = vec![ctm.apply(subpath.start)];
152            let mut current = subpath.start;
153            for segment in &subpath.segments {
154                match *segment {
155                    Segment::Line(to) => {
156                        points.push(ctm.apply(to));
157                        current = to;
158                    }
159                    Segment::Cubic { c1, c2, to } => {
160                        for step in 1..=CURVE_STEPS {
161                            let t = step as f64 / CURVE_STEPS as f64;
162                            points.push(ctm.apply(cubic_at(current, c1, c2, to, t)));
163                        }
164                        current = to;
165                    }
166                }
167            }
168            if subpath.closed && points.len() > 1 {
169                let first = points[0];
170                let last = *points.last().expect("non-empty");
171                if (first.x - last.x).abs() > f64::EPSILON
172                    || (first.y - last.y).abs() > f64::EPSILON
173                {
174                    points.push(first);
175                }
176            }
177            if points.len() > 1 {
178                polylines.push(points);
179            }
180        }
181        polylines
182    }
183}
184
185fn cubic_at(p0: Point, c1: Point, c2: Point, p3: Point, t: f64) -> Point {
186    let u = 1.0 - t;
187    let a = u * u * u;
188    let b = 3.0 * u * u * t;
189    let c = 3.0 * u * t * t;
190    let d = t * t * t;
191    Point::new(
192        a * p0.x + b * c1.x + c * c2.x + d * p3.x,
193        a * p0.y + b * c1.y + c * c2.y + d * p3.y,
194    )
195}
196
197/// Split a device-space polyline into the "on" runs of a dash pattern.
198///
199/// Dash lengths are user-space values; they are scaled by the square root of
200/// the CTM determinant, which matches a uniform scale exactly and is the usual
201/// approximation under shear.
202pub fn dash_polyline(polyline: &[Point], dash: &Dash, ctm_scale: f64) -> Vec<Vec<Point>> {
203    if dash.is_solid() || polyline.len() < 2 {
204        return vec![polyline.to_vec()];
205    }
206    let pattern: Vec<f64> = dash
207        .pattern
208        .iter()
209        .map(|length| (length * ctm_scale).abs())
210        .filter(|length| *length > 1e-9)
211        .collect();
212    if pattern.is_empty() {
213        return vec![polyline.to_vec()];
214    }
215    let mut runs = Vec::new();
216    let mut current_run: Vec<Point> = Vec::new();
217    // Which pattern entry applies, and how far into it we are.
218    let mut index = 0usize;
219    let mut remaining = pattern[0];
220    let mut phase = dash.phase * ctm_scale;
221    while phase > 0.0 {
222        if phase >= remaining {
223            phase -= remaining;
224            index = (index + 1) % pattern.len();
225            remaining = pattern[index];
226        } else {
227            remaining -= phase;
228            phase = 0.0;
229        }
230    }
231    let mut on = index.is_multiple_of(2);
232    if on {
233        current_run.push(polyline[0]);
234    }
235    for window in polyline.windows(2) {
236        let mut start = window[0];
237        let end = window[1];
238        let dx = end.x - start.x;
239        let dy = end.y - start.y;
240        let length = (dx * dx + dy * dy).sqrt();
241        if length <= 1e-12 {
242            continue;
243        }
244        let unit_x = dx / length;
245        let unit_y = dy / length;
246        let mut travelled = 0.0;
247        while travelled < length {
248            let step = remaining.min(length - travelled);
249            let next = Point::new(start.x + unit_x * step, start.y + unit_y * step);
250            if on {
251                if current_run.is_empty() {
252                    current_run.push(start);
253                }
254                current_run.push(next);
255            }
256            travelled += step;
257            remaining -= step;
258            if remaining <= 1e-9 {
259                if on && current_run.len() > 1 {
260                    runs.push(std::mem::take(&mut current_run));
261                }
262                index = (index + 1) % pattern.len();
263                remaining = pattern[index];
264                on = index.is_multiple_of(2);
265            }
266            start = next;
267        }
268    }
269    if on && current_run.len() > 1 {
270        runs.push(current_run);
271    }
272    runs
273}
274
275/// Turn stroked polylines into filled polygons.
276///
277/// The union of per-segment quads, round joins and caps is returned as
278/// polygons wound the same way, so a non-zero fill paints exactly the stroke.
279pub fn stroke_outline(
280    polylines: &[Vec<Point>],
281    width: f64,
282    cap: Cap,
283    join: Join,
284    miter_limit: f64,
285) -> Vec<Vec<Point>> {
286    let half = (width / 2.0).max(0.0);
287    if half <= 0.0 {
288        return Vec::new();
289    }
290    let mut polygons = Vec::new();
291    for polyline in polylines {
292        if polyline.len() < 2 {
293            continue;
294        }
295        let last_index = polyline.len() - 2;
296        for (index, window) in polyline.windows(2).enumerate() {
297            let start = window[0];
298            let end = window[1];
299            let first = index == 0;
300            let last = index == last_index;
301            // Square caps extend the end segments by half the line width;
302            // butt caps stop exactly at the endpoint.
303            let (from, to) = if cap == Cap::Square {
304                (
305                    if first {
306                        extend(start, end, half)
307                    } else {
308                        start
309                    },
310                    if last { extend(end, start, half) } else { end },
311                )
312            } else {
313                (start, end)
314            };
315            let quad = segment_quad(from, to, half);
316            if quad.is_empty() {
317                continue;
318            }
319            polygons.push(oriented(quad));
320            // A vertex between two segments joins them; the closing vertex of a
321            // closed path is a seam, covered by the first segment's quad.
322            if !first {
323                polygons.push(join_polygon(polyline, index, half, join, miter_limit));
324            }
325            if last && cap == Cap::Round {
326                polygons.push(oriented(circle(end, half)));
327            }
328        }
329        if cap == Cap::Round {
330            polygons.push(oriented(circle(polyline[0], half)));
331        }
332    }
333    polygons
334}
335
336/// The wedge that joins the segment ending at `polyline[index]` to the one
337/// starting there.
338fn join_polygon(
339    polyline: &[Point],
340    index: usize,
341    half: f64,
342    join: Join,
343    miter_limit: f64,
344) -> Vec<Point> {
345    let vertex = polyline[index];
346    let before = polyline[index - 1];
347    let after = polyline[index + 1];
348    if join == Join::Round {
349        return oriented(circle(vertex, half));
350    }
351    let (Some(incoming), Some(outgoing)) = (unit(before, vertex), unit(vertex, after)) else {
352        return oriented(circle(vertex, half));
353    };
354    // The outer side of a turn is the side the path turns away from: opposite
355    // the left normal for a left turn, along it for a right turn.
356    let cross = incoming.0 * outgoing.1 - incoming.1 * outgoing.0;
357    let factor = if cross > 0.0 { -1.0 } else { 1.0 };
358    let back_out = offset(vertex, incoming, half * factor);
359    let forward_out = offset(vertex, outgoing, half * factor);
360    if join == Join::Bevel || cross.abs() < 1e-9 {
361        return oriented(vec![vertex, back_out, forward_out]);
362    }
363    // Miter: the two outer edges meet at a point along the bisector; past the
364    // limit the standard cuts the corner instead (8.4.3.5).
365    let Some(tip) = intersect(back_out, incoming, forward_out, outgoing) else {
366        return oriented(vec![vertex, back_out, forward_out]);
367    };
368    let length = ((tip.x - vertex.x).powi(2) + (tip.y - vertex.y).powi(2)).sqrt();
369    if length > half * miter_limit.max(1.0) {
370        return oriented(vec![vertex, back_out, forward_out]);
371    }
372    oriented(vec![vertex, back_out, tip, forward_out])
373}
374
375/// The point `distance` along the left normal of `direction` from `from`.
376fn offset(from: Point, direction: (f64, f64), distance: f64) -> Point {
377    Point::new(
378        from.x - direction.1 * distance,
379        from.y + direction.0 * distance,
380    )
381}
382
383/// A unit vector in the direction `to - from`, or `None` for a zero length.
384fn unit(from: Point, to: Point) -> Option<(f64, f64)> {
385    let dx = to.x - from.x;
386    let dy = to.y - from.y;
387    let length = (dx * dx + dy * dy).sqrt();
388    if length <= 1e-12 {
389        return None;
390    }
391    Some((dx / length, dy / length))
392}
393
394/// Where the line through `p` along `d` meets the line through `q` along `e`.
395fn intersect(p: Point, d: (f64, f64), q: Point, e: (f64, f64)) -> Option<Point> {
396    let denominator = d.0 * e.1 - d.1 * e.0;
397    if denominator.abs() < 1e-9 {
398        return None;
399    }
400    let dx = q.x - p.x;
401    let dy = q.y - p.y;
402    let t = (dx * e.1 - dy * e.0) / denominator;
403    Some(Point::new(p.x + d.0 * t, p.y + d.1 * t))
404}
405
406/// A point `distance` away from `from`, in the direction `from → towards`.
407fn extend(from: Point, towards: Point, distance: f64) -> Point {
408    let dx = towards.x - from.x;
409    let dy = towards.y - from.y;
410    let length = (dx * dx + dy * dy).sqrt();
411    if length <= 1e-12 {
412        return from;
413    }
414    Point::new(
415        from.x - dx / length * distance,
416        from.y - dy / length * distance,
417    )
418}
419
420fn segment_quad(start: Point, end: Point, half: f64) -> Vec<Point> {
421    let dx = end.x - start.x;
422    let dy = end.y - start.y;
423    let length = (dx * dx + dy * dy).sqrt();
424    if length <= 1e-12 {
425        return Vec::new();
426    }
427    let nx = -dy / length * half;
428    let ny = dx / length * half;
429    vec![
430        Point::new(start.x + nx, start.y + ny),
431        Point::new(end.x + nx, end.y + ny),
432        Point::new(end.x - nx, end.y - ny),
433        Point::new(start.x - nx, start.y - ny),
434    ]
435}
436
437/// A polygon approximating a disc.
438pub fn circle(center: Point, radius: f64) -> Vec<Point> {
439    const SEGMENTS: usize = 16;
440    let mut points = Vec::with_capacity(SEGMENTS);
441    for step in 0..SEGMENTS {
442        let angle = step as f64 / SEGMENTS as f64 * std::f64::consts::TAU;
443        points.push(Point::new(
444            center.x + radius * angle.cos(),
445            center.y + radius * angle.sin(),
446        ));
447    }
448    points
449}
450
451/// Reverse a polygon when it is wound clockwise, so unions behave under the
452/// non-zero rule.
453fn oriented(mut polygon: Vec<Point>) -> Vec<Point> {
454    let area = signed_area(&polygon);
455    if area < 0.0 {
456        polygon.reverse();
457    }
458    polygon
459}
460
461fn signed_area(polygon: &[Point]) -> f64 {
462    let mut sum = 0.0;
463    for index in 0..polygon.len() {
464        let current = polygon[index];
465        let next = polygon[(index + 1) % polygon.len()];
466        sum += current.x * next.y - next.x * current.y;
467    }
468    sum / 2.0
469}
470
471#[cfg(test)]
472mod tests {
473    use super::{dash_polyline, stroke_outline, Cap, Dash, Join, Path};
474    use crate::geom::{Matrix, Point};
475
476    #[test]
477    fn rectangles_flatten_to_closed_polylines() {
478        let mut path = Path::new();
479        path.add_rect(0.0, 0.0, 10.0, 20.0);
480        let polylines = path.flatten(Matrix::IDENTITY);
481        assert_eq!(polylines.len(), 1);
482        assert_eq!(polylines[0].len(), 5, "four corners plus the closing point");
483        assert_eq!(polylines[0][0], Point::new(0.0, 0.0));
484        assert_eq!(polylines[0][2], Point::new(10.0, 20.0));
485    }
486
487    #[test]
488    fn curves_are_subdivided() {
489        let mut path = Path::new();
490        path.move_to(Point::new(0.0, 0.0));
491        path.curve_to(
492            Point::new(0.0, 10.0),
493            Point::new(10.0, 10.0),
494            Point::new(10.0, 0.0),
495        );
496        let polylines = path.flatten(Matrix::IDENTITY);
497        assert_eq!(polylines[0].len(), 25);
498        assert_eq!(*polylines[0].last().expect("end"), Point::new(10.0, 0.0));
499    }
500
501    #[test]
502    fn a_solid_dash_keeps_the_polyline() {
503        let line = vec![Point::new(0.0, 0.0), Point::new(10.0, 0.0)];
504        let runs = dash_polyline(&line, &Dash::solid(), 1.0);
505        assert_eq!(runs.len(), 1);
506        assert_eq!(runs[0], line);
507    }
508
509    #[test]
510    fn a_dash_pattern_splits_the_line() {
511        let line = vec![Point::new(0.0, 0.0), Point::new(20.0, 0.0)];
512        let dash = Dash {
513            pattern: vec![5.0, 5.0],
514            phase: 0.0,
515        };
516        let runs = dash_polyline(&line, &dash, 1.0);
517        assert_eq!(runs.len(), 2);
518        assert_eq!(runs[0], vec![Point::new(0.0, 0.0), Point::new(5.0, 0.0)]);
519        assert_eq!(runs[1], vec![Point::new(10.0, 0.0), Point::new(15.0, 0.0)]);
520    }
521
522    #[test]
523    fn a_phase_offsets_the_first_run() {
524        let line = vec![Point::new(0.0, 0.0), Point::new(20.0, 0.0)];
525        let dash = Dash {
526            pattern: vec![5.0, 5.0],
527            phase: 2.0,
528        };
529        let runs = dash_polyline(&line, &dash, 1.0);
530        assert_eq!(runs[0][0], Point::new(0.0, 0.0));
531        assert_eq!(runs[0][1], Point::new(3.0, 0.0));
532    }
533
534    #[test]
535    fn strokes_become_polygons_around_the_line() {
536        let line = vec![Point::new(10.0, 10.0), Point::new(30.0, 10.0)];
537        let polygons = stroke_outline(&[line], 4.0, Cap::Butt, Join::Miter, 10.0);
538        assert!(!polygons.is_empty());
539        // Every polygon is wound counter-clockwise after orientation.
540        for polygon in &polygons {
541            assert!(super::signed_area(polygon) >= 0.0);
542        }
543        // The quad around the segment spans y from 8 to 12.
544        let quad = &polygons[0];
545        let min_y = quad.iter().fold(f64::MAX, |min, point| min.min(point.y));
546        let max_y = quad.iter().fold(f64::MIN, |max, point| max.max(point.y));
547        assert!((min_y - 8.0).abs() < 1e-9, "{min_y}");
548        assert!((max_y - 12.0).abs() < 1e-9, "{max_y}");
549    }
550
551    /// A right-angle corner from (0, 10) to (10, 10) to (10, 20) with a 4-wide
552    /// stroke: the outer corner is the square [10, 12] x [8, 10], and a 90°
553    /// miter needs 1.41 half-widths to reach into it.
554    fn corner(join: Join, limit: f64) -> Vec<Vec<Point>> {
555        let path = vec![
556            Point::new(0.0, 10.0),
557            Point::new(10.0, 10.0),
558            Point::new(10.0, 20.0),
559        ];
560        stroke_outline(&[path], 4.0, Cap::Butt, join, limit)
561    }
562
563    fn painted(polygons: &[Vec<Point>], x: u32, y: u32) -> bool {
564        let mut canvas = crate::canvas::Canvas::new(24, 30, crate::canvas::Color::WHITE);
565        let mask = crate::canvas::ClipMask::all(24, 30);
566        crate::raster::fill_polygons(
567            &mut canvas,
568            &mask,
569            polygons,
570            crate::canvas::Color::BLACK,
571            false,
572            1.0,
573        );
574        canvas.pixel(x, y) == Some([0, 0, 0, 255])
575    }
576
577    #[test]
578    fn a_miter_join_fills_the_corner_and_a_bevel_cuts_it() {
579        // (11, 8) is inside the corner square but outside both stroke bands.
580        assert!(
581            painted(&corner(Join::Miter, 10.0), 11, 8),
582            "the miter fills the corner"
583        );
584        assert!(
585            !painted(&corner(Join::Bevel, 10.0), 11, 8),
586            "the bevel cuts the corner"
587        );
588    }
589
590    #[test]
591    fn the_miter_limit_cuts_the_corner_back_to_a_bevel() {
592        // The 90-degree miter is 1.41 half-widths long: accepted at the default
593        // limit of 10, cut back once the limit is under 1.41 (8.4.3.5).
594        assert!(
595            painted(&corner(Join::Miter, 10.0), 11, 8),
596            "limit 10 miters"
597        );
598        assert!(
599            !painted(&corner(Join::Miter, 1.2), 11, 8),
600            "limit 1.2 bevels"
601        );
602    }
603}