pico_bvh.h File Reference

Dynamic 2D Bounding Volume Heirarchy (BVH) 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 max_t, 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

Dynamic 2D Bounding Volume Heirarchy (BVH)

---

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, max_t, 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.

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.

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.

bvh_create()

bvh_t * bvh_create

(

void

)

Allocates and initializes a BVH instances.

bvh_destroy()

void bvh_destroy

(

bvh_t *

tree

)

Destroys and deallocates a BVH instance.

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).

Returns

A stable ID for future move/remove calls.

bvh_remove()

void bvh_remove	(	bvh_t *	tree,
		int	leaf_id
	)

Remove a leaf.

bvh_move()

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

Update a leaf's AABB.

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.

bvh_query_ray()

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

Queries the tree against a ray.

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

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.

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.

bvh_get_leaf_count()

int bvh_get_leaf_count

(

const bvh_t *

tree

)

Returns number of leaves in the tree.

bvh_walk()

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

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

bvh_get_cost()

float bvh_get_cost

(

const bvh_t *

tree

)

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