cpSpatialIndex

Data Structures
struct	cpSpatialIndex
struct	cpSpatialIndexClass
Typedefs
typedef cpBB(*	cpSpatialIndexBBFunc )(void *obj)
typedef void(*	cpSpatialIndexIteratorFunc )(void *obj, void *data)
	Spatial index/object iterator callback function type.
typedef void(*	cpSpatialIndexQueryFunc )(void *obj1, void *obj2, void *data)
	Spatial query callback function type.
typedef cpFloat(*	cpSpatialIndexSegmentQueryFunc )(void *obj1, void *obj2, void *data)
	Spatial segment query callback function type.
typedef struct cpSpaceHash	cpSpaceHash
typedef struct cpBBTree	cpBBTree
typedef cpVect(*	cpBBTreeVelocityFunc )(void *obj)
typedef struct cpSweep1D	cpSweep1D
typedef void(*	cpSpatialIndexDestroyImpl )(cpSpatialIndex *index)
typedef int(*	cpSpatialIndexCountImpl )(cpSpatialIndex *index)
typedef void(*	cpSpatialIndexEachImpl )(cpSpatialIndex *index, cpSpatialIndexIteratorFunc func, void *data)
typedef cpBool(*	cpSpatialIndexContainsImpl )(cpSpatialIndex *index, void *obj, cpHashValue hashid)
typedef void(*	cpSpatialIndexInsertImpl )(cpSpatialIndex *index, void *obj, cpHashValue hashid)
typedef void(*	cpSpatialIndexRemoveImpl )(cpSpatialIndex *index, void *obj, cpHashValue hashid)
typedef void(*	cpSpatialIndexReindexImpl )(cpSpatialIndex *index)
typedef void(*	cpSpatialIndexReindexObjectImpl )(cpSpatialIndex *index, void *obj, cpHashValue hashid)
typedef void(*	cpSpatialIndexReindexQueryImpl )(cpSpatialIndex *index, cpSpatialIndexQueryFunc func, void *data)
typedef void(*	cpSpatialIndexPointQueryImpl )(cpSpatialIndex *index, cpVect point, cpSpatialIndexQueryFunc func, void *data)
typedef void(*	cpSpatialIndexSegmentQueryImpl )(cpSpatialIndex *index, void *obj, cpVect a, cpVect b, cpFloat t_exit, cpSpatialIndexSegmentQueryFunc func, void *data)
typedef void(*	cpSpatialIndexQueryImpl )(cpSpatialIndex *index, void *obj, cpBB bb, cpSpatialIndexQueryFunc func, void *data)
Functions
cpSpaceHash *	cpSpaceHashAlloc (void)
	Allocate a spatial hash.
cpSpatialIndex *	cpSpaceHashInit (cpSpaceHash *hash, cpFloat celldim, int numcells, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex)
	Initialize a spatial hash.
cpSpatialIndex *	cpSpaceHashNew (cpFloat celldim, int cells, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex)
	Allocate and initialize a spatial hash.
void	cpSpaceHashResize (cpSpaceHash *hash, cpFloat celldim, int numcells)
cpBBTree *	cpBBTreeAlloc (void)
	Allocate a bounding box tree.
cpSpatialIndex *	cpBBTreeInit (cpBBTree *tree, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex)
	Initialize a bounding box tree.
cpSpatialIndex *	cpBBTreeNew (cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex)
	Allocate and initialize a bounding box tree.
void	cpBBTreeOptimize (cpSpatialIndex *index)
	Perform a static top down optimization of the tree.
void	cpBBTreeSetVelocityFunc (cpSpatialIndex *index, cpBBTreeVelocityFunc func)
	Set the velocity function for the bounding box tree to enable temporal coherence.
cpSweep1D *	cpSweep1DAlloc (void)
	Allocate a 1D sort and sweep broadphase.
cpSpatialIndex *	cpSweep1DInit (cpSweep1D *sweep, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex)
	Initialize a 1D sort and sweep broadphase.
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)
static void	cpSpatialIndexInsert (cpSpatialIndex *index, void *obj, cpHashValue hashid)
static void	cpSpatialIndexRemove (cpSpatialIndex *index, void *obj, cpHashValue hashid)
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	cpSpatialIndexPointQuery (cpSpatialIndex *index, cpVect point, cpSpatialIndexQueryFunc func, void *data)
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	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	cpSpatialIndexReindexQuery (cpSpatialIndex *index, cpSpatialIndexQueryFunc func, void *data)

---

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 struct cpBBTree cpBBTree

typedef cpVect(* cpBBTreeVelocityFunc)(void *obj)

Bounding box tree velocity callback function. This function should return an estimate for the object's velocity.

typedef struct cpSpaceHash cpSpaceHash

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.

typedef cpBool(* cpSpatialIndexContainsImpl)(cpSpatialIndex *index, void *obj, cpHashValue hashid)

typedef int(* cpSpatialIndexCountImpl)(cpSpatialIndex *index)

typedef void(* cpSpatialIndexDestroyImpl)(cpSpatialIndex *index)

typedef void(* cpSpatialIndexEachImpl)(cpSpatialIndex *index, cpSpatialIndexIteratorFunc func, void *data)

typedef void(* cpSpatialIndexInsertImpl)(cpSpatialIndex *index, void *obj, cpHashValue hashid)

typedef void(* cpSpatialIndexIteratorFunc)(void *obj, void *data)

Spatial index/object iterator callback function type.

typedef void(* cpSpatialIndexPointQueryImpl)(cpSpatialIndex *index, cpVect point, cpSpatialIndexQueryFunc func, void *data)

