A drawing app built for agent/human collaboration
Rust
use crate::color::{from_oklab, from_u16, to_oklab, to_u16};
use crate::cut::Cut;
use crate::fill::{Coverage, Fill, FillSource};
use crate::markedit::Affine;
use crate::stroke::{Author, Mark, Sample, Stroke, fingerprint};
use anyhow::{Result, anyhow, bail};
use std::collections::BTreeMap;
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub enum Match {
#[default]
Id,
Order,
Near,
}
impl Match {
pub fn parse(text: &str) -> Result<Self> {
Ok(match text {
"" | "id" => Match::Id,
"order" => Match::Order,
"near" => Match::Near,
other => bail!("match takes id, order or near, not {other:?}"),
})
}
pub fn name(self) -> &'static str {
match self {
Match::Id => "id",
Match::Order => "order",
Match::Near => "near",
}
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub enum Unpaired {
#[default]
Leave,
Pop(f32),
Fade,
DrawOn,
}
impl Unpaired {
pub fn parse(text: &str) -> Result<Self> {
let mut words = text.split_whitespace();
let mode = match (words.next().unwrap_or(""), words.next()) {
("" | "leave", None) => Unpaired::Leave,
("pop", None) => Unpaired::Pop(0.5),
("pop", Some(at)) => {
let at: f32 = at
.parse()
.map_err(|_| anyhow!("pop takes the moment it happens, 0 to 1, not {at:?}"))?;
if !(0.0..=1.0).contains(&at) {
bail!("pop happens between 0 and 1, not at {at}");
}
Unpaired::Pop(at)
}
("fade", None) => Unpaired::Fade,
("draw-on", None) => Unpaired::DrawOn,
_ => bail!("unpaired takes leave, pop, fade or draw-on (pop may take a moment: pop 0.3), not {text:?}"),
};
if words.next().is_some() {
bail!("unpaired takes one mode, not {text:?}");
}
Ok(mode)
}
pub fn name(&self) -> String {
match self {
Unpaired::Leave => String::new(),
Unpaired::Pop(at) if *at == 0.5 => "pop".into(),
Unpaired::Pop(at) => format!("pop {at}"),
Unpaired::Fade => "fade".into(),
Unpaired::DrawOn => "draw-on".into(),
}
}
}
#[derive(Clone, Debug, Default, PartialEq)]
pub enum Spacing {
#[default]
Even,
In,
Out,
InOut,
Values(Vec<f32>),
}
impl Spacing {
pub fn parse(text: &str) -> Result<Self> {
Ok(match text.trim() {
"" | "even" => Spacing::Even,
"in" => Spacing::In,
"out" => Spacing::Out,
"in-out" | "inout" => Spacing::InOut,
list => {
let values: Vec<f32> = list
.split(',')
.map(|v| {
v.trim()
.parse::<f32>()
.map_err(|_| anyhow!("spacing {v:?} is not a number"))
})
.collect::<Result<_>>()?;
if values.iter().any(|v| !(*v > 0.0 && *v < 1.0)) {
bail!("spacing values must lie between 0 and 1 (the keys), for example 0.25,0.5,0.75");
}
if values.windows(2).any(|w| w[1] <= w[0]) {
bail!("spacing values must grow from the first key to the second");
}
Spacing::Values(values)
}
})
}
pub fn count(&self) -> Option<usize> {
match self {
Spacing::Values(v) => Some(v.len()),
_ => None,
}
}
pub fn ts(&self, count: usize) -> Vec<f32> {
let s = |i: usize| (i + 1) as f64 / (count + 1) as f64;
(0..count)
.map(|i| {
let x = s(i);
(match self {
Spacing::Even => x,
Spacing::In => x * x,
Spacing::Out => 1.0 - (1.0 - x) * (1.0 - x),
Spacing::InOut => x * x * (3.0 - 2.0 * x),
Spacing::Values(v) => v[i] as f64,
}) as f32
})
.collect()
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq)]
struct P {
x: f64,
y: f64,
p: f64,
tx: f64,
ty: f64,
time: f64,
}
fn lerp(a: f64, b: f64, t: f64) -> f64 {
a + (b - a) * t
}
fn mix(a: &P, b: &P, t: f64) -> P {
P {
x: lerp(a.x, b.x, t),
y: lerp(a.y, b.y, t),
p: lerp(a.p, b.p, t),
tx: lerp(a.tx, b.tx, t),
ty: lerp(a.ty, b.ty, t),
time: lerp(a.time, b.time, t),
}
}
fn points_of(stroke: &Stroke) -> Vec<P> {
let mut time = 0.0;
stroke
.samples
.iter()
.map(|s| {
time += s.dt_ms as f64;
let (x, y) = s.pos();
let (tx, ty) = s.tilt();
P {
x: x as f64,
y: y as f64,
p: s.pressure() as f64,
tx: tx as f64,
ty: ty as f64,
time,
}
})
.collect()
}
fn dist(a: (f64, f64), b: (f64, f64)) -> f64 {
libm::sqrt((a.0 - b.0) * (a.0 - b.0) + (a.1 - b.1) * (a.1 - b.1))
}
fn walked(points: &[P]) -> Vec<f64> {
let mut total = 0.0;
points
.iter()
.enumerate()
.map(|(i, p)| {
if i > 0 {
total += dist((points[i - 1].x, points[i - 1].y), (p.x, p.y));
}
total
})
.collect()
}
fn resample(points: &[P], n: usize) -> Vec<P> {
match (points.len(), n) {
(0, _) | (_, 0) => Vec::new(),
(1, n) => vec![points[0]; n],
(_, 1) => vec![points[0]],
_ => {
let along = walked(points);
let total = along[along.len() - 1];
if total < 1e-9 {
return (0..n)
.map(|i| mix(&points[0], &points[points.len() - 1], i as f64 / (n - 1) as f64))
.collect();
}
let mut seg = 0;
(0..n)
.map(|i| {
let at = total * i as f64 / (n - 1) as f64;
while seg + 2 < points.len() && along[seg + 1] < at {
seg += 1;
}
let span = along[seg + 1] - along[seg];
let t = if span < 1e-12 {
0.0
} else {
((at - along[seg]) / span).clamp(0.0, 1.0)
};
mix(&points[seg], &points[seg + 1], t)
})
.collect()
}
}
}
#[derive(Clone, Copy, Debug, PartialEq)]
struct Sim {
m: (f64, f64),
c: (f64, f64),
}
const SAME: Sim = Sim {
m: (1.0, 0.0),
c: (0.0, 0.0),
};
fn cmul(a: (f64, f64), b: (f64, f64)) -> (f64, f64) {
(a.0 * b.0 - a.1 * b.1, a.0 * b.1 + a.1 * b.0)
}
fn cdiv(a: (f64, f64), b: (f64, f64)) -> (f64, f64) {
let d = b.0 * b.0 + b.1 * b.1;
((a.0 * b.0 + a.1 * b.1) / d, (a.1 * b.0 - a.0 * b.1) / d)
}
fn fit(a: &[(f64, f64)], b: &[(f64, f64)]) -> Sim {
let n = a.len().max(1) as f64;
let centre = |v: &[(f64, f64)]| {
let (sx, sy) = v.iter().fold((0.0, 0.0), |(x, y), p| (x + p.0, y + p.1));
(sx / n, sy / n)
};
let (ca, cb) = (centre(a), centre(b));
let (dot, cross, norm) = a.iter().zip(b).fold((0.0, 0.0, 0.0), |(d, c, s), (p, q)| {
let (ax, ay, bx, by) = (p.0 - ca.0, p.1 - ca.1, q.0 - cb.0, q.1 - cb.1);
(d + ax * bx + ay * by, c + ax * by - ay * bx, s + ax * ax + ay * ay)
});
let m = if norm < 1e-6 || (dot.abs() < 1e-9 && cross.abs() < 1e-9) {
(1.0, 0.0)
} else {
(dot / norm, cross / norm)
};
let turned = cmul(m, ca);
Sim {
m,
c: (cb.0 - turned.0, cb.1 - turned.1),
}
}
impl Sim {
fn apply(&self, p: (f64, f64)) -> (f64, f64) {
let q = cmul(self.m, p);
(q.0 + self.c.0, q.1 + self.c.1)
}
fn then(&self, inner: &Sim) -> Sim {
let c = cmul(self.m, inner.c);
Sim {
m: cmul(self.m, inner.m),
c: (c.0 + self.c.0, c.1 + self.c.1),
}
}
fn inverse(&self) -> Sim {
let m = cdiv((1.0, 0.0), self.m);
let c = cmul(m, self.c);
Sim { m, c: (-c.0, -c.1) }
}
fn arc(&self, t: f64) -> Sim {
let scale = libm::pow(libm::sqrt(self.m.0 * self.m.0 + self.m.1 * self.m.1), t);
let angle = libm::atan2(self.m.1, self.m.0) * t;
let m = (scale * libm::cos(angle), scale * libm::sin(angle));
let gap = (1.0 - self.m.0, -self.m.1);
let ratio = match gap.0 * gap.0 + gap.1 * gap.1 < 1e-12 {
true => (t, 0.0),
false => cdiv((1.0 - m.0, -m.1), gap),
};
Sim {
m,
c: cmul(self.c, ratio),
}
}
fn affine(&self) -> [f64; 6] {
[self.m.0, -self.m.1, self.m.1, self.m.0, self.c.0, self.c.1]
}
}
fn affine32(a: [f64; 6]) -> Affine {
a.map(|v| v as f32)
}
fn xy(points: &[P]) -> Vec<(f64, f64)> {
points.iter().map(|p| (p.x, p.y)).collect()
}
pub type Lines = Vec<Vec<(f32, f32)>>;
type Ring = Vec<(f64, f64)>;
const RIDE: f64 = 1.5;
const REACH: f64 = 60.0;
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Anchor {
pub line: usize,
u: f64,
along: f64,
across: f64,
}
fn frame_at(line: &[(f64, f64)], u: f64) -> Option<((f64, f64), (f64, f64))> {
match line.len() {
0 => None,
1 => Some((line[0], (1.0, 0.0))),
_ => {
let pts: Vec<P> = line.iter().map(|&(x, y)| P { x, y, ..P::default() }).collect();
let along = walked(&pts);
let total = along[along.len() - 1];
let at = total * u.clamp(0.0, 1.0);
let seg = (0..line.len() - 1)
.find(|&i| along[i + 1] >= at)
.unwrap_or(line.len() - 2);
let span = (along[seg + 1] - along[seg]).max(1e-12);
let t = ((at - along[seg]) / span).clamp(0.0, 1.0);
let (a, b) = (line[seg], line[seg + 1]);
let (dx, dy) = (b.0 - a.0, b.1 - a.1);
let len = libm::sqrt(dx * dx + dy * dy);
let tangent = if len < 1e-12 { (1.0, 0.0) } else { (dx / len, dy / len) };
Some(((a.0 + dx * t, a.1 + dy * t), tangent))
}
}
}
fn nearest_on(line: &[(f64, f64)], at: (f64, f64), hint: Option<f64>) -> Option<(f64, f64)> {
match line.len() {
0 => None,
1 => Some((0.0, dist(line[0], at))),
_ => {
let pts: Vec<P> = line.iter().map(|&(x, y)| P { x, y, ..P::default() }).collect();
let along = walked(&pts);
let total = along[along.len() - 1].max(1e-12);
let found: Vec<(f64, f64)> = line
.windows(2)
.enumerate()
.map(|(i, w)| {
let (a, b) = (w[0], w[1]);
let (dx, dy) = (b.0 - a.0, b.1 - a.1);
let span = dx * dx + dy * dy;
let t = if span < 1e-12 {
0.0
} else {
(((at.0 - a.0) * dx + (at.1 - a.1) * dy) / span).clamp(0.0, 1.0)
};
let p = (a.0 + dx * t, a.1 + dy * t);
((along[i] + (along[i + 1] - along[i]) * t) / total, dist(p, at))
})
.collect();
let best = found.iter().map(|f| f.1).fold(f64::MAX, f64::min);
found
.into_iter()
.filter(|f| f.1 <= best + 1.0)
.min_by(|x, y| match hint {
Some(u) => (x.0 - u).abs().total_cmp(&(y.0 - u).abs()),
None => x.1.total_cmp(&y.1),
})
}
}
}
fn anchor_on(line: &[(f64, f64)], index: usize, at: (f64, f64)) -> Option<(Anchor, f64)> {
anchor_near(line, index, at, None)
}
fn anchor_near(line: &[(f64, f64)], index: usize, at: (f64, f64), hint: Option<f64>) -> Option<(Anchor, f64)> {
let (u, d) = nearest_on(line, at, hint)?;
let (p, tangent) = frame_at(line, u)?;
let (ox, oy) = (at.0 - p.0, at.1 - p.1);
Some((
Anchor {
line: index,
u,
along: ox * tangent.0 + oy * tangent.1,
across: -ox * tangent.1 + oy * tangent.0,
},
d,
))
}
pub fn anchor(lines: &[Vec<(f32, f32)>], at: (f32, f32)) -> Option<Anchor> {
let at = (at.0 as f64, at.1 as f64);
lines
.iter()
.enumerate()
.filter_map(|(i, line)| {
let line: Vec<(f64, f64)> = line.iter().map(|&(x, y)| (x as f64, y as f64)).collect();
anchor_on(&line, i, at)
})
.min_by(|a, b| a.1.total_cmp(&b.1))
.map(|(a, _)| a)
}
fn place_on(line: &[(f64, f64)], a: &Anchor) -> Option<(f64, f64)> {
let (p, tangent) = frame_at(line, a.u)?;
Some((
p.0 + a.along * tangent.0 - a.across * tangent.1,
p.1 + a.along * tangent.1 + a.across * tangent.0,
))
}
pub fn place(anchor: &Anchor, lines: &[Vec<(f32, f32)>]) -> Option<(f32, f32)> {
let line: Vec<(f64, f64)> = lines
.get(anchor.line)?
.iter()
.map(|&(x, y)| (x as f64, y as f64))
.collect();
place_on(&line, anchor).map(|(x, y)| (x as f32, y as f32))
}
fn points_of_mark(mark: &Mark) -> Vec<(f32, f32)> {
match mark {
Mark::Stroke(s) => s.samples.iter().map(Sample::pos).collect(),
Mark::Fill(f) => match &f.source {
FillSource::Polygon(points) => points.iter().map(|p| (p[0], p[1])).collect(),
FillSource::Seed { seed, .. } => vec![(seed.x, seed.y)],
FillSource::Cells { .. } => f.centre().into_iter().collect(),
},
}
}
fn wide(line: &[(f32, f32)]) -> Vec<(f64, f64)> {
line.iter().map(|&(x, y)| (x as f64, y as f64)).collect()
}
pub fn carry(mark: &Mark, from: &Lines, to: &Lines, within: Option<&[usize]>) -> Mark {
let pts = points_of_mark(mark);
if pts.is_empty() {
return mark.clone();
}
let n = pts.len() as f64;
let centre = pts
.iter()
.fold((0.0, 0.0), |a, p| (a.0 + p.0 as f64 / n, a.1 + p.1 as f64 / n));
let nearest = from
.iter()
.enumerate()
.filter(|(i, _)| within.is_none_or(|w| w.contains(i)) && to.get(*i).is_some_and(|l| !l.is_empty()))
.filter_map(|(i, line)| anchor_on(&wide(line), i, centre).map(|(_, d)| (i, d)))
.min_by(|a, b| a.1.total_cmp(&b.1).then(a.0.cmp(&b.0)))
.map(|(i, _)| i);
let Some(line) = nearest else {
return mark.clone();
};
let (src, dst) = (wide(&from[line]), wide(&to[line]));
let mv = |(x, y): (f32, f32)| -> (f32, f32) {
anchor_on(&src, line, (x as f64, y as f64))
.and_then(|(a, _)| place_on(&dst, &a))
.map_or((x, y), |(x, y)| (x as f32, y as f32))
};
let mut out = mark.clone();
match &mut out {
Mark::Stroke(s) => s.samples.iter_mut().for_each(|q| {
let (x, y) = mv(q.pos());
q.x = (x * crate::stroke::POS_SCALE).round() as i32;
q.y = (y * crate::stroke::POS_SCALE).round() as i32;
}),
Mark::Fill(f) => match &mut f.source {
FillSource::Polygon(points) => points.iter_mut().for_each(|p| {
let (x, y) = mv((p[0], p[1]));
*p = [x, y];
}),
FillSource::Seed { seed, .. } => {
(seed.x, seed.y) = mv((seed.x, seed.y));
}
FillSource::Cells { .. } => return mark.clone(),
},
}
out.cuts_mut().iter_mut().for_each(|c| {
c.map(|p| {
let (x, y) = mv((p[0], p[1]));
[x, y]
})
});
out
}
fn drawn_part(stroke: &Stroke, share: f32, from_start: bool) -> Option<Stroke> {
if share <= 0.0 || stroke.samples.len() < 2 {
return (share >= 1.0).then(|| stroke.clone());
}
if share >= 1.0 {
return Some(stroke.clone());
}
let pts: Vec<P> = points_of(stroke);
let along = walked(&pts);
let total = along[along.len() - 1];
let keep: Vec<Sample> = stroke
.samples
.iter()
.zip(&along)
.filter(|(_, d)| match from_start {
true => **d <= total * share as f64,
false => **d >= total * (1.0 - share as f64),
})
.map(|(q, _)| *q)
.collect();
(keep.len() >= 2).then(|| Stroke {
samples: keep,
..stroke.clone()
})
}
fn shown(mark: &Mark, t: f32, how: Unpaired, first: bool) -> Option<Mark> {
let presence = if first { 1.0 - t } else { t };
match (how, mark) {
(Unpaired::Leave, _) => None,
(Unpaired::Pop(at), _) => (if first { t < at } else { t >= at }).then(|| mark.clone()),
(Unpaired::Fade, Mark::Stroke(s)) => Some(Mark::Stroke(Stroke {
opacity: s.opacity * presence,
..s.clone()
})),
(Unpaired::Fade, Mark::Fill(f)) => Some(Mark::Fill(Fill {
opacity: f.opacity * presence,
..f.clone()
})),
(Unpaired::DrawOn, Mark::Stroke(s)) => drawn_part(s, presence, true).map(Mark::Stroke),
(Unpaired::DrawOn, Mark::Fill(_)) => (presence >= 0.5).then(|| mark.clone()),
}
}
pub fn line_of(stroke: &Stroke) -> Vec<(f32, f32)> {
stroke.samples.iter().map(Sample::pos).collect()
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Pair {
pub a: u32,
pub b: u32,
pub reversed: bool,
}
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Pairing {
pub pairs: Vec<Pair>,
pub alone_a: Vec<u32>,
pub alone_b: Vec<u32>,
pub clashes: Vec<(u32, u32)>,
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum Sort {
Stroke,
Polygon,
Flood,
}
fn sort_of(mark: &Mark) -> Sort {
match mark {
Mark::Stroke(_) => Sort::Stroke,
Mark::Fill(f) => match f.source {
FillSource::Polygon(_) => Sort::Polygon,
FillSource::Seed { .. } | FillSource::Cells { .. } => Sort::Flood,
},
}
}
fn outline(mark: &Mark) -> Vec<P> {
match mark {
Mark::Stroke(s) => points_of(s),
Mark::Fill(f) => match &f.source {
FillSource::Polygon(points) => points
.iter()
.chain(points.first())
.map(|p| P {
x: p[0] as f64,
y: p[1] as f64,
..P::default()
})
.collect(),
FillSource::Seed { seed, .. } => vec![P {
x: seed.x as f64,
y: seed.y as f64,
..P::default()
}],
FillSource::Cells { .. } => f
.centre()
.map(|(x, y)| P {
x: x as f64,
y: y as f64,
..P::default()
})
.into_iter()
.collect(),
},
}
}
fn shape_cost(a: &Mark, b: &Mark) -> (f64, bool) {
let (pa, pb) = (resample(&outline(a), 16), resample(&outline(b), 16));
let mean = |q: &[P]| pa.iter().zip(q).map(|(x, y)| dist((x.x, x.y), (y.x, y.y))).sum::<f64>() / 16.0;
let forward = mean(&pb);
let back: Vec<P> = pb.iter().rev().copied().collect();
let backward = mean(&back);
match a.as_stroke().is_some() && backward < forward {
true => (backward, true),
false => (forward, false),
}
}
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Parts {
pub a: BTreeMap<String, Vec<u32>>,
pub b: BTreeMap<String, Vec<u32>>,
}
impl Parts {
pub fn shared(&self) -> Vec<(String, Vec<u32>, Vec<u32>)> {
self.a
.iter()
.filter_map(|(name, xs)| self.b.get(name).map(|ys| (name.clone(), xs.clone(), ys.clone())))
.collect()
}
fn named(parts: &BTreeMap<String, Vec<u32>>) -> BTreeMap<u32, &str> {
parts
.iter()
.flat_map(|(name, ids)| ids.iter().map(move |id| (*id, name.as_str())))
.collect()
}
}
fn nearest(free_a: &[&Mark], free_b: &[&Mark], xs: &[u32], ys: &[u32]) -> Vec<(u32, u32, bool)> {
let mut costs: Vec<(f64, u32, u32, bool)> = free_a
.iter()
.filter(|x| xs.contains(&x.id()))
.flat_map(|x| {
free_b
.iter()
.filter(|y| ys.contains(&y.id()) && sort_of(x) == sort_of(y))
.map(|y| {
let (cost, rev) = shape_cost(x, y);
(cost, x.id(), y.id(), rev)
})
.collect::<Vec<_>>()
})
.collect();
costs.sort_by(|p, q| p.0.total_cmp(&q.0).then(p.1.cmp(&q.1)).then(p.2.cmp(&q.2)));
let mut used_a = Vec::new();
let mut used_b = Vec::new();
costs
.into_iter()
.filter(|(_, x, y, _)| {
let fresh = !used_a.contains(x) && !used_b.contains(y);
if fresh {
used_a.push(*x);
used_b.push(*y);
}
fresh
})
.map(|(_, x, y, rev)| (x, y, rev))
.collect()
}
pub fn pair(a: &[Mark], b: &[Mark], how: Match, forced: &[[u32; 2]]) -> Pairing {
pair_parts(a, b, how, forced, &Parts::default())
}
pub fn pair_parts(a: &[Mark], b: &[Mark], how: Match, forced: &[[u32; 2]], parts: &Parts) -> Pairing {
let (in_a, in_b) = (Parts::named(&parts.a), Parts::named(&parts.b));
let apart = |x: u32, y: u32| matches!((in_a.get(&x), in_b.get(&y)), (Some(p), Some(q)) if p != q);
let mut out = Pairing::default();
let mut free_a: Vec<&Mark> = a.iter().collect();
let mut free_b: Vec<&Mark> = b.iter().collect();
let take = |out: &mut Pairing, free_a: &mut Vec<&Mark>, free_b: &mut Vec<&Mark>, x: u32, y: u32, rev: bool| {
let (Some(i), Some(j)) = (
free_a.iter().position(|m| m.id() == x),
free_b.iter().position(|m| m.id() == y),
) else {
return;
};
if sort_of(free_a[i]) != sort_of(free_b[j]) {
out.clashes.push((x, y));
} else {
out.pairs.push(Pair {
a: x,
b: y,
reversed: rev,
});
}
free_a.remove(i);
free_b.remove(j);
};
forced
.iter()
.for_each(|[x, y]| take(&mut out, &mut free_a, &mut free_b, *x, *y, false));
parts.shared().iter().for_each(|(_, xs, ys)| {
[Sort::Stroke, Sort::Polygon, Sort::Flood].iter().for_each(|sort| {
let mine = |free: &[&Mark], ids: &[u32]| -> Vec<u32> {
free.iter()
.filter(|m| sort_of(m) == *sort && ids.contains(&m.id()))
.map(|m| m.id())
.collect()
};
let (left, right) = (mine(&free_a, xs), mine(&free_b, ys));
let chosen: Vec<(u32, u32, bool)> = match left.len() == right.len() {
true => left.iter().zip(&right).map(|(&x, &y)| (x, y, false)).collect(),
false => nearest(&free_a, &free_b, &left, &right),
};
chosen
.into_iter()
.for_each(|(x, y, rev)| take(&mut out, &mut free_a, &mut free_b, x, y, rev));
});
});
match how {
Match::Id => {
let ids: Vec<u32> = free_a.iter().map(|m| m.id()).collect();
ids.iter()
.filter(|&&id| !apart(id, id))
.for_each(|&id| take(&mut out, &mut free_a, &mut free_b, id, id, false));
}
Match::Order => {
[Sort::Stroke, Sort::Polygon, Sort::Flood].iter().for_each(|sort| {
let xs: Vec<u32> = free_a.iter().filter(|m| sort_of(m) == *sort).map(|m| m.id()).collect();
let ys: Vec<u32> = free_b.iter().filter(|m| sort_of(m) == *sort).map(|m| m.id()).collect();
xs.iter()
.zip(&ys)
.filter(|(x, y)| !apart(**x, **y))
.for_each(|(&x, &y)| take(&mut out, &mut free_a, &mut free_b, x, y, false));
});
}
Match::Near => {
let (xs, ys): (Vec<u32>, Vec<u32>) = (
free_a.iter().map(|m| m.id()).collect(),
free_b.iter().map(|m| m.id()).collect(),
);
nearest(&free_a, &free_b, &xs, &ys)
.into_iter()
.filter(|(x, y, _)| !apart(*x, *y))
.for_each(|(x, y, rev)| take(&mut out, &mut free_a, &mut free_b, x, y, rev));
}
}
let order: BTreeMap<u32, usize> = a.iter().enumerate().map(|(i, m)| (m.id(), i)).collect();
out.pairs
.sort_by_key(|p| order.get(&p.a).copied().unwrap_or(usize::MAX));
out.alone_a = free_a.iter().map(|m| m.id()).collect();
out.alone_b = free_b.iter().map(|m| m.id()).collect();
out
}
#[derive(Clone, Copy, Debug, PartialEq)]
struct Touch {
other: usize,
u: (f64, f64),
along: (f64, f64),
across: (f64, f64),
}
#[derive(Clone, Debug, PartialEq)]
struct StrokePlan {
a: Stroke,
b: Stroke,
pa: Vec<P>,
pb: Vec<P>,
own: Sim,
rel: Sim,
parent: Option<usize>,
carrier: Option<Sim>,
rest: Vec<(f64, f64)>,
touches: [Option<Touch>; 2],
}
const TOUCH: f64 = 2.0;
const INSIDE: f64 = 0.9;
const ROUND: f64 = 0.5;
const FITS: f64 = 0.15;
const TURNS_WITH: f64 = 30.0;
const SLACK: f64 = 0.1;
#[derive(Clone, Copy, Debug, PartialEq)]
enum Ride {
Own,
Inside {
on: usize,
rel: Option<Sim>,
},
Joined {
on: usize,
at: ((f64, f64), (f64, f64)),
slack: f64,
},
}
#[derive(Clone, Debug, PartialEq)]
struct ShapePlan {
a: Fill,
b: Fill,
pa: Vec<(f64, f64)>,
pb: Vec<(f64, f64)>,
fit: Sim,
rest: Vec<(f64, f64)>,
ride: Ride,
}
fn sq(v: f64) -> f64 {
v * v
}
fn ring(points: &[(f64, f64)]) -> &[(f64, f64)] {
&points[..points.len().saturating_sub(1)]
}
fn centre(points: &[(f64, f64)]) -> (f64, f64) {
let n = points.len().max(1) as f64;
points.iter().fold((0.0, 0.0), |(x, y), p| (x + p.0 / n, y + p.1 / n))
}
fn spread(points: &[(f64, f64)]) -> f64 {
let c = centre(points);
points.iter().map(|p| sq(p.0 - c.0) + sq(p.1 - c.1)).sum()
}
fn area(points: &[(f64, f64)]) -> f64 {
points
.iter()
.zip(points.iter().cycle().skip(1))
.map(|(p, q)| p.0 * q.1 - q.0 * p.1)
.sum::<f64>()
.abs()
/ 2.0
}
fn roundness(points: &[(f64, f64)]) -> f64 {
let c = centre(points);
let (xx, yy, xy) = points.iter().fold((0.0, 0.0, 0.0), |(a, b, d), p| {
let (dx, dy) = (p.0 - c.0, p.1 - c.1);
(a + dx * dx, b + dy * dy, d + dx * dy)
});
let (half, det) = ((xx + yy) / 2.0, xx * yy - xy * xy);
let gap = libm::sqrt((half * half - det).max(0.0));
if half + gap <= 0.0 {
1.0
} else {
(half - gap) / (half + gap)
}
}
fn inside(at: (f64, f64), ring: &[(f64, f64)]) -> bool {
ring.iter()
.zip(ring.iter().cycle().skip(1))
.filter(|(p, q)| (p.1 > at.1) != (q.1 > at.1) && at.0 < p.0 + (at.1 - p.1) * (q.0 - p.0) / (q.1 - p.1))
.count()
% 2
== 1
}
fn edge(at: (f64, f64), ring: &[(f64, f64)]) -> f64 {
ring.iter()
.zip(ring.iter().cycle().skip(1))
.map(|(p, q)| {
let (dx, dy) = (q.0 - p.0, q.1 - p.1);
let span = dx * dx + dy * dy;
let t = if span < 1e-12 {
0.0
} else {
(((at.0 - p.0) * dx + (at.1 - p.1) * dy) / span).clamp(0.0, 1.0)
};
dist(at, (p.0 + dx * t, p.1 + dy * t))
})
.fold(f64::MAX, f64::min)
}
fn boxed(ring: &[(f64, f64)]) -> (f64, f64, f64, f64) {
ring.iter().fold((f64::MAX, f64::MAX, f64::MIN, f64::MIN), |b, p| {
(b.0.min(p.0), b.1.min(p.1), b.2.max(p.0), b.3.max(p.1))
})
}
fn held(child: &[(f64, f64)], parent: &[(f64, f64)]) -> Vec<(f64, f64)> {
let (x0, y0, x1, y1) = boxed(parent);
child
.iter()
.copied()
.filter(|p| p.0 >= x0 - TOUCH && p.0 <= x1 + TOUCH && p.1 >= y0 - TOUCH && p.1 <= y1 + TOUCH)
.filter(|&p| inside(p, parent) || edge(p, parent) <= TOUCH)
.collect()
}
fn share(child: &[(f64, f64)], parent: &[(f64, f64)]) -> f64 {
held(child, parent).len() as f64 / child.len().max(1) as f64
}
fn touching(x: &[(f64, f64)], y: &[(f64, f64)]) -> bool {
let (a, b) = (boxed(x), boxed(y));
let apart = a.0 > b.2 + TOUCH || b.0 > a.2 + TOUCH || a.1 > b.3 + TOUCH || b.1 > a.3 + TOUCH;
!apart && (!held(x, y).is_empty() || !held(y, x).is_empty())
}
fn meeting(child: &[(f64, f64)], parent: &[(f64, f64)]) -> (f64, f64) {
let found = held(child, parent);
match found.is_empty() {
false => centre(&found),
true => child
.iter()
.copied()
.min_by(|p, q| edge(*p, parent).total_cmp(&edge(*q, parent)))
.unwrap_or((0.0, 0.0)),
}
}
fn shifted(points: &[(f64, f64)], k: usize) -> Vec<(f64, f64)> {
let r = ring(points);
r[k..].iter().chain(&r[..k]).chain(r.get(k)).copied().collect()
}
fn misfits(pa: &[(f64, f64)], pb: &[(f64, f64)]) -> Vec<f64> {
let centred = |v: &[(f64, f64)]| {
let c = centre(v);
v.iter().map(|p| (p.0 - c.0, p.1 - c.1)).collect::<Vec<_>>()
};
let (a, b) = (centred(ring(pa)), centred(ring(pb)));
let (na, nb) = (spread(ring(pa)), spread(ring(pb)));
(0..b.len())
.map(|k| {
let (re, im) = a.iter().enumerate().fold((0.0, 0.0), |(re, im), (i, p)| {
let q = b[(i + k) % b.len()];
(re + p.0 * q.0 + p.1 * q.1, im + p.0 * q.1 - p.1 * q.0)
});
if na < 1e-9 { nb } else { nb - (re * re + im * im) / na }
})
.collect()
}
fn turn(s: &Sim) -> f64 {
libm::atan2(s.m.1, s.m.0) * (180.0 / std::f64::consts::PI)
}
fn turned_apart(a: f64, b: f64) -> f64 {
((a - b).rem_euclid(360.0) + 180.0).rem_euclid(360.0) - 180.0
}
fn start_with(pa: &[(f64, f64)], pb: &[(f64, f64)], turning: f64) -> (usize, f64, Sim) {
let e = misfits(pa, pb);
let best = e.iter().copied().fold(f64::MAX, f64::min);
let floor = 1e-9 * spread(ring(pb));
(0..e.len())
.filter(|&k| e[k] <= 2.0 * best + floor)
.map(|k| (k, e[k], fit(pa, &shifted(pb, k))))
.min_by(|x, y| {
turned_apart(turn(&x.2), turning)
.abs()
.total_cmp(&turned_apart(turn(&y.2), turning).abs())
.then(x.1.total_cmp(&y.1))
.then(x.0.cmp(&y.0))
})
.unwrap_or((0, e.first().copied().unwrap_or(0.0), fit(pa, pb)))
}
fn rest_of(pa: &[(f64, f64)], pb: &[(f64, f64)], f: &Sim) -> Vec<(f64, f64)> {
pa.iter()
.zip(pb)
.map(|(p, q)| {
let m = f.apply(*p);
(q.0 - m.0, q.1 - m.1)
})
.collect()
}
#[derive(Clone, Debug, PartialEq)]
enum Item {
Stroke(StrokePlan),
Polygon(ShapePlan),
Flood { a: Fill, b: Fill },
}
#[derive(Clone, Debug, PartialEq)]
pub struct Plan {
items: Vec<Item>,
order: Vec<usize>,
fills: Vec<usize>,
pub pairing: Pairing,
alone: (Vec<Mark>, Vec<Mark>),
}
fn planned_points(pa: &[P], pb: &[P]) -> (Sim, Vec<(f64, f64)>) {
let (xa, xb) = (xy(pa), xy(pb));
let f = fit(&xa, &xb);
let rest = xa
.iter()
.zip(&xb)
.map(|(p, q)| {
let m = f.apply(*p);
(q.0 - m.0, q.1 - m.1)
})
.collect();
(f, rest)
}
fn reach(stroke: &Stroke) -> f64 {
stroke.size as f64 / 2.0 + 2.0
}
fn touch_of(
strokes: &[(&Stroke, Vec<(f64, f64)>)],
me: usize,
end: usize,
hint: Option<(usize, f64)>,
) -> Option<(usize, f64, f64, f64)> {
let (own, line) = &strokes[me];
let at = match end {
0 => *line.first()?,
_ => *line.last()?,
};
let slack = own.size as f64 * 0.25;
strokes
.iter()
.enumerate()
.filter(|(i, _)| *i != me && hint.is_none_or(|(h, _)| h == *i))
.filter_map(|(i, (stroke, other))| {
let (anchor, d) = anchor_near(other, i, at, hint.map(|(_, u)| u))?;
(d <= reach(stroke) + slack).then_some((i, anchor, d))
})
.min_by(|x, y| x.2.total_cmp(&y.2))
.map(|(i, a, _)| (i, a.u, a.along, a.across))
}
pub fn plan(a: &[Mark], b: &[Mark], how: Match, forced: &[[u32; 2]]) -> Plan {
plan_parts(a, b, how, forced, &Parts::default())
}
pub fn plan_parts(a: &[Mark], b: &[Mark], how: Match, forced: &[[u32; 2]], parts: &Parts) -> Plan {
let pairing = pair_parts(a, b, how, forced, parts);
let find = |marks: &[Mark], id: u32| marks.iter().find(|m| m.id() == id).cloned();
let items: Vec<Item> = pairing
.pairs
.iter()
.filter_map(|p| Some((p, find(a, p.a)?, find(b, p.b)?)))
.map(|(p, ma, mb)| match (ma, mb) {
(Mark::Stroke(sa), Mark::Stroke(sb)) => {
let (oa, mut ob) = (points_of(&sa), points_of(&sb));
if p.reversed {
let end = ob.last().map_or(0.0, |q| q.time);
ob.reverse();
ob.iter_mut().for_each(|q| q.time = end - q.time);
}
let n = oa.len().max(ob.len()).max(1);
let (pa, pb) = (resample(&oa, n), resample(&ob, n));
let (own, rest) = planned_points(&pa, &pb);
Item::Stroke(StrokePlan {
a: sa,
b: sb,
pa,
pb,
own,
rel: own,
parent: None,
carrier: None,
rest,
touches: [None, None],
})
}
(Mark::Fill(fa), Mark::Fill(fb)) => match (&fa.source, &fb.source) {
(FillSource::Polygon(_), FillSource::Polygon(_)) => {
let (oa, ob) = (outline(&Mark::Fill(fa.clone())), outline(&Mark::Fill(fb.clone())));
let n = oa.len().max(ob.len()).max(4);
let (pa, pb) = (resample(&oa, n), resample(&ob, n));
let (fit, rest) = planned_points(&pa, &pb);
Item::Polygon(ShapePlan {
a: fa,
b: fb,
pa: xy(&pa),
pb: xy(&pb),
fit,
rest,
ride: Ride::Own,
})
}
_ => Item::Flood { a: fa, b: fb },
},
_ => unreachable!("pairs share their kind"),
})
.collect();
let alone = |marks: &[Mark], ids: &[u32], clashed: &[u32]| -> Vec<Mark> {
marks
.iter()
.filter(|m| ids.contains(&m.id()) || clashed.contains(&m.id()))
.cloned()
.collect()
};
let (clash_a, clash_b): (Vec<u32>, Vec<u32>) = pairing.clashes.iter().copied().unzip();
let alone = (
alone(a, &pairing.alone_a, &clash_a),
alone(b, &pairing.alone_b, &clash_b),
);
let mut plan = Plan {
items,
order: Vec::new(),
fills: Vec::new(),
pairing,
alone,
};
plan.find_touches();
plan.link_parents();
plan.link_fills();
plan
}
impl Plan {
fn find_touches(&mut self) {
let strokes: Vec<usize> = (0..self.items.len())
.filter(|&i| matches!(self.items[i], Item::Stroke(_)))
.collect();
let side = |pick_b: bool| -> Vec<(&Stroke, Vec<(f64, f64)>)> {
strokes
.iter()
.map(|&i| match &self.items[i] {
Item::Stroke(s) if pick_b => (&s.b, xy(&s.pb)),
Item::Stroke(s) => (&s.a, xy(&s.pa)),
_ => unreachable!(),
})
.collect()
};
let (in_a, in_b) = (side(false), side(true));
let found: Vec<(usize, usize, Touch)> = (0..strokes.len())
.flat_map(|k| (0..2).map(move |end| (k, end)))
.filter_map(|(k, end)| {
let ta = touch_of(&in_a, k, end, None)?;
let tb = touch_of(&in_b, k, end, Some((ta.0, ta.1)))?;
((tb.1 - ta.1).abs() <= 0.5).then(|| {
(
strokes[k],
end,
Touch {
other: strokes[ta.0],
u: (ta.1, tb.1),
along: (ta.2, tb.2),
across: (ta.3, tb.3),
},
)
})
})
.collect();
found.into_iter().for_each(|(i, end, touch)| {
if let Item::Stroke(s) = &mut self.items[i] {
s.touches[end] = Some(touch);
}
});
}
fn link_parents(&mut self) {
let strokes: Vec<usize> = (0..self.items.len())
.filter(|&i| matches!(self.items[i], Item::Stroke(_)))
.collect();
let stroke = |i: usize| match &self.items[i] {
Item::Stroke(s) => Some(s),
_ => None,
};
let length = |i: usize| stroke(i).map_or(0.0, |s| walked(&s.pa).last().copied().unwrap_or(0.0));
let centre = |i: usize| {
stroke(i).map_or((0.0, 0.0), |s| {
let n = s.pa.len().max(1) as f64;
let (x, y) = s.pa.iter().fold((0.0, 0.0), |(x, y), p| (x + p.x, y + p.y));
(x / n, y / n)
})
};
let parent: BTreeMap<usize, usize> = strokes
.iter()
.filter_map(|&i| {
let mine = length(i);
stroke(i)?
.touches
.iter()
.flatten()
.map(|t| t.other)
.filter(|&o| length(o) > mine && length(o) >= RIDE * mine)
.max_by(|x, y| length(*x).total_cmp(&length(*y)).then(y.cmp(x)))
.map(|p| (i, p))
})
.collect();
let cell = |p: (f64, f64)| ((p.0 / REACH).floor() as i64, (p.1 / REACH).floor() as i64);
let mut grid: BTreeMap<(i64, i64), Vec<usize>> = BTreeMap::new();
strokes
.iter()
.for_each(|&i| grid.entry(cell(centre(i))).or_default().push(i));
let carriers: BTreeMap<usize, Sim> = strokes
.iter()
.filter(|i| !parent.contains_key(i))
.filter_map(|&i| {
let s = stroke(i)?;
let c = centre(i);
let (gx, gy) = cell(c);
let mut near: Vec<usize> = (gx - 1..=gx + 1)
.flat_map(|x| (gy - 1..=gy + 1).map(move |y| (x, y)))
.filter_map(|k| grid.get(&k))
.flatten()
.copied()
.filter(|&j| dist(centre(j), c) <= REACH)
.collect();
near.sort_unstable();
let guess: Vec<(usize, (f64, f64))> = near
.iter()
.filter_map(|&j| stroke(j).map(|o| (j, o.own.apply(c))))
.collect();
let here = s.own.apply(c);
let close = |to: (f64, f64)| -> Vec<usize> {
let reach = (0.15 * dist(to, c)).max(6.0);
guess
.iter()
.filter(|(_, q)| dist(*q, to) <= reach)
.map(|(j, _)| *j)
.collect()
};
let mut kept = close(here);
if kept.len() < 3 {
let middle = |pick: fn(&(f64, f64)) -> f64| {
let mut v: Vec<f64> = guess.iter().map(|(_, q)| pick(q)).collect();
v.sort_by(f64::total_cmp);
v.get(v.len() / 2).copied().unwrap_or(0.0)
};
kept = close((middle(|q| q.0), middle(|q| q.1)));
}
if kept.len() < 2 {
return None;
}
let (from, to): (Ring, Ring) = kept
.iter()
.filter_map(|&j| stroke(j))
.flat_map(|o| o.pa.iter().zip(&o.pb).map(|(p, q)| ((p.x, p.y), (q.x, q.y))))
.unzip();
Some((i, fit(&from, &to)))
})
.collect();
let mut order = strokes.clone();
order.sort_by(|x, y| length(*y).total_cmp(&length(*x)).then(x.cmp(y)));
let owns: Vec<Sim> = self
.items
.iter()
.map(|item| match item {
Item::Stroke(s) => s.own,
_ => SAME,
})
.collect();
self.items.iter_mut().enumerate().for_each(|(i, item)| {
if let Item::Stroke(s) = item {
s.parent = parent.get(&i).copied();
s.carrier = carriers.get(&i).copied();
s.rel = match (s.parent, s.carrier) {
(Some(p), _) => owns[p].inverse().then(&s.own),
(None, Some(c)) => c.inverse().then(&s.own),
(None, None) => s.own,
};
}
});
self.order = order;
}
fn link_fills(&mut self) {
let shape = |items: &[Item], i: usize| match &items[i] {
Item::Polygon(f) => f.clone(),
_ => unreachable!("only polygons"),
};
let size = |f: &ShapePlan| (area(ring(&f.pa)) + area(ring(&f.pb))) / 2.0;
let mut order: Vec<usize> = (0..self.items.len())
.filter(|&i| matches!(self.items[i], Item::Polygon(_)))
.collect();
order.sort_by(|&x, &y| {
size(&shape(&self.items, y))
.total_cmp(&size(&shape(&self.items, x)))
.then(x.cmp(&y))
});
let near = |items: &[Item], x: usize, y: usize| {
let (f, g) = (shape(items, x), shape(items, y));
touching(ring(&f.pa), ring(&g.pa)) && touching(ring(&f.pb), ring(&g.pb))
};
let held_by = |items: &[Item], x: usize, y: usize| {
let (f, g) = (shape(items, x), shape(items, y));
share(ring(&f.pa), ring(&g.pa)).min(share(ring(&f.pb), ring(&g.pb)))
};
(0..order.len()).for_each(|rank| {
let i = order[rank];
let me = shape(&self.items, i);
let larger: Vec<usize> = order[..rank]
.iter()
.copied()
.filter(|&j| !matches!(shape(&self.items, j).ride, Ride::Inside { .. }))
.filter(|&j| near(&self.items, i, j))
.collect();
let container = larger
.iter()
.rev()
.copied()
.find(|&j| held_by(&self.items, i, j) >= INSIDE);
let joined = larger
.iter()
.enumerate()
.max_by(|x, y| {
held_by(&self.items, i, *x.1)
.total_cmp(&held_by(&self.items, i, *y.1))
.then(y.0.cmp(&x.0))
})
.map(|(_, &j)| j);
let planned = match (container, joined) {
(Some(on), _) => {
let parent = shape(&self.items, on).fit;
let (k, e, own) = start_with(&me.pa, &me.pb, turn(&parent));
let fits = libm::sqrt(e / spread(ring(&me.pb)).max(1e-9)) <= FITS;
let round = roundness(ring(&me.pa)).max(roundness(ring(&me.pb))) > ROUND;
match fits && !round {
true => {
let pb = shifted(&me.pb, k);
let rest = rest_of(&me.pa, &pb, &own);
ShapePlan {
pb,
fit: own,
rest,
ride: Ride::Inside {
on,
rel: Some(parent.inverse().then(&own)),
},
..me
}
}
false => {
let carried: Vec<(f64, f64)> = ring(&me.pa).iter().map(|&p| parent.apply(p)).collect();
let cost = |k: usize| {
let b = shifted(&me.pb, k);
carried
.iter()
.zip(&b)
.map(|(p, q)| sq(p.0 - q.0) + sq(p.1 - q.1))
.sum::<f64>()
};
let best = (0..carried.len())
.min_by(|&x, &y| cost(x).total_cmp(&cost(y)).then(x.cmp(&y)))
.unwrap_or(0);
let k = if cost(best) < 0.5 * cost(0) { best } else { 0 };
let pb = shifted(&me.pb, k);
let rest = rest_of(&me.pa, &pb, &parent);
ShapePlan {
pb,
fit: parent,
rest,
ride: Ride::Inside { on, rel: None },
..me
}
}
}
}
(None, Some(on)) => {
let up = shape(&self.items, on);
let (k, e, own) = start_with(&me.pa, &me.pb, turn(&up.fit));
let e0 = misfits(&me.pa, &me.pb).first().copied().unwrap_or(0.0);
let better = k != 0
&& e <= 0.5 * e0
&& turned_apart(turn(&own), turn(&up.fit)).abs() + TURNS_WITH
<= turned_apart(turn(&me.fit), turn(&up.fit)).abs();
let (pb, fit) = match better {
true => (shifted(&me.pb, k), own),
false => (me.pb.clone(), me.fit),
};
let rest = rest_of(&me.pa, &pb, &fit);
let at = (meeting(ring(&me.pa), ring(&up.pa)), meeting(ring(&me.pb), ring(&up.pb)));
ShapePlan {
pb,
fit,
rest,
ride: Ride::Joined {
on,
at,
slack: SLACK * libm::sqrt(size(&me)),
},
..me
}
}
(None, None) => me,
};
self.items[i] = Item::Polygon(planned);
});
self.fills = order;
}
pub fn fill_rides(&self) -> (usize, usize) {
self.items.iter().fold((0, 0), |(inside, joined), item| match item {
Item::Polygon(ShapePlan {
ride: Ride::Inside { .. },
..
}) => (inside + 1, joined),
Item::Polygon(ShapePlan {
ride: Ride::Joined { .. },
..
}) => (inside, joined + 1),
_ => (inside, joined),
})
}
pub fn touching_ends(&self) -> usize {
self.items
.iter()
.map(|item| match item {
Item::Stroke(s) => s.touches.iter().flatten().count(),
_ => 0,
})
.sum()
}
pub fn floods(&self) -> Vec<(&Fill, &Fill)> {
self.items
.iter()
.filter_map(|item| match item {
Item::Flood { a, b } => Some((a, b)),
_ => None,
})
.collect()
}
pub fn unpaired_at(&self, t: f32, how: Unpaired, now: &Lines) -> Vec<Mark> {
let (la, lb) = self.key_lines();
let side = |marks: &[Mark], lines: &Lines, first: bool| -> Vec<Mark> {
marks
.iter()
.filter(|m| !matches!(m, Mark::Fill(f) if matches!(f.source, FillSource::Seed { .. })))
.filter_map(|m| shown(&carry(m, lines, now, None), t, how, first))
.collect()
};
side(&self.alone.0, &la, true)
.into_iter()
.chain(side(&self.alone.1, &lb, false))
.collect()
}
pub fn unpaired_floods(&self) -> usize {
self.alone
.0
.iter()
.chain(&self.alone.1)
.filter(|m| matches!(m, Mark::Fill(f) if matches!(f.source, FillSource::Seed { .. })))
.count()
}
pub fn key_lines(&self) -> (Lines, Lines) {
let strokes: Vec<&StrokePlan> = self
.items
.iter()
.filter_map(|item| match item {
Item::Stroke(s) => Some(s),
_ => None,
})
.collect();
let line = |pts: &[P]| pts.iter().map(|p| (p.x as f32, p.y as f32)).collect::<Vec<_>>();
(
strokes.iter().map(|s| line(&s.pa)).collect(),
strokes.iter().map(|s| line(&s.pb)).collect(),
)
}
pub fn at(&self, t: f32) -> Vec<Mark> {
let t64 = t as f64;
let mut moved: Vec<Option<Sim>> = vec![None; self.items.len()];
self.order.iter().for_each(|&i| {
if let Item::Stroke(s) = &self.items[i] {
let own = s.rel.arc(t64);
moved[i] = Some(match (s.parent.and_then(|p| moved[p]), s.carrier) {
(Some(up), _) => up.then(&own),
(None, Some(c)) => c.arc(t64).then(&own),
(None, None) => own,
});
}
});
self.fills.iter().for_each(|&i| {
let Item::Polygon(f) = &self.items[i] else {
return;
};
let own = f.fit.arc(t64);
let up = |j: usize| moved[j].unwrap_or(SAME);
let motion = match f.ride {
Ride::Own => own,
Ride::Inside { on, rel: Some(rel) } => up(on).then(&rel.arc(t64)),
Ride::Inside { on, rel: None } => up(on),
Ride::Joined {
on,
at: (xa, xb),
slack,
} => {
let whole = match &self.items[on] {
Item::Polygon(p) => p.fit,
_ => SAME,
};
let carried = |m: &Sim, total: &Sim| {
let (p, q) = (m.apply(xa), total.apply(xa));
(p.0 + (xb.0 - q.0) * t64, p.1 + (xb.1 - q.1) * t64)
};
let (want, have) = (carried(&up(on), &whole), carried(&own, &f.fit));
let (dx, dy) = (want.0 - have.0, want.1 - have.1);
let gap = libm::sqrt(dx * dx + dy * dy);
let k = if gap > slack { 1.0 - slack / gap } else { 0.0 };
Sim {
m: own.m,
c: (own.c.0 + dx * k, own.c.1 + dy * k),
}
}
};
moved[i] = Some(motion);
});
let mut lines: Vec<Option<Vec<P>>> = self
.items
.iter()
.enumerate()
.map(|(i, item)| match item {
Item::Stroke(s) => {
let a = moved[i].unwrap_or(SAME);
Some(
s.pa.iter()
.zip(&s.pb)
.zip(&s.rest)
.map(|((p, q), r)| {
let (x, y) = a.apply((p.x, p.y));
P {
x: x + r.0 * t64,
y: y + r.1 * t64,
..mix(p, q, t64)
}
})
.collect(),
)
}
_ => None,
})
.collect();
(0..self.items.len()).for_each(|i| {
let Item::Stroke(s) = &self.items[i] else {
return;
};
(0..2).for_each(|end| {
let Some(touch) = s.touches[end] else {
return;
};
let Some(other) = lines[touch.other].as_ref().map(|l| xy(l)) else {
return;
};
let anchor = Anchor {
line: 0,
u: lerp(touch.u.0, touch.u.1, t64),
along: lerp(touch.along.0, touch.along.1, t64),
across: lerp(touch.across.0, touch.across.1, t64),
};
let Some(target) = place_on(&other, &anchor) else {
return;
};
if let Some(line) = lines[i].as_mut() {
snap(line, end, target);
}
});
});
self.items
.iter()
.zip(lines)
.zip(moved)
.map(|((item, line), sim)| match (item, line) {
(Item::Stroke(s), Some(line)) => Mark::Stroke(stroke_at(s, &line, sim.unwrap_or(SAME), t)),
(Item::Polygon(f), _) => Mark::Fill(polygon_at(f, sim.unwrap_or_else(|| f.fit.arc(t as f64)), t)),
(Item::Flood { a, b }, _) => Mark::Fill(flood_at(a, b, t)),
_ => unreachable!(),
})
.collect()
}
}
fn snap(line: &mut [P], end: usize, target: (f64, f64)) {
if line.is_empty() {
return;
}
let order: Vec<usize> = match end {
0 => (0..line.len()).collect(),
_ => (0..line.len()).rev().collect(),
};
let at = line[order[0]];
let (dx, dy) = (target.0 - at.x, target.1 - at.y);
if dx * dx + dy * dy < 1e-6 {
return;
}
let ordered: Vec<P> = order.iter().map(|&i| line[i]).collect();
let along = walked(&ordered);
let total = along[along.len() - 1];
let span = (total * 0.35).clamp(1e-3, 48.0);
order.iter().zip(along).for_each(|(&i, s)| {
if s < span {
let x = 1.0 - s / span;
let w = x * x * (3.0 - 2.0 * x);
line[i].x += dx * w;
line[i].y += dy * w;
}
});
}
fn lerp32(a: f32, b: f32, t: f32) -> f32 {
a + (b - a) * t
}
fn colour(a: [u16; 4], b: [u16; 4], t: f32) -> [u16; 4] {
if a == b {
return a;
}
let (ca, cb) = (from_u16(a), from_u16(b));
let (la, lb) = (to_oklab(ca), to_oklab(cb));
let lab = std::array::from_fn(|i| lerp32(la[i], lb[i], t));
to_u16(from_oklab(lab, lerp32(ca[3], cb[3], t)))
}
fn stroke_at(s: &StrokePlan, line: &[P], sim: Sim, t: f32) -> Stroke {
let mut last = 0.0;
let samples = line
.iter()
.enumerate()
.map(|(i, p)| {
let dt = if i == 0 { 0.0 } else { (p.time - last).max(0.0) };
last = p.time;
Sample::quantize(
p.x as f32,
p.y as f32,
p.p as f32,
(p.tx as f32, p.ty as f32),
dt as f32,
)
})
.collect();
let mut cuts = s.a.cuts.clone();
let a = affine32(sim.affine());
cuts.iter_mut().for_each(|c| {
c.map(|p| {
let (x, y) = crate::markedit::apply_affine(a, (p[0], p[1]));
[x, y]
})
});
Stroke {
id: s.a.id,
brush: if t < 0.5 { s.a.brush.clone() } else { s.b.brush.clone() },
color: colour(s.a.color, s.b.color, t),
size: lerp32(s.a.size, s.b.size, t).max(0.05),
opacity: lerp32(s.a.opacity, s.b.opacity, t).clamp(0.0, 1.0),
flow: lerp32(s.a.flow, s.b.flow, t).max(1e-3),
seed: s.a.seed,
author: Author::Agent,
taper: [
lerp32(s.a.taper[0], s.b.taper[0], t),
lerp32(s.a.taper[1], s.b.taper[1], t),
],
lock: s.a.lock,
cuts,
second: match (s.a.second, s.b.second) {
(Some(a), Some(b)) => Some(colour(a, b, t)),
(a, b) => a.or(b),
},
on: s.a.on.clone(),
samples,
}
}
fn polygon_at(f: &ShapePlan, a: Sim, t: f32) -> Fill {
let points: Vec<[f32; 2]> =
f.pa.iter()
.zip(&f.rest)
.take(f.pa.len().saturating_sub(1).max(3))
.map(|(p, r)| {
let (x, y) = a.apply(*p);
[(x + r.0 * t as f64) as f32, (y + r.1 * t as f64) as f32]
})
.collect();
let mut cuts = f.a.cuts.clone();
let a32 = affine32(a.affine());
cuts.iter_mut().for_each(|c| {
c.map(|p| {
let (x, y) = crate::markedit::apply_affine(a32, (p[0], p[1]));
[x, y]
})
});
Fill {
id: f.a.id,
color: colour(f.a.color, f.b.color, t),
opacity: lerp32(f.a.opacity, f.b.opacity, t).clamp(0.0, 1.0),
author: Author::Agent,
source: FillSource::Polygon(points),
coverage: Coverage::default(),
lock: f.a.lock,
cuts,
}
}
fn flood_at(a: &Fill, b: &Fill, t: f32) -> Fill {
let source = match (&a.source, &b.source) {
(FillSource::Seed { seed: sa, reference }, FillSource::Seed { seed: sb, .. }) => FillSource::Seed {
seed: crate::fill::Seed {
x: lerp32(sa.x, sb.x, t),
y: lerp32(sa.y, sb.y, t),
..*sa
},
reference: reference.clone(),
},
(source, _) => source.clone(),
};
let shift = match (&a.source, &source) {
(FillSource::Seed { seed: from, .. }, FillSource::Seed { seed: to, .. }) => [to.x - from.x, to.y - from.y],
_ => [0.0, 0.0],
};
Fill {
id: a.id,
color: colour(a.color, b.color, t),
opacity: lerp32(a.opacity, b.opacity, t).clamp(0.0, 1.0),
author: Author::Agent,
source,
coverage: Coverage::default(),
lock: a.lock,
cuts: cuts_between(&a.cuts, &b.cuts, t, shift),
}
}
fn cuts_between(a: &[Cut], b: &[Cut], t: f32, shift: [f32; 2]) -> Vec<Cut> {
let matched = a.len() == b.len()
&& a.iter()
.zip(b)
.all(|(p, q)| p.keep == q.keep && p.polygon.len() == q.polygon.len());
match matched {
true => a
.iter()
.zip(b)
.map(|(p, q)| Cut {
keep: p.keep,
polygon: p
.polygon
.iter()
.zip(&q.polygon)
.map(|(u, v)| [lerp32(u[0], v[0], t), lerp32(u[1], v[1], t)])
.collect(),
})
.collect(),
false => a
.iter()
.cloned()
.map(|mut c| {
c.map(|p| [p[0] + shift[0], p[1] + shift[1]]);
c
})
.collect(),
}
}
pub fn made_hash(marks: &[Mark]) -> String {
let hash = marks.iter().fold(crate::rng::FNV_OFFSET, |h, m| {
crate::rng::fnv(h, &fingerprint(m).to_le_bytes())
});
format!("{hash:016x}")
}
#[cfg(test)]
mod tests {
use super::*;
use crate::color::Rgba;
use crate::fill::{FillRef, Seed};
fn stroke(id: u32, points: &[(f32, f32)], size: f32) -> Mark {
let pts: Vec<(f32, f32, f32)> = points.iter().map(|&(x, y)| (x, y, 1.0)).collect();
Stroke::new(id, "ink", [0.0, 0.0, 0.0, 1.0], size, 7)
.with_points(&pts, 8.0)
.into()
}
fn arm(angle: f32) -> Vec<(f32, f32)> {
let (s, c) = (libm::sinf(angle.to_radians()), libm::cosf(angle.to_radians()));
(0..=20)
.map(|i| {
let r = i as f32 * 10.0;
(100.0 + r * c, 100.0 + r * s)
})
.collect()
}
fn ends(mark: &Mark) -> ((f32, f32), (f32, f32)) {
let s = mark.as_stroke().unwrap();
(s.samples[0].pos(), s.samples[s.samples.len() - 1].pos())
}
fn length(mark: &Mark) -> f32 {
let s = mark.as_stroke().unwrap();
s.samples
.windows(2)
.map(|w| {
let (a, b) = (w[0].pos(), w[1].pos());
libm::sqrtf((a.0 - b.0).powi(2) + (a.1 - b.1).powi(2))
})
.sum()
}
#[test]
fn spacing_bunches_in_betweens_where_asked() {
assert_eq!(Spacing::Even.ts(3), [0.25, 0.5, 0.75]);
assert_eq!(Spacing::In.ts(1), [0.25]);
assert_eq!(Spacing::Out.ts(1), [0.75]);
assert_eq!(Spacing::InOut.ts(1), [0.5]);
let list = Spacing::parse("0.1,0.4").unwrap();
assert_eq!((list.count(), list.ts(2)), (Some(2), vec![0.1, 0.4]));
assert!(Spacing::parse("0.5,0.2").is_err() && Spacing::parse("0,1").is_err());
}
#[test]
fn a_swinging_arm_turns_about_its_shoulder_and_keeps_its_length() {
let a = [stroke(1, &arm(0.0), 6.0)];
let b = [stroke(1, &arm(90.0), 6.0)];
let plan = plan(&a, &b, Match::Id, &[]);
let mid = plan.at(0.5);
let (start, end) = ends(&mid[0]);
assert!(
(start.0 - 100.0).abs() < 0.2 && (start.1 - 100.0).abs() < 0.2,
"{start:?}"
);
let diagonal = 200.0 / std::f32::consts::SQRT_2;
assert!(
(end.0 - 100.0 - diagonal).abs() < 0.5 && (end.1 - 100.0 - diagonal).abs() < 0.5,
"{end:?}"
);
assert!((length(&mid[0]) - 200.0).abs() < 1.0, "{}", length(&mid[0]));
let straight = {
let (p, q) = (ends(&a[0]).1, ends(&b[0]).1);
((p.0 + q.0) / 2.0, (p.1 + q.1) / 2.0)
};
assert!(libm::sqrtf((end.0 - straight.0).powi(2) + (end.1 - straight.1).powi(2)) > 40.0);
assert_eq!(mid[0].as_stroke().unwrap().author, Author::Agent);
}
#[test]
fn a_dense_field_of_touching_strokes_turns_with_its_shape() {
let mut rng = crate::rng::Rng::new(7);
let shape = Sim {
m: (0.0, 1.5),
c: (770.0, -180.0),
};
let (mut a, mut b, mut centres) = (Vec::new(), Vec::new(), Vec::new());
(1..=400u32).for_each(|id| {
let c = (rng.range(200.0, 440.0) as f64, rng.range(200.0, 320.0) as f64);
let (length, heading, bend) = (
rng.range(6.0, 40.0) as f64,
rng.range(0.0, std::f32::consts::PI) as f64,
rng.range(-0.6, 0.6) as f64,
);
let n = 3 + rng.below(8);
let size = rng.range(4.0, 14.0);
let turn = rng.range(-20.0, 20.0).to_radians() as f64;
let scale = rng.range(0.8, 1.25) as f64;
let twist = Sim {
m: (scale * turn.cos(), scale * turn.sin()),
c: (0.0, 0.0),
};
let line: Vec<(f64, f64)> = (0..n)
.map(|k| {
let u = k as f64 / (n - 1) as f64 - 0.5;
let along = heading + bend * u;
(c.0 + length * u * along.cos(), c.1 + length * u * along.sin())
})
.collect();
let moved: Vec<(f64, f64)> = line
.iter()
.map(|p| {
let q = twist.apply((p.0 - c.0, p.1 - c.1));
shape.apply((c.0 + q.0, c.1 + q.1))
})
.collect();
let f32s = |v: &[(f64, f64)]| v.iter().map(|p| (p.0 as f32, p.1 as f32)).collect::<Vec<_>>();
a.push(stroke(id, &f32s(&line), size));
b.push(stroke(id, &f32s(&moved), size));
centres.push(c);
});
let plan = plan(&a, &b, Match::Id, &[]);
assert!(plan.touching_ends() > 300, "{}", plan.touching_ends());
[0.25, 0.5, 0.75].into_iter().for_each(|t| {
let made = plan.at(t as f32);
let mut off: Vec<f64> = made
.iter()
.zip(¢res)
.map(|(m, c)| {
let pts = m.as_stroke().unwrap().samples.iter().map(|q| q.pos()).collect::<Vec<_>>();
let n = pts.len() as f64;
let mean = pts.iter().fold((0.0, 0.0), |s, p| (s.0 + p.0 as f64 / n, s.1 + p.1 as f64 / n));
dist(mean, shape.arc(t).apply(*c))
})
.collect();
off.sort_by(f64::total_cmp);
let (median, worst) = (off[off.len() / 2], off[off.len() - 1]);
assert!(
median < 1.5 && worst < 6.0,
"t {t}: the strokes stay with the shape (median {median}, worst {worst} px off; touching ends are snapped)"
);
plan.items.iter().zip(¢res).for_each(|(item, c)| {
if let Item::Stroke(sp) = item
&& let Some(carrier) = sp.carrier
{
let moved = carrier.arc(t).then(&sp.rel.arc(t)).apply(*c);
assert!(dist(moved, shape.arc(t).apply(*c)) < 0.5, "t {t}: a carried stroke moves with its neighbours");
}
});
});
}
#[test]
fn marks_in_differently_named_parts_never_pair() {
let line = |id: u32, y: f32, dx: f32| stroke(id, &[(10.0 + dx, y), (90.0 + dx, y)], 4.0);
let a = vec![line(1, 10.0, 0.0), line(2, 30.0, 0.0), line(3, 50.0, 0.0)];
let b = vec![line(1, 10.0, 5.0), line(2, 30.0, 5.0), line(3, 50.0, 5.0)];
let parts = Parts {
a: BTreeMap::from([
("paint over".to_string(), vec![1]),
("paint over added at 4".to_string(), vec![2]),
]),
b: BTreeMap::from([
("paint over".to_string(), vec![1]),
("paint over added at 8".to_string(), vec![2]),
]),
};
[Match::Id, Match::Order, Match::Near].into_iter().for_each(|how| {
let p = pair_parts(&a, &b, how, &[], &parts);
let pairs: Vec<(u32, u32)> = p.pairs.iter().map(|q| (q.a, q.b)).collect();
assert_eq!(pairs, [(1, 1), (3, 3)], "{how:?}");
assert_eq!((p.alone_a, p.alone_b), (vec![2], vec![2]), "{how:?}");
});
let forced = pair_parts(&a, &b, Match::Id, &[[2, 2]], &parts);
assert!(
forced.pairs.iter().any(|q| (q.a, q.b) == (2, 2)),
"a forced pair still pairs"
);
}
#[test]
fn a_hand_bending_at_the_wrist_rides_on_the_turning_forearm() {
let forearm = |angle: f32| {
let (s, c) = (libm::sinf(angle.to_radians()), libm::cosf(angle.to_radians()));
(0..=20)
.map(|i| (100.0 + i as f32 * 10.0 * c, 100.0 + i as f32 * 10.0 * s))
.collect::<Vec<_>>()
};
let hand = |wrist: (f32, f32), angle: f32| {
let (s, c) = (libm::sinf(angle.to_radians()), libm::cosf(angle.to_radians()));
(0..=6)
.map(|i| (wrist.0 + i as f32 * 10.0 * c, wrist.1 + i as f32 * 10.0 * s))
.collect::<Vec<_>>()
};
let a = [
stroke(1, &forearm(0.0), 6.0),
stroke(2, &hand((300.0, 100.0), 0.0), 4.0),
];
let b = [
stroke(1, &forearm(90.0), 6.0),
stroke(2, &hand((100.0, 300.0), 130.0), 4.0),
];
let plan = plan(&a, &b, Match::Id, &[]);
let mid = plan.at(0.5);
let wrist = ends(&mid[0]).1;
let (start, end) = ends(&mid[1]);
let d = |p: (f32, f32), q: (f32, f32)| libm::sqrtf((p.0 - q.0).powi(2) + (p.1 - q.1).powi(2));
assert!(d(start, wrist) < 1.0, "{start:?} {wrist:?}");
let want = (
wrist.0 + 60.0 * libm::cosf(65f32.to_radians()),
wrist.1 + 60.0 * libm::sinf(65f32.to_radians()),
);
assert!(d(end, want) < 1.5, "{end:?} {want:?}");
assert!((length(&mid[1]) - 60.0).abs() < 1.0);
}
#[test]
fn pairs_by_id_by_order_and_by_nearest_shape() {
let a = vec![
stroke(1, &[(0.0, 0.0), (10.0, 0.0)], 4.0),
stroke(2, &[(0.0, 50.0), (10.0, 50.0)], 4.0),
];
let b = vec![
stroke(5, &[(10.0, 51.0), (0.0, 51.0)], 4.0),
stroke(1, &[(1.0, 1.0), (11.0, 1.0)], 4.0),
];
let by_id = pair(&a, &b, Match::Id, &[]);
assert_eq!(by_id.pairs.len(), 1);
assert_eq!((by_id.alone_a.clone(), by_id.alone_b.clone()), (vec![2], vec![5]));
let by_order = pair(&a, &b, Match::Order, &[]);
assert_eq!(
by_order.pairs.iter().map(|p| (p.a, p.b)).collect::<Vec<_>>(),
[(1, 5), (2, 1)]
);
let near = pair(&a, &b, Match::Near, &[]);
assert_eq!(
near.pairs.iter().map(|p| (p.a, p.b, p.reversed)).collect::<Vec<_>>(),
[(1, 1, false), (2, 5, true)]
);
let forced = pair(&a, &b, Match::Id, &[[2, 1]]);
assert_eq!(forced.pairs.iter().map(|p| (p.a, p.b)).collect::<Vec<_>>(), [(2, 1)]);
assert_eq!(forced.alone_a, [1]);
}
#[test]
fn an_in_between_keeps_what_its_eraser_is_attached_to() {
let eraser = |x: f32| {
let mut e = stroke(2, &[(x, -10.0), (x, 10.0)], 8.0);
if let Mark::Stroke(s) = &mut e {
s.brush = "eraser".into();
s.on = vec![1];
}
e
};
let a = vec![stroke(1, &[(0.0, 0.0), (100.0, 0.0)], 4.0), eraser(50.0)];
let b = vec![stroke(1, &[(0.0, 40.0), (100.0, 40.0)], 4.0), eraser(60.0)];
let between = plan(&a, &b, Match::Id, &[]).at(0.5);
let on: Vec<Vec<u32>> = between
.iter()
.filter_map(Mark::as_stroke)
.map(|s| s.on.clone())
.collect();
assert_eq!(on, vec![vec![], vec![1]]);
}
#[test]
fn line_ends_that_touch_in_both_keys_touch_in_between() {
let bar = |dy: f32| stroke(1, &[(0.0, 100.0 + dy), (200.0, 100.0 + dy)], 6.0);
let post_a = stroke(2, &[(60.0, 0.0), (60.0, 98.0)], 4.0);
let post_b = stroke(2, &[(140.0, 20.0), (140.0, 158.0)], 4.0);
let a = [bar(0.0), post_a];
let b = [bar(60.0), post_b];
let plan = plan(&a, &b, Match::Id, &[]);
assert_eq!(plan.touching_ends(), 1);
let mid = plan.at(0.5);
let (_, end) = ends(&mid[1]);
let bar_y = mid[0].as_stroke().unwrap().samples[0].pos().1;
assert!((end.1 - (bar_y - 2.0)).abs() < 1.0, "{end:?} against {bar_y}");
let open = [bar(0.0), stroke(2, &[(60.0, 0.0), (60.0, 60.0)], 4.0)];
assert_eq!(super::plan(&open, &b, Match::Id, &[]).touching_ends(), 0);
}
fn lasso(id: u32, points: &[(f64, f64)]) -> Mark {
Mark::Fill(Fill::new(
id,
[1.0, 0.0, 0.0, 1.0],
FillSource::Polygon(points.iter().map(|p| [p.0 as f32, p.1 as f32]).collect()),
Coverage::default(),
))
}
fn corners(m: &Mark) -> Vec<(f64, f64)> {
match m {
Mark::Fill(Fill {
source: FillSource::Polygon(p),
..
}) => p.iter().map(|q| (q[0] as f64, q[1] as f64)).collect(),
_ => Vec::new(),
}
}
fn capsule(from: (f64, f64), length: f64, degrees: f64, r: f64) -> Vec<(f64, f64)> {
let a = degrees.to_radians();
let (d, n) = ((a.cos(), a.sin()), (-a.sin(), a.cos()));
let at = |k: f64, side: f64| {
(
from.0 + d.0 * length * k + n.0 * r * side,
from.1 + d.1 * length * k + n.1 * r * side,
)
};
let tip = (from.0 + d.0 * length, from.1 + d.1 * length);
let cap = |c: (f64, f64), start: f64| {
(1..8).map(move |j| {
let u = start - std::f64::consts::PI * j as f64 / 8.0;
(c.0 + r * u.cos(), c.1 + r * u.sin())
})
};
(0..=8)
.map(|k| at(k as f64 / 8.0, 1.0))
.chain(cap(tip, a + std::f64::consts::FRAC_PI_2))
.chain((0..=8).map(|k| at((8 - k) as f64 / 8.0, -1.0)))
.chain(cap(from, a - std::f64::consts::FRAC_PI_2))
.collect()
}
#[test]
fn a_foot_drawn_from_a_fixed_direction_stays_on_a_shin_that_unfolds_and_swings() {
let knee = (300.0, 200.0);
let foot = |tip: (f64, f64), axis: f64| -> Vec<(f64, f64)> {
(0..24)
.map(|i| {
let phi = (15.0 * i as f64).to_radians();
let local = phi - axis.to_radians();
let (x, y) = (26.0 * local.cos(), 13.0 * local.sin());
let (c, s) = (axis.to_radians().cos(), axis.to_radians().sin());
(tip.0 + c * x - s * y, tip.1 + s * x + c * y)
})
.collect()
};
let tip = |length: f64, degrees: f64| {
let a = degrees.to_radians();
(knee.0 + length * a.cos(), knee.1 + length * a.sin())
};
let a = vec![
lasso(1, &capsule(knee, 60.0, 120.0, 16.0)),
lasso(2, &foot(tip(60.0, 120.0), 210.0)),
];
let b = vec![
lasso(1, &capsule(knee, 160.0, -30.0, 16.0)),
lasso(2, &foot(tip(160.0, -30.0), 60.0)),
];
let plan = plan(&a, &b, Match::Id, &[]);
assert_eq!(plan.fill_rides(), (0, 1), "the foot is joined to the shin");
[0.25, 0.5, 0.75].into_iter().for_each(|t| {
let made = plan.at(t);
let (shin, foot) = (corners(&made[0]), corners(&made[1]));
let end = shin
.iter()
.copied()
.max_by(|p, q| dist(*p, knee).total_cmp(&dist(*q, knee)))
.unwrap();
let n = foot.len() as f64;
let middle = foot.iter().fold((0.0, 0.0), |c, p| (c.0 + p.0 / n, c.1 + p.1 / n));
let on = foot
.iter()
.filter(|p| inside(**p, &shin) || edge(**p, &shin) <= 2.0)
.count() as f64
/ n;
assert!(
dist(middle, end) < 30.0,
"t {t}: the foot stays at the shin's end, {} px off",
dist(middle, end)
);
assert!(on >= 0.4, "t {t}: the foot overlaps the shin ({on})");
});
}
#[test]
fn a_round_band_whose_outline_starts_elsewhere_turns_with_the_shape_it_sits_in() {
let turn = |p: (f64, f64)| {
let (a, o) = (20f64.to_radians(), (150.0, 220.0));
let (dx, dy) = (p.0 - o.0, p.1 - o.1);
(
o.0 + dx * a.cos() - dy * a.sin() + 40.0,
o.1 + dx * a.sin() + dy * a.cos() + 10.0,
)
};
let body = capsule((200.0, 200.0), 120.0, 0.0, 30.0);
let band: Vec<(f64, f64)> = (0..18)
.map(|i| {
let phi = (20.0 * i as f64).to_radians();
let r = 9.0 + 2.0 * phi.cos();
(260.0 + 1.2 * r * phi.cos(), 195.0 + r * phi.sin())
})
.collect();
let moved: Vec<(f64, f64)> = band.iter().map(|p| turn(*p)).collect();
let started: Vec<(f64, f64)> = moved[6..].iter().chain(&moved[..6]).copied().collect();
let a = vec![lasso(1, &body), lasso(2, &band)];
let b = vec![
lasso(1, &body.iter().map(|p| turn(*p)).collect::<Vec<_>>()),
lasso(2, &started),
];
let plan = plan(&a, &b, Match::Id, &[]);
[0.25, 0.5, 0.75].into_iter().for_each(|t| {
let made = plan.at(t);
let (shape, ring) = (corners(&made[0]), corners(&made[1]));
let n = ring.len() as f64;
let middle = ring.iter().fold((0.0, 0.0), |c, p| (c.0 + p.0 / n, c.1 + p.1 / n));
let tip = ring
.iter()
.copied()
.max_by(|p, q| dist(*p, middle).total_cmp(&dist(*q, middle)))
.unwrap();
let pointing = libm::atan2(tip.1 - middle.1, tip.0 - middle.0).to_degrees();
let want = 20.0 * t as f64;
assert!(
(pointing - want).abs() < 8.0,
"t {t}: the band points at {pointing}, its body has turned {want}"
);
assert!(
ring.iter().all(|p| inside(*p, &shape)),
"t {t}: the band stays inside its body"
);
});
}
#[test]
fn fills_that_touch_nothing_move_as_before() {
let square = |x: f64, id: u32| lasso(id, &[(x, 0.0), (x + 10.0, 0.0), (x + 10.0, 10.0), (x, 10.0)]);
let a = vec![square(0.0, 1), square(50.0, 2)];
let b = vec![square(40.0, 1), square(90.0, 2)];
let plan = plan(&a, &b, Match::Id, &[]);
assert_eq!(plan.fill_rides(), (0, 0));
let mid = plan.at(0.5);
assert_eq!(corners(&mid[0])[0], (20.0, 0.0));
assert_eq!(corners(&mid[1])[0], (70.0, 0.0));
}
#[test]
fn polygon_fills_interpolate_and_floods_carry_their_settings() {
let square = |x: f32| {
Mark::Fill(Fill::new(
3,
[1.0, 0.0, 0.0, 1.0],
FillSource::Polygon(vec![[x, 0.0], [x + 10.0, 0.0], [x + 10.0, 10.0], [x, 10.0]]),
Coverage::default(),
))
};
let flood = |x: f32| {
Mark::Fill(Fill::new(
4,
[0.0, 0.0, 1.0, 1.0],
FillSource::Seed {
seed: Seed {
x,
y: 5.0,
tolerance: 0.2,
gap: 3.0,
expand: 2.0,
},
reference: FillRef::Layer("l1".into()),
},
Coverage::default(),
))
};
let plan = plan(&[square(0.0), flood(0.0)], &[square(40.0), flood(40.0)], Match::Id, &[]);
let mid = plan.at(0.5);
let FillSource::Polygon(points) = &mid[0].as_fill().unwrap().source else {
panic!()
};
assert_eq!(points.len(), 4);
assert!((points[0][0] - 20.0).abs() < 0.01, "{points:?}");
let FillSource::Seed { seed, reference } = &mid[1].as_fill().unwrap().source else {
panic!()
};
assert_eq!((seed.x, seed.gap, reference.name()), (20.0, 3.0, "l1"));
assert_eq!(plan.floods().len(), 1);
}
#[test]
fn colours_blend_between_keys_through_oklab() {
let coloured = |c: Rgba| -> Mark {
let pts: Vec<(f32, f32, f32)> = arm(0.0).iter().map(|&(x, y)| (x, y, 1.0)).collect();
Stroke::new(1, "ink", c, 6.0, 7).with_points(&pts, 8.0).into()
};
let lit = [0.93, 0.62, 0.25, 1.0];
let shade = [0.36, 0.38, 0.72, 1.0];
let fill = |c: Rgba| {
Mark::Fill(Fill::new(
3,
c,
FillSource::Polygon(vec![[0.0, 0.0], [10.0, 0.0], [10.0, 10.0]]),
Coverage::default(),
))
};
let made = plan(
&[coloured(lit), fill(lit)],
&[coloured(shade), fill(shade)],
Match::Id,
&[],
);
let mid = made.at(0.5);
let (la, lb) = (to_oklab(lit), to_oklab(shade));
let want: [f32; 3] = std::array::from_fn(|i| (la[i] + lb[i]) / 2.0);
[mid[0].as_stroke().unwrap().color, mid[1].as_fill().unwrap().color]
.iter()
.for_each(|&c| {
let got = to_oklab(from_u16(c));
assert!((0..3).all(|i| (got[i] - want[i]).abs() < 0.004), "{got:?} {want:?}");
});
let same = plan(&[coloured(lit)], &[coloured(lit)], Match::Id, &[]);
assert_eq!(
same.at(0.5)[0].as_stroke().unwrap().color,
to_u16(lit),
"keys of one colour keep it exactly"
);
}
#[test]
fn anchors_carry_a_point_with_the_line_it_sits_by() {
let line = vec![(0.0, 0.0), (100.0, 0.0)];
let at = anchor(std::slice::from_ref(&line), (25.0, 10.0)).unwrap();
let turned = vec![(0.0, 0.0), (0.0, 100.0)];
let (x, y) = place(&at, &[turned]).unwrap();
assert!((x + 10.0).abs() < 1e-3 && (y - 25.0).abs() < 1e-3, "{x},{y}");
}
fn band(x0: f32, y0: f32, keep: crate::cut::Keep) -> Cut {
Cut {
keep,
polygon: vec![[x0, y0], [x0 + 40.0, y0], [x0 + 40.0, y0 + 20.0], [x0, y0 + 20.0]],
}
}
#[test]
fn in_betweens_of_flood_fills_move_their_cuts_with_them() {
let flood = |x: f32, cuts: Vec<Cut>| {
let mut f = Fill::new(
4,
[0.0, 0.0, 1.0, 1.0],
FillSource::Seed {
seed: Seed {
x: x + 50.0,
y: 50.0,
tolerance: 0.2,
gap: 3.0,
expand: 2.0,
},
reference: FillRef::Layer("l1".into()),
},
Coverage::default(),
);
f.cuts = cuts;
Mark::Fill(f)
};
let outside = |x: f32| vec![band(x, 40.0, crate::cut::Keep::Outside)];
let left_x = |m: &Mark| m.cuts()[0].polygon[0][0];
let matched = plan(
&[flood(0.0, outside(0.0))],
&[flood(60.0, outside(60.0))],
Match::Id,
&[],
);
assert_eq!(left_x(&matched.at(0.5)[0]), 30.0, "cuts of both keys are blended");
let only_a = plan(&[flood(0.0, outside(0.0))], &[flood(60.0, Vec::new())], Match::Id, &[]);
assert_eq!(
left_x(&only_a.at(0.25)[0]),
15.0,
"a cut of one key moves with the seed"
);
}
#[test]
fn a_carried_mark_takes_its_cuts_along_its_line() {
use crate::cut::Keep;
let mut shape = Fill::new(
4,
[0.0, 0.0, 1.0, 1.0],
FillSource::Polygon(vec![[10.0, 5.0], [30.0, 5.0], [30.0, 15.0], [10.0, 15.0]]),
Coverage::default(),
);
shape.cuts = vec![band(15.0, 0.0, Keep::Outside)];
let pts: Vec<(f32, f32, f32)> = (0..=10).map(|i| (10.0 + i as f32 * 2.0, 10.0, 1.0)).collect();
let mut line = Stroke::new(5, "ink", [0.0, 0.0, 0.0, 1.0], 4.0, 1).with_points(&pts, 8.0);
line.cuts = vec![band(15.0, 0.0, Keep::Inside)];
let mut cells = Fill::cells(6, [0.0, 0.0, 0.0, 1.0], "", false, Coverage::from_cells(&[[20, 10]]));
cells.cuts = vec![band(15.0, 0.0, Keep::Inside)];
let from: Lines = vec![vec![(0.0, 0.0), (100.0, 0.0)]];
let to: Lines = vec![vec![(0.0, 50.0), (100.0, 50.0)]];
let top = |m: &Mark| m.cuts()[0].polygon[0][1];
assert_eq!(top(&carry(&Mark::Fill(shape), &from, &to, None)), 50.0);
assert_eq!(top(&carry(&Mark::Stroke(line), &from, &to, None)), 50.0);
assert_eq!(
top(&carry(&Mark::Fill(cells), &from, &to, None)),
0.0,
"pixel marks stay, and so do their cuts"
);
}
}