sequoia_draw/
raster.rs

1use sequoia_core::{Point, Rect};
2
3use crate::flatten::Contour;
4use crate::path::{FillRule, Path};
5use crate::{DEFAULT_OPTIONS, Span, union_rect};
6
7#[derive(Clone, Copy, Debug, PartialEq)]
8pub struct RasterOptions {
9    pub tolerance: f32,
10
11    pub row_height: f32,
12
13    pub merge_tol: f32,
14
15    pub aa_samples: u32,
16
17    pub analytic: bool,
18
19    /// Split large rasters across worker threads. Small shapes always stay on
20    /// the calling thread, so this only matters for big fills and strokes.
21    pub parallel: bool,
22}
23
24impl Default for RasterOptions {
25    fn default() -> Self {
26        DEFAULT_OPTIONS
27    }
28}
29
30impl RasterOptions {
31    pub const SMOOTH: Self = Self {
32        tolerance: crate::TOLERANCE,
33        row_height: 1.0,
34        merge_tol: 0.35,
35        aa_samples: 4,
36        analytic: true,
37        parallel: true,
38    };
39
40    pub const CRISP: Self = Self {
41        tolerance: crate::TOLERANCE,
42        row_height: 1.0,
43        merge_tol: 0.35,
44        aa_samples: 1,
45        analytic: true,
46        parallel: true,
47    };
48
49    pub const BANDED: Self = Self {
50        tolerance: crate::TOLERANCE,
51        row_height: 1.0,
52        merge_tol: 0.35,
53        aa_samples: 4,
54        analytic: false,
55        parallel: true,
56    };
57
58    pub fn tolerance(mut self, tolerance: f32) -> Self {
59        self.tolerance = tolerance;
60        self
61    }
62
63    pub fn row_height(mut self, row_height: f32) -> Self {
64        self.row_height = row_height;
65        self
66    }
67
68    pub fn merge_tol(mut self, merge_tol: f32) -> Self {
69        self.merge_tol = merge_tol;
70        self
71    }
72
73    pub fn aa_samples(mut self, samples: u32) -> Self {
74        self.aa_samples = samples.clamp(1, 64);
75        self
76    }
77
78    pub fn analytic(mut self, analytic: bool) -> Self {
79        self.analytic = analytic;
80        self
81    }
82
83    /// Enables or disables band-parallel tessellation of large rasters.
84    ///
85    /// Useful on single-core hosts and when a caller needs repeatable span
86    /// order.
87    pub fn parallel(mut self, parallel: bool) -> Self {
88        self.parallel = parallel;
89        self
90    }
91
92    pub fn for_scale(mut self, scale: f32) -> Self {
93        let s = if scale.is_finite() && scale > 0.0 {
94            scale
95        } else {
96            1.0
97        };
98        self.tolerance = (crate::TOLERANCE / s).max(0.05);
99        self.row_height = (1.0 / s).max(1.0 / 8.0);
100        self.merge_tol = (0.35 / s).max(0.02);
101        self
102    }
103}
104
105#[derive(Clone, Copy, Debug, PartialEq)]
106pub struct FillStyle {
107    pub rule: FillRule,
108
109    pub opts: RasterOptions,
110}
111
112impl Default for FillStyle {
113    fn default() -> Self {
114        Self {
115            rule: FillRule::NonZero,
116            opts: RasterOptions::default(),
117        }
118    }
119}
120
121impl FillStyle {
122    pub fn new(rule: FillRule, opts: RasterOptions) -> Self {
123        Self { rule, opts }
124    }
125
126    pub fn with_rule(rule: FillRule) -> Self {
127        Self {
128            rule,
129            opts: RasterOptions::default(),
130        }
131    }
132
133    #[must_use]
134    pub fn with_opts(mut self, opts: RasterOptions) -> Self {
135        self.opts = opts;
136        self
137    }
138}
139
140#[derive(Clone, Copy)]
141struct Edge {
142    x0: f32,
143    y0: f32,
144    x1: f32,
145    y1: f32,
146
147    dir: i32,
148}
149
150#[derive(Clone, Copy, Debug)]
151struct Run {
152    x0: f32,
153    x1: f32,
154    y0: f32,
155    y1: f32,
156
157    alpha: f32,
158    claimed: bool,
159}
160
161pub fn fill_styled(path: &Path, style: FillStyle, out: &mut Vec<Span>) -> Rect {
162    fill(path, style.rule, style.opts, out)
163}
164
165pub fn fill(path: &Path, rule: FillRule, opts: RasterOptions, out: &mut Vec<Span>) -> Rect {
166    if opts.analytic {
167        if let Some(rect) = path.as_rect() {
168            if rect.is_empty() {
169                return Rect::ZERO;
170            }
171            out.push(Span::rect(rect));
172            return rect;
173        }
174        if let Some((rect, radius)) = path.as_rounded_rect() {
175            if rect.is_empty() {
176                return Rect::ZERO;
177            }
178            out.push(Span::rounded(rect, radius));
179            return rect;
180        }
181        if let Some((center, radius)) = path.as_circle() {
182            if radius <= 0.0 {
183                return Rect::ZERO;
184            }
185            let rect = Rect::from_xywh(
186                center.x - radius,
187                center.y - radius,
188                radius * 2.0,
189                radius * 2.0,
190            );
191            out.push(Span::rounded(rect, radius));
192            return rect;
193        }
194    }
195
196    let contours = path.contours(opts.tolerance);
197    fill_contours(&contours, rule, opts, out)
198}
199
200pub fn fill_contours(
201    contours: &[Contour],
202    rule: FillRule,
203    opts: RasterOptions,
204    out: &mut Vec<Span>,
205) -> Rect {
206    let edges = collect_edges(contours);
207    if edges.is_empty() {
208        return Rect::ZERO;
209    }
210
211    let cell = opts.row_height.clamp(0.05, 16.0);
212    let samples = opts.aa_samples.clamp(1, 64) as usize;
213    let merge_tol = opts.merge_tol.max(0.0);
214
215    let mut top = f32::INFINITY;
216    let mut bottom = f32::NEG_INFINITY;
217    let mut left = f32::INFINITY;
218    let mut right = f32::NEG_INFINITY;
219    for e in &edges {
220        top = top.min(e.y0.min(e.y1));
221        bottom = bottom.max(e.y0.max(e.y1));
222        left = left.min(e.x0.min(e.x1));
223        right = right.max(e.x0.max(e.x1));
224    }
225    if !top.is_finite() || !bottom.is_finite() || bottom <= top {
226        return Rect::ZERO;
227    }
228    if !left.is_finite() || !right.is_finite() || right <= left {
229        return Rect::ZERO;
230    }
231
232    let first_row = (top / cell).floor();
233    let last_row = (bottom / cell).ceil();
234    let first_col = (left / cell).floor();
235    let last_col = (right / cell).ceil();
236    let cols = (last_col - first_col).max(0.0) as usize;
237    if cols == 0 {
238        return Rect::ZERO;
239    }
240    let rows = ((last_row - first_row).max(0.0).ceil() as usize) + 1;
241
242    // Large rasters dominate a frame, so they are split into row bands and
243    // tessellated on worker threads. UI-sized shapes stay on the calling
244    // thread: spawning threads would cost more than the raster itself.
245    let bands = if opts.parallel {
246        let cores = std::thread::available_parallelism()
247            .map(|n| n.get())
248            .unwrap_or(1);
249        band_count(rows, cols, samples, cores)
250    } else {
251        1
252    };
253
254    if bands <= 1 {
255        return raster_rows(
256            &edges, rule, cell, samples, merge_tol, first_row, first_col, cols, 0, rows, out,
257        );
258    }
259
260    let band_rows = rows.div_ceil(bands);
261    let mut parts: Vec<(usize, Vec<Span>, Rect)> = Vec::with_capacity(bands);
262    std::thread::scope(|scope| {
263        let mut handles = Vec::with_capacity(bands);
264        for band in 0..bands {
265            let start = (band * band_rows).min(rows);
266            let end = (start + band_rows).min(rows);
267            if start >= end {
268                continue;
269            }
270            let edges = &edges;
271            handles.push((
272                start,
273                scope.spawn(move || {
274                    let mut spans = Vec::new();
275                    let coverage = raster_rows(
276                        edges, rule, cell, samples, merge_tol, first_row, first_col, cols, start,
277                        end, &mut spans,
278                    );
279                    (spans, coverage)
280                }),
281            ));
282        }
283        for (start, handle) in handles {
284            if let Ok((spans, coverage)) = handle.join() {
285                parts.push((start, spans, coverage));
286            }
287        }
288    });
289    // Bands run in parallel but spans must stay ordered by row for the
290    // renderer's batching and for stable output.
291    parts.sort_by_key(|(start, _, _)| *start);
292
293    let mut coverage = Rect::ZERO;
294    for (_, spans, part_coverage) in parts {
295        out.extend(spans);
296        coverage = union_rect(coverage, part_coverage);
297    }
298    coverage
299}
300
301const PARALLEL_MIN_ROWS: usize = 64;
302
303/// Parallel floor in raster *work* units: cells times anti-aliasing samples.
304///
305/// The old floor was 256k cells regardless of sample count, so a one-sample
306/// `CRISP` fill spawned threads for a quarter of the work a four-sample fill
307/// needed. Keeping the floor in work units makes the decision follow the
308/// actual per-cell cost.
309const PARALLEL_MIN_WORK: usize = 256 * 1024 * 4;
310
311const MAX_BANDS: usize = 8;
312
313/// Number of row bands to split a raster into.
314///
315/// `cores` is passed in so the decision can be tested without asking the
316/// process how many CPUs it has.
317fn band_count(rows: usize, cols: usize, samples: usize, cores: usize) -> usize {
318    let work = rows.saturating_mul(cols).saturating_mul(samples.max(1));
319    if rows < PARALLEL_MIN_ROWS || work < PARALLEL_MIN_WORK {
320        return 1;
321    }
322    cores.min(MAX_BANDS).min(rows / PARALLEL_MIN_ROWS).max(1)
323}
324
325#[allow(clippy::too_many_arguments)]
326fn raster_rows(
327    edges: &[Edge],
328    rule: FillRule,
329    cell: f32,
330    samples: usize,
331    merge_tol: f32,
332    first_row: f32,
333    first_col: f32,
334    cols: usize,
335    row_start: usize,
336    row_end: usize,
337    out: &mut Vec<Span>,
338) -> Rect {
339    let mut coverage_per_cell = vec![0.0f32; cols];
340    let mut crossings: Vec<(f32, i32)> = Vec::new();
341    let mut spans: Vec<(f32, f32)> = Vec::new();
342    let mut row_runs: Vec<(f32, f32, f32)> = Vec::new();
343    let mut emitted: Vec<Run> = Vec::new();
344    let mut runs: Vec<Run> = Vec::new();
345    let mut coverage = Rect::ZERO;
346    let inv_samples = 1.0 / samples as f32;
347
348    for row_index in row_start..row_end {
349        let y0 = (first_row + row_index as f32) * cell;
350        let y1 = y0 + cell;
351        coverage_per_cell.fill(0.0);
352
353        for sample in 0..samples {
354            let y = y0 + (sample as f32 + 0.5) * inv_samples * cell;
355            crossings.clear();
356            for e in edges {
357                let (ymin, ymax) = (e.y0.min(e.y1), e.y0.max(e.y1));
358                if y < ymin || y >= ymax {
359                    continue;
360                }
361                let t = (y - e.y0) / (e.y1 - e.y0);
362                crossings.push((e.x0 + (e.x1 - e.x0) * t, e.dir));
363            }
364            if crossings.len() < 2 {
365                continue;
366            }
367            crossings.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
368
369            spans.clear();
370            match rule {
371                FillRule::NonZero => {
372                    let mut winding = 0;
373                    let mut start = 0.0;
374                    for &(x, dir) in &crossings {
375                        let was = winding;
376                        winding += dir;
377                        if was == 0 && winding != 0 {
378                            start = x;
379                        } else if was != 0 && winding == 0 {
380                            spans.push((start, x));
381                        }
382                    }
383                }
384                FillRule::EvenOdd => {
385                    let mut i = 0;
386                    while i + 1 < crossings.len() {
387                        spans.push((crossings[i].0, crossings[i + 1].0));
388                        i += 2;
389                    }
390                }
391            }
392
393            for &(x0, x1) in &spans {
394                add_span_coverage(&mut coverage_per_cell, first_col, cell, x0, x1);
395            }
396        }
397
398        row_runs.clear();
399        let mut i = 0usize;
400        while i < cols {
401            let a = coverage_per_cell[i] * inv_samples;
402            if a <= 0.0 {
403                i += 1;
404                continue;
405            }
406            let alpha = quantize_alpha(a);
407            let start = i;
408            i += 1;
409            while i < cols {
410                let b = coverage_per_cell[i] * inv_samples;
411                if b <= 0.0 || quantize_alpha(b) != alpha {
412                    break;
413                }
414                i += 1;
415            }
416            row_runs.push((
417                (first_col + start as f32) * cell,
418                (first_col + i as f32) * cell,
419                alpha,
420            ));
421        }
422
423        for run in runs.iter_mut() {
424            run.claimed = false;
425        }
426        for (x0, x1, alpha) in row_runs.drain(..) {
427            let mut extended = false;
428            for run in runs.iter_mut() {
429                if run.claimed || run.alpha != alpha {
430                    continue;
431                }
432                if (run.x0 - x0).abs() <= merge_tol && (run.x1 - x1).abs() <= merge_tol {
433                    run.x0 = run.x0.min(x0);
434                    run.x1 = run.x1.max(x1);
435                    run.y1 = y1;
436                    run.claimed = true;
437                    extended = true;
438                    break;
439                }
440            }
441            if !extended {
442                runs.push(Run {
443                    x0,
444                    x1,
445                    y0,
446                    y1,
447                    alpha,
448                    claimed: true,
449                });
450            }
451        }
452
453        emitted.clear();
454        runs.retain_mut(|run| {
455            if run.claimed {
456                run.claimed = false;
457                true
458            } else {
459                emitted.push(*run);
460                false
461            }
462        });
463        for run in emitted.drain(..) {
464            coverage = union_rect(coverage, emit_run(run, out));
465        }
466    }
467    for run in runs.drain(..) {
468        coverage = union_rect(coverage, emit_run(run, out));
469    }
470    coverage
471}
472
473fn add_span_coverage(coverage: &mut [f32], first_col: f32, cell: f32, x0: f32, x1: f32) {
474    if x1 <= x0 {
475        return;
476    }
477    let start = ((x0 / cell).floor() - first_col).max(0.0) as usize;
478    let end = (((x1 / cell).ceil() - first_col).max(0.0) as usize).min(coverage.len());
479    for (i, cell_cov) in coverage[start..end].iter_mut().enumerate() {
480        let cell_left = (first_col + (start + i) as f32) * cell;
481        let lo = x0.max(cell_left);
482        let hi = x1.min(cell_left + cell);
483        if hi > lo {
484            *cell_cov += (hi - lo) / cell;
485        }
486    }
487}
488
489fn quantize_alpha(a: f32) -> f32 {
490    // 64 levels keep curved edges smooth without exploding the number of
491    // distinct span alphas (and therefore GPU instances) on large paths.
492    const LEVELS: f32 = 64.0;
493    if a >= 1.0 {
494        1.0
495    } else if a <= 0.0 {
496        0.0
497    } else {
498        ((a * LEVELS).round().max(1.0) / LEVELS).min(1.0)
499    }
500}
501
502fn emit_run(run: Run, out: &mut Vec<Span>) -> Rect {
503    let rect = Rect::from_xywh(
504        run.x0,
505        run.y0,
506        (run.x1 - run.x0).max(0.0),
507        (run.y1 - run.y0).max(0.0),
508    );
509    if rect.is_empty() {
510        return Rect::ZERO;
511    }
512    out.push(Span::rect(rect).with_alpha(run.alpha));
513    rect
514}
515
516fn collect_edges(contours: &[Contour]) -> Vec<Edge> {
517    let mut edges = Vec::new();
518    for contour in contours {
519        let pts = &contour.points;
520        if pts.len() < 2 {
521            continue;
522        }
523        let n = pts.len();
524        for i in 0..n {
525            let a = pts[i];
526            let b = pts[(i + 1) % n];
527            if a.y == b.y {
528                continue;
529            }
530            if a == b {
531                continue;
532            }
533            let dir = if b.y > a.y { 1 } else { -1 };
534            edges.push(Edge {
535                x0: a.x,
536                y0: a.y,
537                x1: b.x,
538                y1: b.y,
539                dir,
540            });
541        }
542    }
543    edges
544}
545
546pub(crate) fn contains(contours: &[Contour], p: Point, rule: FillRule) -> bool {
547    let edges = collect_edges(contours);
548    let mut winding = 0;
549    let mut crossings = 0;
550    for e in &edges {
551        let (ymin, ymax) = (e.y0.min(e.y1), e.y0.max(e.y1));
552        if p.y < ymin || p.y >= ymax {
553            continue;
554        }
555        let t = (p.y - e.y0) / (e.y1 - e.y0);
556        let x = e.x0 + (e.x1 - e.x0) * t;
557        if x > p.x {
558            winding += e.dir;
559            crossings += 1;
560        }
561    }
562    match rule {
563        FillRule::NonZero => winding != 0,
564        FillRule::EvenOdd => crossings % 2 == 1,
565    }
566}
567
568#[cfg(test)]
569mod tests {
570    use super::{MAX_BANDS, band_count, quantize_alpha};
571
572    #[test]
573    fn band_count_follows_work_not_cells() {
574        assert_eq!(band_count(1000, 1000, 4, 4), 4);
575        assert_eq!(band_count(1000, 1000, 1, 4), 1, "1 sample = 1/4 work");
576        assert_eq!(band_count(1000, 1000, 8, 4), 4);
577    }
578
579    #[test]
580    fn band_count_keeps_small_and_single_core_shapes_serial() {
581        assert_eq!(band_count(32, 4000, 4, 8), 1, "too few rows");
582        assert_eq!(band_count(1000, 1000, 4, 1), 1, "single core");
583        assert_eq!(band_count(1000, 1000, 4, 64), MAX_BANDS);
584    }
585
586    #[test]
587    fn alpha_quantization_keeps_64_levels() {
588        assert_eq!(quantize_alpha(0.0), 0.0);
589        assert_eq!(quantize_alpha(1.0), 1.0);
590        assert!((quantize_alpha(0.51) - 33.0 / 64.0).abs() < f32::EPSILON);
591        assert!(quantize_alpha(0.01) > 0.0, "thin coverage must survive");
592    }
593}
sequoia_draw/raster.rs

sequoia_draw/
raster.rs
