parry2d/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 voxel chunk.
106#[derive(Copy, Clone)]
107pub struct VoxelsChunkRef<'a> {
108    /// The linear index of this chunk within the `Voxels` shape.
109    pub my_id: usize,
110    /// The voxel shape this chunk is part of.
111    pub parent: &'a Voxels,
112    /// The fill status of each voxel from this chunk.
113    pub states: &'a [VoxelState; VoxelsChunk::VOXELS_PER_CHUNK],
114    /// The spatial index of this chunk.
115    pub key: &'a Point<i32>,
116}
117
118impl<'a> VoxelsChunkRef<'a> {
119    /// The AABB of this chunk of voxels.
120    ///
121    /// Note that this return the AABB of the whole chunk, without taking into account the fact
122    /// that some voxels are empty.
123    pub fn local_aabb(&self) -> Aabb {
124        VoxelsChunk::aabb(self.key, &self.parent.voxel_size)
125    }
126
127    /// The domain of this chunk of voxels.
128    pub fn domain(&self) -> [Point<i32>; 2] {
129        VoxelsChunk::keys_bounds(self.key)
130    }
131
132    /// Returns the spatial index of the voxel containing the given point.
133    pub fn voxel_at_point_unchecked(&self, pt: Point<Real>) -> Point<i32> {
134        self.parent.voxel_at_point(pt)
135    }
136
137    /// The state of the voxel with key `voxel_key`.
138    pub fn voxel_state(&self, voxel_key: Point<i32>) -> Option<VoxelState> {
139        let (chunk_key, id_in_chunk) = Voxels::chunk_key_and_id_in_chunk(voxel_key);
140        if &chunk_key != self.key {
141            return None;
142        }
143        Some(self.states[id_in_chunk])
144    }
145
146    /// Clamps the `voxel_key` so it is within the bounds of `self`.
147    pub fn clamp_voxel(&self, voxel_key: Point<i32>) -> Point<i32> {
148        let [mins, maxs] = self.domain();
149        voxel_key
150            .coords
151            .zip_zip_map(&mins.coords, &maxs.coords, |k, min, max| k.clamp(min, max))
152            .into()
153    }
154
155    /// The AABB of the voxel with this key.
156    ///
157    /// Returns a result even if the voxel doesn’t belong to this chunk.
158    pub fn voxel_aabb_unchecked(&self, voxel_key: Point<i32>) -> Aabb {
159        self.parent.voxel_aabb(voxel_key)
160    }
161
162    /// Convert a voxel index (expressed relative to the main `Voxels` shape, not relative to the
163    /// chunk alone) into a flat index within a voxel chunk.
164    ///
165    /// Returns `None` if the voxel isn’t part of this chunk.
166    pub fn flat_id(&self, voxel_key: Point<i32>) -> Option<u32> {
167        let (chunk_key, id_in_chunk) = Voxels::chunk_key_and_id_in_chunk(voxel_key);
168        if &chunk_key != self.key {
169            return None;
170        }
171
172        Some(
173            VoxelIndex {
174                chunk_id: self.my_id,
175                id_in_chunk,
176            }
177            .flat_id() as u32,
178        )
179    }
180
181    /// Iterates through all the voxels in this chunk.
182    ///
183    /// Note that this yields both empty and non-empty voxels within the range. This does not
184    /// include any voxel that falls outside [`Self::domain`].
185    pub fn voxels(&self) -> impl Iterator<Item = VoxelData> + '_ {
186        let range = self.domain();
187        self.voxels_in_range(range[0], range[1])
188    }
189
190    /// Iterate through the data of all the voxels within the given (semi-open) voxel grid indices.
191    ///
192    /// Note that this yields both empty and non-empty voxels within the range. This does not
193    /// include any voxel that falls outside [`Self::domain`].
194    #[cfg(feature = "dim2")]
195    pub fn voxels_in_range(
196        self,
197        mins: Point<i32>,
198        maxs: Point<i32>,
199    ) -> impl Iterator<Item = VoxelData> + use<'a> {
200        let [chunk_mins, chunk_maxs] = VoxelsChunk::keys_bounds(self.key);
201        let mins = mins.coords.sup(&chunk_mins.coords);
202        let maxs = maxs.coords.inf(&chunk_maxs.coords);
203
204        (mins[0]..maxs[0]).flat_map(move |ix| {
205            (mins[1]..maxs[1]).flat_map(move |iy| {
206                let id_in_chunk = (ix - chunk_mins[0]) as usize
207                    + (iy - chunk_mins[1]) as usize * VoxelsChunk::VOXELS_PER_CHUNK_DIM;
208                let state = self.states[id_in_chunk];
209
210                if state.is_empty() {
211                    return None;
212                }
213
214                let grid_coords = Point::new(ix, iy);
215                let center = Vector::new(ix as Real + 0.5, iy as Real + 0.5)
216                    .component_mul(&self.parent.voxel_size);
217                Some(VoxelData {
218                    linear_id: VoxelIndex {
219                        chunk_id: self.my_id,
220                        id_in_chunk,
221                    },
222                    grid_coords,
223                    center: center.into(),
224                    state,
225                })
226            })
227        })
228    }
229
230    /// Iterate through the data of all the voxels within the given (semi-open) voxel grid indices.
231    ///
232    /// Note that this yields both empty and non-empty voxels within the range. This does not
233    /// include any voxel that falls outside [`Self::domain`].
234    #[cfg(feature = "dim3")]
235    pub fn voxels_in_range(
236        self,
237        mins: Point<i32>,
238        maxs: Point<i32>,
239    ) -> impl Iterator<Item = VoxelData> + use<'a> {
240        let [chunk_mins, chunk_maxs] = VoxelsChunk::keys_bounds(self.key);
241        let mins = mins.coords.sup(&chunk_mins.coords);
242        let maxs = maxs.coords.inf(&chunk_maxs.coords);
243
244        (mins[0]..maxs[0]).flat_map(move |ix| {
245            (mins[1]..maxs[1]).flat_map(move |iy| {
246                (mins[2]..maxs[2]).filter_map(move |iz| {
247                    let id_in_chunk = (ix - chunk_mins[0]) as usize
248                        + (iy - chunk_mins[1]) as usize * VoxelsChunk::VOXELS_PER_CHUNK_DIM
249                        + (iz - chunk_mins[2]) as usize
250                            * VoxelsChunk::VOXELS_PER_CHUNK_DIM
251                            * VoxelsChunk::VOXELS_PER_CHUNK_DIM;
252                    let state = self.states[id_in_chunk];
253
254                    if state.is_empty() {
255                        return None;
256                    }
257
258                    let grid_coords = Point::new(ix, iy, iz);
259                    let center = Vector::new(ix as Real + 0.5, iy as Real + 0.5, iz as Real + 0.5)
260                        .component_mul(&self.parent.voxel_size);
261                    Some(VoxelData {
262                        linear_id: VoxelIndex {
263                            chunk_id: self.my_id,
264                            id_in_chunk,
265                        },
266                        grid_coords,
267                        center: center.into(),
268                        state,
269                    })
270                })
271            })
272        })
273    }
274}
parry2d/shape/voxels/voxels_chunk.rs

parry2d/shape/voxels/
voxels_chunk.rs
