use crate::vol::{
BaseVol, IntoPosIterator, IntoVolIterator, RasterableVol, ReadVol, VolSize, WriteVol,
};
use core::{hash::Hash, iter::Iterator, marker::PhantomData, mem};
use hashbrown::HashMap;
use serde::{Deserialize, Serialize};
use vek::*;
#[derive(Debug)]
pub enum ChunkError {
OutOfBounds,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Chunk<V, S: VolSize, M> {
indices: Vec<u8>, vox: Vec<V>,
default: V,
meta: M,
phantom: PhantomData<S>,
}
impl<V, S: VolSize, M> Chunk<V, S, M> {
pub const GROUP_COUNT: Vec3<u32> = Vec3::new(
S::SIZE.x / Self::GROUP_SIZE.x,
S::SIZE.y / Self::GROUP_SIZE.y,
S::SIZE.z / Self::GROUP_SIZE.z,
);
const GROUP_COUNT_TOTAL: u32 = Self::VOLUME / Self::GROUP_VOLUME;
const GROUP_LONG_SIDE_LEN: u32 = 1 << ((Self::GROUP_VOLUME * 4 - 1).count_ones() / 3);
const GROUP_SIZE: Vec3<u32> = Vec3::new(
Self::GROUP_LONG_SIDE_LEN,
Self::GROUP_LONG_SIDE_LEN,
Self::GROUP_VOLUME / (Self::GROUP_LONG_SIDE_LEN * Self::GROUP_LONG_SIDE_LEN),
);
const GROUP_VOLUME: u32 = [Self::VOLUME / 256, 1][(Self::VOLUME < 256) as usize];
const VOLUME: u32 = S::SIZE.x * S::SIZE.y * S::SIZE.z;
pub fn filled(default: V, meta: M) -> Self {
debug_assert!(S::SIZE.x.is_power_of_two());
debug_assert!(S::SIZE.y.is_power_of_two());
debug_assert!(S::SIZE.z.is_power_of_two());
debug_assert!(0 < Self::GROUP_SIZE.x);
debug_assert!(0 < Self::GROUP_SIZE.y);
debug_assert!(0 < Self::GROUP_SIZE.z);
debug_assert!(Self::GROUP_SIZE.x <= 256);
debug_assert!(Self::GROUP_SIZE.y <= 256);
debug_assert!(Self::GROUP_SIZE.z <= 256);
debug_assert!(0 < Self::GROUP_COUNT.x);
debug_assert!(0 < Self::GROUP_COUNT.y);
debug_assert!(0 < Self::GROUP_COUNT.z);
debug_assert!(Self::GROUP_COUNT.x <= 256);
debug_assert!(Self::GROUP_COUNT.y <= 256);
debug_assert!(Self::GROUP_COUNT.z <= 256);
Self {
indices: vec![255; Self::GROUP_COUNT_TOTAL as usize],
vox: Vec::new(),
default,
meta,
phantom: PhantomData,
}
}
pub fn defragment(&mut self)
where
V: Clone + Eq + Hash,
{
let mut map: HashMap<_, Vec<_>> = HashMap::with_capacity(Self::GROUP_COUNT_TOTAL as usize);
let vox = &self.vox;
let default = &self.default;
self.indices
.iter()
.enumerate()
.for_each(|(grp_idx, &base)| {
let start = usize::from(base) * Self::GROUP_VOLUME as usize;
let end = start + Self::GROUP_VOLUME as usize;
if let Some(group) = vox.get(start..end) {
let mut group = group.iter();
let first = group.next().expect("GROUP_VOLUME ≥ 1");
if group.all(|block| block == first) {
map.entry(first).or_default().push(grp_idx);
}
} else {
map.entry(default).or_default().push(grp_idx);
}
});
let (new_default, default_groups) = if let Some((new_default, default_groups)) = map
.into_iter()
.max_by_key(|(_, default_groups)| default_groups.len())
{
(new_default.clone(), default_groups)
} else {
return;
};
let mut new_vox =
Vec::with_capacity(Self::GROUP_COUNT_TOTAL as usize - default_groups.len());
let num_groups = self.num_groups();
self.indices
.iter_mut()
.enumerate()
.for_each(|(grp_idx, base)| {
if default_groups.contains(&grp_idx) {
*base = 255;
} else {
let old_base = usize::from(mem::replace(
base,
(new_vox.len() / Self::GROUP_VOLUME as usize) as u8,
));
if old_base >= num_groups {
new_vox
.resize(new_vox.len() + Self::GROUP_VOLUME as usize, default.clone());
} else {
let start = old_base * Self::GROUP_VOLUME as usize;
let end = start + Self::GROUP_VOLUME as usize;
new_vox.extend_from_slice(&vox[start..end]);
}
}
});
self.vox = new_vox;
self.default = new_default;
}
pub fn metadata(&self) -> &M { &self.meta }
pub fn metadata_mut(&mut self) -> &mut M { &mut self.meta }
pub fn num_groups(&self) -> usize { self.vox.len() / Self::GROUP_VOLUME as usize }
pub fn homogeneous(&self) -> Option<&V> {
if self.num_groups() == 0 {
Some(&self.default)
} else {
None
}
}
#[inline(always)]
fn grp_idx(pos: Vec3<i32>) -> u32 {
let grp_pos = pos.map2(Self::GROUP_SIZE, |e, s| e as u32 / s);
(grp_pos.z * (Self::GROUP_COUNT.y * Self::GROUP_COUNT.x))
+ (grp_pos.y * Self::GROUP_COUNT.x)
+ (grp_pos.x)
}
#[inline(always)]
fn rel_idx(pos: Vec3<i32>) -> u32 {
let rel_pos = pos.map2(Self::GROUP_SIZE, |e, s| e as u32 % s);
(rel_pos.z * (Self::GROUP_SIZE.y * Self::GROUP_SIZE.x))
+ (rel_pos.y * Self::GROUP_SIZE.x)
+ (rel_pos.x)
}
#[inline(always)]
fn idx_unchecked(&self, pos: Vec3<i32>) -> Option<usize> {
let grp_idx = Self::grp_idx(pos);
let rel_idx = Self::rel_idx(pos);
let base = u32::from(self.indices[grp_idx as usize]);
let num_groups = self.vox.len() as u32 / Self::GROUP_VOLUME;
if base >= num_groups {
None
} else {
Some((base * Self::GROUP_VOLUME + rel_idx) as usize)
}
}
#[inline(always)]
fn force_idx_unchecked(&mut self, pos: Vec3<i32>) -> usize
where
V: Clone,
{
let grp_idx = Self::grp_idx(pos);
let rel_idx = Self::rel_idx(pos);
let base = &mut self.indices[grp_idx as usize];
let num_groups = self.vox.len() as u32 / Self::GROUP_VOLUME;
if u32::from(*base) >= num_groups {
*base = num_groups as u8;
self.vox
.extend(std::iter::repeat(self.default.clone()).take(Self::GROUP_VOLUME as usize));
}
(u32::from(*base) * Self::GROUP_VOLUME + rel_idx) as usize
}
#[inline(always)]
fn get_unchecked(&self, pos: Vec3<i32>) -> &V {
match self.idx_unchecked(pos) {
Some(idx) => &self.vox[idx],
None => &self.default,
}
}
#[inline(always)]
fn set_unchecked(&mut self, pos: Vec3<i32>, vox: V) -> V
where
V: Clone + PartialEq,
{
if vox != self.default {
let idx = self.force_idx_unchecked(pos);
mem::replace(&mut self.vox[idx], vox)
} else if let Some(idx) = self.idx_unchecked(pos) {
mem::replace(&mut self.vox[idx], vox)
} else {
self.default.clone()
}
}
}
impl<V, S: VolSize, M> BaseVol for Chunk<V, S, M> {
type Error = ChunkError;
type Vox = V;
}
impl<V, S: VolSize, M> RasterableVol for Chunk<V, S, M> {
const SIZE: Vec3<u32> = S::SIZE;
}
impl<V, S: VolSize, M> ReadVol for Chunk<V, S, M> {
#[inline(always)]
fn get(&self, pos: Vec3<i32>) -> Result<&Self::Vox, Self::Error> {
if !pos
.map2(S::SIZE, |e, s| 0 <= e && e < s as i32)
.reduce_and()
{
Err(Self::Error::OutOfBounds)
} else {
Ok(self.get_unchecked(pos))
}
}
#[inline(always)]
fn get_unchecked(&self, pos: Vec3<i32>) -> &Self::Vox { self.get_unchecked(pos) }
fn for_each_in(&self, mut aabb: Aabb<i32>, mut f: impl FnMut(Vec3<i32>, Self::Vox))
where
Self::Vox: Copy,
{
aabb.intersect(Aabb {
min: Vec3::zero(),
max: S::SIZE.map(|e| e as i32) - 1,
});
for z in aabb.min.z..aabb.max.z + 1 {
for y in aabb.min.y..aabb.max.y + 1 {
for x in aabb.min.x..aabb.max.x + 1 {
f(Vec3::new(x, y, z), *self.get_unchecked(Vec3::new(x, y, z)));
}
}
}
}
}
impl<V: Clone + PartialEq, S: VolSize, M> WriteVol for Chunk<V, S, M> {
#[inline(always)]
fn set(&mut self, pos: Vec3<i32>, vox: Self::Vox) -> Result<Self::Vox, Self::Error> {
if !pos
.map2(S::SIZE, |e, s| 0 <= e && e < s as i32)
.reduce_and()
{
Err(Self::Error::OutOfBounds)
} else {
Ok(self.set_unchecked(pos, vox))
}
}
}
pub struct ChunkPosIter<V, S: VolSize, M> {
lb: Vec3<i32>,
ub: Vec3<i32>,
pos: Vec3<i32>,
phantom: PhantomData<Chunk<V, S, M>>,
}
impl<V, S: VolSize, M> ChunkPosIter<V, S, M> {
fn new(lower_bound: Vec3<i32>, upper_bound: Vec3<i32>) -> Self {
let ub = if lower_bound.map2(upper_bound, |l, u| l < u).reduce_and() {
upper_bound
} else {
lower_bound
};
Self {
lb: lower_bound,
ub,
pos: lower_bound,
phantom: PhantomData,
}
}
}
impl<V, S: VolSize, M> Iterator for ChunkPosIter<V, S, M> {
type Item = Vec3<i32>;
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
if self.pos.z >= self.ub.z {
return None;
}
let res = Some(self.pos);
self.pos.x += 1;
if self.pos.x != self.ub.x && self.pos.x % Chunk::<V, S, M>::GROUP_SIZE.x as i32 != 0 {
return res;
}
self.pos.x = std::cmp::max(
self.lb.x,
(self.pos.x - 1) & !(Chunk::<V, S, M>::GROUP_SIZE.x as i32 - 1),
);
self.pos.y += 1;
if self.pos.y != self.ub.y && self.pos.y % Chunk::<V, S, M>::GROUP_SIZE.y as i32 != 0 {
return res;
}
self.pos.y = std::cmp::max(
self.lb.y,
(self.pos.y - 1) & !(Chunk::<V, S, M>::GROUP_SIZE.y as i32 - 1),
);
self.pos.z += 1;
if self.pos.z != self.ub.z && self.pos.z % Chunk::<V, S, M>::GROUP_SIZE.z as i32 != 0 {
return res;
}
self.pos.z = std::cmp::max(
self.lb.z,
(self.pos.z - 1) & !(Chunk::<V, S, M>::GROUP_SIZE.z as i32 - 1),
);
self.pos.x = (self.pos.x | (Chunk::<V, S, M>::GROUP_SIZE.x as i32 - 1)) + 1;
if self.pos.x < self.ub.x {
return res;
}
self.pos.x = self.lb.x;
self.pos.y = (self.pos.y | (Chunk::<V, S, M>::GROUP_SIZE.y as i32 - 1)) + 1;
if self.pos.y < self.ub.y {
return res;
}
self.pos.y = self.lb.y;
self.pos.z = (self.pos.z | (Chunk::<V, S, M>::GROUP_SIZE.z as i32 - 1)) + 1;
res
}
}
pub struct ChunkVolIter<'a, V, S: VolSize, M> {
chunk: &'a Chunk<V, S, M>,
iter_impl: ChunkPosIter<V, S, M>,
}
impl<'a, V, S: VolSize, M> Iterator for ChunkVolIter<'a, V, S, M> {
type Item = (Vec3<i32>, &'a V);
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
self.iter_impl
.next()
.map(|pos| (pos, self.chunk.get_unchecked(pos)))
}
}
impl<V, S: VolSize, M> Chunk<V, S, M> {
pub fn pos_iter(lower_bound: Vec3<i32>, upper_bound: Vec3<i32>) -> ChunkPosIter<V, S, M> {
ChunkPosIter::<V, S, M>::new(lower_bound, upper_bound)
}
}
impl<'a, V, S: VolSize, M> IntoPosIterator for &'a Chunk<V, S, M> {
type IntoIter = ChunkPosIter<V, S, M>;
fn pos_iter(self, lower_bound: Vec3<i32>, upper_bound: Vec3<i32>) -> Self::IntoIter {
Chunk::<V, S, M>::pos_iter(lower_bound, upper_bound)
}
}
impl<'a, V, S: VolSize, M> IntoVolIterator<'a> for &'a Chunk<V, S, M> {
type IntoIter = ChunkVolIter<'a, V, S, M>;
fn vol_iter(self, lower_bound: Vec3<i32>, upper_bound: Vec3<i32>) -> Self::IntoIter {
ChunkVolIter::<'a, V, S, M> {
chunk: self,
iter_impl: ChunkPosIter::<V, S, M>::new(lower_bound, upper_bound),
}
}
}