What are bounding volume hierarchies?

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.

Definition

A bounding volume hierarchy is a tree data structure on a set of geometric objects. 

• All geometric objects are wrapped in bounding volumes that form the tree's nodes. 

• These nodes are then grouped as small sets and enclosed within the larger bounding volumes, forming the hierarchy of the tree. 

• 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. 

• The choice of bounding volume can impact the efficiency of the BVH and is often chosen based on a trade-off between precision and computational speed.

Purpose of BVH

• The major purpose of using a bounding volume hierarchy is to minimize the number of ray-object intersection tests required in ray tracing algorithms. 

• Instead of testing each ray against every object in the scene, BVH allows the algorithm to test the ray against a bounding volume.

• If the ray does not intersect the bounding volume, all objects within that volume are automatically discarded, leading to significant computational savings.

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.

Here,

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

  • Suppose that the polygon is made of 6000 triangles.

  • The ray-object intersection test with the $5$ rays would be:

    • $5 \times 6000 = 30000$

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

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

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

    • $2 \times 6000 = 12000$

Note:

• Wrap things that are hard to check for intersection in things that are easy to check.

• Always check for intersection with the simple shape first.

Ray-object intersection test

The number of ray-object intersection tests can be a significant factor affecting the performance of a ray tracing algorithm.

You can quantify the tests by using the approach explained below.

Calculation

• Total rays: The total number of rays can be calculated based on the size of the image and the number of rays per pixel.

  • Each pixel in the image represents one primary ray sent from the camera into the scene.

  • If multiple rays are cast per pixel, the number is multiplied by the rays per pixel.

• Number of ray-object intersection tests: The number of tests can be calculated by multiplying the total number of rays with the number of triangles (or other geometric form that the object is composed of) in the object.

Note: The above formula assumes a brute force approach where each ray is tested against every triangle in the object.

Example

Let's consider an example.

• Size of an image $=$ $1920 \times 1080$ pixels

• Rays per pixel $= 4$

• Number of triangles $= 1000$

• Calculate the total rays as follows:

  • $total \; \; rays = \text{image width} \times \text{image height} \times \text{rays per pixel}$

  • $total\; \; rays = 1920 \times 1080 \times 4 = 8,294,400$

• Then, we calculate the number of ray-object intersection tests:

  • $\text{number of ray-object intersection tests} = \text{total rays} \times \text{number of triangles in the object}$

  • $\text{number of ray-object intersection tests} = 8,294,400 \times 1000 = 8,294,400,000$

In this example, the ray tracer must perform over 8 billion ray-triangle intersection tests. It clearly illustrates the need for efficient data structures like bounding volume hierarchies to reduce the number of intersection tests and improve overall performance.

Cost calculation in BVH

In terms of efficiency, it is important to balance the cost of testing rays against the bounding volumes and the cost of intersecting the objects within.

The formula to calculate the cost is given below.

Where,

• $n$ is the number of rays tested against the bounding volume.

• $B$ is the cost of each test.

• $m$ is the number of rays which hit the bounding volume.

• $I$ is the cost of intersecting the object within.

The cost here serves as a measure to compare different BVH structures or split strategies during the BVH construction process.

Strategies for optimizing BVH

There are many ways to build a tree for bounding volume hierarchy.

• Sort the surfaces along the axis before dividing into two boxes

• Carefully choose axis each time

• Choose axis that minimizes the sum of volumes

Bounding volume hierarchies work well with:

• Binary trees

• Roughly balanced trees

  • Boxes of sibling trees not overlapping too much

Demonstration