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.
42///
43/// Joins are drawn as round joins whatever PDF asks for; miter and bevel are
44/// accepted so that content streams parse, and the difference is documented as
45/// a rendering limitation rather than silently changing geometry.
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub enum Join {
48    /// A sharp join (drawn round here).
49    Miter,
50    /// A rounded join.
51    Round,
52    /// A cut-off join (drawn round here).
53    Bevel,
54}
55
56/// One segment of a subpath.
57#[derive(Debug, Clone, Copy, PartialEq)]
58pub enum Segment {
59    /// A straight line to the point.
60    Line(Point),
61    /// A cubic Bézier curve.
62    Cubic {
63        /// First control point.
64        c1: Point,
65        /// Second control point.
66        c2: Point,
67        /// End point.
68        to: Point,
69    },
70}
71
72/// A connected run of segments.
73#[derive(Debug, Clone, PartialEq)]
74pub struct Subpath {
75    /// Where the subpath starts.
76    pub start: Point,
77    /// The segments that follow.
78    pub segments: Vec<Segment>,
79    /// Whether the subpath was closed.
80    pub closed: bool,
81}
82
83/// A path in user space.
84#[derive(Debug, Clone, Default, PartialEq)]
85pub struct Path {
86    /// The subpaths, in the order they were added.
87    pub subpaths: Vec<Subpath>,
88}
89
90impl Path {
91    /// An empty path.
92    pub fn new() -> Self {
93        Self::default()
94    }
95
96    /// Whether the path has no segments.
97    pub fn is_empty(&self) -> bool {
98        self.subpaths
99            .iter()
100            .all(|subpath| subpath.segments.is_empty())
101    }
102
103    /// Start a new subpath.
104    pub fn move_to(&mut self, point: Point) {
105        self.subpaths.push(Subpath {
106            start: point,
107            segments: Vec::new(),
108            closed: false,
109        });
110    }
111
112    /// A line from the current point.
113    pub fn line_to(&mut self, point: Point) {
114        if let Some(subpath) = self.subpaths.last_mut() {
115            subpath.segments.push(Segment::Line(point));
116        } else {
117            self.move_to(point);
118        }
119    }
120
121    /// A cubic curve from the current point.
122    pub fn curve_to(&mut self, c1: Point, c2: Point, to: Point) {
123        if let Some(subpath) = self.subpaths.last_mut() {
124            subpath.segments.push(Segment::Cubic { c1, c2, to });
125        } else {
126            self.move_to(to);
127        }
128    }
129
130    /// Close the current subpath.
131    pub fn close(&mut self) {
132        if let Some(subpath) = self.subpaths.last_mut() {
133            subpath.closed = true;
134        }
135    }
136
137    /// Append a rectangle as its own closed subpath.
138    pub fn add_rect(&mut self, x: f64, y: f64, width: f64, height: f64) {
139        self.move_to(Point::new(x, y));
140        self.line_to(Point::new(x + width, y));
141        self.line_to(Point::new(x + width, y + height));
142        self.line_to(Point::new(x, y + height));
143        self.close();
144    }
145
146    /// Flatten to device-space polylines, applying `ctm`.
147    ///
148    /// Curves are subdivided a fixed number of times: enough that the fixtures
149    /// are visibly round at 1× and cheap to rasterise, and documented as the
150    /// tolerance model until adaptive flattening replaces it.
151    pub fn flatten(&self, ctm: Matrix) -> Vec<Vec<Point>> {
152        const CURVE_STEPS: usize = 24;
153        let mut polylines = Vec::with_capacity(self.subpaths.len());
154        for subpath in &self.subpaths {
155            let mut points = vec![ctm.apply(subpath.start)];
156            let mut current = subpath.start;
157            for segment in &subpath.segments {
158                match *segment {
159                    Segment::Line(to) => {
160                        points.push(ctm.apply(to));
161                        current = to;
162                    }
163                    Segment::Cubic { c1, c2, to } => {
164                        for step in 1..=CURVE_STEPS {
165                            let t = step as f64 / CURVE_STEPS as f64;
166                            points.push(ctm.apply(cubic_at(current, c1, c2, to, t)));
167                        }
168                        current = to;
169                    }
170                }
171            }
172            if subpath.closed && points.len() > 1 {
173                let first = points[0];
174                let last = *points.last().expect("non-empty");
175                if (first.x - last.x).abs() > f64::EPSILON
176                    || (first.y - last.y).abs() > f64::EPSILON
177                {
178                    points.push(first);
179                }
180            }
181            if points.len() > 1 {
182                polylines.push(points);
183            }
184        }
185        polylines
186    }
187}
188
189fn cubic_at(p0: Point, c1: Point, c2: Point, p3: Point, t: f64) -> Point {
190    let u = 1.0 - t;
191    let a = u * u * u;
192    let b = 3.0 * u * u * t;
193    let c = 3.0 * u * t * t;
194    let d = t * t * t;
195    Point::new(
196        a * p0.x + b * c1.x + c * c2.x + d * p3.x,
197        a * p0.y + b * c1.y + c * c2.y + d * p3.y,
198    )
199}
200
201/// Split a device-space polyline into the "on" runs of a dash pattern.
202///
203/// Dash lengths are user-space values; they are scaled by the square root of
204/// the CTM determinant, which matches a uniform scale exactly and is the usual
205/// approximation under shear.
206pub fn dash_polyline(polyline: &[Point], dash: &Dash, ctm_scale: f64) -> Vec<Vec<Point>> {
207    if dash.is_solid() || polyline.len() < 2 {
208        return vec![polyline.to_vec()];
209    }
210    let pattern: Vec<f64> = dash
211        .pattern
212        .iter()
213        .map(|length| (length * ctm_scale).abs())
214        .filter(|length| *length > 1e-9)
215        .collect();
216    if pattern.is_empty() {
217        return vec![polyline.to_vec()];
218    }
219    let mut runs = Vec::new();
220    let mut current_run: Vec<Point> = Vec::new();
221    // Which pattern entry applies, and how far into it we are.
222    let mut index = 0usize;
223    let mut remaining = pattern[0];
224    let mut phase = dash.phase * ctm_scale;
225    while phase > 0.0 {
226        if phase >= remaining {
227            phase -= remaining;
228            index = (index + 1) % pattern.len();
229            remaining = pattern[index];
230        } else {
231            remaining -= phase;
232            phase = 0.0;
233        }
234    }
235    let mut on = index.is_multiple_of(2);
236    if on {
237        current_run.push(polyline[0]);
238    }
239    for window in polyline.windows(2) {
240        let mut start = window[0];
241        let end = window[1];
242        let dx = end.x - start.x;
243        let dy = end.y - start.y;
244        let length = (dx * dx + dy * dy).sqrt();
245        if length <= 1e-12 {
246            continue;
247        }
248        let unit_x = dx / length;
249        let unit_y = dy / length;
250        let mut travelled = 0.0;
251        while travelled < length {
252            let step = remaining.min(length - travelled);
253            let next = Point::new(start.x + unit_x * step, start.y + unit_y * step);
254            if on {
255                if current_run.is_empty() {
256                    current_run.push(start);
257                }
258                current_run.push(next);
259            }
260            travelled += step;
261            remaining -= step;
262            if remaining <= 1e-9 {
263                if on && current_run.len() > 1 {
264                    runs.push(std::mem::take(&mut current_run));
265                }
266                index = (index + 1) % pattern.len();
267                remaining = pattern[index];
268                on = index.is_multiple_of(2);
269            }
270            start = next;
271        }
272    }
273    if on && current_run.len() > 1 {
274        runs.push(current_run);
275    }
276    runs
277}
278
279/// Turn stroked polylines into filled polygons.
280///
281/// The union of per-segment quads, round joins and caps is returned as
282/// polygons wound the same way, so a non-zero fill paints exactly the stroke.
283pub fn stroke_outline(polylines: &[Vec<Point>], width: f64, cap: Cap) -> Vec<Vec<Point>> {
284    let half = (width / 2.0).max(0.0);
285    if half <= 0.0 {
286        return Vec::new();
287    }
288    let mut polygons = Vec::new();
289    for polyline in polylines {
290        if polyline.len() < 2 {
291            continue;
292        }
293        let last_index = polyline.len() - 2;
294        for (index, window) in polyline.windows(2).enumerate() {
295            let start = window[0];
296            let end = window[1];
297            let first = index == 0;
298            let last = index == last_index;
299            // Square caps extend the end segments by half the line width;
300            // butt caps stop exactly at the endpoint.
301            let (from, to) = if cap == Cap::Square {
302                (
303                    if first {
304                        extend(start, end, half)
305                    } else {
306                        start
307                    },
308                    if last { extend(end, start, half) } else { end },
309                )
310            } else {
311                (start, end)
312            };
313            let quad = segment_quad(from, to, half);
314            if quad.is_empty() {
315                continue;
316            }
317            polygons.push(oriented(quad));
318            // Interior vertices get a round join; the closing vertex is a seam,
319            // not a cap, so it is covered by the last segment's quad.
320            if !first {
321                polygons.push(oriented(circle(start, half)));
322            }
323            if last && cap == Cap::Round {
324                polygons.push(oriented(circle(end, half)));
325            }
326        }
327        if cap == Cap::Round {
328            polygons.push(oriented(circle(polyline[0], half)));
329        }
330    }
331    polygons
332}
333
334/// A point `distance` away from `from`, in the direction `from → towards`.
335fn extend(from: Point, towards: Point, distance: f64) -> Point {
336    let dx = towards.x - from.x;
337    let dy = towards.y - from.y;
338    let length = (dx * dx + dy * dy).sqrt();
339    if length <= 1e-12 {
340        return from;
341    }
342    Point::new(
343        from.x - dx / length * distance,
344        from.y - dy / length * distance,
345    )
346}
347
348fn segment_quad(start: Point, end: Point, half: f64) -> Vec<Point> {
349    let dx = end.x - start.x;
350    let dy = end.y - start.y;
351    let length = (dx * dx + dy * dy).sqrt();
352    if length <= 1e-12 {
353        return Vec::new();
354    }
355    let nx = -dy / length * half;
356    let ny = dx / length * half;
357    vec![
358        Point::new(start.x + nx, start.y + ny),
359        Point::new(end.x + nx, end.y + ny),
360        Point::new(end.x - nx, end.y - ny),
361        Point::new(start.x - nx, start.y - ny),
362    ]
363}
364
365/// A polygon approximating a disc.
366pub fn circle(center: Point, radius: f64) -> Vec<Point> {
367    const SEGMENTS: usize = 16;
368    let mut points = Vec::with_capacity(SEGMENTS);
369    for step in 0..SEGMENTS {
370        let angle = step as f64 / SEGMENTS as f64 * std::f64::consts::TAU;
371        points.push(Point::new(
372            center.x + radius * angle.cos(),
373            center.y + radius * angle.sin(),
374        ));
375    }
376    points
377}
378
379/// Reverse a polygon when it is wound clockwise, so unions behave under the
380/// non-zero rule.
381fn oriented(mut polygon: Vec<Point>) -> Vec<Point> {
382    let area = signed_area(&polygon);
383    if area < 0.0 {
384        polygon.reverse();
385    }
386    polygon
387}
388
389fn signed_area(polygon: &[Point]) -> f64 {
390    let mut sum = 0.0;
391    for index in 0..polygon.len() {
392        let current = polygon[index];
393        let next = polygon[(index + 1) % polygon.len()];
394        sum += current.x * next.y - next.x * current.y;
395    }
396    sum / 2.0
397}
398
399#[cfg(test)]
400mod tests {
401    use super::{dash_polyline, stroke_outline, Cap, Dash, Path};
402    use crate::geom::{Matrix, Point};
403
404    #[test]
405    fn rectangles_flatten_to_closed_polylines() {
406        let mut path = Path::new();
407        path.add_rect(0.0, 0.0, 10.0, 20.0);
408        let polylines = path.flatten(Matrix::IDENTITY);
409        assert_eq!(polylines.len(), 1);
410        assert_eq!(polylines[0].len(), 5, "four corners plus the closing point");
411        assert_eq!(polylines[0][0], Point::new(0.0, 0.0));
412        assert_eq!(polylines[0][2], Point::new(10.0, 20.0));
413    }
414
415    #[test]
416    fn curves_are_subdivided() {
417        let mut path = Path::new();
418        path.move_to(Point::new(0.0, 0.0));
419        path.curve_to(
420            Point::new(0.0, 10.0),
421            Point::new(10.0, 10.0),
422            Point::new(10.0, 0.0),
423        );
424        let polylines = path.flatten(Matrix::IDENTITY);
425        assert_eq!(polylines[0].len(), 25);
426        assert_eq!(*polylines[0].last().expect("end"), Point::new(10.0, 0.0));
427    }
428
429    #[test]
430    fn a_solid_dash_keeps_the_polyline() {
431        let line = vec![Point::new(0.0, 0.0), Point::new(10.0, 0.0)];
432        let runs = dash_polyline(&line, &Dash::solid(), 1.0);
433        assert_eq!(runs.len(), 1);
434        assert_eq!(runs[0], line);
435    }
436
437    #[test]
438    fn a_dash_pattern_splits_the_line() {
439        let line = vec![Point::new(0.0, 0.0), Point::new(20.0, 0.0)];
440        let dash = Dash {
441            pattern: vec![5.0, 5.0],
442            phase: 0.0,
443        };
444        let runs = dash_polyline(&line, &dash, 1.0);
445        assert_eq!(runs.len(), 2);
446        assert_eq!(runs[0], vec![Point::new(0.0, 0.0), Point::new(5.0, 0.0)]);
447        assert_eq!(runs[1], vec![Point::new(10.0, 0.0), Point::new(15.0, 0.0)]);
448    }
449
450    #[test]
451    fn a_phase_offsets_the_first_run() {
452        let line = vec![Point::new(0.0, 0.0), Point::new(20.0, 0.0)];
453        let dash = Dash {
454            pattern: vec![5.0, 5.0],
455            phase: 2.0,
456        };
457        let runs = dash_polyline(&line, &dash, 1.0);
458        assert_eq!(runs[0][0], Point::new(0.0, 0.0));
459        assert_eq!(runs[0][1], Point::new(3.0, 0.0));
460    }
461
462    #[test]
463    fn strokes_become_polygons_around_the_line() {
464        let line = vec![Point::new(10.0, 10.0), Point::new(30.0, 10.0)];
465        let polygons = stroke_outline(&[line], 4.0, Cap::Butt);
466        assert!(!polygons.is_empty());
467        // Every polygon is wound counter-clockwise after orientation.
468        for polygon in &polygons {
469            assert!(super::signed_area(polygon) >= 0.0);
470        }
471        // The quad around the segment spans y from 8 to 12.
472        let quad = &polygons[0];
473        let min_y = quad.iter().fold(f64::MAX, |min, point| min.min(point.y));
474        let max_y = quad.iter().fold(f64::MIN, |max, point| max.max(point.y));
475        assert!((min_y - 8.0).abs() < 1e-9, "{min_y}");
476        assert!((max_y - 12.0).abs() < 1e-9, "{max_y}");
477    }
478}