tawasuyu/llimphi

1//! Picking/edición por **raycast de voxels** — la mecánica núcleo de un juego
2//! voxel (mirar → bloque). DDA Amanatides-Woo en CPU sobre un [`VoxelGrid`],
3//! espejo del traversal que hace el shader. Devuelve el voxel sólido golpeado,
4//! la cara de entrada (normal) y la celda vacía adyacente donde *colocar*.
5//!
6//! Coordenadas en **espacio de grilla** (voxel = 1, el mundo ocupa `[0, dim]`).
7//! El motor centra la grilla en el origen, así que para tirar el rayo desde la
8//! cámara: `origin_grilla = eye_mundo + dim/2`. [`raycast`] no toca la GPU;
9//! editar = `grid.set/clear` + `VoxelRenderer::sync` (subida incremental).
10
11use llimphi_3d::VoxelGrid;
12
13/// Resultado de un [`raycast`] que pegó en un voxel sólido.
14#[derive(Debug, Clone, Copy, PartialEq)]
15pub struct VoxelHit {
16    /// Voxel sólido golpeado (coordenadas de grilla).
17    pub cell: [i32; 3],
18    /// Normal de la cara de entrada (uno de ±X/±Y/±Z), apuntando al aire desde
19    /// donde vino el rayo. `[0,0,0]` si el origen ya estaba dentro de un sólido.
20    pub normal: [i32; 3],
21    /// Celda vacía adyacente (`cell + normal`): dónde **colocaría** un bloque
22    /// nuevo un click de "construir".
23    pub place: [i32; 3],
24    /// Distancia (en unidades de voxel) del origen al impacto.
25    pub dist: f32,
26}
27
28/// Marcha un rayo `origin + t·dir` por la grilla hasta el primer voxel sólido,
29/// hasta `max_dist` unidades. `dir` no necesita estar normalizado (se normaliza
30/// aquí, y `dist` queda en unidades de voxel). `None` si no pega nada.
31pub fn raycast(grid: &VoxelGrid, origin: [f32; 3], dir: [f32; 3], max_dist: f32) -> Option<VoxelHit> {
32    // Normalizar para que t sea distancia real.
33    let len = (dir[0] * dir[0] + dir[1] * dir[1] + dir[2] * dir[2]).sqrt();
34    if len < 1e-9 {
35        return None;
36    }
37    let d = [dir[0] / len, dir[1] / len, dir[2] / len];
38
39    // Celda inicial y parámetros DDA por eje.
40    let mut cell = [
41        origin[0].floor() as i32,
42        origin[1].floor() as i32,
43        origin[2].floor() as i32,
44    ];
45    let mut step = [0i32; 3];
46    let mut t_max = [f32::INFINITY; 3];
47    let mut t_delta = [f32::INFINITY; 3];
48    for a in 0..3 {
49        if d[a] > 1e-9 {
50            step[a] = 1;
51            t_delta[a] = 1.0 / d[a];
52            t_max[a] = (cell[a] as f32 + 1.0 - origin[a]) / d[a];
53        } else if d[a] < -1e-9 {
54            step[a] = -1;
55            t_delta[a] = -1.0 / d[a];
56            t_max[a] = (cell[a] as f32 - origin[a]) / d[a];
57        }
58    }
59
60    // ¿El origen ya está dentro de un sólido? (cavar desde adentro)
61    if grid.is_solid(cell[0], cell[1], cell[2]) {
62        return Some(VoxelHit { cell, normal: [0, 0, 0], place: cell, dist: 0.0 });
63    }
64
65    let mut t;
66    let mut normal = [0i32; 3];
67    // Tope de pasos generoso (suma de extensiones + margen) para no colgar.
68    let dim = grid.dim();
69    let max_steps = (dim[0] + dim[1] + dim[2]) as i32 * 2 + 8;
70    for _ in 0..max_steps {
71        // Avanzar al siguiente plano de voxel (eje con menor t_max).
72        let axis = if t_max[0] < t_max[1] && t_max[0] < t_max[2] {
73            0
74        } else if t_max[1] < t_max[2] {
75            1
76        } else {
77            2
78        };
79        t = t_max[axis];
80        if t > max_dist {
81            return None;
82        }
83        cell[axis] += step[axis];
84        t_max[axis] += t_delta[axis];
85        normal = [0, 0, 0];
86        normal[axis] = -step[axis]; // cara por la que entramos
87
88        if grid.is_solid(cell[0], cell[1], cell[2]) {
89            return Some(VoxelHit {
90                cell,
91                normal,
92                place: [cell[0] + normal[0], cell[1] + normal[1], cell[2] + normal[2]],
93                dist: t,
94            });
95        }
96    }
97    let _ = normal;
98    None
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    #[test]
106    fn pega_un_voxel_solo_y_da_cara_y_place() {
107        // Grid 8³ con un único voxel sólido en (4,4,4).
108        let mut g = VoxelGrid::new([8, 8, 8]);
109        g.set(4, 4, 4, [200, 50, 50]);
110
111        // Rayo desde -X hacia +X a la altura/profundidad del voxel.
112        let hit = raycast(&g, [0.5, 4.5, 4.5], [1.0, 0.0, 0.0], 100.0).expect("debe pegar");
113        assert_eq!(hit.cell, [4, 4, 4]);
114        assert_eq!(hit.normal, [-1, 0, 0]); // entró por la cara -X
115        assert_eq!(hit.place, [3, 4, 4]); // colocar queda un voxel antes
116    }
117
118    #[test]
119    fn no_pega_aire() {
120        let g = VoxelGrid::new([8, 8, 8]);
121        assert!(raycast(&g, [0.5, 0.5, 0.5], [1.0, 0.0, 0.0], 100.0).is_none());
122    }
123
124    #[test]
125    fn respeta_max_dist() {
126        let mut g = VoxelGrid::new([64, 8, 8]);
127        g.set(60, 4, 4, [10, 10, 10]);
128        // El voxel está a ~55 unidades; con max_dist 10 no debe alcanzarlo.
129        assert!(raycast(&g, [4.5, 4.5, 4.5], [1.0, 0.0, 0.0], 10.0).is_none());
130        assert!(raycast(&g, [4.5, 4.5, 4.5], [1.0, 0.0, 0.0], 100.0).is_some());
131    }
132}