cranpose_ui_graphics/space/
sdf.rs

1//! Meshes from signed distance fields: the surface where a field is zero,
2//! found on a grid by surface nets.
3
4use std::f32::consts::{PI, TAU};
5
6use super::{Mesh, MeshError, Vec3};
7
8/// The corners of a grid cell, as offsets along x, y and z.
9const CORNERS: [[usize; 3]; 8] = [
10    [0, 0, 0],
11    [1, 0, 0],
12    [0, 1, 0],
13    [1, 1, 0],
14    [0, 0, 1],
15    [1, 0, 1],
16    [0, 1, 1],
17    [1, 1, 1],
18];
19
20/// The edges of a grid cell, as pairs of its corners.
21const EDGES: [[usize; 2]; 12] = [
22    [0, 1],
23    [2, 3],
24    [4, 5],
25    [6, 7],
26    [0, 2],
27    [1, 3],
28    [4, 6],
29    [5, 7],
30    [0, 4],
31    [1, 5],
32    [2, 6],
33    [3, 7],
34];
35
36/// For each axis, the step along a grid edge, and the four cells around the
37/// edge, as offsets back from its start, in turn around the edge.
38const AROUND_EDGES: [([usize; 3], [[usize; 3]; 4]); 3] = [
39    ([1, 0, 0], [[0, 1, 1], [0, 0, 1], [0, 0, 0], [0, 1, 0]]),
40    ([0, 1, 0], [[1, 0, 1], [1, 0, 0], [0, 0, 0], [0, 0, 1]]),
41    ([0, 0, 1], [[1, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0]]),
42];
43
44/// A field sampled on the points of a grid of `cells` cells along each side
45/// of the box from `low` with cells of `step`.
46struct Samples {
47    values: Vec<f32>,
48    cells: usize,
49    low: Vec3,
50    step: Vec3,
51}
52
53impl Samples {
54    fn of(field: &impl Fn(Vec3) -> f32, (low, high): (Vec3, Vec3), cells: usize) -> Self {
55        let side = cells as f32;
56        let step = Vec3::new(
57            (high.x - low.x) / side,
58            (high.y - low.y) / side,
59            (high.z - low.z) / side,
60        );
61        let points = cells + 1;
62        let mut values = Vec::with_capacity(points * points * points);
63        for k in 0..points {
64            for j in 0..points {
65                for i in 0..points {
66                    values.push(field(Self::place(low, step, [i, j, k])));
67                }
68            }
69        }
70        Self {
71            values,
72            cells,
73            low,
74            step,
75        }
76    }
77
78    fn place(low: Vec3, step: Vec3, [i, j, k]: [usize; 3]) -> Vec3 {
79        Vec3::new(
80            low.x + step.x * i as f32,
81            low.y + step.y * j as f32,
82            low.z + step.z * k as f32,
83        )
84    }
85
86    fn point(&self, at: [usize; 3]) -> Vec3 {
87        Self::place(self.low, self.step, at)
88    }
89
90    fn value(&self, [i, j, k]: [usize; 3]) -> f32 {
91        let points = self.cells + 1;
92        self.values[(k * points + j) * points + i]
93    }
94
95    /// Where the surface crosses the cell at `cell`: the mean of the points
96    /// where it crosses the cell's edges, or `None` when it misses the cell.
97    fn cell_point(&self, [i, j, k]: [usize; 3]) -> Option<Vec3> {
98        let corner = |index: usize| {
99            let [di, dj, dk] = CORNERS[index];
100            [i + di, j + dj, k + dk]
101        };
102        let (mut sum, mut count) = (Vec3::ZERO, 0.0);
103        for [a, b] in EDGES {
104            let (va, vb) = (self.value(corner(a)), self.value(corner(b)));
105            if (va < 0.0) == (vb < 0.0) {
106                continue;
107            }
108            let (pa, pb) = (self.point(corner(a)), self.point(corner(b)));
109            sum = sum + pa + (pb - pa) * (va / (va - vb));
110            count += 1.0;
111        }
112        (count > 0.0).then(|| sum * (1.0 / count))
113    }
114}
115
116#[expect(clippy::multiple_inherent_impl, reason = "constructor by its parser")]
117impl Mesh {
118    /// The surface where `field` is zero within the box from `bounds.0` to
119    /// `bounds.1`: a signed distance field, negative inside the shape,
120    /// sampled on a grid of `resolution` cells along each side of the box.
121    /// The normals follow the field's gradient, and the texture wraps the
122    /// shape as it wraps [`Mesh::sphere`], seen from the middle of the box:
123    /// its middle faces the viewer, its left and right edges meet at the
124    /// back and its top and bottom edges are the poles. A field that changes
125    /// gives a shape that changes: build the mesh again for each new shape.
126    pub fn from_sdf(
127        field: impl Fn(Vec3) -> f32,
128        bounds: (Vec3, Vec3),
129        resolution: u32,
130    ) -> Result<Self, MeshError> {
131        let cells = resolution.max(2) as usize;
132        let samples = Samples::of(&field, bounds, cells);
133        let middle = (bounds.0 + bounds.1) * 0.5;
134        let reach = samples.step.x.min(samples.step.y).min(samples.step.z) * 0.5;
135        let mut net = Net::default();
136        let mut cell_vertices = vec![u32::MAX; cells * cells * cells];
137        for k in 0..cells {
138            for j in 0..cells {
139                for i in 0..cells {
140                    if let Some(point) = samples.cell_point([i, j, k]) {
141                        cell_vertices[(k * cells + j) * cells + i] =
142                            net.vertex(point, gradient(&field, point, reach), middle);
143                    }
144                }
145            }
146        }
147        let cell = |[i, j, k]: [usize; 3]| cell_vertices[(k * cells + j) * cells + i];
148        // Each grid edge the surface crosses joins the four cells around it.
149        for (step, around) in AROUND_EDGES {
150            for k in 0..cells {
151                for j in 0..cells {
152                    for i in 0..cells {
153                        let start = [i, j, k];
154                        let back = |axis: usize| around.iter().any(|offset| offset[axis] > 0);
155                        if (0..3).any(|axis| back(axis) && start[axis] == 0) {
156                            continue;
157                        }
158                        let end = [i + step[0], j + step[1], k + step[2]];
159                        let cells_around =
160                            around.map(|[di, dj, dk]| cell([i - di, j - dj, k - dk]));
161                        net.join(&samples, (start, end), cells_around);
162                    }
163                }
164            }
165        }
166        Self::new(net.positions, net.uvs, Some(net.normals), net.indices)
167    }
168}
169
170/// The vertices and triangles of a surface net as it grows.
171#[derive(Default)]
172struct Net {
173    positions: Vec<[f32; 3]>,
174    normals: Vec<[f32; 3]>,
175    uvs: Vec<[f32; 2]>,
176    indices: Vec<u32>,
177    /// For each vertex, the copy of it whose texture coordinate lies one
178    /// turn on, for the triangles that cross the seam at the back.
179    turned: Vec<u32>,
180}
181
182impl Net {
183    fn vertex(&mut self, point: Vec3, normal: Vec3, middle: Vec3) -> u32 {
184        let index = self.positions.len() as u32;
185        self.positions.push([point.x, point.y, point.z]);
186        self.normals.push([normal.x, normal.y, normal.z]);
187        self.uvs.push(wrapped_uv(point - middle));
188        self.turned.push(u32::MAX);
189        index
190    }
191
192    /// Two triangles over the four cells around the grid edge from `edge.0`
193    /// to `edge.1`, when the surface crosses it.
194    fn join(&mut self, samples: &Samples, edge: ([usize; 3], [usize; 3]), around: [u32; 4]) {
195        let (from, to) = (samples.value(edge.0), samples.value(edge.1));
196        if (from < 0.0) == (to < 0.0) || around.contains(&u32::MAX) {
197            return;
198        }
199        // The quad turns to face the outside, where the field grows.
200        let [a, b, c, d] = if from < 0.0 {
201            around
202        } else {
203            [around[0], around[3], around[2], around[1]]
204        };
205        self.triangle([a, b, c]);
206        self.triangle([a, c, d]);
207    }
208
209    /// A triangle; one that crosses the texture's seam takes the copies of
210    /// its corners on the far side of the seam.
211    fn triangle(&mut self, corners: [u32; 3]) {
212        let us = corners.map(|corner| self.uvs[corner as usize][0]);
213        let crosses = us.iter().copied().fold(f32::NEG_INFINITY, f32::max)
214            - us.iter().copied().fold(f32::INFINITY, f32::min)
215            > 0.5;
216        for (corner, u) in corners.into_iter().zip(us) {
217            let index = if crosses && u < 0.5 {
218                self.turned_copy(corner)
219            } else {
220                corner
221            };
222            self.indices.push(index);
223        }
224    }
225
226    fn turned_copy(&mut self, corner: u32) -> u32 {
227        let at = corner as usize;
228        if self.turned[at] == u32::MAX {
229            self.turned[at] = self.positions.len() as u32;
230            self.positions.push(self.positions[at]);
231            self.normals.push(self.normals[at]);
232            let [u, v] = self.uvs[at];
233            self.uvs.push([u + 1.0, v]);
234            self.turned.push(u32::MAX);
235        }
236        self.turned[at]
237    }
238}
239
240/// The texture coordinate of the point in `direction` from a shape's
241/// middle, as [`Mesh::sphere`] lays its texture.
242fn wrapped_uv(direction: Vec3) -> [f32; 2] {
243    let Some(direction) = direction.normalized() else {
244        return [0.5, 0.5];
245    };
246    [
247        direction.x.atan2(-direction.z) / TAU + 0.5,
248        (-direction.y).clamp(-1.0, 1.0).acos() / PI,
249    ]
250}
251
252/// The direction the field grows fastest at `point`, from steps of `reach`.
253fn gradient(field: &impl Fn(Vec3) -> f32, point: Vec3, reach: f32) -> Vec3 {
254    let along = |axis: Vec3| field(point + axis * reach) - field(point - axis * reach);
255    Vec3::new(
256        along(Vec3::new(1.0, 0.0, 0.0)),
257        along(Vec3::new(0.0, 1.0, 0.0)),
258        along(Vec3::new(0.0, 0.0, 1.0)),
259    )
260    .normalized()
261    .unwrap_or(Vec3::new(0.0, 0.0, -1.0))
262}
cranpose_ui_graphics/space/sdf.rs

cranpose_ui_graphics/space/
sdf.rs
