vello_common/
flatten.rs

1// Copyright 2025 the Vello Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! Flattening filled and stroked paths.
5
6use crate::flatten_simd::{Callback, LinePathEl};
7use crate::geometry::RectU16;
8use crate::kurbo::{self, Affine, PathEl, Stroke, StrokeCtx, StrokeOpts};
9use alloc::vec::Vec;
10use fearless_simd::{Level, Simd, dispatch};
11use log::warn;
12
13pub use crate::flatten_simd::FlattenCtx;
14
15// The current tolerance is set to 0.25. Since `sqrt` doesn't work in const contexts, we instead
16// hardcode the squared tolerance and derive the others from that.
17pub(crate) const SQRT_TOL: f64 = 0.5;
18pub(crate) const TOL: f64 = SQRT_TOL * SQRT_TOL;
19pub(crate) const TOL_2: f64 = TOL * TOL;
20
21/// A point.
22#[derive(Clone, Copy, Debug, PartialEq)]
23pub struct Point {
24    /// The x coordinate of the point.
25    pub x: f32,
26    /// The y coordinate of the point.
27    pub y: f32,
28}
29
30impl Point {
31    /// The point `(0, 0)`.
32    pub const ZERO: Self = Self::new(0., 0.);
33
34    /// Create a new point.
35    pub const fn new(x: f32, y: f32) -> Self {
36        Self { x, y }
37    }
38}
39
40impl From<kurbo::Point> for Point {
41    #[inline(always)]
42    fn from(value: kurbo::Point) -> Self {
43        Self {
44            x: value.x as f32,
45            y: value.y as f32,
46        }
47    }
48}
49
50impl core::ops::Add for Point {
51    type Output = Self;
52
53    fn add(self, rhs: Self) -> Self {
54        Self::new(self.x + rhs.x, self.y + rhs.y)
55    }
56}
57
58impl core::ops::Sub for Point {
59    type Output = Self;
60
61    fn sub(self, rhs: Self) -> Self {
62        Self::new(self.x - rhs.x, self.y - rhs.y)
63    }
64}
65
66impl core::ops::Mul<f32> for Point {
67    type Output = Self;
68
69    fn mul(self, rhs: f32) -> Self {
70        Self::new(self.x * rhs, self.y * rhs)
71    }
72}
73
74/// A line.
75#[derive(Clone, Copy, Debug)]
76pub struct Line {
77    /// The start point of the line.
78    pub p0: Point,
79    /// The end point of the line.
80    pub p1: Point,
81}
82
83impl Line {
84    /// Create a new line.
85    pub fn new(p0: Point, p1: Point) -> Self {
86        Self { p0, p1 }
87    }
88}
89
90/// Flatten a filled Bézier path into line segments.
91///
92/// # Open subpaths and culling
93///
94/// Open subpaths in the input path get closed by connecting the last endpoint in the subpath to
95/// the starting point. The output lines in `line_buf` describe the flattened path, but these lines
96/// may describe open subpaths, as some path elements may have been culled.
97///
98/// For example, consider the following, where the box describes the viewport, a path is marked by
99/// `*`, and the region to be filled in the viewport is shaded. For ease of drawing the ASCII art,
100/// the path elements are all lines ([`PathEl::LineTo`]), but the same also holds for Bézier path
101/// elements.
102///
103/// ```text
104///    ---> winding scan direction
105///
106///                   * * * * *
107///                 *         *
108///    ---------- * -----     *
109///    |        *░░░░░░░|     *
110///    |      *░░░░░░░░░|     *
111///    |    *░░░░░░░░░░░|     *
112///    |  *░░░░░░░░░░░░░|     *
113///    |*░░░░░░░░░░░░░░░|     *
114///   *|░░░░░░░░░░░░░░░░|     *
115/// *  |░░░░░░░░░░░░░░░░|     *
116/// *  |░░░░░░░░░░░░░░░░|     *
117/// *  ------------------     *
118/// *                         *
119/// *                         *
120/// *                         *
121/// *                         *
122/// *                         *
123/// *                         *
124/// *                         *
125/// * * * * * * * * * * * * * *
126/// ```
127///
128/// Because the winding scan direction is from left to right, only the left-of-viewport and
129/// diagonal lines matter in later stages of rendering for the winding number and pixel coverage.
130/// The other three lines can be culled.
131///
132/// ```text
133///                   *
134///                 *
135///    ---------- * -----
136///    |        *░░░░░░░|
137///    |      *░░░░░░░░░|
138///    |    *░░░░░░░░░░░|
139///    |  *░░░░░░░░░░░░░|
140///    |*░░░░░░░░░░░░░░░|
141///   *|░░░░░░░░░░░░░░░░|
142/// *  |░░░░░░░░░░░░░░░░|
143/// *  |░░░░░░░░░░░░░░░░|
144/// *  ------------------
145/// *
146/// *
147/// *
148/// *
149/// *
150/// *
151/// *
152/// ```
153///
154/// It is important to keep these flattened subpaths open after culling, as closing the subpaths
155/// might yield different geometry like the following.
156///
157/// ```text
158///                   *
159///                 **
160///    ---------- * *----
161///    |        *░░*    |
162///    |      *░░░*     |
163///    |    *░░░░*      |
164///    |  *░░░░░*       |
165///    |*░░░░░░*        |
166///   *|░░░░░░*         |
167/// *  |░░░░░*          |
168/// *  |░░░░*           |
169/// *  --- * ------------
170/// *     *
171/// *    *
172/// *   *
173/// *  *
174/// * *
175/// **
176/// *
177/// ```
178pub fn fill(
179    level: Level,
180    path: impl IntoIterator<Item = PathEl>,
181    affine: Affine,
182    line_buf: &mut Vec<Line>,
183    ctx: &mut FlattenCtx,
184    cull_bbox: RectU16,
185) {
186    dispatch!(level, simd => fill_impl(simd, path, affine, line_buf, ctx, cull_bbox));
187}
188
189/// Flatten a filled bezier path into line segments.
190///
191/// See the note about open subpaths and culling on [`fill`].
192#[inline(always)]
193pub fn fill_impl<S: Simd>(
194    simd: S,
195    path: impl IntoIterator<Item = PathEl>,
196    affine: Affine,
197    line_buf: &mut Vec<Line>,
198    flatten_ctx: &mut FlattenCtx,
199    cull_bbox: RectU16,
200) {
201    line_buf.clear();
202    let mut lb = FlattenerCallback {
203        line_buf,
204        start: Point::ZERO,
205        p0: Point::ZERO,
206        is_nan: false,
207    };
208
209    crate::flatten_simd::flatten(simd, path, affine, &mut lb, flatten_ctx, cull_bbox);
210
211    // A path that contains NaN is ill-defined, so ignore it.
212    if lb.is_nan {
213        warn!("A path contains NaN, ignoring it.");
214
215        line_buf.clear();
216    }
217}
218/// Flatten a stroked Bézier path into line segments.
219///
220/// See the note about open subpaths and culling on [`fill`].
221pub fn stroke(
222    level: Level,
223    path: impl IntoIterator<Item = PathEl>,
224    style: &Stroke,
225    affine: Affine,
226    line_buf: &mut Vec<Line>,
227    flatten_ctx: &mut FlattenCtx,
228    stroke_ctx: &mut StrokeCtx,
229    cull_bbox: RectU16,
230) {
231    // TODO: Temporary hack to ensure that strokes are scaled properly by the transform.
232    let tolerance = TOL
233        / affine.as_coeffs()[0]
234            .abs()
235            .max(affine.as_coeffs()[3].abs())
236            .max(1.);
237
238    expand_stroke(path, style, tolerance, stroke_ctx);
239    fill(
240        level,
241        stroke_ctx.output(),
242        affine,
243        line_buf,
244        flatten_ctx,
245        cull_bbox,
246    );
247}
248
249/// Expand a stroked path to a filled path.
250pub fn expand_stroke(
251    path: impl IntoIterator<Item = PathEl>,
252    style: &Stroke,
253    tolerance: f64,
254    stroke_ctx: &mut StrokeCtx,
255) {
256    kurbo::stroke_with(path, style, &StrokeOpts::default(), tolerance, stroke_ctx);
257}
258
259struct FlattenerCallback<'a> {
260    line_buf: &'a mut Vec<Line>,
261    start: Point,
262    p0: Point,
263    is_nan: bool,
264}
265
266impl Callback for FlattenerCallback<'_> {
267    #[inline(always)]
268    fn callback(&mut self, el: LinePathEl) {
269        match el {
270            LinePathEl::MoveTo(p) => {
271                self.is_nan |= p.is_nan();
272
273                let p = p.into();
274                self.start = p;
275                self.p0 = p;
276            }
277            LinePathEl::LineTo(p) => {
278                self.is_nan |= p.is_nan();
279
280                let p = p.into();
281                self.line_buf.push(Line::new(self.p0, p));
282                self.p0 = p;
283            }
284        }
285    }
286}
vello_common/flatten.rs

vello_common/
flatten.rs
