Chipmunk2D Pro API Reference  7.0.2
 All Classes Functions Variables Typedefs Enumerations Enumerator Properties Groups Pages
Classes | Typedefs | Functions
cpSpatialIndex

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.
 
CP_EXPORT void cpSpatialIndexFree (cpSpatialIndex *index)
 Destroy and free a spatial index.
 
CP_EXPORT 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.