fn build_r(
        &mut self,
        infos: &mut [BvhObjectInfo],
        mut method: BvhPartitionMethod,
    ) -> Option<usize> {
        match infos.len() {
            0 => None,
            1 => {
                self.nodes.push(BvhNode::Leaf {
                    obj_i: infos[0].index,
                });
                Some(self.nodes.len() - 1)
            }
            _ => {
                let aabb = infos
                    .iter()
                    .fold(Aabb::default(), |aabb, o| aabb.union(o.aabb));
                let centroid_bounds = infos
                    .iter()
                    .fold(Aabb::default(), |aabb, o| aabb.union_p(o.centroid));
                let axis = centroid_bounds.max_extent();
                let (left_o, right_o) = loop {
                    let (left_o, right_o) = match method {
                        BvhPartitionMethod::Middle => {
                            let midpoint = (centroid_bounds.minimum[axis as usize]
                                + centroid_bounds.maximum[axis as usize])
                                / 2.;
                            let pivot_i = itertools::partition(infos.iter_mut(), |o| {
                                o.centroid[axis as usize] < midpoint
                            });
                            if pivot_i == 0 || pivot_i == infos.len() {
                                method = BvhPartitionMethod::EqualCount;
                                continue;
                            }
                            infos.split_at_mut(pivot_i)
                        }
                        BvhPartitionMethod::EqualCount => {
                            let pivot_i = infos.len() / 2;
                            infos.select_nth_unstable_by(pivot_i, |a, b| {
                                a.centroid[axis as usize]
                                    .partial_cmp(&b.centroid[axis as usize])
                                    .unwrap_or(Ordering::Equal)
                            });
                            infos.split_at_mut(pivot_i)
                        }
                    };
                    break (left_o, right_o);
                };
                self.nodes.push(BvhNode::Inner {
                    aabb,
                    axis,
                    left_i: None,
                    right_i: None,
                });
                let inner_i = self.nodes.len() - 1;
                let new_left_i = self.build_r(left_o, method);
                let new_right_i = self.build_r(right_o, method);
                if let BvhNode::Inner {
                    left_i, right_i, ..
                } = &mut self.nodes[inner_i]
                {
                    *left_i = new_left_i;
                    *right_i = new_right_i;
                }
                Some(inner_i)
            }
        }
    }
/// Build the BVH recursively using a slice of objects and a partitioning
/// method. See http://www.pbr-book.org/3ed-2018/Primitives_and_Intersection_Acceleration/Bounding_Volume_Hierarchies.html#BVHConstruction

Build the BVH recursively using a slice of objects and a partitioning
method.
Build the BVH recursively using a slice of objects and a partitioning method .
fn build_r(
        &mut self,
        infos: &mut [BvhObjectInfo],
        mut method: BvhPartitionMethod,
    ) -> Option<usize> {
        match infos.len() {
            0 => None,
            1 => {
                self.nodes.push(BvhNode::Leaf {
                    obj_i: infos[0].index,
                });
                Some(self.nodes.len() - 1)
            }
            _ => {
                let aabb = infos
                    .iter()
                    .fold(Aabb::default(), |aabb, o| aabb.union(o.aabb));
                let centroid_bounds = infos
                    .iter()
                    .fold(Aabb::default(), |aabb, o| aabb.union_p(o.centroid));
                let axis = centroid_bounds.max_extent();
                let (left_o, right_o) = loop {
                    let (left_o, right_o) = match method {
                        BvhPartitionMethod::Middle => {
                            let midpoint = (centroid_bounds.minimum[axis as usize]
                                + centroid_bounds.maximum[axis as usize])
                                / 2.;
                            let pivot_i = itertools::partition(infos.iter_mut(), |o| {
                                o.centroid[axis as usize] < midpoint
                            });
                            if pivot_i == 0 || pivot_i == infos.len() {
                                method = BvhPartitionMethod::EqualCount;
                                continue;
                            }
                            infos.split_at_mut(pivot_i)
                        }
                        BvhPartitionMethod::EqualCount => {
                            let pivot_i = infos.len() / 2;
                            infos.select_nth_unstable_by(pivot_i, |a, b| {
                                a.centroid[axis as usize]
                                    .partial_cmp(&b.centroid[axis as usize])
                                    .unwrap_or(Ordering::Equal)
                            });
                            infos.split_at_mut(pivot_i)
                        }
                    };
                    break (left_o, right_o);
                };
                self.nodes.push(BvhNode::Inner {
                    aabb,
                    axis,
                    left_i: None,
                    right_i: None,
                });
                let inner_i = self.nodes.len() - 1;
                let new_left_i = self.build_r(left_o, method);
                let new_right_i = self.build_r(right_o, method);
                if let BvhNode::Inner {
                    left_i, right_i, ..
                } = &mut self.nodes[inner_i]
                {
                    *left_i = new_left_i;
                    *right_i = new_right_i;
                }
                Some(inner_i)
            }
        }
    }
fn build_r ( & mut self , infos : & mut [ BvhObjectInfo ] , mut method : BvhPartitionMethod , ) -> Option < usize > { match infos . len ( ) { 0 => None , 1 => { self . nodes . push ( BvhNode :: Leaf { obj_i : infos [ 0 ] . index , } ) ; Some ( self . nodes . len ( ) - 1 ) } _ => { let aabb = infos . iter ( ) . fold ( Aabb :: default ( ) , | aabb , o | aabb . union ( o . aabb ) ) ; let centroid_bounds = infos . iter ( ) . fold ( Aabb :: default ( ) , | aabb , o | aabb . union_p ( o . centroid ) ) ; let axis = centroid_bounds . max_extent ( ) ; let ( left_o , right_o ) = loop { let ( left_o , right_o ) = match method { BvhPartitionMethod :: Middle => { let midpoint = ( centroid_bounds . minimum [ axis as usize ] + centroid_bounds . maximum [ axis as usize ] ) / 2. ; let pivot_i = itertools :: partition ( infos . iter_mut ( ) , | o | { o . centroid [ axis as usize ] < midpoint } ) ; if pivot_i == 0 || pivot_i == infos . len ( ) { method = BvhPartitionMethod :: EqualCount ; continue ; } infos . split_at_mut ( pivot_i ) } BvhPartitionMethod :: EqualCount => { let pivot_i = infos . len ( ) / 2 ; infos . select_nth_unstable_by ( pivot_i , | a , b | { a . centroid [ axis as usize ] . partial_cmp ( & b . centroid [ axis as usize ] ) . unwrap_or ( Ordering :: Equal ) } ) ; infos . split_at_mut ( pivot_i ) } } ; break ( left_o , right_o ) ; } ; self . nodes . push ( BvhNode :: Inner { aabb , axis , left_i : None , right_i : None , } ) ; let inner_i = self . nodes . len ( ) - 1 ; let new_left_i = self . build_r ( left_o , method ) ; let new_right_i = self . build_r ( right_o , method ) ; if let BvhNode :: Inner { left_i , right_i , .. } = & mut self . nodes [ inner_i ] { * left_i = new_left_i ; * right_i = new_right_i ; } Some ( inner_i ) } } }
Build the BVH recursively using a slice of objects and a partitioning
method.
Build the BVH recursively using a slice of objects and a partitioning method .
&mut self
infos
&mut [BvhObjectInfo]
method
BvhPartitionMethod
&mut self
infos
&mut [BvhObjectInfo]
method
BvhPartitionMethod