pico_bvh.h File Reference

A Dynamic 2D Bounding Volume Heirarchy (BVH) Library. More...

#include <stdbool.h>
#include <stdint.h>

Include dependency graph for pico_bvh.h:

Go to the source code of this file.

Classes
struct	bvh_vec2_t
struct	bvh_aabb_t

Macros
#define	PICO_BVH_UDATA_TYPE   uint64_t
#define	BVH_NULL_ID   (-1)

Typedefs
typedef PICO_BVH_UDATA_TYPE	bvh_udata_t
typedef bool(*	bvh_query_cb) (int leaf_id, bvh_udata_t udata, void *ctx)
	Return false to stop traversal early.
typedef void(*	bvh_walk_cb) (bvh_aabb_t aabb, int depth, bool is_leaf, bvh_udata_t udata, void *ctx)
	Called for every node during bvh_walk(); depth=0 at root.
typedef struct bvh_t	bvh_t
	BVH instance.

Functions
bvh_aabb_t	bvh_make_aabb (float x, float y, float w, float h)
	Constructs an AABB from a position and dimensions.
bvh_t *	bvh_create (void)
	Allocates and initializes a BVH instances.
void	bvh_destroy (bvh_t *tree)
	Destroys and deallocates a BVH instance.
int	bvh_insert (bvh_t *tree, bvh_aabb_t aabb, float padding, bvh_udata_t udata)
	Inserts a new leaf.
void	bvh_remove (bvh_t *tree, int leaf_id)
	Remove a leaf.
bool	bvh_move (bvh_t *tree, int leaf_id, bvh_aabb_t new_aabb, float padding)
	Update a leaf's AABB.
void	bvh_query_aabb (const bvh_t *tree, bvh_aabb_t query, bvh_query_cb cb, void *ctx)
	Queries the tree against an AABB.
void	bvh_query_ray (const bvh_t *tree, bvh_vec2_t origin, bvh_vec2_t dir, float t_max, bvh_query_cb cb, void *ctx)
	Queries the tree against a ray.
bvh_udata_t	bvh_get_udata (const bvh_t *tree, int leaf_id)
	Returns the user data from the specified leaf node.
bvh_aabb_t	bvh_get_padded_aabb (const bvh_t *tree, int leaf_id)
	Returns the enlarged bounds from the specified leaf node.
int	bvh_get_leaf_count (const bvh_t *tree)
	Returns number of leaves in the tree.
void	bvh_walk (const bvh_t *tree, bvh_walk_cb cb, void *ctx)
	Depth-first walk over every node (internal + leaf).
float	bvh_get_cost (const bvh_t *tree)
	Total surface-area cost (lower = better balanced).

Detailed Description

A Dynamic 2D Bounding Volume Heirarchy (BVH) Library.

---

Licensing information at end of header

Overview

This header implements a dynamic 2D AABB tree for broad-phase spatial queries. Each inserted object becomes a leaf node, while internal nodes are maintained automatically to bound their descendants.

The tree is incrementally rebalanced using SAH-based local rotations, which keeps query/update costs near logarithmic in typical workloads.

Features

• Written in C99
• Broad-phase AABB and ray queries with early-out callbacks.
• Dynamic insert, remove, and move operations for 2D AABBs.
• SAH-guided sibling selection and local rotations for practical balance.
• Configurable leaf padding to reduce reinsertion churn.
• User-defined per-leaf payload type via PICO_BVH_UDATA_TYPE.

Core Concepts

---

• Leaf handle: bvh_insert returns an integer ID used by bvh_move, bvh_remove, and accessor functions.
• Padded bounds: leaves store an expanded AABB (tight bounds + padding) to reduce reinsertion churn for small object motion.
• User payload: bvh_udata_t is user-defined via PICO_BVH_UDATA_TYPE (defaults to uint64_t).

Typical Workflow

1) Create tree bvh_t* tree = bvh_create(); 2) Insert and keep returned IDs int id = bvh_insert(tree, aabb, padding, udata); 3) Update or remove by ID bvh_move(tree, id, new_aabb, padding); bvh_remove(tree, id); 4) Query with callbacks bvh_query_aabb(tree, query, cb, ctx); bvh_query_ray(tree, origin, dir, t_max, cb, ctx); 5) Destroy when done bvh_destroy(tree);

Query Semantics

---

• AABB and ray queries are broad-phase: they report overlapping leaves.
• Callbacks may return false to stop traversal early.
• AABBs that touch at edges are considered overlapping.

Complexity Notes

• Insert/remove/move: O(log n) expected.
• Query: O(log n + k) expected, where k is number of reported leaves.
• Worst-case behavior can degrade if bounds distributions are pathological.

Macro Definition Documentation

PICO_BVH_UDATA_TYPE

#define PICO_BVH_UDATA_TYPE   uint64_t

BVH_NULL_ID

#define BVH_NULL_ID   (-1)

Typedef Documentation

bvh_udata_t

typedef PICO_BVH_UDATA_TYPE bvh_udata_t

bvh_query_cb

typedef bool(* bvh_query_cb) (int leaf_id, bvh_udata_t udata, void *ctx)

Return false to stop traversal early.

