Median-split BVH builder. Not as tight as SAH but 3-5× faster to build, and for our scene sizes (tens to low hundreds of thousands of triangles) the intersection cost difference is negligible. We can revisit this if Phase 4 needs tighter trees.
(
items: &mut [BvhItem],
offset: usize,
nodes: &mut Vec<BvhNode>,
order: &mut Vec<u32>,
node_index: usize,
)
| 748 | /// of triangles) the intersection cost difference is negligible. We |
| 749 | /// can revisit this if Phase 4 needs tighter trees. |
| 750 | fn build_bvh_recursive( |
| 751 | items: &mut [BvhItem], |
| 752 | offset: usize, |
| 753 | nodes: &mut Vec<BvhNode>, |
| 754 | order: &mut Vec<u32>, |
| 755 | node_index: usize, |
| 756 | ) { |
| 757 | // Compute combined bounds for this subtree. |
| 758 | let mut bmin = Vec3::splat(f32::INFINITY); |
| 759 | let mut bmax = Vec3::splat(f32::NEG_INFINITY); |
| 760 | for it in items.iter() { |
| 761 | bmin = bmin.min(it.bounds_min); |
| 762 | bmax = bmax.max(it.bounds_max); |
| 763 | } |
| 764 | |
| 765 | const LEAF_THRESHOLD: usize = 4; |
| 766 | if items.len() <= LEAF_THRESHOLD { |
| 767 | let first = order.len() as u32; |
| 768 | for it in items.iter() { |
| 769 | order.push(it.triangle_index); |
| 770 | } |
| 771 | nodes[node_index] = BvhNode { |
| 772 | bounds_min: bmin, |
| 773 | bounds_max: bmax, |
| 774 | first_triangle: first, |
| 775 | tri_count: items.len() as u32, |
| 776 | }; |
| 777 | return; |
| 778 | } |
| 779 | |
| 780 | // Split on the longest axis of the centroid bounds (not the |
| 781 | // triangle bounds — the centroid bounds give the meaningful split |
| 782 | // range even when triangles are large). |
| 783 | let mut cmin = Vec3::splat(f32::INFINITY); |
| 784 | let mut cmax = Vec3::splat(f32::NEG_INFINITY); |
| 785 | for it in items.iter() { |
| 786 | cmin = cmin.min(it.centroid); |
| 787 | cmax = cmax.max(it.centroid); |
| 788 | } |
| 789 | let extent = cmax - cmin; |
| 790 | let axis = if extent.x > extent.y && extent.x > extent.z { |
| 791 | 0 |
| 792 | } else if extent.y > extent.z { |
| 793 | 1 |
| 794 | } else { |
| 795 | 2 |
| 796 | }; |
| 797 | |
| 798 | // Median split: partial sort so the middle item has the actual median. |
| 799 | // select_nth_unstable is O(N); a full sort would be O(N log N). |
| 800 | let mid = items.len() / 2; |
| 801 | items.select_nth_unstable_by(mid, |a, b| { |
| 802 | let av = match axis { |
| 803 | 0 => a.centroid.x, |
| 804 | 1 => a.centroid.y, |
| 805 | _ => a.centroid.z, |
| 806 | }; |
| 807 | let bv = match axis { |