Supporting Transparent Voxel Textures

EngineersBox commented 4 months ago

Motivation

I am currently utilising the implementation of the Binary Greedy Mesher from this repo for a re-write 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.

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 your 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:

NE

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.

You might wonder.. why is this an issue as opposed to a PR? Well that's because I wanted to post this here for discussion and leave it open to whether this is used by anyone (also up to repo maintainers as to whether they want to do anything with this at all). That being said, if this does indeed work as I have outlined (and I'm not a complete moron that has made an obvious mistake) then by all means I'm happy to PR a version of the mesher that has this transparency support.

This was fun. ye.

Edits: Fixed a bunch of stuff in the logic and naming. Works seamlessly now.

EngineersBox commented 4 months ago

I've attached this screenshot for posterity, to show that the above really does work. Please excuse the weird interleaving of glass and plank textures, some weird texture reference issues. You can make out the transparency is correct though.

Screenshot 2024-05-10 at 22 00 17

EngineersBox commented 4 months ago

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.

duckdoom5 commented 4 months ago

Nice write-up! The only problem I see is that you actually want to separate your opaque mesh from your transparent mesh so you can render them in the correct order. (overdraw is a real problem).

The way I solved it, is to just do 2 'passes' (read called twice). First I keep track of some meta data for optimization, which tells me if the chunk contains any transparent blocks at all. No transparent blocks? No need for the second pass.

The first (opaque) pass, uses the code in this repo as is, with one minor change: if the chunk contains transparent blocks, I test for opaque blocks. (Meaning anything transparent and air is ignored). That way the opaque faces are generated between air and transparent blocks. Otherwise it just tests for non-air.

The second (transparent) pass, tests for non-air. So only transparent blocks are marked. That way we get faces for all transparent blocks that touch air, and don't add any faces between transparent and solid blocks. (We don't want those, since the solid blocks already have that face.). Only problem left, is that we now need to get rid of the solid faces that have also been added. Took me a while to figure that out, but it's actually very simple.

All we need to do is: right before we construct the ao value and want to add the block type to the hashmap, we check if we are in the transparent pass. If we are we ignore any block types that are not transparent (continue;). Easy as that 😁

Now is this the most efficient solution? Probably not, but it does keep the code 'simple' and the opaque pass is not more expensive. (That would be the case, in your proposal). The thing to keep in mind though is that transparency is relatively rare, compared to opaque, so it likely doesn't even matter that the transparent case does everything twice.

EngineersBox commented 4 months ago

Thanks for the reply and alternate implementation suggestion. This makes total sense for a regular engine with z-buffering and the need to use sort for transparency ordering.

I guess this is where it differs for me is that I have only an ordering table, so ordering is guaranteed here by nature of inserting into the table based on Z position. So they are rendered in order correctly.

The only thing I'm not understanding is where the overdraw is? All faces between touching transparent objects are culled (same as solid), they have normals to mass culling when rendering is possible to avoid reverse direction overdraw (same as solid). I guess if you mean separation by a single voxel gap? Then I guess it depends on how you want that to behave if you want it to clear all transparency behind all leave it visible.

I think I'm missing something from your explanation. Can you elaborate on the overdraw? (I've spent way too long in PS1 land so my brain is wired to the jank of that now, so normal/sane rendering is a bit fuzzy for me atm).

duckdoom5 commented 4 months ago

Yeah in traditional rendering, you have to sort your opaque object front to back, so you render the object in view first and don't render the object hidden behind others (because the depth test will be culling them). (If you shade a pixel multiple times, that's called overdraw.)

With transparent objects, you are forced to sort them back to front and after opaque objects, otherwise you won't get the correct blending. Front to back means you will be shading pixels multiple times though, so best to avoid that as much as possible

TanTanDev / binary_greedy_mesher_demo