2bc41aeb8602
shading.rs
//! Shadings that aren't gradients, as gradient meshes: function-based ones (type 1) sampled on a
//! grid, free-form and lattice triangle meshes (types 4 and 5) and Coons and tensor patch meshes
//! (types 6 and 7), their vertices read from an array or packed in a string or file; and sampled
//! functions (type 0) that shadings and tint transforms use.
use std::sync::Arc;
use vectorcraft_color::{Color, Paint};
use vectorcraft_doc::live::GradientMesh;
use vectorcraft_doc::{Node, NodeId, NodeKind};
use vectorcraft_geom::{Affine, Point};
use super::graphics::Space;
use super::interp::{Interp, matrix_of};
use super::obj::{DictRef, Key, Obj, PsError, Res, clamp_between, ps_err};
/// Most patches (or triangles) one shading makes: past it, it is left out with a warning.
const MAX_PATCHES: usize = 4096;
/// Rows and columns of the mesh a function-based shading is sampled on.
const FUNCTION_GRID: u32 = 16;
/// Most samples a sampled function has.
const MAX_SAMPLES: usize = 1 << 24;
/// Most outputs (colour components) a sampled function has.
const MAX_OUTPUTS: usize = 32;
/// Most samples one value of a sampled function is interpolated from: inputs past it take the
/// nearest sample.
const MAX_TAPS: usize = 256;
/// Work one patch costs against the operation budget.
const PATCH_OPS: u64 = 64;
const TOO_MANY_PATCHES: &str = "shadings of more than 4096 patches or triangles were left out";
/// The numbers of a shading's vertices: from an array, or packed in bits ([`Packed`]).
enum Vertices {
Nums(Vec<f64>, usize),
Packed(Packed),
}
/// Vertex data packed in bits: flags, coordinates and colour components, each its own width and
/// mapped through `Decode`.
struct Packed {
bytes: Vec<u8>,
/// The next bit.
at: usize,
flag: u32,
coord: u32,
comp: u32,
decode: Vec<f64>,
}
impl Packed {
fn bits(&mut self, n: u32) -> Option<u64> {
if n == 0 || n > 32 || self.at.checked_add(n as usize)? > self.bytes.len() * 8 {
return None;
}
let mut v = 0u64;
for _ in 0..n {
let byte = *self.bytes.get(self.at / 8)?;
v = v << 1 | u64::from(byte >> (7 - self.at % 8) & 1);
self.at += 1;
}
Some(v)
}
/// A value of `n` bits through decode range `i` (`[min max]` pairs).
fn value(&mut self, n: u32, i: usize) -> Option<f64> {
let raw = self.bits(n)? as f64;
let max = ((1u64 << n) - 1) as f64;
let (lo, hi) = (self.decode.get(2 * i).copied().unwrap_or(0.0), self.decode.get(2 * i + 1).copied().unwrap_or(1.0));
Some(lo + raw * (hi - lo) / max)
}
}
impl Vertices {
fn flag(&mut self) -> Option<u32> {
match self {
Self::Nums(v, at) => {
let f = *v.get(*at)?;
*at += 1;
Some(f.max(0.0) as u32)
}
Self::Packed(p) => p.bits(p.flag).map(|f| f as u32),
}
}
fn num(&mut self, comp: bool, i: usize) -> Option<f64> {
match self {
Self::Nums(v, at) => {
let f = *v.get(*at)?;
*at += 1;
f.is_finite().then_some(f)
}
Self::Packed(p) => p.value(if comp { p.comp } else { p.coord }, i),
}
}
fn point(&mut self) -> Option<Point> {
Some(Point::new(self.num(false, 0)?, self.num(false, 1)?))
}
/// A vertex colour's `n` values (components, or the function's input).
fn color(&mut self, n: usize) -> Option<Vec<f64>> {
(0..n).map(|i| self.num(true, 2 + i)).collect()
}
/// Packed vertices start at a byte (triangle meshes).
fn align(&mut self) {
if let Self::Packed(p) = self {
p.at = p.at.div_ceil(8) * 8;
}
}
}
impl Interp<'_> {
/// Paint shading `sh` (types 1, 4โ7) as gradient meshes, `m` mapping shading space onto the
/// document, under the current clip.
pub fn mesh_fill(&mut self, sh: &DictRef, m: Affine) -> Res {
let get = |k: &str| sh.borrow().get(&Key::name(k)).cloned();
let kind = get("ShadingType").and_then(|o| o.as_num()).unwrap_or(0.0);
let space = self.space_of(&get("ColorSpace").ok_or(PsError::Ps("undefined", "ColorSpace".into()))?, 0)?;
let function = get("Function");
let meshes = if kind == 1.0 { self.function_mesh(sh, &space, m)? } else { self.patch_mesh(sh, kind, &space, function.as_ref(), m)? };
let Some(meshes) = meshes else {
self.out.warn(TOO_MANY_PATCHES);
return Ok(());
};
let mut nodes: Vec<Node> = meshes.into_iter().map(|g| Node::new(NodeId(0), NodeKind::Mesh(g))).collect();
let node = match nodes.len() {
0 => return Ok(()),
1 => nodes.swap_remove(0),
_ => {
let children = nodes
.into_iter()
.map(|mut n| {
n.id = self.out.doc.alloc_id();
Arc::new(n)
})
.collect();
Node::group(NodeId(0), children)
}
};
let clips = self.g.clips.clone();
self.out.push(node, &clips);
Ok(())
}
/// The colour of a vertex's values `v`: through the shading's function when it has one.
fn vertex_color(&mut self, space: &Space, function: Option<&Obj>, v: &[f64]) -> Res<Color> {
let comps = match function {
Some(f) => self.eval(f, v, 0)?,
None => v.to_vec(),
};
Ok(match self.paint_of(space, &comps)? {
Paint::Solid { color, .. } => color,
_ => Color::BLACK,
})
}
/// A function-based shading (type 1) sampled on a grid over its domain.
fn function_mesh(&mut self, sh: &DictRef, space: &Space, m: Affine) -> Res<Option<Vec<GradientMesh>>> {
let get = |k: &str| sh.borrow().get(&Key::name(k)).cloned();
let domain: Vec<f64> = get("Domain").and_then(|o| o.items().map(|i| i.borrow().iter().filter_map(Obj::as_num).collect())).unwrap_or_default();
let [x0, x1, y0, y1] = <[f64; 4]>::try_from(domain).unwrap_or([0.0, 1.0, 0.0, 1.0]);
let f = get("Function").ok_or(PsError::Ps("undefined", "Function".into()))?;
let matrix = get("Matrix").and_then(|o| o.items().and_then(|i| matrix_of(&i.borrow()))).unwrap_or(Affine::IDENTITY);
let n = FUNCTION_GRID as usize;
let at = |i: usize, lo: f64, hi: f64| lo + (hi - lo) * i as f64 / n as f64;
let mut colors = Vec::with_capacity((n + 1) * (n + 1));
for r in 0..=n {
for c in 0..=n {
self.spend(PATCH_OPS)?;
colors.push(self.vertex_color(space, Some(&f), &[at(c, x0, x1), at(r, y0, y1)])?);
}
}
let xf = m * matrix;
let surface = |u: f64, v: f64| xf * Point::new(x0 + (x1 - x0) * u, y0 + (y1 - y0) * v);
let color = |u: f64, v: f64| {
let (c, r) = ((u * n as f64).round() as usize, (v * n as f64).round() as usize);
colors.get(r * (n + 1) + c).copied().unwrap_or(Color::BLACK)
};
Ok(Some(vec![GradientMesh::from_surface(FUNCTION_GRID, FUNCTION_GRID, &surface, &color)]))
}
/// The vertices of a mesh shading's `DataSource`.
fn vertices(&mut self, sh: &DictRef, flags: bool) -> Res<Vertices> {
let get = |k: &str| sh.borrow().get(&Key::name(k)).cloned();
let bytes = match get("DataSource").ok_or(PsError::Ps("undefined", "DataSource".into()))? {
Obj::Array { items, .. } => {
let v: Option<Vec<f64>> = items.borrow().iter().map(Obj::as_num).collect();
return Ok(Vertices::Nums(v.ok_or(PsError::Ps("typecheck", "DataSource".into()))?, 0));
}
Obj::Str(s) => s.to_vec(),
Obj::File { stream, .. } => self.peek_all(&stream)?,
_ => return ps_err("typecheck", "DataSource"),
};
let bits = |k: &str| get(k).and_then(|o| o.as_num()).filter(|v| (1.0..=32.0).contains(v)).map(|v| v as u32);
let (Some(coord), Some(comp)) = (bits("BitsPerCoordinate"), bits("BitsPerComponent")) else {
return ps_err("rangecheck", "BitsPerCoordinate");
};
let flag = if flags { bits("BitsPerFlag").ok_or(PsError::Ps("rangecheck", "BitsPerFlag".into()))? } else { 0 };
let decode: Vec<f64> = get("Decode").and_then(|o| o.items().map(|i| i.borrow().iter().filter_map(Obj::as_num).collect())).unwrap_or_default();
Ok(Vertices::Packed(Packed { bytes, at: 0, flag, coord, comp, decode }))
}
/// A triangle (types 4, 5) or patch (6, 7) mesh in the document (`m`); `None` past
/// [`MAX_PATCHES`].
fn patch_mesh(&mut self, sh: &DictRef, kind: f64, space: &Space, function: Option<&Obj>, m: Affine) -> Res<Option<Vec<GradientMesh>>> {
let n = if function.is_some() { 1 } else { space.n() };
let mut v = self.vertices(sh, kind != 5.0)?;
let mut corner = |it: &mut Self, v: &mut Vertices| -> Res<Option<Color>> {
match v.color(n) {
Some(c) => it.vertex_color(space, function, &c).map(Some),
None => Ok(None),
}
};
if kind == 6.0 || kind == 7.0 {
return self.patches(&mut v, kind == 7.0, m, &mut corner);
}
let per_row = sh.borrow().get(&Key::name("VerticesPerRow")).and_then(Obj::as_num).filter(|r| (2.0..=1e6).contains(r)).map(|r| r as usize);
let lattice = kind == 5.0;
let mut pts: Vec<(Point, Color)> = vec![];
let mut tris: Vec<[usize; 3]> = vec![];
// Free-form: vertices still to come of the triangle being made.
let mut left = 0;
loop {
let flag = if lattice { 0 } else { v.flag().unwrap_or(u32::MAX) };
let Some(p) = v.point().filter(|_| flag != u32::MAX) else { break };
let Some(color) = corner(self, &mut v)? else { break };
if !lattice {
v.align();
}
self.spend(PATCH_OPS)?;
pts.push((m * p, color));
let i = pts.len() - 1;
if lattice {
// Each cell between two rows is two triangles.
if let Some(w) = per_row
&& i >= w
&& !i.is_multiple_of(w)
{
tris.push([i - w - 1, i - w, i - 1]);
tris.push([i - w, i - 1, i]);
}
} else if left > 0 {
// A vertex ending a triangle begun with flag 0.
left -= 1;
if left == 0 && i >= 2 {
tris.push([i - 2, i - 1, i]);
}
} else {
// A triangle on the last one's edge (flag 1: its second and third vertices, 2: its
// first and third), or the first vertex of a new one.
match (flag, tris.last().copied()) {
(1, Some([_, b, c])) => tris.push([b, c, i]),
(2, Some([a, _, c])) => tris.push([a, c, i]),
_ => left = 2,
}
}
if tris.len() > MAX_PATCHES {
return Ok(None);
}
}
let at = |i: usize| pts.get(i).copied().unwrap_or((Point::ZERO, Color::BLACK));
Ok(Some(tris.iter().filter_map(|t| GradientMesh::triangle(t.map(at))).collect()))
}
/// Coons (`tensor`: tensor-product) patches: twelve boundary points (a tensor patch's four
/// inner ones are read and left out), four corner colours; a patch on the last one's edge
/// (flag 1โ3) takes that edge's four points and two colours from it.
fn patches(
&mut self,
v: &mut Vertices,
tensor: bool,
m: Affine,
corner: &mut impl FnMut(&mut Self, &mut Vertices) -> Res<Option<Color>>,
) -> Res<Option<Vec<GradientMesh>>> {
let mut out = vec![];
let mut prev: Option<([Point; 12], [Color; 4])> = None;
while let Some(flag) = v.flag() {
let shared = match (flag, &prev) {
(0, _) => None,
(1, Some((p, c))) => Some(([p[3], p[4], p[5], p[6]], [c[1], c[2]])),
(2, Some((p, c))) => Some(([p[6], p[7], p[8], p[9]], [c[2], c[3]])),
(3, Some((p, c))) => Some(([p[9], p[10], p[11], p[0]], [c[3], c[0]])),
_ => return ps_err("rangecheck", "a patch flag"),
};
let mut cp = [Point::ZERO; 12];
let mut colors = [Color::BLACK; 4];
let (first_point, first_color) = match shared {
Some((pts, cs)) => {
cp[..4].copy_from_slice(&pts);
colors[..2].copy_from_slice(&cs);
(4, 2)
}
None => (0, 0),
};
for slot in cp.iter_mut().skip(first_point) {
let Some(p) = v.point() else { return Ok(Some(out)) };
*slot = m * p;
}
if tensor && (0..4).any(|_| v.point().is_none()) {
return Ok(Some(out));
}
for slot in colors.iter_mut().skip(first_color) {
let Some(c) = corner(self, v)? else { return Ok(Some(out)) };
*slot = c;
}
self.spend(PATCH_OPS)?;
if out.len() >= MAX_PATCHES {
return Ok(None);
}
out.extend(GradientMesh::coons(&cp, colors));
prev = Some((cp, colors));
}
Ok(Some(out))
}
/// A sampled function (type 0) at `x`: the samples around it, interpolated (multilinearly,
/// or by cubics for `Order 3`).
pub(super) fn sampled(&mut self, f: &DictRef, x: &[f64]) -> Res<Vec<f64>> {
let get = |k: &str| f.borrow().get(&Key::name(k)).cloned();
let nums =
|k: &str| -> Vec<f64> { get(k).and_then(|o| o.items().map(|i| i.borrow().iter().filter_map(Obj::as_num).collect())).unwrap_or_default() };
let (domain, range, size) = (nums("Domain"), nums("Range"), nums("Size"));
let m = domain.len() / 2;
let outs = range.len() / 2;
if m == 0 || outs == 0 || outs > MAX_OUTPUTS || size.len() < m || size.iter().any(|s| !(1.0..=MAX_SAMPLES as f64).contains(s)) {
return ps_err("rangecheck", "a sampled function");
}
let bps =
get("BitsPerSample").and_then(|o| o.as_num()).filter(|b| [1.0, 2.0, 4.0, 8.0, 12.0, 16.0, 24.0, 32.0].contains(b)).map(|b| b as usize);
let bps = bps.ok_or(PsError::Ps("rangecheck", "BitsPerSample".into()))?;
if size.iter().take(m).try_fold(1usize, |acc, s| acc.checked_mul(*s as usize)).is_none_or(|t| t > MAX_SAMPLES) {
return ps_err("limitcheck", "Size");
}
let bytes = match get("DataSource") {
Some(Obj::Str(s)) => s.to_vec(),
Some(Obj::File { stream, .. }) => self.peek_all(&stream)?,
_ => return ps_err("typecheck", "DataSource"),
};
// Copying the samples is work too: a shading evaluates its function once for each stop.
self.spend((bytes.len() / 256) as u64)?;
let (encode, decode) = (nums("Encode"), nums("Decode"));
let max = ((1u64 << bps) - 1) as f64;
let sample = |index: usize, j: usize| -> f64 {
let bit = (index as u64 * outs as u64 + j as u64) * bps as u64;
let raw = (0..bps as u64).fold(0u64, |v, k| {
let b = usize::try_from((bit + k) / 8).ok().and_then(|i| bytes.get(i)).copied().unwrap_or(0);
v << 1 | u64::from(b >> (7 - (bit + k) % 8) & 1)
}) as f64;
let (d0, d1) = (
decode.get(2 * j).or(range.get(2 * j)).copied().unwrap_or(0.0),
decode.get(2 * j + 1).or(range.get(2 * j + 1)).copied().unwrap_or(1.0),
);
let (r0, r1) = (range.get(2 * j).copied().unwrap_or(0.0), range.get(2 * j + 1).copied().unwrap_or(1.0));
clamp_between(d0 + raw * (d1 - d0) / max, r0, r1)
};
// Each input into sample space.
let mut pos = Vec::with_capacity(m);
for i in 0..m {
let (a, b) = (domain.get(2 * i).copied().unwrap_or(0.0), domain.get(2 * i + 1).copied().unwrap_or(1.0));
let s = size.get(i).copied().unwrap_or(1.0);
let (e0, e1) = (encode.get(2 * i).copied().unwrap_or(0.0), encode.get(2 * i + 1).copied().unwrap_or(s - 1.0));
let xi = clamp_between(x.get(i).copied().unwrap_or(a), a, b);
let e = if b != a { e0 + (xi - a) * (e1 - e0) / (b - a) } else { e0 };
pos.push(clamp_between(e, 0.0, s - 1.0));
}
// The samples each input reads and their weights: the two around it (linear), or the
// four around it for `Order 3` (cubic). The result is their tensor product.
let cubic = get("Order").and_then(|o| o.as_num()) == Some(3.0);
let mut taps: Vec<Vec<(usize, f64)>> = Vec::with_capacity(m);
let mut combos = 1usize;
for (i, p) in pos.iter().enumerate() {
let last = size.get(i).copied().unwrap_or(1.0) as usize - 1;
let lo = p.floor() as usize;
let t = p - p.floor();
let at = |k: isize| (lo as isize + k).clamp(0, last as isize) as usize;
let w: Vec<(usize, f64)> = if t == 0.0 || last == 0 {
vec![(lo.min(last), 1.0)]
} else if cubic && combos.saturating_mul(4) <= MAX_TAPS {
catmull_rom(t).into_iter().zip(-1..=2).map(|(w, k)| (at(k), w)).collect()
} else if combos.saturating_mul(2) <= MAX_TAPS {
vec![(at(0), 1.0 - t), (at(1), t)]
} else {
// Too many inputs between samples to interpolate them all: the nearest (a
// fractional `Size` can put it past the last sample).
vec![((p.round() as usize).min(last), 1.0)]
};
combos = combos.saturating_mul(w.len());
taps.push(w);
}
// Each combination of taps reads one sample of every output.
self.spend(combos.saturating_mul(outs) as u64)?;
let mut out = vec![0.0; outs];
let mut digits = vec![0usize; m];
loop {
let (mut index, mut stride, mut weight) = (0usize, 1usize, 1.0);
for (i, (tap, d)) in taps.iter().zip(&digits).enumerate() {
let (k, w) = tap.get(*d).copied().unwrap_or((0, 0.0));
index += k * stride;
weight *= w;
stride *= size.get(i).copied().unwrap_or(1.0) as usize;
}
if weight != 0.0 {
for (j, o) in out.iter_mut().enumerate() {
*o += weight * sample(index, j);
}
}
// The next combination, the first input varying fastest.
let Some(i) = digits.iter().zip(&taps).position(|(d, t)| d + 1 < t.len()) else { break };
for d in digits.iter_mut().take(i) {
*d = 0;
}
if let Some(d) = digits.get_mut(i) {
*d += 1;
}
}
// A cubic overshoots between samples of different slopes: kept in the range.
Ok(out
.into_iter()
.enumerate()
.map(|(j, v)| clamp_between(v, range.get(2 * j).copied().unwrap_or(0.0), range.get(2 * j + 1).copied().unwrap_or(1.0)))
.collect())
}
}
/// The weights of the four samples around a point `t` of the way from the second to the third:
/// the Catmull-Rom cubic, which passes through every sample with the slope of its neighbours.
fn catmull_rom(t: f64) -> [f64; 4] {
let (t2, t3) = (t * t, t * t * t);
[(-t3 + 2.0 * t2 - t) / 2.0, (3.0 * t3 - 5.0 * t2 + 2.0) / 2.0, (-3.0 * t3 + 4.0 * t2 + t) / 2.0, (t3 - t2) / 2.0]
}
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.