dali-physics/third-party/chipmunk2d/include/chipmunk/cpSpatialIndex.h

   1 /* Copyright (c) 2013 Scott Lembcke and Howling Moon Software
   2  *
   3  * Permission is hereby granted, free of charge, to any person obtaining a copy
   4  * of this software and associated documentation files (the "Software"), to deal
   5  * in the Software without restriction, including without limitation the rights
   6  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   7  * copies of the Software, and to permit persons to whom the Software is
   8  * furnished to do so, subject to the following conditions:
   9  *
  10  * The above copyright notice and this permission notice shall be included in
  11  * all copies or substantial portions of the Software.
  12  *
  13  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  18  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  19  * SOFTWARE.
  20  */
  21
  22 /**
  23         @defgroup cpSpatialIndex cpSpatialIndex
  24
  25         Spatial indexes are data structures that are used to accelerate collision detection
  26         and spatial queries. Chipmunk provides a number of spatial index algorithms to pick from
  27         and they are programmed in a generic way so that you can use them for holding more than
  28         just cpShape structs.
  29
  30         It works by using @c void pointers to the objects you add and using a callback to ask your code
  31         for bounding boxes when it needs them. Several types of queries can be performed an index as well
  32         as reindexing and full collision information. All communication to the spatial indexes is performed
  33         through callback functions.
  34
  35         Spatial indexes should be treated as opaque structs.
  36         This meanns you shouldn't be reading any of the struct fields.
  37         @{
  38 */
  39
  40 //MARK: Spatial Index
  41
  42 /// Spatial index bounding box callback function type.
  43 /// The spatial index calls this function and passes you a pointer to an object you added
  44 /// when it needs to get the bounding box associated with that object.
  45 typedef cpBB (*cpSpatialIndexBBFunc)(void *obj);
  46 /// Spatial index/object iterator callback function type.
  47 typedef void (*cpSpatialIndexIteratorFunc)(void *obj, void *data);
  48 /// Spatial query callback function type.
  49 typedef cpCollisionID (*cpSpatialIndexQueryFunc)(void *obj1, void *obj2, cpCollisionID id, void *data);
  50 /// Spatial segment query callback function type.
  51 typedef cpFloat (*cpSpatialIndexSegmentQueryFunc)(void *obj1, void *obj2, void *data);
  52
  53
  54 typedef struct cpSpatialIndexClass cpSpatialIndexClass;
  55 typedef struct cpSpatialIndex cpSpatialIndex;
  56
  57 /// @private
  58 struct cpSpatialIndex {
  59         cpSpatialIndexClass *klass;
  60
  61         cpSpatialIndexBBFunc bbfunc;
  62
  63         cpSpatialIndex *staticIndex, *dynamicIndex;
  64 };
  65
  66
  67 //MARK: Spatial Hash
  68
  69 typedef struct cpSpaceHash cpSpaceHash;
  70
  71 /// Allocate a spatial hash.
  72 CP_EXPORT cpSpaceHash* cpSpaceHashAlloc(void);
  73 /// Initialize a spatial hash.
  74 CP_EXPORT cpSpatialIndex* cpSpaceHashInit(cpSpaceHash *hash, cpFloat celldim, int numcells, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
  75 /// Allocate and initialize a spatial hash.
  76 CP_EXPORT cpSpatialIndex* cpSpaceHashNew(cpFloat celldim, int cells, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
  77
  78 /// Change the cell dimensions and table size of the spatial hash to tune it.
  79 /// The cell dimensions should roughly match the average size of your objects
  80 /// and the table size should be ~10 larger than the number of objects inserted.
  81 /// Some trial and error is required to find the optimum numbers for efficiency.
  82 CP_EXPORT void cpSpaceHashResize(cpSpaceHash *hash, cpFloat celldim, int numcells);
  83
  84 //MARK: AABB Tree
  85
  86 typedef struct cpBBTree cpBBTree;
  87
  88 /// Allocate a bounding box tree.
  89 CP_EXPORT cpBBTree* cpBBTreeAlloc(void);
  90 /// Initialize a bounding box tree.
  91 CP_EXPORT cpSpatialIndex* cpBBTreeInit(cpBBTree *tree, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
  92 /// Allocate and initialize a bounding box tree.
  93 CP_EXPORT cpSpatialIndex* cpBBTreeNew(cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
  94
  95 /// Perform a static top down optimization of the tree.
  96 CP_EXPORT void cpBBTreeOptimize(cpSpatialIndex *index);
  97
  98 /// Bounding box tree velocity callback function.
  99 /// This function should return an estimate for the object's velocity.
 100 typedef cpVect (*cpBBTreeVelocityFunc)(void *obj);
 101 /// Set the velocity function for the bounding box tree to enable temporal coherence.
 102 CP_EXPORT void cpBBTreeSetVelocityFunc(cpSpatialIndex *index, cpBBTreeVelocityFunc func);
 103
 104 //MARK: Single Axis Sweep
 105
 106 typedef struct cpSweep1D cpSweep1D;
 107
 108 /// Allocate a 1D sort and sweep broadphase.
 109 CP_EXPORT cpSweep1D* cpSweep1DAlloc(void);
 110 /// Initialize a 1D sort and sweep broadphase.
 111 CP_EXPORT cpSpatialIndex* cpSweep1DInit(cpSweep1D *sweep, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
 112 /// Allocate and initialize a 1D sort and sweep broadphase.
 113 CP_EXPORT cpSpatialIndex* cpSweep1DNew(cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
 114
 115 //MARK: Spatial Index Implementation
 116
 117 typedef void (*cpSpatialIndexDestroyImpl)(cpSpatialIndex *index);
 118
 119 typedef int (*cpSpatialIndexCountImpl)(cpSpatialIndex *index);
 120 typedef void (*cpSpatialIndexEachImpl)(cpSpatialIndex *index, cpSpatialIndexIteratorFunc func, void *data);
 121
 122 typedef cpBool (*cpSpatialIndexContainsImpl)(cpSpatialIndex *index, void *obj, cpHashValue hashid);
 123 typedef void (*cpSpatialIndexInsertImpl)(cpSpatialIndex *index, void *obj, cpHashValue hashid);
 124 typedef void (*cpSpatialIndexRemoveImpl)(cpSpatialIndex *index, void *obj, cpHashValue hashid);
 125
 126 typedef void (*cpSpatialIndexReindexImpl)(cpSpatialIndex *index);
 127 typedef void (*cpSpatialIndexReindexObjectImpl)(cpSpatialIndex *index, void *obj, cpHashValue hashid);
 128 typedef void (*cpSpatialIndexReindexQueryImpl)(cpSpatialIndex *index, cpSpatialIndexQueryFunc func, void *data);
 129
 130 typedef void (*cpSpatialIndexQueryImpl)(cpSpatialIndex *index, void *obj, cpBB bb, cpSpatialIndexQueryFunc func, void *data);
 131 typedef void (*cpSpatialIndexSegmentQueryImpl)(cpSpatialIndex *index, void *obj, cpVect a, cpVect b, cpFloat t_exit, cpSpatialIndexSegmentQueryFunc func, void *data);
 132
 133 struct cpSpatialIndexClass {
 134         cpSpatialIndexDestroyImpl destroy;
 135
 136         cpSpatialIndexCountImpl count;
 137         cpSpatialIndexEachImpl each;
 138
 139         cpSpatialIndexContainsImpl contains;
 140         cpSpatialIndexInsertImpl insert;
 141         cpSpatialIndexRemoveImpl remove;
 142
 143         cpSpatialIndexReindexImpl reindex;
 144         cpSpatialIndexReindexObjectImpl reindexObject;
 145         cpSpatialIndexReindexQueryImpl reindexQuery;
 146
 147         cpSpatialIndexQueryImpl query;
 148         cpSpatialIndexSegmentQueryImpl segmentQuery;
 149 };
 150
 151 /// Destroy and free a spatial index.
 152 CP_EXPORT void cpSpatialIndexFree(cpSpatialIndex *index);
 153 /// Collide the objects in @c dynamicIndex against the objects in @c staticIndex using the query callback function.
 154 CP_EXPORT void cpSpatialIndexCollideStatic(cpSpatialIndex *dynamicIndex, cpSpatialIndex *staticIndex, cpSpatialIndexQueryFunc func, void *data);
 155
 156 /// Destroy a spatial index.
 157 static inline void cpSpatialIndexDestroy(cpSpatialIndex *index)
 158 {
 159         if(index->klass) index->klass->destroy(index);
 160 }
 161
 162 /// Get the number of objects in the spatial index.
 163 static inline int cpSpatialIndexCount(cpSpatialIndex *index)
 164 {
 165         return index->klass->count(index);
 166 }
 167
 168 /// Iterate the objects in the spatial index. @c func will be called once for each object.
 169 static inline void cpSpatialIndexEach(cpSpatialIndex *index, cpSpatialIndexIteratorFunc func, void *data)
 170 {
 171         index->klass->each(index, func, data);
 172 }
 173
 174 /// Returns true if the spatial index contains the given object.
 175 /// Most spatial indexes use hashed storage, so you must provide a hash value too.
 176 static inline cpBool cpSpatialIndexContains(cpSpatialIndex *index, void *obj, cpHashValue hashid)
 177 {
 178         return index->klass->contains(index, obj, hashid);
 179 }
 180
 181 /// Add an object to a spatial index.
 182 /// Most spatial indexes use hashed storage, so you must provide a hash value too.
 183 static inline void cpSpatialIndexInsert(cpSpatialIndex *index, void *obj, cpHashValue hashid)
 184 {
 185         index->klass->insert(index, obj, hashid);
 186 }
 187
 188 /// Remove an object from a spatial index.
 189 /// Most spatial indexes use hashed storage, so you must provide a hash value too.
 190 static inline void cpSpatialIndexRemove(cpSpatialIndex *index, void *obj, cpHashValue hashid)
 191 {
 192         index->klass->remove(index, obj, hashid);
 193 }
 194
 195 /// Perform a full reindex of a spatial index.
 196 static inline void cpSpatialIndexReindex(cpSpatialIndex *index)
 197 {
 198         index->klass->reindex(index);
 199 }
 200
 201 /// Reindex a single object in the spatial index.
 202 static inline void cpSpatialIndexReindexObject(cpSpatialIndex *index, void *obj, cpHashValue hashid)
 203 {
 204         index->klass->reindexObject(index, obj, hashid);
 205 }
 206
 207 /// Perform a rectangle query against the spatial index, calling @c func for each potential match.
 208 static inline void cpSpatialIndexQuery(cpSpatialIndex *index, void *obj, cpBB bb, cpSpatialIndexQueryFunc func, void *data)
 209 {
 210         index->klass->query(index, obj, bb, func, data);
 211 }
 212
 213 /// Perform a segment query against the spatial index, calling @c func for each potential match.
 214 static inline void cpSpatialIndexSegmentQuery(cpSpatialIndex *index, void *obj, cpVect a, cpVect b, cpFloat t_exit, cpSpatialIndexSegmentQueryFunc func, void *data)
 215 {
 216         index->klass->segmentQuery(index, obj, a, b, t_exit, func, data);
 217 }
 218
 219 /// Simultaneously reindex and find all colliding objects.
 220 /// @c func will be called once for each potentially overlapping pair of objects found.
 221 /// If the spatial index was initialized with a static index, it will collide it's objects against that as well.
 222 static inline void cpSpatialIndexReindexQuery(cpSpatialIndex *index, cpSpatialIndexQueryFunc func, void *data)
 223 {
 224         index->klass->reindexQuery(index, func, data);
 225 }
 226
 227 ///@}