Spatial indexes are data structures that are used to accelerate collision detection and spatial queries. More...

Classes
struct	cpSpatialIndexClass

Typedefs
typedef cpBB(*	cpSpatialIndexBBFunc )(void *obj)
	Spatial index bounding box callback function type. More...

typedef void(*	cpSpatialIndexIteratorFunc )(void obj, void data)
	Spatial index/object iterator callback function type.

typedef cpCollisionID(*	cpSpatialIndexQueryFunc )(void obj1, void obj2, cpCollisionID id, void *data)
	Spatial query callback function type.

typedef cpFloat(*	cpSpatialIndexSegmentQueryFunc )(void obj1, void obj2, void *data)
	Spatial segment query callback function type.

typedef cpVect(*	cpBBTreeVelocityFunc )(void *obj)
	Bounding box tree velocity callback function. More...

Functions
CP_EXPORT cpSpaceHash *	cpSpaceHashAlloc (void)
	Allocate a spatial hash.

CP_EXPORT cpSpatialIndex *	cpSpaceHashInit (cpSpaceHash hash, cpFloat celldim, int numcells, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex staticIndex)
	Initialize a spatial hash.

CP_EXPORT cpSpatialIndex *	cpSpaceHashNew (cpFloat celldim, int cells, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex)
	Allocate and initialize a spatial hash.

CP_EXPORT void	cpSpaceHashResize (cpSpaceHash *hash, cpFloat celldim, int numcells)
	Change the cell dimensions and table size of the spatial hash to tune it. More...

CP_EXPORT cpBBTree *	cpBBTreeAlloc (void)
	Allocate a bounding box tree.

CP_EXPORT cpSpatialIndex *	cpBBTreeInit (cpBBTree tree, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex staticIndex)
	Initialize a bounding box tree.

CP_EXPORT cpSpatialIndex *	cpBBTreeNew (cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex)
	Allocate and initialize a bounding box tree.

CP_EXPORT void	cpBBTreeOptimize (cpSpatialIndex *index)
	Perform a static top down optimization of the tree.

CP_EXPORT void	cpBBTreeSetVelocityFunc (cpSpatialIndex *index, cpBBTreeVelocityFunc func)
	Set the velocity function for the bounding box tree to enable temporal coherence.

CP_EXPORT cpSweep1D *	cpSweep1DAlloc (void)
	Allocate a 1D sort and sweep broadphase.

CP_EXPORT cpSpatialIndex *	cpSweep1DInit (cpSweep1D sweep, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex staticIndex)
	Initialize a 1D sort and sweep broadphase.

CP_EXPORT cpSpatialIndex *	cpSweep1DNew (cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex)
	Allocate and initialize a 1D sort and sweep broadphase.

void	cpSpatialIndexFree (cpSpatialIndex *index)
	Destroy and free a spatial index.

void	cpSpatialIndexCollideStatic (cpSpatialIndex dynamicIndex, cpSpatialIndex staticIndex, cpSpatialIndexQueryFunc func, void *data)
	Collide the objects in `dynamicIndex` against the objects in `staticIndex` using the query callback function.

static void	cpSpatialIndexDestroy (cpSpatialIndex *index)
	Destroy a spatial index.

static int	cpSpatialIndexCount (cpSpatialIndex *index)
	Get the number of objects in the spatial index.

static void	cpSpatialIndexEach (cpSpatialIndex index, cpSpatialIndexIteratorFunc func, void data)
	Iterate the objects in the spatial index. `func` will be called once for each object.

static cpBool	cpSpatialIndexContains (cpSpatialIndex index, void obj, cpHashValue hashid)
	Returns true if the spatial index contains the given object. More...

static void	cpSpatialIndexInsert (cpSpatialIndex index, void obj, cpHashValue hashid)
	Add an object to a spatial index. More...

static void	cpSpatialIndexRemove (cpSpatialIndex index, void obj, cpHashValue hashid)
	Remove an object from a spatial index. More...

static void	cpSpatialIndexReindex (cpSpatialIndex *index)
	Perform a full reindex of a spatial index.

static void	cpSpatialIndexReindexObject (cpSpatialIndex index, void obj, cpHashValue hashid)
	Reindex a single object in the spatial index.

static void	cpSpatialIndexQuery (cpSpatialIndex index, void obj, cpBB bb, cpSpatialIndexQueryFunc func, void *data)
	Perform a rectangle query against the spatial index, calling `func` for each potential match.

static void	cpSpatialIndexSegmentQuery (cpSpatialIndex index, void obj, cpVect a, cpVect b, cpFloat t_exit, cpSpatialIndexSegmentQueryFunc func, void *data)
	Perform a segment query against the spatial index, calling `func` for each potential match.

static void	cpSpatialIndexReindexQuery (cpSpatialIndex index, cpSpatialIndexQueryFunc func, void data)
	Simultaneously reindex and find all colliding objects. More...

Detailed Description

Spatial indexes are data structures that are used to accelerate collision detection and spatial queries.

Chipmunk provides a number of spatial index algorithms to pick from and they are programmed in a generic way so that you can use them for holding more than just cpShape structs.

It works by using void pointers to the objects you add and using a callback to ask your code for bounding boxes when it needs them. Several types of queries can be performed an index as well as reindexing and full collision information. All communication to the spatial indexes is performed through callback functions.

Spatial indexes should be treated as opaque structs. This meanns you shouldn't be reading any of the struct fields.

Typedef Documentation

typedef cpVect(* cpBBTreeVelocityFunc)(void *obj)

Bounding box tree velocity callback function.

This function should return an estimate for the object's velocity.

typedef cpBB(* cpSpatialIndexBBFunc)(void *obj)

Spatial index bounding box callback function type.

The spatial index calls this function and passes you a pointer to an object you added when it needs to get the bounding box associated with that object.

Function Documentation

CP_EXPORT void cpSpaceHashResize	(	cpSpaceHash *	hash,
		cpFloat	celldim,
		int	numcells
	)

Change the cell dimensions and table size of the spatial hash to tune it.

The cell dimensions should roughly match the average size of your objects and the table size should be ~10 larger than the number of objects inserted. Some trial and error is required to find the optimum numbers for efficiency.

static cpBool cpSpatialIndexContains	(	cpSpatialIndex *	index,
		void *	obj,
		cpHashValue	hashid
	)

inlinestatic

Returns true if the spatial index contains the given object.

Most spatial indexes use hashed storage, so you must provide a hash value too.

static void cpSpatialIndexInsert	(	cpSpatialIndex *	index,
		void *	obj,
		cpHashValue	hashid
	)

inlinestatic

Add an object to a spatial index.

Most spatial indexes use hashed storage, so you must provide a hash value too.

static void cpSpatialIndexReindexQuery	(	cpSpatialIndex *	index,
		cpSpatialIndexQueryFunc	func,
		void *	data
	)

inlinestatic

Simultaneously reindex and find all colliding objects.

func will be called once for each potentially overlapping pair of objects found. If the spatial index was initialized with a static index, it will collide it's objects against that as well.

static void cpSpatialIndexRemove	(	cpSpatialIndex *	index,
		void *	obj,
		cpHashValue	hashid
	)

inlinestatic

Remove an object from a spatial index.

Most spatial indexes use hashed storage, so you must provide a hash value too.

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation