cpSpatialIndex.h

/* Copyright (c) 2025 Victor Blomqvist
 * Copyright (c) 2007-2024 Scott Lembcke and Howling Moon Software
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
*/
 
//MARK: Spatial Index
 
typedef cpBB (*cpSpatialIndexBBFunc)(void *obj);
typedef void (*cpSpatialIndexIteratorFunc)(void *obj, void *data);
typedef cpCollisionID (*cpSpatialIndexQueryFunc)(void *obj1, void *obj2, cpCollisionID id, void *data);
typedef cpFloat (*cpSpatialIndexSegmentQueryFunc)(void *obj1, void *obj2, void *data);
 
 
typedef struct cpSpatialIndexClass cpSpatialIndexClass;
typedef struct cpSpatialIndex cpSpatialIndex;
 
struct cpSpatialIndex {
  cpSpatialIndexClass *klass;
  
  cpSpatialIndexBBFunc bbfunc;
  
  cpSpatialIndex *staticIndex, *dynamicIndex;
};
 
 
//MARK: Spatial Hash
 
typedef struct cpSpaceHash cpSpaceHash;
 
CP_EXPORT cpSpaceHash* cpSpaceHashAlloc(void);
CP_EXPORT cpSpatialIndex* cpSpaceHashInit(cpSpaceHash *hash, cpFloat celldim, int numcells, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
CP_EXPORT cpSpatialIndex* cpSpaceHashNew(cpFloat celldim, int cells, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
 
CP_EXPORT void cpSpaceHashResize(cpSpaceHash *hash, cpFloat celldim, int numcells);
 
//MARK: AABB Tree
 
typedef struct cpBBTree cpBBTree;
 
CP_EXPORT cpBBTree* cpBBTreeAlloc(void);
CP_EXPORT cpSpatialIndex* cpBBTreeInit(cpBBTree *tree, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
CP_EXPORT cpSpatialIndex* cpBBTreeNew(cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
 
CP_EXPORT void cpBBTreeOptimize(cpSpatialIndex *index);
 
typedef cpVect (*cpBBTreeVelocityFunc)(void *obj);
CP_EXPORT void cpBBTreeSetVelocityFunc(cpSpatialIndex *index, cpBBTreeVelocityFunc func);
 
//MARK: Single Axis Sweep
 
typedef struct cpSweep1D cpSweep1D;
 
CP_EXPORT cpSweep1D* cpSweep1DAlloc(void);
CP_EXPORT cpSpatialIndex* cpSweep1DInit(cpSweep1D *sweep, cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
CP_EXPORT cpSpatialIndex* cpSweep1DNew(cpSpatialIndexBBFunc bbfunc, cpSpatialIndex *staticIndex);
 
//MARK: Spatial Index Implementation
 
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 (*cpSpatialIndexQueryImpl)(cpSpatialIndex *index, void *obj, cpBB bb, cpSpatialIndexQueryFunc func, void *data);
typedef void (*cpSpatialIndexSegmentQueryImpl)(cpSpatialIndex *index, void *obj, cpVect a, cpVect b, cpFloat t_exit, cpSpatialIndexSegmentQueryFunc func, void *data);
 
struct cpSpatialIndexClass {
  cpSpatialIndexDestroyImpl destroy;
  
  cpSpatialIndexCountImpl count;
  cpSpatialIndexEachImpl each;
  
  cpSpatialIndexContainsImpl contains;
  cpSpatialIndexInsertImpl insert;
  cpSpatialIndexRemoveImpl remove;
  
  cpSpatialIndexReindexImpl reindex;
  cpSpatialIndexReindexObjectImpl reindexObject;
  cpSpatialIndexReindexQueryImpl reindexQuery;
  
  cpSpatialIndexQueryImpl query;
  cpSpatialIndexSegmentQueryImpl segmentQuery;
};
 
CP_EXPORT void cpSpatialIndexFree(cpSpatialIndex *index);
CP_EXPORT void cpSpatialIndexCollideStatic(cpSpatialIndex *dynamicIndex, cpSpatialIndex *staticIndex, cpSpatialIndexQueryFunc func, void *data);
 
static inline void cpSpatialIndexDestroy(cpSpatialIndex *index)
{
  if(index->klass) index->klass->destroy(index);
}
 
static inline int cpSpatialIndexCount(cpSpatialIndex *index)
{
  return index->klass->count(index);
}
 
static inline void cpSpatialIndexEach(cpSpatialIndex *index, cpSpatialIndexIteratorFunc func, void *data)
{
  index->klass->each(index, func, data);
}
 
static inline cpBool cpSpatialIndexContains(cpSpatialIndex *index, void *obj, cpHashValue hashid)
{
  return index->klass->contains(index, obj, hashid);
}
 
static inline void cpSpatialIndexInsert(cpSpatialIndex *index, void *obj, cpHashValue hashid)
{
  index->klass->insert(index, obj, hashid);
}
 
static inline void cpSpatialIndexRemove(cpSpatialIndex *index, void *obj, cpHashValue hashid)
{
  index->klass->remove(index, obj, hashid);
}
 
static inline void cpSpatialIndexReindex(cpSpatialIndex *index)
{
  index->klass->reindex(index);
}
 
static inline void cpSpatialIndexReindexObject(cpSpatialIndex *index, void *obj, cpHashValue hashid)
{
  index->klass->reindexObject(index, obj, hashid);
}
 
static inline void cpSpatialIndexQuery(cpSpatialIndex *index, void *obj, cpBB bb, cpSpatialIndexQueryFunc func, void *data)
{
  index->klass->query(index, obj, bb, func, data);
}
 
static inline void cpSpatialIndexSegmentQuery(cpSpatialIndex *index, void *obj, cpVect a, cpVect b, cpFloat t_exit, cpSpatialIndexSegmentQueryFunc func, void *data)
{
  index->klass->segmentQuery(index, obj, a, b, t_exit, func, data);
}
 
static inline void cpSpatialIndexReindexQuery(cpSpatialIndex *index, cpSpatialIndexQueryFunc func, void *data)
{
  index->klass->reindexQuery(index, func, data);
}