Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.
TypeScript agentaiai-agentsall-in-onecrmcrm-systememaillinearmcpmessagingnotesnotionofficerustslackslack-alternativestartupstartup-toolstypescriptworkspace
//! Drawing axial, radial, and function-based shadings pixel by pixel, the
//! color tables they share with meshes, and blending into a premultiplied
//! pixmap.
use super::Shading;
use crate::color::{ColorSpace, to_u8};
use crate::function::{Function, MAX_ARITY};
/// Color table entries for a gradient at least, and at most.
const MIN_SAMPLES: usize = 256;
const MAX_SAMPLES: usize = 4096;
/// Grid points along each side of a function-based shading, at most.
const MAX_GRID: usize = 256;
/// Samples taken along a gradient to find its stops.
const STOP_SAMPLES: usize = 256;
/// How far (sRGB, `0..=1`) colors between stops may stray from a straight
/// line between them.
const STOP_TOLERANCE: f32 = 0.5 / 255.0;
/// An affine map `[a b c d e f]`: `x' = a x + c y + e`, `y' = b x + d y + f`.
#[derive(Clone, Copy, Debug, PartialEq)]
pub(super) struct Affine(pub(super) [f64; 6]);
impl Affine {
pub(super) fn from_transform(t: tiny_skia::Transform) -> Option<Affine> {
let m = [t.sx, t.ky, t.kx, t.sy, t.tx, t.ty].map(f64::from);
m.iter().all(|v| v.is_finite()).then_some(Affine(m))
}
pub(super) fn from_matrix(m: [f32; 6]) -> Affine {
Affine(m.map(f64::from))
}
/// This map, then `next`.
pub(super) fn then(self, next: Affine) -> Affine {
let [a, b, c, d, e, f] = self.0;
let [na, nb, nc, nd, ne, nf] = next.0;
Affine([
na * a + nc * b,
nb * a + nd * b,
na * c + nc * d,
nb * c + nd * d,
na * e + nc * f + ne,
nb * e + nd * f + nf,
])
}
pub(super) fn invert(self) -> Option<Affine> {
let [a, b, c, d, e, f] = self.0;
let det = a * d - b * c;
if det == 0.0 || !det.is_finite() {
return None;
}
let (ia, ib, ic, id) = (d / det, -b / det, -c / det, a / det);
Some(Affine([
ia,
ib,
ic,
id,
-(ia * e + ic * f),
-(ib * e + id * f),
]))
}
pub(super) fn map(self, x: f64, y: f64) -> (f64, f64) {
let [a, b, c, d, e, f] = self.0;
(a * x + c * y + e, b * x + d * y + f)
}
/// Maps a direction (no translation).
pub(super) fn map_vector(self, x: f64, y: f64) -> f64 {
let [a, b, c, d, ..] = self.0;
(a * x + c * y).hypot(b * x + d * y)
}
/// How much lengths grow at most.
pub(super) fn scale(self) -> f64 {
self.map_vector(1.0, 0.0).max(self.map_vector(0.0, 1.0))
}
}
/// A rectangle of pixels, `x0..x1` by `y0..y1`.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct Rect {
pub(super) x0: usize,
pub(super) y0: usize,
pub(super) x1: usize,
pub(super) y1: usize,
}
impl Rect {
pub(super) fn intersect(self, other: Rect) -> Option<Rect> {
let r = Rect {
x0: self.x0.max(other.x0),
y0: self.y0.max(other.y0),
x1: self.x1.min(other.x1),
y1: self.y1.min(other.y1),
};
(r.x0 < r.x1 && r.y0 < r.y1).then_some(r)
}
/// The pixels a device-space box touches.
pub(super) fn covering(min: (f64, f64), max: (f64, f64)) -> Option<Rect> {
let clamp = |v: f64| v.clamp(0.0, f64::from(u32::MAX)) as usize;
if !(min.0.is_finite() && min.1.is_finite() && max.0.is_finite() && max.1.is_finite()) {
return None;
}
let r = Rect {
x0: clamp(min.0.floor()),
y0: clamp(min.1.floor()),
x1: clamp(max.0.ceil()),
y1: clamp(max.1.ceil()),
};
(r.x0 < r.x1 && r.y0 < r.y1).then_some(r)
}
/// The pixels a shading-space box covers on the device.
pub(super) fn of_box(b: [f32; 4], to_device: Affine) -> Option<Rect> {
let [x0, y0, x1, y1] = b.map(f64::from);
let corners = [(x0, y0), (x1, y0), (x0, y1), (x1, y1)].map(|(x, y)| to_device.map(x, y));
let min = corners
.iter()
.fold((f64::MAX, f64::MAX), |m, p| (m.0.min(p.0), m.1.min(p.1)));
let max = corners
.iter()
.fold((f64::MIN, f64::MIN), |m, p| (m.0.max(p.0), m.1.max(p.1)));
Rect::covering(min, max)
}
}
/// Where shading colors land: a premultiplied RGBA8 pixmap, the clip, and
/// the opacity.
pub(super) struct Target<'a> {
data: &'a mut [u8],
width: usize,
height: usize,
clip: Option<&'a tiny_skia::Mask>,
/// Opacity, `0..=255`.
alpha: u32,
}
impl<'a> Target<'a> {
pub(super) fn new(
data: &'a mut [u8],
width: u32,
height: u32,
clip: Option<&'a tiny_skia::Mask>,
alpha: f32,
) -> Target<'a> {
Target {
data,
width: width as usize,
height: height as usize,
clip,
alpha: (alpha.clamp(0.0, 1.0) * 255.0 + 0.5) as u32,
}
}
/// The pixels worth visiting: the pixmap, narrowed to where the clip
/// covers.
pub(super) fn bounds(&self) -> Option<Rect> {
let all = Rect {
x0: 0,
y0: 0,
x1: self.width,
y1: self.height,
};
let Some(mask) = self.clip else {
return (self.width > 0 && self.height > 0).then_some(all);
};
let mw = mask.width() as usize;
let (w, h) = (self.width.min(mw), self.height.min(mask.height() as usize));
let data = mask.data();
let mut found: Option<Rect> = None;
for y in 0..h {
let row = &data[y * mw..y * mw + w];
let Some(first) = row.iter().position(|&v| v != 0) else {
continue;
};
let last = row.iter().rposition(|&v| v != 0).unwrap_or(first);
let r = found.get_or_insert(Rect {
x0: first,
y0: y,
x1: last + 1,
y1: y + 1,
});
r.x0 = r.x0.min(first);
r.x1 = r.x1.max(last + 1);
r.y1 = y + 1;
}
found
}
/// Opacity at a pixel (`0..=255`): the clip's coverage times alpha.
pub(super) fn coverage(&self, x: usize, y: usize) -> u32 {
match self.clip {
None => self.alpha,
Some(mask) => {
let mw = mask.width() as usize;
if x >= mw {
return 0;
}
let c = mask.data().get(y * mw + x).copied().unwrap_or(0);
(u32::from(c) * self.alpha + 127) / 255
}
}
}
/// Blends an opaque color over a pixel at opacity `a` (`0..=255`).
pub(super) fn blend(&mut self, x: usize, y: usize, rgb: [u8; 3], a: u32) {
let at = (y * self.width + x) * 4;
let Some(px) = self.data.get_mut(at..at + 4) else {
return;
};
if a >= 255 {
px.copy_from_slice(&[rgb[0], rgb[1], rgb[2], 255]);
return;
}
let keep = 255 - a;
for (d, s) in px.iter_mut().zip([rgb[0], rgb[1], rgb[2], 255]) {
*d = ((u32::from(s) * a + u32::from(*d) * keep + 127) / 255) as u8;
}
}
}
/// Whether a shading-space point is inside the shading's `BBox`.
pub(super) fn in_box(bbox: Option<[f32; 4]>, x: f64, y: f64) -> bool {
bbox.is_none_or(|[x0, y0, x1, y1]| {
x >= f64::from(x0) && x <= f64::from(x1) && y >= f64::from(y0) && y <= f64::from(y1)
})
}
/// Paints each pixel of `rect` whose center maps (through `to_shading`)
/// into the box to the color `color_at` gives for that point, if any.
fn fill(
target: &mut Target<'_>,
rect: Rect,
to_shading: Affine,
bbox: Option<[f32; 4]>,
mut color_at: impl FnMut(f64, f64) -> Option<[u8; 3]>,
) {
let [a, b, c, d, e, f] = to_shading.0;
for y in rect.y0..rect.y1 {
let py = y as f64 + 0.5;
let px = rect.x0 as f64 + 0.5;
let (mut sx, mut sy) = (a * px + c * py + e, b * px + d * py + f);
for x in rect.x0..rect.x1 {
let cover = target.coverage(x, y);
if cover > 0
&& in_box(bbox, sx, sy)
&& let Some(rgb) = color_at(sx, sy)
{
target.blend(x, y, rgb, cover);
}
sx += a;
sy += b;
}
}
}
/// The region a shading may paint: the target's, within its `BBox`.
fn region(sh: &Shading, target: &Target<'_>, to_device: Affine) -> Option<Rect> {
let rect = target.bounds()?;
match sh.bbox {
Some(b) => rect.intersect(Rect::of_box(b, to_device)?),
None => Some(rect),
}
}
/// Colors along a gradient: entry `i` of `n` is the color at
/// `t = t0 + (t1 - t0) i / (n - 1)`.
pub(super) struct Lut {
colors: Vec<[u8; 3]>,
}
impl Lut {
/// The colors `function` gives over `domain`.
pub(super) fn new(
cs: &ColorSpace,
function: &Function,
domain: [f32; 2],
samples: usize,
) -> Lut {
Lut::over(domain, samples, |t| rgb_at(cs, function, t))
}
/// The colors of a one-component space over `range`.
pub(super) fn of_space(cs: &ColorSpace, range: [f32; 2], samples: usize) -> Lut {
Lut::over(range, samples, |v| cs.to_rgb(&[v]))
}
fn over(domain: [f32; 2], samples: usize, color: impl Fn(f32) -> [f32; 3]) -> Lut {
let samples = samples.clamp(2, MAX_SAMPLES);
let colors = (0..samples)
.map(|i| {
let s = i as f32 / (samples - 1) as f32;
color(domain[0] + s * (domain[1] - domain[0])).map(to_u8)
})
.collect();
Lut { colors }
}
/// Entries for a gradient `length` device pixels long.
pub(super) fn samples_for(length: f64) -> usize {
if length.is_finite() {
(length.ceil() as usize)
.saturating_add(1)
.clamp(MIN_SAMPLES, MAX_SAMPLES)
} else {
MAX_SAMPLES
}
}
/// The color at `s` (`0..=1` along the table); past the ends only
/// where extended.
pub(super) fn at(&self, s: f64, extend: [bool; 2]) -> Option<[u8; 3]> {
let s = if s < 0.0 {
if !extend[0] {
return None;
}
0.0
} else if s > 1.0 {
if !extend[1] {
return None;
}
1.0
} else if s.is_nan() {
return None;
} else {
s
};
let last = self.colors.len() - 1;
Some(self.colors[((s * last as f64 + 0.5) as usize).min(last)])
}
}
/// The color a function gives at `t`, as sRGB.
pub(super) fn rgb_at(cs: &ColorSpace, function: &Function, t: f32) -> [f32; 3] {
let mut out = [0.0f32; MAX_ARITY];
function.eval_into(&[t], &mut out);
cs.to_rgb(&out[..cs.components().min(MAX_ARITY)])
}
pub(super) fn axial(
sh: &Shading,
target: &mut Target<'_>,
to_device: Affine,
coords: [f32; 4],
domain: [f32; 2],
function: &Function,
extend: [bool; 2],
) {
let [x0, y0, x1, y1] = coords.map(f64::from);
let (dx, dy) = (x1 - x0, y1 - y0);
let len2 = dx * dx + dy * dy;
let (Some(rect), Some(to_shading)) = (region(sh, target, to_device), to_device.invert()) else {
return;
};
if len2 == 0.0 || !len2.is_finite() {
return;
}
let lut = Lut::new(
&sh.color_space,
function,
domain,
Lut::samples_for(to_device.map_vector(dx, dy)),
);
fill(target, rect, to_shading, sh.bbox, |x, y| {
lut.at(((x - x0) * dx + (y - y0) * dy) / len2, extend)
});
}
pub(super) fn radial(
sh: &Shading,
target: &mut Target<'_>,
to_device: Affine,
coords: [f32; 6],
domain: [f32; 2],
function: &Function,
extend: [bool; 2],
) {
let [x0, y0, r0, x1, y1, r1] = coords.map(f64::from);
let (Some(rect), Some(to_shading)) = (region(sh, target, to_device), to_device.invert()) else {
return;
};
let (cx, cy, dr) = (x1 - x0, y1 - y0, r1 - r0);
let a = cx * cx + cy * cy - dr * dr;
// Below this, the circles are tangent inside one another and the
// equation for `s` is linear.
let flat = 1e-9 * (cx * cx + cy * cy + dr * dr);
let length = (to_device.map_vector(cx, cy) + to_device.scale() * dr.abs())
.max(to_device.scale() * r0.max(r1));
let lut = Lut::new(&sh.color_space, function, domain, Lut::samples_for(length));
let ok = |s: f64| r0 + s * dr >= 0.0 && (s >= 0.0 || extend[0]) && (s <= 1.0 || extend[1]);
fill(target, rect, to_shading, sh.bbox, |x, y| {
// The largest `s` whose circle (center c0 + s (c1 - c0), radius
// r0 + s (r1 - r0)) passes through the point.
let (px, py) = (x - x0, y - y0);
let b = px * cx + py * cy + r0 * dr;
let c = px * px + py * py - r0 * r0;
let s = if a.abs() <= flat {
if b == 0.0 {
return None;
}
Some(c / (2.0 * b)).filter(|&s| ok(s))
} else {
let disc = b * b - a * c;
if disc < 0.0 {
return None;
}
let root = disc.sqrt();
let (s1, s2) = ((b + root) / a, (b - root) / a);
let (hi, lo) = if s1 >= s2 { (s1, s2) } else { (s2, s1) };
[hi, lo].into_iter().find(|&s| ok(s))
}?;
lut.at(s.clamp(0.0, 1.0), extend)
});
}
pub(super) fn function_based(
sh: &Shading,
target: &mut Target<'_>,
to_device: Affine,
domain: [f32; 4],
matrix: [f32; 6],
function: &Function,
) {
let [x0, x1, y0, y1] = domain.map(f64::from);
let to_space = Affine::from_matrix(matrix);
let domain_to_device = to_space.then(to_device);
let (Some(to_shading), Some(from_space)) = (to_device.invert(), to_space.invert()) else {
return;
};
let Some(rect) = region(sh, target, to_device).and_then(|r| {
r.intersect(Rect::of_box(
[domain[0], domain[2], domain[1], domain[3]],
domain_to_device,
)?)
}) else {
return;
};
// A grid point every two device pixels or so.
let points = |len: f64| ((len / 2.0).ceil() as usize).clamp(1, MAX_GRID - 1) + 1;
let gu = points(domain_to_device.map_vector(x1 - x0, 0.0));
let gv = points(domain_to_device.map_vector(0.0, y1 - y0));
let n = sh.color_space.components().min(MAX_ARITY);
let mut out = [0.0f32; MAX_ARITY];
let mut grid = Vec::with_capacity(gu * gv);
for j in 0..gv {
let v = y0 + (y1 - y0) * j as f64 / (gv - 1) as f64;
for i in 0..gu {
let u = x0 + (x1 - x0) * i as f64 / (gu - 1) as f64;
function.eval_into(&[u as f32, v as f32], &mut out);
grid.push(sh.color_space.to_rgb(&out[..n]));
}
}
let (lo_u, hi_u) = (x0.min(x1), x0.max(x1));
let (lo_v, hi_v) = (y0.min(y1), y0.max(y1));
fill(target, rect, to_shading, sh.bbox, |x, y| {
let (u, v) = from_space.map(x, y);
if u < lo_u || u > hi_u || v < lo_v || v > hi_v {
return None;
}
let fu = ((u - x0) / (x1 - x0) * (gu - 1) as f64).clamp(0.0, (gu - 1) as f64);
let fv = ((v - y0) / (y1 - y0) * (gv - 1) as f64).clamp(0.0, (gv - 1) as f64);
let (i, j) = ((fu as usize).min(gu - 1), (fv as usize).min(gv - 1));
let (i1, j1) = ((i + 1).min(gu - 1), (j + 1).min(gv - 1));
let (tu, tv) = ((fu - i as f64) as f32, (fv - j as f64) as f32);
let at = |i: usize, j: usize| grid[j * gu + i];
let mut rgb = [0u8; 3];
for (k, out) in rgb.iter_mut().enumerate() {
let top = at(i, j)[k] * (1.0 - tu) + at(i1, j)[k] * tu;
let bottom = at(i, j1)[k] * (1.0 - tu) + at(i1, j1)[k] * tu;
*out = to_u8(top * (1.0 - tv) + bottom * tv);
}
Some(rgb)
});
}
/// A gradient's stops (see [`Shading::stops`]).
pub(super) fn stops(
cs: &ColorSpace,
function: &Function,
domain: [f32; 2],
) -> Vec<(f32, [f32; 3])> {
let [t0, t1] = domain;
let at_t = |t: f32| rgb_at(cs, function, t);
let at_s = |s: f32| at_t(t0 + s * (t1 - t0));
// Where a stitching function may jump.
let mut jumps: Vec<(f32, f32)> = function
.bounds()
.iter()
.filter(|_| t1 != t0)
.map(|&b| ((b - t0) / (t1 - t0), b))
.filter(|&(s, _)| s > 0.0 && s < 1.0)
.collect();
jumps.sort_by(|a, b| a.0.total_cmp(&b.0));
jumps.dedup_by(|a, b| a.0 == b.0);
// Runs of samples between jumps, each simplified on its own.
let mut out: Vec<(f32, [f32; 3])> = Vec::new();
let mut start = (0.0f32, at_s(0.0));
for i in 0..=jumps.len() {
// The colors on either side of the jump (in the order `s` meets
// them): below the bound the previous subfunction applies.
let (end, left, right) = match jumps.get(i) {
Some(&(s, b)) => {
let (below, above) = (at_t(b.next_down()), at_t(b));
if t1 > t0 {
(s, below, above)
} else {
(s, above, below)
}
}
None => (1.0, at_s(1.0), at_s(1.0)),
};
let mut run = vec![start];
for k in 1..STOP_SAMPLES {
let s = k as f32 / STOP_SAMPLES as f32;
if s > start.0 + 1e-6 && s < end - 1e-6 {
run.push((s, at_s(s)));
}
}
run.push((end, left));
let simplified = simplify(&run);
// A jump that does not change the color is no stop.
if let (Some(last), Some(first)) = (out.last(), simplified.first())
&& last.0 == first.0
&& close(last.1, first.1)
{
out.pop();
}
out.extend(simplified);
start = (end, right);
}
out
}
fn close(a: [f32; 3], b: [f32; 3]) -> bool {
a.iter()
.zip(&b)
.all(|(x, y)| (x - y).abs() <= STOP_TOLERANCE)
}
/// Keeps the samples needed to redraw a run of colors by straight lines
/// between them (Douglas–Peucker over the colors).
fn simplify(points: &[(f32, [f32; 3])]) -> Vec<(f32, [f32; 3])> {
if points.len() <= 2 {
return points.to_vec();
}
let mut keep = vec![false; points.len()];
keep[0] = true;
keep[points.len() - 1] = true;
let mut spans = vec![(0, points.len() - 1)];
while let Some((i, j)) = spans.pop() {
let (si, ci) = points[i];
let (sj, cj) = points[j];
let mut worst = (0.0f32, 0);
for (k, &(s, c)) in points.iter().enumerate().take(j).skip(i + 1) {
let f = if sj > si { (s - si) / (sj - si) } else { 0.0 };
let error = (0..3)
.map(|n| (c[n] - (ci[n] + (cj[n] - ci[n]) * f)).abs())
.fold(0.0, f32::max);
if error > worst.0 {
worst = (error, k);
}
}
if worst.0 > STOP_TOLERANCE {
keep[worst.1] = true;
spans.push((i, worst.1));
spans.push((worst.1, j));
}
}
points
.iter()
.zip(&keep)
.filter(|(_, k)| **k)
.map(|(p, _)| *p)
.collect()
}