parry3d/transformation/voxelization/voxelized_volume.rs
1// Rust port, with modifications, of https://github.com/kmammou/v-hacd/blob/master/src/VHACD_Lib/src/vhacdVolume.cpp
2// By Khaled Mamou
3//
4// # License of the original C++ code:
5// > Copyright (c) 2011 Khaled Mamou (kmamou at gmail dot com)
6// > All rights reserved.
7// >
8// >
9// > Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
10// >
11// > 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
12// >
13// > 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
14// >
15// > 3. The names of the contributors may not be used to endorse or promote products derived from this software without specific prior written permission.
16// >
17// > THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
18
19use crate::bounding_volume::Aabb;
20use crate::math::{Point, Real, Vector, DIM};
21use crate::query;
22use crate::transformation::voxelization::{Voxel, VoxelSet};
23use alloc::sync::Arc;
24use alloc::vec::Vec;
25#[cfg(not(feature = "std"))]
26use na::ComplexField;
27
28/// Controls how the voxelization determines which voxel needs
29/// to be considered empty, and which ones will be considered full.
30#[derive(Copy, Clone, Debug, PartialEq, Eq)]
31pub enum FillMode {
32 /// Only consider full the voxels intersecting the surface of the
33 /// shape being voxelized.
34 SurfaceOnly,
35 /// Use a flood-fill technique to consider fill the voxels intersecting
36 /// the surface of the shape being voxelized, as well as all the voxels
37 /// bounded of them.
38 FloodFill {
39 /// Detects holes inside of a solid contour.
40 detect_cavities: bool,
41 /// Attempts to properly handle self-intersections.
42 #[cfg(feature = "dim2")]
43 detect_self_intersections: bool,
44 },
45 // RaycastFill
46}
47
48impl Default for FillMode {
49 fn default() -> Self {
50 Self::FloodFill {
51 detect_cavities: false,
52 #[cfg(feature = "dim2")]
53 detect_self_intersections: false,
54 }
55 }
56}
57
58impl FillMode {
59 #[cfg(feature = "dim2")]
60 pub(crate) fn detect_cavities(self) -> bool {
61 match self {
62 FillMode::FloodFill {
63 detect_cavities, ..
64 } => detect_cavities,
65 _ => false,
66 }
67 }
68
69 #[cfg(feature = "dim2")]
70 pub(crate) fn detect_self_intersections(self) -> bool {
71 match self {
72 FillMode::FloodFill {
73 detect_self_intersections,
74 ..
75 } => detect_self_intersections,
76 _ => false,
77 }
78 }
79
80 #[cfg(feature = "dim3")]
81 pub(crate) fn detect_self_intersections(self) -> bool {
82 false
83 }
84}
85
86/// The values of a voxel.
87///
88/// Most values are only intermediate value set during the
89/// voxelization process. The only values output after the
90/// voxelization is complete are `PrimitiveOutsideSurface`,
91/// `PrimitiveInsideSurface`, and `PrimitiveOnSurface`.
92#[derive(Copy, Clone, Debug, PartialEq, Eq)]
93pub enum VoxelValue {
94 /// Intermediate value, should be ignored by end-user code.
95 PrimitiveUndefined,
96 /// Intermediate value, should be ignored by end-user code.
97 PrimitiveOutsideSurfaceToWalk,
98 /// Intermediate value, should be ignored by end-user code.
99 PrimitiveInsideSurfaceToWalk,
100 /// Intermediate value, should be ignored by end-user code.
101 PrimitiveOnSurfaceNoWalk,
102 /// Intermediate value, should be ignored by end-user code.
103 PrimitiveOnSurfaceToWalk1,
104 /// Intermediate value, should be ignored by end-user code.
105 PrimitiveOnSurfaceToWalk2,
106 /// A voxel that is outside of the voxelized shape.
107 PrimitiveOutsideSurface,
108 /// A voxel that is on the interior of the voxelized shape.
109 PrimitiveInsideSurface,
110 /// Voxel that intersects the surface of the voxelized shape.
111 PrimitiveOnSurface,
112}
113
114#[derive(Copy, Clone, Debug, PartialEq, Eq)]
115struct VoxelState {
116 #[cfg(feature = "dim2")]
117 multiplicity: u32,
118 num_primitive_intersections: u32,
119}
120
121/// A cubic volume filled with voxels.
122pub struct VoxelizedVolume {
123 origin: Point<Real>,
124 scale: Real,
125 resolution: [u32; DIM],
126 values: Vec<VoxelValue>,
127 data: Vec<VoxelState>,
128 primitive_intersections: Vec<(u32, u32)>,
129}
130
131impl VoxelizedVolume {
132 /// Voxelizes the given shape described by its boundary:
133 /// a triangle mesh (in 3D) or polyline (in 2D).
134 ///
135 /// # Parameters
136 /// * `points` - The vertex buffer of the boundary of the shape to voxelize.
137 /// * `indices` - The index buffer of the boundary of the shape to voxelize.
138 /// * `resolution` - Controls the number of subdivision done along each axis. This number
139 /// is the number of subdivisions along the axis where the input shape has the largest extent.
140 /// The other dimensions will have a different automatically-determined resolution (in order to
141 /// keep the voxels cubic).
142 /// * `fill_mode` - Controls what is being voxelized.
143 /// * `keep_voxel_to_primitives_map` - If set to `true` a map between the voxels
144 /// and the primitives (3D triangles or 2D segments) it intersects will be computed.
145 pub fn with_voxel_size(
146 points: &[Point<Real>],
147 indices: &[[u32; DIM]],
148 voxel_size: Real,
149 fill_mode: FillMode,
150 keep_voxel_to_primitives_map: bool,
151 ) -> Self {
152 let mut result = VoxelizedVolume {
153 resolution: [0; DIM],
154 origin: Point::origin(),
155 scale: voxel_size,
156 values: Vec::new(),
157 data: Vec::new(),
158 primitive_intersections: Vec::new(),
159 };
160
161 if points.is_empty() {
162 return result;
163 }
164
165 let aabb = crate::bounding_volume::details::local_point_cloud_aabb_ref(points);
166 result.origin = aabb.mins;
167 result.resolution = (aabb.extents() / voxel_size)
168 .map(|x| (x.ceil() as u32).max(2) + 1)
169 .into();
170
171 result.do_voxelize(points, indices, fill_mode, keep_voxel_to_primitives_map);
172 result
173 }
174
175 /// Voxelizes the given shape described by its boundary:
176 /// a triangle mesh (in 3D) or polyline (in 2D).
177 ///
178 /// # Parameters
179 /// * `points` - The vertex buffer of the boundary of the shape to voxelize.
180 /// * `indices` - The index buffer of the boundary of the shape to voxelize.
181 /// * `resolution` - Controls the number of subdivision done along each axis. This number
182 /// is the number of subdivisions along the axis where the input shape has the largest extent.
183 /// The other dimensions will have a different automatically-determined resolution (in order to
184 /// keep the voxels cubic).
185 /// * `fill_mode` - Controls what is being voxelized.
186 /// * `keep_voxel_to_primitives_map` - If set to `true` a map between the voxels
187 /// and the primitives (3D triangles or 2D segments) it intersects will be computed.
188 pub fn voxelize(
189 points: &[Point<Real>],
190 indices: &[[u32; DIM]],
191 resolution: u32,
192 fill_mode: FillMode,
193 keep_voxel_to_primitives_map: bool,
194 ) -> Self {
195 let mut result = VoxelizedVolume {
196 resolution: [0; DIM],
197 origin: Point::origin(),
198 scale: 1.0,
199 values: Vec::new(),
200 data: Vec::new(),
201 primitive_intersections: Vec::new(),
202 };
203
204 if points.is_empty() {
205 return result;
206 }
207
208 let aabb = crate::bounding_volume::details::local_point_cloud_aabb_ref(points);
209 result.origin = aabb.mins;
210
211 let d = aabb.maxs - aabb.mins;
212 let r;
213
214 #[cfg(feature = "dim2")]
215 if d[0] > d[1] {
216 r = d[0];
217 result.resolution[0] = resolution;
218 result.resolution[1] = 2 + (resolution as Real * d[1] / d[0]) as u32;
219 } else {
220 r = d[1];
221 result.resolution[1] = resolution;
222 result.resolution[0] = 2 + (resolution as Real * d[0] / d[1]) as u32;
223 }
224
225 #[cfg(feature = "dim3")]
226 if d[0] >= d[1] && d[0] >= d[2] {
227 r = d[0];
228 result.resolution[0] = resolution;
229 result.resolution[1] = 2 + (resolution as Real * d[1] / d[0]) as u32;
230 result.resolution[2] = 2 + (resolution as Real * d[2] / d[0]) as u32;
231 } else if d[1] >= d[0] && d[1] >= d[2] {
232 r = d[1];
233 result.resolution[1] = resolution;
234 result.resolution[0] = 2 + (resolution as Real * d[0] / d[1]) as u32;
235 result.resolution[2] = 2 + (resolution as Real * d[2] / d[1]) as u32;
236 } else {
237 r = d[2];
238 result.resolution[2] = resolution;
239 result.resolution[0] = 2 + (resolution as Real * d[0] / d[2]) as u32;
240 result.resolution[1] = 2 + (resolution as Real * d[1] / d[2]) as u32;
241 }
242
243 result.scale = r / (resolution as Real - 1.0);
244 result.do_voxelize(points, indices, fill_mode, keep_voxel_to_primitives_map);
245 result
246 }
247
248 fn do_voxelize(
249 &mut self,
250 points: &[Point<Real>],
251 indices: &[[u32; DIM]],
252 fill_mode: FillMode,
253 keep_voxel_to_primitives_map: bool,
254 ) {
255 let inv_scale = 1.0 / self.scale;
256 self.allocate();
257
258 let mut tri_pts = [Point::origin(); DIM];
259 let box_half_size = Vector::repeat(0.5);
260 let mut ijk0 = Vector::repeat(0u32);
261 let mut ijk1 = Vector::repeat(0u32);
262
263 let detect_self_intersections = fill_mode.detect_self_intersections();
264 #[cfg(feature = "dim2")]
265 let lock_high_multiplicities =
266 fill_mode.detect_cavities() && fill_mode.detect_self_intersections();
267
268 for (tri_id, tri) in indices.iter().enumerate() {
269 // Find the range of voxels potentially intersecting the triangle.
270 for c in 0..DIM {
271 let pt = points[tri[c] as usize];
272 tri_pts[c] = (pt - self.origin.coords) * inv_scale;
273
274 let i = (tri_pts[c].x + 0.5) as u32;
275 let j = (tri_pts[c].y + 0.5) as u32;
276 #[cfg(feature = "dim3")]
277 let k = (tri_pts[c].z + 0.5) as u32;
278
279 assert!(i < self.resolution[0] && j < self.resolution[1]);
280 #[cfg(feature = "dim3")]
281 assert!(k < self.resolution[2]);
282
283 #[cfg(feature = "dim2")]
284 let ijk = Vector::new(i, j);
285 #[cfg(feature = "dim3")]
286 let ijk = Vector::new(i, j, k);
287
288 if c == 0 {
289 ijk0 = ijk;
290 ijk1 = ijk;
291 } else {
292 ijk0 = ijk0.inf(&ijk);
293 ijk1 = ijk1.sup(&ijk);
294 }
295 }
296
297 ijk0.apply(|e| *e = e.saturating_sub(1));
298 ijk1 = ijk1
299 .map(|e| e + 1)
300 .inf(&Point::from(self.resolution).coords);
301
302 #[cfg(feature = "dim2")]
303 let range_k = 0..1;
304 #[cfg(feature = "dim3")]
305 let range_k = ijk0.z..ijk1.z;
306
307 // Determine exactly what voxel intersect the triangle.
308 for i in ijk0.x..ijk1.x {
309 for j in ijk0.y..ijk1.y {
310 for k in range_k.clone() {
311 #[cfg(feature = "dim2")]
312 let pt = Point::new(i as Real, j as Real);
313 #[cfg(feature = "dim3")]
314 let pt = Point::new(i as Real, j as Real, k as Real);
315
316 let id = self.voxel_index(i, j, k);
317 let value = &mut self.values[id as usize];
318 let data = &mut self.data[id as usize];
319
320 if detect_self_intersections
321 || keep_voxel_to_primitives_map
322 || *value == VoxelValue::PrimitiveUndefined
323 {
324 let aabb = Aabb::from_half_extents(pt, box_half_size);
325
326 #[cfg(feature = "dim2")]
327 if !detect_self_intersections {
328 let segment = crate::shape::Segment::from(tri_pts);
329 let intersect =
330 query::details::intersection_test_aabb_segment(&aabb, &segment);
331
332 if intersect {
333 if keep_voxel_to_primitives_map {
334 data.num_primitive_intersections += 1;
335 self.primitive_intersections.push((id, tri_id as u32));
336 }
337
338 *value = VoxelValue::PrimitiveOnSurface;
339 }
340 } else if let Some(params) =
341 aabb.clip_line_parameters(&tri_pts[0], &(tri_pts[1] - tri_pts[0]))
342 {
343 let eps = 0.0; // -1.0e-6;
344
345 assert!(params.0 <= params.1);
346 if params.0 > 1.0 + eps || params.1 < 0.0 - eps {
347 continue;
348 }
349
350 if keep_voxel_to_primitives_map {
351 data.num_primitive_intersections += 1;
352 self.primitive_intersections.push((id, tri_id as u32));
353 }
354
355 if data.multiplicity > 4 && lock_high_multiplicities {
356 *value = VoxelValue::PrimitiveOnSurfaceNoWalk;
357 } else {
358 *value = VoxelValue::PrimitiveOnSurface;
359 }
360 };
361
362 #[cfg(feature = "dim3")]
363 {
364 let triangle = crate::shape::Triangle::from(tri_pts);
365 let intersect = query::details::intersection_test_aabb_triangle(
366 &aabb, &triangle,
367 );
368
369 if intersect {
370 *value = VoxelValue::PrimitiveOnSurface;
371
372 if keep_voxel_to_primitives_map {
373 data.num_primitive_intersections += 1;
374 self.primitive_intersections.push((id, tri_id as u32));
375 }
376 }
377 };
378 }
379 }
380 }
381 }
382 }
383
384 match fill_mode {
385 FillMode::SurfaceOnly => {
386 for value in &mut self.values {
387 if *value != VoxelValue::PrimitiveOnSurface {
388 *value = VoxelValue::PrimitiveOutsideSurface
389 }
390 }
391 }
392 FillMode::FloodFill {
393 detect_cavities, ..
394 } => {
395 #[cfg(feature = "dim2")]
396 {
397 self.mark_outside_surface(0, 0, self.resolution[0], 1);
398 self.mark_outside_surface(
399 0,
400 self.resolution[1] - 1,
401 self.resolution[0],
402 self.resolution[1],
403 );
404 self.mark_outside_surface(0, 0, 1, self.resolution[1]);
405 self.mark_outside_surface(
406 self.resolution[0] - 1,
407 0,
408 self.resolution[0],
409 self.resolution[1],
410 );
411 }
412
413 #[cfg(feature = "dim3")]
414 {
415 self.mark_outside_surface(0, 0, 0, self.resolution[0], self.resolution[1], 1);
416 self.mark_outside_surface(
417 0,
418 0,
419 self.resolution[2] - 1,
420 self.resolution[0],
421 self.resolution[1],
422 self.resolution[2],
423 );
424 self.mark_outside_surface(0, 0, 0, self.resolution[0], 1, self.resolution[2]);
425 self.mark_outside_surface(
426 0,
427 self.resolution[1] - 1,
428 0,
429 self.resolution[0],
430 self.resolution[1],
431 self.resolution[2],
432 );
433 self.mark_outside_surface(0, 0, 0, 1, self.resolution[1], self.resolution[2]);
434 self.mark_outside_surface(
435 self.resolution[0] - 1,
436 0,
437 0,
438 self.resolution[0],
439 self.resolution[1],
440 self.resolution[2],
441 );
442 }
443
444 if detect_cavities {
445 let _ = self.propagate_values(
446 VoxelValue::PrimitiveOutsideSurfaceToWalk,
447 VoxelValue::PrimitiveOutsideSurface,
448 None,
449 VoxelValue::PrimitiveOnSurfaceToWalk1,
450 );
451
452 loop {
453 if !self.propagate_values(
454 VoxelValue::PrimitiveInsideSurfaceToWalk,
455 VoxelValue::PrimitiveInsideSurface,
456 Some(VoxelValue::PrimitiveOnSurfaceToWalk1),
457 VoxelValue::PrimitiveOnSurfaceToWalk2,
458 ) {
459 break;
460 }
461
462 if !self.propagate_values(
463 VoxelValue::PrimitiveOutsideSurfaceToWalk,
464 VoxelValue::PrimitiveOutsideSurface,
465 Some(VoxelValue::PrimitiveOnSurfaceToWalk2),
466 VoxelValue::PrimitiveOnSurfaceToWalk1,
467 ) {
468 break;
469 }
470 }
471
472 for voxel in &mut self.values {
473 if *voxel == VoxelValue::PrimitiveOnSurfaceToWalk1
474 || *voxel == VoxelValue::PrimitiveOnSurfaceToWalk2
475 || *voxel == VoxelValue::PrimitiveOnSurfaceNoWalk
476 {
477 *voxel = VoxelValue::PrimitiveOnSurface;
478 }
479 }
480 } else {
481 let _ = self.propagate_values(
482 VoxelValue::PrimitiveOutsideSurfaceToWalk,
483 VoxelValue::PrimitiveOutsideSurface,
484 None,
485 VoxelValue::PrimitiveOnSurface,
486 );
487
488 self.replace_value(
489 VoxelValue::PrimitiveUndefined,
490 VoxelValue::PrimitiveInsideSurface,
491 );
492 }
493 }
494 }
495 }
496
497 /// The number of voxel subdivisions along each coordinate axis.
498 pub fn resolution(&self) -> [u32; DIM] {
499 self.resolution
500 }
501
502 /// The scale factor that needs to be applied to the voxels of `self`
503 /// in order to give them the size matching the original model's size.
504 pub fn scale(&self) -> Real {
505 self.scale
506 }
507
508 fn allocate(&mut self) {
509 #[cfg(feature = "dim2")]
510 let len = self.resolution[0] * self.resolution[1];
511 #[cfg(feature = "dim3")]
512 let len = self.resolution[0] * self.resolution[1] * self.resolution[2];
513 self.values
514 .resize(len as usize, VoxelValue::PrimitiveUndefined);
515 self.data.resize(
516 len as usize,
517 VoxelState {
518 #[cfg(feature = "dim2")]
519 multiplicity: 0,
520 num_primitive_intersections: 0,
521 },
522 );
523 }
524
525 fn voxel_index(&self, i: u32, j: u32, _k: u32) -> u32 {
526 #[cfg(feature = "dim2")]
527 return i + j * self.resolution[0];
528 #[cfg(feature = "dim3")]
529 return i + j * self.resolution[0] + _k * self.resolution[0] * self.resolution[1];
530 }
531
532 fn voxel_mut(&mut self, i: u32, j: u32, k: u32) -> &mut VoxelValue {
533 let idx = self.voxel_index(i, j, k);
534 &mut self.values[idx as usize]
535 }
536
537 /// The value of the given voxel.
538 ///
539 /// In 2D, the `k` argument is ignored.
540 pub fn voxel(&self, i: u32, j: u32, k: u32) -> VoxelValue {
541 let idx = self.voxel_index(i, j, k);
542 self.values[idx as usize]
543 }
544
545 /// Mark all the PrimitiveUndefined voxels within the given bounds as PrimitiveOutsideSurfaceToWalk.
546 #[cfg(feature = "dim2")]
547 fn mark_outside_surface(&mut self, i0: u32, j0: u32, i1: u32, j1: u32) {
548 for i in i0..i1 {
549 for j in j0..j1 {
550 let v = self.voxel_mut(i, j, 0);
551
552 if *v == VoxelValue::PrimitiveUndefined {
553 *v = VoxelValue::PrimitiveOutsideSurfaceToWalk;
554 }
555 }
556 }
557 }
558
559 /// Mark all the PrimitiveUndefined voxels within the given bounds as PrimitiveOutsideSurfaceToWalk.
560 #[cfg(feature = "dim3")]
561 fn mark_outside_surface(&mut self, i0: u32, j0: u32, k0: u32, i1: u32, j1: u32, k1: u32) {
562 for i in i0..i1 {
563 for j in j0..j1 {
564 for k in k0..k1 {
565 let v = self.voxel_mut(i, j, k);
566
567 if *v == VoxelValue::PrimitiveUndefined {
568 *v = VoxelValue::PrimitiveOutsideSurfaceToWalk;
569 }
570 }
571 }
572 }
573 }
574
575 fn walk_forward(
576 primitive_undefined_value_to_set: VoxelValue,
577 on_surface_value_to_set: VoxelValue,
578 start: isize,
579 end: isize,
580 mut ptr: isize,
581 out: &mut [VoxelValue],
582 stride: isize,
583 max_distance: isize,
584 ) {
585 let mut i = start;
586 let mut count = 0;
587
588 while count < max_distance && i < end {
589 if out[ptr as usize] == VoxelValue::PrimitiveUndefined {
590 out[ptr as usize] = primitive_undefined_value_to_set;
591 } else if out[ptr as usize] == VoxelValue::PrimitiveOnSurface {
592 out[ptr as usize] = on_surface_value_to_set;
593 break;
594 } else {
595 break;
596 }
597
598 i += 1;
599 ptr += stride;
600 count += 1;
601 }
602 }
603
604 fn walk_backward(
605 primitive_undefined_value_to_set: VoxelValue,
606 on_surface_value_to_set: VoxelValue,
607 start: isize,
608 end: isize,
609 mut ptr: isize,
610 out: &mut [VoxelValue],
611 stride: isize,
612 max_distance: isize,
613 ) {
614 let mut i = start;
615 let mut count = 0;
616
617 while count < max_distance && i >= end {
618 if out[ptr as usize] == VoxelValue::PrimitiveUndefined {
619 out[ptr as usize] = primitive_undefined_value_to_set;
620 } else if out[ptr as usize] == VoxelValue::PrimitiveOnSurface {
621 out[ptr as usize] = on_surface_value_to_set;
622 break;
623 } else {
624 break;
625 }
626
627 i -= 1;
628 ptr -= stride;
629 count += 1;
630 }
631 }
632
633 fn propagate_values(
634 &mut self,
635 inside_surface_value_to_walk: VoxelValue,
636 inside_surface_value_to_set: VoxelValue,
637 on_surface_value_to_walk: Option<VoxelValue>,
638 on_surface_value_to_set: VoxelValue,
639 ) -> bool {
640 let mut voxels_walked;
641 let mut walked_at_least_once = false;
642 let i0 = self.resolution[0];
643 let j0 = self.resolution[1];
644 #[cfg(feature = "dim2")]
645 let k0 = 1;
646 #[cfg(feature = "dim3")]
647 let k0 = self.resolution[2];
648
649 // Avoid striding too far in each direction to stay in L1 cache as much as possible.
650 // The cache size required for the walk is roughly (4 * walk_distance * 64) since
651 // the k direction doesn't count as it's walking byte per byte directly in a cache lines.
652 // ~16k is required for a walk distance of 64 in each directions.
653 let walk_distance = 64;
654
655 // using the stride directly instead of calling get_voxel for each iterations saves
656 // a lot of multiplications and pipeline stalls due to values dependencies on imul.
657 let istride = self.voxel_index(1, 0, 0) as isize - self.voxel_index(0, 0, 0) as isize;
658 let jstride = self.voxel_index(0, 1, 0) as isize - self.voxel_index(0, 0, 0) as isize;
659 #[cfg(feature = "dim3")]
660 let kstride = self.voxel_index(0, 0, 1) as isize - self.voxel_index(0, 0, 0) as isize;
661
662 // It might seem counter intuitive to go over the whole voxel range multiple times
663 // but since we do the run in memory order, it leaves us with far fewer cache misses
664 // than a BFS algorithm and it has the additional benefit of not requiring us to
665 // store and manipulate a fifo for recursion that might become huge when the number
666 // of voxels is large.
667 // This will outperform the BFS algorithm by several orders of magnitude in practice.
668 loop {
669 voxels_walked = 0;
670
671 for i in 0..i0 {
672 for j in 0..j0 {
673 for k in 0..k0 {
674 let idx = self.voxel_index(i, j, k) as isize;
675 let voxel = self.voxel_mut(i, j, k);
676
677 if *voxel == inside_surface_value_to_walk {
678 voxels_walked += 1;
679 walked_at_least_once = true;
680 *voxel = inside_surface_value_to_set;
681 } else if Some(*voxel) != on_surface_value_to_walk {
682 continue;
683 }
684
685 // walk in each direction to mark other voxel that should be walked.
686 // this will generate a 3d pattern that will help the overall
687 // algorithm converge faster while remaining cache friendly.
688 #[cfg(feature = "dim3")]
689 Self::walk_forward(
690 inside_surface_value_to_walk,
691 on_surface_value_to_set,
692 k as isize + 1,
693 k0 as isize,
694 idx + kstride,
695 &mut self.values,
696 kstride,
697 walk_distance,
698 );
699 #[cfg(feature = "dim3")]
700 Self::walk_backward(
701 inside_surface_value_to_walk,
702 on_surface_value_to_set,
703 k as isize - 1,
704 0,
705 idx - kstride,
706 &mut self.values,
707 kstride,
708 walk_distance,
709 );
710
711 Self::walk_forward(
712 inside_surface_value_to_walk,
713 on_surface_value_to_set,
714 j as isize + 1,
715 j0 as isize,
716 idx + jstride,
717 &mut self.values,
718 jstride,
719 walk_distance,
720 );
721 Self::walk_backward(
722 inside_surface_value_to_walk,
723 on_surface_value_to_set,
724 j as isize - 1,
725 0,
726 idx - jstride,
727 &mut self.values,
728 jstride,
729 walk_distance,
730 );
731
732 Self::walk_forward(
733 inside_surface_value_to_walk,
734 on_surface_value_to_set,
735 (i + 1) as isize,
736 i0 as isize,
737 idx + istride,
738 &mut self.values,
739 istride,
740 walk_distance,
741 );
742 Self::walk_backward(
743 inside_surface_value_to_walk,
744 on_surface_value_to_set,
745 i as isize - 1,
746 0,
747 idx - istride,
748 &mut self.values,
749 istride,
750 walk_distance,
751 );
752 }
753 }
754 }
755
756 if voxels_walked == 0 {
757 break;
758 }
759 }
760
761 walked_at_least_once
762 }
763
764 fn replace_value(&mut self, current_value: VoxelValue, new_value: VoxelValue) {
765 for voxel in &mut self.values {
766 if *voxel == current_value {
767 *voxel = new_value;
768 }
769 }
770 }
771
772 /// Naive conversion of all the voxels with the given `value` to a triangle-mesh.
773 ///
774 /// This conversion is extremely naive: it will simply collect all the 12 triangles forming
775 /// the faces of each voxel. No actual boundary extraction is done.
776 #[cfg(feature = "dim3")]
777 pub fn to_trimesh(&self, value: VoxelValue) -> (Vec<Point<Real>>, Vec<[u32; DIM]>) {
778 let mut vertices = Vec::new();
779 let mut indices = Vec::new();
780
781 for i in 0..self.resolution[0] {
782 for j in 0..self.resolution[1] {
783 for k in 0..self.resolution[2] {
784 let voxel = self.voxel(i, j, k);
785
786 if voxel == value {
787 let ijk = Vector::new(i as Real, j as Real, k as Real);
788
789 let shifts = [
790 Vector::new(-0.5, -0.5, -0.5),
791 Vector::new(0.5, -0.5, -0.5),
792 Vector::new(0.5, 0.5, -0.5),
793 Vector::new(-0.5, 0.5, -0.5),
794 Vector::new(-0.5, -0.5, 0.5),
795 Vector::new(0.5, -0.5, 0.5),
796 Vector::new(0.5, 0.5, 0.5),
797 Vector::new(-0.5, 0.5, 0.5),
798 ];
799
800 for shift in &shifts {
801 vertices.push(self.origin + (ijk + shift) * self.scale);
802 }
803
804 let s = vertices.len() as u32;
805 indices.push([s, s + 2, s + 1]);
806 indices.push([s, s + 3, s + 2]);
807 indices.push([s + 4, s + 5, s + 6]);
808 indices.push([s + 4, s + 6, s + 7]);
809 indices.push([s + 7, s + 6, s + 2]);
810 indices.push([s + 7, s + 2, s + 3]);
811 indices.push([s + 4, s + 1, s + 5]);
812 indices.push([s + 4, s, s + 1]);
813 indices.push([s + 6, s + 5, s + 1]);
814 indices.push([s + 6, s + 1, s + 2]);
815 indices.push([s + 7, s, s + 4]);
816 indices.push([s + 7, s + 3, s]);
817 }
818 }
819 }
820 }
821
822 (vertices, indices)
823 }
824}
825
826impl From<VoxelizedVolume> for VoxelSet {
827 fn from(mut shape: VoxelizedVolume) -> Self {
828 let mut curr_intersection_index = 0;
829 let mut vset = VoxelSet::new();
830 let mut vset_intersections = Vec::new();
831 vset.origin = shape.origin;
832 vset.scale = shape.scale;
833
834 #[cfg(feature = "dim2")]
835 let k1 = 1;
836 #[cfg(feature = "dim3")]
837 let k1 = shape.resolution[2];
838
839 for i in 0..shape.resolution[0] {
840 for j in 0..shape.resolution[1] {
841 for k in 0..k1 {
842 let id = shape.voxel_index(i, j, k) as usize;
843 let value = shape.values[id];
844 #[cfg(feature = "dim2")]
845 let coords = Point::new(i, j);
846 #[cfg(feature = "dim3")]
847 let coords = Point::new(i, j, k);
848
849 if value == VoxelValue::PrimitiveInsideSurface {
850 let voxel = Voxel {
851 coords,
852 is_on_surface: false,
853 intersections_range: (curr_intersection_index, curr_intersection_index),
854 };
855 vset.voxels.push(voxel);
856 } else if value == VoxelValue::PrimitiveOnSurface {
857 let mut voxel = Voxel {
858 coords,
859 is_on_surface: true,
860 intersections_range: (curr_intersection_index, curr_intersection_index),
861 };
862
863 if !shape.primitive_intersections.is_empty() {
864 let num_intersections =
865 shape.data[id].num_primitive_intersections as usize;
866 // We store the index where we should write the intersection on the
867 // vset into num_primitive_intersections. That way we can reuse it
868 // afterwards when copying the set of intersection into a single
869 // flat Vec.
870 shape.data[id].num_primitive_intersections =
871 curr_intersection_index as u32;
872 curr_intersection_index += num_intersections;
873 voxel.intersections_range.1 = curr_intersection_index;
874 }
875
876 vset.voxels.push(voxel);
877 }
878 }
879 }
880 }
881
882 if !shape.primitive_intersections.is_empty() {
883 vset_intersections.resize(shape.primitive_intersections.len(), 0);
884 for (voxel_id, prim_id) in shape.primitive_intersections {
885 let num_inter = &mut shape.data[voxel_id as usize].num_primitive_intersections;
886 vset_intersections[*num_inter as usize] = prim_id;
887 *num_inter += 1;
888 }
889 }
890
891 vset.intersections = Arc::new(vset_intersections);
892
893 vset
894 }
895}
896
897/*
898fn traceRay(
899 mesh: &RaycastMesh,
900 start: Real,
901 dir: &Vector<Real>,
902 inside_count: &mut u32,
903 outside_count: &mut u32,
904) {
905 let out_t;
906 let u;
907 let v;
908 let w;
909 let face_sign;
910 let face_index;
911 let hit = raycast_mesh.raycast(start, dir, out_t, u, v, w, face_sign, face_index);
912
913 if hit {
914 if face_sign >= 0 {
915 *inside_count += 1;
916 } else {
917 *outside_count += 1;
918 }
919 }
920}
921
922
923fn raycast_fill(volume: &Volume, raycast_mesh: &RaycastMesh) {
924if !raycast_mesh {
925 return;
926}
927
928let scale = volume.scale;
929let bmin = volume.min_bb;
930
931let i0 = volume.resolution[0];
932let j0 = volume.resolution[1];
933let k0 = volume.resolution[2];
934
935for i in 0..i0 {
936 for j in 0..j0 {
937 for k in 0..k0 {
938 let voxel = volume.get_voxel(i, j, k);
939
940 if voxel != VoxelValue::PrimitiveOnSurface {
941 let start = Vector::new(
942 i as Real * scale + bmin[0],
943 j as Real * scale + bmin[1],
944 k as Real * scale + bmin[2],
945 );
946
947 let mut inside_count = 0;
948 let mut outside_count = 0;
949
950 let directions = [
951 Vector::x(),
952 -Vector::x(),
953 Vector::y(),
954 -Vector::y(),
955 Vector::z(),
956 -Vector::z(),
957 ];
958
959 for r in 0..6 {
960 traceRay(
961 raycast_mesh,
962 start,
963 &directions[r * 3],
964 &mut inside_count,
965 &mut outside_count,
966 );
967
968 // Early out if we hit the outside of the mesh
969 if outside_count != 0 {
970 break;
971 }
972
973 // Early out if we accumulated 3 inside hits
974 if inside_count >= 3 {
975 break;
976 }
977 }
978
979 if outside_count == 0 && inside_count >= 3 {
980 volume.set_voxel(i, j, k, VoxelValue::PrimitiveInsideSurface);
981 } else {
982 volume.set_voxel(i, j, k, VoxelValue::PrimitiveOutsideSurface);
983 }
984 }
985 }
986 }
987}
988}
989 */