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 =
91                plane[0] * center[0] + plane[1] * center[1] + plane[2] * center[2] + plane[3];
92            if dist < -radius {
93                return false;
94            }
95        }
96        true
97    }
98}
99
100/// Spatial hash cell coordinates.
101#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
102pub struct SpatialCell {
103    pub x: i32,
104    pub y: i32,
105    pub z: i32,
106}
107
108/// Spatial hash for scene virtualization.
109#[derive(Clone, Debug)]
110pub struct SpatialHash {
111    cell_size: f32,
112    cells: std::collections::HashMap<SpatialCell, Vec<u64>>,
113}
114
115impl SpatialHash {
116    pub fn new(cell_size: f32) -> Self {
117        Self {
118            cell_size,
119            cells: std::collections::HashMap::new(),
120        }
121    }
122
123    /// Insert an entity into the spatial hash.
124    pub fn insert(&mut self, entity_id: u64, position: &[f32; 3]) {
125        let cell = self.world_to_cell(position);
126        self.cells.entry(cell).or_default().push(entity_id);
127    }
128
129    /// Remove an entity from the spatial hash.
130    pub fn remove(&mut self, entity_id: u64, position: &[f32; 3]) {
131        let cell = self.world_to_cell(position);
132        if let Some(entities) = self.cells.get_mut(&cell) {
133            entities.retain(|&id| id != entity_id);
134            if entities.is_empty() {
135                self.cells.remove(&cell);
136            }
137        }
138    }
139
140    /// Query entities within a frustum.
141    pub fn query_frustum(&self, frustum: &Frustum) -> Vec<u64> {
142        let mut results = Vec::new();
143        // Check all occupied cells against the frustum
144        for (cell, entities) in &self.cells {
145            // Convert cell coordinates to world-space AABB
146            let min = [
147                cell.x as f32 * self.cell_size,
148                cell.y as f32 * self.cell_size,
149                cell.z as f32 * self.cell_size,
150            ];
151            let max = [
152                min[0] + self.cell_size,
153                min[1] + self.cell_size,
154                min[2] + self.cell_size,
155            ];
156            if frustum.intersects_aabb(&min, &max) {
157                results.extend(entities);
158            }
159        }
160        results
161    }
162
163    /// Query entities within a sphere.
164    pub fn query_sphere(&self, center: &[f32; 3], radius: f32) -> Vec<u64> {
165        let mut results = Vec::new();
166        // Check cells that could contain entities within the sphere
167        let min_cell =
168            self.world_to_cell(&[center[0] - radius, center[1] - radius, center[2] - radius]);
169        let max_cell =
170            self.world_to_cell(&[center[0] + radius, center[1] + radius, center[2] + radius]);
171
172        for x in min_cell.x..=max_cell.x {
173            for y in min_cell.y..=max_cell.y {
174                for z in min_cell.z..=max_cell.z {
175                    let cell = SpatialCell { x, y, z };
176                    if let Some(entities) = self.cells.get(&cell) {
177                        results.extend(entities);
178                    }
179                }
180            }
181        }
182        results
183    }
184
185    fn world_to_cell(&self, position: &[f32; 3]) -> SpatialCell {
186        SpatialCell {
187            x: (position[0] / self.cell_size).floor() as i32,
188            y: (position[1] / self.cell_size).floor() as i32,
189            z: (position[2] / self.cell_size).floor() as i32,
190        }
191    }
192
193    /// Clear all cells.
194    pub fn clear(&mut self) {
195        self.cells.clear();
196    }
197
198    /// Returns the number of occupied cells.
199    pub fn len(&self) -> usize {
200        self.cells.len()
201    }
202
203    pub fn is_empty(&self) -> bool {
204        self.cells.is_empty()
205    }
206}
207
208#[cfg(test)]
209mod p2_28_virtualization_tests {
210    use super::*;
211
212    #[test]
213    fn frustum_intersects_aabb_visible() {
214        let identity = [
215            [1.0, 0.0, 0.0, 0.0],
216            [0.0, 1.0, 0.0, 0.0],
217            [0.0, 0.0, 1.0, 0.0],
218            [0.0, 0.0, 0.0, 1.0],
219        ];
220        let frustum = Frustum::from_view_proj(&identity);
221        assert!(frustum.intersects_aabb(&[0.0, 0.0, 0.0], &[1.0, 1.0, 1.0]));
222    }
223
224    #[test]
225    fn frustum_intersects_aabb_outside() {
226        let frustum = Frustum {
227            planes: [
228                [0.0, 0.0, -1.0, -10.0], // Near plane at z=-10
229                [0.0, 0.0, 1.0, -10.0],  // Far plane
230                [0.0, 0.0, 0.0, 0.0],
231                [0.0, 0.0, 0.0, 0.0],
232                [0.0, 0.0, 0.0, 0.0],
233                [0.0, 0.0, 0.0, 0.0],
234            ],
235        };
236        assert!(!frustum.intersects_aabb(&[0.0, 0.0, -11.0], &[1.0, 1.0, -10.5]));
237    }
238
239    #[test]
240    fn frustum_intersects_sphere() {
241        let identity = [
242            [1.0, 0.0, 0.0, 0.0],
243            [0.0, 1.0, 0.0, 0.0],
244            [0.0, 0.0, 1.0, 0.0],
245            [0.0, 0.0, 0.0, 1.0],
246        ];
247        let frustum = Frustum::from_view_proj(&identity);
248        assert!(frustum.intersects_sphere(&[0.0, 0.0, 0.0], 1.0));
249    }
250
251    #[test]
252    fn spatial_hash_insert_and_query() {
253        let mut hash = SpatialHash::new(10.0);
254        hash.insert(1, &[5.0, 5.0, 0.0]);
255        hash.insert(2, &[15.0, 5.0, 0.0]);
256        assert_eq!(hash.len(), 2);
257    }
258
259    #[test]
260    fn spatial_hash_query_frustum() {
261        let mut hash = SpatialHash::new(10.0);
262        hash.insert(1, &[5.0, 5.0, 0.0]);
263        hash.insert(2, &[50.0, 50.0, 0.0]);
264
265        let identity = [
266            [1.0, 0.0, 0.0, 0.0],
267            [0.0, 1.0, 0.0, 0.0],
268            [0.0, 0.0, 1.0, 0.0],
269            [0.0, 0.0, 0.0, 1.0],
270        ];
271        let frustum = Frustum::from_view_proj(&identity);
272        let results = hash.query_frustum(&frustum);
273        assert!(!results.is_empty());
274    }
275
276    #[test]
277    fn spatial_hash_remove() {
278        let mut hash = SpatialHash::new(10.0);
279        hash.insert(1, &[5.0, 5.0, 0.0]);
280        hash.remove(1, &[5.0, 5.0, 0.0]);
281        assert_eq!(hash.len(), 0);
282    }
283
284    #[test]
285    fn spatial_hash_clear() {
286        let mut hash = SpatialHash::new(10.0);
287        hash.insert(1, &[5.0, 5.0, 0.0]);
288        hash.insert(2, &[15.0, 5.0, 0.0]);
289        hash.clear();
290        assert!(hash.is_empty());
291    }
292}
cvkg_render_gpu/types/virtualization.rs

cvkg_render_gpu/types/
virtualization.rs
