veloren_common/terrain/
chonk.rs

1use crate::{
2    vol::{
3        BaseVol, IntoPosIterator, IntoVolIterator, ReadVol, RectRasterableVol, RectVolSize,
4        VolSize, WriteVol,
5    },
6    volumes::chunk::{Chunk, ChunkError, ChunkPosIter, ChunkVolIter},
7};
8use core::{hash::Hash, marker::PhantomData};
9use serde::{Deserialize, Serialize};
10use vek::*;
11
12#[derive(Debug)]
13pub enum ChonkError {
14    SubChunkError(ChunkError),
15    OutOfBounds,
16}
17
18#[derive(Debug, Clone, Serialize, Deserialize)]
19pub struct SubChunkSize<ChonkSize: RectVolSize> {
20    phantom: PhantomData<ChonkSize>,
21}
22
23// TODO (haslersn): Assert ChonkSize::RECT_SIZE.x == ChonkSize::RECT_SIZE.y
24
25impl<ChonkSize: RectVolSize> VolSize for SubChunkSize<ChonkSize> {
26    const SIZE: Vec3<u32> = Vec3 {
27        x: ChonkSize::RECT_SIZE.x,
28        y: ChonkSize::RECT_SIZE.x,
29        // NOTE: Currently, use 32 instead of 2 for RECT_SIZE.x = 128.
30        z: ChonkSize::RECT_SIZE.x / 2,
31    };
32}
33
34type SubChunk<V, S, M> = Chunk<V, SubChunkSize<S>, M>;
35
36#[derive(Debug, Clone, Serialize, Deserialize)]
37pub struct Chonk<V, S: RectVolSize, M: Clone> {
38    z_offset: i32,
39    sub_chunks: Vec<SubChunk<V, S, M>>,
40    below: V,
41    above: V,
42    meta: M,
43    phantom: PhantomData<S>,
44}
45
46impl<V, S: RectVolSize, M: Clone> Chonk<V, S, M> {
47    pub fn new(z_offset: i32, below: V, above: V, meta: M) -> Self {
48        Self {
49            z_offset,
50            sub_chunks: Vec::new(),
51            below,
52            above,
53            meta,
54            phantom: PhantomData,
55        }
56    }
57
58    pub fn meta(&self) -> &M { &self.meta }
59
60    pub fn meta_mut(&mut self) -> &mut M { &mut self.meta }
61
62    #[inline]
63    pub fn get_min_z(&self) -> i32 { self.z_offset }
64
65    #[inline]
66    pub fn get_max_z(&self) -> i32 {
67        self.z_offset + (self.sub_chunks.len() as u32 * SubChunkSize::<S>::SIZE.z) as i32
68    }
69
70    pub fn sub_chunks_len(&self) -> usize { self.sub_chunks.len() }
71
72    pub fn sub_chunk_groups(&self) -> usize {
73        self.sub_chunks.iter().map(SubChunk::num_groups).sum()
74    }
75
76    /// Iterate through the voxels in this chunk, attempting to avoid those that
77    /// are unchanged (i.e: match the `below` and `above` voxels). This is
78    /// generally useful for performance reasons.
79    pub fn iter_changed(&self) -> impl Iterator<Item = (Vec3<i32>, &V)> + '_ {
80        self.sub_chunks
81            .iter()
82            .enumerate()
83            .filter(|(_, sc)| sc.num_groups() > 0)
84            .flat_map(move |(i, sc)| {
85                let z_offset = self.z_offset + i as i32 * SubChunkSize::<S>::SIZE.z as i32;
86                sc.vol_iter(Vec3::zero(), SubChunkSize::<S>::SIZE.map(|e| e as i32))
87                    .map(move |(pos, vox)| (pos + Vec3::unit_z() * z_offset, vox))
88            })
89    }
90
91    // Returns the index (in self.sub_chunks) of the SubChunk that contains
92    // layer z; note that this index changes when more SubChunks are prepended
93    #[inline]
94    fn sub_chunk_idx(&self, z: i32) -> i32 {
95        let diff = z - self.z_offset;
96        diff >> (SubChunkSize::<S>::SIZE.z - 1).count_ones()
97    }
98
99    // Converts a z coordinate into a local z coordinate within a sub chunk
100    fn sub_chunk_z(&self, z: i32) -> i32 {
101        let diff = z - self.z_offset;
102        diff & (SubChunkSize::<S>::SIZE.z - 1) as i32
103    }
104
105    // Returns the z offset of the sub_chunk that contains layer z
106    fn sub_chunk_min_z(&self, z: i32) -> i32 { z - self.sub_chunk_z(z) }
107
108    /// Compress chunk by using more intelligent defaults.
109    pub fn defragment(&mut self)
110    where
111        V: Clone + Eq + Hash,
112    {
113        // First, defragment all subchunks.
114        self.sub_chunks.iter_mut().for_each(SubChunk::defragment);
115        // For each homogeneous subchunk (i.e. those where all blocks are the same),
116        // find those which match `below` at the bottom of the cunk, or `above`
117        // at the top, since these subchunks are redundant and can be removed.
118        // Note that we find (and drain) the above chunks first, so that when we
119        // remove the below chunks we have fewer remaining chunks to backshift.
120        // Note that we use `take_while` instead of `rposition` here because `rposition`
121        // goes one past the end, which we only want in the forward direction.
122        let above_count = self
123            .sub_chunks
124            .iter()
125            .rev()
126            .take_while(|subchunk| subchunk.homogeneous() == Some(&self.above))
127            .count();
128        // Unfortunately, `TakeWhile` doesn't implement `ExactSizeIterator` or
129        // `DoubleEndedIterator`, so we have to recreate the same state by calling
130        // `nth_back` (note that passing 0 to nth_back goes back 1 time, not 0
131        // times!).
132        let mut subchunks = self.sub_chunks.iter();
133        if above_count > 0 {
134            subchunks.nth_back(above_count - 1);
135        }
136        // `above_index` is now the number of remaining elements, since all the elements
137        // we drained were at the end.
138        let above_index = subchunks.len();
139        // `below_len` now needs to be applied to the state after the `above` chunks are
140        // drained, to make sure we don't accidentally have overlap (this is
141        // possible if self.above == self.below).
142        let below_len = subchunks.position(|subchunk| subchunk.homogeneous() != Some(&self.below));
143        let below_len = below_len
144            // NOTE: If `below_index` is `None`, then every *remaining* chunk after we drained
145            // `above` was full and matched `below`.
146            .unwrap_or(above_index);
147        // Now, actually remove the redundant chunks.
148        self.sub_chunks.truncate(above_index);
149        self.sub_chunks.drain(..below_len);
150        // Finally, bump the z_offset to account for the removed subchunks at the
151        // bottom. TODO: Add invariants to justify why `below_len` must fit in
152        // i32.
153        self.z_offset += below_len as i32 * SubChunkSize::<S>::SIZE.z as i32;
154    }
155}
156
157impl<V, S: RectVolSize, M: Clone> BaseVol for Chonk<V, S, M> {
158    type Error = ChonkError;
159    type Vox = V;
160}
161
162impl<V, S: RectVolSize, M: Clone> RectRasterableVol for Chonk<V, S, M> {
163    const RECT_SIZE: Vec2<u32> = S::RECT_SIZE;
164}
165
166impl<V, S: RectVolSize, M: Clone> ReadVol for Chonk<V, S, M> {
167    #[inline(always)]
168    fn get(&self, pos: Vec3<i32>) -> Result<&V, Self::Error> {
169        if pos.z < self.get_min_z() {
170            // Below the terrain
171            Ok(&self.below)
172        } else if pos.z >= self.get_max_z() {
173            // Above the terrain
174            Ok(&self.above)
175        } else {
176            // Within the terrain
177            let sub_chunk_idx = self.sub_chunk_idx(pos.z);
178            let rpos = pos
179                - Vec3::unit_z()
180                    * (self.z_offset + sub_chunk_idx * SubChunkSize::<S>::SIZE.z as i32);
181            self.sub_chunks[sub_chunk_idx as usize]
182                .get(rpos)
183                .map_err(Self::Error::SubChunkError)
184        }
185    }
186
187    #[inline(always)]
188    fn get_unchecked(&self, pos: Vec3<i32>) -> &V {
189        if pos.z < self.get_min_z() {
190            // Below the terrain
191            &self.below
192        } else if pos.z >= self.get_max_z() {
193            // Above the terrain
194            &self.above
195        } else {
196            // Within the terrain
197            let sub_chunk_idx = self.sub_chunk_idx(pos.z);
198            let rpos = pos
199                - Vec3::unit_z()
200                    * (self.z_offset + sub_chunk_idx * SubChunkSize::<S>::SIZE.z as i32);
201            self.sub_chunks[sub_chunk_idx as usize].get_unchecked(rpos)
202        }
203    }
204
205    fn for_each_in(&self, aabb: Aabb<i32>, mut f: impl FnMut(Vec3<i32>, Self::Vox))
206    where
207        Self::Vox: Copy,
208    {
209        let idx = self.sub_chunk_idx(aabb.min.z);
210        // Special-case for the AABB being entirely within a single sub-chunk as this is
211        // very common.
212        if idx == self.sub_chunk_idx(aabb.max.z) && idx >= 0 && idx < self.sub_chunks.len() as i32 {
213            let sub_chunk = &self.sub_chunks[idx as usize];
214            let z_off = self.z_offset + idx * SubChunkSize::<S>::SIZE.z as i32;
215            sub_chunk.for_each_in(
216                Aabb {
217                    min: aabb.min.with_z(aabb.min.z - z_off),
218                    max: aabb.max.with_z(aabb.max.z - z_off),
219                },
220                |pos, vox| f(pos.with_z(pos.z + z_off), vox),
221            );
222        } else {
223            for z in aabb.min.z..aabb.max.z + 1 {
224                for y in aabb.min.y..aabb.max.y + 1 {
225                    for x in aabb.min.x..aabb.max.x + 1 {
226                        f(Vec3::new(x, y, z), *self.get_unchecked(Vec3::new(x, y, z)));
227                    }
228                }
229            }
230        }
231    }
232}
233
234impl<V: Clone + PartialEq, S: RectVolSize, M: Clone> WriteVol for Chonk<V, S, M> {
235    #[inline(always)]
236    fn set(&mut self, pos: Vec3<i32>, block: Self::Vox) -> Result<V, Self::Error> {
237        let mut sub_chunk_idx = self.sub_chunk_idx(pos.z);
238
239        if pos.z < self.get_min_z() {
240            // Make sure we're not adding a redundant chunk.
241            if block == self.below {
242                return Ok(self.below.clone());
243            }
244            // Prepend exactly sufficiently many SubChunks via Vec::splice
245            let c = Chunk::<V, SubChunkSize<S>, M>::filled(self.below.clone(), self.meta.clone());
246            let n = (-sub_chunk_idx) as usize;
247            self.sub_chunks.splice(0..0, std::iter::repeat_n(c, n));
248            self.z_offset += sub_chunk_idx * SubChunkSize::<S>::SIZE.z as i32;
249            sub_chunk_idx = 0;
250        } else if pos.z >= self.get_max_z() {
251            // Make sure we're not adding a redundant chunk.
252            if block == self.above {
253                return Ok(self.above.clone());
254            }
255            // Append exactly sufficiently many SubChunks via Vec::extend
256            let c = Chunk::<V, SubChunkSize<S>, M>::filled(self.above.clone(), self.meta.clone());
257            let n = 1 + sub_chunk_idx as usize - self.sub_chunks.len();
258            self.sub_chunks.extend(std::iter::repeat_n(c, n));
259        }
260
261        let rpos = pos
262            - Vec3::unit_z() * (self.z_offset + sub_chunk_idx * SubChunkSize::<S>::SIZE.z as i32);
263        self.sub_chunks[sub_chunk_idx as usize] // TODO (haslersn): self.sub_chunks.get(...).and_then(...)
264            .set(rpos, block)
265            .map_err(Self::Error::SubChunkError)
266    }
267}
268
269struct ChonkIterHelper<V, S: RectVolSize, M: Clone> {
270    sub_chunk_min_z: i32,
271    lower_bound: Vec3<i32>,
272    upper_bound: Vec3<i32>,
273    phantom: PhantomData<Chonk<V, S, M>>,
274}
275
276impl<V, S: RectVolSize, M: Clone> Iterator for ChonkIterHelper<V, S, M> {
277    type Item = (i32, Vec3<i32>, Vec3<i32>);
278
279    #[inline(always)]
280    fn next(&mut self) -> Option<Self::Item> {
281        if self.lower_bound.z >= self.upper_bound.z {
282            return None;
283        }
284        let mut lb = self.lower_bound;
285        let mut ub = self.upper_bound;
286        let current_min_z = self.sub_chunk_min_z;
287        lb.z -= current_min_z;
288        ub.z -= current_min_z;
289        ub.z = std::cmp::min(ub.z, SubChunkSize::<S>::SIZE.z as i32);
290        self.sub_chunk_min_z += SubChunkSize::<S>::SIZE.z as i32;
291        self.lower_bound.z = self.sub_chunk_min_z;
292        Some((current_min_z, lb, ub))
293    }
294}
295
296pub struct ChonkPosIter<V, S: RectVolSize, M: Clone> {
297    outer: ChonkIterHelper<V, S, M>,
298    opt_inner: Option<(i32, ChunkPosIter<V, SubChunkSize<S>, M>)>,
299}
300
301impl<V, S: RectVolSize, M: Clone> Iterator for ChonkPosIter<V, S, M> {
302    type Item = Vec3<i32>;
303
304    #[inline(always)]
305    fn next(&mut self) -> Option<Self::Item> {
306        loop {
307            if let Some((sub_chunk_min_z, ref mut inner)) = self.opt_inner {
308                if let Some(mut pos) = inner.next() {
309                    pos.z += sub_chunk_min_z;
310                    return Some(pos);
311                }
312            }
313            match self.outer.next() {
314                None => return None,
315                Some((sub_chunk_min_z, lb, ub)) => {
316                    self.opt_inner = Some((sub_chunk_min_z, SubChunk::<V, S, M>::pos_iter(lb, ub)))
317                },
318            }
319        }
320    }
321}
322
323enum InnerChonkVolIter<'a, V, S: RectVolSize, M: Clone> {
324    Vol(ChunkVolIter<'a, V, SubChunkSize<S>, M>),
325    Pos(ChunkPosIter<V, SubChunkSize<S>, M>),
326}
327
328pub struct ChonkVolIter<'a, V, S: RectVolSize, M: Clone> {
329    chonk: &'a Chonk<V, S, M>,
330    outer: ChonkIterHelper<V, S, M>,
331    opt_inner: Option<(i32, InnerChonkVolIter<'a, V, S, M>)>,
332}
333
334impl<'a, V, S: RectVolSize, M: Clone> Iterator for ChonkVolIter<'a, V, S, M> {
335    type Item = (Vec3<i32>, &'a V);
336
337    #[inline(always)]
338    fn next(&mut self) -> Option<Self::Item> {
339        loop {
340            if let Some((sub_chunk_min_z, ref mut inner)) = self.opt_inner {
341                let got = match inner {
342                    InnerChonkVolIter::<'a, V, S, M>::Vol(iter) => iter.next(),
343                    InnerChonkVolIter::<'a, V, S, M>::Pos(iter) => iter.next().map(|pos| {
344                        if sub_chunk_min_z < self.chonk.get_min_z() {
345                            (pos, &self.chonk.below)
346                        } else {
347                            (pos, &self.chonk.above)
348                        }
349                    }),
350                };
351                if let Some((mut pos, vox)) = got {
352                    pos.z += sub_chunk_min_z;
353                    return Some((pos, vox));
354                }
355            }
356            match self.outer.next() {
357                None => return None,
358                Some((sub_chunk_min_z, lb, ub)) => {
359                    let inner = if sub_chunk_min_z < self.chonk.get_min_z()
360                        || sub_chunk_min_z >= self.chonk.get_max_z()
361                    {
362                        InnerChonkVolIter::<'a, V, S, M>::Pos(SubChunk::<V, S, M>::pos_iter(lb, ub))
363                    } else {
364                        InnerChonkVolIter::<'a, V, S, M>::Vol(
365                            self.chonk.sub_chunks
366                                [self.chonk.sub_chunk_idx(sub_chunk_min_z) as usize]
367                                .vol_iter(lb, ub),
368                        )
369                    };
370                    self.opt_inner = Some((sub_chunk_min_z, inner));
371                },
372            }
373        }
374    }
375}
376
377impl<V, S: RectVolSize, M: Clone> IntoPosIterator for &Chonk<V, S, M> {
378    type IntoIter = ChonkPosIter<V, S, M>;
379
380    fn pos_iter(self, lower_bound: Vec3<i32>, upper_bound: Vec3<i32>) -> Self::IntoIter {
381        Self::IntoIter {
382            outer: ChonkIterHelper::<V, S, M> {
383                sub_chunk_min_z: self.sub_chunk_min_z(lower_bound.z),
384                lower_bound,
385                upper_bound,
386                phantom: PhantomData,
387            },
388            opt_inner: None,
389        }
390    }
391}
392
393impl<'a, V, S: RectVolSize, M: Clone> IntoVolIterator<'a> for &'a Chonk<V, S, M> {
394    type IntoIter = ChonkVolIter<'a, V, S, M>;
395
396    fn vol_iter(self, lower_bound: Vec3<i32>, upper_bound: Vec3<i32>) -> Self::IntoIter {
397        Self::IntoIter {
398            chonk: self,
399            outer: ChonkIterHelper::<V, S, M> {
400                sub_chunk_min_z: self.sub_chunk_min_z(lower_bound.z),
401                lower_bound,
402                upper_bound,
403                phantom: PhantomData,
404            },
405            opt_inner: None,
406        }
407    }
408}
veloren_common/terrain/chonk.rs

veloren_common/terrain/
chonk.rs
