vello_cpu/dispatch/multi_threaded/
cost.rs

1// Copyright 2025 the Vello Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4/// There is not much science behind this constant. It was instead determined by doing profiling
5/// and finding a constant that seems to strike a reasonable trade-off between not causing too
6/// big batch sizes
7pub(crate) const COST_THRESHOLD: f32 = 250.0;
8
9use crate::dispatch::multi_threaded::RenderTaskType;
10use crate::kurbo::{Affine, PathEl, PathSeg, Point, segments};
11
12/// Try to estimate the cost of the render task.
13pub(crate) fn estimate_render_task_cost(task: &RenderTaskType, paths: &[PathEl]) -> f32 {
14    const LAYER_COST: f32 = 10.0;
15
16    match task {
17        RenderTaskType::FillPath {
18            path_range,
19            transform,
20            ..
21        } => {
22            let path = &paths[path_range.start as usize..path_range.end as usize];
23            estimate_path_cost(segments(path.iter().copied()), *transform, false)
24        }
25        RenderTaskType::StrokePath {
26            path_range,
27            transform,
28            ..
29        } => {
30            let path = &paths[path_range.start as usize..path_range.end as usize];
31            estimate_path_cost(segments(path.iter().copied()), *transform, true)
32        }
33        RenderTaskType::PushLayer { clip_path, .. } => {
34            LAYER_COST
35                + clip_path
36                    .as_ref()
37                    .map(|(path_range, transform)| {
38                        let path = &paths[path_range.start as usize..path_range.end as usize];
39                        estimate_path_cost(segments(path.iter().copied()), *transform, false)
40                    })
41                    .unwrap_or(0.0)
42        }
43        RenderTaskType::PopLayer => LAYER_COST,
44    }
45}
46
47/// Try to estimate an (admittedly somewhat abstract) "path cost".
48///
49/// The main point here is that when sending paths to a thread to convert them into sparse strip
50/// representation, we might want to batch them. This is especially the case for small, line-only
51/// geometries, where handling each path separately would lead to a huge overhead.
52///
53/// Because of this, before rendering a path, we try to estimate a very rough cost based on
54/// the following attributes that (usually) have an impact on rendering times:
55///
56/// - Number of line segments (more line segments -> more work during strip rendering).
57/// - Number of curve segments (same as line segments, plus we need to flatten them first).
58/// - Path length (if the path is longer, the covered area is _likely_ to also be larger). However,
59///   the path length usually grows much faster than the render time, so we only apply a very small
60///   fractional value.
61/// - Strokes (if we are stroking a path, there is even more overhead for stroke expansion before doing
62///   flattening and strip rendering).
63pub(crate) fn estimate_path_cost(
64    path: impl IntoIterator<Item = PathSeg>,
65    transform: Affine,
66    is_stroke: bool,
67) -> f32 {
68    let cost_data = PathCostData::new(path, transform);
69
70    // Once again, those constants were not determined "scientifically" in any way, but
71    // are instead based on intuition as well as a number of experiments.
72    const CURVE_MULTIPLIER: f32 = 2.5;
73    const STROKE_MULTIPLIER: f32 = 1.5;
74
75    let mut cost = cost_data.num_line_segments as f32;
76    cost += cost_data.num_curve_segments as f32 * CURVE_MULTIPLIER;
77    cost += cost * (cost_data.path_length as f32 / 1024.0);
78
79    cost *= if is_stroke { STROKE_MULTIPLIER } else { 1.0 };
80    cost
81}
82
83struct PathCostData {
84    num_line_segments: u64,
85    num_curve_segments: u64,
86    path_length: f64,
87}
88
89impl PathCostData {
90    fn new(path: impl IntoIterator<Item = PathSeg>, transform: Affine) -> Self {
91        let mut num_line_segments = 0;
92        let mut num_curve_segments = 0;
93        let mut path_length = 0.0;
94
95        let mut register_path_length = |mut p0: Point, mut p1: Point| {
96            p0 = transform * p0;
97            p1 = transform * p1;
98            // We don't sqrt here because it's too expensive, we just want a rough estimate.
99            let dx = (p1.x - p0.x).abs();
100            let dy = (p1.y - p0.y).abs();
101            path_length += dx + dy;
102        };
103
104        for seg in path.into_iter() {
105            match seg {
106                PathSeg::Line(l) => {
107                    num_line_segments += 1;
108
109                    register_path_length(l.p0, l.p1);
110                }
111                PathSeg::Quad(q) => {
112                    num_curve_segments += 1;
113
114                    register_path_length(q.p0, q.p2);
115                }
116                PathSeg::Cubic(c) => {
117                    num_curve_segments += 1;
118
119                    register_path_length(c.p0, c.p3);
120                }
121            }
122        }
123
124        Self {
125            num_line_segments,
126            num_curve_segments,
127            path_length,
128        }
129    }
130}
vello_cpu/dispatch/multi_threaded/cost.rs

vello_cpu/dispatch/multi_threaded/
cost.rs
