Add the code for `vello_common` (#828)
Note that this is not ready for merging yet as I'm still tracking down a
regression I introduced. I didn't notice this because in my branch all
affected tests use the rectangle fast path, which I removed here for
now. So that might take a while.
But other than that, this part of the code should be pretty much done
(and reviewable).
diff --git a/Cargo.lock b/Cargo.lock
index d213d27..5f478d1 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -2602,6 +2602,11 @@
[[package]]
name = "vello_common"
version = "0.4.0"
+dependencies = [
+ "kurbo",
+ "peniko",
+ "vello_api",
+]
[[package]]
name = "vello_cpu"
diff --git a/Cargo.toml b/Cargo.toml
index d363e22..6fdd4a3 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -86,7 +86,6 @@
[workspace.dependencies]
vello = { version = "0.4.0", path = "vello" }
-vello_api = { path = "sparse_strips/vello_api" }
vello_encoding = { version = "0.4.0", path = "vello_encoding" }
vello_shaders = { version = "0.4.0", path = "vello_shaders" }
bytemuck = { version = "1.21.0", features = ["derive"] }
@@ -101,6 +100,10 @@
static_assertions = "1.1.0"
thiserror = "2.0.11"
+# The below crates are experimental!
+vello_api = { path = "sparse_strips/vello_api" }
+vello_common = { path = "sparse_strips/vello_common" }
+
# NOTE: Make sure to keep this in sync with the version badge in README.md and vello/README.md
wgpu = { version = "24.0.1" }
log = "0.4.22"
diff --git a/sparse_strips/vello_common/Cargo.toml b/sparse_strips/vello_common/Cargo.toml
index 429d064..740301c 100644
--- a/sparse_strips/vello_common/Cargo.toml
+++ b/sparse_strips/vello_common/Cargo.toml
@@ -12,6 +12,12 @@
publish = false
[dependencies]
+vello_api = { workspace = true }
+kurbo = { workspace = true }
+peniko = { workspace = true }
+
+[features]
+simd = ["vello_api/simd"]
[lints]
workspace = true
diff --git a/sparse_strips/vello_common/src/coarse.rs b/sparse_strips/vello_common/src/coarse.rs
new file mode 100644
index 0000000..af39223
--- /dev/null
+++ b/sparse_strips/vello_common/src/coarse.rs
@@ -0,0 +1,246 @@
+// Copyright 2025 the Vello Authors
+// SPDX-License-Identifier: Apache-2.0 OR MIT
+
+//! Generating and processing wide tiles.
+
+use crate::color::{AlphaColor, Srgb};
+use crate::strip::{Strip, STRIP_HEIGHT};
+use vello_api::paint::Paint;
+use vello_api::peniko::Fill;
+
+/// The width of a wide tile.
+pub const WIDE_TILE_WIDTH: usize = 256;
+
+/// A container for wide tiles.
+#[derive(Debug)]
+pub struct Wide {
+ tiles: Vec<WideTile>,
+ width: usize,
+ height: usize,
+}
+
+impl Wide {
+ /// Create a new container for wide tiles.
+ pub fn new(width: usize, height: usize) -> Self {
+ let width_tiles = width.div_ceil(WIDE_TILE_WIDTH);
+ let height_tiles = height.div_ceil(STRIP_HEIGHT);
+ let mut tiles = Vec::with_capacity(width_tiles * height_tiles);
+
+ for w in 0..width_tiles {
+ for h in 0..height_tiles {
+ tiles.push(WideTile::new(w * WIDE_TILE_WIDTH, h * STRIP_HEIGHT));
+ }
+ }
+
+ Self {
+ tiles,
+ width,
+ height,
+ }
+ }
+
+ /// Reset all tiles in the container.
+ pub fn reset(&mut self) {
+ for tile in &mut self.tiles {
+ tile.bg = AlphaColor::TRANSPARENT;
+ tile.cmds.clear();
+ }
+ }
+
+ /// Return the number of horizontal tiles.
+ pub fn width_tiles(&self) -> usize {
+ self.width.div_ceil(WIDE_TILE_WIDTH)
+ }
+
+ /// Return the number of vertical tiles.
+ pub fn height_tiles(&self) -> usize {
+ self.height.div_ceil(STRIP_HEIGHT)
+ }
+
+ /// Get the wide tile at a certain index.
+ ///
+ /// Panics if the index is out-of-range.
+ pub fn get(&self, x: usize, y: usize) -> &WideTile {
+ assert!(
+ x < self.width && y < self.height,
+ "attempted to access out-of-bounds wide tile"
+ );
+
+ &self.tiles[y * self.width_tiles() + x]
+ }
+
+ /// Get mutable access to the wide tile at a certain index.
+ ///
+ /// Panics if the index is out-of-range.
+ pub fn get_mut(&mut self, x: usize, y: usize) -> &mut WideTile {
+ assert!(
+ x < self.width && y < self.height,
+ "attempted to access out-of-bounds wide tile"
+ );
+
+ let idx = y * self.width_tiles() + x;
+ &mut self.tiles[idx]
+ }
+
+ /// Return a reference to all wide tiles.
+ pub fn tiles(&self) -> &[WideTile] {
+ self.tiles.as_slice()
+ }
+
+ /// Generate wide tile commands from the strip buffer.
+ pub fn generate(&mut self, strip_buf: &[Strip], fill_rule: Fill, paint: Paint) {
+ let width_tiles = self.width_tiles();
+
+ if strip_buf.is_empty() {
+ return;
+ }
+
+ for i in 0..strip_buf.len() - 1 {
+ let strip = &strip_buf[i];
+
+ if strip.x >= self.width as i32 {
+ // Don't render strips that are outside the viewport.
+ continue;
+ }
+
+ if strip.y >= self.height as u16 {
+ // Since strips are sorted by location, any subsequent strips will also be
+ // outside the viewport, so we can abort entirely.
+ break;
+ }
+
+ let next_strip = &strip_buf[i + 1];
+ // Currently, strips can also start at a negative x position, since we don't
+ // support viewport culling yet. However, when generating the commands
+ // we only want to emit strips >= 0, so we calculate the adjustment
+ // and then only include the alpha indices for columns where x >= 0.
+ let x0_adjustment = strip.x.min(0).unsigned_abs();
+ let x0 = (strip.x + x0_adjustment as i32) as u32;
+ let strip_y = strip.strip_y();
+ let mut col = strip.col + x0_adjustment;
+ // Can potentially be 0, if the next strip's x values is also < 0.
+ let strip_width = next_strip.col.saturating_sub(col);
+ let x1 = x0 + strip_width;
+ let tile_x0 = x0 as usize / WIDE_TILE_WIDTH;
+ // It's possible that a strip extends into a new wide tile, but we don't actually
+ // have as many wide tiles (e.g. because the pixmap width is only 512, but
+ // strip ends at 513), so take the minimum between the rounded values and `width_tiles`.
+ let tile_x1 = (x1 as usize).div_ceil(WIDE_TILE_WIDTH).min(width_tiles);
+ let mut x = x0;
+
+ for tile_x in tile_x0..tile_x1 {
+ let x_tile_rel = x % WIDE_TILE_WIDTH as u32;
+ let width = x1.min(((tile_x + 1) * WIDE_TILE_WIDTH) as u32) - x;
+ let cmd = CmdAlphaFill {
+ x: x_tile_rel,
+ width,
+ alpha_ix: col as usize,
+ paint: paint.clone(),
+ };
+ x += width;
+ col += width;
+ self.get_mut(tile_x, strip_y as usize)
+ .push(Cmd::AlphaFill(cmd));
+ }
+
+ let active_fill = match fill_rule {
+ Fill::NonZero => next_strip.winding != 0,
+ Fill::EvenOdd => next_strip.winding % 2 != 0,
+ };
+
+ if active_fill
+ && strip_y == next_strip.strip_y()
+ // Only fill if we are actually inside the viewport.
+ && next_strip.x >= 0
+ {
+ x = x1;
+ let x2 = next_strip.x as u32;
+ let fxt0 = x1 as usize / WIDE_TILE_WIDTH;
+ let fxt1 = (x2 as usize).div_ceil(WIDE_TILE_WIDTH);
+ for tile_x in fxt0..fxt1 {
+ let x_tile_rel = x % WIDE_TILE_WIDTH as u32;
+ let width = x2.min(((tile_x + 1) * WIDE_TILE_WIDTH) as u32) - x;
+ x += width;
+ self.get_mut(tile_x, strip_y as usize)
+ .fill(x_tile_rel, width, paint.clone());
+ }
+ }
+ }
+ }
+}
+
+/// A wide tile.
+#[derive(Debug)]
+pub struct WideTile {
+ /// The x coordinate of the wide tile.
+ pub x: usize,
+ /// The y coordinate of the wide tile.
+ pub y: usize,
+ /// The background of the tile.
+ pub bg: AlphaColor<Srgb>,
+ /// The draw commands of the tile.
+ pub cmds: Vec<Cmd>,
+}
+
+impl WideTile {
+ /// Create a new wide tile.
+ pub fn new(x: usize, y: usize) -> Self {
+ Self {
+ x,
+ y,
+ bg: AlphaColor::TRANSPARENT,
+ cmds: vec![],
+ }
+ }
+
+ pub(crate) fn fill(&mut self, x: u32, width: u32, paint: Paint) {
+ let Paint::Solid(s) = &paint else {
+ unimplemented!()
+ };
+ let can_override = x == 0 && width == WIDE_TILE_WIDTH as u32 && s.components[3] == 1.0;
+
+ if can_override {
+ self.cmds.clear();
+ self.bg = *s;
+ } else {
+ self.cmds.push(Cmd::Fill(CmdFill { x, width, paint }));
+ }
+ }
+
+ pub(crate) fn push(&mut self, cmd: Cmd) {
+ self.cmds.push(cmd);
+ }
+}
+
+/// A drawing command.
+#[derive(Debug)]
+pub enum Cmd {
+ /// A fill command.
+ Fill(CmdFill),
+ /// A fill command with alpha mask.
+ AlphaFill(CmdAlphaFill),
+}
+
+/// Fill a consecutive region of a wide tile.
+#[derive(Debug)]
+pub struct CmdFill {
+ /// The horizontal start position of the command.
+ pub x: u32,
+ /// The width of the command.
+ pub width: u32,
+ /// The paint that should be used to fill the area.
+ pub paint: Paint,
+}
+
+/// Fill a consecutive region of a wide tile with an alpha mask.
+#[derive(Debug)]
+pub struct CmdAlphaFill {
+ /// The horizontal start position of the command.
+ pub x: u32,
+ /// The width of the command.
+ pub width: u32,
+ /// The start index in the alpha buffer of the command.
+ pub alpha_ix: usize,
+ /// The paint that should be used to fill the area.
+ pub paint: Paint,
+}
diff --git a/sparse_strips/vello_common/src/flatten.rs b/sparse_strips/vello_common/src/flatten.rs
new file mode 100644
index 0000000..aada20c
--- /dev/null
+++ b/sparse_strips/vello_common/src/flatten.rs
@@ -0,0 +1,124 @@
+// Copyright 2025 the Vello Authors
+// SPDX-License-Identifier: Apache-2.0 OR MIT
+
+//! Flattening filled and stroked paths.
+
+use kurbo::StrokeOpts;
+use vello_api::kurbo;
+use vello_api::kurbo::{Affine, BezPath, Stroke};
+
+/// The flattening tolerance.
+const TOL: f64 = 0.25;
+
+/// A point.
+#[derive(Clone, Copy, Debug, PartialEq)]
+pub struct Point {
+ /// The x coordinate of the point.
+ pub x: f32,
+ /// The y coordinate of the point.
+ pub y: f32,
+}
+
+impl Point {
+ /// Create a new point.
+ pub const fn new(x: f32, y: f32) -> Self {
+ Self { x, y }
+ }
+}
+
+impl std::ops::Add for Point {
+ type Output = Self;
+
+ fn add(self, rhs: Self) -> Self {
+ Self::new(self.x + rhs.x, self.y + rhs.y)
+ }
+}
+
+impl std::ops::Sub for Point {
+ type Output = Self;
+
+ fn sub(self, rhs: Self) -> Self {
+ Self::new(self.x - rhs.x, self.y - rhs.y)
+ }
+}
+
+impl std::ops::Mul<f32> for Point {
+ type Output = Self;
+
+ fn mul(self, rhs: f32) -> Self {
+ Self::new(self.x * rhs, self.y * rhs)
+ }
+}
+
+/// A line.
+#[derive(Clone, Copy, Debug)]
+pub struct Line {
+ /// The start point of the line.
+ pub p0: Point,
+ /// The end point of the line.
+ pub p1: Point,
+}
+
+impl Line {
+ /// Create a new line.
+ pub fn new(p0: Point, p1: Point) -> Self {
+ Self { p0, p1 }
+ }
+}
+
+/// Flatten a filled bezier path into line segments.
+pub fn fill(path: &BezPath, affine: Affine, line_buf: &mut Vec<Line>) {
+ line_buf.clear();
+ let mut start = kurbo::Point::default();
+ let mut p0 = kurbo::Point::default();
+ let iter = path.iter().map(|el| affine * el);
+
+ let mut closed = false;
+
+ kurbo::flatten(iter, TOL, |el| match el {
+ kurbo::PathEl::MoveTo(p) => {
+ if !closed && p0 != start {
+ close_path(start, p0, line_buf);
+ }
+
+ closed = false;
+ start = p;
+ p0 = p;
+ }
+ kurbo::PathEl::LineTo(p) => {
+ let pt0 = Point::new(p0.x as f32, p0.y as f32);
+ let pt1 = Point::new(p.x as f32, p.y as f32);
+ line_buf.push(Line::new(pt0, pt1));
+ p0 = p;
+ }
+ kurbo::PathEl::QuadTo(_, _) => unreachable!(),
+ kurbo::PathEl::CurveTo(_, _, _) => unreachable!(),
+ kurbo::PathEl::ClosePath => {
+ closed = true;
+
+ close_path(start, p0, line_buf);
+ }
+ });
+
+ if !closed {
+ close_path(start, p0, line_buf);
+ }
+}
+
+/// Flatten a stroked bezier path into line segments.
+pub fn stroke(path: &BezPath, style: &Stroke, affine: Affine, line_buf: &mut Vec<Line>) {
+ // TODO: Temporary hack to ensure that strokes are scaled properly by the transform.
+ let tolerance = TOL / affine.as_coeffs()[0].abs().max(affine.as_coeffs()[3].abs());
+
+ let expanded = kurbo::stroke(path.iter(), style, &StrokeOpts::default(), tolerance);
+ fill(&expanded, affine, line_buf);
+}
+
+fn close_path(start: kurbo::Point, p0: kurbo::Point, line_buf: &mut Vec<Line>) {
+ let pt0 = Point::new(p0.x as f32, p0.y as f32);
+ let pt1 = Point::new(start.x as f32, start.y as f32);
+
+ if pt0 != pt1 {
+ line_buf.push(Line::new(pt0, pt1));
+ }
+}
diff --git a/sparse_strips/vello_common/src/footprint.rs b/sparse_strips/vello_common/src/footprint.rs
new file mode 100644
index 0000000..485f262
--- /dev/null
+++ b/sparse_strips/vello_common/src/footprint.rs
@@ -0,0 +1,145 @@
+// Copyright 2025 the Vello Authors
+// SPDX-License-Identifier: Apache-2.0 OR MIT
+
+use crate::tile::{Tile, TILE_WIDTH};
+
+/// A footprint represents in a compact fashion the range of pixels covered by a tile.
+/// We represent this as a u32 so that we can work with bit-shifting for better performance.
+pub(crate) struct Footprint(pub(crate) u32);
+
+impl Footprint {
+ /// Create a new, empty footprint.
+ pub(crate) fn empty() -> Self {
+ Self(0)
+ }
+
+ /// Create a new footprint from a single index, i.e. [i, i + 1).
+ pub(crate) fn from_index(index: u8) -> Self {
+ Self(1 << index)
+ }
+
+ /// Create a new footprint from a single index, i.e. [start, end).
+ pub(crate) fn from_range(start: u8, end: u8) -> Self {
+ Self((1 << end) - (1 << start))
+ }
+
+ /// The start point of the covered range (inclusive).
+ pub(crate) fn x0(&self) -> u32 {
+ self.0.trailing_zeros()
+ }
+
+ /// The end point of the covered range (exclusive).
+ pub(crate) fn x1(&self) -> u32 {
+ 32 - self.0.leading_zeros()
+ }
+
+ /// Extend the range with a single index.
+ pub(crate) fn extend(&mut self, index: u8) {
+ self.0 |= (1 << index) as u32;
+ }
+
+ /// Merge another footprint with the current one.
+ pub(crate) fn merge(&mut self, fp: &Self) {
+ self.0 |= fp.0;
+ }
+}
+
+impl Tile {
+ // TODO: Profiling shows that this method takes up quite a lot of time in AVX SIMD, investigate
+ // if it can be improved.
+ pub(crate) fn footprint(&self) -> Footprint {
+ let x0 = self.p0.x;
+ let x1 = self.p1.x;
+ let x_min = x0.min(x1).floor();
+ let x_max = x0.max(x1).ceil();
+ let start_i = x_min as u32;
+ let end_i = (start_i + 1).max(x_max as u32).min(TILE_WIDTH);
+
+ Footprint::from_range(start_i as u8, end_i as u8)
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::footprint::Footprint;
+
+ #[test]
+ fn footprint_empty() {
+ let fp1 = Footprint::empty();
+ // Not optimal behavior, but currently how it is.
+ assert_eq!(fp1.x0(), 32);
+ assert_eq!(fp1.x1(), 0);
+ }
+
+ #[test]
+ fn footprint_from_index() {
+ let fp1 = Footprint::from_index(0);
+ assert_eq!(fp1.x0(), 0);
+ assert_eq!(fp1.x1(), 1);
+
+ let fp2 = Footprint::from_index(3);
+ assert_eq!(fp2.x0(), 3);
+ assert_eq!(fp2.x1(), 4);
+
+ let fp3 = Footprint::from_index(6);
+ assert_eq!(fp3.x0(), 6);
+ assert_eq!(fp3.x1(), 7);
+ }
+
+ #[test]
+ fn footprint_from_range() {
+ let fp1 = Footprint::from_range(1, 3);
+ assert_eq!(fp1.x0(), 1);
+ assert_eq!(fp1.x1(), 3);
+
+ // Same comment as for empty.
+ let fp2 = Footprint::from_range(2, 2);
+ assert_eq!(fp2.x0(), 32);
+ assert_eq!(fp2.x1(), 0);
+
+ let fp3 = Footprint::from_range(3, 7);
+ assert_eq!(fp3.x0(), 3);
+ assert_eq!(fp3.x1(), 7);
+ }
+
+ #[test]
+ fn footprint_extend() {
+ let mut fp = Footprint::empty();
+ fp.extend(5);
+ assert_eq!(fp.x0(), 5);
+ assert_eq!(fp.x1(), 6);
+
+ fp.extend(3);
+ assert_eq!(fp.x0(), 3);
+ assert_eq!(fp.x1(), 6);
+
+ fp.extend(8);
+ assert_eq!(fp.x0(), 3);
+ assert_eq!(fp.x1(), 9);
+
+ fp.extend(0);
+ assert_eq!(fp.x0(), 0);
+ assert_eq!(fp.x1(), 9);
+
+ fp.extend(9);
+ assert_eq!(fp.x0(), 0);
+ assert_eq!(fp.x1(), 10);
+ }
+
+ #[test]
+ fn footprint_merge() {
+ let mut fp1 = Footprint::from_range(2, 4);
+ let fp2 = Footprint::from_range(5, 6);
+ fp1.merge(&fp2);
+
+ assert_eq!(fp1.x0(), 2);
+ assert_eq!(fp1.x1(), 6);
+
+ let mut fp3 = Footprint::from_range(5, 9);
+ let fp4 = Footprint::from_range(7, 10);
+ fp3.merge(&fp4);
+
+ assert_eq!(fp3.x0(), 5);
+ assert_eq!(fp3.x1(), 10);
+ }
+}
diff --git a/sparse_strips/vello_common/src/lib.rs b/sparse_strips/vello_common/src/lib.rs
index 8024d24..7766d8a 100644
--- a/sparse_strips/vello_common/src/lib.rs
+++ b/sparse_strips/vello_common/src/lib.rs
@@ -4,3 +4,18 @@
//! This crate contains core data structures and utilities shared across crates. It includes
//! foundational types for path geometry, tiling, and other common operations used in both CPU and
//! hybrid CPU/GPU rendering.
+
+#![cfg_attr(not(feature = "simd"), forbid(unsafe_code))]
+#![expect(
+ clippy::cast_possible_truncation,
+ reason = "We temporarily ignore those because the casts\
+only break in edge cases, and some of them are also only related to conversions from f64 to f32."
+)]
+mod footprint;
+
+pub mod coarse;
+pub mod flatten;
+pub mod strip;
+pub mod tile;
+
+pub use vello_api::*;
diff --git a/sparse_strips/vello_common/src/strip.rs b/sparse_strips/vello_common/src/strip.rs
new file mode 100644
index 0000000..312c9f2
--- /dev/null
+++ b/sparse_strips/vello_common/src/strip.rs
@@ -0,0 +1,190 @@
+// Copyright 2025 the Vello Authors
+// SPDX-License-Identifier: Apache-2.0 OR MIT
+
+//! Rendering strips.
+
+use crate::footprint::Footprint;
+use crate::tile::{Tiles, TILE_HEIGHT, TILE_WIDTH};
+use peniko::Fill;
+
+// Note that this will probably disappear and be turned into a const generic in the future.
+/// The height of a strip.
+pub const STRIP_HEIGHT: usize = 4;
+
+/// A strip.
+#[derive(Debug, Clone, Copy)]
+pub struct Strip {
+ /// The x coordinate of the strip, in user coordinates.
+ pub x: i32,
+ /// The y coordinate of the strip, in user coordinates.
+ pub y: u16,
+ /// The index into the alpha buffer
+ pub col: u32,
+ /// The winding number at the start of the strip.
+ pub winding: i32,
+}
+
+impl Strip {
+ /// Return the y coordinate of the strip, in strip units.
+ pub fn strip_y(&self) -> u16 {
+ self.y / u16::try_from(STRIP_HEIGHT).unwrap()
+ }
+}
+
+/// Render the tiles stored in `tiles` into the strip and alpha buffer.
+/// The strip buffer will be cleared in the beginning.
+pub fn render(
+ tiles: &Tiles,
+ strip_buf: &mut Vec<Strip>,
+ alpha_buf: &mut Vec<u32>,
+ fill_rule: Fill,
+) {
+ strip_buf.clear();
+
+ let mut strip_start = true;
+ let mut cols = alpha_buf.len() as u32;
+ let mut prev_tile = tiles.get(0);
+ let mut fp = prev_tile.footprint();
+ let mut seg_start = 0;
+ let mut delta = 0;
+
+ // Note: the input should contain a sentinel tile, to avoid having
+ // logic here to process the final strip.
+ for i in 1..tiles.len() {
+ let cur_tile = tiles.get(i);
+
+ if !prev_tile.same_loc(cur_tile) {
+ let start_delta = delta;
+ let same_strip = prev_tile.prev_loc(cur_tile);
+
+ if same_strip {
+ fp.extend(3);
+ }
+
+ let x0 = fp.x0();
+ let x1 = fp.x1();
+ let mut areas = [[start_delta as f32; TILE_WIDTH as usize]; TILE_HEIGHT as usize];
+
+ for j in seg_start..i {
+ let tile = tiles.get(j);
+
+ delta += tile.delta();
+
+ let p0 = tile.p0;
+ let p1 = tile.p1;
+ let inv_slope = (p1.x - p0.x) / (p1.y - p0.y);
+
+ // Note: We are iterating in column-major order because the inner loop always
+ // has a constant number of iterations, which makes it more SIMD-friendly. Worth
+ // running some tests whether a different order allows for better performance.
+ for x in x0..x1 {
+ // Relative x offset of the start point from the
+ // current column.
+ let rel_x = p0.x - x as f32;
+
+ for y in 0..STRIP_HEIGHT {
+ // Relative y offset of the start
+ // point from the current row.
+ let rel_y = p0.y - y as f32;
+ // y values will be 1 if the point is below the current row,
+ // 0 if the point is above the current row, and between 0-1
+ // if it is on the same row.
+ let y0 = rel_y.clamp(0.0, 1.0);
+ let y1 = (p1.y - y as f32).clamp(0.0, 1.0);
+ // If != 0, then the line intersects the current row
+ // in the current tile.
+ let dy = y0 - y1;
+
+ // x intersection points in the current tile.
+ let xx0 = rel_x + (y0 - rel_y) * inv_slope;
+ let xx1 = rel_x + (y1 - rel_y) * inv_slope;
+ let xmin0 = xx0.min(xx1);
+ let xmax = xx0.max(xx1);
+ // Subtract a small delta to prevent a division by zero below.
+ let xmin = xmin0.min(1.0) - 1e-6;
+ // Clip x_max to the right side of the pixel.
+ let b = xmax.min(1.0);
+ // Clip x_max to the left side of the pixel.
+ let c = b.max(0.0);
+ // Clip x_min to the left side of the pixel.
+ let d = xmin.max(0.0);
+ // Calculate the covered area.
+ // TODO: How is this formula derived?
+ let mut a = (b + 0.5 * (d * d - c * c) - xmin) / (xmax - xmin);
+ // a can be NaN if dy == 0 (and thus xmax - xmin = 0, resulting in
+ // a division by 0 above). This code changes those NaNs to 0.
+ a = a.abs().max(0.).copysign(a);
+
+ areas[x as usize][y] += a * dy;
+
+ // Making this branchless doesn't lead to any performance improvements
+ // according to my measurements.
+ if p0.x == 0.0 {
+ areas[x as usize][y] += (y as f32 - p0.y + 1.0).clamp(0.0, 1.0);
+ } else if p1.x == 0.0 {
+ areas[x as usize][y] -= (y as f32 - p1.y + 1.0).clamp(0.0, 1.0);
+ }
+ }
+ }
+ }
+
+ macro_rules! fill {
+ ($rule:expr) => {
+ for x in x0..x1 {
+ let mut alphas = 0_u32;
+
+ for y in 0..STRIP_HEIGHT {
+ let area = areas[x as usize][y];
+ let coverage = $rule(area);
+ let area_u8 = (coverage * 255.0 + 0.5) as u32;
+
+ alphas += area_u8 << (y * 8);
+ }
+
+ alpha_buf.push(alphas);
+ }
+ };
+ }
+
+ match fill_rule {
+ Fill::NonZero => {
+ fill!(|area: f32| area.abs().min(1.0))
+ }
+ Fill::EvenOdd => {
+ // As in other parts of the code, we avoid using `round` since it's very
+ // slow on x86.
+ fill!(|area: f32| (area - 2.0 * ((0.5 * area) + 0.5).floor()).abs())
+ }
+ }
+
+ if strip_start {
+ let strip = Strip {
+ x: 4 * prev_tile.x + x0 as i32,
+ y: 4 * prev_tile.y,
+ col: cols,
+ winding: start_delta,
+ };
+
+ strip_buf.push(strip);
+ }
+
+ cols += x1 - x0;
+ fp = if same_strip {
+ Footprint::from_index(0)
+ } else {
+ Footprint::empty()
+ };
+
+ strip_start = !same_strip;
+ seg_start = i;
+
+ if !prev_tile.same_row(cur_tile) {
+ delta = 0;
+ }
+ }
+
+ fp.merge(&cur_tile.footprint());
+
+ prev_tile = cur_tile;
+ }
+}
diff --git a/sparse_strips/vello_common/src/tile.rs b/sparse_strips/vello_common/src/tile.rs
new file mode 100644
index 0000000..0cceae6
--- /dev/null
+++ b/sparse_strips/vello_common/src/tile.rs
@@ -0,0 +1,516 @@
+// Copyright 2025 the Vello Authors
+// SPDX-License-Identifier: Apache-2.0 OR MIT
+
+//! Primitives for creating tiles.
+
+use crate::flatten::{Line, Point};
+
+/// The width of a tile.
+pub const TILE_WIDTH: u32 = 4;
+/// The height of a tile.
+pub const TILE_HEIGHT: u32 = 4;
+const TILE_WIDTH_SCALE: f32 = TILE_WIDTH as f32;
+const TILE_HEIGHT_SCALE: f32 = TILE_HEIGHT as f32;
+const INV_TILE_WIDTH_SCALE: f32 = 1.0 / TILE_WIDTH_SCALE;
+const INV_TILE_HEIGHT_SCALE: f32 = 1.0 / TILE_HEIGHT_SCALE;
+// The value of 8192.0 is mainly chosen for compatibility with the old cpu-sparse
+// implementation, where we scaled to u16.
+const NUDGE_FACTOR: f32 = 1.0 / 8192.0;
+const SCALED_X_NUDGE_FACTOR: f32 = 1.0 / (8192.0 * TILE_WIDTH_SCALE);
+
+/// A tile represents an aligned area on the pixmap, used to subdivide the viewport into sub-areas
+/// (currently 4x4) and analyze line intersections inside each such area.
+///
+/// Keep in mind that it is possible to have multiple tiles with the same index,
+/// namely if we have multiple lines crossing the same 4x4 area!
+#[derive(Debug, Clone)]
+pub struct Tile {
+ /// The index of the tile in the x direction.
+ pub x: i32,
+ /// The index of the tile in the y direction.
+ pub y: u16,
+ /// The start point of the line in that tile.
+ pub p0: Point,
+ /// The end point of the line in that tile.
+ pub p1: Point,
+}
+
+impl Tile {
+ /// Create a new tile.
+ pub fn new(x: i32, y: u16, p0: Point, p1: Point) -> Self {
+ Self {
+ // We don't need to store the exact negative location, just that it is negative,
+ // so that the winding number calculation is correct.
+ x: x.max(-1),
+ y,
+ p0,
+ p1,
+ }
+ }
+
+ /// Check whether two tiles are at the same location.
+ pub fn same_loc(&self, other: &Self) -> bool {
+ self.x == other.x && self.same_row(other)
+ }
+
+ /// Check whether `self` is adjacent to the left of `other`.
+ pub fn prev_loc(&self, other: &Self) -> bool {
+ self.same_row(other) && self.x + 1 == other.x
+ }
+
+ /// Check whether two tiles are on the same row.
+ pub fn same_row(&self, other: &Self) -> bool {
+ self.y == other.y
+ }
+
+ /// Return the delta of the tile.
+ pub fn delta(&self) -> i32 {
+ (self.p1.y == 0.0) as i32 - (self.p0.y == 0.0) as i32
+ }
+}
+
+/// Handles the tiling of paths.
+#[derive(Clone, Debug)]
+pub struct Tiles {
+ tile_buf: Vec<Tile>,
+ tile_index_buf: Vec<TileIndex>,
+ sorted: bool,
+}
+
+impl Default for Tiles {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl Tiles {
+ /// Create a new tiles container.
+ pub fn new() -> Self {
+ Self {
+ tile_buf: vec![],
+ sorted: false,
+ tile_index_buf: vec![],
+ }
+ }
+
+ /// Get the number of tiles in the container.
+ pub fn len(&self) -> u32 {
+ self.tile_buf.len() as u32
+ }
+
+ /// Returns true if the container has no tiles.
+ pub fn is_empty(&self) -> bool {
+ self.tile_buf.is_empty()
+ }
+
+ /// Reset the tiles' container.
+ pub fn reset(&mut self) {
+ self.tile_buf.clear();
+ self.tile_index_buf.clear();
+ self.sorted = false;
+ }
+
+ /// Sort the tiles in the container.
+ pub fn sort_tiles(&mut self) {
+ self.sorted = true;
+ self.tile_index_buf.sort_unstable_by(TileIndex::cmp);
+ }
+
+ /// Get the tile at a certain index.
+ ///
+ /// Panics if the container hasn't been sorted before.
+ pub fn get(&self, index: u32) -> &Tile {
+ assert!(
+ self.sorted,
+ "attempted to call `get` before sorting the tile container."
+ );
+
+ &self.tile_buf[self.tile_index_buf[index as usize].index()]
+ }
+
+ /// Populate the tiles' container with a buffer of lines.
+ pub fn make_tiles(&mut self, lines: &[Line]) {
+ self.reset();
+
+ // Calculate how many tiles are covered between two positions. p0 and p1 are scaled
+ // to the tile unit square.
+ let spanned_tiles =
+ |p0: f32, p1: f32| -> u32 { (p0.max(p1).ceil() - p0.min(p1).floor()).max(1.0) as u32 };
+
+ let nudge_point = |p: Point| -> Point {
+ // Lines that cross vertical tile boundaries need special treatment during
+ // anti-aliasing. This case is detected via tile-relative x == 0. However,
+ // lines can naturally start or end at a multiple of the 4x4 grid, too, but
+ // these don't constitute crossings. We nudge these points ever so slightly,
+ // by ensuring that xfrac0 and xfrac1 are always at least 1/8192 of a pixel.
+ // By doing so, whenever we encounter a point
+ // at a tile relative 0, we can treat it as an edge crossing. This is somewhat
+ // of a hack and in theory we should rather solve the underlying issue in the
+ // strip generation code, but it works for now.
+ if p.x.fract() == 0.0 {
+ Point {
+ x: p.x + SCALED_X_NUDGE_FACTOR,
+ y: p.y,
+ }
+ } else {
+ p
+ }
+ };
+
+ let mut push_tile = |x: f32, y: f32, p0: Point, p1: Point| {
+ if y >= 0.0 {
+ let tile = Tile::new(x as i32, y as u16, p0, p1);
+ self.tile_index_buf
+ .push(TileIndex::from_tile(self.tile_buf.len() as u32, &tile));
+ self.tile_buf.push(tile);
+ }
+ };
+
+ for line in lines {
+ // Points scaled to the tile unit square.
+ let s0 = nudge_point(scale_down(line.p0));
+ let s1 = nudge_point(scale_down(line.p1));
+
+ // Count how many tiles are covered on each axis.
+ let tile_count_x = spanned_tiles(s0.x, s1.x);
+ let tile_count_y = spanned_tiles(s0.y, s1.y);
+
+ // Note: This code is technically unreachable now, because we always nudge x points at tile-relative 0
+ // position. But we might need it again in the future if we change the logic.
+ let mut x = s0.x.floor();
+ if s0.x == x && s1.x < x {
+ // s0.x is on right side of first tile.
+ x -= 1.0;
+ }
+
+ let mut y = s0.y.floor();
+ if s0.y == y && s1.y < y {
+ // Since the end point of the line is above the start point,
+ // s0.y is conceptually on bottom of the previous tile instead of at the top
+ // of the current tile, so we need to adjust the y location.
+ y -= 1.0;
+ }
+
+ let xfrac0 = scale_up(s0.x - x);
+ let yfrac0 = scale_up(s0.y - y);
+ let packed0 = Point::new(xfrac0, yfrac0);
+
+ if tile_count_x == 1 {
+ let xfrac1 = scale_up(s1.x - x);
+
+ if tile_count_y == 1 {
+ let yfrac1 = scale_up(s1.y - y);
+
+ // A 1x1 tile.
+ push_tile(x, y, Point::new(xfrac0, yfrac0), Point::new(xfrac1, yfrac1));
+ } else {
+ // A vertical column.
+ let inv_slope = (s1.x - s0.x) / (s1.y - s0.y);
+ let sign = (s1.y - s0.y).signum();
+
+ // For downward lines, xclip0 and yclip store the x and y intersection points
+ // at the bottom side of the current tile. For upward lines, they store the in
+ // intersection points at the top side of the current tile.
+ let mut xclip0 = (s0.x - x) + (y - s0.y) * inv_slope;
+ // We handled the case of a 1x1 tile before, so in this case the line will
+ // definitely cross the tile either at the top or bottom, and thus yclip is
+ // either 0 or 1.
+ let (yclip, flip) = if sign > 0.0 {
+ // If the line goes downward, instead store where the line would intersect
+ // the first tile at the bottom
+ xclip0 += inv_slope;
+ (scale_up(1.0), scale_up(-1.0))
+ } else {
+ // Otherwise, the line goes up, and thus will intersect the top side of the
+ // tile.
+ (scale_up(0.0), scale_up(1.0))
+ };
+
+ let mut last_packed = packed0;
+ // For the first tile, as well as all subsequent tiles that are intersected
+ // at the top and bottom, calculate the x intersection points and push the
+ // corresponding tiles.
+
+ // Note: This could perhaps be SIMD-optimized, but initial experiments suggest
+ // that in the vast majority of cases the number of tiles is between 0-5, so
+ // it's probably not really worth it.
+ for i in 0..tile_count_y - 1 {
+ // Calculate the next x intersection point.
+ let xclip = xclip0 + i as f32 * sign * inv_slope;
+ // The .max(1) is necessary to indicate that the point actually crosses the
+ // edge instead of ending at it. Perhaps we can figure out a different way
+ // to represent this.
+ let xfrac = scale_up(xclip).max(NUDGE_FACTOR);
+ let packed = Point::new(xfrac, yclip);
+
+ push_tile(x, y, last_packed, packed);
+
+ // Flip y between top and bottom of tile (i.e. from TILE_HEIGHT
+ // to 0 or 0 to TILE_HEIGHT).
+ last_packed = Point::new(packed.x, packed.y + flip);
+ y += sign;
+ }
+
+ // Push the last tile, which might be at a fractional y offset.
+ let yfrac1 = scale_up(s1.y - y);
+ let packed1 = Point::new(xfrac1, yfrac1);
+
+ push_tile(x, y, last_packed, packed1);
+ }
+ } else if tile_count_y == 1 {
+ // A horizontal row.
+ // Same explanations apply as above, but instead in the horizontal direction.
+
+ let slope = (s1.y - s0.y) / (s1.x - s0.x);
+ let sign = (s1.x - s0.x).signum();
+
+ let mut yclip0 = (s0.y - y) + (x - s0.x) * slope;
+ let (xclip, flip) = if sign > 0.0 {
+ yclip0 += slope;
+ (scale_up(1.0), scale_up(-1.0))
+ } else {
+ (scale_up(0.0), scale_up(1.0))
+ };
+
+ let mut last_packed = packed0;
+
+ for i in 0..tile_count_x - 1 {
+ let yclip = yclip0 + i as f32 * sign * slope;
+ let yfrac = scale_up(yclip).max(NUDGE_FACTOR);
+ let packed = Point::new(xclip, yfrac);
+
+ push_tile(x, y, last_packed, packed);
+
+ last_packed = Point::new(packed.x + flip, packed.y);
+
+ x += sign;
+ }
+
+ let xfrac1 = scale_up(s1.x - x);
+ let yfrac1 = scale_up(s1.y - y);
+ let packed1 = Point::new(xfrac1, yfrac1);
+
+ push_tile(x, y, last_packed, packed1);
+ } else {
+ // General case (i.e. more than one tile covered in both directions). We perform a DDA
+ // to "walk" along the path and find out which tiles are intersected by the line
+ // and at which positions.
+
+ let recip_dx = 1.0 / (s1.x - s0.x);
+ let sign_x = (s1.x - s0.x).signum();
+ let recip_dy = 1.0 / (s1.y - s0.y);
+ let sign_y = (s1.y - s0.y).signum();
+
+ // How much we advance at each intersection with a vertical grid line.
+ let mut t_clipx = (x - s0.x) * recip_dx;
+
+ // Similarly to the case "horizontal column", if the line goes to the right,
+ // we will always intersect the tiles on the right side (except for perhaps the last
+ // tile, but this case is handled separately in the end). Otherwise, we always intersect
+ // on the left side.
+ let (xclip, flip_x) = if sign_x > 0.0 {
+ t_clipx += recip_dx;
+ (scale_up(1.0), scale_up(-1.0))
+ } else {
+ (scale_up(0.0), scale_up(1.0))
+ };
+
+ // How much we advance at each intersection with a horizontal grid line.
+ let mut t_clipy = (y - s0.y) * recip_dy;
+
+ // Same as xclip, but for the vertical direction, analogously to the
+ // "vertical column" case.
+ let (yclip, flip_y) = if sign_y > 0.0 {
+ t_clipy += recip_dy;
+ (scale_up(1.0), scale_up(-1.0))
+ } else {
+ (scale_up(0.0), scale_up(1.0))
+ };
+
+ // x and y coordinates of the target tile.
+ let x1 = x + (tile_count_x - 1) as f32 * sign_x;
+ let y1 = y + (tile_count_y - 1) as f32 * sign_y;
+ let mut xi = x;
+ let mut yi = y;
+ let mut last_packed = packed0;
+
+ loop {
+ // See https://github.com/LaurenzV/cpu-sparse-experiments/issues/46
+ // for why we don't just use an inequality check.
+ let x_cond = if sign_x > 0.0 { xi >= x1 } else { xi <= x1 };
+ let y_cond = if sign_y > 0.0 { yi >= y1 } else { yi <= y1 };
+
+ if x_cond && y_cond {
+ break;
+ }
+
+ if t_clipy < t_clipx {
+ // Intersected with a horizontal grid line.
+ let x_intersect = s0.x + (s1.x - s0.x) * t_clipy - xi;
+ let xfrac = scale_up(x_intersect).max(NUDGE_FACTOR);
+ let packed = Point::new(xfrac, yclip);
+
+ push_tile(xi, yi, last_packed, packed);
+
+ t_clipy += recip_dy.abs();
+ yi += sign_y;
+ last_packed = Point::new(packed.x, packed.y + flip_y);
+ } else {
+ // Intersected with vertical grid line.
+ let y_intersect = s0.y + (s1.y - s0.y) * t_clipx - yi;
+ let yfrac = scale_up(y_intersect).max(NUDGE_FACTOR);
+ let packed = Point::new(xclip, yfrac);
+
+ push_tile(xi, yi, last_packed, packed);
+
+ t_clipx += recip_dx.abs();
+ xi += sign_x;
+ last_packed = Point::new(packed.x + flip_x, packed.y);
+ }
+ }
+
+ // The last tile, where the end point is possibly not at an integer coordinate.
+ let xfrac1 = scale_up(s1.x - xi);
+ let yfrac1 = scale_up(s1.y - yi);
+ let packed1 = Point::new(xfrac1, yfrac1);
+
+ push_tile(xi, yi, last_packed, packed1);
+ }
+ }
+
+ // This particular choice of sentinel tiles generates a sentinel strip.
+ push_tile(
+ 0x3ffd as f32,
+ 0x3fff as f32,
+ Point::new(0.0, 0.0),
+ Point::new(0.0, 0.0),
+ );
+ push_tile(
+ 0x3fff as f32,
+ 0x3fff as f32,
+ Point::new(0.0, 0.0),
+ Point::new(0.0, 0.0),
+ );
+ }
+}
+
+/// An index into a sorted tile buffer.
+#[derive(Clone, Debug)]
+struct TileIndex {
+ x: u16,
+ y: u16,
+ index: u32,
+}
+
+impl TileIndex {
+ pub(crate) fn from_tile(index: u32, tile: &Tile) -> Self {
+ let x = (tile.x + 1).max(0) as u16;
+ let y = tile.y;
+
+ Self { x, y, index }
+ }
+
+ pub(crate) fn cmp(&self, b: &Self) -> std::cmp::Ordering {
+ let xya = ((self.y as u32) << 16) + (self.x as u32);
+ let xyb = ((b.y as u32) << 16) + (b.x as u32);
+ xya.cmp(&xyb)
+ }
+
+ pub(crate) fn index(&self) -> usize {
+ self.index as usize
+ }
+}
+
+#[cfg(test)]
+const _: () = if TILE_WIDTH_SCALE != TILE_HEIGHT_SCALE {
+ panic!("Can only handle square tiles for now.");
+};
+
+/// Scale a tile coordinate to a viewport coordinate. Note this assumes tiles are square.
+const fn scale_up(z: f32) -> f32 {
+ z * TILE_WIDTH_SCALE
+}
+
+/// Scale a viewport coordinate to a tile coordinate.
+const fn scale_down(z: Point) -> Point {
+ Point::new(z.x * INV_TILE_WIDTH_SCALE, z.y * INV_TILE_HEIGHT_SCALE)
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::flatten::{Line, Point};
+ use crate::footprint::Footprint;
+ use crate::tile::{scale_up, Tile, Tiles};
+
+ impl Footprint {
+ pub(crate) fn is_empty(&self) -> bool {
+ self.0 == 0
+ }
+ }
+
+ #[test]
+ fn footprint_at_tile_edge() {
+ let tile = Tile::new(
+ 0,
+ 0,
+ Point::new(scale_up(1.0), scale_up(0.0)),
+ Point::new(scale_up(1.0), scale_up(1.0)),
+ );
+
+ assert!(tile.footprint().is_empty());
+ }
+
+ #[test]
+ fn footprints_in_tile() {
+ let mut tile = Tile::new(
+ 0,
+ 0,
+ Point::new(scale_up(0.5), scale_up(0.0)),
+ Point::new(scale_up(0.55), scale_up(1.0)),
+ );
+
+ assert_eq!(tile.footprint().x0(), 2);
+ assert_eq!(tile.footprint().x1(), 3);
+
+ tile = Tile::new(
+ 0,
+ 0,
+ Point::new(scale_up(0.1), scale_up(0.0)),
+ Point::new(scale_up(0.6), scale_up(1.0)),
+ );
+
+ assert_eq!(tile.footprint().x0(), 0);
+ assert_eq!(tile.footprint().x1(), 3);
+
+ tile = Tile::new(
+ 0,
+ 0,
+ Point::new(scale_up(0.0), scale_up(0.0)),
+ Point::new(scale_up(1.0), scale_up(1.0)),
+ );
+
+ assert_eq!(tile.footprint().x0(), 0);
+ assert_eq!(tile.footprint().x1(), 4);
+
+ tile = Tile::new(
+ 0,
+ 0,
+ Point::new(scale_up(0.74), scale_up(0.0)),
+ Point::new(scale_up(1.76), scale_up(1.0)),
+ );
+
+ assert_eq!(tile.footprint().x0(), 2);
+ assert_eq!(tile.footprint().x1(), 4);
+ }
+
+ #[test]
+ fn issue_46_infinite_loop() {
+ let line = Line {
+ p0: Point { x: 22.0, y: 552.0 },
+ p1: Point { x: 224.0, y: 388.0 },
+ };
+
+ let mut tiles = Tiles::new();
+ tiles.make_tiles(&[line]);
+ }
+}
