alpha2_geometry/
far.rs

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

alpha2_geometry/
far.rs
