use thiserror::Error;
#[derive(Debug, Error)]
pub enum CullingError {
#[error("Invalid frustum: {0}")]
InvalidFrustum(String),
#[error("Empty input: no Gaussians provided")]
EmptyInput,
#[error("Invalid camera: {0}")]
InvalidCamera(String),
}
#[derive(Debug, Clone, Copy)]
pub struct FrustumPlane {
pub normal: [f32; 3],
pub d: f32,
}
impl FrustumPlane {
pub fn new(normal: [f32; 3], d: f32) -> Self {
Self { normal, d }
}
#[inline]
pub fn signed_distance(&self, point: [f32; 3]) -> f32 {
self.normal[0] * point[0] + self.normal[1] * point[1] + self.normal[2] * point[2] + self.d
}
}
#[derive(Debug, Clone)]
pub struct ViewFrustum {
pub planes: [FrustumPlane; 6],
}
impl ViewFrustum {
pub fn from_perspective(
fov_y_rad: f32,
aspect: f32,
near: f32,
far: f32,
) -> Result<Self, CullingError> {
if fov_y_rad <= 0.0 || fov_y_rad >= std::f32::consts::PI {
return Err(CullingError::InvalidFrustum(format!(
"fov_y_rad must be in (0, π), got {}",
fov_y_rad
)));
}
if aspect <= 0.0 {
return Err(CullingError::InvalidFrustum(format!(
"aspect must be > 0, got {}",
aspect
)));
}
if near <= 0.0 {
return Err(CullingError::InvalidFrustum(format!(
"near must be > 0, got {}",
near
)));
}
if far <= near {
return Err(CullingError::InvalidFrustum(format!(
"far ({}) must be > near ({})",
far, near
)));
}
let f = 1.0 / (fov_y_rad * 0.5).tan();
let nf = near - far;
#[rustfmt::skip]
let mat: [f32; 16] = [
f / aspect, 0.0, 0.0, 0.0,
0.0, f, 0.0, 0.0,
0.0, 0.0, (far + near) / nf, 2.0 * far * near / nf,
0.0, 0.0, -1.0, 0.0,
];
Self::from_projection_matrix(&mat)
}
pub fn from_projection_matrix(mat: &[f32; 16]) -> Result<Self, CullingError> {
let row =
|i: usize| -> [f32; 4] { [mat[i * 4], mat[i * 4 + 1], mat[i * 4 + 2], mat[i * 4 + 3]] };
let r0 = row(0);
let r1 = row(1);
let r2 = row(2);
let r3 = row(3);
let raw_planes: [[f32; 4]; 6] = [
[r3[0] + r0[0], r3[1] + r0[1], r3[2] + r0[2], r3[3] + r0[3]],
[r3[0] - r0[0], r3[1] - r0[1], r3[2] - r0[2], r3[3] - r0[3]],
[r3[0] + r1[0], r3[1] + r1[1], r3[2] + r1[2], r3[3] + r1[3]],
[r3[0] - r1[0], r3[1] - r1[1], r3[2] - r1[2], r3[3] - r1[3]],
[r3[0] + r2[0], r3[1] + r2[1], r3[2] + r2[2], r3[3] + r2[3]],
[r3[0] - r2[0], r3[1] - r2[1], r3[2] - r2[2], r3[3] - r2[3]],
];
let mut planes = [FrustumPlane::new([0.0; 3], 0.0); 6];
for (i, rp) in raw_planes.iter().enumerate() {
let len = (rp[0] * rp[0] + rp[1] * rp[1] + rp[2] * rp[2]).sqrt();
if len < 1e-10 {
return Err(CullingError::InvalidFrustum(format!(
"Degenerate plane {} (zero normal length) in projection matrix",
i
)));
}
planes[i] = FrustumPlane::new([rp[0] / len, rp[1] / len, rp[2] / len], rp[3] / len);
}
Ok(Self { planes })
}
#[inline]
pub fn intersects_sphere(&self, center: [f32; 3], radius: f32) -> bool {
for plane in &self.planes {
if plane.signed_distance(center) < -radius {
return false;
}
}
true
}
#[inline]
pub fn intersects_aabb(&self, min: [f32; 3], max: [f32; 3]) -> bool {
for plane in &self.planes {
let px = if plane.normal[0] >= 0.0 {
max[0]
} else {
min[0]
};
let py = if plane.normal[1] >= 0.0 {
max[1]
} else {
min[1]
};
let pz = if plane.normal[2] >= 0.0 {
max[2]
} else {
min[2]
};
if plane.signed_distance([px, py, pz]) < 0.0 {
return false;
}
}
true
}
}
#[derive(Debug, Clone, Copy)]
pub struct GaussianCullData {
pub center: [f32; 3],
pub radius: f32,
}
#[derive(Debug, Clone)]
pub struct CullingConfig {
pub radius_scale: f32,
pub frustum_cull: bool,
pub distance_cull: bool,
pub max_distance: f32,
pub min_screen_size: f32,
}
impl Default for CullingConfig {
fn default() -> Self {
Self {
radius_scale: 1.0,
frustum_cull: true,
distance_cull: false,
max_distance: 100.0,
min_screen_size: 0.0,
}
}
}
#[derive(Debug, Clone)]
pub struct CullingResult {
pub visible: Vec<bool>,
pub visible_indices: Vec<usize>,
pub frustum_culled: usize,
pub distance_culled: usize,
pub size_culled: usize,
pub behind_camera_culled: usize,
pub total: usize,
pub num_visible: usize,
}
impl CullingResult {
pub fn visibility_ratio(&self) -> f32 {
if self.total == 0 {
0.0
} else {
self.num_visible as f32 / self.total as f32
}
}
pub fn format_summary(&self) -> String {
format!(
"visible={}/{} ({:.1}%) | frustum_culled={} distance_culled={} size_culled={} behind_camera_culled={}",
self.num_visible,
self.total,
self.visibility_ratio() * 100.0,
self.frustum_culled,
self.distance_culled,
self.size_culled,
self.behind_camera_culled,
)
}
}
pub fn transform_point(mat: &[f32; 16], p: [f32; 3]) -> [f32; 3] {
let x = mat[0] * p[0] + mat[1] * p[1] + mat[2] * p[2] + mat[3];
let y = mat[4] * p[0] + mat[5] * p[1] + mat[6] * p[2] + mat[7];
let z = mat[8] * p[0] + mat[9] * p[1] + mat[10] * p[2] + mat[11];
let w = mat[12] * p[0] + mat[13] * p[1] + mat[14] * p[2] + mat[15];
if w.abs() < 1e-10 {
[x, y, z]
} else {
[x / w, y / w, z / w]
}
}
#[inline]
pub fn project_radius_ndc(radius: f32, depth: f32, focal_x: f32, focal_y: f32) -> f32 {
let abs_depth = depth.abs();
if abs_depth < 1e-10 {
return f32::INFINITY;
}
let rx = radius * focal_x / abs_depth;
let ry = radius * focal_y / abs_depth;
rx.max(ry)
}
pub fn cull_gaussians(
gaussians: &[GaussianCullData],
view_matrix: &[f32; 16],
frustum: Option<&ViewFrustum>,
focal_x: f32,
focal_y: f32,
config: &CullingConfig,
) -> Result<CullingResult, CullingError> {
if config.frustum_cull && frustum.is_none() {
return Err(CullingError::InvalidFrustum(
"frustum_cull enabled but no ViewFrustum supplied".to_string(),
));
}
let total = gaussians.len();
if total == 0 {
return Ok(CullingResult {
visible: Vec::new(),
visible_indices: Vec::new(),
frustum_culled: 0,
distance_culled: 0,
size_culled: 0,
behind_camera_culled: 0,
total: 0,
num_visible: 0,
});
}
let mut visible = vec![true; total];
let mut frustum_culled = 0usize;
let mut distance_culled = 0usize;
let mut size_culled = 0usize;
let mut behind_camera_culled = 0usize;
for (idx, g) in gaussians.iter().enumerate() {
let view_center = transform_point(view_matrix, g.center);
let signed_depth = -view_center[2];
if signed_depth <= 0.0 {
visible[idx] = false;
behind_camera_culled += 1;
continue;
}
if config.distance_cull && signed_depth > config.max_distance {
visible[idx] = false;
distance_culled += 1;
continue;
}
if config.frustum_cull {
if let Some(frust) = frustum {
let scaled_radius = g.radius * config.radius_scale;
if !frust.intersects_sphere(view_center, scaled_radius) {
visible[idx] = false;
frustum_culled += 1;
continue;
}
}
}
if config.min_screen_size > 0.0 {
let screen_r = project_radius_ndc(
g.radius * config.radius_scale,
signed_depth,
focal_x,
focal_y,
);
if screen_r < config.min_screen_size {
visible[idx] = false;
size_culled += 1;
continue;
}
}
}
let visible_indices: Vec<usize> = (0..total).filter(|&i| visible[i]).collect();
let num_visible = visible_indices.len();
Ok(CullingResult {
visible,
visible_indices,
frustum_culled,
distance_culled,
size_culled,
behind_camera_culled,
total,
num_visible,
})
}
#[derive(Debug, Clone, Copy)]
pub struct ScreenSpaceBounds {
pub center_ndc: [f32; 2],
pub radius_ndc: f32,
pub min: [f32; 2],
pub max: [f32; 2],
pub depth: f32,
}
pub fn compute_screen_bounds(
view_center: [f32; 3],
world_radius: f32,
focal_x: f32,
focal_y: f32,
) -> Option<ScreenSpaceBounds> {
let depth = -view_center[2];
if depth <= 0.0 {
return None;
}
let cx = view_center[0] * focal_x / depth;
let cy = view_center[1] * focal_y / depth;
let r = project_radius_ndc(world_radius, depth, focal_x, focal_y);
Some(ScreenSpaceBounds {
center_ndc: [cx, cy],
radius_ndc: r,
min: [cx - r, cy - r],
max: [cx + r, cy + r],
depth,
})
}
#[derive(Debug, Clone)]
pub struct CullStats {
pub mean_depth: f32,
pub max_depth: f32,
pub min_depth: f32,
pub mean_radius: f32,
pub visibility_ratio: f32,
}
pub fn compute_cull_stats(gaussians: &[GaussianCullData], result: &CullingResult) -> CullStats {
if gaussians.is_empty() {
return CullStats {
mean_depth: 0.0,
max_depth: 0.0,
min_depth: 0.0,
mean_radius: 0.0,
visibility_ratio: 0.0,
};
}
let n = gaussians.len() as f32;
let depths: Vec<f32> = gaussians.iter().map(|g| g.center[2].abs()).collect();
let radii: Vec<f32> = gaussians.iter().map(|g| g.radius).collect();
let mean_depth = depths.iter().sum::<f32>() / n;
let max_depth = depths.iter().cloned().fold(f32::NEG_INFINITY, f32::max);
let min_depth = depths.iter().cloned().fold(f32::INFINITY, f32::min);
let mean_radius = radii.iter().sum::<f32>() / n;
CullStats {
mean_depth,
max_depth,
min_depth,
mean_radius,
visibility_ratio: result.visibility_ratio(),
}
}
#[cfg(test)]
mod tests {
use super::*;
fn identity() -> [f32; 16] {
[
1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0,
]
}
fn translation(tx: f32, ty: f32, tz: f32) -> [f32; 16] {
[
1.0, 0.0, 0.0, tx, 0.0, 1.0, 0.0, ty, 0.0, 0.0, 1.0, tz, 0.0, 0.0, 0.0, 1.0,
]
}
fn test_frustum() -> ViewFrustum {
ViewFrustum::from_perspective(60_f32.to_radians(), 1.0, 0.1, 100.0)
.expect("valid perspective parameters")
}
#[test]
fn test_frustum_plane_positive_side() {
let plane = FrustumPlane::new([0.0, 0.0, 1.0], 0.0);
assert!(plane.signed_distance([0.0, 0.0, 1.0]) > 0.0);
}
#[test]
fn test_frustum_plane_negative_side() {
let plane = FrustumPlane::new([0.0, 0.0, 1.0], 0.0);
assert!(plane.signed_distance([0.0, 0.0, -1.0]) < 0.0);
}
#[test]
fn test_from_perspective_valid() {
let result = ViewFrustum::from_perspective(60_f32.to_radians(), 1.6, 0.1, 1000.0);
assert!(result.is_ok(), "Expected Ok for valid parameters");
}
#[test]
fn test_from_perspective_zero_fov() {
let result = ViewFrustum::from_perspective(0.0, 1.0, 0.1, 100.0);
assert!(
matches!(result, Err(CullingError::InvalidFrustum(_))),
"Expected InvalidFrustum for fov=0"
);
}
#[test]
fn test_from_perspective_near_ge_far() {
let result = ViewFrustum::from_perspective(60_f32.to_radians(), 1.0, 10.0, 5.0);
assert!(
matches!(result, Err(CullingError::InvalidFrustum(_))),
"Expected InvalidFrustum for near >= far"
);
}
#[test]
fn test_sphere_inside_frustum() {
let frustum = test_frustum();
assert!(frustum.intersects_sphere([0.0, 0.0, -5.0], 0.1));
}
#[test]
fn test_sphere_behind_near() {
let frustum = test_frustum();
assert!(!frustum.intersects_sphere([0.0, 0.0, 5.0], 0.01));
}
#[test]
fn test_sphere_partially_inside() {
let frustum = test_frustum();
assert!(frustum.intersects_sphere([0.0, 0.0, 0.0], 5.0));
}
#[test]
fn test_aabb_inside() {
let frustum = test_frustum();
assert!(frustum.intersects_aabb([-0.5, -0.5, -5.0], [0.5, 0.5, -2.0]));
}
#[test]
fn test_aabb_outside_right() {
let frustum = test_frustum();
assert!(!frustum.intersects_aabb([500.0, -0.5, -5.0], [600.0, 0.5, -2.0]));
}
#[test]
fn test_transform_point_identity() {
let p = [1.0_f32, 2.0, 3.0];
let result = transform_point(&identity(), p);
assert!((result[0] - p[0]).abs() < 1e-6);
assert!((result[1] - p[1]).abs() < 1e-6);
assert!((result[2] - p[2]).abs() < 1e-6);
}
#[test]
fn test_transform_point_translation() {
let mat = translation(10.0, -5.0, 3.0);
let result = transform_point(&mat, [1.0, 2.0, 3.0]);
assert!((result[0] - 11.0).abs() < 1e-5, "x={}", result[0]);
assert!((result[1] - -3.0).abs() < 1e-5, "y={}", result[1]);
assert!((result[2] - 6.0).abs() < 1e-5, "z={}", result[2]);
}
#[test]
fn test_project_radius_ndc() {
let r = project_radius_ndc(1.0, 10.0, 1.0, 1.0);
assert!((r - 0.1).abs() < 1e-6, "r={}", r);
}
#[test]
fn test_cull_empty_input() {
let config = CullingConfig {
frustum_cull: false,
..CullingConfig::default()
};
let result = cull_gaussians(&[], &identity(), None, 1.0, 1.0, &config);
let r = result.expect("empty input should return Ok, not Err");
assert_eq!(r.total, 0);
assert_eq!(r.num_visible, 0);
assert!(r.visible.is_empty());
assert!(r.visible_indices.is_empty());
}
#[test]
fn test_cull_all_visible() {
let gaussians = vec![
GaussianCullData {
center: [0.0, 0.0, -5.0],
radius: 0.1,
},
GaussianCullData {
center: [1.0, 0.0, -5.0],
radius: 0.1,
},
];
let config = CullingConfig {
frustum_cull: false,
distance_cull: false,
min_screen_size: 0.0,
..Default::default()
};
let result = cull_gaussians(&gaussians, &identity(), None, 1.0, 1.0, &config)
.expect("should succeed");
assert_eq!(result.num_visible, 2);
assert!(result.visible.iter().all(|&v| v));
}
#[test]
fn test_cull_distance() {
let gaussians = vec![
GaussianCullData {
center: [0.0, 0.0, -3.0],
radius: 0.1,
}, GaussianCullData {
center: [0.0, 0.0, -200.0],
radius: 0.1,
}, ];
let config = CullingConfig {
frustum_cull: false,
distance_cull: true,
max_distance: 50.0,
min_screen_size: 0.0,
..Default::default()
};
let result = cull_gaussians(&gaussians, &identity(), None, 1.0, 1.0, &config)
.expect("should succeed");
assert_eq!(result.num_visible, 1);
assert_eq!(result.distance_culled, 1);
assert!(result.visible[0]);
assert!(!result.visible[1]);
}
#[test]
fn test_cull_frustum() {
let frustum = test_frustum();
let gaussians = vec![
GaussianCullData {
center: [0.0, 0.0, -5.0],
radius: 0.05,
}, GaussianCullData {
center: [1000.0, 0.0, -5.0],
radius: 0.05,
}, ];
let config = CullingConfig {
frustum_cull: true,
distance_cull: false,
min_screen_size: 0.0,
radius_scale: 1.0,
..Default::default()
};
let result = cull_gaussians(&gaussians, &identity(), Some(&frustum), 1.0, 1.0, &config)
.expect("should succeed");
assert_eq!(
result.frustum_culled, 1,
"Expected 1 frustum-culled Gaussian"
);
}
#[test]
fn test_cull_visible_indices_consistent() {
let gaussians = vec![
GaussianCullData {
center: [0.0, 0.0, -3.0],
radius: 0.1,
},
GaussianCullData {
center: [0.0, 0.0, -200.0],
radius: 0.1,
},
GaussianCullData {
center: [0.0, 0.0, -5.0],
radius: 0.1,
},
];
let config = CullingConfig {
frustum_cull: false,
distance_cull: true,
max_distance: 50.0,
min_screen_size: 0.0,
..Default::default()
};
let result = cull_gaussians(&gaussians, &identity(), None, 1.0, 1.0, &config)
.expect("should succeed");
let expected_indices: Vec<usize> =
(0..result.total).filter(|&i| result.visible[i]).collect();
assert_eq!(result.visible_indices, expected_indices);
}
#[test]
fn test_visibility_ratio() {
let gaussians = vec![
GaussianCullData {
center: [0.0, 0.0, -5.0],
radius: 0.1,
},
GaussianCullData {
center: [0.0, 0.0, -200.0],
radius: 0.1,
},
];
let config = CullingConfig {
frustum_cull: false,
distance_cull: true,
max_distance: 50.0,
min_screen_size: 0.0,
..Default::default()
};
let result = cull_gaussians(&gaussians, &identity(), None, 1.0, 1.0, &config)
.expect("should succeed");
let ratio = result.visibility_ratio();
assert!((ratio - 0.5).abs() < 1e-6, "Expected 0.5, got {}", ratio);
}
#[test]
fn test_screen_bounds_behind_camera() {
let result = compute_screen_bounds([0.0, 0.0, 5.0], 1.0, 1.0, 1.0);
assert!(result.is_none(), "Expected None for point behind camera");
}
#[test]
fn test_screen_bounds_valid() {
let result = compute_screen_bounds([0.0, 0.0, -10.0], 1.0, 1.0, 1.0);
let bounds = result.expect("should return Some for point in front of camera");
assert!(
(bounds.center_ndc[0] - 0.0).abs() < 1e-6,
"cx={}",
bounds.center_ndc[0]
);
assert!(
(bounds.center_ndc[1] - 0.0).abs() < 1e-6,
"cy={}",
bounds.center_ndc[1]
);
assert!(
(bounds.radius_ndc - 0.1).abs() < 1e-5,
"r={}",
bounds.radius_ndc
);
assert!((bounds.min[0] - -0.1).abs() < 1e-5);
assert!((bounds.max[0] - 0.1).abs() < 1e-5);
assert!((bounds.depth - 10.0).abs() < 1e-5, "depth={}", bounds.depth);
}
#[test]
fn test_cull_stats_basic() {
let gaussians = vec![
GaussianCullData {
center: [0.0, 0.0, -3.0],
radius: 0.5,
},
GaussianCullData {
center: [0.0, 0.0, -7.0],
radius: 1.5,
},
];
let config = CullingConfig {
frustum_cull: false,
distance_cull: false,
min_screen_size: 0.0,
..Default::default()
};
let result = cull_gaussians(&gaussians, &identity(), None, 1.0, 1.0, &config)
.expect("should succeed");
let stats = compute_cull_stats(&gaussians, &result);
assert!(
(stats.mean_depth - 5.0).abs() < 1e-5,
"mean_depth={}",
stats.mean_depth
);
assert!(
(stats.min_depth - 3.0).abs() < 1e-5,
"min_depth={}",
stats.min_depth
);
assert!(
(stats.max_depth - 7.0).abs() < 1e-5,
"max_depth={}",
stats.max_depth
);
assert!(
(stats.mean_radius - 1.0).abs() < 1e-5,
"mean_radius={}",
stats.mean_radius
);
assert!((stats.visibility_ratio - 1.0).abs() < 1e-6);
}
#[test]
fn test_cull_gaussians_requires_frustum_when_enabled() {
let gaussians = vec![GaussianCullData {
center: [0.0, 0.0, -5.0],
radius: 0.1,
}];
let config = CullingConfig {
frustum_cull: true,
..Default::default()
};
let result = cull_gaussians(&gaussians, &identity(), None, 1.0, 1.0, &config);
assert!(
matches!(result, Err(CullingError::InvalidFrustum(_))),
"Expected InvalidFrustum when frustum_cull=true and frustum=None, got {result:?}"
);
}
#[test]
fn test_cull_gaussians_culls_behind_camera() {
let gaussians = vec![
GaussianCullData {
center: [0.0, 0.0, 5.0],
radius: 0.1,
},
GaussianCullData {
center: [0.0, 0.0, -5.0],
radius: 0.1,
},
];
let config = CullingConfig {
frustum_cull: false,
distance_cull: false,
min_screen_size: 0.0,
..Default::default()
};
let result = cull_gaussians(&gaussians, &identity(), None, 1.0, 1.0, &config)
.expect("should succeed");
assert!(
!result.visible[0],
"Gaussian behind the camera must be culled"
);
assert!(
result.visible[1],
"Gaussian in front of the camera must stay visible"
);
assert_eq!(result.behind_camera_culled, 1);
assert_eq!(result.num_visible, 1);
}
}