CoreSource checked

Bounding Volume Hierarchy Construction

Builds a tree of bounding volumes around geometry for faster spatial queries.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Advanced
Family: Spatial Index Construction
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 3
Code example: Ready
Visualization: Ready
Aliases: BVH Construction

Overview

BVH construction recursively groups primitives into bounding boxes, often using split heuristics that reduce expected traversal cost.

Core Concepts

bounding boxprimitive partitionsurface area heuristicspatial tree

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use when collision and intersection tests needs bounding box.
Use when the input matches the assumptions behind spatial Index Construction.

When Not to Use

Avoid when floating-point robustness is critical and no tolerance strategy is defined.
Avoid when a simpler algorithm gives the required result with less setup.

What It Does

Builds a tree of bounding volumes around geometry for faster spatial queries
Uses bounding box and primitive partition to guide the work.
Produces geometric relation, simplified shape, or constructed geometry.

Use Cases

Collision and intersection tests
Shape analysis
Geometry processing

Inputs

Points, segments, polygons, or meshes
Query shape or tolerance

Outputs

Geometric relation, simplified shape, or constructed geometry

Key Formulas (1)

Surface area heuristic

cost = traversal_cost + (area_left/area_parent)·n_left + (area_right/area_parent)·n_right

cost = traversal_cost + (area_left/area_parent)*n_left + (area_right/area_parent)*n_right

Scores a split by expected traversal work.

Pseudocode

1.Prepare the inputs and state needed for Bounding Volume Hierarchy Construction.
2.Apply the bounding box step while the stopping condition has not been met.
3.Update intermediate state and discard invalid candidates.
4.Return geometric relation, simplified shape, or constructed geometry.

Canonical Example

Input: Bounding Volume Hierarchy Construction with a minimal inspectable input
Output: Geometric relation, simplified shape, or constructed geometry
Explanation: Bounding Volume Hierarchy Construction applies bounding box to produce geometric relation, simplified shape, or constructed geometry.

Implementation Notes

Use robust orientation and tolerance checks for boundary cases.
Keep the bounding box step separate enough to test independently.

Common Pitfalls

Degenerate cases such as collinear points or shared edges often need explicit handling.
Forgetting to check edge cases can make Bounding Volume Hierarchy Construction look correct on only ideal inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Draw the input shapes, active tests, and generated geometric result.

Step 1 of 4: Prepare the inputs and state needed for Bounding Volume Hierarchy Construction.

geometry-mechanism

Notes

Bounding Volume Hierarchy Construction should be used with the assumptions and tradeoffs of spatial Index Construction in mind.

Sources (2)

What each reference supports for this entry.

Real-Time Collision Detection

Book

Geometric collision reference for Bounding Volume Hierarchy Construction's primitive tests, bounding volumes, and numerical edge cases.

Physically Based Rendering

Book

Rendering reference for Bounding Volume Hierarchy Construction's ray queries, acceleration structures, or implicit-geometry use case.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Often paired withAxis-Aligned Bounding Box Intersection

Geometry · Foundation

BVHs commonly store axis-aligned bounding boxes.

Compare with this

Prerequisite ofBVH Traversal

Rendering · Core

Traversal requires a constructed bounding volume hierarchy.