spatial - v1.0.1

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)

insert

</> 
pub fn insert(
  bvh: BVH(a),
  position: vec3.Vec3(Float),
  item: a,
  max_leaf_size max_leaf_size: Int,
) -> BVH(a)

Insert a new item into the BVH.

Uses Surface Area Heuristic (SAH) to find the best insertion point. Returns a new BVH with the item inserted.

Time Complexity: O(log n) average case.

Example

let bvh = bvh.from_items([#(vec3.Vec3(0.0, 0.0, 0.0), "item1")], max_leaf_size: 4)
let updated_bvh = bvh.insert(bvh, vec3.Vec3(1.0, 0.0, 0.0), "item2", 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.

refit

</> 
pub fn refit(bvh: BVH(a)) -> BVH(a)

Refit the BVH bounds after items have been modified.

This is cheaper than rebuilding but doesn’t optimize the tree structure. Use this when items haven’t moved much, or rebuild when structure degrades.

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

Example

let refitted_bvh = bvh.refit(bvh)

remove

</> 
pub fn remove(
  bvh: BVH(a),
  predicate: fn(a) -> Bool,
) -> Result(BVH(a), Nil)

Remove an item from the BVH by comparing values using equality.

Returns a new BVH with the item removed, or the original BVH if not found.

Time Complexity: O(n) worst case (must search all leaves).

Example

let bvh = bvh.from_items([...], max_leaf_size: 4)
let updated_bvh = bvh.remove(bvh, fn(item) { item == "item_to_remove" })

update

</> 
pub fn update(
  bvh: BVH(a),
  predicate: fn(a) -> Bool,
  new_position: vec3.Vec3(Float),
  new_item: a,
  max_leaf_size max_leaf_size: Int,
) -> Result(BVH(a), Nil)

Update an item’s position in the BVH.

This is equivalent to removing the old item and inserting it at the new position.

Time Complexity: O(n + log n) = O(n) due to removal requiring search.

Example

let bvh = bvh.from_items([...], max_leaf_size: 4)
let updated_bvh = bvh.update(
  bvh,
  fn(item) { item.id == target_id },
  new_position,
  updated_item,
  max_leaf_size: 4
)
✨ Search Document