Overview
BVH traversal quickly rejects large groups of primitives whose boxes a ray misses, reducing the number of expensive primitive intersections.
CoreSource checked
BVH Traversal
Tests rays against a hierarchy of bounding volumes before testing contained geometry.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Rendering
- Difficulty
- Intermediate
- Family
- Acceleration Structure
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Bounding Volume Hierarchy Traversal
Core Concepts
bounding volumeray-box testtree traversalprimitive intersection
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n)
Worst
O(n)
Space
O(depth)
When to Use
- Use when real-time graphics needs bounding volume.
- Use when the input matches the assumptions behind acceleration Structure.
When Not to Use
- Avoid when the effect costs more than the visual improvement for the target hardware.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Tests rays against a hierarchy of bounding volumes before testing contained geometry
- Uses bounding volume and ray-box test to guide the work.
- Produces rendered image.
Use Cases
- Real-time graphics
- Offline rendering
- Lighting and visibility effects
Inputs
- Scene geometry
- Materials
- Camera and lighting state
Outputs
- Rendered image
- Visibility or shading buffers
Key Formulas (1)
Ray equation
p(t) = origin + t · direction
p(t) = origin + t * directionFinds a point along a ray for intersection or shading work.
Pseudocode
- 1.Prepare the inputs and state needed for BVH Traversal.
- 2.Apply the bounding volume step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return rendered image.
Canonical Example
- Input
- ray and a BVH over triangle bounds
- Output
- nearest candidate triangle hit
- Explanation
- Traversal tests the ray against bounding boxes first and descends only into intersected nodes.
Implementation Notes
- Check node bounding boxes before primitive tests.
- Visit nearer children first when ray distances are available.
- Keep leaf primitive ranges compact for cache-friendly traversal.
Common Pitfalls
- Traversing child nodes in an order that misses nearer hit pruning opportunities.
- Using stale bounds after geometry changes.
- Testing every primitive even after a closer hit bounds later work.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow rays, samples, buffers, or shading terms that contribute to the final pixel.
Step 1 of 4: Prepare the inputs and state needed for BVH Traversal.
rendering-mechanismNotes
BVH Traversal should be used with the assumptions and tradeoffs of acceleration Structure in mind.
Sources (1)
What each reference supports for this entry.
Physically Based Rendering
BookRendering reference covering bounding volume hierarchies and ray-acceleration traversal.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageDepends onBounding Volume Hierarchy Construction
Traversal requires a built hierarchy of bounding volumes.
Used byRay Tracing
Ray tracers use BVH traversal to skip large sets of primitives.
Often paired withRay-Triangle Intersection
BVH traversal often ends by testing rays against triangles.
Related Algorithms
Tags
GraphicsAcceleration StructureRay IntersectionSpatial Index