parry3d/shape/voxels/
voxels_chunk.rs

1use crate::bounding_volume::Aabb;
2use crate::math::{Point, Real, Vector};
3use crate::shape::{VoxelData, VoxelState, Voxels};
4use na::point;
5
6#[derive(Clone, Debug)]
7#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
8pub(super) struct VoxelsChunkHeader {
9    pub(super) id: usize,
10    // The number of non-empty voxels in the chunk.
11    // This is used for detecting when a chunk can be removed
12    // if it becomes fully empty.
13    pub(super) len: usize,
14}
15
16#[derive(Clone, Debug)]
17#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
18#[repr(C)]
19#[repr(align(64))]
20pub(super) struct VoxelsChunk {
21    #[cfg_attr(feature = "serde-serialize", serde(with = "serde_arrays"))]
22    pub(super) states: [VoxelState; VoxelsChunk::VOXELS_PER_CHUNK],
23}
24
25impl Default for VoxelsChunk {
26    fn default() -> Self {
27        Self {
28            states: [VoxelState::EMPTY; VoxelsChunk::VOXELS_PER_CHUNK],
29        }
30    }
31}
32
33#[derive(Copy, Clone, Debug, PartialEq)]
34pub struct VoxelIndex {
35    pub(super) chunk_id: usize,
36    pub(super) id_in_chunk: usize,
37}
38
39impl VoxelIndex {
40    pub fn flat_id(&self) -> usize {
41        self.chunk_id * VoxelsChunk::VOXELS_PER_CHUNK + self.id_in_chunk
42    }
43
44    pub fn from_flat_id(id: usize) -> Self {
45        Self {
46            chunk_id: id / VoxelsChunk::VOXELS_PER_CHUNK,
47            id_in_chunk: id % VoxelsChunk::VOXELS_PER_CHUNK,
48        }
49    }
50}
51
52impl VoxelsChunk {
53    // TODO: find the ideal number. We want a good balance between cache locality
54    //       and number of BVH leaf nodes.
55    #[cfg(feature = "dim2")]
56    pub(super) const VOXELS_PER_CHUNK_DIM: usize = 16;
57    #[cfg(feature = "dim3")]
58    pub(super) const VOXELS_PER_CHUNK_DIM: usize = 8;
59    #[cfg(feature = "dim2")]
60    pub(super) const VOXELS_PER_CHUNK: usize =
61        Self::VOXELS_PER_CHUNK_DIM * Self::VOXELS_PER_CHUNK_DIM;
62    #[cfg(feature = "dim3")]
63    pub(super) const VOXELS_PER_CHUNK: usize =
64        Self::VOXELS_PER_CHUNK_DIM * Self::VOXELS_PER_CHUNK_DIM * Self::VOXELS_PER_CHUNK_DIM;
65
66    #[cfg(feature = "dim2")]
67    pub(super) const INVALID_CHUNK_KEY: Point<i32> = point![i32::MAX, i32::MAX];
68    #[cfg(feature = "dim3")]
69    pub(super) const INVALID_CHUNK_KEY: Point<i32> = point![i32::MAX, i32::MAX, i32::MAX];
70
71    /// The key of the voxel at the given linearized index within this chunk.
72    #[cfg(feature = "dim2")]
73    pub(super) fn voxel_key_at_id(chunk_key: Point<i32>, id_in_chunk: u32) -> Point<i32> {
74        let y = id_in_chunk as i32 / Self::VOXELS_PER_CHUNK_DIM as i32;
75        let x = id_in_chunk as i32 % Self::VOXELS_PER_CHUNK_DIM as i32;
76        chunk_key * (Self::VOXELS_PER_CHUNK_DIM as i32) + Vector::new(x, y)
77    }
78
79    /// The key of the voxel at the given linearized index.
80    #[cfg(feature = "dim3")]
81    pub(super) fn voxel_key_at_id(chunk_key: Point<i32>, id_in_chunk: u32) -> Point<i32> {
82        let d0d1 = (Self::VOXELS_PER_CHUNK_DIM * Self::VOXELS_PER_CHUNK_DIM) as u32;
83        let z = id_in_chunk / d0d1;
84        let y = (id_in_chunk - z * d0d1) / Self::VOXELS_PER_CHUNK_DIM as u32;
85        let x = id_in_chunk % Self::VOXELS_PER_CHUNK_DIM as u32;
86        chunk_key * (Self::VOXELS_PER_CHUNK_DIM as i32) + Vector::new(x as i32, y as i32, z as i32)
87    }
88
89    /// The semi-open range of valid voxel keys for this chunk.
90    pub(super) fn keys_bounds(chunk_key: &Point<i32>) -> [Point<i32>; 2] {
91        let imins = chunk_key * Self::VOXELS_PER_CHUNK_DIM as i32;
92        let imaxs = imins + Vector::repeat(Self::VOXELS_PER_CHUNK_DIM as i32);
93        [imins, imaxs]
94    }
95
96    pub(super) fn aabb(chunk_key: &Point<i32>, voxel_size: &Vector<Real>) -> Aabb {
97        let [imins, imaxs] = Self::keys_bounds(chunk_key);
98        let mut aabb = Aabb::new(imins.cast(), imaxs.cast());
99        aabb.mins.coords.component_mul_assign(voxel_size);
100        aabb.maxs.coords.component_mul_assign(voxel_size);
101        aabb
102    }
103}
104
105/// A reference to a chunk of voxels within a [`Voxels`] shape.
106///
107/// # What is a Chunk?
108///
109/// To efficiently manage large voxel worlds, Parry internally divides the voxel grid into
110/// fixed-size chunks. Each chunk contains a small region of voxels (e.g., 8×8×8 in 3D or
111/// 16×16 in 2D). This chunking provides:
112///
113/// - **Spatial acceleration**: Quick queries using a BVH of chunks
114/// - **Memory efficiency**: Empty chunks are not stored
115/// - **Cache locality**: Nearby voxels are stored together
116///
117/// A `VoxelsChunkRef` provides read-only access to a single chunk's data, allowing you to
118/// query voxels within that chunk without iterating through the entire voxel shape.
119///
120/// # When to Use
121///
122/// You typically don't create `VoxelsChunkRef` directly. Instead, you get them from:
123/// - [`Voxels::chunk_ref`]: Get a specific chunk by ID
124/// - BVH traversal for spatial queries on large voxel worlds
125///
126/// # Examples
127///
128/// ```
129/// # #[cfg(all(feature = "dim3", feature = "f32"))] {
130/// use parry3d::shape::Voxels;
131/// use nalgebra::{Point3, Vector3};
132///
133/// let voxels = Voxels::new(
134///     Vector3::new(1.0, 1.0, 1.0),
135///     &[Point3::new(0, 0, 0), Point3::new(1, 0, 0)],
136/// );
137///
138/// // Get a chunk reference (chunk IDs come from BVH traversal)
139/// let chunk_ref = voxels.chunk_ref(0);
140///
141/// // Query voxels within this chunk
142/// for voxel in chunk_ref.voxels() {
143///     if !voxel.state.is_empty() {
144///         println!("Voxel at {:?}", voxel.grid_coords);
145///     }
146/// }
147///
148/// // Get chunk's AABB
149/// let aabb = chunk_ref.local_aabb();
150/// println!("Chunk bounds: {:?}", aabb);
151/// # }
152/// ```
153#[derive(Copy, Clone)]
154pub struct VoxelsChunkRef<'a> {
155    /// The linear index of this chunk within the `Voxels` shape.
156    pub my_id: usize,
157    /// The voxel shape this chunk is part of.
158    pub parent: &'a Voxels,
159    /// The fill status of each voxel from this chunk.
160    pub states: &'a [VoxelState; VoxelsChunk::VOXELS_PER_CHUNK],
161    /// The spatial index of this chunk.
162    pub key: &'a Point<i32>,
163}
164
165impl<'a> VoxelsChunkRef<'a> {
166    /// The AABB of this chunk of voxels.
167    ///
168    /// Note that this return the AABB of the whole chunk, without taking into account the fact
169    /// that some voxels are empty.
170    pub fn local_aabb(&self) -> Aabb {
171        VoxelsChunk::aabb(self.key, &self.parent.voxel_size)
172    }
173
174    /// The domain of this chunk of voxels.
175    pub fn domain(&self) -> [Point<i32>; 2] {
176        VoxelsChunk::keys_bounds(self.key)
177    }
178
179    /// Returns the spatial index of the voxel containing the given point.
180    pub fn voxel_at_point_unchecked(&self, pt: Point<Real>) -> Point<i32> {
181        self.parent.voxel_at_point(pt)
182    }
183
184    /// The state of the voxel with key `voxel_key`.
185    pub fn voxel_state(&self, voxel_key: Point<i32>) -> Option<VoxelState> {
186        let (chunk_key, id_in_chunk) = Voxels::chunk_key_and_id_in_chunk(voxel_key);
187        if &chunk_key != self.key {
188            return None;
189        }
190        Some(self.states[id_in_chunk])
191    }
192
193    /// Clamps the `voxel_key` so it is within the bounds of `self`.
194    pub fn clamp_voxel(&self, voxel_key: Point<i32>) -> Point<i32> {
195        let [mins, maxs] = self.domain();
196        voxel_key
197            .coords
198            .zip_zip_map(&mins.coords, &maxs.coords, |k, min, max| k.clamp(min, max))
199            .into()
200    }
201
202    /// The AABB of the voxel with this key.
203    ///
204    /// Returns a result even if the voxel doesn’t belong to this chunk.
205    pub fn voxel_aabb_unchecked(&self, voxel_key: Point<i32>) -> Aabb {
206        self.parent.voxel_aabb(voxel_key)
207    }
208
209    /// Convert a voxel index (expressed relative to the main `Voxels` shape, not relative to the
210    /// chunk alone) into a flat index within a voxel chunk.
211    ///
212    /// Returns `None` if the voxel isn’t part of this chunk.
213    pub fn flat_id(&self, voxel_key: Point<i32>) -> Option<u32> {
214        let (chunk_key, id_in_chunk) = Voxels::chunk_key_and_id_in_chunk(voxel_key);
215        if &chunk_key != self.key {
216            return None;
217        }
218
219        Some(
220            VoxelIndex {
221                chunk_id: self.my_id,
222                id_in_chunk,
223            }
224            .flat_id() as u32,
225        )
226    }
227
228    /// Iterates through all the voxels in this chunk.
229    ///
230    /// Note that this only yields non-empty voxels within the range. This does not
231    /// include any voxel that falls outside [`Self::domain`].
232    pub fn voxels(&self) -> impl Iterator<Item = VoxelData> + '_ {
233        let range = self.domain();
234        self.voxels_in_range(range[0], range[1])
235    }
236
237    /// Iterate through the data of all the voxels within the given (semi-open) voxel grid indices.
238    ///
239    /// Note that this only yields non-empty voxels within the range. This does not
240    /// include any voxel that falls outside [`Self::domain`].
241    #[cfg(feature = "dim2")]
242    pub fn voxels_in_range(
243        self,
244        mins: Point<i32>,
245        maxs: Point<i32>,
246    ) -> impl Iterator<Item = VoxelData> + use<'a> {
247        let [chunk_mins, chunk_maxs] = VoxelsChunk::keys_bounds(self.key);
248        let mins = mins.coords.sup(&chunk_mins.coords);
249        let maxs = maxs.coords.inf(&chunk_maxs.coords);
250
251        (mins[0]..maxs[0]).flat_map(move |ix| {
252            (mins[1]..maxs[1]).flat_map(move |iy| {
253                let id_in_chunk = (ix - chunk_mins[0]) as usize
254                    + (iy - chunk_mins[1]) as usize * VoxelsChunk::VOXELS_PER_CHUNK_DIM;
255                let state = self.states[id_in_chunk];
256
257                if state.is_empty() {
258                    return None;
259                }
260
261                let grid_coords = Point::new(ix, iy);
262                let center = Vector::new(ix as Real + 0.5, iy as Real + 0.5)
263                    .component_mul(&self.parent.voxel_size);
264                Some(VoxelData {
265                    linear_id: VoxelIndex {
266                        chunk_id: self.my_id,
267                        id_in_chunk,
268                    },
269                    grid_coords,
270                    center: center.into(),
271                    state,
272                })
273            })
274        })
275    }
276
277    /// Iterate through the data of all the voxels within the given (semi-open) voxel grid indices.
278    ///
279    /// Note that this yields both empty and non-empty voxels within the range. This does not
280    /// include any voxel that falls outside [`Self::domain`].
281    #[cfg(feature = "dim3")]
282    pub fn voxels_in_range(
283        self,
284        mins: Point<i32>,
285        maxs: Point<i32>,
286    ) -> impl Iterator<Item = VoxelData> + use<'a> {
287        let [chunk_mins, chunk_maxs] = VoxelsChunk::keys_bounds(self.key);
288        let mins = mins.coords.sup(&chunk_mins.coords);
289        let maxs = maxs.coords.inf(&chunk_maxs.coords);
290
291        (mins[0]..maxs[0]).flat_map(move |ix| {
292            (mins[1]..maxs[1]).flat_map(move |iy| {
293                (mins[2]..maxs[2]).filter_map(move |iz| {
294                    let id_in_chunk = (ix - chunk_mins[0]) as usize
295                        + (iy - chunk_mins[1]) as usize * VoxelsChunk::VOXELS_PER_CHUNK_DIM
296                        + (iz - chunk_mins[2]) as usize
297                            * VoxelsChunk::VOXELS_PER_CHUNK_DIM
298                            * VoxelsChunk::VOXELS_PER_CHUNK_DIM;
299                    let state = self.states[id_in_chunk];
300
301                    if state.is_empty() {
302                        return None;
303                    }
304
305                    let grid_coords = Point::new(ix, iy, iz);
306                    let center = Vector::new(ix as Real + 0.5, iy as Real + 0.5, iz as Real + 0.5)
307                        .component_mul(&self.parent.voxel_size);
308                    Some(VoxelData {
309                        linear_id: VoxelIndex {
310                            chunk_id: self.my_id,
311                            id_in_chunk,
312                        },
313                        grid_coords,
314                        center: center.into(),
315                        state,
316                    })
317                })
318            })
319        })
320    }
321}
parry3d/shape/voxels/voxels_chunk.rs

parry3d/shape/voxels/
voxels_chunk.rs
