vello_cpu/coarse/
depth.rs

1// Copyright 2026 the Vello Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! CPU-based depth buffers.
5//!
6//! GPUs have depth buffers, so why not use them for CPU rendering as well! For many of the existing
7//! CPU-based 2D renderers, this is not really possible because they use immediate-mode rendering.
8//! But Vello CPU first converts all rendering commands into strips and then processes them, meaning
9//! that before we even start with rasterization, we already have a rough idea of what we are about
10//! to rasterize. Therefore, we can use this information to go about performing rasterization in a
11//! smarter way.
12//!
13//! Unlike GPUs, it is not feasible to have a per-pixel depth buffer. While certain per-pixel work
14//! can be expensive (images, gradients), what is even more expensive is splitting up work in a
15//! too granular fashion, especially when only dealing with solid colors. It is much faster to just
16//! fill a 256x1 buffer of pixels with a single colors than doing it in 32 chunks of 4x1, just to
17//! save 50% pixel work.
18//!
19//! Therefore, the CPU-based depth buffer acts at a much coarser granularity. Vertically, it comes
20//! very natural to simply decide that one depth buffer entry covers a range of [`Tile::HEIGHT`]
21//! pixels, since all commands are executed at this height anyway. Choosing a width is much trickier:
22//! Similarly, the width should be a multiple of [`Tile::WIDTH`], but using this as the granularity
23//! is still to narrow. After some empirical measurements, it was decided that a width of
24//! [`DEPTH_BUCKET_WIDTH`] overall represents a good compromise across different paint types.
25//!
26//! How this essentially works now is that, once we've collected all strips, we split them up
27//! into opaque fills aligned to the depth bucket width, and all other fills which either have
28//! transparency or stem from non-aligned parts of an opaque fill. During rasterization, we
29//! first render the opaque strips front-to-back, each time checking the depth buffer whether
30//! this hasn't already been filled by an opaque strip with a higher z-index. Otherwise, we
31//! perform the fill and update the depth buffer.
32//!
33//! Then, we simply render the remaining strips back to front, again always comparing the depth
34//! against what's written in the depth buffer and skipping any commands that would be fully
35//! covered by existing content.
36
37use crate::util::Span;
38use alloc::vec;
39use alloc::vec::Vec;
40use core::ops::Range;
41use vello_common::tile::Tile;
42
43pub(crate) const DEPTH_BUCKET_WIDTH: u16 = 128;
44const DEPTH_BUCKET_TILE_WIDTH: u16 = DEPTH_BUCKET_WIDTH / Tile::WIDTH;
45const _: () = assert!(
46    DEPTH_BUCKET_WIDTH.is_multiple_of(Tile::WIDTH),
47    "depth bucket width must be a multiple of tile width"
48);
49
50/// A horizontal range in depth-bucket coordinates.
51#[derive(Debug, Clone, Copy, PartialEq, Eq)]
52pub(crate) struct BucketRange {
53    pub(crate) start: u16,
54    pub(crate) end: u16,
55}
56
57impl BucketRange {
58    pub(crate) fn new(start: u16, end: u16) -> Self {
59        Self { start, end }
60    }
61
62    pub(crate) fn span(self) -> Span {
63        let x = self.start * DEPTH_BUCKET_WIDTH;
64        Span::new(x, (self.end - self.start) * DEPTH_BUCKET_WIDTH)
65    }
66}
67
68#[derive(Debug, Clone, Copy, PartialEq, Eq)]
69pub(crate) enum DepthSegment {
70    /// An opaque span that cannot be tracked in the depth buffer because it is not
71    /// aligned to whole depth buckets.
72    Regular(Span),
73    /// An opaque span that is aligned and can therefore be rendered front-to-back with
74    /// depth-buffer write enabled.
75    Opaque(BucketRange),
76}
77
78/// Splits a tile-aligned span into regular edge spans and a depth-trackable
79/// opaque middle span.
80pub(crate) fn split_opaque_span(span: Span, mut segment: impl FnMut(DepthSegment)) {
81    debug_assert!(
82        span.pixel_x().is_multiple_of(Tile::WIDTH) && span.pixel_end().is_multiple_of(Tile::WIDTH),
83        "`split_opaque_span` requires a tile-aligned span"
84    );
85
86    let x = span.tile_x();
87    let end = span.tile_end();
88    let aligned_x = x.next_multiple_of(DEPTH_BUCKET_TILE_WIDTH);
89    let aligned_end = (end / DEPTH_BUCKET_TILE_WIDTH) * DEPTH_BUCKET_TILE_WIDTH;
90
91    if aligned_x >= aligned_end {
92        segment(DepthSegment::Regular(span));
93
94        return;
95    }
96
97    if x < aligned_x {
98        segment(DepthSegment::Regular(Span::new_tile(x, aligned_x - x)));
99    }
100
101    if aligned_x < aligned_end {
102        segment(DepthSegment::Opaque(BucketRange::new(
103            aligned_x / DEPTH_BUCKET_TILE_WIDTH,
104            aligned_end / DEPTH_BUCKET_TILE_WIDTH,
105        )));
106    }
107
108    if aligned_end < end {
109        segment(DepthSegment::Regular(Span::new_tile(
110            aligned_end,
111            end - aligned_end,
112        )));
113    }
114}
115
116/// Coarse state for the depth buffer.
117#[derive(Debug, Clone, Copy, Default)]
118pub(crate) struct DepthState {
119    /// Coarse union of all depth-tracked opaque spans in this row.
120    bounds: Option<Span>,
121    /// Maximum draw ID of any depth-trackable opaque command in this row.
122    ///
123    /// Draw IDs start at 1, so 0 represents "no opaque command".
124    max_draw_id: u32,
125}
126
127impl DepthState {
128    pub(crate) fn reset(&mut self) {
129        *self = Self::default();
130    }
131
132    pub(crate) fn include_span(&mut self, span: Span, draw_id: u32) {
133        if let Some(bounds) = &mut self.bounds {
134            bounds.extend(span);
135        } else {
136            self.bounds = Some(span);
137        }
138
139        self.max_draw_id = self.max_draw_id.max(draw_id);
140    }
141
142    /// Returns whether this draw can skip consulting the depth buffer.
143    ///
144    /// This is the case in case there is no overlap between the span and the coarse span
145    /// of the current depth buffer.
146    pub(crate) fn can_skip(self, span: Span, draw_id: u32) -> bool {
147        if draw_id >= self.max_draw_id {
148            return true;
149        }
150
151        let Some(opaque_bounds) = self.bounds else {
152            return true;
153        };
154
155        let opaque_start = opaque_bounds.tile_x();
156        let opaque_end = opaque_bounds.tile_end();
157        let x = span.tile_x();
158        let end = span.tile_end();
159
160        x >= opaque_end || end <= opaque_start
161    }
162}
163
164#[derive(Debug)]
165pub(crate) struct DepthBuffer {
166    /// Stores the maximum draw ID for each depth bucket.
167    data: Vec<u32>,
168}
169
170impl DepthBuffer {
171    pub(crate) fn new(buffer_width: u16) -> Self {
172        Self {
173            data: vec![0; usize::from(buffer_width.div_ceil(DEPTH_BUCKET_WIDTH))],
174        }
175    }
176
177    /// Calls `f` for every subspan of `span` that is not covered by any entry in the
178    /// depth buffer.
179    pub(crate) fn for_each_unset_run(&self, span: Span, mut f: impl FnMut(Span)) {
180        let (mut idx, depth_end) = self.range(span);
181        while let Some((span, _)) = self.next_unset_run(&mut idx, depth_end, span) {
182            f(span);
183        }
184    }
185
186    /// Calls `f` for every bucket run in `bucket_range` that is not covered by any
187    /// entry in the depth buffer, and then marks the newly covered buckets in the
188    /// depth buffer.
189    pub(crate) fn for_each_unset_run_and_write(
190        &mut self,
191        bucket_range: BucketRange,
192        draw_id: u32,
193        mut f: impl FnMut(BucketRange),
194    ) {
195        let bounds = bucket_range.span();
196        let mut idx = usize::from(bucket_range.start);
197        let depth_end = usize::from(bucket_range.end);
198
199        while let Some((_, depth_range)) = self.next_unset_run(&mut idx, depth_end, bounds) {
200            let bucket_start =
201                u16::try_from(depth_range.start).expect("depth bucket range start overflow");
202            let bucket_end =
203                u16::try_from(depth_range.end).expect("depth bucket range end overflow");
204            f(BucketRange::new(bucket_start, bucket_end));
205            self.mark(depth_range, draw_id);
206        }
207    }
208
209    /// Calls `f` for every subspan of `span` that should be considered as visible assuming the
210    /// given draw ID.
211    pub(crate) fn for_each_visible_run(&self, span: Span, draw_id: u32, mut f: impl FnMut(Span)) {
212        let (mut idx, depth_end) = self.range(span);
213
214        while let Some(span) = self.next_visible_run(&mut idx, depth_end, draw_id, span) {
215            f(span);
216        }
217    }
218
219    /// Returns the depth-bucket index range touched by `span`.
220    fn range(&self, span: Span) -> (usize, usize) {
221        (
222            usize::from(span.pixel_x() / DEPTH_BUCKET_WIDTH),
223            usize::from(span.pixel_end().div_ceil(DEPTH_BUCKET_WIDTH)).min(self.data.len()),
224        )
225    }
226
227    pub(crate) fn clear(&mut self) {
228        self.data.fill(0);
229    }
230
231    fn mark(&mut self, range: Range<usize>, draw_id: u32) {
232        self.data[range].fill(draw_id);
233    }
234
235    /// Finds the next consecutive run of unset depth buckets.
236    fn next_unset_run(
237        &self,
238        idx: &mut usize,
239        end: usize,
240        bounds: Span,
241    ) -> Option<(Span, Range<usize>)> {
242        while *idx < end && self.data[*idx] != 0 {
243            *idx += 1;
244        }
245
246        let run_start = *idx;
247        while *idx < end && self.data[*idx] == 0 {
248            *idx += 1;
249        }
250
251        if run_start == *idx {
252            return None;
253        }
254
255        Some((
256            bucket_span(run_start, *idx).intersect(bounds)?,
257            run_start..*idx,
258        ))
259    }
260
261    /// Finds the next consecutive run visible to `draw_id`.
262    fn next_visible_run(
263        &self,
264        idx: &mut usize,
265        end: usize,
266        draw_id: u32,
267        bounds: Span,
268    ) -> Option<Span> {
269        while *idx < end && self.data[*idx] > draw_id {
270            *idx += 1;
271        }
272
273        let run_start = *idx;
274        while *idx < end && self.data[*idx] <= draw_id {
275            *idx += 1;
276        }
277
278        if run_start == *idx {
279            return None;
280        }
281
282        bucket_span(run_start, *idx).intersect(bounds)
283    }
284}
285
286fn bucket_span(start: usize, end: usize) -> Span {
287    let x = start as u16 * DEPTH_BUCKET_WIDTH;
288    Span::new(x, (end - start) as u16 * DEPTH_BUCKET_WIDTH)
289}
290
291#[cfg(test)]
292mod tests {
293    use super::*;
294    use alloc::vec::Vec;
295    use core::ops::Range;
296
297    fn buffer(bucket_count: usize) -> DepthBuffer {
298        DepthBuffer::new(bucket_count as u16 * DEPTH_BUCKET_WIDTH)
299    }
300
301    fn buckets(start: usize, end: usize) -> Span {
302        bucket_span(start, end)
303    }
304
305    fn bucket_range(span: Span) -> (usize, usize) {
306        (
307            usize::from(span.pixel_x() / DEPTH_BUCKET_WIDTH),
308            usize::from(span.pixel_end() / DEPTH_BUCKET_WIDTH),
309        )
310    }
311
312    fn visible_runs(buffer: &DepthBuffer, span: Span, draw_id: u32) -> Vec<(usize, usize)> {
313        let mut runs = Vec::new();
314        buffer.for_each_visible_run(span, draw_id, |span| {
315            runs.push(bucket_range(span));
316        });
317        runs
318    }
319
320    fn unset_runs(buffer: &DepthBuffer, span: Span) -> Vec<(usize, usize)> {
321        let mut runs = Vec::new();
322        buffer.for_each_unset_run(span, |span| {
323            runs.push(bucket_range(span));
324        });
325        runs
326    }
327
328    fn write_buckets(buffer: &mut DepthBuffer, range: Range<usize>, draw_id: u32) {
329        buffer.for_each_unset_run_and_write(
330            BucketRange::new(range.start as u16, range.end as u16),
331            draw_id,
332            |_| {},
333        );
334    }
335
336    fn assert_depth(buffer: &DepthBuffer, ranges: &[(Range<usize>, u32)]) {
337        let mut expected = vec![0; buffer.data.len()];
338        for (range, draw_id) in ranges {
339            expected[range.clone()].fill(*draw_id);
340        }
341
342        assert_eq!(buffer.data, expected);
343    }
344
345    #[test]
346    fn split_opaque_span_extracts_aligned_middle() {
347        let mut segments = Vec::new();
348        split_opaque_span(Span::new(4, DEPTH_BUCKET_WIDTH * 3), |segment| {
349            segments.push(segment);
350        });
351
352        assert_eq!(
353            segments,
354            [
355                DepthSegment::Regular(Span::new(4, DEPTH_BUCKET_WIDTH - 4)),
356                DepthSegment::Opaque(BucketRange::new(1, 3)),
357                DepthSegment::Regular(Span::new(DEPTH_BUCKET_WIDTH * 3, 4)),
358            ]
359        );
360    }
361
362    #[test]
363    fn depth_state_skips_when_no_later_overlapping_opaque_draw_exists() {
364        let mut state = DepthState::default();
365        let opaque = buckets(1, 2);
366        state.include_span(opaque, 7);
367
368        assert!(state.can_skip(buckets(0, 1), 1));
369        assert!(state.can_skip(opaque, 7));
370        assert!(!state.can_skip(opaque, 6));
371
372        state.reset();
373        assert!(state.can_skip(opaque, 1));
374    }
375
376    #[test]
377    fn visible_runs_skip_interleaved_later_draws() {
378        let mut buffer = buffer(5);
379        write_buckets(&mut buffer, 1..2, 10);
380        write_buckets(&mut buffer, 3..4, 10);
381
382        assert_eq!(
383            visible_runs(&buffer, buckets(0, 5), 9),
384            [(0, 1), (2, 3), (4, 5)]
385        );
386        assert_eq!(visible_runs(&buffer, buckets(0, 5), 10), [(0, 5)]);
387    }
388
389    #[test]
390    fn unset_runs_and_writes_fill_interleaved_gaps() {
391        let mut buffer = buffer(5);
392        write_buckets(&mut buffer, 1..2, 10);
393        write_buckets(&mut buffer, 3..4, 10);
394
395        assert_eq!(unset_runs(&buffer, buckets(0, 5)), [(0, 1), (2, 3), (4, 5)]);
396
397        let mut written_runs = Vec::new();
398        buffer.for_each_unset_run_and_write(BucketRange::new(0, 5), 7, |range| {
399            written_runs.push((usize::from(range.start), usize::from(range.end)));
400        });
401        assert_eq!(written_runs, [(0, 1), (2, 3), (4, 5)]);
402        assert_depth(
403            &buffer,
404            [(0..1, 7), (1..2, 10), (2..3, 7), (3..4, 10), (4..5, 7)].as_slice(),
405        );
406    }
407
408    #[test]
409    fn visible_and_unset_runs_are_limited_to_the_requested_span() {
410        let mut buffer = buffer(6);
411        write_buckets(&mut buffer, 1..2, 10);
412        write_buckets(&mut buffer, 4..5, 10);
413
414        assert_eq!(visible_runs(&buffer, buckets(2, 5), 9), [(2, 4)]);
415        assert_eq!(unset_runs(&buffer, buckets(2, 5)), [(2, 4)]);
416    }
417
418    #[test]
419    fn unset_runs_clip_to_unaligned_requested_span() {
420        let buffer = buffer(3);
421        let span = Span::new(7, DEPTH_BUCKET_WIDTH + 13);
422        let mut runs = Vec::new();
423
424        buffer.for_each_unset_run(span, |span| {
425            runs.push((span.pixel_x(), span.pixel_end()));
426        });
427
428        assert_eq!(runs, [(7, DEPTH_BUCKET_WIDTH + 20)]);
429    }
430
431    #[test]
432    fn visible_runs_only_skip_buckets_with_later_draw_ids() {
433        let mut buffer = buffer(6);
434        write_buckets(&mut buffer, 0..1, 4);
435        write_buckets(&mut buffer, 1..2, 9);
436        write_buckets(&mut buffer, 2..3, 6);
437        write_buckets(&mut buffer, 3..4, 12);
438        write_buckets(&mut buffer, 5..6, 2);
439
440        assert_eq!(
441            visible_runs(&buffer, buckets(0, 6), 6),
442            [(0, 1), (2, 3), (4, 6)]
443        );
444    }
445
446    #[test]
447    fn clear_resets_all_buckets() {
448        let mut buffer = buffer(3);
449        write_buckets(&mut buffer, 0..3, 10);
450
451        buffer.clear();
452
453        assert_depth(&buffer, &[]);
454    }
455}
vello_cpu/coarse/depth.rs

vello_cpu/coarse/
depth.rs
