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 void cpSpatialIndexFree(cpSpatialIndex *index);
153 /// Collide the objects in @c dynamicIndex against the objects in @c staticIndex using the query callback function.
154 void cpSpatialIndexCollideStatic(cpSpatialIndex *dynamicIndex, cpSpatialIndex *staticIndex, cpSpatialIndexQueryFunc func, void *data);
155
156 /// Destroy a spatial index.
cpSpatialIndexDestroy(cpSpatialIndex * 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.
cpSpatialIndexCount(cpSpatialIndex * 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.
cpSpatialIndexEach(cpSpatialIndex * index,cpSpatialIndexIteratorFunc func,void * data)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.
cpSpatialIndexContains(cpSpatialIndex * index,void * obj,cpHashValue hashid)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.
cpSpatialIndexInsert(cpSpatialIndex * index,void * obj,cpHashValue hashid)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.
cpSpatialIndexRemove(cpSpatialIndex * index,void * obj,cpHashValue hashid)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.
cpSpatialIndexReindex(cpSpatialIndex * 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.
cpSpatialIndexReindexObject(cpSpatialIndex * index,void * obj,cpHashValue hashid)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.
cpSpatialIndexQuery(cpSpatialIndex * index,void * obj,cpBB bb,cpSpatialIndexQueryFunc func,void * data)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.
cpSpatialIndexSegmentQuery(cpSpatialIndex * index,void * obj,cpVect a,cpVect b,cpFloat t_exit,cpSpatialIndexSegmentQueryFunc func,void * data)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.
cpSpatialIndexReindexQuery(cpSpatialIndex * index,cpSpatialIndexQueryFunc func,void * data)222 static inline void cpSpatialIndexReindexQuery(cpSpatialIndex *index, cpSpatialIndexQueryFunc func, void *data)
223 {
224 index->klass->reindexQuery(index, func, data);
225 }
226
227 ///@}
228