use std::f64::consts::PI;
use super::{Vertex, VertexSource};
use crate::Point;
use crate::numeric::{fused, sum_of_products};
use crate::path::PathCode;
const PIECE_BUDGET: f64 = 1_048_576.0;
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct SketchParams {
pub scale: f64,
pub length: f64,
pub randomness: f64,
}
impl SketchParams {
pub const DEFAULT_LENGTH: f64 = 128.0;
pub const DEFAULT_RANDOMNESS: f64 = 16.0;
pub fn new(scale: f64, length: Option<f64>, randomness: Option<f64>) -> Self {
let or_default = |v: Option<f64>, default| v.filter(|v| *v != 0.0).unwrap_or(default);
Self {
scale,
length: or_default(length, Self::DEFAULT_LENGTH),
randomness: or_default(randomness, Self::DEFAULT_RANDOMNESS),
}
}
}
#[derive(Clone, Debug)]
struct Lcg(u32);
impl Lcg {
fn next_f64(&mut self) -> f64 {
self.0 = self.0.wrapping_mul(214_013).wrapping_add(2_531_011);
f64::from(self.0) / 4_294_967_296.0
}
}
#[derive(Clone, Debug)]
struct Segmenter<I> {
source: I,
cmd: Option<PathCode>,
origin: Point,
delta: Point,
dl: f64,
ddl: f64,
start: Point,
pending_close: bool,
vertices: usize,
budget: f64,
}
impl<I: VertexSource> Segmenter<I> {
const fn new(source: I) -> Self {
Self {
source,
cmd: None,
origin: Point::ORIGIN,
delta: Point::ORIGIN,
dl: 0.0,
ddl: 0.0,
start: Point::ORIGIN,
pending_close: false,
vertices: 0,
budget: PIECE_BUDGET,
}
}
fn move_to(&mut self, p: Point) {
self.origin = p;
self.delta = Point::ORIGIN;
self.dl = 2.0;
self.ddl = 2.0;
self.cmd = Some(PathCode::MoveTo);
}
fn line_to(&mut self, p: Point) {
self.origin += self.delta;
self.delta = p - self.origin;
let len = sum_of_products(self.delta.x, self.delta.x, self.delta.y, self.delta.y).sqrt();
let len = if len < 1e-30 { 1e-30 } else { len };
let ddl = 1.0 / len;
self.ddl = if ddl.is_finite() && ddl > 0.0 && len <= self.budget {
self.budget -= len;
ddl
} else {
1.0
};
self.dl = if self.cmd == Some(PathCode::MoveTo) {
0.0
} else {
self.ddl
};
if self.cmd.is_none() {
self.cmd = Some(PathCode::LineTo);
}
}
fn generate(&mut self) -> Option<Vertex> {
let cmd = self.cmd?;
self.cmd = Some(PathCode::LineTo);
if self.dl >= 1.0 - self.ddl {
self.dl = 1.0;
self.cmd = None;
return Some(Vertex::new(cmd, self.origin + self.delta));
}
let p = Point::new(
fused(self.delta.x, self.dl, self.origin.x),
fused(self.delta.y, self.dl, self.origin.y),
);
self.dl += self.ddl;
Some(Vertex::new(cmd, p))
}
}
impl<I: VertexSource> Iterator for Segmenter<I> {
type Item = Vertex;
fn next(&mut self) -> Option<Vertex> {
loop {
if let Some(vertex) = self.generate() {
return Some(vertex);
}
if self.pending_close {
self.pending_close = false;
return Some(Vertex::new(PathCode::ClosePoly, Point::ORIGIN));
}
let vertex = self.source.next()?;
match vertex.code {
PathCode::MoveTo => {
self.move_to(vertex.point);
self.start = vertex.point;
self.vertices = 1;
}
PathCode::ClosePoly => {
self.pending_close = true;
if self.vertices > 2 {
self.line_to(self.start);
}
self.vertices = 0;
}
PathCode::LineTo | PathCode::Curve3 | PathCode::Curve4 => {
self.line_to(vertex.point);
self.vertices += 1;
}
}
}
}
}
impl<I: VertexSource> VertexSource for Segmenter<I> {
fn rewind(&mut self) {
self.source.rewind();
self.cmd = None;
self.start = Point::ORIGIN;
self.pending_close = false;
self.vertices = 0;
self.budget = PIECE_BUDGET;
}
}
#[derive(Clone, Copy, Debug)]
struct Wiggle {
scale: f64,
p_scale: f64,
log_randomness: f64,
}
#[derive(Clone, Debug)]
pub struct Sketcher<I> {
segments: Segmenter<I>,
wiggle: Option<Wiggle>,
last: Point,
has_last: bool,
phase: f64,
rng: Lcg,
}
impl<I: VertexSource> Sketcher<I> {
pub(super) fn new(source: I, params: Option<SketchParams>) -> Self {
let wiggle = params.filter(|p| p.scale != 0.0).map(|p| Wiggle {
scale: p.scale,
p_scale: (2.0 * PI) / (p.length * p.randomness),
log_randomness: 2.0 * p.randomness.ln(),
});
let mut sketcher = Self {
segments: Segmenter::new(source),
wiggle,
last: Point::ORIGIN,
has_last: false,
phase: 0.0,
rng: Lcg(0),
};
sketcher.rewind();
sketcher
}
}
impl<I: VertexSource> Iterator for Sketcher<I> {
type Item = Vertex;
fn next(&mut self) -> Option<Vertex> {
let Some(wiggle) = self.wiggle else {
return self.segments.source.next();
};
let mut vertex = self.segments.next()?;
if vertex.code == PathCode::MoveTo {
self.has_last = false;
self.phase = 0.0;
}
if self.has_last {
self.phase += (self.rng.next_f64() * wiggle.log_randomness).exp();
let den = self.last.x - vertex.point.x;
let num = self.last.y - vertex.point.y;
let len_sq = sum_of_products(num, num, den, den);
self.last = vertex.point;
if len_sq != 0.0 {
let r = (self.phase * wiggle.p_scale).sin() * wiggle.scale;
let r_over_len = r / len_sq.sqrt();
vertex.point.x = fused(r_over_len, num, vertex.point.x);
vertex.point.y = fused(-r_over_len, den, vertex.point.y);
}
} else {
self.last = vertex.point;
}
self.has_last = true;
Some(vertex)
}
}
impl<I: VertexSource> VertexSource for Sketcher<I> {
fn rewind(&mut self) {
self.has_last = false;
self.phase = 0.0;
if self.wiggle.is_some() {
self.rng = Lcg(0);
self.segments.rewind();
} else {
self.segments.source.rewind();
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::path::Path;
fn p(x: f64, y: f64) -> Point {
Point::new(x, y)
}
#[test]
fn lcg_matches_matplotlib() {
let mut rng = Lcg(0);
assert_eq!(rng.next_f64(), 2_531_011.0 / 4_294_967_296.0);
assert!((rng.next_f64() - 0.117_791_085_038_334_13).abs() < 1e-15);
}
#[test]
fn lines_are_split_into_unit_pieces() {
let path = Path::polyline(vec![p(0.0, 0.0), p(10.0, 0.0)]);
let flat = SketchParams::new(1e-300, None, None);
let out: Vec<Vertex> = path.iter_vertices().sketch(Some(flat)).collect();
assert!((10..=12).contains(&out.len()));
assert_eq!(out[0].code, PathCode::MoveTo);
assert_eq!(out.last().map(|v| v.point.x), Some(10.0));
}
#[test]
fn wiggle_is_perpendicular_and_bounded() {
let path = Path::polyline(vec![p(0.0, 0.0), p(100.0, 0.0)]);
let params = SketchParams::new(2.0, None, None);
let out: Vec<Vertex> = path.iter_vertices().sketch(Some(params)).collect();
assert!((100..=102).contains(&out.len()));
assert_eq!(out.last().map(|v| v.point.x), Some(100.0));
for (i, v) in out[..out.len() - 1].iter().enumerate() {
assert!((v.point.x - i as f64).abs() < 1e-9);
assert!(v.point.y.abs() <= 2.0);
}
assert!(out.iter().any(|v| v.point.y.abs() > 0.1));
}
#[test]
fn zero_scale_passes_through() {
let path = Path::polyline(vec![p(0.0, 0.0), p(10.0, 0.0)]);
let params = SketchParams::new(0.0, None, None);
assert_eq!(path.iter_vertices().sketch(Some(params)).count(), 2);
}
#[test]
fn non_finite_lines_terminate() {
let path = Path::polyline(vec![p(0.0, 0.0), p(f64::INFINITY, 0.0), p(f64::NAN, 1.0)]);
let params = SketchParams::new(1.0, None, None);
assert_eq!(path.iter_vertices().sketch(Some(params)).count(), 3);
}
#[test]
fn huge_lines_are_not_cut_beyond_the_budget() {
let path = Path::polyline(vec![p(0.0, 0.0), p(1e300, 0.0), p(1e300, 10.0)]);
let params = SketchParams::new(1.0, None, None);
assert_eq!(path.iter_vertices().sketch(Some(params)).count(), 12);
}
#[test]
fn long_paths_are_cut_within_the_budget() {
let zigzag = (0..100).map(|i| p(f64::from(i % 2) * 50_000.0, f64::from(i)));
let path = Path::polyline(zigzag.collect());
let params = SketchParams::new(1.0, None, None);
let pieces = path.iter_vertices().sketch(Some(params)).count();
assert!(pieces <= PIECE_BUDGET as usize + 100, "{pieces} pieces");
assert!(pieces > PIECE_BUDGET as usize / 2, "{pieces} pieces");
}
}