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 */