alpha2_geometry/
far.rs

1//! Projection of paths that reach far past the canvas before rasterization.
2//!
3//! The rasterizer accumulates in `f32` relative to its clip, so coordinates around a million
4//! pixels lose the precision coverage needs. A path whose bounds exceed [`MAX_DEVICE`] has every
5//! point outside the canvas plus [`MARGIN`] clamped onto that rectangle. Clamping never moves a
6//! point across the rectangle's interior, so the winding number inside it is unchanged for every
7//! fill rule. Lines are split where they cross the rectangle's edge lines; curves are split until
8//! each piece is inside (kept), beyond one edge line (projected to a line), or below [`FLAT`].
9
10use kurbo::{BezPath, CubicBez, ParamCurve, PathEl, Point, QuadBez};
11
12/// How far past the canvas, in device pixels, a path may reach before it is projected.
13pub const MAX_DEVICE: f64 = 65_536.0;
14
15/// Distance of the projection rectangle from the canvas. Antialiasing reaches one pixel past an
16/// edge, and projected edges must not touch the canvas.
17const MARGIN: f64 = 64.0;
18
19/// A curve piece smaller than this, in device pixels, is drawn as a line.
20const FLAT: f64 = 1.0 / 64.0;
21
22const MAX_DEPTH: u32 = 64;
23
24/// `path` unchanged when it stays within [`MAX_DEVICE`] of a `width` by `height` canvas,
25/// otherwise projected onto the canvas plus a 64-pixel margin with every subpath closed. A
26/// non-finite coordinate yields an empty path.
27#[must_use]
28pub fn project_far(path: &BezPath, width: u32, height: u32) -> BezPath {
29    let bounds = kurbo::Shape::bounding_box(path);
30    let (w, h) = (f64::from(width), f64::from(height));
31    let finite = bounds.x0.is_finite()
32        && bounds.y0.is_finite()
33        && bounds.x1.is_finite()
34        && bounds.y1.is_finite();
35    if !finite {
36        return BezPath::new();
37    }
38    if bounds.x0 >= -MAX_DEVICE
39        && bounds.y0 >= -MAX_DEVICE
40        && bounds.x1 <= w + MAX_DEVICE
41        && bounds.y1 <= h + MAX_DEVICE
42    {
43        return path.clone();
44    }
45    let mut clip = Clip {
46        left: -MARGIN,
47        top: -MARGIN,
48        right: w + MARGIN,
49        bottom: h + MARGIN,
50        out: BezPath::new(),
51        at: Point::ZERO,
52        start: Point::ZERO,
53        open: false,
54    };
55    for element in path.elements() {
56        match *element {
57            PathEl::MoveTo(p) => {
58                clip.close();
59                clip.move_to(p);
60            }
61            PathEl::LineTo(p) => clip.line(p),
62            PathEl::QuadTo(p1, p2) => clip.quad(QuadBez::new(clip.at, p1, p2), 0),
63            PathEl::CurveTo(p1, p2, p3) => clip.cubic(CubicBez::new(clip.at, p1, p2, p3), 0),
64            PathEl::ClosePath => clip.close(),
65        }
66    }
67    clip.close();
68    clip.out
69}
70
71struct Clip {
72    left: f64,
73    top: f64,
74    right: f64,
75    bottom: f64,
76    out: BezPath,
77    at: Point,
78    start: Point,
79    open: bool,
80}
81
82enum Side {
83    Inside,
84    Outside,
85    Across,
86}
87
88impl Clip {
89    fn project(&self, p: Point) -> Point {
90        Point::new(
91            p.x.clamp(self.left, self.right),
92            p.y.clamp(self.top, self.bottom),
93        )
94    }
95
96    fn inside(&self, p: Point) -> bool {
97        (self.left..=self.right).contains(&p.x) && (self.top..=self.bottom).contains(&p.y)
98    }
99
100    fn move_to(&mut self, p: Point) {
101        let projected = self.project(p);
102        self.out.move_to(projected);
103        self.at = p;
104        self.start = p;
105        self.open = true;
106    }
107
108    fn line_to(&mut self, p: Point) {
109        if !self.open {
110            self.move_to(self.at);
111        }
112        let projected = self.project(p);
113        self.out.line_to(projected);
114        self.at = p;
115    }
116
117    /// Closes the subpath with a projected line back to its start.
118    fn close(&mut self) {
119        if self.open {
120            self.line(self.start);
121            self.out.close_path();
122            self.open = false;
123        }
124        self.at = self.start;
125    }
126
127    /// A line to `to`, split where it crosses the rectangle's edge lines.
128    fn line(&mut self, to: Point) {
129        let from = self.at;
130        let mut cuts = [0.0_f64; 4];
131        let mut count = 0;
132        for (a, b, edge) in [
133            (from.x, to.x, self.left),
134            (from.x, to.x, self.right),
135            (from.y, to.y, self.top),
136            (from.y, to.y, self.bottom),
137        ] {
138            if (a < edge) != (b < edge) {
139                let t = (edge - a) / (b - a);
140                if t > 0.0 && t < 1.0 {
141                    cuts[count] = t;
142                    count += 1;
143                }
144            }
145        }
146        let cuts = &mut cuts[..count];
147        cuts.sort_by(f64::total_cmp);
148        for t in cuts.iter() {
149            self.line_to(from.lerp(to, *t));
150        }
151        self.line_to(to);
152    }
153
154    /// Which region a curve's control points (and so its hull) lie in.
155    fn side(&self, points: &[Point]) -> Side {
156        if points.iter().all(|p| self.inside(*p)) {
157            Side::Inside
158        } else if points.iter().all(|p| p.x <= self.left)
159            || points.iter().all(|p| p.x >= self.right)
160            || points.iter().all(|p| p.y <= self.top)
161            || points.iter().all(|p| p.y >= self.bottom)
162        {
163            Side::Outside
164        } else {
165            Side::Across
166        }
167    }
168
169    fn small(points: &[Point]) -> bool {
170        let first = points[0];
171        points
172            .iter()
173            .all(|p| (p.x - first.x).abs() < FLAT && (p.y - first.y).abs() < FLAT)
174    }
175
176    fn quad(&mut self, quad: QuadBez, depth: u32) {
177        let points = [quad.p0, quad.p1, quad.p2];
178        match self.side(&points) {
179            Side::Inside => {
180                if !self.open {
181                    self.move_to(self.at);
182                }
183                self.out.quad_to(quad.p1, quad.p2);
184                self.at = quad.p2;
185            }
186            Side::Across if depth < MAX_DEPTH && !Self::small(&points) => {
187                let (a, b) = quad.subdivide();
188                self.quad(a, depth + 1);
189                self.quad(b, depth + 1);
190            }
191            Side::Outside | Side::Across => self.line(quad.p2),
192        }
193    }
194
195    fn cubic(&mut self, cubic: CubicBez, depth: u32) {
196        let points = [cubic.p0, cubic.p1, cubic.p2, cubic.p3];
197        match self.side(&points) {
198            Side::Inside => {
199                if !self.open {
200                    self.move_to(self.at);
201                }
202                self.out.curve_to(cubic.p1, cubic.p2, cubic.p3);
203                self.at = cubic.p3;
204            }
205            Side::Across if depth < MAX_DEPTH && !Self::small(&points) => {
206                let (a, b) = cubic.subdivide();
207                self.cubic(a, depth + 1);
208                self.cubic(b, depth + 1);
209            }
210            Side::Outside | Side::Across => self.line(cubic.p3),
211        }
212    }
213}
alpha2_geometry/far.rs

alpha2_geometry/
far.rs
