use crate::buffer::Cell;
use crate::canvas::Canvas;
use crate::common::{
DEFAULT_SEED, EffectRng, TerminalEffect, normalize_effect_size, seeded_rng,
};
use crate::render::glyph_ramp::{GlyphRamp, presets as glyph_presets};
use crate::render::palette::{oklab_hue, shade};
use crate::runtime::FrameContext;
use crossterm::style::{Attribute, Color};
use serde::{Deserialize, Serialize};
pub const MAX_DEGREE: usize = 5;
pub const MIN_DEGREE: usize = 3;
const START_SCALE: f64 = 1.7;
const END_SCALE: f64 = 0.22;
const DEFAULT_DRIFT_RADIUS: f32 = 0.45;
const ROOT_LIGHTNESS: f32 = 0.75;
const ROOT_CHROMA: f32 = 0.20;
const INK_FLOOR: f32 = 0.45;
const UNCONVERGED: Color = Color::Rgb {
r: 236,
g: 236,
b: 240,
};
pub const MIN_SHADE_STEPS: u16 = 2;
pub const MAX_SHADE_STEPS: u16 = 32;
#[cfg(test)]
const NO_BASIN: u8 = u8::MAX;
#[cfg(test)]
const MIN_SEPARATION: f32 = 0.15;
#[cfg(test)]
const MIN_DARK_SEPARATION: f32 = 0.09;
#[derive(Debug, Clone, Copy, PartialEq, Default)]
struct Complex {
re: f32,
im: f32,
}
impl Complex {
const ZERO: Self = Self { re: 0.0, im: 0.0 };
fn new(re: f32, im: f32) -> Self {
Self { re, im }
}
fn mul(self, other: Self) -> Self {
Self {
re: self.re * other.re - self.im * other.im,
im: self.re * other.im + self.im * other.re,
}
}
fn add(self, other: Self) -> Self {
Self::new(self.re + other.re, self.im + other.im)
}
fn sub(self, other: Self) -> Self {
Self::new(self.re - other.re, self.im - other.im)
}
fn scale(self, k: f32) -> Self {
Self::new(self.re * k, self.im * k)
}
fn div(self, other: Self) -> Self {
let den = other.len_squared();
if den < 1e-30 {
return Self::ZERO;
}
Self {
re: (self.re * other.re + self.im * other.im) / den,
im: (self.im * other.re - self.re * other.im) / den,
}
}
fn len_squared(self) -> f32 {
self.re * self.re + self.im * self.im
}
fn powe(self, mut n: usize) -> Self {
let mut acc = Complex::new(1.0, 0.0);
let mut base = self;
while n > 0 {
if n & 1 == 1 {
acc = acc.mul(base);
}
n >>= 1;
if n > 0 {
base = base.mul(base);
}
}
acc
}
fn powe_and_prev<const N: usize>(self) -> (Self, Self) {
let mut acc = Complex::new(1.0, 0.0);
let mut prev = Complex::new(1.0, 0.0);
for _ in 0..N {
prev = acc;
acc = acc.mul(self);
}
(acc, prev)
}
fn angle_turns(self) -> f32 {
if self.len_squared() < 1e-20 {
return 0.0;
}
(self.im.atan2(self.re) / std::f32::consts::TAU).rem_euclid(1.0)
}
}
fn durand_kerner(degree: usize, c: Complex) -> Vec<Complex> {
const GOLDEN_ANGLE: f32 = 0.618_034;
let mut roots: Vec<Complex> = (0..degree)
.map(|k| {
let angle =
(k as f32 * GOLDEN_ANGLE).rem_euclid(1.0) * std::f32::consts::TAU;
Complex::new(angle.cos() * 0.7, angle.sin() * 0.7)
})
.collect();
for _ in 0..200 {
let mut worst: f32 = 0.0;
for i in 0..degree {
let z = roots[i];
let p = z.powe(degree).add(c);
let mut denom = Complex::new(1.0, 0.0);
for (j, other) in roots.iter().enumerate() {
if i != j {
denom = denom.mul(z.sub(*other));
}
}
if denom.len_squared() < 1e-24 {
continue;
}
let step = p.div(denom);
roots[i] = z.sub(step);
worst = worst.max(step.len_squared().sqrt());
}
if worst < 1e-12 {
break;
}
}
roots
}
#[derive(Debug, Clone, Copy, PartialEq)]
struct Converged {
root: usize,
iterations: u32,
ok: bool,
at: Complex,
}
fn newton_iter(
start: Complex,
degree: usize,
c: Complex,
roots: &[Complex],
max_iter: u32,
tolerance: f32,
) -> Converged {
match degree {
3 => newton_iter_n::<3>(start, c, roots, max_iter, tolerance),
4 => newton_iter_n::<4>(start, c, roots, max_iter, tolerance),
5 => newton_iter_n::<5>(start, c, roots, max_iter, tolerance),
_ => newton_iter_generic(start, degree, c, roots, max_iter, tolerance),
}
}
fn newton_iter_generic(
start: Complex,
degree: usize,
c: Complex,
roots: &[Complex],
max_iter: u32,
tolerance: f32,
) -> Converged {
let tolerance_sq = tolerance * tolerance;
let mut z = start;
for i in 0..max_iter {
let mut best = f32::INFINITY;
let mut nearest = 0usize;
for (k, root) in roots.iter().enumerate() {
let d = z.sub(*root).len_squared();
if d < best {
best = d;
nearest = k;
}
}
if best < tolerance_sq {
return Converged {
root: nearest,
iterations: i,
ok: true,
at: z,
};
}
let p = z.powe(degree).add(c);
let dp = z.powe(degree - 1).scale(degree as f32);
z = z.sub(p.div(dp));
}
Converged {
root: 0,
iterations: max_iter,
ok: false,
at: z,
}
}
fn newton_iter_n<const N: usize>(
start: Complex,
c: Complex,
roots: &[Complex],
max_iter: u32,
tolerance: f32,
) -> Converged {
debug_assert!(
roots.len() >= N,
"degree {N} needs {N} roots but only {} were solved",
roots.len()
);
let tolerance_sq = tolerance * tolerance;
let mut z = start;
for i in 0..max_iter {
let mut best = f32::INFINITY;
let mut nearest = 0usize;
for (k, root) in roots.iter().enumerate().take(N) {
let d = z.sub(*root).len_squared();
if d < best {
best = d;
nearest = k;
}
}
if best < tolerance_sq {
return Converged {
root: nearest,
iterations: i,
ok: true,
at: z,
};
}
let (zn, zn1) = z.powe_and_prev::<N>();
let p = zn.add(c);
let dp = zn1.scale(N as f32);
z = z.sub(p.div(dp));
}
Converged {
root: 0,
iterations: max_iter,
ok: false,
at: z,
}
}
fn drift_constant(angle: f32, radius: f32) -> Complex {
let radius = if radius.is_finite() {
radius.max(0.0)
} else {
DEFAULT_DRIFT_RADIUS
};
Complex::new(angle.cos() * radius, angle.sin() * radius)
}
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(default)]
pub struct NewtonOptions {
pub degree: u8,
pub drift_radius: f32,
pub drift_speed: f32,
pub max_iterations: u16,
pub tolerance: f32,
pub shade_steps: u16,
pub depth: f32,
pub zoom_speed: f32,
pub spin_speed: f32,
pub ramp: String,
pub seed: u64,
}
const DEFAULT_DEPTH_RATIO: f32 = (END_SCALE / START_SCALE) as f32;
impl Default for NewtonOptions {
fn default() -> Self {
Self {
degree: 3,
drift_radius: DEFAULT_DRIFT_RADIUS,
drift_speed: 0.06,
max_iterations: 32,
tolerance: 1e-3,
shade_steps: 8,
depth: DEFAULT_DEPTH_RATIO,
zoom_speed: 0.05,
spin_speed: 0.04,
ramp: String::from("inked"),
seed: DEFAULT_SEED,
}
}
}
struct Camera {
half_width: f64,
half_height: f64,
rotation: f64,
}
pub struct Newton {
screen_size: (u16, u16),
options: NewtonOptions,
canvas: Canvas,
c: Complex,
roots: Vec<Complex>,
root_colors: Vec<Color>,
shaded: Vec<Vec<Color>>,
glyphs: Vec<char>,
hue_shift: f32,
time: f32,
ramp: GlyphRamp,
unconverged: char,
scratch: Vec<Cell>,
_rng: EffectRng,
}
impl TerminalEffect for Newton {
fn get_diff(&mut self) -> Vec<(usize, usize, Cell)> {
self.draw();
self.canvas.commit()
}
fn update(&mut self) {
self.advance(1.0 / 60.0);
}
fn update_with_context(&mut self, context: &FrameContext) {
self.advance(context.delta.as_secs_f32());
}
fn update_size(&mut self, width: u16, height: u16) {
self.screen_size = normalize_effect_size((width, height));
self.canvas.resize(self.screen_size.0, self.screen_size.1);
self.scratch.resize(self.cell_count(), Cell::default());
}
fn reset(&mut self) {
let options = self.options.clone();
let size = self.screen_size;
*self = Self::new(options, size);
}
}
impl Newton {
pub fn new(options: NewtonOptions, screen_size: (u16, u16)) -> Self {
let screen_size = normalize_effect_size(screen_size);
let degree = (options.degree as usize).clamp(MIN_DEGREE, MAX_DEGREE);
let ramp = GlyphRamp::from_text(
glyph_presets::by_name(&options.ramp).unwrap_or(glyph_presets::INKED),
);
let unconverged = ramp.at(ramp.len().saturating_sub(1));
let phase = std::f32::consts::PI + seeded_phase(options.seed);
let mut effect = Self {
screen_size,
canvas: Canvas::new(screen_size.0, screen_size.1),
options: NewtonOptions {
degree: degree as u8,
..options
},
c: drift_constant(phase, DEFAULT_DRIFT_RADIUS),
roots: Vec::new(),
root_colors: Vec::new(),
shaded: Vec::new(),
glyphs: Vec::new(),
hue_shift: 0.0,
time: 0.0,
ramp,
unconverged,
scratch: Vec::new(),
_rng: seeded_rng(options.seed, "newton"),
};
effect.scratch.resize(effect.cell_count(), Cell::default());
effect.solve_roots();
effect.advance(0.0);
effect
}
fn cell_count(&self) -> usize {
self.screen_size.0 as usize * self.screen_size.1 as usize
}
fn degree(&self) -> usize {
self.options.degree as usize
}
fn iteration_budget(&self) -> u32 {
u32::from(self.options.max_iterations).max(1)
}
fn tolerance(&self) -> f32 {
if self.options.tolerance.is_finite() {
self.options.tolerance.clamp(0.0, 0.5)
} else {
1e-3
}
}
fn shade_steps(&self) -> usize {
self.options
.shade_steps
.clamp(MIN_SHADE_STEPS, MAX_SHADE_STEPS) as usize
}
fn drift_angle(&self) -> f32 {
std::f32::consts::PI
+ seeded_phase(self.options.seed)
+ self.time * self.options.drift_speed
}
fn solve_roots(&mut self) {
self.roots = durand_kerner(self.degree(), self.c);
self.rebuild_colours();
}
fn rebuild_colours(&mut self) {
let steps = self.shade_steps();
self.root_colors = self
.roots
.iter()
.map(|root| {
oklab_hue(
ROOT_LIGHTNESS,
ROOT_CHROMA,
root.angle_turns() + self.hue_shift,
)
})
.collect();
self.glyphs = (0..steps)
.map(|i| {
let t = i as f32 / (steps - 1).max(1) as f32;
self.ramp.sample(t)
})
.collect();
self.shaded = self
.root_colors
.iter()
.map(|base| {
(0..steps)
.map(|i| {
let t = i as f32 / (steps - 1).max(1) as f32;
shade(*base, INK_FLOOR + (1.0 - INK_FLOOR) * t)
})
.collect()
})
.collect();
}
fn camera(&self) -> Camera {
let depth = if self.options.depth.is_finite() {
self.options.depth.clamp(0.01, 1.0)
} else {
DEFAULT_DEPTH_RATIO
};
let period = if self.options.zoom_speed > 0.0 {
1.0f64 / self.options.zoom_speed as f64
} else {
f64::INFINITY
};
let phase =
0.5 + 0.5 * (std::f64::consts::TAU * self.time as f64 / period).sin();
let log_wide = START_SCALE.ln();
let log_narrow = (START_SCALE as f32 * depth).ln() as f64;
let scale = (log_wide + phase * (log_narrow - log_wide)).exp();
Camera {
half_width: scale * self.aspect() as f64,
half_height: scale,
rotation: (self.options.spin_speed * self.time * std::f32::consts::TAU)
as f64,
}
}
fn aspect(&self) -> f32 {
self.screen_size.0 as f32 / self.screen_size.1 as f32
}
fn advance(&mut self, dt: f32) {
self.time += if dt.is_finite() { dt } else { 0.0 };
let radius = if self.options.drift_radius.is_finite() {
self.options.drift_radius.max(0.0)
} else {
DEFAULT_DRIFT_RADIUS
};
let c = drift_constant(self.drift_angle(), radius);
if c != self.c {
self.c = c;
self.solve_roots();
}
}
fn draw(&mut self) {
let degree = self.degree();
let max_iter = self.iteration_budget();
let tolerance = self.tolerance();
let steps = self.shade_steps();
let shade_max = (steps - 1) as f32;
let inv_sqrt_max = 1.0 / (max_iter as f32).sqrt();
let camera = self.camera();
let (cw, ch) = (self.screen_size.0 as usize, self.screen_size.1 as usize);
let (cos_r, sin_r) =
(camera.rotation.cos() as f32, camera.rotation.sin() as f32);
let (hw, hh) = (camera.half_width as f32, camera.half_height as f32);
let (c, roots) = (self.c, &self.roots);
self.canvas.clear();
for y in 0..ch {
let ny = ((y as f32 + 0.5) / ch as f32) * 2.0 - 1.0;
for x in 0..cw {
let nx = ((x as f32 + 0.5) / cw as f32) * 2.0 - 1.0;
let (rx, ry) = (nx * cos_r - ny * sin_r, nx * sin_r + ny * cos_r);
let start = Complex::new(rx * hw, ry * hh);
let got = newton_iter(start, degree, c, roots, max_iter, tolerance);
let (glyph, color) = if got.ok {
let norm = (got.iterations as f32).sqrt() * inv_sqrt_max;
let band =
(norm * shade_max).round().clamp(0.0, shade_max) as usize;
let color = self
.shaded
.get(got.root)
.and_then(|rungs| rungs.get(band))
.copied()
.unwrap_or(Color::Black);
(*self.glyphs.get(band).unwrap_or(&self.unconverged), color)
} else {
(self.unconverged, UNCONVERGED)
};
self.scratch[y * cw + x] =
Cell::new(glyph, color, Attribute::Reset);
self.canvas
.set(x, y, Cell::new(glyph, color, Attribute::Reset));
}
}
}
}
fn seeded_phase(seed: u64) -> f32 {
use rand::RngExt;
seeded_rng(seed, "newton").random::<f32>()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::common::MIN_EFFECT_SIZE;
use crate::render::palette::perceptual_distance;
use std::collections::HashSet;
fn settle(effect: &mut Newton) {
for _ in 0..20 {
effect.advance(1.0 / 60.0);
let _ = effect.get_diff();
}
}
#[test]
fn the_roots_satisfy_the_polynomial() {
for degree in MIN_DEGREE..=MAX_DEGREE {
for c in [
Complex::new(-1.0, 0.0),
Complex::new(-0.5, 0.0),
Complex::new(0.4, 0.0),
Complex::new(0.0, 0.3),
Complex::new(0.3, 0.3),
] {
let roots = durand_kerner(degree, c);
assert_eq!(
roots.len(),
degree,
"degree {degree} returned the wrong count"
);
for root in &roots {
let p = root.powe(degree).add(c);
assert!(
p.len_squared().sqrt() < 1e-4,
"degree {degree}, c = ({}, {}): root ({}, {}) has |p| = {}",
c.re,
c.im,
root.re,
root.im,
p.len_squared().sqrt()
);
}
for i in 0..roots.len() {
for j in (i + 1)..roots.len() {
assert!(
roots[i].sub(roots[j]).len_squared().sqrt() > 1e-3,
"degree {degree}, c = ({}, {}): roots {i} and {j} coincide",
c.re,
c.im
);
}
}
}
}
}
#[test]
fn a_converged_sample_satisfies_the_polynomial() {
let c = Complex::new(-1.0, 0.0);
let roots = durand_kerner(3, c);
for (re, im) in [
(0.9f32, 0.1f32),
(-0.4, 0.7),
(-0.4, -0.7),
(1.4, 0.0),
(0.0, 1.4),
(1.5, 1.2),
] {
let start = Complex::new(re, im);
let got = newton_iter(start, 3, c, &roots, 32, 1e-3);
assert!(got.ok, "({re}, {im}) did not converge to any root");
let root = roots[got.root];
let residual = got.at.sub(root).len_squared().sqrt();
assert!(
residual < 1e-3,
"({re}, {im}) reported root {} = ({}, {}), but it stopped at ({}, {}), \
which is {residual} away",
got.root,
root.re,
root.im,
got.at.re,
got.at.im
);
let p = got.at.powe(3).add(c);
assert!(
p.len_squared().sqrt() < 1e-2,
"({re}, {im}) stopped at ({}, {}), where |p| = {}",
got.at.re,
got.at.im,
p.len_squared().sqrt()
);
}
}
#[test]
fn rotating_the_hue_assignment_moves_colour_and_not_convergence() {
let mut effect = Newton::new(NewtonOptions::default(), (80, 24));
settle(&mut effect);
let before = cell_colors(&mut effect);
let basins_before = basin_shares(&effect);
effect.hue_shift += 0.5;
effect.rebuild_colours();
let after = cell_colors(&mut effect);
let basins_after = basin_shares(&effect);
assert_eq!(
basins_before, basins_after,
"convergence changed when only the hue assignment was rotated"
);
let moved = before
.iter()
.zip(after.iter())
.filter(|(a, b)| a != b)
.count();
assert!(
moved > before.len() / 2,
"only {moved} of {} cells changed colour when the hue assignment rotated",
before.len()
);
}
#[test]
fn the_iteration_count_uses_the_ramp_rather_than_one_value() {
let mut effect = Newton::new(NewtonOptions::default(), (200, 50));
settle(&mut effect);
let inks: HashSet<Color> = cell_colors(&mut effect).into_iter().collect();
assert!(
inks.len() >= 6,
"only {} distinct colours on a 200x50 frame; the shading channel is not alive",
inks.len()
);
}
#[test]
fn the_basins_have_a_fractal_boundary() {
for (w, h) in [(200usize, 50usize), (400, 200), (80, 24)] {
let mut effect =
Newton::new(NewtonOptions::default(), (w as u16, h as u16));
settle(&mut effect);
let basins = basin_grid(&effect, w, h);
let boundary = boundary_percent(&basins, w, h);
assert!(
(0.5..22.0).contains(&boundary),
"{w}x{h}: basin boundary fraction is {boundary:.2}%; a flat wash is \
about 0 and uniform noise about 25"
);
}
}
#[test]
fn every_basin_holds_a_measurable_share() {
for radius in [0.0f32, 0.25, 0.45, 0.5] {
let mut effect = Newton::new(
NewtonOptions {
drift_radius: radius,
..NewtonOptions::default()
},
(120, 40),
);
settle(&mut effect);
for (root, share) in basin_shares(&effect).iter().enumerate() {
assert!(
*share > 0.05,
"drift radius {radius}: root {root} holds {:.1}% of the frame",
share * 100.0
);
assert!(
*share < 0.75,
"drift radius {radius}: root {root} holds {:.1}% of the frame",
share * 100.0
);
}
}
}
#[test]
fn no_root_is_swallowed_anywhere_on_the_drift() {
let degree = 3usize;
let (w, h) = (120usize, 40usize);
let mut worst_min = 1.0f32;
let mut worst_max = 0.0f32;
for step in 0..48 {
let angle =
std::f32::consts::PI + std::f32::consts::TAU * step as f32 / 48.0;
let c = drift_constant(angle, DEFAULT_DRIFT_RADIUS);
let roots = durand_kerner(degree, c);
let mut counts = vec![0usize; degree];
for (nx, ny) in normalised_points(w, h) {
let got = newton_iter(
Complex::new(nx * 1.7 * 4.0, ny * 1.7),
degree,
c,
&roots,
32,
1e-3,
);
if got.ok {
counts[got.root] += 1;
}
}
let total = (w * h) as f32;
for count in &counts {
worst_min = worst_min.min(*count as f32 / total);
worst_max = worst_max.max(*count as f32 / total);
}
}
assert!(
worst_min > 0.10,
"a root fell to {:.1}% somewhere on the drift",
worst_min * 100.0
);
assert!(
worst_max < 0.70,
"a root reached {:.1}% somewhere on the drift",
worst_max * 100.0
);
}
#[test]
fn the_root_colours_are_perceptually_separable() {
for degree in MIN_DEGREE..=MAX_DEGREE {
let mut effect = Newton::new(
NewtonOptions {
degree: degree as u8,
..NewtonOptions::default()
},
(80, 24),
);
settle(&mut effect);
for i in 0..effect.root_colors.len() {
for j in (i + 1)..effect.root_colors.len() {
let d = perceptual_distance(
effect.root_colors[i],
effect.root_colors[j],
);
assert!(
d > MIN_SEPARATION,
"degree {degree}: roots {i} and {j} are only {d:.3} apart in \
OKLab, which reads as a shading step and not a boundary"
);
}
}
}
}
#[test]
fn the_darkest_ink_step_still_separates_the_basins() {
for degree in MIN_DEGREE..=MAX_DEGREE {
let mut effect = Newton::new(
NewtonOptions {
degree: degree as u8,
..NewtonOptions::default()
},
(80, 24),
);
settle(&mut effect);
for step in 0..effect.shaded.len() {
let ladder: Vec<Color> =
effect.shaded.iter().map(|rungs| rungs[step]).collect();
for i in 0..ladder.len() {
for j in (i + 1)..ladder.len() {
let d = perceptual_distance(ladder[i], ladder[j]);
assert!(
d > MIN_DARK_SEPARATION,
"degree {degree}, ink step {step}: roots {i} and {j} are \
only {d:.3} apart; the shading has eaten the hue"
);
}
}
}
}
}
#[test]
fn basins_are_separated_in_hue_and_not_only_in_brightness() {
for degree in MIN_DEGREE..=MAX_DEGREE {
let effect = Newton::new(
NewtonOptions {
degree: degree as u8,
..NewtonOptions::default()
},
(80, 24),
);
for i in 0..effect.root_colors.len() {
for j in (i + 1)..effect.root_colors.len() {
let a = opponent(effect.root_colors[i]);
let b = opponent(effect.root_colors[j]);
let hue_gap = ((a.0 - b.0).abs() + (a.1 - b.1).abs()) / 2.0;
let light_gap = (a.2 - b.2).abs();
assert!(
hue_gap > 40.0,
"degree {degree}: roots {i} {a:?} and {j} {b:?} differ by \
{hue_gap:.0} in the opponent axes, which is a shading step"
);
assert!(
hue_gap > light_gap * 0.5,
"degree {degree}: roots {i} and {j} separate mostly in \
brightness ({light_gap:.0}), which is the other channel"
);
}
}
}
}
#[test]
fn the_zoom_is_continuous_over_a_whole_cycle() {
let mut effect = Newton::new(NewtonOptions::default(), (80, 24));
let mut previous = effect.camera().half_height;
let mut jumps = 0;
for _ in 0..600 {
effect.advance(1.0 / 60.0);
let now = effect.camera().half_height;
if (now / previous - 1.0).abs() > 0.25 {
jumps += 1;
}
previous = now;
}
assert_eq!(jumps, 0, "the camera jumped {jumps} times in ten seconds");
}
#[test]
fn the_zoom_visits_both_ends_of_its_range() {
let mut effect = Newton::new(NewtonOptions::default(), (80, 24));
let mut lo = f64::INFINITY;
let mut hi = 0.0f64;
for _ in 0..1800 {
effect.advance(1.0 / 60.0);
let s = effect.camera().half_height;
lo = lo.min(s);
hi = hi.max(s);
}
assert!(
hi / lo > 5.0,
"the scale only ranged over {lo:.4}..{hi:.4}, a ratio of {:.2}",
hi / lo
);
}
#[test]
fn a_tighter_iteration_cap_costs_the_picture_not_just_time() {
let (w, h) = (120usize, 40usize);
let mut generous =
Newton::new(NewtonOptions::default(), (w as u16, h as u16));
settle(&mut generous);
let loose = convergence_failure(&generous, w, h, 48);
let mut tight = Newton::new(
NewtonOptions {
max_iterations: 6,
..NewtonOptions::default()
},
(w as u16, h as u16),
);
settle(&mut tight);
let clipped = convergence_failure(&tight, w, h, 6);
assert!(
loose < 0.01,
"a cap of 48 failed to converge on {:.2}% of the frame",
loose * 100.0
);
assert!(
clipped > 0.25,
"a cap of 6 only failed on {:.2}% of the frame, so the cap is not the \
quality lever this file's docs describe",
clipped * 100.0
);
}
fn convergence_failure(effect: &Newton, w: usize, h: usize, cap: u16) -> f32 {
let degree = effect.degree();
let camera = effect.camera();
let (cos_r, sin_r) =
(camera.rotation.cos() as f32, camera.rotation.sin() as f32);
let (hw, hh) = (camera.half_width as f32, camera.half_height as f32);
let (c, roots) = (effect.c, &effect.roots);
let failures = normalised_points(w, h)
.into_iter()
.filter(|(nx, ny)| {
let (rx, ry) = (nx * cos_r - ny * sin_r, nx * sin_r + ny * cos_r);
!newton_iter(
Complex::new(rx * hw, ry * hh),
degree,
c,
roots,
u32::from(cap),
1e-3,
)
.ok
})
.count();
failures as f32 / (w * h) as f32
}
#[test]
fn the_default_ramp_has_no_space_in_it() {
let options = NewtonOptions::default();
let glyphs =
glyph_presets::by_name(&options.ramp).expect("the default exists");
assert!(
!glyphs.contains(' '),
"the default ramp {:?} contains a space, so the low end of every basin \
would be a hole",
options.ramp
);
}
#[test]
fn any_named_ramp_renders_and_an_unknown_one_falls_back() {
for (name, _) in glyph_presets::ALL {
let mut effect = Newton::new(
NewtonOptions {
ramp: String::from(*name),
..NewtonOptions::default()
},
(60, 20),
);
settle(&mut effect);
assert_eq!(effect.scratch.len(), 60 * 20, "ramp {name} drew no frame");
}
let mut effect = Newton::new(
NewtonOptions {
ramp: String::from("not-a-ramp"),
..NewtonOptions::default()
},
(60, 20),
);
settle(&mut effect);
assert_eq!(
effect.ramp.len(),
GlyphRamp::from_text(glyph_presets::INKED).len(),
"an unknown ramp name did not fall back to the default"
);
}
#[test]
fn every_degree_renders_with_visible_basins() {
for degree in MIN_DEGREE..=MAX_DEGREE {
let mut effect = Newton::new(
NewtonOptions {
degree: degree as u8,
..NewtonOptions::default()
},
(80, 24),
);
settle(&mut effect);
let basins = basin_grid(&effect, 80, 24);
let converged: HashSet<u8> =
basins.iter().copied().filter(|b| *b != NO_BASIN).collect();
assert_eq!(
converged.len(),
degree,
"degree {degree}: {converged:?} on screen, wanted {degree} basins"
);
}
}
#[test]
fn a_resize_keeps_the_frame_buffer_the_right_size() {
let mut effect = Newton::new(NewtonOptions::default(), (120, 40));
settle(&mut effect);
for (w, h) in [(80u16, 24u16), (200, 50), (6, 6), (400, 200)] {
effect.update_size(w, h);
let _ = effect.get_diff();
assert_eq!(effect.screen_size, normalize_effect_size((w, h)));
assert_eq!(effect.scratch.len(), w as usize * h as usize);
}
}
#[test]
fn the_specialised_iteration_draws_the_same_picture() {
for degree in MIN_DEGREE..=MAX_DEGREE {
let c = drift_constant(std::f32::consts::PI, 0.45);
let roots = durand_kerner(degree, c);
let mut total = 0usize;
let mut disagree = 0usize;
for (nx, ny) in normalised_points(80, 40) {
let start = Complex::new(nx * 3.0, ny * 1.5);
let fast = newton_iter(start, degree, c, &roots, 32, 1e-3);
let slow = newton_iter_generic(start, degree, c, &roots, 32, 1e-3);
total += 1;
if (fast.ok, fast.root) != (slow.ok, slow.root) {
disagree += 1;
}
}
let rate = 100.0 * disagree as f64 / total as f64;
assert!(
rate < 1.0,
"degree {degree}: {disagree} of {total} samples ({rate:.2}%) were \
drawn by a different basin"
);
}
}
#[test]
fn a_hostile_config_renders_rather_than_panicking() {
let hostile = NewtonOptions {
degree: 99,
max_iterations: 0,
tolerance: 5.0,
shade_steps: 0,
depth: 0.0,
zoom_speed: 0.0,
spin_speed: 0.0,
drift_radius: -3.0,
drift_speed: 0.0,
ramp: String::from("nonexistent"),
..NewtonOptions::default()
};
let mut effect = Newton::new(hostile.clone(), (80, 24));
settle(&mut effect);
assert_eq!(
effect.degree(),
MAX_DEGREE,
"an out-of-range degree was not clamped"
);
assert_eq!(effect.iteration_budget(), 1, "a zero cap was not clamped");
assert!(
(0.0..=0.5).contains(&effect.tolerance()),
"a tolerance of 5.0 escaped the clamp"
);
assert_eq!(
effect.shade_steps(),
MIN_SHADE_STEPS as usize,
"zero shade steps was not clamped"
);
for options in [
NewtonOptions {
tolerance: f32::NAN,
..NewtonOptions::default()
},
NewtonOptions {
depth: f32::NAN,
..NewtonOptions::default()
},
NewtonOptions {
drift_radius: f32::NAN,
..NewtonOptions::default()
},
] {
let mut effect = Newton::new(options, (60, 20));
effect.advance(1.0 / 60.0);
let _ = effect.get_diff();
}
let mut wide = Newton::new(hostile, (1000, 4));
settle(&mut wide);
assert_eq!(wide.screen_size, normalize_effect_size((1000, 4)));
assert_eq!(wide.scratch.len(), 1000 * MIN_EFFECT_SIZE as usize);
}
#[test]
fn a_frame_is_drawn_and_stays_in_bounds() {
let mut effect = Newton::new(NewtonOptions::default(), (80, 24));
settle(&mut effect);
effect.advance(1.0 / 60.0);
let diff = effect.get_diff();
assert!(!diff.is_empty(), "a settled effect drew nothing");
for (x, y, _) in &diff {
assert!(*x < 80 && *y < 24, "cell ({x}, {y}) is outside 80x24");
}
}
#[test]
fn an_unchanged_frame_reports_no_cells() {
let mut effect = Newton::new(NewtonOptions::default(), (80, 24));
settle(&mut effect);
let diff = effect.get_diff();
assert!(
diff.is_empty(),
"drawing twice with no time in between reported {} changed cells",
diff.len()
);
}
fn cell_colors(effect: &mut Newton) -> Vec<Color> {
let _ = effect.get_diff();
effect.scratch.iter().map(|c| c.color).collect()
}
fn normalised_points(w: usize, h: usize) -> Vec<(f32, f32)> {
let mut out = Vec::with_capacity(w * h);
for y in 0..h {
let ny = ((y as f32 + 0.5) / h as f32) * 2.0 - 1.0;
for x in 0..w {
let nx = ((x as f32 + 0.5) / w as f32) * 2.0 - 1.0;
out.push((nx, ny));
}
}
out
}
fn basin_grid(effect: &Newton, w: usize, h: usize) -> Vec<u8> {
let degree = effect.degree();
let camera = effect.camera();
let (cos_r, sin_r) =
(camera.rotation.cos() as f32, camera.rotation.sin() as f32);
let (hw, hh) = (camera.half_width as f32, camera.half_height as f32);
let (c, roots) = (effect.c, &effect.roots);
normalised_points(w, h)
.into_iter()
.map(|(nx, ny)| {
let (rx, ry) = (nx * cos_r - ny * sin_r, nx * sin_r + ny * cos_r);
let got = newton_iter(
Complex::new(rx * hw, ry * hh),
degree,
c,
roots,
32,
1e-3,
);
if got.ok { got.root as u8 } else { NO_BASIN }
})
.collect()
}
fn boundary_percent(basins: &[u8], w: usize, h: usize) -> f32 {
let mut boundary = 0usize;
for y in 0..h.saturating_sub(1) {
for x in 0..w.saturating_sub(1) {
let a = basins[y * w + x];
if a != basins[y * w + x + 1] || a != basins[(y + 1) * w + x] {
boundary += 1;
}
}
}
100.0 * boundary as f32 / (w * h) as f32
}
fn basin_shares(effect: &Newton) -> Vec<f32> {
let degree = effect.degree();
let (w, h) = (effect.screen_size.0 as usize, effect.screen_size.1 as usize);
let basins = basin_grid(effect, w, h);
let mut counts = vec![0usize; degree];
let mut total = 0usize;
for b in &basins {
if (*b as usize) < degree {
counts[*b as usize] += 1;
total += 1;
}
}
counts
.iter()
.map(|c| *c as f32 / total.max(1) as f32)
.collect()
}
fn opponent(color: Color) -> (f32, f32, f32) {
let (r, g, b) = match color {
Color::Rgb { r, g, b } => (r as f32, g as f32, b as f32),
_ => (0.0, 0.0, 0.0),
};
(r - b, g - b, 0.2126 * r + 0.7152 * g + 0.0722 * b)
}
}