cvkg_render_gpu/types/
virtualization.rs

1/// A frustum for visibility culling.
2#[derive(Clone, Debug)]
3pub struct Frustum {
4    /// Planes: [normal_x, normal_y, normal_z, distance]
5    pub planes: [[f32; 4]; 6],
6}
7
8impl Frustum {
9    /// Create a frustum from a view-projection matrix.
10    pub fn from_view_proj(view_proj: &[[f32; 4]; 4]) -> Self {
11        let mut planes = [[0.0f32; 4]; 6];
12        let m = view_proj;
13
14        // Left plane
15        planes[0] = [
16            m[0][3] + m[0][0],
17            m[1][3] + m[1][0],
18            m[2][3] + m[2][0],
19            m[3][3] + m[3][0],
20        ];
21        // Right plane
22        planes[1] = [
23            m[0][3] - m[0][0],
24            m[1][3] - m[1][0],
25            m[2][3] - m[2][0],
26            m[3][3] - m[3][0],
27        ];
28        // Top plane
29        planes[2] = [
30            m[0][3] - m[0][1],
31            m[1][3] - m[1][1],
32            m[2][3] - m[2][1],
33            m[3][3] - m[3][1],
34        ];
35        // Bottom plane
36        planes[3] = [
37            m[0][3] + m[0][1],
38            m[1][3] + m[1][1],
39            m[2][3] + m[2][1],
40            m[3][3] + m[3][1],
41        ];
42        // Near plane
43        planes[4] = [
44            m[0][3] + m[0][2],
45            m[1][3] + m[1][2],
46            m[2][3] + m[2][2],
47            m[3][3] + m[3][2],
48        ];
49        // Far plane
50        planes[5] = [
51            m[0][3] - m[0][2],
52            m[1][3] - m[1][2],
53            m[2][3] - m[2][2],
54            m[3][3] - m[3][2],
55        ];
56
57        // Normalize planes
58        for plane in &mut planes {
59            let len = (plane[0] * plane[0] + plane[1] * plane[1] + plane[2] * plane[2]).sqrt();
60            if len > 0.0 {
61                plane[0] /= len;
62                plane[1] /= len;
63                plane[2] /= len;
64                plane[3] /= len;
65            }
66        }
67
68        Self { planes }
69    }
70
71    /// Test if an axis-aligned bounding box is visible within this frustum.
72    pub fn intersects_aabb(&self, min: &[f32; 3], max: &[f32; 3]) -> bool {
73        for plane in &self.planes {
74            // Find the p-vertex (the corner most in the direction of the plane normal)
75            let px = if plane[0] > 0.0 { max[0] } else { min[0] };
76            let py = if plane[1] > 0.0 { max[1] } else { min[1] };
77            let pz = if plane[2] > 0.0 { max[2] } else { min[2] };
78
79            // If the p-vertex is behind the plane, the entire AABB is outside
80            if plane[0] * px + plane[1] * py + plane[2] * pz + plane[3] < 0.0 {
81                return false;
82            }
83        }
84        true
85    }
86
87    /// Test if a sphere is visible within this frustum.
88    pub fn intersects_sphere(&self, center: &[f32; 3], radius: f32) -> bool {
89        for plane in &self.planes {
90            let dist = plane[0] * center[0] + plane[1] * center[1] + plane[2] * center[2] + plane[3];
91            if dist < -radius {
92                return false;
93            }
94        }
95        true
96    }
97}
98
99/// Spatial hash cell coordinates.
100#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
101pub struct SpatialCell {
102    pub x: i32,
103    pub y: i32,
104    pub z: i32,
105}
106
107/// Spatial hash for scene virtualization.
108#[derive(Clone, Debug)]
109pub struct SpatialHash {
110    cell_size: f32,
111    cells: std::collections::HashMap<SpatialCell, Vec<u64>>,
112}
113
114impl SpatialHash {
115    pub fn new(cell_size: f32) -> Self {
116        Self {
117            cell_size,
118            cells: std::collections::HashMap::new(),
119        }
120    }
121
122    /// Insert an entity into the spatial hash.
123    pub fn insert(&mut self, entity_id: u64, position: &[f32; 3]) {
124        let cell = self.world_to_cell(position);
125        self.cells.entry(cell).or_default().push(entity_id);
126    }
127
128    /// Remove an entity from the spatial hash.
129    pub fn remove(&mut self, entity_id: u64, position: &[f32; 3]) {
130        let cell = self.world_to_cell(position);
131        if let Some(entities) = self.cells.get_mut(&cell) {
132            entities.retain(|&id| id != entity_id);
133            if entities.is_empty() {
134                self.cells.remove(&cell);
135            }
136        }
137    }
138
139    /// Query entities within a frustum.
140    pub fn query_frustum(&self, frustum: &Frustum) -> Vec<u64> {
141        let mut results = Vec::new();
142        // Check all occupied cells against the frustum
143        for (cell, entities) in &self.cells {
144            // Convert cell coordinates to world-space AABB
145            let min = [
146                cell.x as f32 * self.cell_size,
147                cell.y as f32 * self.cell_size,
148                cell.z as f32 * self.cell_size,
149            ];
150            let max = [
151                min[0] + self.cell_size,
152                min[1] + self.cell_size,
153                min[2] + self.cell_size,
154            ];
155            if frustum.intersects_aabb(&min, &max) {
156                results.extend(entities);
157            }
158        }
159        results
160    }
161
162    /// Query entities within a sphere.
163    pub fn query_sphere(&self, center: &[f32; 3], radius: f32) -> Vec<u64> {
164        let mut results = Vec::new();
165        // Check cells that could contain entities within the sphere
166        let min_cell = self.world_to_cell(&[
167            center[0] - radius,
168            center[1] - radius,
169            center[2] - radius,
170        ]);
171        let max_cell = self.world_to_cell(&[
172            center[0] + radius,
173            center[1] + radius,
174            center[2] + radius,
175        ]);
176
177        for x in min_cell.x..=max_cell.x {
178            for y in min_cell.y..=max_cell.y {
179                for z in min_cell.z..=max_cell.z {
180                    let cell = SpatialCell { x, y, z };
181                    if let Some(entities) = self.cells.get(&cell) {
182                        results.extend(entities);
183                    }
184                }
185            }
186        }
187        results
188    }
189
190    fn world_to_cell(&self, position: &[f32; 3]) -> SpatialCell {
191        SpatialCell {
192            x: (position[0] / self.cell_size).floor() as i32,
193            y: (position[1] / self.cell_size).floor() as i32,
194            z: (position[2] / self.cell_size).floor() as i32,
195        }
196    }
197
198    /// Clear all cells.
199    pub fn clear(&mut self) {
200        self.cells.clear();
201    }
202
203    /// Returns the number of occupied cells.
204    pub fn len(&self) -> usize {
205        self.cells.len()
206    }
207
208    pub fn is_empty(&self) -> bool {
209        self.cells.is_empty()
210    }
211}
212
213#[cfg(test)]
214mod p2_28_virtualization_tests {
215    use super::*;
216
217    #[test]
218    fn frustum_intersects_aabb_visible() {
219        let identity = [
220            [1.0, 0.0, 0.0, 0.0],
221            [0.0, 1.0, 0.0, 0.0],
222            [0.0, 0.0, 1.0, 0.0],
223            [0.0, 0.0, 0.0, 1.0],
224        ];
225        let frustum = Frustum::from_view_proj(&identity);
226        assert!(frustum.intersects_aabb(&[0.0, 0.0, 0.0], &[1.0, 1.0, 1.0]));
227    }
228
229    #[test]
230    fn frustum_intersects_aabb_outside() {
231        let frustum = Frustum {
232            planes: [
233                [0.0, 0.0, -1.0, -10.0], // Near plane at z=-10
234                [0.0, 0.0, 1.0, -10.0],  // Far plane
235                [0.0, 0.0, 0.0, 0.0],
236                [0.0, 0.0, 0.0, 0.0],
237                [0.0, 0.0, 0.0, 0.0],
238                [0.0, 0.0, 0.0, 0.0],
239            ],
240        };
241        assert!(!frustum.intersects_aabb(&[0.0, 0.0, -11.0], &[1.0, 1.0, -10.5]));
242    }
243
244    #[test]
245    fn frustum_intersects_sphere() {
246        let identity = [
247            [1.0, 0.0, 0.0, 0.0],
248            [0.0, 1.0, 0.0, 0.0],
249            [0.0, 0.0, 1.0, 0.0],
250            [0.0, 0.0, 0.0, 1.0],
251        ];
252        let frustum = Frustum::from_view_proj(&identity);
253        assert!(frustum.intersects_sphere(&[0.0, 0.0, 0.0], 1.0));
254    }
255
256    #[test]
257    fn spatial_hash_insert_and_query() {
258        let mut hash = SpatialHash::new(10.0);
259        hash.insert(1, &[5.0, 5.0, 0.0]);
260        hash.insert(2, &[15.0, 5.0, 0.0]);
261        assert_eq!(hash.len(), 2);
262    }
263
264    #[test]
265    fn spatial_hash_query_frustum() {
266        let mut hash = SpatialHash::new(10.0);
267        hash.insert(1, &[5.0, 5.0, 0.0]);
268        hash.insert(2, &[50.0, 50.0, 0.0]);
269
270        let identity = [
271            [1.0, 0.0, 0.0, 0.0],
272            [0.0, 1.0, 0.0, 0.0],
273            [0.0, 0.0, 1.0, 0.0],
274            [0.0, 0.0, 0.0, 1.0],
275        ];
276        let frustum = Frustum::from_view_proj(&identity);
277        let results = hash.query_frustum(&frustum);
278        assert!(!results.is_empty());
279    }
280
281    #[test]
282    fn spatial_hash_remove() {
283        let mut hash = SpatialHash::new(10.0);
284        hash.insert(1, &[5.0, 5.0, 0.0]);
285        hash.remove(1, &[5.0, 5.0, 0.0]);
286        assert_eq!(hash.len(), 0);
287    }
288
289    #[test]
290    fn spatial_hash_clear() {
291        let mut hash = SpatialHash::new(10.0);
292        hash.insert(1, &[5.0, 5.0, 0.0]);
293        hash.insert(2, &[15.0, 5.0, 0.0]);
294        hash.clear();
295        assert!(hash.is_empty());
296    }
297}
cvkg_render_gpu/types/virtualization.rs

cvkg_render_gpu/types/
virtualization.rs
