Bounding Volume Hierarchy (BHV)

Bounding volume hierarchy (BVH) is an advanced data structure widely used in computer graphics, especially in ray tracing algorithms. The primary function of BVH is to effectively organize geometric data, such as polygons or triangles that compose a 3D model, to accelerate the process of ray-object intersection tests

1. Definition of Bounding Volume Hierarchy (BVH):

Each node of a tree is associated with a subset of primitives of the objects together with a bounding volume (BV) that encloses this subset with the smallest instance of some specified class of shape.

modeling
Figure 1. BHV construction

A bounding volume can take various forms, such as a sphere, a box (AABB - Axis Aligned Bounding Box), or an oriented bounding box (OBB), depending on the application’s specific requirements.

modeling
Figure 2. Various forms of BVH

2. How to construct BVH

The process of constructing a bounding volume hierarchy is explained below.

  • Object partitioning: It involves partitioning the objects in the scene into two groups. Several strategies to do this include a median or a surface area heuristic (SAH).

  • Bounding volume creation: After partitioning, a bounding volume is created for each group, encapsulating all the objects within.

  • Recursive splitting: The process is repeated recursively, further splitting each group and creating bounding volumes until each group contains only one object.

without
Figure 3. Ray tracing to a surface without bvh
with
Figure 4. Ray tracing to a surface with bvh

Here,

  • Slide 1: It shows a polygon with 5 intersection rays.

    1. Suppose that the polygon is made of 6000 triangles.

    2. The ray-object intersection test with the 5 rays would be:

      5×6000 = 30000

  • Slide 2: It shows a polygon with the bounding volume (a square).

    1. We need to check for intersection with the simple shape first.

    2. Since, only 2 rays are intersecting the bounding volume, the number of ray-object intersection tests can be reduced to:

      2×6000 = 12000

In these two parts of code, we construct the BVH using two different methods: The BVH is constructed by calling bvh::v2::DefaultBuilder<node_type>::build with the bounding boxes, centers, and configuration. The result is stored in M_bvh, which is a std::unique_ptr pointing to the constructed BVH object.

typename bvh::v2::DefaultBuilder<node_type>::Config config;
 switch ( this->M_quality )
 {
 default:
 case BVHEnum::Quality::High: config.quality = bvh::v2::DefaultBuilder<node_type>::Quality::High; break;
 case BVHEnum::Quality::Medium: config.quality = bvh::v2::DefaultBuilder<node_type>::Quality::Medium; break;
 case BVHEnum::Quality::Low: config.quality = bvh::v2::DefaultBuilder<node_type>::Quality::Low; break;
 }
 M_bvh = std::make_unique<backend_bvh_type>( bvh::v2::DefaultBuilder<node_type>::build(/*thread_pool,*/ bboxes, centers, config) );

The buildTree method constructs the BVH by recursively traversing the primitives. It uses a stack to build the BVH tree by splitting the primitives based on their centroids and creating internal nodes or leaves depending on the number of primitives.

void buildTree()
 {
     if ( M_rootNode )
         return;
     M_rootNode = std::make_unique<BVHNode>();
     std::stack<std::tuple<BVHNode*,int,int,int>> stack;
     stack.push( std::make_tuple(M_rootNode.get(),0,0,this->M_primitiveInfo.size()) );
     // TODO case only one 1 element
     while ( !stack.empty() )
     {
         auto [currentNode,cut_dimension,start_index_primitive,end_index_primitive] = stack.top();
         stack.pop();
         int nPrimitives = end_index_primitive - start_index_primitive;
         auto [bound_min_node,bound_max_node] = nPrimitives > 0 ? this->bounds( start_index_primitive,end_index_primitive ) : std::make_tuple( vector_realdim_type{}, vector_realdim_type{});
         if ( nPrimitives <= 1 )
         {
             // Create a leaf, since there is only one primitive in the list
             int firstPrimOffset = M_orderedPrims.size();
             for (int i = start_index_primitive; i < end_index_primitive; ++i)
             {
                 int primNum = this->M_primitiveInfo[i].meshEntity().id();
                 M_orderedPrims.push_back(primNum);
             }
             currentNode->updateForUse( firstPrimOffset, nPrimitives, -1, bound_min_node, bound_max_node );
         }
         else
         {
             CHECK( start_index_primitive >=0 && end_index_primitive <= this->M_primitiveInfo.size() ) << start_index_primitive << " " << end_index_primitive;
             auto mid = (start_index_primitive + end_index_primitive) / 2;
             std::nth_element(&this->M_primitiveInfo[start_index_primitive], &this->M_primitiveInfo[mid],
                              &this->M_primitiveInfo[end_index_primitive-1]+1,
                              [cut_dimension=cut_dimension](primitiveinfo_type const&a, primitiveinfo_type const& b) {
                                  return a.centroid()[cut_dimension] < b.centroid()[cut_dimension];
                              });
             int next_cut_dimension=(cut_dimension+1)%nRealDim;
             auto childNode0 = currentNode->setChild( 0, std::make_unique<BVHNode>() );
             stack.push( std::make_tuple(childNode0, next_cut_dimension, start_index_primitive, mid) );
             auto childNode1 = currentNode->setChild( 1, std::make_unique<BVHNode>() );
             stack.push( std::make_tuple( childNode1, next_cut_dimension, mid, end_index_primitive ) );
             currentNode->updateForUse( -1, nPrimitives, next_cut_dimension, bound_min_node, bound_max_node );
         }
     }
 }

Next: Monte Carlo Method



back to main page