use super::lights::{GRID, LIST_WIDTH};
use super::{Camera3D, Transform3D, linear};
use crate::{Color, World};
use glam::{Mat4, Vec2, Vec3};
pub const MAX_DECALS: usize = 4096;
pub const MAX_DECALS_PER_CLUSTER: usize = 64;
#[repr(C)]
#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize, serde::Deserialize)]
#[serde(default)]
pub struct Decal3D {
pub size: Vec3,
pub image: u32,
pub normal_image: u32,
pub uv_min: Vec2,
pub uv_max: Vec2,
pub color: Color,
pub opacity: f32,
pub normal_strength: f32,
pub roughness: f32,
pub metallic: f32,
pub angle_fade_start: f32,
pub angle_fade_end: f32,
pub depth_fade: f32,
pub max_distance: f32,
pub order: i32,
pub layers: u32,
}
impl Decal3D {
pub const NO_IMAGE: u32 = u32::MAX;
}
impl Default for Decal3D {
fn default() -> Self {
Self {
size: Vec3::ONE,
image: 0,
normal_image: Self::NO_IMAGE,
uv_min: Vec2::ZERO,
uv_max: Vec2::ONE,
color: Color::WHITE,
opacity: 1.0,
normal_strength: 1.0,
roughness: -1.0,
metallic: -1.0,
angle_fade_start: 1.0,
angle_fade_end: 1.45,
depth_fade: 0.25,
max_distance: 0.0,
order: 0,
layers: ReceivesDecals::ALL.0,
}
}
}
#[repr(C)]
#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct ReceivesDecals(pub u32);
impl ReceivesDecals {
pub const ALL: Self = Self(0xFFFF);
pub const NONE: Self = Self(0);
}
impl Default for ReceivesDecals {
fn default() -> Self {
Self::ALL
}
}
pub(crate) fn receiver_mask(r: Option<&ReceivesDecals>) -> f32 {
r.map_or(ReceivesDecals::ALL.0, |r| r.0 & 0xFFFF) as f32
}
#[repr(C)]
#[derive(Debug, Clone, Copy, Default, bytemuck::Pod, bytemuck::Zeroable)]
pub(crate) struct GpuDecal {
pub to_box: [[f32; 4]; 3],
pub color: [f32; 4],
pub rect: [f32; 4],
pub images: [f32; 4],
pub fades: [f32; 4],
pub surface: [f32; 4],
}
pub(crate) const DECAL_TEXELS: usize = 8;
#[derive(Clone, Copy)]
struct Candidate {
key: (i32, u32),
distance: f32,
record: GpuDecal,
lo: [usize; 3],
hi: [usize; 3],
}
#[derive(Default)]
pub(crate) struct DecalGrid {
pub records: Vec<GpuDecal>,
pub lists: Vec<u32>,
candidates: Vec<Candidate>,
counts: Vec<u32>,
taken: Vec<u32>,
}
const CELLS: usize = GRID[0] * GRID[1] * GRID[2];
impl DecalGrid {
pub fn collect(
&mut self,
world: &mut World,
camera: &Camera3D,
depth: [f32; 4],
layers: u32,
base: usize,
first_row: usize,
) {
self.records.clear();
self.lists.clear();
self.candidates.clear();
let near = depth[0];
let far = camera.far.max(near * 1.001);
let view = camera.view();
let proj = camera.view_proj() * view.inverse();
let mut seq = 0u32;
for (t, d) in world.query::<(&Transform3D, &Decal3D)>().iter() {
seq += 1;
let key = (d.order, seq);
if let Some(c) = candidate(t, d, key, camera, view, proj, near, far, depth[1], layers) {
self.candidates.push(c);
}
}
if self.candidates.is_empty() {
return;
}
if self.candidates.len() > MAX_DECALS {
self.candidates
.select_nth_unstable_by(MAX_DECALS, |a, b| a.distance.total_cmp(&b.distance));
self.candidates.truncate(MAX_DECALS);
}
self.candidates.sort_unstable_by_key(|c| c.key);
self.records.extend(self.candidates.iter().map(|c| c.record));
self.counts.clear();
self.counts.resize(CELLS, 0);
for c in self.candidates.iter().rev() {
visit(c.lo, c.hi, |cell| {
if (self.counts[cell] as usize) < MAX_DECALS_PER_CLUSTER {
self.counts[cell] += 1;
}
});
}
let total: usize = self.counts.iter().map(|&n| n as usize).sum();
let used = CELLS * 2 + total;
self.lists.resize(used.div_ceil(LIST_WIDTH) * LIST_WIDTH, 0);
let mut offset = base + CELLS * 2;
for cell in 0..CELLS {
self.lists[cell * 2] = offset as u32;
self.lists[cell * 2 + 1] = self.counts[cell];
offset += self.counts[cell] as usize;
}
self.taken.clear();
self.taken.resize(CELLS, 0);
let count = self.candidates.len();
for (rank, c) in self.candidates.iter().enumerate().rev() {
let id = (first_row + rank) as u32;
debug_assert!(rank < count);
visit(c.lo, c.hi, |cell| {
let n = self.counts[cell];
let taken = self.taken[cell];
if taken < n {
let start = self.lists[cell * 2] as usize - base;
self.lists[start + (n - 1 - taken) as usize] = id;
self.taken[cell] = taken + 1;
}
});
}
}
}
#[allow(clippy::too_many_arguments)]
fn candidate(
t: &Transform3D,
d: &Decal3D,
key: (i32, u32),
camera: &Camera3D,
view: Mat4,
proj: Mat4,
near: f32,
far: f32,
slices_per_log: f32,
layers: u32,
) -> Option<Candidate> {
let mask = d.layers & 0xFFFF;
if mask == 0
|| !t.position.is_finite()
|| !t.rotation.is_finite()
|| !t.scale.is_finite()
|| !d.size.is_finite()
|| d.size.min_element() <= 0.0
|| t.scale.min_element() == 0.0
|| !d.opacity.is_finite()
|| d.opacity <= 0.0
|| !d.uv_min.is_finite()
|| !d.uv_max.is_finite()
{
return None;
}
let linear_color = linear(d.color);
if !linear_color[..3].iter().all(|v| v.is_finite()) {
return None;
}
let distance = t.position.distance(camera.position);
let mut opacity = d.opacity.clamp(0.0, 1.0)
* if d.color.a.is_finite() {
d.color.a.clamp(0.0, 1.0)
} else {
1.0
};
if d.max_distance > 0.0 {
if distance > d.max_distance {
return None;
}
let k = ((distance / d.max_distance - 0.75) / 0.25).clamp(0.0, 1.0);
opacity *= 1.0 - k * k * (3.0 - 2.0 * k);
}
if t.rotation.length_squared() < 1e-8 {
return None;
}
let rotation = t.rotation.normalize();
let to_world = Mat4::from_scale_rotation_translation(t.scale * d.size, rotation, t.position);
let to_box = to_world.inverse();
if !to_box.is_finite() {
return None;
}
let mut lo = [0usize; 3];
let mut hi = [GRID[0] - 1, GRID[1] - 1, GRID[2] - 1];
let mut z_min = f32::INFINITY;
let mut z_max = f32::NEG_INFINITY;
let mut crosses_near = false;
let mut corners = [Vec3::ZERO; 8];
for (i, corner) in corners.iter_mut().enumerate() {
let local = Vec3::new(
if i & 1 == 0 { -0.5 } else { 0.5 },
if i & 2 == 0 { -0.5 } else { 0.5 },
if i & 4 == 0 { -0.5 } else { 0.5 },
);
let v = view.transform_point3(to_world.transform_point3(local));
*corner = v;
z_min = z_min.min(-v.z);
z_max = z_max.max(-v.z);
crosses_near |= -v.z <= near;
}
if z_max < near || z_min > far {
return None;
}
if !crosses_near {
let mut min = [f32::INFINITY; 2];
let mut max = [f32::NEG_INFINITY; 2];
for v in &corners {
let z = -v.z;
for axis in 0..2 {
let scale = if axis == 0 { proj.x_axis.x } else { proj.y_axis.y };
let p = v[axis] * scale / z;
min[axis] = min[axis].min(p);
max[axis] = max[axis].max(p);
}
}
for axis in 0..2 {
if min[axis] > 1.0 || max[axis] < -1.0 {
return None;
}
let tile = |v: f32| {
(((v * 0.5 + 0.5) * GRID[axis] as f32).floor() as i32).clamp(0, GRID[axis] as i32 - 1) as usize
};
lo[axis] = tile(min[axis]);
hi[axis] = tile(max[axis]);
}
}
let slice = |z: f32| {
((z.max(near) / near).ln() * slices_per_log)
.floor()
.clamp(0.0, (GRID[2] - 1) as f32) as usize
};
lo[2] = slice(z_min);
hi[2] = slice(z_max);
let in_layers = |i: u32| (i != Decal3D::NO_IMAGE && i < layers).then_some(i as f32);
let (start, end) = (d.angle_fade_start, d.angle_fade_end);
let (start, end) = if start.is_finite() && end.is_finite() {
let start = start.clamp(0.0, std::f32::consts::FRAC_PI_2);
(start, end.clamp(start, std::f32::consts::FRAC_PI_2))
} else {
(1.0, 1.45)
};
let rows = [to_box.row(0), to_box.row(1), to_box.row(2)];
let record = GpuDecal {
to_box: rows.map(|r| r.to_array()),
color: [linear_color[0], linear_color[1], linear_color[2], opacity],
rect: [d.uv_min.x, d.uv_min.y, d.uv_max.x, d.uv_max.y],
images: [
in_layers(d.image).unwrap_or(-1.0),
in_layers(d.normal_image).unwrap_or(-1.0),
if d.normal_strength.is_finite() {
d.normal_strength
} else {
1.0
},
mask as f32,
],
fades: [
start.cos(),
end.cos().max(0.0),
if d.depth_fade.is_finite() {
d.depth_fade.clamp(0.0, 1.0)
} else {
0.0
},
0.0,
],
surface: [
if d.roughness.is_finite() {
d.roughness.min(1.0)
} else {
-1.0
},
if d.metallic.is_finite() {
d.metallic.min(1.0)
} else {
-1.0
},
0.0,
0.0,
],
};
Some(Candidate {
key,
distance,
record,
lo,
hi,
})
}
fn visit(lo: [usize; 3], hi: [usize; 3], mut f: impl FnMut(usize)) {
for z in lo[2]..=hi[2] {
for y in lo[1]..=hi[1] {
for x in lo[0]..=hi[0] {
f((z * GRID[1] + y) * GRID[0] + x);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use glam::{Quat, vec3};
fn camera() -> Camera3D {
let mut c = Camera3D::new(Vec2::new(800.0, 600.0));
c.position = Vec3::ZERO;
c.rotation = Quat::IDENTITY;
c.far = 100.0;
c
}
fn depth(c: &Camera3D) -> [f32; 4] {
[c.near, GRID[2] as f32 / (c.far / c.near).ln(), 0.0, 0.0]
}
fn collect(w: &mut World, layers: u32) -> DecalGrid {
let c = camera();
let mut g = DecalGrid::default();
g.collect(w, &c, depth(&c), layers, 4096, 100);
g
}
#[test]
fn only_decals_in_view_are_kept_and_sorted_by_order() {
let mut w = World::new();
let at = |z: f32| Transform3D::at(vec3(0.0, 0.0, z));
w.spawn((
at(-10.0),
Decal3D {
order: 5,
..Default::default()
},
));
w.spawn((
at(-10.0),
Decal3D {
order: -3,
..Default::default()
},
));
w.spawn((at(10.0), Decal3D::default())); w.spawn((at(-500.0), Decal3D::default())); w.spawn((
at(-10.0),
Decal3D {
opacity: 0.0,
..Default::default()
},
));
w.spawn((
at(-10.0),
Decal3D {
layers: 0,
..Default::default()
},
));
w.spawn((
at(-10.0),
Decal3D {
size: vec3(f32::NAN, 1.0, 1.0),
..Default::default()
},
));
let g = collect(&mut w, 0);
assert_eq!(g.records.len(), 2);
let cell = (0..CELLS)
.find(|&c| g.lists[c * 2 + 1] == 2)
.expect("a cell sees both decals");
let start = g.lists[cell * 2] as usize - 4096;
assert_eq!(g.lists[start..start + 2], [100, 101]);
assert!(g.lists.len().is_multiple_of(LIST_WIDTH));
}
#[test]
fn the_box_places_the_image_and_scale_multiplies_size() {
let mut w = World::new();
w.spawn((
Transform3D::at(vec3(2.0, 0.0, -10.0)).scaled(2.0),
Decal3D {
size: vec3(1.0, 1.0, 0.5),
..Default::default()
},
));
let g = collect(&mut w, 0);
let r = g.records[0].to_box;
let to_box = |p: Vec3| {
Vec3::new(
r[0][..3].iter().zip(p.to_array()).map(|(a, b)| a * b).sum::<f32>() + r[0][3],
r[1][..3].iter().zip(p.to_array()).map(|(a, b)| a * b).sum::<f32>() + r[1][3],
r[2][..3].iter().zip(p.to_array()).map(|(a, b)| a * b).sum::<f32>() + r[2][3],
)
};
assert!((to_box(vec3(2.0, 0.0, -10.0))).length() < 1e-5);
assert!((to_box(vec3(3.0, 0.0, -10.0)) - Vec3::new(0.5, 0.0, 0.0)).length() < 1e-5);
assert!((to_box(vec3(2.0, 0.0, -9.5)) - Vec3::new(0.0, 0.0, 0.5)).length() < 1e-5);
}
#[test]
fn a_distance_limit_culls_and_fades() {
let mut w = World::new();
let near = w.spawn((
Transform3D::at(vec3(0.0, 0.0, -10.0)),
Decal3D {
max_distance: 40.0,
..Default::default()
},
));
w.spawn((
Transform3D::at(vec3(0.0, 0.0, -38.0)),
Decal3D {
max_distance: 40.0,
..Default::default()
},
));
w.spawn((
Transform3D::at(vec3(0.0, 0.0, -50.0)),
Decal3D {
max_distance: 40.0,
..Default::default()
},
));
let g = collect(&mut w, 0);
assert_eq!(g.records.len(), 2);
assert_eq!(g.records[0].color[3], 1.0);
assert!(g.records[1].color[3] < 0.5, "fading near its limit");
let _ = near;
}
#[test]
fn images_outside_the_layers_draw_flat() {
let mut w = World::new();
w.spawn((
Transform3D::at(vec3(0.0, 0.0, -5.0)),
Decal3D {
image: 3,
normal_image: 1,
..Default::default()
},
));
let g = collect(&mut w, 2);
assert_eq!(g.records[0].images[..2], [-1.0, 1.0]);
let g = collect(&mut w, 0);
assert_eq!(g.records[0].images[..2], [-1.0, -1.0]);
}
#[test]
fn full_cells_keep_the_highest_orders() {
let mut w = World::new();
for i in 0..MAX_DECALS_PER_CLUSTER + 10 {
w.spawn((
Transform3D::at(vec3(0.0, 0.0, -10.0)),
Decal3D {
order: i as i32,
..Default::default()
},
));
}
let g = collect(&mut w, 0);
assert_eq!(g.records.len(), MAX_DECALS_PER_CLUSTER + 10);
let cell = (0..CELLS).find(|&c| g.lists[c * 2 + 1] > 0).unwrap();
assert_eq!(g.lists[cell * 2 + 1] as usize, MAX_DECALS_PER_CLUSTER);
let start = g.lists[cell * 2] as usize - 4096;
let ids = &g.lists[start..start + MAX_DECALS_PER_CLUSTER];
assert_eq!(ids[0], 100 + 10, "the 10 lowest orders were dropped");
assert_eq!(
ids[MAX_DECALS_PER_CLUSTER - 1],
100 + (MAX_DECALS_PER_CLUSTER + 9) as u32
);
assert!(ids.windows(2).all(|p| p[0] < p[1]));
}
#[test]
fn more_than_the_cap_keeps_the_nearest() {
let mut w = World::new();
for i in 0..MAX_DECALS + 5 {
let z = -6.0 - (i as f32) * 0.01;
w.spawn((
Transform3D::at(vec3((i % 7) as f32 * 0.2 - 0.6, 0.0, z)),
Decal3D::default(),
));
}
let g = collect(&mut w, 0);
assert_eq!(g.records.len(), MAX_DECALS);
}
#[test]
fn a_decal_crossing_the_camera_covers_every_tile() {
let mut w = World::new();
w.spawn((
Transform3D::at(Vec3::ZERO),
Decal3D {
size: Vec3::splat(4.0),
..Default::default()
},
));
let g = collect(&mut w, 0);
let covered = (0..CELLS).filter(|&c| g.lists[c * 2 + 1] > 0).count();
assert!(covered >= GRID[0] * GRID[1], "all tiles in the first slices: {covered}");
}
#[test]
fn receivers_carry_their_layers_as_exact_floats() {
assert_eq!(receiver_mask(None), 65535.0);
assert_eq!(receiver_mask(Some(&ReceivesDecals::NONE)), 0.0);
assert_eq!(receiver_mask(Some(&ReceivesDecals(0xFFFF_0002))), 2.0);
assert_eq!(ReceivesDecals::default(), ReceivesDecals::ALL);
}
}