Bounding Volume Hierarchies (BVH)
As it can be understood from the title of this post, I have finally implemented BVH ( Bounding Volume Hierarchy)[1] in my ray tracer. It provided huge speed up in terms of render times so I have much more free time from now on, YAY !
Since I have more time now I will spend it on talking about BVH to show my gratitude…
BVH is a spatial partitioning tree structure, in which geometric objects are wrapped in bounding volumes. Leaf nodes of BVH structure represents the actual geometric objects where intermediate nodes represent bounding volumes of its descendants.
Figure-1: BVH illustration, on left objects are wrapped by bounding volumes, on right associated spatial tree structure[1]
As result of this structure, in ray tracing we can easily find the objects that intersect with the rays by traversing BVH structure. While traversing we check if the incoming rays intersect the bounding volume of the tree nodes, if so we recurse to left and right children of the current tree node and at the end we try to end up in leaf nodes where actual object and ray intersection happens. We then select the intersection that provides minimum distance according to the ray origin (closest object that intersects with ray). If ray does not intersect with the bounding volume of any node in tree we can immediately return false since it is not possible that it can not intersect the objects that are bounded by this node.
A sample(non-optimized) code for traversing BVH structure is as follows:
bool BVH::traverse(Ray r, HitRecord &hitRecord)
{
if (this->intersectRay(r, hitRecord))
{
HitRecord leftRecord, rightRecord;
//Recurse on left child
if (this->leftChild != nullptr && this->leftChild->traverse(r, leftRecord))
{
hitRecord = HitRecord(leftRecord);
}
//Recurse on right child
if (this->rightChild != nullptr && this->rightChild->traverse(r, rightRecord))
{
if (rightRecord.getDistance() < hitRecord.getDistance())
{
hitRecord = HitRecord(rightRecord);
}
}
return true;
}
else
{
return false;
}
}
My rendering results for two famous models with 92K and 871K triangles with BVH and multi-threading is enabled, are as follows:
BVH is constructed in 0.16 seconds
Total triangle count 92092
Rendered model killeroo.png in 0.36 seconds
Figure-2: Rendered Killeroo model
BVH is constructed in 1.81 seconds
Total triangle count 871414
Rendered model dragon.png in 0.75 seconds
Figure-3: Rendered Dragon model
References