meshgen.rs

//! Heavily based on <https://youtu.be/qnGoGq7DWMc> and <https://github.com/TanTanDev/binary_greedy_mesher_demo>
//! See that video and repo for more information
//!
//! # Finding what faces to draw
//!
//! For more information, see:
//! - <https://www.youtube.com/watch?v=qnGoGq7DWMc>
//!
//! First we build an bitmask of all [`Occupied<_>`] blocks for all 3 directions [`X`], [`Y`], and [`Z`]. We do this for each [`BlockId`].
//!
//! Then we bitshift the occupied masks as followed:
//!
//! ```
//! let mask = 0b01110010 // 1 = solid, 0 = air
//! let shifted = mask << 1;
//! assert_eq!(shifted, 0b11100100); //         0b11100100
//! let inverted = !shifted;
//! assert_eq!(inverted, 0b11100100); //        0b00011011
//! let faces = mask & inverted;
//! //         0b01110010
//! //         0b00011011
//! //         ---------- &
//! //         0b00010010
//! assert_eq!(faces, 0b00010010);
//! ```
//! Which are all of our [`Face<_>`]s that we need to draw in that direction
//!
//! To get all the faces in the other direction, we shift the mask to the right.
//!
//! We apply this 6 times (2 directions, 3 axis) to get all the faces we need to draw.
//!
//! *Note:* Even though our chunk is only 32 bits, we actually need 34 bits, as we also need to know the neighbour chunk blocks adjacent to this to chunk
//!
//! # Merging face vertices
//!
//! For more information, see:
//! - <https://www.youtube.com/watch?v=qnGoGq7DWMc>
//!
//! We start with a [`Face<_>`] in each [`BlockSide`] direction.
//!
//! These faces are a bitmask for each voxel side that needs to be rendered.
//!
//! ```ignore
//! let face = [
//!     0b00000000, // -> x
//!     0b00011000, // |
//!     0b00011100, // v y
//!     0b00011100,
//!     0b00000000,
//! ];
//! ```
//!
//! We check the first block we need to render, at `x = 3, y = 1`, marked with `*`
//!
//! ```ignore
//! let face = [
//!     0b00000000,
//!     0b000*1000,
//!     0b00011100,
//!     0b00011100,
//!     0b00000000,
//! ];
//! ```
//!
//! Then we grow that in the x direction as far as there are bits
//!
//! ```ignore
//! let face = [
//!     0b00000000,
//!     0b000**000,
//!     0b00011100,
//!     0b00011100,
//!     0b00000000,
//! ];
//! ```
//!
//! Then we step each `y` direction which matches this bitmask
//!
//! ```ignore
//! let face = [
//!     0b00000000,
//!     0b000**000,
//!     0b000**100,
//!     0b000**100,
//!     0b00000000,
//! ];
//! ```
//!
//! Once we can't fully match the bitmask any more, we are done, and clear out the bits
//!
//! ```ignore
//! let face = [
//!     0b00000000,
//!     0b00000000,
//!     0b00000100,
//!     0b00000100,
//!     0b00000000,
//! ];
//! ```
//!
//! And repeat for all the vertices we need to render.

use std::marker::PhantomData;

pub(crate) use crate::{state::BlockSide, BlockId};
use crate::{
    utils::grid::{Grid2, Grid3},
    BlockIdMap,
};

pub(crate) struct MeshGen<'a> {
    blocks: &'a Grid3<BlockId, 32, 32, 32>,
    solids: (Occupied<X>, Occupied<Y>, Occupied<Z>),
    transparents: (Occupied<X>, Occupied<Y>, Occupied<Z>),
}

pub(crate) trait Plane {
    fn swizzle(x: u8, y: u8, z: u8) -> (u8, u8, u8);
    fn side<const IS_POSITIVE: bool>() -> BlockSide;
}

#[derive(Default)]
pub(crate) struct X;

impl Plane for X {
    fn swizzle(x: u8, y: u8, z: u8) -> (u8, u8, u8) {
        (z, y, x)
    }

    fn side<const IS_POSITIVE: bool>() -> BlockSide {
        if IS_POSITIVE {
            BlockSide::Right
        } else {
            BlockSide::Left
        }
    }
}
#[derive(Default)]
pub(crate) struct Y;
impl Plane for Y {
    fn swizzle(x: u8, y: u8, z: u8) -> (u8, u8, u8) {
        (x, z, y)
    }
    fn side<const IS_POSITIVE: bool>() -> BlockSide {
        if IS_POSITIVE {
            BlockSide::Back
        } else {
            BlockSide::Front
        }
    }
}
#[derive(Default)]
pub(crate) struct Z;
impl Plane for Z {
    fn swizzle(x: u8, y: u8, z: u8) -> (u8, u8, u8) {
        (x, y, z)
    }
    fn side<const IS_POSITIVE: bool>() -> BlockSide {
        if IS_POSITIVE {
            BlockSide::Top
        } else {
            BlockSide::Bottom
        }
    }
}

#[derive(Default)]
pub(crate) struct Occupied<D> {
    bits: Grid2<u64, 32, 32>,
    pd: PhantomData<D>,
}

impl<D: Plane> Occupied<D> {
    fn from_bits<const IS_POSITIVE: bool>(
        bits: Grid2<u32, 32, 32>,
        blocks: &Grid3<BlockId, 32, 32, 32>,
    ) -> BlockIdMap<Face<D, IS_POSITIVE>> {
        Face::from_iter(bits.iter_copy().flat_map(|(x, y, mut face)| {
            std::iter::from_fn(move || {
                if face == 0 {
                    None
                } else {
                    let z = face.trailing_zeros();
                    face ^= 1 << z;
                    let (x, y, z) = D::swizzle(x, y, z as u8);
                    Some((x, y, z, blocks.get(x, y, z)))
                }
            })
        }))
    }

