spatial/bvh

Bounding Volume Hierarchy (BVH) for efficient spatial queries.

BVH is a tree structure where each node contains a bounding box that encompasses all its children. Excellent for dynamic scenes and collision detection.

Types

BVH

opaque </>

BVH node for spatial partitioning.

Industry standard for game engines and physics systems.

pub opaque type BVH(a)

Values

bounds

</>

pub fn bounds(bvh: BVH(a)) -> collider.Collider

Get the root bounds of the BVH.

count

</>

pub fn count(bvh: BVH(a)) -> Int

Count total items in the BVH.

Time Complexity: O(n) where n is the total number of items.

from_items

</>

pub fn from_items(
  items: List(#(vec3.Vec3(Float), a)),
  max_leaf_size max_leaf_size: Int,
) -> Result(BVH(a), Nil)

Create a new BVH from a list of positioned items.

Uses Surface Area Heuristic (SAH) for optimal splits.

Time Complexity: O(n log n) where n is the number of items.

Example

let items = [
  #(vec3.Vec3(0.0, 0.0, 0.0), "item1"),
  #(vec3.Vec3(10.0, 0.0, 0.0), "item2"),
]
let bvh = bvh.from_items(items, max_leaf_size: 4)

query

</>

pub fn query(
  bvh: BVH(a),
  query_bounds: collider.Collider,
) -> List(#(vec3.Vec3(Float), a))

Query all items within a collider region.

Time Complexity: O(log n + k) average case where k is the number of results. Worst case O(n) if query region covers entire BVH.

query_all

</>

pub fn query_all(bvh: BVH(a)) -> List(#(vec3.Vec3(Float), a))

Query all items in the BVH.

Time Complexity: O(n) where n is the total number of items.

query_radius

</>

pub fn query_radius(
  bvh: BVH(a),
  center: vec3.Vec3(Float),
  radius: Float,
) -> List(#(vec3.Vec3(Float), a))

Query all items within a radius of a point.

Time Complexity: O(log n + k) average case where k is the number of results.