vello_common/
strip_generator.rs

1// Copyright 2025 the Vello Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! Abstraction for generating strips from paths.
5
6use crate::clip::{PathDataRef, intersect};
7use crate::fearless_simd::Level;
8use crate::flatten::{FlattenCtx, Line};
9use crate::geometry::RectU16;
10use crate::kurbo::{Affine, PathEl, Rect, Stroke};
11use crate::peniko::Fill;
12use crate::strip::Strip;
13use crate::tile::Tiles;
14use crate::{flatten, rect, strip};
15use alloc::vec::Vec;
16use peniko::kurbo::StrokeCtx;
17
18/// A storage for storing strip-related data.
19#[derive(Debug, Default, PartialEq, Eq)]
20pub struct StripStorage {
21    /// The strips in the storage.
22    pub strips: Vec<Strip>,
23    /// The alphas in the storage.
24    pub alphas: Vec<u8>,
25    generation_mode: GenerationMode,
26}
27
28/// The generation mode of the strip storage.
29#[derive(Debug, Default, Copy, Clone, PartialEq, Eq)]
30pub enum GenerationMode {
31    #[default]
32    /// Clear strips before generating the new ones.
33    Replace,
34    /// Don't clear strips, append to the existing buffer.
35    Append,
36    /// Truncate strips to the given index before generating new ones,
37    /// preserving strips in `[0..n]`.
38    ReplaceAfter(usize),
39}
40
41impl StripStorage {
42    /// Create a new strip storage with the given generation mode.
43    pub fn new(generation_mode: GenerationMode) -> Self {
44        Self {
45            strips: Vec::new(),
46            alphas: Vec::new(),
47            generation_mode,
48        }
49    }
50
51    /// Reset the storage.
52    pub fn clear(&mut self) {
53        self.strips.clear();
54        self.alphas.clear();
55    }
56
57    /// Get the current generation mode.
58    pub fn generation_mode(&self) -> GenerationMode {
59        self.generation_mode
60    }
61
62    /// Set the generation mode of the storage.
63    pub fn set_generation_mode(&mut self, mode: GenerationMode) {
64        self.generation_mode = mode;
65    }
66
67    /// Whether the strip storage is empty.
68    pub fn is_empty(&self) -> bool {
69        self.strips.is_empty() && self.alphas.is_empty()
70    }
71
72    /// Extend the current strip storage with the data from another storage.
73    pub fn extend(&mut self, other: &Self) {
74        self.strips.extend(&other.strips);
75        self.alphas.extend(&other.alphas);
76    }
77}
78
79/// An object for easily generating strips for a filled/stroked path.
80#[derive(Debug)]
81pub struct StripGenerator {
82    pub(crate) level: Level,
83    line_buf: Vec<Line>,
84    flatten_ctx: FlattenCtx,
85    stroke_ctx: StrokeCtx,
86    temp_storage: StripStorage,
87    tiles: Tiles,
88    width: u16,
89    height: u16,
90}
91
92impl StripGenerator {
93    /// Create a new strip generator.
94    pub fn new(width: u16, height: u16, level: Level) -> Self {
95        Self {
96            level,
97            line_buf: Vec::new(),
98            tiles: Tiles::new(level, width, height),
99            flatten_ctx: FlattenCtx::default(),
100            stroke_ctx: StrokeCtx::default(),
101            temp_storage: StripStorage::default(),
102            width,
103            height,
104        }
105    }
106
107    /// Get this strip generator's viewport width.
108    #[inline(always)]
109    pub fn width(&self) -> u16 {
110        self.width
111    }
112
113    /// Get this strip generator's viewport height.
114    #[inline(always)]
115    pub fn height(&self) -> u16 {
116        self.height
117    }
118
119    /// Generate the strips for a filled path.
120    pub fn generate_filled_path(
121        &mut self,
122        path: impl IntoIterator<Item = PathEl>,
123        fill_rule: Fill,
124        transform: Affine,
125        aliasing_threshold: Option<u8>,
126        strip_storage: &mut StripStorage,
127        clip_path: Option<PathDataRef<'_>>,
128    ) {
129        let cull_bbox = clip_path
130            .map(|clip_path| clip_path.bbox)
131            .unwrap_or(RectU16::new(0, 0, self.width, self.height));
132        flatten::fill(
133            self.level,
134            path,
135            transform,
136            &mut self.line_buf,
137            &mut self.flatten_ctx,
138            cull_bbox,
139        );
140
141        self.generate_with_clip(aliasing_threshold, strip_storage, fill_rule, clip_path);
142    }
143
144    /// Generate the strips for a stroked path.
145    pub fn generate_stroked_path(
146        &mut self,
147        path: impl IntoIterator<Item = PathEl>,
148        stroke: &Stroke,
149        transform: Affine,
150        aliasing_threshold: Option<u8>,
151        strip_storage: &mut StripStorage,
152        clip_path: Option<PathDataRef<'_>>,
153    ) {
154        let cull_bbox = clip_path
155            .map(|clip_path| clip_path.bbox)
156            .unwrap_or(RectU16::new(0, 0, self.width, self.height));
157        flatten::stroke(
158            self.level,
159            path,
160            stroke,
161            transform,
162            &mut self.line_buf,
163            &mut self.flatten_ctx,
164            &mut self.stroke_ctx,
165            cull_bbox,
166        );
167        self.generate_with_clip(aliasing_threshold, strip_storage, Fill::NonZero, clip_path);
168    }
169
170    fn generate_with_clip(
171        &mut self,
172        aliasing_threshold: Option<u8>,
173        strip_storage: &mut StripStorage,
174        fill_rule: Fill,
175        clip_path: Option<PathDataRef<'_>>,
176    ) {
177        self.tiles
178            .make_tiles_analytic_aa(self.level, &self.line_buf, self.width, self.height);
179
180        self.tiles.sort_tiles();
181
182        let level = self.level;
183        let tiles = &self.tiles;
184        let line_buf = &self.line_buf;
185        render_with_clip(
186            level,
187            &mut self.temp_storage,
188            strip_storage,
189            clip_path,
190            |strips, alphas| {
191                strip::render(
192                    level,
193                    tiles,
194                    strips,
195                    alphas,
196                    fill_rule,
197                    aliasing_threshold,
198                    line_buf,
199                );
200            },
201        );
202    }
203
204    /// Generate strips directly for a pixel-aligned rectangle.
205    ///
206    /// This bypasses the full path processing pipeline (flatten -> tiles -> strips)
207    /// by directly creating strip coverage data for the rectangle.
208    pub fn generate_filled_rect_fast(
209        &mut self,
210        rect: &Rect,
211        strip_storage: &mut StripStorage,
212        clip_path: Option<PathDataRef<'_>>,
213    ) {
214        let viewport = Rect::new(0.0, 0.0, self.width as f64, self.height as f64);
215        let clip_bbox = clip_path
216            .map(|clip| {
217                // Clip bbox is always guaranteed to be within viewport bounds, so no need to
218                // intersect again.
219                Rect::new(
220                    f64::from(clip.bbox.x0),
221                    f64::from(clip.bbox.y0),
222                    f64::from(clip.bbox.x1),
223                    f64::from(clip.bbox.y1),
224                )
225            })
226            .unwrap_or(viewport);
227        let clamped = rect.abs().intersect(clip_bbox);
228
229        let level = self.level;
230        render_with_clip(
231            level,
232            &mut self.temp_storage,
233            strip_storage,
234            clip_path,
235            |strips, alphas| {
236                rect::render(level, clamped, strips, alphas);
237            },
238        );
239    }
240
241    /// Reset the strip generator for a viewport size, resizing only when needed.
242    pub fn reset(&mut self, width: u16, height: u16) {
243        self.width = width;
244        self.height = height;
245        self.line_buf.clear();
246        self.tiles.reset(width, height);
247        self.temp_storage.clear();
248    }
249}
250
251/// Render strips via `render_fn` with optional clip intersection.
252///
253/// When `clip_path` is `Some`, strips are rendered into `temp_storage` first, then
254/// intersected with the clip mask into `strip_storage`. Otherwise strips are rendered
255/// directly into `strip_storage`.
256fn render_with_clip(
257    level: Level,
258    temp_storage: &mut StripStorage,
259    strip_storage: &mut StripStorage,
260    clip_path: Option<PathDataRef<'_>>,
261    render_fn: impl FnOnce(&mut Vec<Strip>, &mut Vec<u8>),
262) {
263    match strip_storage.generation_mode {
264        GenerationMode::Replace => strip_storage.strips.clear(),
265        GenerationMode::Append => {}
266        GenerationMode::ReplaceAfter(n) => strip_storage.strips.truncate(n),
267    }
268
269    if let Some(clip_path) = clip_path {
270        temp_storage.clear();
271
272        render_fn(&mut temp_storage.strips, &mut temp_storage.alphas);
273
274        let path_data = PathDataRef {
275            strips: &temp_storage.strips,
276            alphas: &temp_storage.alphas,
277            bbox: RectU16::new(0, 0, u16::MAX, u16::MAX),
278        };
279        intersect(level, clip_path, path_data, strip_storage);
280    } else {
281        render_fn(&mut strip_storage.strips, &mut strip_storage.alphas);
282    }
283}
284
285#[cfg(test)]
286mod tests {
287    use alloc::format;
288
289    use crate::fearless_simd::Level;
290    use crate::kurbo::{Affine, Rect, Shape};
291    use crate::peniko::Fill;
292    use crate::strip_generator::{StripGenerator, StripStorage};
293
294    #[test]
295    fn reset() {
296        let mut generator = StripGenerator::new(100, 100, Level::baseline());
297        let mut storage = StripStorage::default();
298        let rect = Rect::new(0.0, 0.0, 100.0, 100.0);
299
300        generator.generate_filled_path(
301            rect.to_path(0.1),
302            Fill::NonZero,
303            Affine::IDENTITY,
304            None,
305            &mut storage,
306            None,
307        );
308
309        assert!(!generator.line_buf.is_empty());
310        assert!(!storage.is_empty());
311
312        generator.reset(100, 100);
313        storage.clear();
314
315        assert!(generator.line_buf.is_empty());
316        assert!(storage.is_empty());
317    }
318
319    /// Assert that `generate_filled_rect_fast` produces the same strips as the
320    /// path-based pipeline for the given rectangle.
321    fn assert_rect_fast_eq_path(rect: Rect, test_name: &str) {
322        let mut generator = StripGenerator::new(100, 100, Level::baseline());
323        let mut storage_path = StripStorage::default();
324        let mut storage_rect = StripStorage::default();
325
326        generator.generate_filled_path(
327            rect.to_path(0.1),
328            Fill::NonZero,
329            Affine::IDENTITY,
330            None,
331            &mut storage_path,
332            None,
333        );
334        generator.reset(100, 100);
335
336        generator.generate_filled_rect_fast(&rect, &mut storage_rect, None);
337
338        assert_eq!(
339            storage_path.strips, storage_rect.strips,
340            "{test_name}: strips mismatch",
341        );
342        assert_eq!(
343            storage_path.alphas, storage_rect.alphas,
344            "{test_name}: alphas mismatch",
345        );
346    }
347
348    #[test]
349    fn rect_small_single_tile() {
350        assert_rect_fast_eq_path(Rect::new(1.0, 1.0, 3.0, 3.0), "small_single_tile");
351    }
352
353    #[test]
354    fn rect_spanning_multiple_tiles_horizontally() {
355        assert_rect_fast_eq_path(Rect::new(2.0, 1.0, 14.0, 3.0), "spanning_horizontal");
356    }
357
358    #[test]
359    fn rect_spanning_multiple_tiles_vertically() {
360        assert_rect_fast_eq_path(Rect::new(1.0, 2.0, 3.0, 14.0), "spanning_vertical");
361    }
362
363    #[test]
364    fn rect_spanning_multiple_tiles_both_directions() {
365        assert_rect_fast_eq_path(Rect::new(2.0, 2.0, 18.0, 18.0), "spanning_both");
366    }
367
368    #[test]
369    fn rect_tile_aligned() {
370        assert_rect_fast_eq_path(Rect::new(0.0, 0.0, 8.0, 8.0), "tile_aligned");
371    }
372
373    #[test]
374    fn rect_one_pixel_wide() {
375        assert_rect_fast_eq_path(Rect::new(5.0, 2.0, 6.0, 12.0), "one_pixel_wide");
376    }
377
378    #[test]
379    fn rect_one_pixel_tall() {
380        assert_rect_fast_eq_path(Rect::new(2.0, 5.0, 12.0, 6.0), "one_pixel_tall");
381    }
382
383    #[test]
384    fn rect_fractional_within_single_tile() {
385        let cases: &[(f64, f64, f64, f64)] = &[
386            (0.25, 0.75, 2.5, 3.5),
387            (1.2, 1.3, 1.8, 1.7),
388            (0.1, 0.1, 3.9, 3.9),
389            (2.5, 2.5, 2.6, 2.6),
390            (0.01, 0.99, 3.99, 3.01),
391        ];
392        for (i, &(x0, y0, x1, y1)) in cases.iter().enumerate() {
393            assert_rect_fast_eq_path(Rect::new(x0, y0, x1, y1), &format!("single_tile_{i}"));
394        }
395    }
396
397    #[test]
398    fn rect_fractional_multi_tile() {
399        let cases: &[(f64, f64, f64, f64)] = &[
400            (1.5, 2.3, 10.7, 8.9),
401            (0.5, 0.5, 8.5, 8.5),
402            (2.3, 5.1, 15.7, 5.9),
403            (5.1, 2.3, 5.9, 15.7),
404            (0.25, 0.25, 12.75, 12.75),
405            (1.0 / 3.0, 2.0 / 3.0, 10.33, 8.67),
406            (1.99, 2.01, 9.01, 7.99),
407            (3.9, 3.9, 8.1, 8.1),
408            (3.2, 6.3, 14.8, 6.7),
409            (6.3, 3.2, 6.7, 14.8),
410            (0.1, 0.9, 49.9, 49.1),
411            (4.0, 2.7, 12.0, 9.3),
412            (2.7, 4.0, 9.3, 12.0),
413            (1.5, 1.2, 10.5, 2.8),
414            (1.5, 2.5, 14.5, 18.5),
415            (0.7, 0.3, 30.2, 25.8),
416            (7.9, 7.9, 8.1, 8.1),
417            (3.5, 0.5, 4.5, 0.9),
418            (0.01, 0.01, 99.99, 99.99),
419            (10.0, 10.0, 10.1, 10.1),
420        ];
421        for (i, &(x0, y0, x1, y1)) in cases.iter().enumerate() {
422            assert_rect_fast_eq_path(Rect::new(x0, y0, x1, y1), &format!("multi_tile_{i}"));
423        }
424    }
425
426    #[test]
427    fn rect_fractional_exhaustive() {
428        for xi in 0..100_u32 {
429            for yi in 0..100_u32 {
430                let dx = xi as f64 * 0.01;
431                let dy = yi as f64 * 0.01;
432                let rect = Rect::new(dx, dy, 50.0 + dx, 50.0 + dy);
433                assert_rect_fast_eq_path(rect, &format!("exhaustive_{dx}_{dy}"));
434            }
435        }
436    }
437
438    #[test]
439    fn rect_inverted_both_axes() {
440        assert_rect_fast_eq_path(Rect::new(18.0, 18.0, 2.0, 2.0), "inverted_both_axes");
441    }
442}
vello_common/strip_generator.rs

vello_common/
strip_generator.rs