    fn face_positive(&self, blocks: &Grid3<BlockId, 32, 32, 32>) -> BlockIdMap<Face<D, true>> {
        Self::from_bits(
            self.bits.clone().modify(|b| {
                let shifted = b >> 1;
                let inverted = !shifted;
                let faces = b & inverted;
                // faces is actually 34 bits, because we also have the neighbouring chunks around, so shift to the right and cast to `u32`
                (faces >> 1) as u32
            }),
            blocks,
        )
    }
    fn face_negative(&self, blocks: &Grid3<BlockId, 32, 32, 32>) -> BlockIdMap<Face<D, false>> {
        Self::from_bits(
            self.bits.clone().modify(|b| {
                let shifted = b << 1;
                let inverted = !shifted;
                let faces = b & inverted;
                // faces is actually 34 bits, because we also have the neighbouring chunks around, so shift to the right and cast to `u32`
                (faces >> 1) as u32
            }),
            blocks,
        )
    }
    fn set(&mut self, x: u8, y: u8, z: u8) {
        let (x, y, z) = D::swizzle(x, y, z);
        // we need to add 1 bit because we have the neighbouring chunk blocks around
        *self.bits.get_mut(x, y) |= 1u64 << ((z + 1) as u32);
    }
}

pub(crate) struct Face<D, const IS_POSITIVE: bool> {
    bits: Grid2<u32, 32, 32>,
    pd1: PhantomData<D>,
}

impl<D, const IS_POSITIVE: bool> Default for Face<D, IS_POSITIVE> {
    fn default() -> Self {
        Self {
            bits: Grid2::default(),
            pd1: PhantomData,
        }
    }
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub(crate) struct VertexFace {
    pub(crate) side: BlockSide,
    pub(crate) x: u8,
    pub(crate) y: u8,
    pub(crate) z: u8,
    pub(crate) width: u8,
    pub(crate) height: u8,
}

impl<D: Plane, const IS_POSITIVE: bool> Face<D, IS_POSITIVE> {
    fn from_iter(iter: impl Iterator<Item = (u8, u8, u8, BlockId)>) -> BlockIdMap<Self> {
        let mut map = BlockIdMap::<Self>::default();
        for (x, y, z, id) in iter {
            *map[id].bits.get_mut(z, x) |= 1 << y as u32;
        }

        map
    }

    fn is_empty(&self) -> bool {
        self.bits.is_empty()
    }

    fn side(&self) -> BlockSide {
        D::side::<IS_POSITIVE>()
    }

    fn iter_faces(mut self, mut cb: impl FnMut(VertexFace)) {
        let side = self.side();
        for z in 0..32 {
            let mut y = 0;
            while y < 32 {
                let row = self.bits.get_mut(y, z);
                if *row == 0 {
                    // no faces in this x coordinate
                    y += 1;
                    continue;
                }

                let x = row.trailing_zeros();
                let width = (*row >> x).trailing_ones();
                debug_assert!(width > 0);
                let mask = ((1 << width) - 1) << x; // clear out the bits
                *row &= !mask;

                let mut height = 1;
                // find the width of the rectangle, as far as we can go
                for y2 in y + 1..32 {
                    let row = self.bits.get_mut(y2, z);
                    if *row & mask == mask {
                        *row &= !mask; // also clear out these bits
                        height += 1;
                    } else {
                        break;
                    }
                }
                cb(VertexFace {
                    x: x as u8,
                    y,
                    z,
                    width: width as u8,
                    height: height as u8,
                    side,
                });
            }
        }
    }
}

#[test]
fn validate_occupied_into_faces() {
    println!("validate_occupied_into_faces");
    let mut occupied = Occupied::<X>::default();
    let mut blocks = Grid3::default();
    // Generate a somewhat interesting shape
    for x in 1..=3 {
        for y in 1..=3 {
            for z in 1..=3 {
                occupied.set(x, y, z);
                blocks.set(x, y, z, BlockId::Stone);
            }
        }
    }
    // for x in 3..=4 {
    //     for y in 3..=5 {
    //         for z in 3..=6 {
    //             occupied.set(x, y, z);
    //         }
    //     }
    // }

    let faces_right = occupied.face_positive(&blocks);
    for (block_id, face) in faces_right.into_iter() {
        if face.is_empty() {
            continue;
        }
        assert_eq!(block_id, BlockId::Stone);
        assert_eq!(face.side(), BlockSide::Right);
        let mut faces = Vec::new();
        face.iter_faces(|f| faces.push(f));
        assert_eq!(
            faces.as_slice(),
            &[VertexFace {
                side: BlockSide::Right,
                x: 1,
                y: 1,
                z: 3,
                width: 3,
                height: 3
            }]
        );
    }

    let faces_left = occupied.face_negative(&blocks);
    for (block_id, face) in faces_left.into_iter() {
        if face.is_empty() {
            continue;
        }
        assert_eq!(block_id, BlockId::Stone);
        assert_eq!(face.side(), BlockSide::Left);
        let mut faces = Vec::new();
        face.iter_faces(|f| faces.push(f));
        assert_eq!(
            faces.as_slice(),
            &[VertexFace {
                side: BlockSide::Left,
                x: 1,
                y: 1,
                z: 1,
                width: 3,
                height: 3
            }]
        );
    }
}