alex/beta-minecraft-rust
Minecraft Beta 1.7.3 Rewrite
BRANCH main
SNAPSHOT Draw terrain GPU-driven from packed per-section buffers with GPU occlusion culling, add a render distance slider (2-128) with a quad/disk shape, cut chunk bookkeeping at high render distances, and fix a light underflow at y=0
DOWNLOAD
root crates client src render mesher pack.rs
//! Packs quads into the layout `terrain.slang` reads: deduplicated shapes, lights and tints, and
//! 8-byte faces that reference them, grouped by layer and facing.
use std::sync::atomic::{AtomicU64, Ordering};
use rustc_hash::FxHashMap;
use super::Quad;
use crate::assets::RgbaImage;
/// Facings in the order of `SIDE_OFFSETS`, then quads that face no axis.
pub const FACINGS: usize = 7;
/// Solid and cutout faces per facing, then translucent faces, which are never facing culled.
pub const GROUPS: usize = 2 * FACINGS + 1;
/// Quads one section may have, the reach of the shared index buffer.
pub const MAX_QUADS: usize = 1 << 18;
const MAX_SHAPES: usize = 1 << 20;
const MAX_TINTS: usize = 1 << 14;
/// Bytes of a shape: per corner, the block-relative position, shade and texture coordinates.
const SHAPE_WORDS: usize = 12;
/// Tiles without a texel the alpha test discards, as 256 bits.
static OPAQUE_TILES: [AtomicU64; 4] = [const { AtomicU64::new(0) }; 4];
/// Finds the atlas tiles whose texels all pass the alpha test, apart from `transparent` ones
/// that animate. Quads textured only by those draw without it.
pub fn set_atlas(atlas: &RgbaImage, transparent: &[u8]) {
let size = (atlas.width / 16) as usize;
let opaque = |tile: usize| {
let (x, y) = (tile % 16 * size, tile / 16 * size);
(y..y + size).all(|row| {
let start = (row * atlas.width as usize + x) * 4;
atlas.pixels[start..start + size * 4]
.as_chunks::<4>()
.0
.iter()
.all(|texel| f32::from(texel[3]) / 255.0 > 0.1)
})
};
for (word, bits) in OPAQUE_TILES.iter().enumerate() {
let tiles = (0..64)
.filter(|bit| {
let tile = word * 64 + bit;
opaque(tile) && !transparent.contains(&(tile as u8))
})
.fold(0, |bits, bit| bits | 1 << bit);
bits.store(tiles, Ordering::Relaxed);
}
}
fn opaque_tile(tile: u32) -> bool {
OPAQUE_TILES[(tile / 64) as usize].load(Ordering::Relaxed) >> (tile % 64) & 1 != 0
}
/// A section's geometry, ready for upload.
#[derive(Default)]
pub struct SectionMesh {
/// Shapes, then lights, tints and faces, each starting at a 16-byte boundary.
pub data: Vec<u32>,
/// Byte offsets of the lights, tints and faces in `data`; shapes start at 0.
pub lights: u32,
pub tints: u32,
pub faces: u32,
/// Faces per group, stored one group after the other.
pub counts: [u32; GROUPS],
/// Section-relative block bounds of all geometry: minimum x, y, z, then maximum.
pub bounds: [i8; 6],
/// Per facing, the plane the camera must be beyond for any of its faces to show: the lowest
/// plane rounded down for positive facings, the highest rounded up for negative ones.
pub planes: [i8; 6],
}
impl SectionMesh {
pub fn is_empty(&self) -> bool {
self.counts.iter().all(|&count| count == 0)
}
pub fn pack(opaque: &[Quad], translucent: &[Quad]) -> Self {
let mut packer = Packer {
min: [u32::MAX; 3],
planes: [0, u32::MAX, 0, u32::MAX, 0, u32::MAX],
..Packer::default()
};
for quad in opaque {
packer.add(quad, false);
}
for quad in translucent {
packer.add(quad, true);
}
packer.finish()
}
}
#[derive(Default)]
struct Packer {
shapes: Dedup<[u32; SHAPE_WORDS]>,
lights: Dedup<[u32; 4]>,
tints: Dedup<u32>,
groups: [Vec<[u32; 2]>; GROUPS],
quads: usize,
/// Quantized bounds of all corners.
min: [u32; 3],
max: [u32; 3],
/// Quantized planes, see [`SectionMesh::planes`].
planes: [u32; 6],
}
struct Dedup<T> {
indices: FxHashMap<T, u32>,
items: Vec<T>,
}
impl<T> Default for Dedup<T> {
fn default() -> Self {
Self {
indices: FxHashMap::default(),
items: Vec::new(),
}
}
}
impl<T: Copy + Eq + std::hash::Hash> Dedup<T> {
fn index(&mut self, item: T) -> u32 {
*self.indices.entry(item).or_insert_with(|| {
self.items.push(item);
self.items.len() as u32 - 1
})
}
}
impl Packer {
fn add(&mut self, quad: &Quad, translucent: bool) {
if self.quads == MAX_QUADS
|| self.shapes.items.len() == MAX_SHAPES
|| self.tints.items.len() == MAX_TINTS
{
tracing::warn!("section exceeds the packed mesh limits, dropping quads");
return;
}
self.quads += 1;
let v = &quad.vertices;
let positions = v.map(|v| [v.xy & 0xFFFF, v.xy >> 16, v.z_shade & 0xFFFF]);
let [bx, by, bz] = quad.block.map(u32::from);
// Block-relative positions wrap around 16 bits: the shader adds the block back
let offset = [bx, by, bz].map(|c| c << 11);
let mut shape = [0; SHAPE_WORDS];
for (corner, (vertex, p)) in v.iter().zip(&positions).enumerate() {
let [x, y, z] = std::array::from_fn(|a| p[a].wrapping_sub(offset[a]) & 0xFFFF);
shape[corner * 3] = x | y << 16;
shape[corner * 3 + 1] = z | vertex.z_shade & 0xFFFF_0000;
shape[corner * 3 + 2] = vertex.uv;
}
let shape = self.shapes.index(shape);
let light = self.lights.index(v.map(|v| v.light));
let tint = self.tints.index(v[0].tint);
for p in &positions {
self.min = std::array::from_fn(|a| self.min[a].min(p[a]));
self.max = std::array::from_fn(|a| self.max[a].max(p[a]));
}
let group = if translucent {
GROUPS - 1
} else {
let facing = facing(&positions);
if facing < 6 {
let plane = positions[0][AXES[facing]];
let bound = &mut self.planes[facing];
*bound = if facing % 2 == 1 {
(*bound).min(plane)
} else {
(*bound).max(plane)
};
}
let solid = !quad.cutout && opaque_texture(v);
usize::from(!solid) * FACINGS + facing
};
self.groups[group].push([bx | by << 4 | bz << 8 | shape << 12, light | tint << 18]);
}
fn finish(self) -> SectionMesh {
if self.quads == 0 {
return SectionMesh::default();
}
let mut data: Vec<u32> = self.shapes.items.as_flattened().to_vec();
let region = |data: &mut Vec<u32>, words: &[u32]| {
data.resize(data.len().next_multiple_of(4), 0);
let offset = data.len() as u32 * 4;
data.extend_from_slice(words);
offset
};
let lights = region(&mut data, self.lights.items.as_flattened());
let tints = region(&mut data, &self.tints.items);
let faces = region(&mut data, &[]);
for group in &self.groups {
data.extend(group.as_flattened());
}
let blocks = |q: u32| q as f32 / 2048.0 - 8.0;
let min = self.min.map(|q| blocks(q).floor() as i8);
let max = self.max.map(|q| blocks(q).ceil() as i8);
SectionMesh {
data,
lights,
tints,
faces,
counts: self.groups.each_ref().map(|group| group.len() as u32),
bounds: [min[0], min[1], min[2], max[0], max[1], max[2]],
planes: std::array::from_fn(|facing| {
let plane = blocks(self.planes[facing]);
(if facing % 2 == 1 {
plane.floor()
} else {
plane.ceil()
}) as i8
}),
}
}
}
/// The axis each facing points along.
const AXES: [usize; 6] = [1, 1, 2, 2, 0, 0];
/// The facing of a quad that lies in an axis plane, from the winding of its corners, or 6.
fn facing(p: &[[u32; 3]; 4]) -> usize {
let mut planar = (0..3).filter(|&a| p.iter().all(|c| c[a] == p[0][a]));
let (Some(axis), None) = (planar.next(), planar.next()) else {
return 6;
};
let edge =
|i: usize| -> [i64; 3] { std::array::from_fn(|a| i64::from(p[i][a]) - i64::from(p[0][a])) };
// The axis component of the winding's normal
let normal = |a: [i64; 3], b: [i64; 3]| {
let (u, v) = ((axis + 1) % 3, (axis + 2) % 3);
a[u] * b[v] - a[v] * b[u]
};
let mut n = normal(edge(1), edge(2));
if n == 0 {
n = normal(edge(2), edge(3));
}
match (axis, n) {
(_, 0) => 6,
(1, n) => usize::from(n > 0),
(2, n) => 2 + usize::from(n > 0),
(_, n) => 4 + usize::from(n > 0),
}
}
/// Whether every atlas tile the quad samples passes the alpha test everywhere.
fn opaque_texture(v: &[super::Vertex; 4]) -> bool {
let (u, w) = (v.map(|v| v.uv & 0xFFFF), v.map(|v| v.uv >> 16));
let range = |c: [u32; 4]| (c.iter().min().unwrap() >> 12)..=(c.iter().max().unwrap() >> 12);
range(w).all(|row| range(u).all(|column| opaque_tile(row * 16 + column)))
}