sdfer/
bruteforce_bitmap.rs

1//! Bitmap-based "closest opposite-color pixel" bruteforce search.
2//!
3//! This algorithm is a commonly implemented one, but a naive and inefficient one.
4//!
5//! It was most notably popularized by Valve in their 2007 SIGGRAPH entry,
6//! on using 2D texture-based SDFs to render text (or any vector shapes) in 3D environments,
7//! ["Improved Alpha-Tested Magnification for Vector Textures and Special Effects"](https://steamcdn-a.akamaihd.net/apps/valve/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf).
8
9use crate::{Bitmap, Image2d, Unorm8};
10
11// HACK(eddyb) only exists to allow toggling precision for testing purposes.
12#[cfg(sdfer_use_f64_instead_of_f32)]
13type f32 = f64;
14
15pub fn sdf(bitmap: &Bitmap, sdf_size: usize, spread: usize) -> Image2d<Unorm8> {
16    let (w, h) = (bitmap.width(), bitmap.height());
17
18    assert!(w.is_power_of_two() && h.is_power_of_two() && sdf_size.is_power_of_two());
19    let scale = w.max(h) / sdf_size;
20    assert_ne!(scale, 0);
21
22    let spread = spread * scale;
23
24    let width = w / scale;
25    let height = h / scale;
26    Image2d::from_fn(width, height, |x, y| {
27        let (x, y) = (x * scale + scale / 2, y * scale + scale / 2);
28        let inside = bitmap.get(x, y);
29        // FIXME(eddyb) this could use a spiral search, and maybe better bitmap
30        // access, e.g. "which bits in a block are different than the center x,y".
31        let dist = (((y.saturating_sub(spread)..=(y + spread))
32            .flat_map(|y2| (x.saturating_sub(spread)..=(x + spread)).map(move |x2| (x2, y2)))
33            .filter(|&(x2, y2)| x2 < w && y2 < h && bitmap.get(x2, y2) != inside)
34            .map(|(x2, y2)| x2.abs_diff(x).pow(2) + y2.abs_diff(y).pow(2))
35            .min()
36            .unwrap_or(usize::MAX) as f32)
37            .sqrt()
38            / (spread as f32))
39            .clamp(0.0, 1.0);
40        let signed_dist = if inside { -dist } else { dist };
41
42        // [-1, +1] -> [0, 1]
43        Unorm8::encode((signed_dist + 1.0) / 2.0)
44    })
45}
sdfer/bruteforce_bitmap.rs

sdfer/
bruteforce_bitmap.rs
