pub(crate) const SDF_BUFFER: u32 = 3;
pub(crate) const SDF_RADIUS: u32 = 8;
pub(crate) const SDF_CUTOFF: f64 = 0.25;
const INF: f64 = 1e20;
pub(crate) fn alpha_to_sdf(
width: u32,
height: u32,
rgba: &[u8],
pixel_ratio: u8,
) -> (u32, u32, Vec<u8>) {
let ratio = u32::from(pixel_ratio);
let buffer = SDF_BUFFER * ratio;
let radius = f64::from(SDF_RADIUS * ratio);
let out_width = width + 2 * buffer;
let out_height = height + 2 * buffer;
let size = out_width as usize * out_height as usize;
let mut outer = vec![INF; size];
let mut inner = vec![0.0; size];
for y in 0..height {
for x in 0..width {
let alpha = rgba[((y * width + x) * 4 + 3) as usize];
let index = ((y + buffer) * out_width + x + buffer) as usize;
if alpha == 255 {
outer[index] = 0.0;
inner[index] = INF;
} else if alpha != 0 {
let distance = 0.5 - f64::from(alpha) / 255.0;
outer[index] = if distance > 0.0 {
distance * distance
} else {
0.0
};
inner[index] = if distance < 0.0 {
distance * distance
} else {
0.0
};
}
}
}
let mut work = Work::new(out_width.max(out_height) as usize);
edt(
&mut outer,
out_width as usize,
out_height as usize,
&mut work,
);
edt(
&mut inner,
out_width as usize,
out_height as usize,
&mut work,
);
let mut pixels = vec![0; size * 4];
for index in 0..size {
let distance = outer[index].sqrt() - inner[index].sqrt();
let value = (255.0 - 255.0 * (distance / radius + SDF_CUTOFF)).round();
pixels[index * 4 + 3] = value.clamp(0.0, 255.0) as u8;
}
(out_width, out_height, pixels)
}
struct Work {
f: Vec<f64>,
v: Vec<usize>,
z: Vec<f64>,
}
impl Work {
fn new(length: usize) -> Self {
Self {
f: vec![0.0; length],
v: vec![0; length],
z: vec![0.0; length + 1],
}
}
}
fn edt(grid: &mut [f64], width: usize, height: usize, work: &mut Work) {
for x in 0..width {
edt_1d(grid, x, width, height, work);
}
for y in 0..height {
edt_1d(grid, y * width, 1, width, work);
}
}
fn edt_1d(grid: &mut [f64], offset: usize, stride: usize, length: usize, work: &mut Work) {
let Work { f, v, z } = work;
for q in 0..length {
f[q] = grid[offset + q * stride];
}
v[0] = 0;
z[0] = -INF;
z[1] = INF;
let mut k: isize = 0;
for q in 1..length {
let qf = q as f64;
let mut s;
loop {
let r = v[k as usize];
let rf = r as f64;
s = (f[q] - f[r] + qf * qf - rf * rf) / (qf - rf) / 2.0;
if s <= z[k as usize] {
k -= 1;
if k > -1 {
continue;
}
}
break;
}
k += 1;
let k_index = k as usize;
v[k_index] = q;
z[k_index] = s;
z[k_index + 1] = INF;
}
let mut k = 0;
for q in 0..length {
while z[k + 1] < q as f64 {
k += 1;
}
let r = v[k];
let distance = q as f64 - r as f64;
grid[offset + q * stride] = f[r] + distance * distance;
}
}
#[cfg(test)]
mod tests {
use super::*;
fn square(size: u32, side: u32) -> Vec<u8> {
let offset = (size - side) / 2;
let mut rgba = vec![0; (size * size * 4) as usize];
for y in offset..offset + side {
for x in offset..offset + side {
rgba[((y * size + x) * 4 + 3) as usize] = 255;
}
}
rgba
}
fn alpha(pixels: &[u8], width: u32, x: u32, y: u32) -> u8 {
pixels[((y * width + x) * 4 + 3) as usize]
}
#[test]
fn opaque_square_matches_hand_computed_values() {
let (width, height, pixels) = alpha_to_sdf(10, 10, &square(10, 10), 1);
assert_eq!((width, height), (16, 16));
assert_eq!(alpha(&pixels, width, 7, 7), 255);
assert_eq!(alpha(&pixels, width, 3, 7), 223);
assert_eq!(alpha(&pixels, width, 2, 7), 159);
assert_eq!(alpha(&pixels, width, 0, 0), 56);
assert!(pixels.chunks_exact(4).all(|pixel| pixel[..3] == [0, 0, 0]));
}
#[test]
fn output_is_symmetric() {
let (width, height, pixels) = alpha_to_sdf(10, 10, &square(10, 6), 1);
for y in 0..height {
for x in 0..width {
let value = alpha(&pixels, width, x, y);
assert_eq!(value, alpha(&pixels, width, width - 1 - x, y));
assert_eq!(value, alpha(&pixels, width, x, height - 1 - y));
assert_eq!(value, alpha(&pixels, width, y, x));
}
}
}
#[test]
fn padding_and_radius_scale_with_pixel_ratio() {
let (width, height, pixels) = alpha_to_sdf(20, 20, &square(20, 20), 2);
assert_eq!((width, height), (32, 32));
assert_eq!(alpha(&pixels, width, 7, 15), 223);
assert_eq!(alpha(&pixels, width, 4, 15), 159);
assert_eq!(alpha(&pixels, width, 6, 15), 207);
assert_eq!(alpha(&pixels, width, 5, 15), 175);
}
#[test]
fn fully_transparent_input_becomes_zero() {
let (width, height, pixels) = alpha_to_sdf(4, 3, &[0; 4 * 3 * 4], 1);
assert_eq!((width, height), (10, 9));
assert!(pixels.iter().all(|&value| value == 0));
}
}