1use super::lights::{GRID, LIST_WIDTH};
8use super::{Camera3D, Transform3D, linear};
9use crate::{Color, World};
10use glam::{Mat4, Vec2, Vec3};
11
12pub const MAX_DECALS: usize = 4096;
18
19pub const MAX_DECALS_PER_CLUSTER: usize = 64;
26
27#[repr(C)]
55#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize, serde::Deserialize)]
56#[serde(default)]
57pub struct Decal3D {
58 pub size: Vec3,
61 pub image: u32,
65 pub normal_image: u32,
68 pub uv_min: Vec2,
71 pub uv_max: Vec2,
73 pub color: Color,
76 pub opacity: f32,
79 pub normal_strength: f32,
81 pub roughness: f32,
85 pub metallic: f32,
88 pub angle_fade_start: f32,
92 pub angle_fade_end: f32,
95 pub depth_fade: f32,
98 pub max_distance: f32,
101 pub order: i32,
105 pub layers: u32,
108}
109
110impl Decal3D {
111 pub const NO_IMAGE: u32 = u32::MAX;
113}
114
115impl Default for Decal3D {
116 fn default() -> Self {
117 Self {
118 size: Vec3::ONE,
119 image: 0,
120 normal_image: Self::NO_IMAGE,
121 uv_min: Vec2::ZERO,
122 uv_max: Vec2::ONE,
123 color: Color::WHITE,
124 opacity: 1.0,
125 normal_strength: 1.0,
126 roughness: -1.0,
127 metallic: -1.0,
128 angle_fade_start: 1.0,
129 angle_fade_end: 1.45,
130 depth_fade: 0.25,
131 max_distance: 0.0,
132 order: 0,
133 layers: ReceivesDecals::ALL.0,
134 }
135 }
136}
137
138#[repr(C)]
151#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
152pub struct ReceivesDecals(pub u32);
153
154impl ReceivesDecals {
155 pub const ALL: Self = Self(0xFFFF);
157 pub const NONE: Self = Self(0);
159}
160
161impl Default for ReceivesDecals {
162 fn default() -> Self {
163 Self::ALL
164 }
165}
166
167pub(crate) fn receiver_mask(r: Option<&ReceivesDecals>) -> f32 {
169 r.map_or(ReceivesDecals::ALL.0, |r| r.0 & 0xFFFF) as f32
170}
171
172#[repr(C)]
174#[derive(Debug, Clone, Copy, Default, bytemuck::Pod, bytemuck::Zeroable)]
175pub(crate) struct GpuDecal {
176 pub to_box: [[f32; 4]; 3],
179 pub color: [f32; 4],
181 pub rect: [f32; 4],
183 pub images: [f32; 4],
185 pub fades: [f32; 4],
187 pub surface: [f32; 4],
189}
190
191pub(crate) const DECAL_TEXELS: usize = 8;
193
194#[derive(Clone, Copy)]
196struct Candidate {
197 key: (i32, u32),
198 distance: f32,
199 record: GpuDecal,
200 lo: [usize; 3],
201 hi: [usize; 3],
202}
203
204#[derive(Default)]
207pub(crate) struct DecalGrid {
208 pub records: Vec<GpuDecal>,
209 pub lists: Vec<u32>,
213 candidates: Vec<Candidate>,
214 counts: Vec<u32>,
215 taken: Vec<u32>,
216}
217
218const CELLS: usize = GRID[0] * GRID[1] * GRID[2];
219
220impl DecalGrid {
221 pub fn collect(
228 &mut self,
229 world: &mut World,
230 camera: &Camera3D,
231 depth: [f32; 4],
232 layers: u32,
233 base: usize,
234 first_row: usize,
235 ) {
236 self.records.clear();
237 self.lists.clear();
238 self.candidates.clear();
239 let near = depth[0];
240 let far = camera.far.max(near * 1.001);
241 let view = camera.view();
242 let proj = camera.view_proj() * view.inverse();
243 let mut seq = 0u32;
244 for (t, d) in world.query::<(&Transform3D, &Decal3D)>().iter() {
245 seq += 1;
246 let key = (d.order, seq);
247 if let Some(c) = candidate(t, d, key, camera, view, proj, near, far, depth[1], layers) {
248 self.candidates.push(c);
249 }
250 }
251 if self.candidates.is_empty() {
252 return;
253 }
254 if self.candidates.len() > MAX_DECALS {
255 self.candidates
257 .select_nth_unstable_by(MAX_DECALS, |a, b| a.distance.total_cmp(&b.distance));
258 self.candidates.truncate(MAX_DECALS);
259 }
260 self.candidates.sort_unstable_by_key(|c| c.key);
261 self.records.extend(self.candidates.iter().map(|c| c.record));
262
263 self.counts.clear();
267 self.counts.resize(CELLS, 0);
268 for c in self.candidates.iter().rev() {
269 visit(c.lo, c.hi, |cell| {
270 if (self.counts[cell] as usize) < MAX_DECALS_PER_CLUSTER {
271 self.counts[cell] += 1;
272 }
273 });
274 }
275 let total: usize = self.counts.iter().map(|&n| n as usize).sum();
276 let used = CELLS * 2 + total;
277 self.lists.resize(used.div_ceil(LIST_WIDTH) * LIST_WIDTH, 0);
278 let mut offset = base + CELLS * 2;
279 for cell in 0..CELLS {
280 self.lists[cell * 2] = offset as u32;
281 self.lists[cell * 2 + 1] = self.counts[cell];
282 offset += self.counts[cell] as usize;
283 }
284 self.taken.clear();
285 self.taken.resize(CELLS, 0);
286 let count = self.candidates.len();
287 for (rank, c) in self.candidates.iter().enumerate().rev() {
288 let id = (first_row + rank) as u32;
289 debug_assert!(rank < count);
290 visit(c.lo, c.hi, |cell| {
291 let n = self.counts[cell];
292 let taken = self.taken[cell];
293 if taken < n {
294 let start = self.lists[cell * 2] as usize - base;
295 self.lists[start + (n - 1 - taken) as usize] = id;
296 self.taken[cell] = taken + 1;
297 }
298 });
299 }
300 }
301}
302
303#[allow(clippy::too_many_arguments)]
305fn candidate(
306 t: &Transform3D,
307 d: &Decal3D,
308 key: (i32, u32),
309 camera: &Camera3D,
310 view: Mat4,
311 proj: Mat4,
312 near: f32,
313 far: f32,
314 slices_per_log: f32,
315 layers: u32,
316) -> Option<Candidate> {
317 let mask = d.layers & 0xFFFF;
318 if mask == 0
319 || !t.position.is_finite()
320 || !t.rotation.is_finite()
321 || !t.scale.is_finite()
322 || !d.size.is_finite()
323 || d.size.min_element() <= 0.0
324 || t.scale.min_element() == 0.0
325 || !d.opacity.is_finite()
326 || d.opacity <= 0.0
327 || !d.uv_min.is_finite()
328 || !d.uv_max.is_finite()
329 {
330 return None;
331 }
332 let linear_color = linear(d.color);
333 if !linear_color[..3].iter().all(|v| v.is_finite()) {
334 return None;
335 }
336 let distance = t.position.distance(camera.position);
337 let mut opacity = d.opacity.clamp(0.0, 1.0)
338 * if d.color.a.is_finite() {
339 d.color.a.clamp(0.0, 1.0)
340 } else {
341 1.0
342 };
343 if d.max_distance > 0.0 {
344 if distance > d.max_distance {
345 return None;
346 }
347 let k = ((distance / d.max_distance - 0.75) / 0.25).clamp(0.0, 1.0);
348 opacity *= 1.0 - k * k * (3.0 - 2.0 * k);
349 }
350 if t.rotation.length_squared() < 1e-8 {
351 return None;
352 }
353 let rotation = t.rotation.normalize();
354 let to_world = Mat4::from_scale_rotation_translation(t.scale * d.size, rotation, t.position);
355 let to_box = to_world.inverse();
356 if !to_box.is_finite() {
357 return None;
358 }
359 let mut lo = [0usize; 3];
361 let mut hi = [GRID[0] - 1, GRID[1] - 1, GRID[2] - 1];
362 let mut z_min = f32::INFINITY;
363 let mut z_max = f32::NEG_INFINITY;
364 let mut crosses_near = false;
365 let mut corners = [Vec3::ZERO; 8];
366 for (i, corner) in corners.iter_mut().enumerate() {
367 let local = Vec3::new(
368 if i & 1 == 0 { -0.5 } else { 0.5 },
369 if i & 2 == 0 { -0.5 } else { 0.5 },
370 if i & 4 == 0 { -0.5 } else { 0.5 },
371 );
372 let v = view.transform_point3(to_world.transform_point3(local));
373 *corner = v;
374 z_min = z_min.min(-v.z);
375 z_max = z_max.max(-v.z);
376 crosses_near |= -v.z <= near;
377 }
378 if z_max < near || z_min > far {
379 return None;
380 }
381 if !crosses_near {
382 let mut min = [f32::INFINITY; 2];
383 let mut max = [f32::NEG_INFINITY; 2];
384 for v in &corners {
385 let z = -v.z;
386 for axis in 0..2 {
387 let scale = if axis == 0 { proj.x_axis.x } else { proj.y_axis.y };
388 let p = v[axis] * scale / z;
389 min[axis] = min[axis].min(p);
390 max[axis] = max[axis].max(p);
391 }
392 }
393 for axis in 0..2 {
394 if min[axis] > 1.0 || max[axis] < -1.0 {
395 return None;
396 }
397 let tile = |v: f32| {
398 (((v * 0.5 + 0.5) * GRID[axis] as f32).floor() as i32).clamp(0, GRID[axis] as i32 - 1) as usize
399 };
400 lo[axis] = tile(min[axis]);
401 hi[axis] = tile(max[axis]);
402 }
403 }
404 let slice = |z: f32| {
405 ((z.max(near) / near).ln() * slices_per_log)
406 .floor()
407 .clamp(0.0, (GRID[2] - 1) as f32) as usize
408 };
409 lo[2] = slice(z_min);
410 hi[2] = slice(z_max);
411 let in_layers = |i: u32| (i != Decal3D::NO_IMAGE && i < layers).then_some(i as f32);
412 let (start, end) = (d.angle_fade_start, d.angle_fade_end);
413 let (start, end) = if start.is_finite() && end.is_finite() {
414 let start = start.clamp(0.0, std::f32::consts::FRAC_PI_2);
415 (start, end.clamp(start, std::f32::consts::FRAC_PI_2))
416 } else {
417 (1.0, 1.45)
418 };
419 let rows = [to_box.row(0), to_box.row(1), to_box.row(2)];
420 let record = GpuDecal {
421 to_box: rows.map(|r| r.to_array()),
422 color: [linear_color[0], linear_color[1], linear_color[2], opacity],
423 rect: [d.uv_min.x, d.uv_min.y, d.uv_max.x, d.uv_max.y],
424 images: [
425 in_layers(d.image).unwrap_or(-1.0),
426 in_layers(d.normal_image).unwrap_or(-1.0),
427 if d.normal_strength.is_finite() {
428 d.normal_strength
429 } else {
430 1.0
431 },
432 mask as f32,
433 ],
434 fades: [
435 start.cos(),
436 end.cos().max(0.0),
437 if d.depth_fade.is_finite() {
438 d.depth_fade.clamp(0.0, 1.0)
439 } else {
440 0.0
441 },
442 0.0,
443 ],
444 surface: [
445 if d.roughness.is_finite() {
446 d.roughness.min(1.0)
447 } else {
448 -1.0
449 },
450 if d.metallic.is_finite() {
451 d.metallic.min(1.0)
452 } else {
453 -1.0
454 },
455 0.0,
456 0.0,
457 ],
458 };
459 Some(Candidate {
460 key,
461 distance,
462 record,
463 lo,
464 hi,
465 })
466}
467
468fn visit(lo: [usize; 3], hi: [usize; 3], mut f: impl FnMut(usize)) {
469 for z in lo[2]..=hi[2] {
470 for y in lo[1]..=hi[1] {
471 for x in lo[0]..=hi[0] {
472 f((z * GRID[1] + y) * GRID[0] + x);
473 }
474 }
475 }
476}
477
478#[cfg(test)]
479mod tests {
480 use super::*;
481 use glam::{Quat, vec3};
482
483 fn camera() -> Camera3D {
484 let mut c = Camera3D::new(Vec2::new(800.0, 600.0));
485 c.position = Vec3::ZERO;
486 c.rotation = Quat::IDENTITY;
487 c.far = 100.0;
488 c
489 }
490 fn depth(c: &Camera3D) -> [f32; 4] {
491 [c.near, GRID[2] as f32 / (c.far / c.near).ln(), 0.0, 0.0]
492 }
493 fn collect(w: &mut World, layers: u32) -> DecalGrid {
494 let c = camera();
495 let mut g = DecalGrid::default();
496 g.collect(w, &c, depth(&c), layers, 4096, 100);
497 g
498 }
499
500 #[test]
501 fn only_decals_in_view_are_kept_and_sorted_by_order() {
502 let mut w = World::new();
503 let at = |z: f32| Transform3D::at(vec3(0.0, 0.0, z));
504 w.spawn((
505 at(-10.0),
506 Decal3D {
507 order: 5,
508 ..Default::default()
509 },
510 ));
511 w.spawn((
512 at(-10.0),
513 Decal3D {
514 order: -3,
515 ..Default::default()
516 },
517 ));
518 w.spawn((at(10.0), Decal3D::default())); w.spawn((at(-500.0), Decal3D::default())); w.spawn((
521 at(-10.0),
522 Decal3D {
523 opacity: 0.0,
524 ..Default::default()
525 },
526 ));
527 w.spawn((
528 at(-10.0),
529 Decal3D {
530 layers: 0,
531 ..Default::default()
532 },
533 ));
534 w.spawn((
535 at(-10.0),
536 Decal3D {
537 size: vec3(f32::NAN, 1.0, 1.0),
538 ..Default::default()
539 },
540 ));
541 let g = collect(&mut w, 0);
542 assert_eq!(g.records.len(), 2);
543 let cell = (0..CELLS)
545 .find(|&c| g.lists[c * 2 + 1] == 2)
546 .expect("a cell sees both decals");
547 let start = g.lists[cell * 2] as usize - 4096;
548 assert_eq!(g.lists[start..start + 2], [100, 101]);
549 assert!(g.lists.len().is_multiple_of(LIST_WIDTH));
550 }
551
552 #[test]
553 fn the_box_places_the_image_and_scale_multiplies_size() {
554 let mut w = World::new();
555 w.spawn((
556 Transform3D::at(vec3(2.0, 0.0, -10.0)).scaled(2.0),
557 Decal3D {
558 size: vec3(1.0, 1.0, 0.5),
559 ..Default::default()
560 },
561 ));
562 let g = collect(&mut w, 0);
563 let r = g.records[0].to_box;
564 let to_box = |p: Vec3| {
565 Vec3::new(
566 r[0][..3].iter().zip(p.to_array()).map(|(a, b)| a * b).sum::<f32>() + r[0][3],
567 r[1][..3].iter().zip(p.to_array()).map(|(a, b)| a * b).sum::<f32>() + r[1][3],
568 r[2][..3].iter().zip(p.to_array()).map(|(a, b)| a * b).sum::<f32>() + r[2][3],
569 )
570 };
571 assert!((to_box(vec3(2.0, 0.0, -10.0))).length() < 1e-5);
572 assert!((to_box(vec3(3.0, 0.0, -10.0)) - Vec3::new(0.5, 0.0, 0.0)).length() < 1e-5);
574 assert!((to_box(vec3(2.0, 0.0, -9.5)) - Vec3::new(0.0, 0.0, 0.5)).length() < 1e-5);
575 }
576
577 #[test]
578 fn a_distance_limit_culls_and_fades() {
579 let mut w = World::new();
580 let near = w.spawn((
581 Transform3D::at(vec3(0.0, 0.0, -10.0)),
582 Decal3D {
583 max_distance: 40.0,
584 ..Default::default()
585 },
586 ));
587 w.spawn((
588 Transform3D::at(vec3(0.0, 0.0, -38.0)),
589 Decal3D {
590 max_distance: 40.0,
591 ..Default::default()
592 },
593 ));
594 w.spawn((
595 Transform3D::at(vec3(0.0, 0.0, -50.0)),
596 Decal3D {
597 max_distance: 40.0,
598 ..Default::default()
599 },
600 ));
601 let g = collect(&mut w, 0);
602 assert_eq!(g.records.len(), 2);
603 assert_eq!(g.records[0].color[3], 1.0);
604 assert!(g.records[1].color[3] < 0.5, "fading near its limit");
605 let _ = near;
606 }
607
608 #[test]
609 fn images_outside_the_layers_draw_flat() {
610 let mut w = World::new();
611 w.spawn((
612 Transform3D::at(vec3(0.0, 0.0, -5.0)),
613 Decal3D {
614 image: 3,
615 normal_image: 1,
616 ..Default::default()
617 },
618 ));
619 let g = collect(&mut w, 2);
620 assert_eq!(g.records[0].images[..2], [-1.0, 1.0]);
621 let g = collect(&mut w, 0);
622 assert_eq!(g.records[0].images[..2], [-1.0, -1.0]);
623 }
624
625 #[test]
626 fn full_cells_keep_the_highest_orders() {
627 let mut w = World::new();
628 for i in 0..MAX_DECALS_PER_CLUSTER + 10 {
629 w.spawn((
630 Transform3D::at(vec3(0.0, 0.0, -10.0)),
631 Decal3D {
632 order: i as i32,
633 ..Default::default()
634 },
635 ));
636 }
637 let g = collect(&mut w, 0);
638 assert_eq!(g.records.len(), MAX_DECALS_PER_CLUSTER + 10);
639 let cell = (0..CELLS).find(|&c| g.lists[c * 2 + 1] > 0).unwrap();
640 assert_eq!(g.lists[cell * 2 + 1] as usize, MAX_DECALS_PER_CLUSTER);
641 let start = g.lists[cell * 2] as usize - 4096;
642 let ids = &g.lists[start..start + MAX_DECALS_PER_CLUSTER];
643 assert_eq!(ids[0], 100 + 10, "the 10 lowest orders were dropped");
644 assert_eq!(
645 ids[MAX_DECALS_PER_CLUSTER - 1],
646 100 + (MAX_DECALS_PER_CLUSTER + 9) as u32
647 );
648 assert!(ids.windows(2).all(|p| p[0] < p[1]));
649 }
650
651 #[test]
652 fn more_than_the_cap_keeps_the_nearest() {
653 let mut w = World::new();
654 for i in 0..MAX_DECALS + 5 {
655 let z = -6.0 - (i as f32) * 0.01;
656 w.spawn((
657 Transform3D::at(vec3((i % 7) as f32 * 0.2 - 0.6, 0.0, z)),
658 Decal3D::default(),
659 ));
660 }
661 let g = collect(&mut w, 0);
662 assert_eq!(g.records.len(), MAX_DECALS);
663 }
664
665 #[test]
666 fn a_decal_crossing_the_camera_covers_every_tile() {
667 let mut w = World::new();
668 w.spawn((
669 Transform3D::at(Vec3::ZERO),
670 Decal3D {
671 size: Vec3::splat(4.0),
672 ..Default::default()
673 },
674 ));
675 let g = collect(&mut w, 0);
676 let covered = (0..CELLS).filter(|&c| g.lists[c * 2 + 1] > 0).count();
677 assert!(covered >= GRID[0] * GRID[1], "all tiles in the first slices: {covered}");
678 }
679
680 #[test]
681 fn receivers_carry_their_layers_as_exact_floats() {
682 assert_eq!(receiver_mask(None), 65535.0);
683 assert_eq!(receiver_mask(Some(&ReceivesDecals::NONE)), 0.0);
684 assert_eq!(receiver_mask(Some(&ReceivesDecals(0xFFFF_0002))), 2.0);
685 assert_eq!(ReceivesDecals::default(), ReceivesDecals::ALL);
686 }
687}