2bc41aeb8602
arap.rs
//! As-Rigid-As-Possible shape manipulation (Igarashi, Moscovich & Hughes, SIGGRAPH 2005),
//! implemented from the paper.
//!
//! - The mesh is a regular grid of triangles over the artwork: grid cells are kept when their
//! centre is inside the filled outline or near any path (so separate limbs stay separate).
//! - Step 1 (similarity): every triangle vertex is expressed in the local frame of the opposite
//! edge, `v2 = v0 + x·(v1 − v0) + y·R90(v1 − v0)`; the quadratic error of those relations over
//! all triangles (rotation + uniform scale free) plus soft pin constraints is minimised.
//! - Step 2 (scale adjustment): each triangle's rest shape is rigidly fitted (optimal 2D rotation)
//! to its step-1 result, then the vertices are solved so every edge vector matches its fitted
//! triangle's, which removes the scaling step 1 allows.
//! - Pins are arbitrary points (barycentric combinations of a triangle's vertices), so both steps
//! use weighted soft constraints. Systems are symmetric positive definite and banded (vertices
//! are numbered row by row), solved with a banded Cholesky factorisation written here.
//! - Artwork points (anchors and handles) follow the mesh through barycentric coordinates in
//! their rest triangle.
use vectorcraft_geom::kurbo::ParamCurveNearest;
use vectorcraft_geom::{BezPath, Point, Rect, Shape, Vec2};
/// Banded symmetric positive definite matrix (lower band stored row by row).
#[derive(Clone, Debug)]
pub struct BandMatrix {
n: usize,
bw: usize,
/// Row i holds columns i-bw..=i at offsets 0..=bw.
a: Vec<f64>,
}
impl BandMatrix {
pub fn new(n: usize, bw: usize) -> Self {
Self { n, bw, a: vec![0.0; n * (bw + 1)] }
}
pub fn len(&self) -> usize {
self.n
}
pub fn is_empty(&self) -> bool {
self.n == 0
}
fn idx(&self, i: usize, j: usize) -> usize {
// j <= i, i - j <= bw
i * (self.bw + 1) + (j + self.bw - i)
}
/// Add `v` at (i, j) (and implicitly (j, i)); diagonal entries are added once.
pub fn add(&mut self, i: usize, j: usize, v: f64) {
let (i, j) = if i >= j { (i, j) } else { (j, i) };
debug_assert!(i - j <= self.bw, "outside band");
let k = self.idx(i, j);
self.a[k] += v;
}
pub fn get(&self, i: usize, j: usize) -> f64 {
let (i, j) = if i >= j { (i, j) } else { (j, i) };
if i - j > self.bw { 0.0 } else { self.a[self.idx(i, j)] }
}
/// In-place Cholesky factorisation (L·Lᵀ). Returns false if the matrix isn't positive definite.
pub fn factor(&mut self) -> bool {
let (n, bw) = (self.n, self.bw);
for i in 0..n {
let j0 = i.saturating_sub(bw);
for j in j0..=i {
let mut s = self.a[self.idx(i, j)];
let k0 = j0.max(j.saturating_sub(bw));
for k in k0..j {
s -= self.a[self.idx(i, k)] * self.a[self.idx(j, k)];
}
if i == j {
if s <= 0.0 || !s.is_finite() {
return false;
}
let k = self.idx(i, i);
self.a[k] = s.sqrt();
} else {
let k = self.idx(i, j);
self.a[k] = s / self.a[self.idx(j, j)];
}
}
}
true
}
/// Solve with a factored matrix.
pub fn solve(&self, b: &mut [f64]) {
let (n, bw) = (self.n, self.bw);
for i in 0..n {
let mut s = b[i];
let k0 = i.saturating_sub(bw);
for (k, bk) in b[k0..i].iter().enumerate() {
s -= self.a[self.idx(i, k0 + k)] * bk;
}
b[i] = s / self.a[self.idx(i, i)];
}
for i in (0..n).rev() {
let mut s = b[i];
for (k, bk) in b[i + 1..(i + bw + 1).min(n)].iter().enumerate() {
s -= self.a[self.idx(i + 1 + k, i)] * bk;
}
b[i] = s / self.a[self.idx(i, i)];
}
}
}
/// A triangle mesh on a regular grid.
#[derive(Clone, Debug)]
pub struct Mesh {
pub verts: Vec<Point>,
pub tris: Vec<[usize; 3]>,
origin: Point,
cell: f64,
nx: usize,
ny: usize,
/// Per grid cell: its two triangles (None = cell not part of the mesh).
cells: Vec<Option<[usize; 2]>>,
/// Per grid cell: centre inside the art (not just the band around it).
core: Vec<bool>,
}
/// Mesh construction options.
#[derive(Clone, Copy, Debug)]
pub struct MeshOptions {
/// Cells along the longer side.
pub resolution: usize,
/// Expand Mesh: extra reach around the outline, points.
pub expand: f64,
}
impl Default for MeshOptions {
fn default() -> Self {
Self { resolution: 20, expand: 3.0 }
}
}
impl Mesh {
/// Build a mesh covering `bounds` restricted to the region of `outlines` (filled interiors of
/// closed subpaths plus a band around every path). With no outlines, the whole bounds.
pub fn build(outlines: &[BezPath], bounds: Rect, opt: MeshOptions) -> Mesh {
// The cells cover the expanded art, so tiny art with a wide Expand stays a small grid.
let side = (bounds.width().max(bounds.height()) + 2.0 * opt.expand.max(0.0)).max(1e-3);
let cell = (side / opt.resolution.max(1) as f64).max(1e-3);
let pad = opt.expand.max(0.0) + cell * 0.01;
let b = bounds.inflate(pad, pad);
let nx = ((b.width() / cell).ceil() as usize).max(1);
let ny = ((b.height() / cell).ceil() as usize).max(1);
let origin = Point::new(b.x0, b.y0);
let reach = cell * 0.75 + opt.expand.max(0.0);
// 0 = outside, 1 = in the band around the art, 2 = core (inside a fill or on a path).
let keep = |c: Point| -> u8 {
if outlines.is_empty() {
return 2;
}
let near = |o: &BezPath, r: f64| o.segments().any(|s| s.nearest(c, 1e-3).distance_sq <= r * r);
if outlines.iter().any(|o| closed_winding(o, c) != 0 || near(o, cell * 0.25)) {
return 2;
}
u8::from(outlines.iter().any(|o| {
let bb = o.bounding_box().inflate(reach, reach);
if !bb.contains(c) {
return false;
}
if closed_winding(o, c) != 0 {
return true;
}
near(o, reach)
}))
};
let mut vid = vec![usize::MAX; (nx + 1) * (ny + 1)];
let mut verts = vec![];
let mut kept = vec![false; nx * ny];
let mut core = vec![false; nx * ny];
for j in 0..ny {
for i in 0..nx {
let c = Point::new(origin.x + (i as f64 + 0.5) * cell, origin.y + (j as f64 + 0.5) * cell);
let k = keep(c);
kept[j * nx + i] = k > 0;
core[j * nx + i] = k == 2;
}
}
// Number vertices row by row (keeps the systems banded).
for j in 0..=ny {
for i in 0..=nx {
let used = [(i.wrapping_sub(1), j.wrapping_sub(1)), (i, j.wrapping_sub(1)), (i.wrapping_sub(1), j), (i, j)]
.iter()
.any(|&(ci, cj)| ci < nx && cj < ny && kept[cj * nx + ci]);
if used {
vid[j * (nx + 1) + i] = verts.len();
verts.push(Point::new(origin.x + i as f64 * cell, origin.y + j as f64 * cell));
}
}
}
let mut tris = vec![];
let mut cells = vec![None; nx * ny];
for j in 0..ny {
for i in 0..nx {
if !kept[j * nx + i] {
continue;
}
let v = |di: usize, dj: usize| vid[(j + dj) * (nx + 1) + i + di];
let (v00, v10, v01, v11) = (v(0, 0), v(1, 0), v(0, 1), v(1, 1));
let t0 = tris.len();
tris.push([v00, v10, v11]);
tris.push([v00, v11, v01]);
cells[j * nx + i] = Some([t0, t0 + 1]);
}
}
Mesh { verts, tris, origin, cell, nx, ny, cells, core }
}
/// Band width (in vertices) of the vertex adjacency.
fn vertex_band(&self) -> usize {
self.tris.iter().filter_map(|t| Some(t.iter().max()? - t.iter().min()?)).max().unwrap_or(0)
}
/// The triangle and barycentric coordinates of `p` (extrapolated from the nearest mesh cell
/// when `p` is outside the mesh).
pub fn locate(&self, p: Point) -> Option<(usize, [f64; 3])> {
let fi = ((p.x - self.origin.x) / self.cell).floor();
let fj = ((p.y - self.origin.y) / self.cell).floor();
let inside = fi >= 0.0 && fj >= 0.0 && (fi as usize) < self.nx && (fj as usize) < self.ny;
let cell = if inside && self.cells[fj as usize * self.nx + fi as usize].is_some() {
fj as usize * self.nx + fi as usize
} else {
// Nearest kept cell centre.
let mut best = None;
for (k, c) in self.cells.iter().enumerate() {
if c.is_none() {
continue;
}
let cc =
Point::new(self.origin.x + ((k % self.nx) as f64 + 0.5) * self.cell, self.origin.y + ((k / self.nx) as f64 + 0.5) * self.cell);
let d = cc.distance_squared(p);
if best.is_none_or(|(bd, _)| d < bd) {
best = Some((d, k));
}
}
best?.1
};
let [ta, tb] = self.cells[cell]?;
// Pick the triangle on p's side of the diagonal v00–v11.
let v00 = self.verts[self.tris[ta][0]];
let local = (p - v00) / self.cell;
let t = if local.x >= local.y { ta } else { tb };
Some((t, self.bary(t, p)))
}
fn bary(&self, t: usize, p: Point) -> [f64; 3] {
let [a, b, c] = self.tris[t].map(|i| self.verts[i]);
let (v0, v1, v2) = (b - a, c - a, p - a);
let den = v0.cross(v1);
if den.abs() < 1e-18 {
return [1.0, 0.0, 0.0];
}
let l1 = v2.cross(v1) / den;
let l2 = v0.cross(v2) / den;
[1.0 - l1 - l2, l1, l2]
}
/// Map a rest-space point through deformed vertex positions.
pub fn map(&self, deformed: &[Point], p: Point) -> Point {
match self.locate(p) {
Some((t, w)) => {
let [a, b, c] = self.tris[t].map(|i| deformed[i].to_vec2());
(a * w[0] + b * w[1] + c * w[2]).to_point()
}
None => p,
}
}
/// Signed area of triangle `t` for the given vertex positions.
pub fn tri_area(&self, pos: &[Point], t: usize) -> f64 {
let [a, b, c] = self.tris[t].map(|i| pos[i]);
(b - a).cross(c - a) / 2.0
}
/// Is `p` (rest space) on the mesh?
pub fn contains(&self, p: Point) -> bool {
self.cell_at(p).is_some_and(|k| self.cells.get(k).is_some_and(Option::is_some))
}
/// The grid cell under `p`, if inside the grid.
fn cell_at(&self, p: Point) -> Option<usize> {
let fi = ((p.x - self.origin.x) / self.cell).floor();
let fj = ((p.y - self.origin.y) / self.cell).floor();
(fi >= 0.0 && fj >= 0.0 && fi < self.nx as f64 && fj < self.ny as f64).then(|| fj as usize * self.nx + fi as usize)
}
/// The rest-space point that the `deformed` mesh shows at `q` (None: `q` is off the mesh).
/// Where the warp folds the mesh over itself, the triangle `q` is deepest inside wins.
pub fn unmap(&self, deformed: &[Point], q: Point) -> Option<Point> {
let mut best: Option<(f64, Point)> = None;
for t in &self.tris {
let [a, b, c] = t.map(|i| deformed.get(i).copied().unwrap_or(self.verts[i]));
let den = (b - a).cross(c - a);
if den.abs() < 1e-18 {
continue;
}
let l1 = (q - a).cross(c - a) / den;
let l2 = (b - a).cross(q - a) / den;
let w = [1.0 - l1 - l2, l1, l2];
let depth = w.iter().copied().fold(f64::MAX, f64::min);
if depth >= -1e-9 && best.is_none_or(|(d, _)| depth > d) {
let [ra, rb, rc] = t.map(|i| self.verts[i].to_vec2());
best = Some((depth, (ra * w[0] + rb * w[1] + rc * w[2]).to_point()));
}
}
best.map(|b| b.1)
}
/// How far (radians) the `deformed` mesh turned the art at rest point `p`.
pub fn turn_at(&self, deformed: &[Point], p: Point) -> Option<f64> {
let (t, _) = self.locate(p)?;
let tri = self.tris.get(t)?;
let cur = [*deformed.get(tri[0])?, *deformed.get(tri[1])?, *deformed.get(tri[2])?];
Some(fit_angle(&tri.map(|i| self.verts[i]), &cur))
}
/// Centre of grid cell `k`.
fn cell_centre(&self, k: usize) -> Point {
Point::new(self.origin.x + ((k % self.nx) as f64 + 0.5) * self.cell, self.origin.y + ((k / self.nx) as f64 + 0.5) * self.cell)
}
/// The cells pins go in: those inside the art (or every kept cell when none is).
fn pin_cells(&self) -> Vec<bool> {
let any_core = self.core.iter().any(|c| *c);
self.cells.iter().zip(&self.core).map(|(c, core)| c.is_some() && (*core || !any_core)).collect()
}
/// The 8 neighbours of cell `k` inside the grid, with the step length (in cells).
fn neighbours(&self, k: usize) -> impl Iterator<Item = (usize, f64)> + use<> {
let (nx, ny) = (self.nx as i64, self.ny as i64);
let (i, j) = ((k % self.nx) as i64, (k / self.nx) as i64);
(-1i64..=1).flat_map(move |dj| (-1i64..=1).map(move |di| (di, dj))).filter_map(move |(di, dj)| {
let (a, b) = (i + di, j + dj);
let step = if di != 0 && dj != 0 { std::f64::consts::SQRT_2 } else { 1.0 };
((di, dj) != (0, 0) && a >= 0 && b >= 0 && a < nx && b < ny).then_some(((b * nx + a) as usize, step))
})
}
/// Distances (in cells, through the cells where `inside`) from `sources` (cells with their
/// start distances) to every cell; cells out of reach stay at infinity.
fn geodesic(&self, inside: &[bool], sources: &[(usize, f64)]) -> Vec<f64> {
let mut dist = vec![f64::INFINITY; self.cells.len()];
for &(k, d) in sources {
if let Some(v) = dist.get_mut(k) {
*v = v.min(d);
}
}
let inside = |k: usize| inside.get(k).copied().unwrap_or(false);
// Relax until nothing improves (the grid is small: a few dozen cells a side).
let mut changed = true;
while changed {
changed = false;
for k in 0..dist.len() {
if !inside(k) || !dist[k].is_finite() {
continue;
}
for (m, step) in self.neighbours(k) {
if inside(m) && dist[k] + step < dist[m] - 1e-12 {
dist[m] = dist[k] + step;
changed = true;
}
}
}
}
dist
}
}
/// Winding number of the closed subpaths of `o` at `p` (open subpaths ignored).
fn closed_winding(o: &BezPath, p: Point) -> i32 {
let mut total = 0;
let mut cur = BezPath::new();
let mut closed = false;
let flush = |cur: &mut BezPath, closed: bool, total: &mut i32| {
if closed && !cur.elements().is_empty() {
*total += cur.winding(p);
}
*cur = BezPath::new();
};
for el in o.elements() {
match el {
vectorcraft_geom::PathEl::MoveTo(_) => {
flush(&mut cur, closed, &mut total);
closed = false;
cur.push(*el);
}
vectorcraft_geom::PathEl::ClosePath => {
closed = true;
cur.push(*el);
}
e => cur.push(*e),
}
}
flush(&mut cur, closed, &mut total);
total
}
/// Weight of the soft pin constraints relative to the shape terms.
const PIN_WEIGHT: f64 = 1.0e5;
/// Tikhonov regularisation toward the rest pose (keeps pin-less islands in place).
const REG: f64 = 1.0e-7;
/// A pin in rest space and where it should go.
#[derive(Clone, Copy, Debug)]
pub struct Pin {
pub rest: Point,
pub target: Point,
/// The rotation (radians) the art takes around the pin; `None` leaves it free (the solve
/// picks it), as for a pin that was only moved.
pub angle: Option<f64>,
}
impl Pin {
/// A pin free to turn.
pub fn new(rest: Point, target: Point) -> Self {
Self { rest, target, angle: None }
}
/// The soft constraints this pin puts on the mesh: the pin itself and, when its rotation is
/// held, two points a cell away along the rest axes, turned by the angle around the target.
fn constraints(&self, reach: f64) -> impl Iterator<Item = (Point, Point)> + use<> {
let frame = self.angle.map(|a| {
let (s, c) = a.sin_cos();
[Vec2::new(reach, 0.0), Vec2::new(0.0, reach)].map(|d| (self.rest + d, self.target + Vec2::new(d.x * c - d.y * s, d.x * s + d.y * c)))
});
std::iter::once((self.rest, self.target)).chain(frame.into_iter().flatten())
}
}
/// Run both ARAP steps. Returns the deformed vertex positions (the rest mesh if fewer than one
/// pin lands on it or a system is singular).
pub fn deform(mesh: &Mesh, pins: &[Pin]) -> Vec<Point> {
let n = mesh.verts.len();
if n == 0 || pins.is_empty() {
return mesh.verts.clone();
}
let located: Vec<(usize, [f64; 3], Point)> =
pins.iter().flat_map(|p| p.constraints(mesh.cell)).filter_map(|(rest, target)| mesh.locate(rest).map(|(t, w)| (t, w, target))).collect();
let vb = mesh.vertex_band();
// ---- step 1: similarity-invariant error, 2n unknowns interleaved (x0, y0, x1, y1, ...).
let mut g = BandMatrix::new(2 * n, 2 * vb + 1);
for tri in &mesh.tris {
for k in 0..3 {
let (a, b, c) = (tri[k], tri[(k + 1) % 3], tri[(k + 2) % 3]);
let (pa, pb, pc) = (mesh.verts[a], mesh.verts[b], mesh.verts[c]);
let e = pb - pa;
let l2 = e.hypot2();
if l2 < 1e-18 {
continue;
}
let d = pc - pa;
let x = d.dot(e) / l2;
let y = d.dot(Vec2::new(-e.y, e.x)) / l2;
// Residual coefficients over (ax, ay, bx, by, cx, cy); see module docs.
let vars = [2 * a, 2 * a + 1, 2 * b, 2 * b + 1, 2 * c, 2 * c + 1];
let rx = [x - 1.0, -y, -x, y, 1.0, 0.0];
let ry = [y, x - 1.0, -y, -x, 0.0, 1.0];
for r in [rx, ry] {
for i in 0..6 {
for j in 0..=i {
let v = r[i] * r[j];
if v != 0.0 {
g.add(vars[i], vars[j], v);
}
}
}
}
}
}
let mut rhs = vec![0.0; 2 * n];
for (t, w, target) in &located {
let tri = mesh.tris[*t];
for comp in 0..2 {
for i in 0..3 {
for j in 0..=i {
g.add(2 * tri[i] + comp, 2 * tri[j] + comp, PIN_WEIGHT * w[i] * w[j]);
}
rhs[2 * tri[i] + comp] += PIN_WEIGHT * w[i] * if comp == 0 { target.x } else { target.y };
}
}
}
for (i, v) in mesh.verts.iter().enumerate() {
g.add(2 * i, 2 * i, REG);
g.add(2 * i + 1, 2 * i + 1, REG);
rhs[2 * i] += REG * v.x;
rhs[2 * i + 1] += REG * v.y;
}
if !g.factor() {
return mesh.verts.clone();
}
g.solve(&mut rhs);
let step1: Vec<Point> = (0..n).map(|i| Point::new(rhs[2 * i], rhs[2 * i + 1])).collect();
// ---- step 2: fit rigid triangles, then match edge vectors (x and y separable).
let mut l = BandMatrix::new(n, vb);
let mut bx = vec![0.0; n];
let mut by = vec![0.0; n];
for tri in &mesh.tris {
let rest = tri.map(|i| mesh.verts[i]);
let cur = tri.map(|i| step1[i]);
let (rc, cc) = (centroid(&rest), centroid(&cur));
let (s, co) = fit_angle(&rest, &cur).sin_cos();
let fit = rest.map(|r| {
let d = r - rc;
cc + Vec2::new(d.x * co - d.y * s, d.x * s + d.y * co)
});
for k in 0..3 {
let (i, j) = (tri[k], tri[(k + 1) % 3]);
let e = fit[k] - fit[(k + 1) % 3];
// (v_i - v_j - e)^2
l.add(i, i, 1.0);
l.add(j, j, 1.0);
l.add(i, j, -1.0);
bx[i] += e.x;
bx[j] -= e.x;
by[i] += e.y;
by[j] -= e.y;
}
}
for (t, w, target) in &located {
let tri = mesh.tris[*t];
for i in 0..3 {
for j in 0..=i {
l.add(tri[i], tri[j], PIN_WEIGHT * w[i] * w[j]);
}
bx[tri[i]] += PIN_WEIGHT * w[i] * target.x;
by[tri[i]] += PIN_WEIGHT * w[i] * target.y;
}
}
for (i, v) in step1.iter().enumerate() {
l.add(i, i, REG);
bx[i] += REG * v.x;
by[i] += REG * v.y;
}
if !l.factor() {
return step1;
}
l.solve(&mut bx);
l.solve(&mut by);
(0..n).map(|i| Point::new(bx[i], by[i])).collect()
}
fn centroid(p: &[Point; 3]) -> Point {
Point::new((p[0].x + p[1].x + p[2].x) / 3.0, (p[0].y + p[1].y + p[2].y) / 3.0)
}
/// The rotation (radians) that best fits triangle `rest` onto `cur` (least squares, about their
/// centroids).
fn fit_angle(rest: &[Point; 3], cur: &[Point; 3]) -> f64 {
let (rc, cc) = (centroid(rest), centroid(cur));
let (mut sc, mut ss) = (0.0, 0.0);
for k in 0..3 {
let (r, c) = (rest[k] - rc, cur[k] - cc);
sc += r.dot(c);
ss += r.cross(c);
}
ss.atan2(sc)
}
/// Pick `count` well-spread pin positions inside the mesh (farthest-point sampling over the
/// kept cell centres, starting from the one nearest the centroid).
pub fn auto_pins(mesh: &Mesh, count: usize) -> Vec<Point> {
let mut out: Vec<Point> = centre_of(mesh).map(|c| c.1).into_iter().collect();
spread_pins(mesh, &mut out, count);
out
}
/// The centre of the cells pins go in: the cell nearest their centroid, and the centroid itself
/// (that cell's centre when the centroid falls off the art, as in a ring).
fn centre_of(mesh: &Mesh) -> Option<(usize, Point)> {
let cells: Vec<usize> = mesh.pin_cells().iter().enumerate().filter(|(_, c)| **c).map(|(k, _)| k).collect();
let c = (cells.iter().fold(Vec2::ZERO, |a, k| a + mesh.cell_centre(*k).to_vec2()) / cells.len().max(1) as f64).to_point();
let k = cells.into_iter().min_by(|a, b| mesh.cell_centre(*a).distance_squared(c).total_cmp(&mesh.cell_centre(*b).distance_squared(c)))?;
Some((k, if mesh.contains(c) { c } else { mesh.cell_centre(k) }))
}
/// The most pins placed automatically.
const MAX_AUTO_PINS: usize = 12;
/// The pins the Puppet Warp tool places by itself: one at the centre of the art and one at the
/// end of each limb (a part reaching well beyond the art's thickness, like the arms of a star or
/// the ends of a long bar); at least three in all where the art has room.
pub fn default_pins(mesh: &Mesh) -> Vec<Point> {
let Some((centre, middle)) = centre_of(mesh) else { return vec![] };
let inside = mesh.pin_cells();
// Thickness: the largest distance from inside the art to its edge.
let edge: Vec<(usize, f64)> = (0..inside.len())
.filter(|k| inside[*k] && (mesh.neighbours(*k).count() < 8 || mesh.neighbours(*k).any(|(m, _)| !inside[m])))
.map(|k| (k, 0.5))
.collect();
let radius = mesh.geodesic(&inside, &edge).into_iter().filter(|d| d.is_finite()).fold(0.0, f64::max);
// Limb ends: the cells farthest from the centre (through the art), well beyond the thickness.
let from_centre = mesh.geodesic(&inside, &[(centre, 0.0)]);
let mut ends: Vec<usize> = (0..inside.len())
.filter(|k| {
let d = from_centre[*k];
inside[*k] && d.is_finite() && d >= 1.5 * radius && mesh.neighbours(*k).all(|(m, _)| !inside[m] || from_centre[m] <= d)
})
.collect();
ends.sort_by(|a, b| from_centre[*b].total_cmp(&from_centre[*a]));
// One pin per limb: ends closer than about the art's width belong to the same limb.
let apart = 2.2 * radius * mesh.cell;
let mut out = vec![middle];
let mut tips: Vec<Point> = vec![];
for k in ends {
let p = mesh.cell_centre(k);
if out.len() >= MAX_AUTO_PINS || tips.iter().any(|q| q.distance(p) < apart) {
continue;
}
tips.push(p);
// The pin goes in the middle of the limb's end: the centroid of the cells about as far out
// near its tip (the tip itself if that falls off the art).
let cap: Vec<Point> = (0..inside.len())
.filter(|m| inside[*m] && from_centre[*m] >= from_centre[k] - radius)
.map(|m| mesh.cell_centre(m))
.filter(|q| q.distance(p) < apart)
.collect();
let mid = (cap.iter().fold(Vec2::ZERO, |a, q| a + q.to_vec2()) / cap.len().max(1) as f64).to_point();
out.push(if mesh.contains(mid) { mid } else { p });
}
spread_pins(mesh, &mut out, 3);
out
}
/// Add pins to `out` until there are `count`, each as far as possible from the others
/// (farthest-point sampling over the cells pins go in).
fn spread_pins(mesh: &Mesh, out: &mut Vec<Point>, count: usize) {
let centres: Vec<Point> = mesh.pin_cells().iter().enumerate().filter(|(_, c)| **c).map(|(k, _)| mesh.cell_centre(k)).collect();
while out.len() < count.min(centres.len()) {
let Some(&next) = centres.iter().max_by(|a, b| {
let da = out.iter().map(|o| o.distance_squared(**a)).fold(f64::MAX, f64::min);
let db = out.iter().map(|o| o.distance_squared(**b)).fold(f64::MAX, f64::min);
da.total_cmp(&db)
}) else {
break;
};
out.push(next);
}
}
#[cfg(test)]
mod tests {
use super::*;
use vectorcraft_geom::shapes;
#[test]
fn band_cholesky_solves_spd_systems() {
// Tridiagonal [4 1; 1 4 1; ...] vs a dense reference.
let n = 12;
let mut m = BandMatrix::new(n, 1);
for i in 0..n {
m.add(i, i, 4.0);
if i > 0 {
m.add(i, i - 1, 1.0);
}
}
let x: Vec<f64> = (0..n).map(|i| i as f64 * 0.5 - 2.0).collect();
let mut b: Vec<f64> = (0..n).map(|i| (0..n).map(|j| m.get(i, j) * x[j]).sum()).collect();
assert!(m.factor());
m.solve(&mut b);
for i in 0..n {
assert!((b[i] - x[i]).abs() < 1e-12);
}
let mut bad = BandMatrix::new(2, 1);
bad.add(0, 0, 1.0);
bad.add(1, 0, 2.0);
bad.add(1, 1, 1.0);
assert!(!bad.factor(), "indefinite");
}
fn rect_mesh() -> Mesh {
let r = Rect::new(0.0, 0.0, 200.0, 100.0);
Mesh::build(&[shapes::rectangle(r).to_bezpath()], r, MeshOptions { resolution: 16, expand: 0.0 })
}
#[test]
fn mesh_covers_shape_and_locates_points() {
let m = rect_mesh();
assert!(!m.tris.is_empty());
for p in [Point::new(10.0, 10.0), Point::new(150.0, 70.0), Point::new(199.0, 99.0)] {
let (t, w) = m.locate(p).unwrap();
assert!(w.iter().all(|v| *v >= -1e-9), "{w:?}");
assert!((m.map(&m.verts, p) - p).hypot() < 1e-9);
let _ = t;
}
// An L-shaped outline drops the empty corner cells.
let mut l = BezPath::new();
l.move_to((0.0, 0.0));
l.line_to((100.0, 0.0));
l.line_to((100.0, 20.0));
l.line_to((20.0, 20.0));
l.line_to((20.0, 100.0));
l.line_to((0.0, 100.0));
l.close_path();
let lm = Mesh::build(&[l], Rect::new(0.0, 0.0, 100.0, 100.0), MeshOptions { resolution: 10, expand: 0.0 });
assert!(lm.tris.len() < m.tris.len() / 2, "{} tris", lm.tris.len());
assert!(lm.cells.iter().filter(|c| c.is_some()).count() < 60);
}
#[test]
fn pins_at_rest_leave_the_mesh_unchanged() {
let m = rect_mesh();
let pins: Vec<Pin> =
[(20.0, 50.0), (180.0, 50.0), (100.0, 20.0)].iter().map(|&(x, y)| Pin::new(Point::new(x, y), Point::new(x, y))).collect();
let d = deform(&m, &pins);
let err = m.verts.iter().zip(&d).map(|(a, b)| a.distance(*b)).fold(0.0, f64::max);
assert!(err < 1e-4, "{err}");
}
#[test]
fn rigid_motion_is_reproduced_exactly() {
let m = rect_mesh();
let rot = |p: Point| {
let (s, c) = 0.5f64.sin_cos();
Point::new(p.x * c - p.y * s + 30.0, p.x * s + p.y * c - 10.0)
};
let pins: Vec<Pin> =
[(20.0, 50.0), (180.0, 50.0), (100.0, 90.0)].iter().map(|&(x, y)| Pin::new(Point::new(x, y), rot(Point::new(x, y)))).collect();
let d = deform(&m, &pins);
let err = m.verts.iter().zip(&d).map(|(a, b)| rot(*a).distance(*b)).fold(0.0, f64::max);
assert!(err < 1e-2, "{err}");
}
#[test]
fn pins_are_satisfied_and_free_regions_stay_rigid() {
let m = rect_mesh();
// Hold the left end, lift the right end.
let pins = vec![
Pin::new(Point::new(10.0, 30.0), Point::new(10.0, 30.0)),
Pin::new(Point::new(10.0, 70.0), Point::new(10.0, 70.0)),
Pin::new(Point::new(190.0, 50.0), Point::new(180.0, -30.0)),
];
let d = deform(&m, &pins);
for p in &pins {
let got = m.map(&d, p.rest);
assert!(got.distance(p.target) < 0.05, "pin {:?} → {got:?}", p.target);
}
// Area is preserved (as-rigid-as-possible): total within a few percent, no flipped triangles.
let (a0, a1): (f64, f64) =
(0..m.tris.len()).map(|t| (m.tri_area(&m.verts, t), m.tri_area(&d, t))).fold((0.0, 0.0), |s, v| (s.0 + v.0, s.1 + v.1));
assert!((a1 / a0 - 1.0).abs() < 0.05, "area ratio {}", a1 / a0);
assert!((0..m.tris.len()).all(|t| m.tri_area(&d, t) * m.tri_area(&m.verts, t) > 0.0));
// Each triangle stays nearly congruent: edge lengths change by < 25%.
let worst = m
.tris
.iter()
.flat_map(|t| (0..3).map(move |k| (t[k], t[(k + 1) % 3])))
.map(|(i, j)| (d[i].distance(d[j]) / m.verts[i].distance(m.verts[j]) - 1.0).abs())
.fold(0.0, f64::max);
assert!(worst < 0.3, "edge stretch {worst}");
}
#[test]
fn a_held_rotation_turns_the_art_around_its_pin() {
let m = rect_mesh();
let c = Point::new(100.0, 50.0);
let rot = |p: Point| {
let (s, co) = 0.4f64.sin_cos();
let d = p - c;
c + Vec2::new(d.x * co - d.y * s, d.x * s + d.y * co)
};
// One pin, held at 0.4 rad: the whole shape turns rigidly around it.
let d = deform(&m, &[Pin { angle: Some(0.4), ..Pin::new(c, c) }]);
let err = m.verts.iter().zip(&d).map(|(a, b)| rot(*a).distance(*b)).fold(0.0, f64::max);
assert!(err < 0.05, "{err}");
// A free pin alone leaves the shape where it is.
let d = deform(&m, &[Pin::new(c, c)]);
assert!(m.verts.iter().zip(&d).all(|(a, b)| a.distance(*b) < 1e-3));
// Held ends: the turned end turns, the other end stays.
let left = Point::new(10.0, 50.0);
let pins = [Pin { angle: Some(0.5), ..Pin::new(left, left) }, Pin::new(Point::new(190.0, 50.0), Point::new(190.0, 50.0))];
let d = deform(&m, &pins);
let near = m.map(&d, Point::new(10.0, 62.0)) - left;
assert!((near.atan2() - (Vec2::new(0.0, 12.0).atan2() + 0.5)).abs() < 0.1, "the left end turned: {near:?}");
assert!(m.map(&d, Point::new(190.0, 80.0)).distance(Point::new(190.0, 80.0)) < 5.0);
}
#[test]
fn default_pins_go_at_the_centre_and_the_end_of_each_limb() {
// A long bar: the centre and both ends.
let m = rect_mesh();
let p = default_pins(&m);
assert_eq!(p.len(), 3, "{p:?}");
assert!(p[0].distance(Point::new(100.0, 50.0)) < 10.0, "{p:?}");
let mut xs: Vec<f64> = p[1..].iter().map(|q| q.x).collect();
xs.sort_by(f64::total_cmp);
assert!(xs[0] < 25.0 && xs[1] > 175.0, "{p:?}");
// A five-pointed star: the centre and its five tips.
let star = vectorcraft_geom::shapes::star(Point::new(100.0, 100.0), 100.0, 35.0, 5, 0.0).to_bezpath();
let sm = Mesh::build(std::slice::from_ref(&star), star.bounding_box(), MeshOptions { resolution: 30, expand: 0.0 });
let p = default_pins(&sm);
assert_eq!(p.len(), 6, "{p:?}");
assert!(p[1..].iter().all(|q| q.distance(Point::new(100.0, 100.0)) > 55.0), "{p:?}");
// A disc has no limbs: the centre, topped up to three.
let disc = vectorcraft_geom::kurbo::Circle::new((50.0, 50.0), 50.0).to_path(0.1);
let dm = Mesh::build(std::slice::from_ref(&disc), disc.bounding_box(), MeshOptions::default());
assert_eq!(default_pins(&dm).len(), 3);
// A point with a wide Expand stays a small grid.
let dot = Mesh::build(&[], Rect::new(5.0, 5.0, 5.0, 5.0), MeshOptions { expand: 1000.0, ..Default::default() });
assert!(dot.verts.len() < 30 * 30 && default_pins(&dot).len() == 3, "{}", dot.verts.len());
}
#[test]
fn unmap_and_turn_read_a_warped_mesh_back() {
let m = rect_mesh();
let rot = |p: Point| {
let (s, c) = 0.3f64.sin_cos();
Point::new(p.x * c - p.y * s + 20.0, p.x * s + p.y * c)
};
let d: Vec<Point> = m.verts.iter().map(|v| rot(*v)).collect();
let p = Point::new(60.0, 40.0);
assert!(m.unmap(&d, rot(p)).unwrap().distance(p) < 1e-6);
assert!(m.unmap(&d, Point::new(-500.0, 0.0)).is_none(), "off the mesh");
assert!((m.turn_at(&d, p).unwrap() - 0.3).abs() < 1e-9);
assert!(m.contains(p) && !m.contains(Point::new(300.0, 50.0)));
}
#[test]
fn auto_pins_are_spread_inside_the_shape() {
let m = rect_mesh();
let p = auto_pins(&m, 3);
assert_eq!(p.len(), 3);
assert!(p.iter().all(|q| Rect::new(0.0, 0.0, 200.0, 100.0).contains(*q)));
assert!(p[1].distance(p[2]) > 100.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.