e4f86d11fe8a
pathgrad.rs
//! Path gradients (`a:path`) that follow a rectangle or the shape's own outline, which no vello
//! gradient draws: they're rasterised into a small image of the bounds and painted with it.
//!
//! Measured on PowerPoint's export (black to grey to white from the centre):
//! - `rect`: the colour position is the larger of the horizontal and vertical distances from the
//! focus, each as a share of the distance to that side's edge (X-shaped contours);
//! - `shape`: contours are the outline scaled about the focus (an ellipse gives ellipses, a
//! triangle triangles): the share of the way from the focus to the outline along the same ray.
//!
//! `circle` stays a radial vello gradient (see `paint::gradient`).
use std::sync::Arc;
use deckcraft_color::Rgba;
use kurbo::{Affine, BezPath, PathEl, Point, Rect};
use vello_cpu::{Pixmap, RenderContext, peniko};
/// Longest side of the rasterised gradient, in pixels (bilinear sampling smooths the rest).
const MAX_SIDE: f64 = 384.0;
/// Most pixel × outline-edge tests one `shape` gradient may cost; a denser outline is simplified
/// to fit (each pixel tests every edge).
const MAX_EDGE_WORK: u64 = 64_000_000;
/// Fewest edges a simplified polygon keeps, so a coarse outline still has a shape.
const MIN_POLY_EDGES: usize = 8;
/// Most points `polygons` keeps from one path; a path flattening past this (a huge finite curve) is
/// not drawn rather than held in memory first.
const MAX_POINTS: usize = 2_000_000;
/// Quads beyond one per cubic that a path's cubics may subdivide into before [`polygons`] refuses it.
const MAX_EXTRA_QUADS: f64 = 200_000.0;
/// Flattening tolerance of [`polygons`], in path units.
const FLATTEN_TOLERANCE: f64 = 0.25;
/// The edge budget for a `pw` x `ph` raster where each pixel tests every edge.
pub(crate) fn edge_budget(pw: u32, ph: u32) -> usize {
let pixels = u64::from(pw).saturating_mul(u64::from(ph)).max(1);
usize::try_from(MAX_EDGE_WORK / pixels).unwrap_or(usize::MAX).max(MIN_POLY_EDGES)
}
/// `pw` x `ph` cut down (aspect kept) until every pixel testing all of `edges` stays within
/// [`MAX_EDGE_WORK`]; the raster is stretched when painted, so a many-contour outline keeps every
/// contour at a coarser sampling.
pub(crate) fn fit_raster(edges: usize, pw: u32, ph: u32) -> (u32, u32) {
let work = u64::from(pw).saturating_mul(u64::from(ph)).saturating_mul(edges.max(1) as u64);
if work <= MAX_EDGE_WORK {
return (pw, ph);
}
let k = (MAX_EDGE_WORK as f64 / work as f64).sqrt();
let w = ((f64::from(pw) * k) as u32).max(1);
let h = ((f64::from(ph) * k) as u32).max(1);
// A side held at 1 pixel leaves the other to take the rest of the cut.
let room = |side: u32| u32::try_from(MAX_EDGE_WORK / u64::from(side).saturating_mul(edges.max(1) as u64).max(1)).unwrap_or(u32::MAX).max(1);
let w = w.min(room(h));
(w, h.min(room(w)))
}
/// Colour position (0 at the focus, 1 at the edge) of `p` for path `kind` in `bounds` with the
/// focus rect `focus` (fractions inset from left, top, right, bottom), `outline` being the
/// shape's flattened polygon(s) for `shape`.
pub fn position(kind: &str, bounds: Rect, focus: [f64; 4], outline: &[Vec<Point>], p: Point) -> f64 {
let f = Rect::new(
bounds.x0 + bounds.width() * focus[0].clamp(0.0, 1.0),
bounds.y0 + bounds.height() * focus[1].clamp(0.0, 1.0),
bounds.x1 - bounds.width() * focus[2].clamp(0.0, 1.0),
bounds.y1 - bounds.height() * focus[3].clamp(0.0, 1.0),
);
let f = if f.x0 <= f.x1 && f.y0 <= f.y1 { f } else { Rect::from_center_size(f.center(), (0.0, 0.0)) };
match kind {
"shape" if !outline.is_empty() => {
// A focus rectangle (not a point) is the first colour throughout, as PowerPoint draws
// it; outside, the colour runs from the rectangle's edge to the outline along the ray
// from its centre.
if f.width() > 1e-9 && f.height() > 1e-9 {
if f.contains(p) {
return 0.0;
}
let c = f.center();
let to_outline = shape_position(outline, c, p);
let d = (p - c).hypot();
if to_outline <= 0.0 || d <= 0.0 {
return 1.0;
}
// Where the ray leaves the focus rectangle, as a share of the way to `p`.
let v = p - c;
let kx = if v.x.abs() > 1e-12 { (f.width() / 2.0) / v.x.abs() } else { f64::INFINITY };
let ky = if v.y.abs() > 1e-12 { (f.height() / 2.0) / v.y.abs() } else { f64::INFINITY };
let rect_share = kx.min(ky).min(1.0);
// p is `to_outline` of the way to the outline; the rectangle edge `rect_share` of
// the way to p.
let outline_share = 1.0 / to_outline; // outline distance in units of |p - c|
return ((1.0 - rect_share) / (outline_share - rect_share).max(1e-9)).clamp(0.0, 1.0);
}
shape_position(outline, f.center(), p)
}
_ => {
// Distance outside the focus rect along each axis, over the room to that side's edge.
let axis = |v: f64, lo: f64, hi: f64, edge_lo: f64, edge_hi: f64| {
if v < lo {
(lo - v) / (lo - edge_lo).max(1e-9)
} else if v > hi {
(v - hi) / (edge_hi - hi).max(1e-9)
} else {
0.0
}
};
axis(p.x, f.x0, f.x1, bounds.x0, bounds.x1).max(axis(p.y, f.y0, f.y1, bounds.y0, bounds.y1)).clamp(0.0, 1.0)
}
}
}
/// The share of the way from `c` to the outline along the ray through `p` (1 when the ray meets
/// no edge).
fn shape_position(outline: &[Vec<Point>], c: Point, p: Point) -> f64 {
let d = p - c;
let len = d.hypot();
if len < 1e-9 {
return 0.0;
}
// The outline scaled about `c` by t reaches `p` first (smallest t) where the ray's farthest
// crossing does: the only crossing for a focus inside a convex outline, and the one that
// still works for a focus off the shape (a corner of an ellipse's box).
let mut best = f64::INFINITY;
for poly in outline {
for w in poly.windows(2) {
let (a, b) = (w[0], w[1]);
let e = b - a;
let den = d.cross(e);
if den.abs() < 1e-12 {
continue;
}
let ac = a - c;
let s = ac.cross(e) / den;
let u = ac.cross(d) / den;
if s > 1e-9 && (-1e-9..=1.0 + 1e-9).contains(&u) {
best = if best.is_finite() { best.max(s) } else { s };
}
}
}
if best.is_finite() { (1.0 / best).clamp(0.0, 1.0) } else { 1.0 }
}
/// The outline flattened into closed polygons.
pub fn polygons(path: &BezPath) -> Vec<Vec<Point>> {
// `kurbo::flatten` buffers all of a cubic's quads before calling back, and cannot be stopped
// once running, so bound the quads the cubics will make first (kurbo's own count: it splits
// cubics into quads at a tenth of the tolerance). An ordinary curve makes a few; only those
// past the first of each count.
let mut extra_quads = 0.0f64;
let mut at = Point::ZERO;
let mut start = Point::ZERO;
for el in path.iter() {
match el {
PathEl::MoveTo(p) => {
at = p;
start = p;
}
PathEl::LineTo(p) | PathEl::QuadTo(_, p) => at = p,
PathEl::CurveTo(a, b, p) => {
let err = ((b.to_vec2() * 3.0 - p.to_vec2()) - (a.to_vec2() * 3.0 - at.to_vec2())).hypot2();
extra_quads += (err / (432.0 * (FLATTEN_TOLERANCE * 0.1).powi(2))).powf(1.0 / 6.0).ceil().max(1.0) - 1.0;
// A non-finite estimate is over the limit too.
if extra_quads.is_nan() || extra_quads > MAX_EXTRA_QUADS {
return Vec::new();
}
at = p;
}
PathEl::ClosePath => at = start,
}
}
let mut out: Vec<Vec<Point>> = Vec::new();
let mut cur: Vec<Point> = Vec::new();
let mut total = 0usize;
kurbo::flatten(path.iter(), FLATTEN_TOLERANCE, |el| {
total += 1;
if total > MAX_POINTS {
return;
}
match el {
PathEl::MoveTo(p) => {
if cur.len() > 1 {
out.push(std::mem::take(&mut cur));
}
cur = vec![p];
}
PathEl::LineTo(p) => cur.push(p),
PathEl::ClosePath => {
if let Some(f) = cur.first().copied() {
cur.push(f);
}
}
_ => {}
}
});
if total > MAX_POINTS {
return Vec::new();
}
if cur.len() > 1 {
out.push(cur);
}
for poly in &mut out {
if let (Some(f), Some(l)) = (poly.first().copied(), poly.last().copied())
&& (f - l).hypot() > 1e-9
{
poly.push(f);
}
}
out.retain(|p| p.len() > 2 && p.len() < 100_000);
out
}
/// `outline` cut down to at most about `max_edges` edges in total: first by dropping points
/// closer than `tol` to the last kept one (detail finer than a raster pixel), then, if still too
/// many, by keeping every k-th point (a polygon too small to thin stays whole, and none is
/// dropped). Each polygon stays closed. Returns it unchanged when it fits.
pub(crate) fn simplify(outline: Vec<Vec<Point>>, tol: f64, max_edges: usize) -> Vec<Vec<Point>> {
let edges = |o: &[Vec<Point>]| o.iter().map(|p| p.len().saturating_sub(1)).sum::<usize>();
if edges(&outline) <= max_edges {
return outline;
}
let tol = if tol.is_finite() && tol > 0.0 { tol } else { 0.0 };
let mut out: Vec<Vec<Point>> = outline
.into_iter()
.map(|poly| {
let mut kept: Vec<Point> = Vec::with_capacity(poly.len());
let last = poly.last().copied();
for p in poly {
if kept.last().is_none_or(|q| (p - *q).hypot() >= tol) {
kept.push(p);
}
}
if let (Some(l), Some(k)) = (last, kept.last().copied())
&& k != l
{
kept.push(l);
}
kept
})
.filter(|p| p.len() > 2)
.collect();
let total = edges(&out);
if total > max_edges {
let k = total.div_ceil(max_edges.max(1)).max(2);
for poly in &mut out {
let n = poly.len();
if n <= MIN_POLY_EDGES + 1 {
continue;
}
let k = k.min((n - 1) / MIN_POLY_EDGES).max(1);
let last = poly.last().copied();
let mut kept: Vec<Point> = poly.iter().step_by(k).copied().collect();
if let (Some(l), Some(q)) = (last, kept.last().copied())
&& q != l
{
kept.push(l);
}
*poly = kept;
}
// Polygons too small to thin stay whole, so the total can still exceed `max_edges`: the
// caller shrinks its raster ([`fit_raster`]) rather than lose contours.
}
out
}
/// A 256-entry colour ramp for the sorted, already expanded `stops` (linear in sRGB between them).
pub fn ramp(stops: &[(f64, Rgba)]) -> Vec<Rgba> {
(0..256)
.map(|i| {
let t = i as f64 / 255.0;
let after = stops.iter().position(|s| s.0 >= t);
match after {
Some(0) | None => stops.get(after.unwrap_or(stops.len().saturating_sub(1))).map(|s| s.1).unwrap_or(Rgba::BLACK),
Some(j) => {
let (Some(a), Some(b)) = (stops.get(j - 1), stops.get(j)) else { return Rgba::BLACK };
let k = if b.0 - a.0 > 1e-12 { (t - a.0) / (b.0 - a.0) } else { 1.0 };
a.1.lerp(b.1, k)
}
}
})
.collect()
}
/// Fill `path` with a `rect` or `shape` path gradient of `stops` (sorted and expanded, see
/// `ramp::expand`) over `bounds`, faded by `alpha`; `m` maps the path to the output.
#[allow(clippy::too_many_arguments)]
pub fn fill(ctx: &mut RenderContext, kind: &str, focus: [f64; 4], stops: &[(f64, Rgba)], bounds: Rect, path: &BezPath, m: Affine, alpha: f64) {
if bounds.width() <= 0.0 || bounds.height() <= 0.0 || !bounds.is_finite() || stops.is_empty() {
return;
}
let k = crate::scale_of(m);
let k = if k.is_finite() && k > 0.0 { k } else { 1.0 };
let longest = bounds.width().max(bounds.height()) * k;
let s = (MAX_SIDE / longest).min(1.0) * k;
let (pw, ph) = (((bounds.width() * s).ceil() as u32).clamp(1, 4096), ((bounds.height() * s).ceil() as u32).clamp(1, 4096));
let (outline, pw, ph) = if kind == "shape" {
let max_edges = edge_budget(pw, ph);
let pixel = (bounds.width() / f64::from(pw)).min(bounds.height() / f64::from(ph));
let o = simplify(polygons(path), pixel, max_edges);
let (pw, ph) = fit_raster(o.iter().map(|p| p.len().saturating_sub(1)).sum(), pw, ph);
(o, pw, ph)
} else {
(Vec::new(), pw, ph)
};
// An outline `polygons` refused (too many points) has no contours: skip the shape rather than
// paint it with the rectangle fallback's different gradient.
if kind == "shape" && outline.is_empty() {
return;
}
let lut = ramp(stops);
let a = alpha.clamp(0.0, 1.0);
let mut data = Vec::with_capacity((pw * ph) as usize);
for j in 0..ph {
for i in 0..pw {
let p = Point::new(bounds.x0 + (i as f64 + 0.5) / pw as f64 * bounds.width(), bounds.y0 + (j as f64 + 0.5) / ph as f64 * bounds.height());
let t = position(kind, bounds, focus, &outline, p);
let c = lut.get((t * 255.0).round().clamp(0.0, 255.0) as usize).copied().unwrap_or(Rgba::BLACK);
let ca = (c.a as f64 * a).round().clamp(0.0, 255.0);
let mul = |v: u8| (v as f64 * ca / 255.0).round().clamp(0.0, 255.0) as u8;
data.push(vello_cpu::color::PremulRgba8 { r: mul(c.r), g: mul(c.g), b: mul(c.b), a: ca as u8 });
}
}
let pm = Arc::new(Pixmap::from_parts(data, pw as u16, ph as u16));
ctx.set_transform(m);
ctx.set_paint(vello_cpu::Image {
image: vello_cpu::ImageSource::Pixmap(pm),
sampler: peniko::ImageSampler { quality: peniko::ImageQuality::Medium, ..Default::default() },
});
ctx.set_paint_transform(
Affine::translate(bounds.origin().to_vec2()) * Affine::scale_non_uniform(bounds.width() / pw as f64, bounds.height() / ph as f64),
);
ctx.fill_path(path);
ctx.reset_paint_transform();
}
#[cfg(test)]
mod tests {
use super::*;
use kurbo::Shape;
const CENTRE: [f64; 4] = [0.5, 0.5, 0.5, 0.5];
#[test]
fn rect_paths_take_the_larger_axis_share() {
// PowerPoint, 280x200 box from the centre: 20 px across is 1/7, 20 px down is 1/5.
let b = Rect::new(0.0, 0.0, 280.0, 200.0);
let at = |x: f64, y: f64| position("rect", b, CENTRE, &[], Point::new(x, y));
assert!((at(160.0, 100.0) - 20.0 / 140.0).abs() < 1e-9);
assert!((at(140.0, 120.0) - 20.0 / 100.0).abs() < 1e-9);
assert!((at(168.0, 120.0) - 0.2).abs() < 1e-9, "the diagonal takes the larger share");
assert_eq!(at(0.0, 0.0), 1.0);
// From a corner (fillToRect 0,0,100%,100%): the far corner is the end.
let corner = [0.0, 0.0, 1.0, 1.0];
assert!((position("rect", b, corner, &[], Point::new(140.0, 50.0)) - 0.5).abs() < 1e-9);
}
#[test]
fn shape_paths_follow_the_outline() {
let b = Rect::new(0.0, 0.0, 280.0, 200.0);
let ellipse = polygons(&kurbo::Ellipse::from_rect(b).to_path(0.01));
let at = |x: f64, y: f64| position("shape", b, CENTRE, &ellipse, Point::new(x, y));
assert!((at(160.0, 100.0) - 20.0 / 140.0).abs() < 0.01);
assert!((at(140.0, 120.0) - 0.2).abs() < 0.01);
// Half way to the outline along any ray is 0.5.
let (dx, dy) = (140.0 * 0.6, 100.0 * 0.8);
assert!((at(140.0 + dx * 0.5, 100.0 + dy * 0.5) - 0.5).abs() < 0.01);
// A triangle: half way from its centre to its apex is 0.5.
let mut tri = BezPath::new();
tri.move_to((140.0, 0.0));
tri.line_to((280.0, 200.0));
tri.line_to((0.0, 200.0));
tri.close_path();
let polys = polygons(&tri);
assert!((position("shape", b, CENTRE, &polys, Point::new(140.0, 50.0)) - 0.5).abs() < 1e-6);
}
#[test]
fn shape_paths_from_off_the_shape_or_a_focus_box() {
let b = Rect::new(0.0, 0.0, 280.0, 200.0);
let ellipse = polygons(&kurbo::Ellipse::from_rect(b).to_path(0.01));
// Focus on the box's corner, outside the ellipse: contours are the ellipse shrunk towards
// the corner, so its far edge is the end and its middle part way (it was all the end
// colour).
let corner = [0.0, 0.0, 1.0, 1.0];
let mid = position("shape", b, corner, &ellipse, Point::new(140.0, 100.0));
assert!(mid > 0.3 && mid < 0.8, "{mid}");
assert!(position("shape", b, corner, &ellipse, Point::new(279.0, 100.0)) > 0.95);
// A focus rectangle is the first colour inside, and the colour runs from its edge out.
let boxed = [0.25, 0.25, 0.25, 0.25];
assert_eq!(position("shape", b, boxed, &ellipse, Point::new(150.0, 110.0)), 0.0);
let half = position("shape", b, boxed, &ellipse, Point::new(140.0 + 70.0 + 35.0, 100.0));
assert!((half - 0.5).abs() < 0.02, "{half}");
}
fn many_segment_square(n: usize) -> BezPath {
// A 200x200 square whose sides are split into `n` segments each.
let mut p = BezPath::new();
p.move_to((0.0, 0.0));
let corners = [(200.0, 0.0), (200.0, 200.0), (0.0, 200.0), (0.0, 0.0)];
let mut from = (0.0, 0.0);
for to in corners {
for i in 1..=n {
let t = i as f64 / n as f64;
p.line_to((from.0 + (to.0 - from.0) * t, from.1 + (to.1 - from.1) * t));
}
from = to;
}
p.close_path();
p
}
#[test]
fn dense_outlines_are_simplified_to_the_work_budget() {
// Below the per-polygon flatten cap, so the simplifier has to do the work.
let polys = polygons(&many_segment_square(20_000));
assert!(polys.iter().map(|p| p.len() - 1).sum::<usize>() >= 80_000);
let b = Rect::new(0.0, 0.0, 200.0, 200.0);
let simple = simplify(polys, 200.0 / 384.0, 400);
let edges: usize = simple.iter().map(|p| p.len() - 1).sum();
assert!((MIN_POLY_EDGES..=400).contains(&edges), "{edges}");
// Still the square: half way to a side or a corner is 0.5.
for q in [Point::new(150.0, 100.0), Point::new(150.0, 150.0), Point::new(100.0, 50.0)] {
let t = position("shape", b, CENTRE, &simple, q);
assert!((t - 0.5).abs() < 0.01, "{q:?} {t}");
}
// Small outlines pass through untouched.
let tri = vec![vec![Point::new(0.0, 0.0), Point::new(1.0, 0.0), Point::new(0.0, 1.0), Point::new(0.0, 0.0)]];
assert_eq!(simplify(tri.clone(), 10.0, 400), tri);
}
#[test]
fn a_dense_shape_gradient_renders_promptly() {
let path = many_segment_square(20_000);
let mut ctx = RenderContext::new(400, 400);
let stops = [(0.0, Rgba::rgb(0, 0, 0)), (1.0, Rgba::rgb(255, 255, 255))];
let t = std::time::Instant::now();
fill(&mut ctx, "shape", CENTRE, &stops, Rect::new(0.0, 0.0, 200.0, 200.0), &path, Affine::scale(2.0), 1.0);
// Unbudgeted this is 147k pixels × 80k edges ≈ 1.2e10 tests (minutes); budgeted, well under a second in release.
assert!(t.elapsed() < std::time::Duration::from_secs(20), "{:?}", t.elapsed());
}
#[test]
fn a_shape_gradient_with_no_usable_outline_paints_nothing() {
// One polygon over the per-polygon cap is dropped by `polygons`.
let path = many_segment_square(26_000);
assert!(polygons(&path).is_empty());
let mut ctx = RenderContext::new(64, 64);
let stops = [(0.0, Rgba::rgb(0, 0, 0)), (1.0, Rgba::rgb(255, 255, 255))];
fill(&mut ctx, "shape", CENTRE, &stops, Rect::new(0.0, 0.0, 64.0, 64.0), &path, Affine::IDENTITY, 1.0);
ctx.flush();
let mut px = vec![0u8; 64 * 64 * 4];
ctx.render(vello_cpu::PixmapMut::new(64, 64, &mut px).unwrap(), &mut vello_cpu::Resources::new());
assert!(px.chunks(4).all(|p| p[3] == 0), "nothing was painted");
}
#[test]
fn the_ramp_runs_through_the_stops() {
let stops = [(0.0, Rgba::rgb(0, 0, 0)), (0.5, Rgba::rgb(128, 128, 128)), (1.0, Rgba::rgb(255, 255, 255))];
let r = ramp(&stops);
assert_eq!(r.len(), 256);
assert_eq!(r[0], Rgba::rgb(0, 0, 0));
assert_eq!(r[255], Rgba::rgb(255, 255, 255));
assert!((r[64].r as i32 - 64).abs() <= 2);
assert!(ramp(&[(0.3, Rgba::rgb(9, 9, 9))]).iter().all(|c| *c == Rgba::rgb(9, 9, 9)));
}
#[test]
fn huge_cubics_are_refused_before_flattening() {
let mut p = BezPath::new();
p.move_to((0.0, 0.0));
// About 250,000 quads each: over the limit.
for _ in 0..3 {
p.curve_to((1e15, -1e15), (-1e15, 1e15), (1.0, 1.0));
}
p.close_path();
assert!(polygons(&p).is_empty());
// A cubic of ordinary size still flattens.
let mut q = BezPath::new();
q.move_to((0.0, 0.0));
q.curve_to((100.0, 0.0), (100.0, 100.0), (0.0, 100.0));
q.close_path();
assert_eq!(polygons(&q).len(), 1);
}
#[test]
fn many_contours_keep_every_contour_at_a_coarser_raster() {
let square = |x: f64| vec![Point::new(x, 0.0), Point::new(x + 1.0, 0.0), Point::new(x + 1.0, 1.0), Point::new(x, 1.0), Point::new(x, 0.0)];
let polys: Vec<Vec<Point>> = (0..100).map(|i| square(f64::from(i) * 2.0)).collect();
let simple = simplify(polys, 0.001, 244);
assert_eq!(simple.len(), 100, "no contour is dropped");
let (pw, ph) = fit_raster(400, 512, 512);
assert!(u64::from(pw) * u64::from(ph) * 400 <= MAX_EDGE_WORK && pw > 100, "{pw}x{ph}");
assert_eq!(fit_raster(200, 512, 512), (512, 512));
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.