typedef void(* cpSpatialIndexQueryFunc)(void *obj1, void *obj2, void *data)

Spatial query callback function type.

typedef void(* cpSpatialIndexQueryImpl)(cpSpatialIndex *index, void *obj, cpBB bb, cpSpatialIndexQueryFunc func, void *data)

typedef void(* cpSpatialIndexReindexImpl)(cpSpatialIndex *index)

typedef void(* cpSpatialIndexReindexObjectImpl)(cpSpatialIndex *index, void *obj, cpHashValue hashid)

typedef void(* cpSpatialIndexReindexQueryImpl)(cpSpatialIndex *index, cpSpatialIndexQueryFunc func, void *data)

typedef void(* cpSpatialIndexRemoveImpl)(cpSpatialIndex *index, void *obj, cpHashValue hashid)

typedef cpFloat(* cpSpatialIndexSegmentQueryFunc)(void *obj1, void *obj2, void *data)

Spatial segment query callback function type.

typedef void(* cpSpatialIndexSegmentQueryImpl)(cpSpatialIndex *index, void *obj, cpVect a, cpVect b, cpFloat t_exit, cpSpatialIndexSegmentQueryFunc func, void *data)

typedef struct cpSweep1D cpSweep1D

---

Function Documentation

cpBBTree* cpBBTreeAlloc

(

void

)

Allocate a bounding box tree.

cpSpatialIndex* cpBBTreeInit	(	cpBBTree *	tree,
		cpSpatialIndexBBFunc	bbfunc,
		cpSpatialIndex *	staticIndex
	)

Initialize a bounding box tree.

cpSpatialIndex* cpBBTreeNew	(	cpSpatialIndexBBFunc	bbfunc,
		cpSpatialIndex *	staticIndex
	)

Allocate and initialize a bounding box tree.

void cpBBTreeOptimize

(

cpSpatialIndex *

index

)

Perform a static top down optimization of the tree.

void cpBBTreeSetVelocityFunc	(	cpSpatialIndex *	index,
		cpBBTreeVelocityFunc	func
	)

Set the velocity function for the bounding box tree to enable temporal coherence.

cpSpaceHash* cpSpaceHashAlloc

(

void

)

Allocate a spatial hash.

cpSpatialIndex* cpSpaceHashInit	(	cpSpaceHash *	hash,
		cpFloat	celldim,
		int	numcells,
		cpSpatialIndexBBFunc	bbfunc,
		cpSpatialIndex *	staticIndex
	)

Initialize a spatial hash.

cpSpatialIndex* cpSpaceHashNew	(	cpFloat	celldim,
		int	cells,
		cpSpatialIndexBBFunc	bbfunc,
		cpSpatialIndex *	staticIndex
	)

Allocate and initialize a spatial hash.

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.

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 cpBool cpSpatialIndexContains	(	cpSpatialIndex *	index,
		void *	obj,
		cpHashValue	hashid
	)		[inline, static]

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 int cpSpatialIndexCount

(

cpSpatialIndex *

index

)

[inline, static]

Get the number of objects in the spatial index.

static void cpSpatialIndexDestroy

(

cpSpatialIndex *

index

)

[inline, static]

Destroy a spatial index.

static void cpSpatialIndexEach	(	cpSpatialIndex *	index,
		cpSpatialIndexIteratorFunc	func,
		void *	data
	)		[inline, static]

Iterate the objects in the spatial index. func will be called once for each object.

void cpSpatialIndexFree

(

cpSpatialIndex *

index

)

Destroy and free a spatial index.

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

Add an object to a spatial index. Most spatial indexes use hashed storage, so you must provide a hash value too.

static void cpSpatialIndexPointQuery	(	cpSpatialIndex *	index,
		cpVect	point,
		cpSpatialIndexQueryFunc	func,
		void *	data
	)		[inline, static]

Perform a point query against the spatial index, calling func for each potential match. A pointer to the point will be passed as obj1 of func.

static void cpSpatialIndexQuery	(	cpSpatialIndex *	index,
		void *	obj,
		cpBB	bb,
		cpSpatialIndexQueryFunc	func,
		void *	data
	)		[inline, static]

Perform a rectangle query against the spatial index, calling func for each potential match.

static void cpSpatialIndexReindex

(

cpSpatialIndex *

index

)

[inline, static]

Perform a full reindex of a spatial index.

static void cpSpatialIndexReindexObject	(	cpSpatialIndex *	index,
		void *	obj,
		cpHashValue	hashid
	)		[inline, static]

Reindex a single object in the spatial index.

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

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
	)		[inline, static]

Remove an object from a spatial index. Most spatial indexes use hashed storage, so you must provide a hash value too.

static void cpSpatialIndexSegmentQuery	(	cpSpatialIndex *	index,
		void *	obj,
		cpVect	a,
		cpVect	b,
		cpFloat	t_exit,
		cpSpatialIndexSegmentQueryFunc	func,
		void *	data
	)		[inline, static]

Perform a segment query against the spatial index, calling func for each potential match.

cpSweep1D* cpSweep1DAlloc

(

void

)

Allocate a 1D sort and sweep broadphase.

cpSpatialIndex* cpSweep1DInit	(	cpSweep1D *	sweep,
		cpSpatialIndexBBFunc	bbfunc,
		cpSpatialIndex *	staticIndex
	)

Initialize a 1D sort and sweep broadphase.

cpSpatialIndex* cpSweep1DNew	(	cpSpatialIndexBBFunc	bbfunc,
		cpSpatialIndex *	staticIndex
	)

Allocate and initialize a 1D sort and sweep broadphase.