#[doc(hidden)]
pub const INF: f64 = 1e20;
pub fn edt_1d(f: &[f64], d: &mut [f64], v: &mut [usize], z: &mut [f64], n: usize) {
if n == 0 {
return;
}
v[0] = 0;
z[0] = -INF;
z[1] = INF;
let mut k: isize = 0;
for q in 1..n {
let mut s;
loop {
let r = v[k as usize];
s = (f[q] - f[r] + (q * q) as f64 - (r * r) as f64) / (2 * q - 2 * r) as f64;
if s > z[k as usize] {
break;
}
k -= 1;
if k < 0 {
break;
}
}
k += 1;
let ku = k as usize;
v[ku] = q;
z[ku] = s;
z[ku + 1] = INF;
}
let mut k: usize = 0;
for (q, dq) in d.iter_mut().enumerate().take(n) {
while z[k + 1] < q as f64 {
k += 1;
}
let dx = q as f64 - v[k] as f64;
*dq = dx * dx + f[v[k]];
}
}
pub(crate) fn edt_2d(grid: &mut [f64], width: usize, height: usize) {
let max_dim = width.max(height);
let mut f = vec![0.0f64; max_dim];
let mut d = vec![0.0f64; max_dim];
let mut v = vec![0usize; max_dim];
let mut z = vec![0.0f64; max_dim + 1];
for x in 0..width {
for y in 0..height {
f[y] = grid[y * width + x];
}
edt_1d(&f, &mut d, &mut v, &mut z, height);
for y in 0..height {
grid[y * width + x] = d[y];
}
}
for y in 0..height {
let offset = y * width;
f[..width].copy_from_slice(&grid[offset..offset + width]);
edt_1d(&f, &mut d, &mut v, &mut z, width);
grid[offset..offset + width].copy_from_slice(&d[..width]);
}
}
pub fn compute_sdf(alpha: &[u8], width: usize, height: usize, alpha_threshold: u8) -> Vec<f64> {
let size = width * height;
assert_eq!(alpha.len(), size, "alpha plane must be width * height");
let mut outside = vec![0.0f64; size];
let mut inside = vec![0.0f64; size];
for i in 0..size {
if alpha[i] >= alpha_threshold {
outside[i] = 0.0;
inside[i] = INF;
} else {
outside[i] = INF;
inside[i] = 0.0;
}
}
edt_2d(&mut outside, width, height);
edt_2d(&mut inside, width, height);
(0..size)
.map(|i| outside[i].sqrt() - inside[i].sqrt())
.collect()
}
pub fn compute_sdf_default(alpha: &[u8], width: usize, height: usize) -> Vec<f64> {
compute_sdf(alpha, width, height, 128)
}