[HN Gopher] How to Build a BVH (Bounding Volume Hierarchy) on th...
___________________________________________________________________
How to Build a BVH (Bounding Volume Hierarchy) on the CPU
Author : henkie_b
Score : 46 points
Date : 2022-04-22 18:55 UTC (2 days ago)
(HTM) web link (jacco.ompf2.com)
(TXT) w3m dump (jacco.ompf2.com)
| olliej wrote:
| 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 :)
| froh wrote:
| 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._
| vvanders wrote:
| 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...
| phkahler wrote:
| 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.
| henkie_b wrote:
| 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.
| HWR_14 wrote:
| Interesting. Thanks for posting.
| froh wrote:
| 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++'._
| jbikker wrote:
| 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.
| a_e_k wrote:
| 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.
| pixelpoet wrote:
| I miss TBP and the original ompf :'(
___________________________________________________________________
(page generated 2022-04-24 23:01 UTC)