I am working on a series of blog posts on constructing a BVH, in straight 'sane' C++, with source code on Github:
https://jacco.ompf2.com/2022/04/13/how-to-build-a-bvh-part-1-basics/
and
https://github.com/jbikker/bvh_article
Three articles have been released so far:
* Basics
* Faster rays
* Binned building
Two more articles are planned, one on BVH refitting, one on TLAS/BLAS for animated scenes.
Comments are welcome, e.g. via Twitter, @j_bikker.
How to build a BVH - tutorial + code
Great to see you still work on some tutorials. I've learned the basics of raytracing from yours at flipcode. :D
There really seems a need for BVH tutorials. Did some ‘BVH8 in a nutshell’ tutorial recently within this post, covering some similar things: https://www.gamedev.net/forums/topic/712135-lots-and-lots-of-triangles-how-to-accelerate-ray-triangle-intersection/5447159/
Nice stuff! But: isn't that an octree rather than BVH8? A BVH4 or BVH8 would normally be created by collapsing a regular BVH (a BVH2 if you will); that way, you keep the adaptive planes and the object partitioning. Octrees split at a fixed point and they split space, so primitives can be in multiple nodes. You can expect significantly better ray tracing performance from a BVH, see my post on SAH.
phantomus said:
Nice stuff! But: isn't that an octree rather than BVH8? A BVH4 or BVH8 would normally be created by collapsing a regular BVH (a BVH2 if you will); that way, you keep the adaptive planes and the object partitioning. Octrees split at a fixed point and they split space, so primitives can be in multiple nodes. You can expect significantly better ray tracing performance from a BVH, see my post on SAH.
Maybe that's subject of personal interpretation, as often if terms are not strictly defined. Personally i think BVHx only means one node has x children, independent of construction algorithm or special properties, not sure.
But yes, my sample splits the nodes at the center of the parent bound giving 8 sub spaces, so the construction algorithm feels very similar to octree. It's fast to build and simple, but ignores other goals like a balanced tree or SAH for faster RT.
phantomus said:
Octrees split at a fixed point and they split space, so primitives can be in multiple nodes.
I use the octant sub spaces only to bin the centers of objects to 8 new children. The bounds of objects then still form overlapping node bounds, and each object is contained only in one node, as usual with BVH.
Though, the same is possible with octree too, if we use a loose octree. At this point it's hard to make a distinction between octree and BVH, because technically a loose octree is both of them.
And btw, that's exactly why i think people need BVH tutorials. It seems most people still prefer octree. It's just the most known spatial acceleration structure.
Then, eventually they notice Octree sucks, because objects go into multiple nodes. And they find the solution is a loose octree, which extends the implicit bounds of a node by a factor of two and stores large objects in internal nodes.
At his point we have a tree which works well for both collision detection and tracing, but we need to rebuild the tree each frame if objects move.
The next step to solve this is BVH, because it no longer relies on the world space grid. Thus we can keep lower branches of the tree, only refitting their bounds under movement, and only rebuilding the top levels.
That's a lot of advantages for the cost of storing the bound per node, so usually it's the best solution. But i feel like many people are not aware about advantages / disadvantages, or they think BVH would be more complex and harder, etc.
Maybe this improves now, as DXR makes the top / low level approach + BVH more popular.
Now, @phantomus this is a name I haven't heard in quite long time (probably since the time original ompf died). You, sir, were a great source of inspiration and knowledge back in the day prior to me going to university and when studying it (and always digging as deep in underlying base concepts in rendering). Let me say Thank you properly here first. I'm very glad to see you're still writing. The articles are, as always, readable and very informative.
Now - as for my comment - I saw that in planned articles is a variation of Split-BVH, from my experience those builders tend to be quite slow (and I've ended up storing Split-BVHs on hard drive precomputed for static BLAS) - is there some future master plan to include also high performance ones (like HLBVH), or even a (massively) parallel variants? I read through PBRTv3 part on the former, but never really got through the latter (never really needed it though so far).
My current blog on programming, linux and stuff - http://gameprogrammerdiary.blogspot.com
Hi @vilem otte , good to see you here. ? The return of the phantom is a bit of a coincidence, my account here is ancient although dormant.
Regarding SBVH (and quick building in general): this is not a technique that is generally used for runtime BVH construction, but it is definitely possible to make it very rapid. E.g., in the Bonsai algorithm the authors propose a SBVH approximation that gets close to full SBVH, while at the same time reaching state-of-the-art CPU BVH construction performance. Check it out here:
https://fileadmin.cs.lth.se/graphics/research/papers/2016/splitting/
This paper is by now 7 years old, yet it builds a BVH for 12M triangles in less than 2 seconds. You can probably beat that by loading the BVH from disk, but the gains are (for me) not worth it, I prefer the rebuild.
For the articles, I will stick with the basic concepts for now (talking about SIMD in article 2 was a mistake); perhaps at the end I will discuss ways to improve performance. As the SAH and binning articles show, algorithmic improvements have far more impact than low-level tricks. That doesn't mean we shouldn't do the low-level tricks of course, those are the most fun. ?
And article 5. There will be one more, in which full animation with a scene graph will be discussed. Link to article 5:
https://jacco.ompf2.com/2022/05/07/how-to-build-a-bvh-part-5-tlas-blas/
Article 6, 7, 8 and 9 have been released in the meantime. Article 8 applies the BVH to real-time recursive ray tracing of an animated scene on the CPU; article 9 takes this to the GPU using OpenCL. Article 9 basically is an OpenCL tutorial, using the BVH code as an example.
The final article is expected somewhere next week.
Hey @phantomus just wanted to let you know how awesome your BVH articles are. Really well put together and immensely helpful. I've seen some references to using SIMD for querying BVH's as it allows you to simultaneously test against multiple AABB's. Just wondering if you've had any experience with that