treeculler 0.4.0

Utilities to help with frustum culling.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

use crate::{Float, Vec3, Vec4, AABB};
use core::fmt::Debug;

/// A data structure for six planes of a view frustum.
pub struct Frustum<T: Float + Debug> {
    /// A plane: ax + bx + cy + d = 0 --> [a, b, c, d]
    ///
    /// [near, left, right, bottom, top, far]
    pub planes: [Vec4<T>; 6],
    /// Plane intersection points.
    ///
    /// - n: near, f: far
    /// - l: left, r: right
    /// - t: top,  b: bottom
    ///
    /// [nlt, nrt, nlb, nrb, flt, frt, flb, frb]
    pub points: [Vec3<T>; 8],
}

impl<T: Float + Debug> Frustum<T> {
    /// Create a frustum given the product of the modelview and projection as a float array.
    pub fn from_modelview_projection(mvp: [[T; 4]; 4]) -> Frustum<T> {
        let left = normalize_plane(Vec4::new(
            mvp[0][0] + mvp[0][3],
            mvp[1][0] + mvp[1][3],
            mvp[2][0] + mvp[2][3],
            mvp[3][0] + mvp[3][3],
        ));
        let right = normalize_plane(Vec4::new(
            -mvp[0][0] + mvp[0][3],
            -mvp[1][0] + mvp[1][3],
            -mvp[2][0] + mvp[2][3],
            -mvp[3][0] + mvp[3][3],
        ));
        let bottom = normalize_plane(Vec4::new(
            mvp[0][1] + mvp[0][3],
            mvp[1][1] + mvp[1][3],
            mvp[2][1] + mvp[2][3],
            mvp[3][1] + mvp[3][3],
        ));
        let top = normalize_plane(Vec4::new(
            -mvp[0][1] + mvp[0][3],
            -mvp[1][1] + mvp[1][3],
            -mvp[2][1] + mvp[2][3],
            -mvp[3][1] + mvp[3][3],
        ));
        let near = normalize_plane(Vec4::new(
            mvp[0][2] + mvp[0][3],
            mvp[1][2] + mvp[1][3],
            mvp[2][2] + mvp[2][3],
            mvp[3][2] + mvp[3][3],
        ));
        let far = normalize_plane(Vec4::new(
            -mvp[0][2] + mvp[0][3],
            -mvp[1][2] + mvp[1][3],
            -mvp[2][2] + mvp[2][3],
            -mvp[3][2] + mvp[3][3],
        ));

        let flt = intersect_planes(&far, &left, &top);
        let frt = intersect_planes(&far, &right, &top);
        let flb = intersect_planes(&far, &left, &bottom);
        let frb = intersect_planes(&far, &right, &bottom);
        let nlt = intersect_planes(&near, &left, &top);
        let nrt = intersect_planes(&near, &right, &top);
        let nlb = intersect_planes(&near, &left, &bottom);
        let nrb = intersect_planes(&near, &right, &bottom);

        Self {
            planes: [near, left, right, bottom, top, far],
            points: [nlt, nrt, nlb, nrb, flt, frt, flb, frb],
        }
    }

    pub(crate) fn test_against_aabb(&self, aabb: &AABB<T>) -> bool {
        for i in 0..3 {
            let mut out = 0;
            for j in 0..8 {
                if self.points[j][i] < aabb.min[i] {
                    out += 1;
                }
            }
            if out == 8 {
                return false;
            }
            out = 0;
            for j in 0..8 {
                if self.points[j][i] > aabb.max[i] {
                    out += 1;
                }
            }
            if out == 8 {
                return false;
            }
        }
        true
    }
}

/// Normalize a plane.
pub fn normalize_plane<T: Float>(mut plane: Vec4<T>) -> Vec4<T> {
    let normal_magnitude = (plane.x.powi(2) + plane.y.powi(2) + plane.z.powi(2)).sqrt();
    plane.x = plane.x / normal_magnitude;
    plane.y = plane.y / normal_magnitude;
    plane.z = plane.z / normal_magnitude;
    plane.w = plane.w / normal_magnitude;
    plane
}

/// Find the intersection point of three planes.
///
/// # Notes
/// This assumes that the planes will not intersect in a line.
pub fn intersect_planes<T: Float>(p0: &Vec4<T>, p1: &Vec4<T>, p2: &Vec4<T>) -> Vec3<T> {
    use core::ops::Mul;

    let bxc = p1.xyz().cross(p2.xyz());
    let cxa = p2.xyz().cross(p0.xyz());
    let axb = p0.xyz().cross(p1.xyz());
    let r = -bxc.mul(p0.w) - cxa.mul(p1.w) - axb.mul(p2.w);
    r * (T::one() / bxc.dot(p0.xyz()))
}