Transparency with binary greedy meshing

Motivation

I am currently utilising a variant of TanTan's Binary Greedy Mesher from https://github.com/TanTanDev/binary_greedy_mesher_demo for an ongoing rewrite of Minecraft for the Playstation 1 (yep that one). Mine is translated into C, but is essentially a copy-and-paste of this repo's greedy_mesher_optimized.rs. If you would like to see my implemention in it's full janky glory, it can be found here in the PSXMC repo.

At some later stage I will add blocks that will support partial transparency in the full texture (such as glass) and blocks with opaque textures with gaps (such as the upper half of doors or pistons). This necessitates transparency support, which the old mesher I have written, has. But using this new fancy, shiny and blazingly fast mesher, I want to support transparency there. So, here... we... go.

Context

Creating a mask of the voxels in the scene is done on an absolute basis, i.e. whether there is or isn't a block, marked by a bit on the relevant query axis in the mask array col_face_masks. This is generated using the neat shifting for left/right faces in the cull loop with:

// set if current is solid and next is air.
let col = axis_cols[axis][z][x];
// sample descending axis, and set true when air meets solid
col_face_masks[2 * axis + 0][z][x] = col & !(col << 1);
// sample ascending axis, and set true when air meets solid
col_face_masks[2 * axis + 1][z][x] = col & !(col >> 1);

The last ops ensure that only the bits on the outer faces of a sequence of 1's is set, specifically based on the shift direction. So for instance for a slice (where 0 = air and 1 = block):

Slice	Left Faces	Right Faces
00000 00110 00110 01110 01111	00000 00100 00100 01000 01000	00000 00010 00010 00010 00001

Great, this then gets used to build the plane data by creating hashmap entries for the voxel data for each set bit by retrieving the y (axial-specific) value by invoking u64::trailing_zeros() and combining with the x,z iterator values we are traversing through.

The Problem

We need some way of determining that for any given set bit, there is a following bit (relative to the direction that the face was generated for, by the shift direction) that is still visible through some form of transparency.

More precisely, we want to be able to detect sequential bits that are pairings of solid and transparent voxels and include them both. Let's take an example where 0 = air, 1 = transparent and 2 = solid.

Let's suppose we have the following slice of a chunk, which covers all the cases we need to handle:

