3 ms·

https://en.wikipedia.org/wiki/Bounding_volume_hierarchy https://en.wikipedia.org/wiki/Bounding_volume_hierarchy _A bounding volume hierarchy (BVH) is a tree st

by froh 5y ago

https://en.wikipedia.org/wiki/Bounding_volume_hierarchy 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 5y ago
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-Interactive-Technology/dp/1558607323 https://www.amazon.com/Real-Time-Collision-Detection-Interac...
phkahler 5y ago
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.
- nwallin 5y ago
  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.

by froh 5y ago

vvanders 5y ago

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-Interactive-Technology/dp/1558607323 https://www.amazon.com/Real-Time-Collision-Detection-Interac...

phkahler 5y ago

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.

nwallin 5y ago
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.