mesh_to_sdf/
grid.rs

1#[cfg(feature = "serde")]
2use serde::{de::DeserializeOwned, Deserialize, Serialize};
3
4use crate::point::Point;
5
6/// Result of snapping a point to the grid.
7/// If the point is inside the grid, the cell it is within is returned.
8/// If the point is outside the grid, the cell index is the nearest cell.
9#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
10pub enum SnapResult {
11    /// The point is inside the grid.
12    /// Cell index is the cell it is within.
13    Inside([usize; 3]),
14    /// The point is outside the grid
15    /// Cell index is the cell it is the nearest from.
16    Outside([usize; 3]),
17}
18
19/// Helper struct to represent a grid for grid sdf.
20/// A grid is defined by three parameters:
21/// - `first_cell`: the position of the center of the first cell.
22/// - `cell_size`: the size of a cell (i.e. the size of a voxel).
23/// - `cell_count`: the number of cells in each direction (i.e. the number of voxels in each direction).
24///                 Note that if you want to sample x in 0 1 2 .. 10, you need 11 cells in this direction and not 10.
25/// - `cell_size` can be different in each direction and even negative.
26/// - `cell_count` can be different in each direction
27#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord)]
28#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
29#[cfg_attr(feature = "serde", serde(bound = "V: Serialize + DeserializeOwned"))]
30pub struct Grid<V: Point> {
31    /// The center of the first cell.
32    first_cell: V,
33    /// The size of a cell. A cell goes from `center - cell_size / 2` to `center + cell_size / 2`.
34    cell_size: V,
35    /// The number of cells in each direction.
36    cell_count: [usize; 3],
37}
38
39impl<V: Point> Grid<V> {
40    /// Create a new grid.
41    /// - `first_cell` is the center of the first cell.
42    /// - `cell_size` is the size of a cell. A cell goes from `center - cell_size / 2` to `center + cell_size / 2`.
43    pub const fn new(first_cell: V, cell_size: V, cell_count: [usize; 3]) -> Self {
44        Self {
45            first_cell,
46            cell_size,
47            cell_count,
48        }
49    }
50
51    /// Create a new grid from a bounding box.
52    /// - `bbox_min` is the minimum corner of the bounding box.
53    /// - `bbox_max` is the maximum corner of the bounding box.
54    /// - `cell_count` is the number of cells in each direction.
55    ///
56    /// The grid will be centered in the bounding box.
57    /// The size of a cell will be `bounding_box_size / cell_count`.
58    /// The first cell will be at `min_cell + cell_size / 2`.
59    pub fn from_bounding_box(bbox_min: &V, bbox_max: &V, cell_count: [usize; 3]) -> Self {
60        let fcell_count = V::new(
61            cell_count[0] as f32,
62            cell_count[1] as f32,
63            cell_count[2] as f32,
64        );
65        let cell_size = bbox_max.sub(bbox_min).comp_div(&fcell_count);
66        // We add half a cell size to the first cell to center it.
67        let first_cell = bbox_min.add(&cell_size.fmul(0.5));
68
69        Self {
70            first_cell,
71            cell_size,
72            cell_count,
73        }
74    }
75
76    /// Get the center of the first cell.
77    pub const fn get_first_cell(&self) -> V {
78        self.first_cell
79    }
80
81    /// Get the center of the last cell.
82    pub fn get_last_cell(&self) -> V {
83        V::new(
84            self.first_cell.x() + self.cell_count[0] as f32 * self.cell_size.x(),
85            self.first_cell.y() + self.cell_count[1] as f32 * self.cell_size.y(),
86            self.first_cell.z() + self.cell_count[2] as f32 * self.cell_size.z(),
87        )
88    }
89
90    /// Get the size of a cell.
91    pub const fn get_cell_size(&self) -> V {
92        self.cell_size
93    }
94
95    /// Get the number of cells in each direction.
96    pub const fn get_cell_count(&self) -> [usize; 3] {
97        self.cell_count
98    }
99
100    /// Get the total  of cells.
101    pub const fn get_total_cell_count(&self) -> usize {
102        self.cell_count[0] * self.cell_count[1] * self.cell_count[2]
103    }
104
105    /// Get bouding box.
106    ///
107    /// The bounding box is defined by the minimum and maximum corners.
108    /// - The minimum corner is the center of the first cell minus half a cell size.
109    /// - The maximum corner is the center of the last cell plus half a cell size.
110    pub fn get_bounding_box(&self) -> (V, V) {
111        let min = self.first_cell.sub(&self.cell_size.fmul(0.5));
112        let max = V::new(
113            min.x() + self.cell_count[0] as f32 * self.cell_size.x(),
114            min.y() + self.cell_count[1] as f32 * self.cell_size.y(),
115            min.z() + self.cell_count[2] as f32 * self.cell_size.z(),
116        );
117
118        (min, max)
119    }
120
121    /// Get the index of a cell in a grid.
122    pub const fn get_cell_idx(&self, cell: &[usize; 3]) -> usize {
123        cell[2] + cell[1] * self.cell_count[2] + cell[0] * self.cell_count[1] * self.cell_count[2]
124    }
125
126    /// Get the integer coordinates of a cell index in a grid.
127    pub const fn get_cell_integer_coordinates(&self, cell_idx: usize) -> [usize; 3] {
128        let z = cell_idx % self.cell_count[2];
129        let y = (cell_idx / self.cell_count[2]) % self.cell_count[1];
130        let x = cell_idx / (self.cell_count[1] * self.cell_count[2]);
131        [x, y, z]
132    }
133
134    /// Get the position of a cell in a grid.
135    pub fn get_cell_center(&self, cell: &[usize; 3]) -> V {
136        V::new(
137            self.first_cell.x() + cell[0] as f32 * self.cell_size.x(),
138            self.first_cell.y() + cell[1] as f32 * self.cell_size.y(),
139            self.first_cell.z() + cell[2] as f32 * self.cell_size.z(),
140        )
141    }
142
143    /// Snap a point to the grid.
144    /// Returns a `SnapResult` specifying if the point is inside or outside the grid.
145    pub fn snap_point_to_grid(&self, point: &V) -> SnapResult {
146        let cell = point
147            .sub(&self.get_bounding_box().0)
148            .comp_div(&self.cell_size);
149
150        let cell = [
151            cell.x().floor() as isize,
152            cell.y().floor() as isize,
153            cell.z().floor() as isize,
154        ];
155
156        #[expect(clippy::cast_possible_wrap)]
157        let ires = [
158            cell[0].clamp(0, self.cell_count[0] as isize - 1),
159            cell[1].clamp(0, self.cell_count[1] as isize - 1),
160            cell[2].clamp(0, self.cell_count[2] as isize - 1),
161        ];
162
163        let res = [ires[0] as usize, ires[1] as usize, ires[2] as usize];
164
165        if ires == cell {
166            SnapResult::Inside(res)
167        } else {
168            SnapResult::Outside(res)
169        }
170    }
171
172    // TODO: provide functions to get distance from any point with interpolation
173}
174
175#[cfg(test)]
176mod tests {
177    use super::*;
178
179    #[test]
180    fn test_new() {
181        let first_cell = [0.1, 0.2, 0.3];
182        let cell_size = [1.1, 1.2, 1.3];
183        let cell_count = [11, 12, 13];
184        let grid = Grid::new(first_cell, cell_size, cell_count);
185        assert_eq!(grid.first_cell, [0.1, 0.2, 0.3]);
186        assert_eq!(grid.cell_size, [1.1, 1.2, 1.3]);
187        assert_eq!(grid.cell_count, [11, 12, 13]);
188    }
189
190    #[test]
191    fn test_first_last_cells() {
192        let first_cell = [0.0, 1.0, 2.0];
193        let cell_size = [1.0, 2.0, 3.0];
194        let cell_count = [10, 20, 30];
195        let grid = Grid::new(first_cell, cell_size, cell_count);
196        assert_eq!(grid.get_first_cell(), [0.0, 1.0, 2.0]);
197        assert_eq!(grid.get_last_cell(), [10.0, 41.0, 92.0]);
198    }
199
200    #[test]
201    fn test_from_bounding_box() {
202        let min_cell = [-1.0, 0.0, 1.0];
203        let max_cell = [0.0, 2.0, 5.0];
204        let cell_count = [2, 2, 2];
205        let grid = Grid::from_bounding_box(&min_cell, &max_cell, cell_count);
206        assert_eq!(grid.first_cell, [-0.75, 0.5, 2.]);
207        assert_eq!(grid.cell_size, [0.5, 1., 2.]);
208        assert_eq!(grid.cell_count, [2, 2, 2]);
209
210        assert_eq!(grid.get_bounding_box(), (min_cell, max_cell));
211    }
212
213    #[test]
214    fn test_snap_point_to_grid() {
215        let min_cell = [0.0, 0.0, 0.0];
216        let max_cell = [1.0, 1.0, 1.0];
217        let cell_count = [2, 2, 2];
218        let grid = Grid::from_bounding_box(&min_cell, &max_cell, cell_count);
219
220        assert_eq!(
221            grid.snap_point_to_grid(&[0.4, 0.8, 0.1]),
222            SnapResult::Inside([0, 1, 0])
223        );
224
225        assert_eq!(
226            grid.snap_point_to_grid(&[-0.5, 0.8, 0.8]),
227            SnapResult::Outside([0, 1, 1])
228        );
229
230        assert_eq!(
231            grid.snap_point_to_grid(&[0.8, 0.8, 0.8]),
232            SnapResult::Inside([1, 1, 1])
233        );
234
235        assert_eq!(
236            grid.snap_point_to_grid(&[0.8, 1.5, 0.8]),
237            SnapResult::Outside([1, 1, 1])
238        );
239    }
240
241    #[test]
242    fn test_get_cell_idx() {
243        let min_cell = [0.0, 0.0, 0.0];
244        let max_cell = [1.0, 1.0, 1.0];
245        let cell_count = [2, 3, 4];
246        let grid = Grid::from_bounding_box(&min_cell, &max_cell, cell_count);
247
248        assert_eq!(grid.get_cell_idx(&[0, 0, 0]), 0);
249        assert_eq!(grid.get_cell_idx(&[0, 0, 1]), 1);
250        assert_eq!(grid.get_cell_idx(&[0, 1, 0]), 4);
251        assert_eq!(grid.get_cell_idx(&[0, 1, 1]), 5);
252        assert_eq!(grid.get_cell_idx(&[1, 0, 0]), 12);
253        assert_eq!(grid.get_cell_idx(&[1, 0, 1]), 13);
254        assert_eq!(grid.get_cell_idx(&[1, 1, 0]), 16);
255        assert_eq!(grid.get_cell_idx(&[1, 1, 1]), 17);
256    }
257
258    #[test]
259    fn test_get_cell_integer_coordinates() {
260        let min_cell = [0.0, 0.0, 0.0];
261        let max_cell = [1.0, 1.0, 1.0];
262        let cell_count = [5, 10, 15];
263        let grid = Grid::from_bounding_box(&min_cell, &max_cell, cell_count);
264
265        for i in 0..1000 {
266            let cell = grid.get_cell_integer_coordinates(i);
267            let idx = grid.get_cell_idx(&cell);
268            assert_eq!(i, idx);
269        }
270
271        for x in 0..5 {
272            for y in 0..10 {
273                for z in 0..15 {
274                    let i = grid.get_cell_idx(&[x, y, z]);
275                    let cell = grid.get_cell_integer_coordinates(i);
276                    assert_eq!([x, y, z], cell);
277                }
278            }
279        }
280    }
281
282    #[test]
283    fn test_get_cell_center() {
284        let min_cell = [0.0, 0.0, 0.0];
285        let max_cell = [1.0, 1.0, 1.0];
286        let cell_count = [2, 2, 2];
287        let grid = Grid::from_bounding_box(&min_cell, &max_cell, cell_count);
288
289        assert_eq!(grid.get_cell_center(&[0, 0, 0]), [0.25, 0.25, 0.25]);
290        assert_eq!(grid.get_cell_center(&[0, 0, 1]), [0.25, 0.25, 0.75]);
291        assert_eq!(grid.get_cell_center(&[0, 1, 0]), [0.25, 0.75, 0.25]);
292        assert_eq!(grid.get_cell_center(&[0, 1, 1]), [0.25, 0.75, 0.75]);
293        assert_eq!(grid.get_cell_center(&[1, 0, 0]), [0.75, 0.25, 0.25]);
294        assert_eq!(grid.get_cell_center(&[1, 0, 1]), [0.75, 0.25, 0.75]);
295        assert_eq!(grid.get_cell_center(&[1, 1, 0]), [0.75, 0.75, 0.25]);
296        assert_eq!(grid.get_cell_center(&[1, 1, 1]), [0.75, 0.75, 0.75]);
297    }
298}
mesh_to_sdf/grid.rs

mesh_to_sdf/
grid.rs