Given that we have transparent voxels, we need a way to generate the following masks for the faces in each of the rows (called col in code but easier to understand as rows since it's a direct map to binary visually):

Left Faces	Right Faces
01010 01010 01000 01100 01100	00010 01010 00010 00110 00001

Take a minute to see why the bits that are set as they are, we need anything solid followed by a transparent voxel in the direction of the face to be included. This begs the question... why do we want this? It is because the meshing plane construction for each face considers each bit of the column independently (assuming only one bit surrounded by zeros) by invoking u64::trailing_zeros. However the nature of the implementation means that if there are two successive 1 bits then it will consider each distinctly in mesh creation, which allows us to do this transparent-solid handling in any situation.

Solution

Taking a step back for a second, we can see that the essence of what we are trying to do here is actually detect any voxel that isn't empty as one mask (NE) and then detect any voxel that ins't air and isn't transparent as another mask (NET), then combine them in some manner.

...What?

Let's take our previous example where 0 = air, 1 = transparent and 2 = solid.

Suppose we construct two initial mappings of this slice for each the types mentioned before (NE and NET). Let's do this based on the conditionals mentioned:

Non-Empty (NE)	Non-Empty & Non-Transparent (NET)
01110 01010 01110 01110 01111	00010 00000 01010 00100 00111

In terms of implementation it looks like this:

// solid binary for each x,y,z axis
let mut axis_cols = [[[0u64; CHUNK_SIZE_P]; CHUNK_SIZE_P]; 3];
// solid and non-transparent binary for each x,y,z axis
let mut axis_cols_opaque = [[[0u64; CHUNK_SIZE_P]; CHUNK_SIZE_P]; 3];
// the cull mask to perform greedy slicing, based on solids on previous axis_cols
let mut col_face_masks = [[[0u64; CHUNK_SIZE_P]; CHUNK_SIZE_P]; 6];
#[inline]
fn add_voxel_to_axis_cols(
	b: &crate::voxel::BlockData,
	x: usize,
	y: usize,
	z: usize,
	axis_cols: &mut [[[u64; 34]; 34]; 3],
	axis_cols_opaque: &mut [[[u64; 34]; 34]; 3],
) {
	if !b.block_type.is_solid() {
		return;
	}
	// x,z - y axis
	axis_cols[0][z][x] |= 1u64 << y as u64;
	// z,y - x axis
	axis_cols[1][y][z] |= 1u64 << x as u64;
	// x,y - z axis
	axis_cols[2][y][x] |= 1u64 << z as u64;
	if !b.block_type.is_transparent() {
		// x,z - y axis
		axis_cols_opaque[0][z][x] |= 1u64 << y as u64;
		// z,y - x axis
		axis_cols_opaque[1][y][z] |= 1u64 << x as u64;
		// x,y - z axis
		axis_cols_opaque[2][y][x] |= 1u64 << z as u64;
	}
}

We can combine these two views in order to get a complete understanding of the overlapping sections, which will indicate where we need to include transparent faces. This is simply a logical AND operation between the two views on a per column basis! (Call this result NETC - NET Combined)

Non-Empty (NE)	Non-Empty & Non-Transparent (NET)	Non-Empty & Non-Transparent (NETC)
01110 01010 01110 01110 01111	00010 00000 01010 00100 00111	00010 00000 01010 00100 00111

Using these two tables we can simply repeat the same shifting operations for left and right face detection (left: col & !(col >> 1), right: col & !(col << 1)) for both NE and NETC (we don't care about NET since it was used to construct NETC). This provides us a with a visualisation of visible faces for both solid and transparent voxels simultaneously. Using our example, we can see that the following face mappings are generated:

NETC

Left Face	Right Face
01000 01000 01000 01000 01000	00010 00010 00010 00010 00001

Left Face	Right Face
00010 00000 01010 00100 00100	00010 00000 01010 00100 00001

We are so very close to our final map of all faces with proper transparency handling. Thankfully, the last step is just as simple as the construction of NETC. We just need to apply logical OR between the left and right maps of NE and NETC (i.e. NE_L | NETC_L and NE_R | NETC_R).

Left Face	Right Face
01010 01000 01010 01100 01100	00010 00010 01010 00110 00001

This finalised result can be added as the value for the current column face mask, corresponding to the following implementation:

// face culling
for axis in 0..3 {
	for z in 0..CHUNK_SIZE_P {
		for x in 0..CHUNK_SIZE_P {
			// set if current is solid, and next is air
			let col = axis_cols[axis][z][x];
			// set if current is solid and not transparent and next is air
			let col_opaque = col & axis_cols_opaque[axis][z][x];
			// solid
			let solid_descending = col & !(col << 1);
			let solid_ascending = col & !(col >> 1);
			// Transparent
			let opaque_descending = col_opaque & !(col_opaque << 1);
			let opaque_ascending = col_opaque & !(col_opaque >> 1);
			// Combined solid + transparent faces
			col_face_masks[2 * axis + 0][z][x] = solid_descending | opaque_descending;
			col_face_masks[2 * axis + 1][z][x] = solid_ascending | opaque_ascending;
		}
	}
}

B E H O L D. We have achieved greatness. Now, subsequent (unchanged) plane mesh generation loops will do all the work for us:

// skip padded by adding 1(for x padding) and (z+1) for (z padding)
let mut col = col_face_masks[axis][z + 1][x + 1];
// removes the right most padding value, because it's invalid
col >>= 1;
// removes the left most padding value, because it's invalid
col &= !(1 << CHUNK_SIZE as u64);
while col != 0 {
    let y = col.trailing_zeros();
    // clear least significant set bit
    col &= col - 1;
    // get the voxel position based on axis
    let voxel_pos = match axis {
        0 | 1 => ivec3(x as i32, y as i32, z as i32), // down,up
        2 | 3 => ivec3(y as i32, z as i32, x as i32), // left, right
        _ => ivec3(x as i32, z as i32, y as i32),     // forward, back
    };
	// ... snip ao ...
    let current_voxel = chunks_refs.get_block_no_neighbour(voxel_pos);
    // let current_voxel = chunks_refs.get_block(voxel_pos);
    // we can only greedy mesh same block types + same ambient occlusion
    let block_hash = ao_index | ((current_voxel.block_type as u32) << 9);
    let data = data[axis]
        .entry(block_hash)
        .or_default()
        .entry(y)
        .or_default();
    data[x as usize] |= 1u32 << z as u32;
}

Note specifically, that we get the trailing zeros as the y offset for this voxel and then clear ONLY this current voxel while creating the entry. The voxel position is queried in the world and we subsequently create a hashmap entry making this possible. Simple.

Conclusion

Now, theres an obvious caveat to this... you need to implement your mesh generation and subsequently the rendering pipeline such that transparency ordering is respected from the Z-axis (presumably through depth testing) here in order make use of this. This will however, guarantee that the absolute minimum amount of transparent faces are constructed in the mesh.

This was fun. ye.

Per-Face Transparency

You could take this a step further an allow for per-face transparency controlled at a block level. To do that you refactor the definitions of axis_cols and axis_cols_opaque to be on use per-face arrays instead of per-axis:

// solid binary for each x,y,z face
let mut face_cols = [[[0u64; CHUNK_SIZE_P]; CHUNK_SIZE_P]; 6];
// solid and non-transparent binary for each x,y,z face
let mut face_cols_opaque = [[[0u64; CHUNK_SIZE_P]; CHUNK_SIZE_P]; 6];

Then you change the implementation of add_voxel_to_axis_cols to create per-face array entries and add a bitset (u8) to the block definition that has each bit set for each face in order 0-5 of up, down, left, right, front, back (or whatever your coordinate space is):

// solid binary for each x,y,z face
let mut face_cols = [[[0u64; CHUNK_SIZE_P]; CHUNK_SIZE_P]; 6];
// solid and non-transparent binary for each x,y,z face
let mut face_cols_opaque = [[[0u64; CHUNK_SIZE_P]; CHUNK_SIZE_P]; 6];
// the cull mask to perform greedy slicing, based on solids on previous axis_cols
let mut col_face_masks = [[[0u64; CHUNK_SIZE_P]; CHUNK_SIZE_P]; 6];

#[inline]
fn bitset_at(bitset: u8, i: u8) -> u8 {
	((bitset >> i) & 0b1)
}

#[inline]
fn add_voxel_to_face_cols(
	b: &crate::voxel::BlockData,
	x: usize,
	y: usize,
	z: usize,
	face_cols: &mut [[[u64; 34]; 34]; 6],
	face_cols_opaque: &mut [[[u64; 34]; 34]; 6],
) {
	if !b.block_type.is_solid() {
		return;
	}
	// x,z - y axis
	face_cols[0][z][x] |= 1u64 << y as u64;
	face_cols[1][z][x] |= 1u64 << y as u64;
	// z,y - x axis
	face_cols[2][y][z] |= 1u64 << x as u64;
	face_cols[3][y][z] |= 1u64 << x as u64;
	// x,y - z axis
	face_cols[4][y][x] |= 1u64 << z as u64;
	face_cols[5][y][x] |= 1u64 << z as u64;
	let u8 bitset = b.opaque_faces_bitset;
	// x,z - y axis
	face_cols_opaque[0][z][x] |= bitset_at(bitset, 0u8) << y as u64;
	face_cols_opaque[1][z][x] |= bitset_at(bitset, 1u8) << y as u64;
	// z,y - x axis
	face_cols_opaque[2][y][z] |= bitset_at(bitset, 2u8) << x as u64;
	face_cols_opaque[3][y][z] |= bitset_at(bitset, 3u8) << x as u64;
	// x,y - z axis
	face_cols_opaque[4][y][x] |= bitset_at(bitset, 4u8) << z as u64;
	face_cols_opaque[5][y][x] |= bitset_at(bitset, 5u8) << z as u64;
}

Using the new per-face column and opaque column arrays, we can do face culling on a per-face basis, which finally allows us to have full per-face control over opacity

// face culling
for axis in 0..3 {
	for z in 0..CHUNK_SIZE_P {
		for x in 0..CHUNK_SIZE_P {
			let face_pos = (2 * axis) + 0;
			let face_neg = (2 * axis) + 1;
			// set if current is solid, and next is air
			let col_pos = face_cols[face_pos][z][x];
			let col_neg = face_cols[face_neg][z][x];
			// set if current is solid and not transparent and next is air
			let col_opaque_pos = col_pos & face_cols_opaque[face_pos][z][x];
			let col_opaque_neg = col_neg & face_cols_opaque[face_neg][z][x];
			// solid
			let solid_descending = col_pos & !(col_pos << 1);
			let solid_ascending = col_neg & !(col_neg >> 1);
			// Transparent
			let opaque_descending = col_opaque_pos & !(col_opaque_pos << 1);
			let opaque_ascending = col_opaque_neg & !(col_opaque_neg >> 1);
			// Combined solid + transparent faces
			col_face_masks[face_pos][z][x] = solid_descending | opaque_descending;
			col_face_masks[face_neg][z][x] = solid_ascending | opaque_ascending;
		}
	}
}

It's definitely going to cost a bit more in terms of cycle time, but depending on the level of control you want, this gives you a very efficient way to have complete opacity control. Much faster than a non-binary meshing approach I would think.