Parameters

leaf_id	Leaf handle for the candidate hit.
udata	User payload stored in that leaf.
ctx	User-provided context pointer passed through query calls.

Returns

true to continue traversal, false to stop early.

bvh_walk_cb

typedef void(* bvh_walk_cb) (bvh_aabb_t aabb, int depth, bool is_leaf, bvh_udata_t udata, void *ctx)

Called for every node during bvh_walk(); depth=0 at root.

Parameters

aabb	Node bounds.
depth	Tree depth, where 0 is the root.
is_leaf	true for leaf nodes, false for internal nodes.
udata	User payload for leaf nodes; unspecified for internal nodes.
ctx	User-provided context pointer passed through bvh_walk.

bvh_t

typedef struct bvh_t bvh_t

BVH instance.

Function Documentation

bvh_make_aabb()

bvh_aabb_t bvh_make_aabb	(	float	x,
		float	y,
		float	w,
		float	h
	)

Constructs an AABB from a position and dimensions.

Parameters

x	Minimum x coordinate.
y	Minimum y coordinate.
w	Width added to x to form max.x.
h	Height added to y to form max.y.

Returns

Constructed AABB.

bvh_create()

bvh_t * bvh_create

(

void

)

Allocates and initializes a BVH instances.

Returns

New BVH instance, or NULL on allocation failure.

bvh_destroy()

void bvh_destroy

(

bvh_t *

tree

)

Destroys and deallocates a BVH instance.

Parameters

tree	BVH instance to destroy.

bvh_insert()

int bvh_insert	(	bvh_t *	tree,
		bvh_aabb_t	aabb,
		float	padding,
		bvh_udata_t	udata
	)

Inserts a new leaf.

The stored AABB is padded by padding (pass 0 for exact fit).

Parameters

tree	BVH instance to modify.
aabb	Tight bounds for the new leaf.
padding	Margin added on all sides before storing the leaf bounds.
udata	User payload associated with the leaf.

Returns

A stable ID for future move/remove calls.

bvh_remove()

void bvh_remove	(	bvh_t *	tree,
		int	leaf_id
	)

Remove a leaf.

Parameters

tree	BVH instance to modify.
leaf_id	ID previously returned by bvh_insert.

bvh_move()

bool bvh_move	(	bvh_t *	tree,
		int	leaf_id,
		bvh_aabb_t	new_aabb,
		float	padding
	)

Update a leaf's AABB.

Parameters

tree	BVH instance to modify.
leaf_id	ID previously returned by bvh_insert.
new_aabb	New tight bounds for the leaf.
padding	Margin added on all sides before storing the leaf bounds.

Returns

true if the tree was restructured (the old padded AABB no longer contained the new tight one).

bvh_query_aabb()

void bvh_query_aabb	(	const bvh_t *	tree,
		bvh_aabb_t	query,
		bvh_query_cb	cb,
		void *	ctx
	)

Queries the tree against an AABB.

Parameters

tree	BVH instance to query.
query	Query AABB in world space.
cb	Callback invoked for each overlapping leaf.
ctx	User-provided context pointer passed to cb.

bvh_query_ray()

void bvh_query_ray	(	const bvh_t *	tree,
		bvh_vec2_t	origin,
		bvh_vec2_t	dir,
		float	t_max,
		bvh_query_cb	cb,
		void *	ctx
	)

Queries the tree against a ray.

Ray: origin + t*dir, t in [0, t_max]. Use FLT_MAX for infinite ray.

Parameters

tree	BVH instance to query.
origin	Ray origin.
dir	Ray direction; it does not need to be normalized.
t_max	Maximum parametric distance along the ray.
cb	Callback invoked for each overlapping leaf.
ctx	User-provided context pointer passed to cb.

bvh_get_udata()

bvh_udata_t bvh_get_udata	(	const bvh_t *	tree,
		int	leaf_id
	)

Returns the user data from the specified leaf node.

Parameters

tree	BVH instance to read from.
leaf_id	ID previously returned by bvh_insert.

Returns

User payload stored in that leaf.

bvh_get_padded_aabb()

bvh_aabb_t bvh_get_padded_aabb	(	const bvh_t *	tree,
		int	leaf_id
	)

Returns the enlarged bounds from the specified leaf node.

Parameters

tree	BVH instance to read from.
leaf_id	ID previously returned by bvh_insert.

Returns

Stored padded AABB for that leaf.

bvh_get_leaf_count()

int bvh_get_leaf_count

(

const bvh_t *

tree

)

Returns number of leaves in the tree.

Parameters

tree	BVH instance to read from.

Returns

Number of currently allocated leaves.

bvh_walk()

void bvh_walk	(	const bvh_t *	tree,
		bvh_walk_cb	cb,
		void *	ctx
	)

Depth-first walk over every node (internal + leaf).

Parameters

tree	BVH instance to walk.
cb	Callback invoked once per node.
ctx	User-provided context pointer passed to cb.

bvh_get_cost()

float bvh_get_cost

(

const bvh_t *

tree

)

Total surface-area cost (lower = better balanced).

Parameters

tree	BVH instance to evaluate.

Returns

Sum of node perimeters in the tree.