How to Build a BVH (Bounding Volume Hierarchy) on the CPU | Hacker News Reader

How to Build a BVH (Bounding Volume Hierarchy) on the CPU

jacco.ompf2.com

59 pointshenkie_b11 comments

A year or so ago I wrote a raytracer in swift (writing RTs is how I learn languages, and they’re not the super fancy advanced feature ones, think university assignment), and actually made a BVH for a change. It is amazing the perf difference you get from binned construction, it obviously makes sense when you actually think about it, but until you do think you don’t know just how much perf you’re losing.

It’s nice to see the surface area heuristic still hasn’t gone anywhere :)

Three articles (so far) describing how to build a BVH and traverse it with a ray, on the CPU. Includes compact source code for each article.

Article 4 (on refitting) and 5 (constructing BLAS + TLAS) should arrive this week, completing the basic C++ implementation of the algorithm used for DXR / RTX.

I skimmed through the series last night and enjoyed it. It's a nice basic overview so far and will be handy to point to for anyone who wants to learn the basics of this stuff. I look forward to seeing the rest of it.

As I didn't know what the BVH is, from the first, OP linked article: In this series we explore the wonderful world of the bounding volume hierarchy: the mysterious data structure that enables real-time ray tracing on recent GPUs, in complex, animated scenes. Despite the broad adoption of ray tracing in games, in-depth understanding of the underlying technology seems to be reserved to a select few. In this article we show how a proper BVH is implemented without support from DXR / RTX / OptiX / Vulkan, in easy-to-read ‘sane C++’.

Interesting. Thanks for posting.

https://en.wikipedia.org/wiki/Bounding_volume_hierarchy

_A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, that form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree. Bounding volume hierarchies are used to support several operations on sets of geometric objects efficiently, such as in collision detection and ray tracing._

If you're curious about this area, Real-Time Collision Detection[1] is one of my favorite technical books on this topic. While the title is "Collision Detection" it's basically data structures for 2D/3D. It's also the only algorithms book I've seen to actually have a section on CPU cache-aware algorithms instead of assuming you only care about big-O notation.

[1] https://www.amazon.com/Real-Time-Collision-Detection-Interac...

With a good BVH, the time to render an image becomes O(k*logn) where k is the number of pixels and n is the number of primitives (triangles). This scales with scene complexity better than anything the raster APIs have done in the past 50 years. The issue has always been a largish constant factor and ever increasing resolutions.

The time to render an image is O(k log n), but the space required for any given pixel is O(log n). A BVH search is a recursive operation. Each pixel needs its own stack.

Rasterizing triangles requires O(1) space. So you can cram 4096 or whatever very, very dumb "cores" into a GPU that can rasterize, but if you want to spend the same amount of silicon to raytrace? Not so much.

I miss TBP and the original ompf :'(

Reply on news.ycombinator.com