sparse_strips/vello_cpu/src/coarse/depth.rs - external/github.com/linebender/vello - Git at Google

 // Copyright 2026 the Vello Authors
 // SPDX-License-Identifier: Apache-2.0 OR MIT

 //! CPU-based depth buffers.
 //!
 //! GPUs have depth buffers, so why not use them for CPU rendering as well! For many of the existing
 //! CPU-based 2D renderers, this is not really possible because they use immediate-mode rendering.
 //! But Vello CPU first converts all rendering commands into strips and then processes them, meaning
 //! that before we even start with rasterization, we already have a rough idea of what we are about
 //! to rasterize. Therefore, we can use this information to go about performing rasterization in a
 //! smarter way.
 //!
 //! Unlike GPUs, it is not feasible to have a per-pixel depth buffer. While certain per-pixel work
 //! can be expensive (images, gradients), what is even more expensive is splitting up work in a
 //! too granular fashion, especially when only dealing with solid colors. It is much faster to just
 //! fill a 256x1 buffer of pixels with a single colors than doing it in 32 chunks of 4x1, just to
 //! save 50% pixel work.
 //!
 //! Therefore, the CPU-based depth buffer acts at a much coarser granularity. Vertically, it comes
 //! very natural to simply decide that one depth buffer entry covers a range of [`Tile::HEIGHT`]
 //! pixels, since all commands are executed at this height anyway. Choosing a width is much trickier:
 //! Similarly, the width should be a multiple of [`Tile::WIDTH`], but using this as the granularity
 //! is still to narrow. After some empirical measurements, it was decided that a width of
 //! [`DEPTH_BUCKET_WIDTH`] overall represents a good compromise across different paint types.
 //!
 //! How this essentially works now is that, once we've collected all strips, we split them up
 //! into opaque fills aligned to the depth bucket width, and all other fills which either have
 //! transparency or stem from non-aligned parts of an opaque fill. During rasterization, we
 //! first render the opaque strips front-to-back, each time checking the depth buffer whether
 //! this hasn't already been filled by an opaque strip with a higher z-index. Otherwise, we
 //! perform the fill and update the depth buffer.
 //!
 //! Then, we simply render the remaining strips back to front, again always comparing the depth
 //! against what's written in the depth buffer and skipping any commands that would be fully
 //! covered by existing content.

 use crate::util::Span;
 use alloc::vec;
 use alloc::vec::Vec;
 use core::ops::Range;
 use vello_common::tile::Tile;

 pub(crate) const DEPTH_BUCKET_WIDTH: u16 = 128;
 const DEPTH_BUCKET_TILE_WIDTH: u16 = DEPTH_BUCKET_WIDTH / Tile::WIDTH;
 const _: () = assert!(
     DEPTH_BUCKET_WIDTH.is_multiple_of(Tile::WIDTH),
     "depth bucket width must be a multiple of tile width"
 );

 /// A horizontal range in depth-bucket coordinates.
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
 pub(crate) struct BucketRange {
     pub(crate) start: u16,
     pub(crate) end: u16,
 }

 impl BucketRange {
     pub(crate) fn new(start: u16, end: u16) -> Self {
         Self { start, end }
     }

     pub(crate) fn span(self) -> Span {
         let x = self.start * DEPTH_BUCKET_WIDTH;
         Span::new(x, (self.end - self.start) * DEPTH_BUCKET_WIDTH)
     }
 }

 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
 pub(crate) enum DepthSegment {
     /// An opaque span that cannot be tracked in the depth buffer because it is not
     /// aligned to whole depth buckets.
     Regular(Span),
     /// An opaque span that is aligned and can therefore be rendered front-to-back with
     /// depth-buffer write enabled.
     Opaque(BucketRange),
 }

 /// Splits a tile-aligned span into regular edge spans and a depth-trackable
 /// opaque middle span.
 pub(crate) fn split_opaque_span(span: Span, mut segment: impl FnMut(DepthSegment)) {
     debug_assert!(
         span.pixel_x().is_multiple_of(Tile::WIDTH) && span.pixel_end().is_multiple_of(Tile::WIDTH),
         "`split_opaque_span` requires a tile-aligned span"
     );

     let x = span.tile_x();
     let end = span.tile_end();
     let aligned_x = x.next_multiple_of(DEPTH_BUCKET_TILE_WIDTH);
     let aligned_end = (end / DEPTH_BUCKET_TILE_WIDTH) * DEPTH_BUCKET_TILE_WIDTH;

     if aligned_x >= aligned_end {
         segment(DepthSegment::Regular(span));

         return;
     }

     if x < aligned_x {
         segment(DepthSegment::Regular(Span::new_tile(x, aligned_x - x)));
     }

     if aligned_x < aligned_end {
         segment(DepthSegment::Opaque(BucketRange::new(
             aligned_x / DEPTH_BUCKET_TILE_WIDTH,
             aligned_end / DEPTH_BUCKET_TILE_WIDTH,
         )));
     }

     if aligned_end < end {
         segment(DepthSegment::Regular(Span::new_tile(
             aligned_end,
             end - aligned_end,
         )));
     }
 }

 /// Coarse state for the depth buffer.
 #[derive(Debug, Clone, Copy, Default)]
 pub(crate) struct DepthState {
     /// Coarse union of all depth-tracked opaque spans in this row.
     bounds: Option<Span>,
     /// Maximum draw ID of any depth-trackable opaque command in this row.
     ///
     /// Draw IDs start at 1, so 0 represents "no opaque command".
     max_draw_id: u32,
 }

 impl DepthState {
     pub(crate) fn reset(&mut self) {
         *self = Self::default();
     }

     pub(crate) fn include_span(&mut self, span: Span, draw_id: u32) {
         if let Some(bounds) = &mut self.bounds {
             bounds.extend(span);
         } else {
             self.bounds = Some(span);
         }

         self.max_draw_id = self.max_draw_id.max(draw_id);
     }

     /// Returns whether this draw can skip consulting the depth buffer.
     ///
     /// This is the case in case there is no overlap between the span and the coarse span
     /// of the current depth buffer.
     pub(crate) fn can_skip(self, span: Span, draw_id: u32) -> bool {
         if draw_id >= self.max_draw_id {
             return true;
         }

         let Some(opaque_bounds) = self.bounds else {
             return true;
         };

         let opaque_start = opaque_bounds.tile_x();
         let opaque_end = opaque_bounds.tile_end();
         let x = span.tile_x();
         let end = span.tile_end();

         x >= opaque_end || end <= opaque_start
     }
 }

 #[derive(Debug)]
 pub(crate) struct DepthBuffer {
     /// Stores the maximum draw ID for each depth bucket.
     data: Vec<u32>,
 }

 impl DepthBuffer {
     pub(crate) fn new(buffer_width: u16) -> Self {
         Self {
             data: vec![0; usize::from(buffer_width.div_ceil(DEPTH_BUCKET_WIDTH))],
         }
     }

     /// Calls `f` for every subspan of `span` that is not covered by any entry in the
     /// depth buffer.
     pub(crate) fn for_each_unset_run(&self, span: Span, mut f: impl FnMut(Span)) {
         let (mut idx, depth_end) = self.range(span);
         while let Some((span, _)) = self.next_unset_run(&mut idx, depth_end, span) {
             f(span);
         }
     }

     /// Calls `f` for every bucket run in `bucket_range` that is not covered by any
     /// entry in the depth buffer, and then marks the newly covered buckets in the
     /// depth buffer.
     pub(crate) fn for_each_unset_run_and_write(
         &mut self,
         bucket_range: BucketRange,
         draw_id: u32,
         mut f: impl FnMut(BucketRange),
     ) {
         let bounds = bucket_range.span();
         let mut idx = usize::from(bucket_range.start);
         let depth_end = usize::from(bucket_range.end);

         while let Some((_, depth_range)) = self.next_unset_run(&mut idx, depth_end, bounds) {
             let bucket_start =
                 u16::try_from(depth_range.start).expect("depth bucket range start overflow");
             let bucket_end =
                 u16::try_from(depth_range.end).expect("depth bucket range end overflow");
             f(BucketRange::new(bucket_start, bucket_end));
             self.mark(depth_range, draw_id);
         }
     }

     /// Calls `f` for every subspan of `span` that should be considered as visible assuming the
     /// given draw ID.
     pub(crate) fn for_each_visible_run(&self, span: Span, draw_id: u32, mut f: impl FnMut(Span)) {
         let (mut idx, depth_end) = self.range(span);

         while let Some(span) = self.next_visible_run(&mut idx, depth_end, draw_id, span) {
             f(span);
         }
     }

     /// Returns the depth-bucket index range touched by `span`.
     fn range(&self, span: Span) -> (usize, usize) {
         (
             usize::from(span.pixel_x() / DEPTH_BUCKET_WIDTH),
             usize::from(span.pixel_end().div_ceil(DEPTH_BUCKET_WIDTH)).min(self.data.len()),
         )
     }

     pub(crate) fn clear(&mut self) {
         self.data.fill(0);
     }

     fn mark(&mut self, range: Range<usize>, draw_id: u32) {
         self.data[range].fill(draw_id);
     }

     /// Finds the next consecutive run of unset depth buckets.
     fn next_unset_run(
         &self,
         idx: &mut usize,
         end: usize,
         bounds: Span,
     ) -> Option<(Span, Range<usize>)> {
         while *idx < end && self.data[*idx] != 0 {
             *idx += 1;
         }

         let run_start = *idx;
         while *idx < end && self.data[*idx] == 0 {
             *idx += 1;
         }

         if run_start == *idx {
             return None;
         }

         Some((
             bucket_span(run_start, *idx).intersect(bounds)?,
             run_start..*idx,
         ))
     }

     /// Finds the next consecutive run visible to `draw_id`.
     fn next_visible_run(
         &self,
         idx: &mut usize,
         end: usize,
         draw_id: u32,
         bounds: Span,
     ) -> Option<Span> {
         while *idx < end && self.data[*idx] > draw_id {
             *idx += 1;
         }

         let run_start = *idx;
         while *idx < end && self.data[*idx] <= draw_id {
             *idx += 1;
         }

         if run_start == *idx {
             return None;
         }

         bucket_span(run_start, *idx).intersect(bounds)
     }
 }

 fn bucket_span(start: usize, end: usize) -> Span {
     let x = start as u16 * DEPTH_BUCKET_WIDTH;
     Span::new(x, (end - start) as u16 * DEPTH_BUCKET_WIDTH)
 }

 #[cfg(test)]
 mod tests {
     use super::*;
     use alloc::vec::Vec;
     use core::ops::Range;

     fn buffer(bucket_count: usize) -> DepthBuffer {
         DepthBuffer::new(bucket_count as u16 * DEPTH_BUCKET_WIDTH)
     }

     fn buckets(start: usize, end: usize) -> Span {
         bucket_span(start, end)
     }

     fn bucket_range(span: Span) -> (usize, usize) {
         (
             usize::from(span.pixel_x() / DEPTH_BUCKET_WIDTH),
             usize::from(span.pixel_end() / DEPTH_BUCKET_WIDTH),
         )
     }

     fn visible_runs(buffer: &DepthBuffer, span: Span, draw_id: u32) -> Vec<(usize, usize)> {
         let mut runs = Vec::new();
         buffer.for_each_visible_run(span, draw_id, |span| {
             runs.push(bucket_range(span));
         });
         runs
     }

     fn unset_runs(buffer: &DepthBuffer, span: Span) -> Vec<(usize, usize)> {
         let mut runs = Vec::new();
         buffer.for_each_unset_run(span, |span| {
             runs.push(bucket_range(span));
         });
         runs
     }

     fn write_buckets(buffer: &mut DepthBuffer, range: Range<usize>, draw_id: u32) {
         buffer.for_each_unset_run_and_write(
             BucketRange::new(range.start as u16, range.end as u16),
             draw_id,
             |_| {},
         );
     }

     fn assert_depth(buffer: &DepthBuffer, ranges: &[(Range<usize>, u32)]) {
         let mut expected = vec![0; buffer.data.len()];
         for (range, draw_id) in ranges {
             expected[range.clone()].fill(*draw_id);
         }

         assert_eq!(buffer.data, expected);
     }

     #[test]
     fn split_opaque_span_extracts_aligned_middle() {
         let mut segments = Vec::new();
         split_opaque_span(Span::new(4, DEPTH_BUCKET_WIDTH * 3), |segment| {
             segments.push(segment);
         });

         assert_eq!(
             segments,
             [
                 DepthSegment::Regular(Span::new(4, DEPTH_BUCKET_WIDTH - 4)),
                 DepthSegment::Opaque(BucketRange::new(1, 3)),
                 DepthSegment::Regular(Span::new(DEPTH_BUCKET_WIDTH * 3, 4)),
             ]
         );
     }

     #[test]
     fn depth_state_skips_when_no_later_overlapping_opaque_draw_exists() {
         let mut state = DepthState::default();
         let opaque = buckets(1, 2);
         state.include_span(opaque, 7);

         assert!(state.can_skip(buckets(0, 1), 1));
         assert!(state.can_skip(opaque, 7));
         assert!(!state.can_skip(opaque, 6));

         state.reset();
         assert!(state.can_skip(opaque, 1));
     }

     #[test]
     fn visible_runs_skip_interleaved_later_draws() {
         let mut buffer = buffer(5);
         write_buckets(&mut buffer, 1..2, 10);
         write_buckets(&mut buffer, 3..4, 10);

         assert_eq!(
             visible_runs(&buffer, buckets(0, 5), 9),
             [(0, 1), (2, 3), (4, 5)]
         );
         assert_eq!(visible_runs(&buffer, buckets(0, 5), 10), [(0, 5)]);
     }

     #[test]
     fn unset_runs_and_writes_fill_interleaved_gaps() {
         let mut buffer = buffer(5);
         write_buckets(&mut buffer, 1..2, 10);
         write_buckets(&mut buffer, 3..4, 10);

         assert_eq!(unset_runs(&buffer, buckets(0, 5)), [(0, 1), (2, 3), (4, 5)]);

         let mut written_runs = Vec::new();
         buffer.for_each_unset_run_and_write(BucketRange::new(0, 5), 7, |range| {
             written_runs.push((usize::from(range.start), usize::from(range.end)));
         });
         assert_eq!(written_runs, [(0, 1), (2, 3), (4, 5)]);
         assert_depth(
             &buffer,
             [(0..1, 7), (1..2, 10), (2..3, 7), (3..4, 10), (4..5, 7)].as_slice(),
         );
     }

     #[test]
     fn visible_and_unset_runs_are_limited_to_the_requested_span() {
         let mut buffer = buffer(6);
         write_buckets(&mut buffer, 1..2, 10);
         write_buckets(&mut buffer, 4..5, 10);

         assert_eq!(visible_runs(&buffer, buckets(2, 5), 9), [(2, 4)]);
         assert_eq!(unset_runs(&buffer, buckets(2, 5)), [(2, 4)]);
     }

     #[test]
     fn unset_runs_clip_to_unaligned_requested_span() {
         let buffer = buffer(3);
         let span = Span::new(7, DEPTH_BUCKET_WIDTH + 13);
         let mut runs = Vec::new();

         buffer.for_each_unset_run(span, |span| {
             runs.push((span.pixel_x(), span.pixel_end()));
         });

         assert_eq!(runs, [(7, DEPTH_BUCKET_WIDTH + 20)]);
     }

     #[test]
     fn visible_runs_only_skip_buckets_with_later_draw_ids() {
         let mut buffer = buffer(6);
         write_buckets(&mut buffer, 0..1, 4);
         write_buckets(&mut buffer, 1..2, 9);
         write_buckets(&mut buffer, 2..3, 6);
         write_buckets(&mut buffer, 3..4, 12);
         write_buckets(&mut buffer, 5..6, 2);

         assert_eq!(
             visible_runs(&buffer, buckets(0, 6), 6),
             [(0, 1), (2, 3), (4, 6)]
         );
     }

     #[test]
     fn clear_resets_all_buckets() {
         let mut buffer = buffer(3);
         write_buckets(&mut buffer, 0..3, 10);

         buffer.clear();

         assert_depth(&buffer, &[]);
     }
 }
	// Copyright 2026 the Vello Authors
	// SPDX-License-Identifier: Apache-2.0 OR MIT

	//! CPU-based depth buffers.
	//!
	//! GPUs have depth buffers, so why not use them for CPU rendering as well! For many of the existing
	//! CPU-based 2D renderers, this is not really possible because they use immediate-mode rendering.
	//! But Vello CPU first converts all rendering commands into strips and then processes them, meaning
	//! that before we even start with rasterization, we already have a rough idea of what we are about
	//! to rasterize. Therefore, we can use this information to go about performing rasterization in a
	//! smarter way.
	//!
	//! Unlike GPUs, it is not feasible to have a per-pixel depth buffer. While certain per-pixel work
	//! can be expensive (images, gradients), what is even more expensive is splitting up work in a
	//! too granular fashion, especially when only dealing with solid colors. It is much faster to just
	//! fill a 256x1 buffer of pixels with a single colors than doing it in 32 chunks of 4x1, just to
	//! save 50% pixel work.
	//!
	//! Therefore, the CPU-based depth buffer acts at a much coarser granularity. Vertically, it comes
	//! very natural to simply decide that one depth buffer entry covers a range of [`Tile::HEIGHT`]
	//! pixels, since all commands are executed at this height anyway. Choosing a width is much trickier:
	//! Similarly, the width should be a multiple of [`Tile::WIDTH`], but using this as the granularity
	//! is still to narrow. After some empirical measurements, it was decided that a width of
	//! [`DEPTH_BUCKET_WIDTH`] overall represents a good compromise across different paint types.
	//!
	//! How this essentially works now is that, once we've collected all strips, we split them up
	//! into opaque fills aligned to the depth bucket width, and all other fills which either have
	//! transparency or stem from non-aligned parts of an opaque fill. During rasterization, we
	//! first render the opaque strips front-to-back, each time checking the depth buffer whether
	//! this hasn't already been filled by an opaque strip with a higher z-index. Otherwise, we
	//! perform the fill and update the depth buffer.
	//!
	//! Then, we simply render the remaining strips back to front, again always comparing the depth
	//! against what's written in the depth buffer and skipping any commands that would be fully
	//! covered by existing content.

	use crate::util::Span;
	use alloc::vec;
	use alloc::vec::Vec;
	use core::ops::Range;
	use vello_common::tile::Tile;

	pub(crate) const DEPTH_BUCKET_WIDTH: u16 = 128;
	const DEPTH_BUCKET_TILE_WIDTH: u16 = DEPTH_BUCKET_WIDTH / Tile::WIDTH;
	const _: () = assert!(
	DEPTH_BUCKET_WIDTH.is_multiple_of(Tile::WIDTH),
	"depth bucket width must be a multiple of tile width"
	);

	/// A horizontal range in depth-bucket coordinates.
	#[derive(Debug, Clone, Copy, PartialEq, Eq)]
	pub(crate) struct BucketRange {
	pub(crate) start: u16,
	pub(crate) end: u16,
	}

	impl BucketRange {
	pub(crate) fn new(start: u16, end: u16) -> Self {
	Self { start, end }
	}

	pub(crate) fn span(self) -> Span {
	let x = self.start * DEPTH_BUCKET_WIDTH;
	Span::new(x, (self.end - self.start) * DEPTH_BUCKET_WIDTH)
	}
	}

	#[derive(Debug, Clone, Copy, PartialEq, Eq)]
	pub(crate) enum DepthSegment {
	/// An opaque span that cannot be tracked in the depth buffer because it is not
	/// aligned to whole depth buckets.
	Regular(Span),
	/// An opaque span that is aligned and can therefore be rendered front-to-back with
	/// depth-buffer write enabled.
	Opaque(BucketRange),
	}

	/// Splits a tile-aligned span into regular edge spans and a depth-trackable
	/// opaque middle span.
	pub(crate) fn split_opaque_span(span: Span, mut segment: impl FnMut(DepthSegment)) {
	debug_assert!(
	span.pixel_x().is_multiple_of(Tile::WIDTH) && span.pixel_end().is_multiple_of(Tile::WIDTH),
	"`split_opaque_span` requires a tile-aligned span"
	);

	let x = span.tile_x();
	let end = span.tile_end();
	let aligned_x = x.next_multiple_of(DEPTH_BUCKET_TILE_WIDTH);
	let aligned_end = (end / DEPTH_BUCKET_TILE_WIDTH) * DEPTH_BUCKET_TILE_WIDTH;

	if aligned_x >= aligned_end {
	segment(DepthSegment::Regular(span));

	return;
	}

	if x < aligned_x {
	segment(DepthSegment::Regular(Span::new_tile(x, aligned_x - x)));
	}

	if aligned_x < aligned_end {
	segment(DepthSegment::Opaque(BucketRange::new(
	aligned_x / DEPTH_BUCKET_TILE_WIDTH,
	aligned_end / DEPTH_BUCKET_TILE_WIDTH,
	)));
	}

	if aligned_end < end {
	segment(DepthSegment::Regular(Span::new_tile(
	aligned_end,
	end - aligned_end,
	)));
	}
	}

	/// Coarse state for the depth buffer.
	#[derive(Debug, Clone, Copy, Default)]
	pub(crate) struct DepthState {
	/// Coarse union of all depth-tracked opaque spans in this row.
	bounds: Option<Span>,
	/// Maximum draw ID of any depth-trackable opaque command in this row.
	///
	/// Draw IDs start at 1, so 0 represents "no opaque command".
	max_draw_id: u32,
	}

	impl DepthState {
	pub(crate) fn reset(&mut self) {
	*self = Self::default();
	}

	pub(crate) fn include_span(&mut self, span: Span, draw_id: u32) {
	if let Some(bounds) = &mut self.bounds {
	bounds.extend(span);
	} else {
	self.bounds = Some(span);
	}

	self.max_draw_id = self.max_draw_id.max(draw_id);
	}

	/// Returns whether this draw can skip consulting the depth buffer.
	///
	/// This is the case in case there is no overlap between the span and the coarse span
	/// of the current depth buffer.
	pub(crate) fn can_skip(self, span: Span, draw_id: u32) -> bool {
	if draw_id >= self.max_draw_id {
	return true;
	}

	let Some(opaque_bounds) = self.bounds else {
	return true;
	};

	let opaque_start = opaque_bounds.tile_x();
	let opaque_end = opaque_bounds.tile_end();
	let x = span.tile_x();
	let end = span.tile_end();

	x >= opaque_end \|\| end <= opaque_start
	}
	}

	#[derive(Debug)]
	pub(crate) struct DepthBuffer {
	/// Stores the maximum draw ID for each depth bucket.
	data: Vec<u32>,
	}

	impl DepthBuffer {
	pub(crate) fn new(buffer_width: u16) -> Self {
	Self {
	data: vec![0; usize::from(buffer_width.div_ceil(DEPTH_BUCKET_WIDTH))],
	}
	}

	/// Calls `f` for every subspan of `span` that is not covered by any entry in the
	/// depth buffer.
	pub(crate) fn for_each_unset_run(&self, span: Span, mut f: impl FnMut(Span)) {
	let (mut idx, depth_end) = self.range(span);
	while let Some((span, _)) = self.next_unset_run(&mut idx, depth_end, span) {
	f(span);
	}
	}

	/// Calls `f` for every bucket run in `bucket_range` that is not covered by any
	/// entry in the depth buffer, and then marks the newly covered buckets in the
	/// depth buffer.
	pub(crate) fn for_each_unset_run_and_write(
	&mut self,
	bucket_range: BucketRange,
	draw_id: u32,
	mut f: impl FnMut(BucketRange),
	) {
	let bounds = bucket_range.span();
	let mut idx = usize::from(bucket_range.start);
	let depth_end = usize::from(bucket_range.end);

	while let Some((_, depth_range)) = self.next_unset_run(&mut idx, depth_end, bounds) {
	let bucket_start =
	u16::try_from(depth_range.start).expect("depth bucket range start overflow");
	let bucket_end =
	u16::try_from(depth_range.end).expect("depth bucket range end overflow");
	f(BucketRange::new(bucket_start, bucket_end));
	self.mark(depth_range, draw_id);
	}
	}

	/// Calls `f` for every subspan of `span` that should be considered as visible assuming the
	/// given draw ID.
	pub(crate) fn for_each_visible_run(&self, span: Span, draw_id: u32, mut f: impl FnMut(Span)) {
	let (mut idx, depth_end) = self.range(span);

	while let Some(span) = self.next_visible_run(&mut idx, depth_end, draw_id, span) {
	f(span);
	}
	}

	/// Returns the depth-bucket index range touched by `span`.
	fn range(&self, span: Span) -> (usize, usize) {
	(
	usize::from(span.pixel_x() / DEPTH_BUCKET_WIDTH),
	usize::from(span.pixel_end().div_ceil(DEPTH_BUCKET_WIDTH)).min(self.data.len()),
	)
	}

	pub(crate) fn clear(&mut self) {
	self.data.fill(0);
	}

	fn mark(&mut self, range: Range<usize>, draw_id: u32) {
	self.data[range].fill(draw_id);
	}

	/// Finds the next consecutive run of unset depth buckets.
	fn next_unset_run(
	&self,
	idx: &mut usize,
	end: usize,
	bounds: Span,
	) -> Option<(Span, Range<usize>)> {
	while idx < end && self.data[idx] != 0 {
	*idx += 1;
	}

	let run_start = *idx;
	while idx < end && self.data[idx] == 0 {
	*idx += 1;
	}

	if run_start == *idx {
	return None;
	}

	Some((
	bucket_span(run_start, *idx).intersect(bounds)?,
	run_start..*idx,
	))
	}

	/// Finds the next consecutive run visible to `draw_id`.
	fn next_visible_run(
	&self,
	idx: &mut usize,
	end: usize,
	draw_id: u32,
	bounds: Span,
	) -> Option<Span> {
	while idx < end && self.data[idx] > draw_id {
	*idx += 1;
	}

	let run_start = *idx;
	while idx < end && self.data[idx] <= draw_id {
	*idx += 1;
	}

	if run_start == *idx {
	return None;
	}

	bucket_span(run_start, *idx).intersect(bounds)
	}
	}

	fn bucket_span(start: usize, end: usize) -> Span {
	let x = start as u16 * DEPTH_BUCKET_WIDTH;
	Span::new(x, (end - start) as u16 * DEPTH_BUCKET_WIDTH)
	}

	#[cfg(test)]
	mod tests {
	use super::*;
	use alloc::vec::Vec;
	use core::ops::Range;

	fn buffer(bucket_count: usize) -> DepthBuffer {
	DepthBuffer::new(bucket_count as u16 * DEPTH_BUCKET_WIDTH)
	}

	fn buckets(start: usize, end: usize) -> Span {
	bucket_span(start, end)
	}

	fn bucket_range(span: Span) -> (usize, usize) {
	(
	usize::from(span.pixel_x() / DEPTH_BUCKET_WIDTH),
	usize::from(span.pixel_end() / DEPTH_BUCKET_WIDTH),
	)
	}

	fn visible_runs(buffer: &DepthBuffer, span: Span, draw_id: u32) -> Vec<(usize, usize)> {
	let mut runs = Vec::new();
	buffer.for_each_visible_run(span, draw_id, \|span\| {
	runs.push(bucket_range(span));
	});
	runs
	}

	fn unset_runs(buffer: &DepthBuffer, span: Span) -> Vec<(usize, usize)> {
	let mut runs = Vec::new();
	buffer.for_each_unset_run(span, \|span\| {
	runs.push(bucket_range(span));
	});
	runs
	}

	fn write_buckets(buffer: &mut DepthBuffer, range: Range<usize>, draw_id: u32) {
	buffer.for_each_unset_run_and_write(
	BucketRange::new(range.start as u16, range.end as u16),
	draw_id,
	\|_\| {},
	);
	}

	fn assert_depth(buffer: &DepthBuffer, ranges: &[(Range<usize>, u32)]) {
	let mut expected = vec![0; buffer.data.len()];
	for (range, draw_id) in ranges {
	expected[range.clone()].fill(*draw_id);
	}

	assert_eq!(buffer.data, expected);
	}

	#[test]
	fn split_opaque_span_extracts_aligned_middle() {
	let mut segments = Vec::new();
	split_opaque_span(Span::new(4, DEPTH_BUCKET_WIDTH * 3), \|segment\| {
	segments.push(segment);
	});

	assert_eq!(
	segments,
	[
	DepthSegment::Regular(Span::new(4, DEPTH_BUCKET_WIDTH - 4)),
	DepthSegment::Opaque(BucketRange::new(1, 3)),
	DepthSegment::Regular(Span::new(DEPTH_BUCKET_WIDTH * 3, 4)),
	]
	);
	}

	#[test]
	fn depth_state_skips_when_no_later_overlapping_opaque_draw_exists() {
	let mut state = DepthState::default();
	let opaque = buckets(1, 2);
	state.include_span(opaque, 7);

	assert!(state.can_skip(buckets(0, 1), 1));
	assert!(state.can_skip(opaque, 7));
	assert!(!state.can_skip(opaque, 6));

	state.reset();
	assert!(state.can_skip(opaque, 1));
	}

	#[test]
	fn visible_runs_skip_interleaved_later_draws() {
	let mut buffer = buffer(5);
	write_buckets(&mut buffer, 1..2, 10);
	write_buckets(&mut buffer, 3..4, 10);

	assert_eq!(
	visible_runs(&buffer, buckets(0, 5), 9),
	[(0, 1), (2, 3), (4, 5)]
	);
	assert_eq!(visible_runs(&buffer, buckets(0, 5), 10), [(0, 5)]);
	}

	#[test]
	fn unset_runs_and_writes_fill_interleaved_gaps() {
	let mut buffer = buffer(5);
	write_buckets(&mut buffer, 1..2, 10);
	write_buckets(&mut buffer, 3..4, 10);

	assert_eq!(unset_runs(&buffer, buckets(0, 5)), [(0, 1), (2, 3), (4, 5)]);

	let mut written_runs = Vec::new();
	buffer.for_each_unset_run_and_write(BucketRange::new(0, 5), 7, \|range\| {
	written_runs.push((usize::from(range.start), usize::from(range.end)));
	});
	assert_eq!(written_runs, [(0, 1), (2, 3), (4, 5)]);
	assert_depth(
	&buffer,
	[(0..1, 7), (1..2, 10), (2..3, 7), (3..4, 10), (4..5, 7)].as_slice(),
	);
	}

	#[test]
	fn visible_and_unset_runs_are_limited_to_the_requested_span() {
	let mut buffer = buffer(6);
	write_buckets(&mut buffer, 1..2, 10);
	write_buckets(&mut buffer, 4..5, 10);

	assert_eq!(visible_runs(&buffer, buckets(2, 5), 9), [(2, 4)]);
	assert_eq!(unset_runs(&buffer, buckets(2, 5)), [(2, 4)]);
	}

	#[test]
	fn unset_runs_clip_to_unaligned_requested_span() {
	let buffer = buffer(3);
	let span = Span::new(7, DEPTH_BUCKET_WIDTH + 13);
	let mut runs = Vec::new();

	buffer.for_each_unset_run(span, \|span\| {
	runs.push((span.pixel_x(), span.pixel_end()));
	});

	assert_eq!(runs, [(7, DEPTH_BUCKET_WIDTH + 20)]);
	}

	#[test]
	fn visible_runs_only_skip_buckets_with_later_draw_ids() {
	let mut buffer = buffer(6);
	write_buckets(&mut buffer, 0..1, 4);
	write_buckets(&mut buffer, 1..2, 9);
	write_buckets(&mut buffer, 2..3, 6);
	write_buckets(&mut buffer, 3..4, 12);
	write_buckets(&mut buffer, 5..6, 2);

	assert_eq!(
	visible_runs(&buffer, buckets(0, 6), 6),
	[(0, 1), (2, 3), (4, 6)]
	);
	}

	#[test]
	fn clear_resets_all_buckets() {
	let mut buffer = buffer(3);
	write_buckets(&mut buffer, 0..3, 10);

	buffer.clear();

	assert_depth(&buffer, &[]);
	}
	}