euv_engine/spatial/impl.rs
1use super::*;
2
3/// Implements construction, insertion, and querying for `SpatialHashGrid2D`.
4impl SpatialHashGrid2D {
5 /// Creates a new 2D spatial hash grid with the given cell size.
6 ///
7 /// # Arguments
8 ///
9 /// - `f64` - The world-space size of each grid cell.
10 ///
11 /// # Returns
12 ///
13 /// - `SpatialHashGrid2D` - The new grid.
14 pub fn create(cell_size: f64) -> SpatialHashGrid2D {
15 let safe_size: f64 = cell_size.max(EPSILON);
16 let mut grid: SpatialHashGrid2D = SpatialHashGrid2D::new(safe_size);
17 grid.set_inverse_cell_size(1.0 / safe_size);
18 grid
19 }
20
21 /// Creates a new 2D spatial hash grid with the default cell size.
22 ///
23 /// # Returns
24 ///
25 /// - `SpatialHashGrid2D` - The new grid.
26 pub fn with_default_size() -> SpatialHashGrid2D {
27 Self::create(SPATIAL_DEFAULT_CELL_SIZE_2D)
28 }
29
30 /// Inserts a body index into all cells overlapping the given bounding box.
31 ///
32 /// # Arguments
33 ///
34 /// - `usize` - The body index to insert.
35 /// - `Vector2D` - The minimum corner of the bounding box.
36 /// - `Vector2D` - The maximum corner of the bounding box.
37 pub fn insert(&mut self, index: usize, min: Vector2D, max: Vector2D) {
38 let inv: f64 = self.get_inverse_cell_size();
39 let min_col: i32 = (min.get_x() * inv).floor() as i32;
40 let min_row: i32 = (min.get_y() * inv).floor() as i32;
41 let max_col: i32 = (max.get_x() * inv).floor() as i32;
42 let max_row: i32 = (max.get_y() * inv).floor() as i32;
43 for col in min_col..=max_col {
44 for row in min_row..=max_row {
45 self.get_mut_cells()
46 .entry((col, row))
47 .or_default()
48 .push(index);
49 }
50 }
51 }
52
53 /// Returns all candidate body indices whose cells overlap the given bounding box.
54 ///
55 /// Deduplicates indices so each candidate appears at most once.
56 ///
57 /// # Arguments
58 ///
59 /// - `Vector2D` - The minimum corner of the query box.
60 /// - `Vector2D` - The maximum corner of the query box.
61 ///
62 /// # Returns
63 ///
64 /// - `Vec<usize>` - The list of candidate body indices.
65 pub fn query(&self, min: Vector2D, max: Vector2D) -> Vec<usize> {
66 let inv: f64 = self.get_inverse_cell_size();
67 let min_col: i32 = (min.get_x() * inv).floor() as i32;
68 let min_row: i32 = (min.get_y() * inv).floor() as i32;
69 let max_col: i32 = (max.get_x() * inv).floor() as i32;
70 let max_row: i32 = (max.get_y() * inv).floor() as i32;
71 let mut seen: HashSet<usize> = HashSet::new();
72 let mut result: Vec<usize> = Vec::new();
73 for col in min_col..=max_col {
74 for row in min_row..=max_row {
75 if let Some(entries) = self.get_cells().get(&(col, row)) {
76 for index in entries {
77 if seen.insert(*index) {
78 result.push(*index);
79 }
80 }
81 }
82 }
83 }
84 result
85 }
86
87 /// Removes all entries from the grid, preparing it for a fresh insertion pass.
88 pub fn clear(&mut self) {
89 self.get_mut_cells().clear();
90 }
91
92 /// Appends all candidate body indices overlapping the query box into `out`,
93 /// deduplicating via the caller-provided `seen` set.
94 ///
95 /// Both `out` and `seen` are cleared first, so the caller can reuse the same
96 /// buffers across all queries in a step without any per-query allocation.
97 ///
98 /// # Arguments
99 ///
100 /// - `Vector2D` - The minimum corner of the query box.
101 /// - `Vector2D` - The maximum corner of the query box.
102 /// - `&mut Vec<usize>` - The output buffer, cleared then filled with candidates.
103 /// - `&mut HashSet<usize>` - The dedup scratch set, cleared then reused.
104 pub fn query_into(
105 &self,
106 min: Vector2D,
107 max: Vector2D,
108 out: &mut Vec<usize>,
109 seen: &mut HashSet<usize>,
110 ) {
111 out.clear();
112 seen.clear();
113 let inv: f64 = self.get_inverse_cell_size();
114 let min_col: i32 = (min.get_x() * inv).floor() as i32;
115 let min_row: i32 = (min.get_y() * inv).floor() as i32;
116 let max_col: i32 = (max.get_x() * inv).floor() as i32;
117 let max_row: i32 = (max.get_y() * inv).floor() as i32;
118 for col in min_col..=max_col {
119 for row in min_row..=max_row {
120 if let Some(entries) = self.get_cells().get(&(col, row)) {
121 for index in entries {
122 if seen.insert(*index) {
123 out.push(*index);
124 }
125 }
126 }
127 }
128 }
129 }
130}
131
132/// Implements construction, insertion, and querying for `SpatialHashGrid3D`.
133impl SpatialHashGrid3D {
134 /// Creates a new 3D spatial hash grid with the given cell size.
135 ///
136 /// # Arguments
137 ///
138 /// - `f64` - The world-space size of each grid cell.
139 ///
140 /// # Returns
141 ///
142 /// - `SpatialHashGrid3D` - The new grid.
143 pub fn create(cell_size: f64) -> SpatialHashGrid3D {
144 let safe_size: f64 = cell_size.max(EPSILON);
145 let mut grid: SpatialHashGrid3D = SpatialHashGrid3D::new(safe_size);
146 grid.set_inverse_cell_size(1.0 / safe_size);
147 grid
148 }
149
150 /// Creates a new 3D spatial hash grid with the default cell size.
151 ///
152 /// # Returns
153 ///
154 /// - `SpatialHashGrid3D` - The new grid.
155 pub fn with_default_size() -> SpatialHashGrid3D {
156 Self::create(SPATIAL_DEFAULT_CELL_SIZE_3D)
157 }
158
159 /// Inserts a body index into all cells overlapping the given 3D bounding box.
160 ///
161 /// # Arguments
162 ///
163 /// - `usize` - The body index to insert.
164 /// - `Vector3D` - The minimum corner of the bounding box.
165 /// - `Vector3D` - The maximum corner of the bounding box.
166 pub fn insert(&mut self, index: usize, min: Vector3D, max: Vector3D) {
167 let inv: f64 = self.get_inverse_cell_size();
168 let min_col: i32 = (min.get_x() * inv).floor() as i32;
169 let min_row: i32 = (min.get_y() * inv).floor() as i32;
170 let min_layer: i32 = (min.get_z() * inv).floor() as i32;
171 let max_col: i32 = (max.get_x() * inv).floor() as i32;
172 let max_row: i32 = (max.get_y() * inv).floor() as i32;
173 let max_layer: i32 = (max.get_z() * inv).floor() as i32;
174 for col in min_col..=max_col {
175 for row in min_row..=max_row {
176 for layer in min_layer..=max_layer {
177 self.get_mut_cells()
178 .entry((col, row, layer))
179 .or_default()
180 .push(index);
181 }
182 }
183 }
184 }
185
186 /// Returns all candidate body indices whose cells overlap the given 3D bounding box.
187 ///
188 /// Deduplicates indices so each candidate appears at most once.
189 ///
190 /// # Arguments
191 ///
192 /// - `Vector3D` - The minimum corner of the query box.
193 /// - `Vector3D` - The maximum corner of the query box.
194 ///
195 /// # Returns
196 ///
197 /// - `Vec<usize>` - The list of candidate body indices.
198 pub fn query(&self, min: Vector3D, max: Vector3D) -> Vec<usize> {
199 let inv: f64 = self.get_inverse_cell_size();
200 let min_col: i32 = (min.get_x() * inv).floor() as i32;
201 let min_row: i32 = (min.get_y() * inv).floor() as i32;
202 let min_layer: i32 = (min.get_z() * inv).floor() as i32;
203 let max_col: i32 = (max.get_x() * inv).floor() as i32;
204 let max_row: i32 = (max.get_y() * inv).floor() as i32;
205 let max_layer: i32 = (max.get_z() * inv).floor() as i32;
206 let mut seen: HashSet<usize> = HashSet::new();
207 let mut result: Vec<usize> = Vec::new();
208 for col in min_col..=max_col {
209 for row in min_row..=max_row {
210 for layer in min_layer..=max_layer {
211 if let Some(entries) = self.get_cells().get(&(col, row, layer)) {
212 for index in entries {
213 if seen.insert(*index) {
214 result.push(*index);
215 }
216 }
217 }
218 }
219 }
220 }
221 result
222 }
223
224 /// Removes all entries from the grid, preparing it for a fresh insertion pass.
225 pub fn clear(&mut self) {
226 self.get_mut_cells().clear();
227 }
228
229 /// Appends all candidate body indices overlapping the query box into `out`,
230 /// deduplicating via the caller-provided `seen` set.
231 ///
232 /// Both `out` and `seen` are cleared first, so the caller can reuse the same
233 /// buffers across all queries in a step without any per-query allocation.
234 ///
235 /// # Arguments
236 ///
237 /// - `Vector3D` - The minimum corner of the query box.
238 /// - `Vector3D` - The maximum corner of the query box.
239 /// - `&mut Vec<usize>` - The output buffer, cleared then filled with candidates.
240 /// - `&mut HashSet<usize>` - The dedup scratch set, cleared then reused.
241 pub fn query_into(
242 &self,
243 min: Vector3D,
244 max: Vector3D,
245 out: &mut Vec<usize>,
246 seen: &mut HashSet<usize>,
247 ) {
248 out.clear();
249 seen.clear();
250 let inv: f64 = self.get_inverse_cell_size();
251 let min_col: i32 = (min.get_x() * inv).floor() as i32;
252 let min_row: i32 = (min.get_y() * inv).floor() as i32;
253 let min_layer: i32 = (min.get_z() * inv).floor() as i32;
254 let max_col: i32 = (max.get_x() * inv).floor() as i32;
255 let max_row: i32 = (max.get_y() * inv).floor() as i32;
256 let max_layer: i32 = (max.get_z() * inv).floor() as i32;
257 for col in min_col..=max_col {
258 for row in min_row..=max_row {
259 for layer in min_layer..=max_layer {
260 if let Some(entries) = self.get_cells().get(&(col, row, layer)) {
261 for index in entries {
262 if seen.insert(*index) {
263 out.push(*index);
264 }
265 }
266 }
267 }
268 }
269 }
270 }
271}
272impl Default for SpatialHashGrid2D {
273 fn default() -> SpatialHashGrid2D {
274 SpatialHashGrid2D::with_default_size()
275 }
276}
277
278/// Implements `Default` for `SpatialHashGrid3D` with the default cell size.
279impl Default for SpatialHashGrid3D {
280 fn default() -> SpatialHashGrid3D {
281 SpatialHashGrid3D::with_default_size()
282 }
283}