Bounding Volume Hierarchy
Background: Imagine that you are writing your own ray tracer. For it to work, you need to fire rays. The more the rays, the better will be the image. But now you also need to check where these rays intersect your geometry. To check this, you need to actually solve for ray-triangle intersection.
What needs to be fixed: If you have a geometry with a million triangles, and you are shooting a million rays, you now need to calculate ray-triangle intersection a million x million times. That is huge! You definitely don’t want to do that unless you have a really high end hardware. I am not sure if it will run realtime on that too. This for sure needs fixing!
How to fix it: What if I tell you that you don’t need to check million x million times. Let’s divide our geometry into chunks of cubes/cuboids. If a ray doesn’t hit the bounding box (cuboid) of that chunk, we can directly ignore all the triangles inside that box. This significantly reduces the number of checks needed to be done and improves search efficiency. This is the crux of BVH! BVH comes under spatial partitioning algorithms. Some other techniques that come under space partitioning are Trees (quad, oct, k-d, BSP, r).
When to use it: This is not just useful for ray tracing, but has usages wherever you have to query for object positions. When this querying is causing a performance hit, you may need to think of ways to store geometry hierarchically. Technically it brings down a O(n) or O(n²) search to a lower complexity.
Things to note: Since we divide the scene into chunks, we may need to recalculate the BVH as the scene moves/changes. Also this requires additional bookkeeping for this data. BVH based search trades memory for speed. Considering all these things, you may need to take decision on how you want to use it.
I hope you learnt something new today!
