obvhs/
splits.rs

1//! Split large triangles into multiple smaller Aabbs.
2
3use glam::Vec3A;
4
5use crate::{aabb::Aabb, triangle::Triangle};
6
7/// Splits large triangles into multiple smaller Aabbs. Fits the new aabbs tightly to the triangle.
8/// Note: This will result in more aabbs than triangles. The indices Vec will have grow with the
9/// added Aabb's with the respective mapping back to the initial list of triangles.
10/// # Arguments
11/// * `avg_half_area` - The average half area of the Triangles
12/// * `largest_half_area` - The largest half area of the Triangles
13///   This is tuned to try to create splits conservatively enough that it generally
14///   wont result in lower traversal performance across a variety of scenes.
15///   (Naive splitting can result in lower traversal performance in some scenes)
16pub fn split_aabbs_preset(
17    aabbs: &mut Vec<Aabb>,
18    indices: &mut Vec<u32>,
19    triangles: &[Triangle],
20    avg_half_area: f32,
21    largest_half_area: f32,
22) {
23    split_aabbs_precise(
24        aabbs,
25        indices,
26        triangles,
27        avg_half_area * 3.0,
28        (avg_half_area * 4.0).max(avg_half_area * 0.9 + largest_half_area * 0.1),
29        1.8,
30        1.6,
31        12,
32        12,
33    );
34}
35
36/// Splits large triangles into multiple smaller Aabbs. Fits the new aabbs tightly to the triangle.
37/// Note: This will result in more aabbs than triangles. The indices Vec will have grow with the
38/// added Aabb's with the respective mapping back to the initial list of triangles.
39/// # Arguments
40/// * `area_thresh_low` - Triangles with aabb half areas below this will not be considered for splitting.
41/// * `area_thresh_high` - If the low split factor condition is not met then area_thresh_high > old_cost
42///   must be met in addition to best_cost * split_factor_high < old_cost in order for the split to occur
43/// * `split_factor_low` - If the resulting smallest aabb half area (best_cost) multiplied by this factor is
44///   lower than the original cost the best split will be used (best_cost * split_factor_low < old_cost)
45///   (area_thresh_high > old_cost && best_cost * split_factor_high < old_cost)
46/// * `max_iterations` - Number of times to evaluate the entire set of aabbs/triangles (including the newly added splits)
47/// * `split_tests` - Number of places try splitting the triangle at.
48#[allow(clippy::too_many_arguments)]
49pub fn split_aabbs_precise(
50    aabbs: &mut Vec<Aabb>,
51    indices: &mut Vec<u32>,
52    triangles: &[Triangle],
53    area_thresh_low: f32,
54    area_thresh_high: f32,
55    split_factor_low: f32,
56    split_factor_high: f32,
57    max_iterations: u32,
58    split_tests: u32,
59) {
60    crate::scope!("split_aabbs_precise");
61
62    let mut candidates = Vec::new();
63
64    for (i, aabb) in aabbs.iter().enumerate() {
65        if aabb.half_area() > area_thresh_low {
66            candidates.push(i)
67        }
68    }
69
70    let mut old_candidates_len = candidates.len();
71    for _ in 0..max_iterations {
72        for i in 0..candidates.len() {
73            let aabb = &mut aabbs[candidates[i]];
74            let index = indices[candidates[i]];
75            let axis: usize = aabb.largest_axis();
76
77            let tri = triangles[index as usize];
78
79            let mut best_cost = f32::MAX;
80            let mut left = *aabb;
81            let mut right = *aabb;
82
83            // TODO optimization: create multiple splits simultaneously
84            for i in 1..split_tests {
85                let n = i as f32 / split_tests as f32;
86                let pos = aabb.min[axis] * n + aabb.max[axis] * (1.0 - n);
87
88                let mut tmp_left = *aabb;
89                let mut tmp_right = *aabb;
90
91                tmp_left.max[axis] = pos;
92                tmp_right.min[axis] = pos;
93                let verts = [tri.v0, tri.v1, tri.v2, tri.v0];
94                let (t_left, t_right) = split_triangle(axis as u32, pos, verts);
95                tmp_left = t_left.intersection(&tmp_left);
96                tmp_right = t_right.intersection(&tmp_right);
97                let area = tmp_left.half_area() + tmp_right.half_area();
98                if area < best_cost {
99                    best_cost = area;
100                    left = tmp_left;
101                    right = tmp_right;
102                }
103            }
104
105            let old_cost = aabb.half_area();
106
107            if (area_thresh_high > old_cost && best_cost * split_factor_high < old_cost)
108                || best_cost * split_factor_low < old_cost
109            {
110                *aabb = left;
111                candidates.push(aabbs.len());
112                aabbs.push(right);
113                indices.push(index);
114            }
115        }
116        if old_candidates_len == candidates.len() {
117            break;
118        } else {
119            candidates.retain(|c| aabbs[*c].half_area() > area_thresh_low);
120            old_candidates_len = candidates.len();
121        }
122    }
123}
124
125/// Based on <https://github.com/embree/embree/blob/be0accfd0b246e2b03355b8ee7710a22c1b49240/kernels/builders/splitter.h#L17C1-L49C6>,
126/// but with the "current bounds" moved out.
127pub fn split_triangle(dim: u32, pos: f32, v: [Vec3A; 4]) -> (Aabb, Aabb) {
128    let mut left = Aabb::INVALID;
129    let mut right = Aabb::INVALID;
130
131    // Clip triangle to left and right box by processing all edges
132    for i in 0..3 {
133        let v0 = v[i];
134        let v1 = v[i + 1];
135        let v0d = v0[dim as usize];
136        let v1d = v1[dim as usize];
137
138        if v0d <= pos {
139            // This point is on left side
140            left.extend(v0);
141        }
142        if v0d >= pos {
143            // This point is on right side
144            right.extend(v0);
145        }
146
147        // The edge crosses the splitting location
148        if (v0d < pos && pos < v1d) || (v1d < pos && pos < v0d) {
149            debug_assert!((v1d - v0d) != 0.0);
150            let inv_length = 1.0 / (v1d - v0d);
151            let c = Vec3A::mul_add(Vec3A::splat((pos - v0d) * inv_length), v1 - v0, v0);
152            left.extend(c);
153            right.extend(c);
154        }
155    }
156
157    (left, right)
158}
obvhs/splits.rs

obvhs/
splits.rs
