pub mod d2;
pub mod d3;
mod shape;
#[cfg(all(target_arch = "wasm32", not(threers_no_js_bindings)))]
mod web;
pub use shape::Shape;
#[cfg(all(target_arch = "wasm32", not(threers_no_js_bindings)))]
pub use web::WebSdf;
use crate::core::{BufferAttribute, BufferGeometry};
use crate::extras::MarchingCubes;
use crate::math::{Vector2, Vector3};
pub const WGSL: &str = crate::wgsl!(include_str!("sdf.wgsl"));
#[inline]
pub fn union(a: f32, b: f32) -> f32 {
a.min(b)
}
#[inline]
pub fn intersection(a: f32, b: f32) -> f32 {
a.max(b)
}
#[inline]
pub fn subtraction(a: f32, b: f32) -> f32 {
a.max(-b)
}
#[inline]
pub fn smooth_union(a: f32, b: f32, k: f32) -> f32 {
smooth_union_blend(a, b, k).0
}
#[inline]
pub fn smooth_union_blend(a: f32, b: f32, k: f32) -> (f32, f32) {
if k <= 0.0 {
return if a <= b { (a, 1.0) } else { (b, 0.0) };
}
let h = (0.5 + 0.5 * (b - a) / k).clamp(0.0, 1.0);
(b + (a - b) * h - k * h * (1.0 - h), h)
}
#[inline]
pub fn smooth_intersection(a: f32, b: f32, k: f32) -> f32 {
-smooth_union(-a, -b, k)
}
#[inline]
pub fn smooth_subtraction(a: f32, b: f32, k: f32) -> f32 {
-smooth_union(-a, b, k)
}
#[inline]
pub fn round(d: f32, r: f32) -> f32 {
d - r
}
#[inline]
pub fn onion(d: f32, t: f32) -> f32 {
d.abs() - t
}
#[inline]
pub fn coverage(d: f32) -> f32 {
(0.5 - d).clamp(0.0, 1.0)
}
#[inline]
pub fn footprint(g: Vector2) -> f32 {
let l = g.length();
if l > 1e-12 {
(g.x.abs() + g.y.abs()) / l
} else {
1.0
}
}
#[inline]
pub fn coverage_edge(d: f32, footprint: f32) -> f32 {
(0.5 - d / footprint.max(1e-6)).clamp(0.0, 1.0)
}
#[inline]
pub fn coverage_stroke(u: f32, half_width: f32, footprint: f32) -> f32 {
let (u, h) = (u.abs(), half_width.max(0.0));
let w = footprint.max(1e-6);
let lo = (u - 0.5 * w).max(-h);
let hi = (u + 0.5 * w).min(h);
((hi - lo) / w).clamp(0.0, 1.0)
}
pub trait Sdf2 {
fn distance(&self, p: Vector2) -> f32;
fn gradient(&self, p: Vector2, h: f32) -> Vector2 {
let dx =
self.distance(Vector2::new(p.x + h, p.y)) - self.distance(Vector2::new(p.x - h, p.y));
let dy =
self.distance(Vector2::new(p.x, p.y + h)) - self.distance(Vector2::new(p.x, p.y - h));
Vector2::new(dx, dy) * (0.5 / h)
}
}
impl<F: Fn(Vector2) -> f32> Sdf2 for F {
fn distance(&self, p: Vector2) -> f32 {
self(p)
}
}
#[derive(Debug, Clone, Copy)]
pub struct Raymarch {
pub max_distance: f32,
pub max_steps: u32,
pub epsilon: f32,
}
impl Default for Raymarch {
fn default() -> Self {
Self {
max_distance: 100.0,
max_steps: 256,
epsilon: 1e-4,
}
}
}
#[derive(Debug, Clone, Copy)]
pub struct RayHit {
pub distance: f32,
pub point: Vector3,
pub normal: Vector3,
pub steps: u32,
}
pub trait Sdf3 {
fn distance(&self, p: Vector3) -> f32;
fn normal(&self, p: Vector3, h: f32) -> Vector3 {
let k = [
Vector3::new(1.0, -1.0, -1.0),
Vector3::new(-1.0, -1.0, 1.0),
Vector3::new(-1.0, 1.0, -1.0),
Vector3::new(1.0, 1.0, 1.0),
];
let mut n = Vector3::ZERO;
for e in k {
n = n + e * self.distance(p + e * h);
}
n.normalize()
}
fn raymarch(&self, origin: Vector3, direction: Vector3, settings: Raymarch) -> Option<RayHit> {
let dir = direction.normalize();
let mut t = 0.0f32;
for step in 0..settings.max_steps {
let p = origin + dir * t;
let d = self.distance(p);
let eps = settings.epsilon * t.max(1.0);
if d < eps {
let h = eps.max(1e-5);
return Some(RayHit {
distance: t,
point: p,
normal: self.normal(p, h),
steps: step + 1,
});
}
t += d;
if t > settings.max_distance {
break;
}
}
None
}
fn to_geometry(&self, resolution: usize, centre: Vector3, size: Vector3) -> BufferGeometry {
let mut geometry = MarchingCubes::new(resolution, size).extract(0.0, |x, y, z| {
-self.distance(Vector3::new(x, y, z) + centre)
});
if centre != Vector3::ZERO
&& let Some(position) = geometry.get_attribute("position")
{
let mut array = position.array.clone();
for v in array.as_chunks_mut::<3>().0 {
v[0] += centre.x;
v[1] += centre.y;
v[2] += centre.z;
}
geometry.set_attribute("position", BufferAttribute::new(array, 3));
}
geometry
}
fn to_surface_nets(&self, cell: f32, min: Vector3, max: Vector3) -> SurfaceNets {
let g = cell.max(1e-6);
let n = |lo: f32, hi: f32| (((hi - lo) / g).ceil() as usize + 1).max(2);
let (nx, ny, nz) = (n(min.x, max.x), n(min.y, max.y), n(min.z, max.z));
let id = |i: usize, j: usize, k: usize| (k * ny + j) * nx + i;
let at =
|i: usize, j: usize, k: usize| min + Vector3::new(i as f32, j as f32, k as f32) * g;
let mut field = vec![0.0f32; nx * ny * nz];
for k in 0..nz {
for j in 0..ny {
for i in 0..nx {
field[id(i, j, k)] = self.distance(at(i, j, k));
}
}
}
const CORNER: [[usize; 3]; 8] = [
[0, 0, 0],
[1, 0, 0],
[0, 1, 0],
[1, 1, 0],
[0, 0, 1],
[1, 0, 1],
[0, 1, 1],
[1, 1, 1],
];
const EDGE: [[usize; 2]; 12] = [
[0, 1],
[2, 3],
[4, 5],
[6, 7],
[0, 2],
[1, 3],
[4, 6],
[5, 7],
[0, 4],
[1, 5],
[2, 6],
[3, 7],
];
let (cx, cy, cz) = (nx - 1, ny - 1, nz - 1);
let cid = |i: usize, j: usize, k: usize| (k * cy + j) * cx + i;
let mut cell_vertex = vec![u32::MAX; cx * cy * cz];
let mut position: Vec<Vector3> = Vec::new();
for k in 0..cz {
for j in 0..cy {
for i in 0..cx {
let mut v = [0.0f32; 8];
let mut inside = 0;
for (c, o) in CORNER.iter().enumerate() {
v[c] = field[id(i + o[0], j + o[1], k + o[2])];
inside += (v[c] < 0.0) as u32;
}
if inside == 0 || inside == 8 {
continue;
}
let (mut sum, mut count) = (Vector3::ZERO, 0.0f32);
for [a, b] in EDGE {
if (v[a] < 0.0) == (v[b] < 0.0) {
continue;
}
let t = v[a] / (v[a] - v[b]);
let (pa, pb) = (CORNER[a], CORNER[b]);
let corner =
|q: [usize; 3]| Vector3::new(q[0] as f32, q[1] as f32, q[2] as f32);
sum = sum + corner(pa) + (corner(pb) - corner(pa)) * t;
count += 1.0;
}
cell_vertex[cid(i, j, k)] = position.len() as u32;
position.push(at(i, j, k) + sum * (g / count));
}
}
}
let h = g * 0.1;
let mut normal = Vec::with_capacity(position.len());
for p in position.iter_mut() {
for _ in 0..3 {
let d = self.distance(*p);
let grad = self.normal(*p, h);
if !grad.x.is_finite() {
break;
}
*p = *p - grad * d;
}
normal.push(self.normal(*p, h));
}
let mut index: Vec<u32> = Vec::new();
let mut quad = |q: [u32; 4]| {
if q.iter().all(|&v| v != u32::MAX) {
index.extend_from_slice(&[q[0], q[1], q[2], q[0], q[2], q[3]]);
}
};
let cv = |i: usize, j: usize, k: usize| cell_vertex[cid(i, j, k)];
for k in 1..cz {
for j in 1..cy {
for i in 0..cx {
if (field[id(i, j, k)] < 0.0) != (field[id(i + 1, j, k)] < 0.0) {
quad([
cv(i, j - 1, k - 1),
cv(i, j, k - 1),
cv(i, j, k),
cv(i, j - 1, k),
]);
}
}
}
}
for k in 1..cz {
for j in 0..cy {
for i in 1..cx {
if (field[id(i, j, k)] < 0.0) != (field[id(i, j + 1, k)] < 0.0) {
quad([
cv(i - 1, j, k - 1),
cv(i - 1, j, k),
cv(i, j, k),
cv(i, j, k - 1),
]);
}
}
}
}
for k in 0..cz {
for j in 1..cy {
for i in 1..cx {
if (field[id(i, j, k)] < 0.0) != (field[id(i, j, k + 1)] < 0.0) {
quad([
cv(i - 1, j - 1, k),
cv(i, j - 1, k),
cv(i, j, k),
cv(i - 1, j, k),
]);
}
}
}
}
for t in index.as_chunks_mut::<3>().0 {
let (a, b, c) = (t[0] as usize, t[1] as usize, t[2] as usize);
let face = (position[b] - position[a]).cross(position[c] - position[a]);
if face.dot(normal[a] + normal[b] + normal[c]) < 0.0 {
t.swap(1, 2);
}
}
SurfaceNets {
position,
normal,
index,
}
}
}
#[derive(Debug, Clone, Default)]
pub struct SurfaceNets {
pub position: Vec<Vector3>,
pub normal: Vec<Vector3>,
pub index: Vec<u32>,
}
impl SurfaceNets {
pub fn to_geometry(&self) -> BufferGeometry {
let flat = |v: &[Vector3]| v.iter().flat_map(|p| [p.x, p.y, p.z]).collect::<Vec<f32>>();
let mut g = BufferGeometry::new();
g.set_attribute("position", BufferAttribute::new(flat(&self.position), 3));
g.set_attribute("normal", BufferAttribute::new(flat(&self.normal), 3));
g.set_index(self.index.clone());
g
}
pub fn triangle_count(&self) -> usize {
self.index.len() / 3
}
}
impl<F: Fn(Vector3) -> f32> Sdf3 for F {
fn distance(&self, p: Vector3) -> f32 {
self(p)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn smooth_union_is_the_hard_union_beyond_k() {
assert_eq!(smooth_union(1.0, 3.0, 0.5), 1.0);
assert_eq!(smooth_union(3.0, 1.0, 0.5), 1.0);
assert!((smooth_union(1.0, 1.0, 0.8) - 0.8).abs() < 1e-6);
for i in 0..50 {
let a = i as f32 * 0.05 - 1.0;
for k in [0.1, 0.5, 2.0] {
assert!(smooth_union(a, 0.2, k) <= a.min(0.2) + 1e-7);
}
}
}
#[test]
fn a_zero_width_blend_is_a_hard_union() {
assert_eq!(smooth_union_blend(0.3, 0.7, 0.0), (0.3, 1.0));
assert_eq!(smooth_union_blend(0.7, 0.3, 0.0), (0.3, 0.0));
assert_eq!(smooth_intersection(0.3, 0.7, 0.0), 0.7);
}
#[test]
fn the_blend_weight_follows_the_nearer_field() {
assert_eq!(smooth_union_blend(0.0, 5.0, 1.0).1, 1.0);
assert_eq!(smooth_union_blend(5.0, 0.0, 1.0).1, 0.0);
assert!((smooth_union_blend(2.0, 2.0, 1.0).1 - 0.5).abs() < 1e-6);
}
#[test]
fn subtraction_and_intersection_signs() {
let p = |r: f32| (r - 1.0, r - 0.5);
let (a, b) = p(0.25);
assert!(subtraction(a, b) > 0.0, "the hole is outside");
let (a, b) = p(0.75);
assert!(subtraction(a, b) < 0.0, "the ring is inside");
assert!(intersection(a, b) > 0.0);
assert!(smooth_subtraction(a, b, 0.05) < 0.0);
}
#[test]
fn raymarch_finds_a_sphere_and_misses_beside_it() {
let ball = |p: Vector3| d3::sphere(p, 1.0);
let hit = ball
.raymarch(
Vector3::new(0.0, 0.0, -4.0),
Vector3::new(0.0, 0.0, 2.0),
Raymarch::default(),
)
.unwrap();
assert!((hit.distance - 3.0).abs() < 1e-3, "{hit:?}");
assert!((hit.normal.z + 1.0).abs() < 1e-3, "{hit:?}");
assert!(ball
.raymarch(
Vector3::new(1.5, 0.0, -4.0),
Vector3::new(0.0, 0.0, 1.0),
Raymarch::default()
)
.is_none());
let inside = ball
.raymarch(
Vector3::ZERO,
Vector3::new(1.0, 0.0, 0.0),
Raymarch::default(),
)
.unwrap();
assert_eq!(inside.distance, 0.0);
}
#[test]
fn meshing_an_offset_sphere_lands_where_the_field_is() {
let c = Vector3::new(3.0, -1.0, 2.0);
let ball = move |p: Vector3| d3::sphere(p - c, 0.8);
let mut g = ball.to_geometry(32, c, Vector3::new(2.0, 2.0, 2.0));
assert!(g.triangle_count() > 100);
let b = g.compute_bounding_box();
for (lo, hi, centre) in [
(b.min.x, b.max.x, c.x),
(b.min.y, b.max.y, c.y),
(b.min.z, b.max.z, c.z),
] {
assert!(
(lo - (centre - 0.8)).abs() < 0.05,
"{lo} vs {}",
centre - 0.8
);
assert!(
(hi - (centre + 0.8)).abs() < 0.05,
"{hi} vs {}",
centre + 0.8
);
}
for p in g.positions().unwrap() {
assert!(ball(p).abs() < 0.01, "{p:?} is {} off", ball(p));
}
}
#[test]
fn stroke_coverage_conserves_the_line_width() {
for (w, step) in [
(1.0f32, 1.0f32),
(std::f32::consts::SQRT_2, std::f32::consts::FRAC_1_SQRT_2),
] {
for half in [0.05f32, 0.2, 0.35, 0.5, 1.3, 4.0] {
for k in 0..10 {
let phase = k as f32 / 10.0 * step;
let total: f32 = (-20..=20)
.map(|i| coverage_stroke(i as f32 * step + phase, half, w))
.sum();
assert!(
(total * step - 2.0 * half).abs() < 1e-4 * (1.0 + half),
"w {w} half {half} phase {phase}: {}",
total * step
);
}
}
}
}
#[test]
fn stroke_coverage_peaks_at_the_width_and_matches_edges_when_thick() {
assert!((coverage_stroke(0.0, 0.2, 1.0) - 0.4).abs() < 1e-6);
assert!(
(coverage(0.0 - 0.2) - 0.7).abs() < 1e-6,
"what the edge rule gives"
);
assert_eq!(
coverage_stroke(1.0, 0.2, 1.0),
0.0,
"a pixel away it is gone"
);
for i in 0..40 {
let u = i as f32 * 0.1;
assert!(
(coverage_stroke(u, 2.0, 1.0) - coverage(u - 2.0)).abs() < 1e-6,
"{u}"
);
assert!(
(coverage_stroke(u, 2.0, 1.3) - coverage_edge(u - 2.0, 1.3)).abs() < 1e-6,
"{u}"
);
}
}
#[test]
fn the_footprint_widens_on_a_diagonal() {
assert_eq!(footprint(Vector2::new(0.0, -3.0)), 1.0);
assert!((footprint(Vector2::new(1.0, 1.0)) - std::f32::consts::SQRT_2).abs() < 1e-6);
assert_eq!(footprint(Vector2::ZERO), 1.0);
assert_eq!(coverage_edge(0.0, 1.4), 0.5);
assert!(
(coverage_edge(0.6, 1.4) - (0.5 - 0.6 / 1.4)).abs() < 1e-6,
"still partly covered"
);
assert_eq!(
coverage(0.6),
0.0,
"where the one-pixel ramp has already stopped"
);
}
#[test]
fn gradients_are_unit_on_exact_fields() {
let disc = |p: Vector2| d2::circle(p, 1.0);
let g = disc.gradient(Vector2::new(2.0, 0.0), 1e-3);
assert!((g.x - 1.0).abs() < 1e-3 && g.y.abs() < 1e-3);
let n = (|p: Vector3| d3::cuboid(p, Vector3::new(1.0, 2.0, 3.0)))
.normal(Vector3::new(0.2, 2.5, 0.1), 1e-3);
assert!((n.y - 1.0).abs() < 1e-3, "{n:?}");
}
}