code:
/* Copyright (c) 2007 Scott Lembcke
 *
 * 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.
 */

// cpHashSet uses a chained hashtable implementation.
// Other than the transformation functions, there is nothing fancy going on.

// cpHashSetBin's form the linked lists in the chained hash table.
typedef struct cpHashSetBin {
	// Pointer to the element.
	CP_PRIVATE(void *elt);
	// Hash value of the element.
	CP_PRIVATE(cpHashValue hash);
	// Next element in the chain.
	CP_PRIVATE(struct cpHashSetBin *next);
} cpHashSetBin;

// Equality function. Returns true if ptr is equal to elt.
typedef cpBool (*cpHashSetEqlFunc)(void *ptr, void *elt);
// Used by cpHashSetInsert(). Called to transform the ptr into an element.
typedef void *(*cpHashSetTransFunc)(void *ptr, void *data);

typedef struct cpHashSet {
	// Number of elements stored in the table.
	CP_PRIVATE(int entries);
	// Number of cells in the table.
	CP_PRIVATE(int size);

	CP_PRIVATE(cpHashSetEqlFunc eql);
	CP_PRIVATE(cpHashSetTransFunc trans);

	// Default value returned by cpHashSetFind() when no element is found.
	// Defaults to NULL.
	CP_PRIVATE(void *default_value);

	// The table and recycled bins
	CP_PRIVATE(cpHashSetBin **table);
	CP_PRIVATE(cpHashSetBin *pooledBins);

	CP_PRIVATE(cpArray *allocatedBuffers);
} cpHashSet;

// Basic allocation/destruction functions.
void cpHashSetDestroy(cpHashSet *set);
void cpHashSetFree(cpHashSet *set);

cpHashSet *cpHashSetAlloc(void);
cpHashSet *cpHashSetInit(cpHashSet *set, int size, cpHashSetEqlFunc eqlFunc, cpHashSetTransFunc trans);
cpHashSet *cpHashSetNew(int size, cpHashSetEqlFunc eqlFunc, cpHashSetTransFunc trans);

// Insert an element into the set, returns the element.
// If it doesn't already exist, the transformation function is applied.
void *cpHashSetInsert(cpHashSet *set, cpHashValue hash, void *ptr, void *data);
// Remove and return an element from the set.
void *cpHashSetRemove(cpHashSet *set, cpHashValue hash, void *ptr);
// Find an element in the set. Returns the default value if the element isn't found.
void *cpHashSetFind(cpHashSet *set, cpHashValue hash, void *ptr);

// Iterate over a hashset.
typedef void (*cpHashSetIterFunc)(void *elt, void *data);
void cpHashSetEach(cpHashSet *set, cpHashSetIterFunc func, void *data);

// Iterate over a hashset, drop the element if the func returns false.
typedef cpBool (*cpHashSetFilterFunc)(void *elt, void *data);
void cpHashSetFilter(cpHashSet *set, cpHashSetFilterFunc func, void *data);


code:
/* Copyright (c) 2007 Scott Lembcke
 *
 * 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.
 */

// Axis structure used by cpPolyShape.
typedef struct cpPolyShapeAxis{
	// normal
	cpVect n;
	// distance from origin
	cpFloat d;
} cpPolyShapeAxis;

// Convex polygon shape structure.
typedef struct cpPolyShape{
	cpShape shape;

	// Vertex and axis lists.
	CP_PRIVATE(int numVerts);
	CP_PRIVATE(cpVect *verts);
	CP_PRIVATE(cpPolyShapeAxis *axes);

	// Transformed vertex and axis lists.
	CP_PRIVATE(cpVect *tVerts);
	CP_PRIVATE(cpPolyShapeAxis *tAxes);
} cpPolyShape;

// Basic allocation functions.
cpPolyShape *cpPolyShapeAlloc(void);
cpPolyShape *cpPolyShapeInit(cpPolyShape *poly, cpBody *body, int numVerts, cpVect *verts, cpVect offset);
cpShape *cpPolyShapeNew(cpBody *body, int numVerts, cpVect *verts, cpVect offset);

cpPolyShape *cpBoxShapeInit(cpPolyShape *poly, cpBody *body, cpFloat width, cpFloat height);
cpShape *cpBoxShapeNew(cpBody *body, cpFloat width, cpFloat height);

// Check that a set of vertexes has a correct winding and that they are convex
cpBool cpPolyValidate(const cpVect *verts, const int numVerts);

int cpPolyShapeGetNumVerts(cpShape *shape);
cpVect cpPolyShapeGetVert(cpShape *shape, int idx);

// *** inlined utility functions

// Returns the minimum distance of the polygon to the axis.
static inline cpFloat
cpPolyShapeValueOnAxis(const cpPolyShape *poly, const cpVect n, const cpFloat d)
{
	cpVect *verts = poly->CP_PRIVATE(tVerts);
	cpFloat min = cpvdot(n, verts[0]);

	int i;
	for(i=1; i<poly->CP_PRIVATE(numVerts); i++)
		min = cpfmin(min, cpvdot(n, verts[i]));

	return min - d;
}

// Returns true if the polygon contains the vertex.
static inline cpBool
cpPolyShapeContainsVert(const cpPolyShape *poly, const cpVect v)
{
	cpPolyShapeAxis *axes = poly->CP_PRIVATE(tAxes);

	int i;
	for(i=0; i<poly->CP_PRIVATE(numVerts); i++){
		cpFloat dist = cpvdot(axes[i].n, v) - axes[i].d;
		if(dist > 0.0f) return cpFalse;
	}

	return cpTrue;
}

// Same as cpPolyShapeContainsVert() but ignores faces pointing away from the normal.
static inline cpBool
cpPolyShapeContainsVertPartial(const cpPolyShape *poly, const cpVect v, const cpVect n)
{
	cpPolyShapeAxis *axes = poly->CP_PRIVATE(tAxes);

	int i;
	for(i=0; i<poly->CP_PRIVATE(numVerts); i++){
		if(cpvdot(axes[i].n, n) < 0.0f) continue;
		cpFloat dist = cpvdot(axes[i].n, v) - axes[i].d;
		if(dist > 0.0f) return cpFalse;
	}

	return cpTrue;
}

license: mit


code:
/* Copyright (c) 2007 Scott Lembcke
 *
 * 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.
 */

// Forward declarations required for defining other structs.
struct cpShape;
struct cpShapeClass;

typedef struct cpSegmentQueryInfo {
	struct cpShape *shape; // shape that was hit, NULL if no collision
	cpFloat t; // Distance along query segment, will always be in the range [0, 1].
	cpVect n; // normal of hit surface
} cpSegmentQueryInfo;

// Enumeration of shape types.
typedef enum cpShapeType{
	CP_CIRCLE_SHAPE,
	CP_SEGMENT_SHAPE,
	CP_POLY_SHAPE,
	CP_NUM_SHAPES
} cpShapeType;

// Shape class. Holds function pointers and type data.
typedef struct cpShapeClass {
	cpShapeType type;

	// Called by cpShapeCacheBB().
	cpBB (*cacheData)(struct cpShape *shape, cpVect p, cpVect rot);
	// Called to by cpShapeDestroy().
	void (*destroy)(struct cpShape *shape);

	// called by cpShapePointQuery().
	cpBool (*pointQuery)(struct cpShape *shape, cpVect p);

	// called by cpShapeSegmentQuery()
	 void (*segmentQuery)(struct cpShape *shape, cpVect a, cpVect b, cpSegmentQueryInfo *info);
} cpShapeClass;

// Basic shape struct that the others inherit from.
typedef struct cpShape{
	// The "class" of a shape as defined above
	CP_PRIVATE(const cpShapeClass *klass);

	// cpBody that the shape is attached to.
	cpBody *body;

	// Cached BBox for the shape.
	cpBB bb;

	// Sensors invoke callbacks, but do not generate collisions
	cpBool sensor;

	// *** Surface properties.

	// Coefficient of restitution. (elasticity)
	cpFloat e;
	// Coefficient of friction.
	cpFloat u;
	// Surface velocity used when solving for friction.
	cpVect surface_v;

	// *** User Definable Fields

	// User defined data pointer for the shape.
	cpDataPointer data;

	// User defined collision type for the shape.
	cpCollisionType collision_type;
	// User defined collision group for the shape.
	cpGroup group;
	// User defined layer bitmask for the shape.
	cpLayers layers;

	// *** Internally Used Fields

	// Shapes form a linked list when added to space on a non-NULL body
	CP_PRIVATE(struct cpShape *next);

	// Unique id used as the hash value.
	CP_PRIVATE(cpHashValue hashid);
} cpShape;

// Low level shape initialization func.
cpShape* cpShapeInit(cpShape *shape, const struct cpShapeClass *klass, cpBody *body);

// Basic destructor functions. (allocation functions are not shared)
void cpShapeDestroy(cpShape *shape);
void cpShapeFree(cpShape *shape);

// Cache the BBox of the shape.
cpBB cpShapeCacheBB(cpShape *shape);

// Test if a point lies within a shape.
cpBool cpShapePointQuery(cpShape *shape, cpVect p);

#define CP_DeclareShapeGetter(struct, type, name) type struct##Get##name(cpShape *shape)

// Circle shape structure.
typedef struct cpCircleShape{
	cpShape shape;

	// Center in body space coordinates
	CP_PRIVATE(cpVect c);
	// Radius.
	CP_PRIVATE(cpFloat r);

	// Transformed center. (world space coordinates)
	CP_PRIVATE(cpVect tc);
} cpCircleShape;

// Basic allocation functions for cpCircleShape.
cpCircleShape *cpCircleShapeAlloc(void);
cpCircleShape *cpCircleShapeInit(cpCircleShape *circle, cpBody *body, cpFloat radius, cpVect offset);
cpShape *cpCircleShapeNew(cpBody *body, cpFloat radius, cpVect offset);

CP_DeclareShapeGetter(cpCircleShape, cpVect, Offset);
CP_DeclareShapeGetter(cpCircleShape, cpFloat, Radius);

// Segment shape structure.
typedef struct cpSegmentShape{
	cpShape shape;

	// Endpoints and normal of the segment. (body space coordinates)
	cpVect CP_PRIVATE(a), CP_PRIVATE(b), CP_PRIVATE(n);
	// Radius of the segment. (Thickness)
	cpFloat CP_PRIVATE(r);

	// Transformed endpoints and normal. (world space coordinates)
	cpVect CP_PRIVATE(ta), CP_PRIVATE(tb), CP_PRIVATE(tn);
} cpSegmentShape;

// Basic allocation functions for cpSegmentShape.
cpSegmentShape* cpSegmentShapeAlloc(void);
cpSegmentShape* cpSegmentShapeInit(cpSegmentShape *seg, cpBody *body, cpVect a, cpVect b, cpFloat radius);
cpShape* cpSegmentShapeNew(cpBody *body, cpVect a, cpVect b, cpFloat radius);

CP_DeclareShapeGetter(cpSegmentShape, cpVect, A);
CP_DeclareShapeGetter(cpSegmentShape, cpVect, B);
CP_DeclareShapeGetter(cpSegmentShape, cpVect, Normal);
CP_DeclareShapeGetter(cpSegmentShape, cpFloat, Radius);

// For determinism, you can reset the shape id counter.
void cpResetShapeIdCounter(void);

// Directed segment queries against individual shapes.
void cpSegmentQueryInfoPrint(cpSegmentQueryInfo *info);

cpBool cpShapeSegmentQuery(cpShape *shape, cpVect a, cpVect b, cpSegmentQueryInfo *info);

static inline cpVect
cpSegmentQueryHitPoint(const cpVect start, const cpVect end, const cpSegmentQueryInfo info)
{
	return cpvlerp(start, end, info.t);
}

static inline cpFloat
cpSegmentQueryHitDist(const cpVect start, const cpVect end, const cpSegmentQueryInfo info)
{
	return cpvdist(start, end)*info.t;
}


code:
/* Copyright (c) 2007 Scott Lembcke
 *
 * 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.
 */

struct cpSpace;

// Number of frames that contact information should persist.
extern cpTimestamp cp_contact_persistence;

// User collision handler function types.
typedef cpBool (*cpCollisionBeginFunc)(cpArbiter *arb, struct cpSpace *space, void *data);
typedef cpBool (*cpCollisionPreSolveFunc)(cpArbiter *arb, struct cpSpace *space, void *data);
typedef void (*cpCollisionPostSolveFunc)(cpArbiter *arb, struct cpSpace *space, void *data);
typedef void (*cpCollisionSeparateFunc)(cpArbiter *arb, struct cpSpace *space, void *data);

// Structure for holding collision pair function information.
// Used internally.
typedef struct cpCollisionHandler {
	cpCollisionType a;
	cpCollisionType b;
	cpCollisionBeginFunc begin;
	cpCollisionPreSolveFunc preSolve;
	cpCollisionPostSolveFunc postSolve;
	cpCollisionSeparateFunc separate;
	void *data;
} cpCollisionHandler;

extern cpCollisionHandler cpSpaceDefaultHandler;

typedef struct cpContactBufferHeader {
	cpTimestamp stamp;
	struct cpContactBufferHeader *next;
	unsigned int numContacts;
} cpContactBufferHeader;

typedef struct cpSpace{
	// *** User definable fields

	// Number of iterations to use in the impulse solver to solve contacts.
	int iterations;

	// Number of iterations to use in the impulse solver to solve elastic collisions.
	int elasticIterations;

	// Default gravity to supply when integrating rigid body motions.
	cpVect gravity;

	// Default damping to supply when integrating rigid body motions.
	cpFloat damping;

	// Speed threshold for a body to be considered idle.
	// The default value of 0 means to let the space guess a good threshold based on gravity.
	cpFloat idleSpeedThreshold;

	// Time a group of bodies must remain idle in order to fall asleep
	// The default value of INFINITY disables the sleeping algorithm.
	cpFloat sleepTimeThreshold;

	// *** Internally Used Fields

	// When the space lock count is non zero you cannot add or remove objects
	CP_PRIVATE(int locked);

	// Time stamp. Is incremented on every call to cpSpaceStep().
	CP_PRIVATE(cpTimestamp stamp);

	// The static and active shape spatial hashes.
	CP_PRIVATE(cpSpaceHash *staticShapes);
	CP_PRIVATE(cpSpaceHash *activeShapes);

	// List of bodies in the system.
	CP_PRIVATE(cpArray *bodies);

	// List of groups of sleeping bodies.
	CP_PRIVATE(cpArray *sleepingComponents);

	// List of bodies that have been flagged to be awoken.
	CP_PRIVATE(cpArray *rousedBodies);

	// List of active arbiters for the impulse solver.
	CP_PRIVATE(cpArray *arbiters);
	CP_PRIVATE(cpArray *pooledArbiters);

	// Linked list ring of contact buffers.
	// Head is the newest buffer, and each buffer points to a newer buffer.
	// Head wraps around and points to the oldest (tail) buffer.
	CP_PRIVATE(cpContactBufferHeader *contactBuffersHead);
	CP_PRIVATE(cpContactBufferHeader *_contactBuffersTail_Deprecated);

	// List of buffers to be free()ed when destroying the space.
	CP_PRIVATE(cpArray *allocatedBuffers);

	// Persistant contact set.
	CP_PRIVATE(cpHashSet *contactSet);

	// List of constraints in the system.
	CP_PRIVATE(cpArray *constraints);

	// Set of collisionpair functions.
	CP_PRIVATE(cpHashSet *collFuncSet);
	// Default collision handler.
	CP_PRIVATE(cpCollisionHandler defaultHandler);

	CP_PRIVATE(cpHashSet *postStepCallbacks);

	cpBody staticBody;
} cpSpace;

// Basic allocation/destruction functions.
cpSpace* cpSpaceAlloc(void);
cpSpace* cpSpaceInit(cpSpace *space);
cpSpace* cpSpaceNew(void);

void cpSpaceDestroy(cpSpace *space);
void cpSpaceFree(cpSpace *space);

// Convenience function. Frees all referenced entities. (bodies, shapes and constraints)
void cpSpaceFreeChildren(cpSpace *space);

// Collision handler management functions.
void cpSpaceSetDefaultCollisionHandler(
	cpSpace *space,
	cpCollisionBeginFunc begin,
	cpCollisionPreSolveFunc preSolve,
	cpCollisionPostSolveFunc postSolve,
	cpCollisionSeparateFunc separate,
	void *data
);
void cpSpaceAddCollisionHandler(
	cpSpace *space,
	cpCollisionType a, cpCollisionType b,
	cpCollisionBeginFunc begin,
	cpCollisionPreSolveFunc preSolve,
	cpCollisionPostSolveFunc postSolve,
	cpCollisionSeparateFunc separate,
	void *data
);
void cpSpaceRemoveCollisionHandler(cpSpace *space, cpCollisionType a, cpCollisionType b);

// Add and remove entities from the system.
cpShape *cpSpaceAddShape(cpSpace *space, cpShape *shape);
cpShape *cpSpaceAddStaticShape(cpSpace *space, cpShape *shape);
cpBody *cpSpaceAddBody(cpSpace *space, cpBody *body);
cpConstraint *cpSpaceAddConstraint(cpSpace *space, cpConstraint *constraint);

void cpSpaceRemoveShape(cpSpace *space, cpShape *shape);
void cpSpaceRemoveStaticShape(cpSpace *space, cpShape *shape);
void cpSpaceRemoveBody(cpSpace *space, cpBody *body);
void cpSpaceRemoveConstraint(cpSpace *space, cpConstraint *constraint);

// Post Step function definition
typedef void (*cpPostStepFunc)(cpSpace *space, void *obj, void *data);
// Register a post step function to be called after cpSpaceStep() has finished.
// obj is used a key, you can only register one callback per unique value for obj
void cpSpaceAddPostStepCallback(cpSpace *space, cpPostStepFunc func, void *obj, void *data);

// Point query callback function
typedef void (*cpSpacePointQueryFunc)(cpShape *shape, void *data);
void cpSpacePointQuery(cpSpace *space, cpVect point, cpLayers layers, cpGroup group, cpSpacePointQueryFunc func, void *data);
cpShape *cpSpacePointQueryFirst(cpSpace *space, cpVect point, cpLayers layers, cpGroup group);

// Segment query callback function
typedef void (*cpSpaceSegmentQueryFunc)(cpShape *shape, cpFloat t, cpVect n, void *data);
void cpSpaceSegmentQuery(cpSpace *space, cpVect start, cpVect end, cpLayers layers, cpGroup group, cpSpaceSegmentQueryFunc func, void *data);
cpShape *cpSpaceSegmentQueryFirst(cpSpace *space, cpVect start, cpVect end, cpLayers layers, cpGroup group, cpSegmentQueryInfo *out);

// BB query callback function
typedef void (*cpSpaceBBQueryFunc)(cpShape *shape, void *data);
void cpSpaceBBQuery(cpSpace *space, cpBB bb, cpLayers layers, cpGroup group, cpSpaceBBQueryFunc func, void *data);

// Shape query callback function
typedef void (*cpSpaceShapeQueryFunc)(cpShape *shape, cpContactPointSet *points, void *data);
cpBool cpSpaceShapeQuery(cpSpace *space, cpShape *shape, cpSpaceShapeQueryFunc func, void *data);

void cpSpaceActivateShapesTouchingShape(cpSpace *space, cpShape *shape);

// Iterator function for iterating the bodies in a space.
typedef void (*cpSpaceBodyIterator)(cpBody *body, void *data);
void cpSpaceEachBody(cpSpace *space, cpSpaceBodyIterator func, void *data);

// Spatial hash management functions.
void cpSpaceResizeStaticHash(cpSpace *space, cpFloat dim, int count);
void cpSpaceResizeActiveHash(cpSpace *space, cpFloat dim, int count);
void cpSpaceRehashStatic(cpSpace *space);

void cpSpaceRehashShape(cpSpace *space, cpShape *shape);

// Update the space.
void cpSpaceStep(cpSpace *space, cpFloat dt);


code:
/* Copyright (c) 2007 Scott Lembcke
 *
 * 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.
 */

// The spatial hash is Chipmunk's default (and currently only) spatial index type.
// Based on a chained hash table.

// Used internally to track objects added to the hash
typedef struct cpHandle{
	// Pointer to the object
	void *obj;
	// Retain count
	int retain;
	// Query stamp. Used to make sure two objects
	// aren't identified twice in the same query.
	cpTimestamp stamp;
} cpHandle;

// Linked list element for in the chains.
typedef struct cpSpaceHashBin{
	cpHandle *handle;
	struct cpSpaceHashBin *next;
} cpSpaceHashBin;

// BBox callback. Called whenever the hash needs a bounding box from an object.
typedef cpBB (*cpSpaceHashBBFunc)(void *obj);

typedef struct cpSpaceHash{
	// Number of cells in the table.
	CP_PRIVATE(int numcells);
	// Dimentions of the cells.
	CP_PRIVATE(cpFloat celldim);

	// BBox callback.
	CP_PRIVATE(cpSpaceHashBBFunc bbfunc);

	// Hashset of the handles and the recycled ones.
	CP_PRIVATE(cpHashSet *handleSet);
	CP_PRIVATE(cpArray *pooledHandles);

	// The table and the recycled bins.
	CP_PRIVATE(cpSpaceHashBin **table);
	CP_PRIVATE(cpSpaceHashBin *pooledBins);

	// list of buffers to free on destruction.
	CP_PRIVATE(cpArray *allocatedBuffers);

	// Incremented on each query. See cpHandle.stamp.
	CP_PRIVATE(cpTimestamp stamp);
} cpSpaceHash;

//Basic allocation/destruction functions.
cpSpaceHash *cpSpaceHashAlloc(void);
cpSpaceHash *cpSpaceHashInit(cpSpaceHash *hash, cpFloat celldim, int cells, cpSpaceHashBBFunc bbfunc);
cpSpaceHash *cpSpaceHashNew(cpFloat celldim, int cells, cpSpaceHashBBFunc bbfunc);

void cpSpaceHashDestroy(cpSpaceHash *hash);
void cpSpaceHashFree(cpSpaceHash *hash);

// Resize the hashtable. (Does not rehash! You must call cpSpaceHashRehash() if needed.)
void cpSpaceHashResize(cpSpaceHash *hash, cpFloat celldim, int numcells);

// Add an object to the hash.
void cpSpaceHashInsert(cpSpaceHash *hash, void *obj, cpHashValue id, cpBB _deprecated_ignored);
// Remove an object from the hash.
void cpSpaceHashRemove(cpSpaceHash *hash, void *obj, cpHashValue id);

// Iterator function
typedef void (*cpSpaceHashIterator)(void *obj, void *data);
// Iterate over the objects in the hash.
void cpSpaceHashEach(cpSpaceHash *hash, cpSpaceHashIterator func, void *data);

// Rehash the contents of the hash.
void cpSpaceHashRehash(cpSpaceHash *hash);
// Rehash only a specific object.
void cpSpaceHashRehashObject(cpSpaceHash *hash, void *obj, cpHashValue id);

// Query callback.
typedef void (*cpSpaceHashQueryFunc)(void *obj1, void *obj2, void *data);
// Point query the hash. A reference to the query point is passed as obj1 to the query callback.
void cpSpaceHashPointQuery(cpSpaceHash *hash, cpVect point, cpSpaceHashQueryFunc func, void *data);
// Query the hash for a given BBox.
void cpSpaceHashQuery(cpSpaceHash *hash, void *obj, cpBB bb, cpSpaceHashQueryFunc func, void *data);
// Run a query for the object, then insert it. (Optimized case)
void cpSpaceHashQueryInsert(cpSpaceHash *hash, void *obj, cpBB bb, cpSpaceHashQueryFunc func, void *data);
// Rehashes while querying for each object. (Optimized case)
void cpSpaceHashQueryRehash(cpSpaceHash *hash, cpSpaceHashQueryFunc func, void *data);

// Segment Query callback.
// Return value is uesd for early exits of the query.
// If while traversing the grid, the raytrace function detects that an entire grid cell is beyond the hit point, it will stop the trace.
typedef cpFloat (*cpSpaceHashSegmentQueryFunc)(void *obj1, void *obj2, void *data);
void cpSpaceHashSegmentQuery(cpSpaceHash *hash, void *obj, cpVect a, cpVect b, cpFloat t_exit, cpSpaceHashSegmentQueryFunc func, void *data);


code:
/* Copyright (c) 2007 Scott Lembcke
 *
 * 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.
 */

/// Constant for the zero vector.
static const cpVect cpvzero = {0.0f,0.0f};

/// Convenience constructor for cpVect structs.
static inline cpVect
cpv(const cpFloat x, const cpFloat y)
{
	cpVect v = {x, y};
	return v;
}

// non-inlined functions

/// Returns the length of v.
cpFloat cpvlength(const cpVect v);

/// Spherical linearly interpolate between v1 and v2.
cpVect cpvslerp(const cpVect v1, const cpVect v2, const cpFloat t);

/// Spherical linearly interpolate between v1 towards v2 by no more than angle a radians
cpVect cpvslerpconst(const cpVect v1, const cpVect v2, const cpFloat a);

/// Returns the unit length vector for the given angle (in radians).
cpVect cpvforangle(const cpFloat a);

/// Returns the angular direction v is pointing in (in radians).
cpFloat cpvtoangle(const cpVect v);

/**
	Returns a string representation of v. Intended mostly for debugging purposes and not production use.

	@attention The string points to a static local and is reset every time the function is called.
	If you want to print more than one vector you will have to split up your printing onto separate lines.
*/
char *cpvstr(const cpVect v);

/// Check if two vectors are equal. (Be careful when comparing floating point numbers!)
static inline cpBool
cpveql(const cpVect v1, const cpVect v2)
{
	return (v1.x == v2.x && v1.y == v2.y);
}

/// Add two vectors
static inline cpVect
cpvadd(const cpVect v1, const cpVect v2)
{
	return cpv(v1.x + v2.x, v1.y + v2.y);
}

/// Negate a vector.
static inline cpVect
cpvneg(const cpVect v)
{
	return cpv(-v.x, -v.y);
}

/// Subtract two vectors.
static inline cpVect
cpvsub(const cpVect v1, const cpVect v2)
{
	return cpv(v1.x - v2.x, v1.y - v2.y);
}

/// Scalar multiplication.
static inline cpVect
cpvmult(const cpVect v, const cpFloat s)
{
	return cpv(v.x*s, v.y*s);
}

/// Vector dot product.
static inline cpFloat
cpvdot(const cpVect v1, const cpVect v2)
{
	return v1.x*v2.x + v1.y*v2.y;
}

/**
	2D vector cross product analog.
	The cross product of 2D vectors results in a 3D vector with only a z component.
	This function returns the magnitude of the z value.
*/
static inline cpFloat
cpvcross(const cpVect v1, const cpVect v2)
{
	return v1.x*v2.y - v1.y*v2.x;
}

/// Returns a perpendicular vector. (90 degree rotation)
static inline cpVect
cpvperp(const cpVect v)
{
	return cpv(-v.y, v.x);
}

/// Returns a perpendicular vector. (-90 degree rotation)
static inline cpVect
cpvrperp(const cpVect v)
{
	return cpv(v.y, -v.x);
}

/// Returns the vector projection of v1 onto v2.
static inline cpVect
cpvproject(const cpVect v1, const cpVect v2)
{
	return cpvmult(v2, cpvdot(v1, v2)/cpvdot(v2, v2));
}

/// Uses complex number multiplication to rotate v1 by v2. Scaling will occur if v1 is not a unit vector.
static inline cpVect
cpvrotate(const cpVect v1, const cpVect v2)
{
	return cpv(v1.x*v2.x - v1.y*v2.y, v1.x*v2.y + v1.y*v2.x);
}

/// Inverse of cpvrotate().
static inline cpVect
cpvunrotate(const cpVect v1, const cpVect v2)
{
	return cpv(v1.x*v2.x + v1.y*v2.y, v1.y*v2.x - v1.x*v2.y);
}

/// Returns the squared length of v. Faster than cpvlength() when you only need to compare lengths.
static inline cpFloat
cpvlengthsq(const cpVect v)
{
	return cpvdot(v, v);
}

/// Linearly interpolate between v1 and v2.
static inline cpVect
cpvlerp(const cpVect v1, const cpVect v2, const cpFloat t)
{
	return cpvadd(cpvmult(v1, 1.0f - t), cpvmult(v2, t));
}

/// Returns a normalized copy of v.
static inline cpVect
cpvnormalize(const cpVect v)
{
	return cpvmult(v, 1.0f/cpvlength(v));
}

/// Returns a normalized copy of v or cpvzero if v was already cpvzero. Protects against divide by zero errors.
static inline cpVect
cpvnormalize_safe(const cpVect v)
{
	return (v.x == 0.0f && v.y == 0.0f ? cpvzero : cpvnormalize(v));
}

/// Clamp v to length len.
static inline cpVect
cpvclamp(const cpVect v, const cpFloat len)
{
	return (cpvdot(v,v) > len*len) ? cpvmult(cpvnormalize(v), len) : v;
}

/// Linearly interpolate between v1 towards v2 by distance d.
static inline cpVect
cpvlerpconst(cpVect v1, cpVect v2, cpFloat d)
{
	return cpvadd(v1, cpvclamp(cpvsub(v2, v1), d));
}

/// Returns the distance between v1 and v2.
static inline cpFloat
cpvdist(const cpVect v1, const cpVect v2)
{
	return cpvlength(cpvsub(v1, v2));
}

/// Returns the squared distance between v1 and v2. Faster than cpvdist() when you only need to compare distances.
static inline cpFloat
cpvdistsq(const cpVect v1, const cpVect v2)
{
	return cpvlengthsq(cpvsub(v1, v2));
}

/// Returns true if the distance between v1 and v2 is less than dist.
static inline cpBool
cpvnear(const cpVect v1, const cpVect v2, const cpFloat dist)
{
	return cpvdistsq(v1, v2) < dist*dist;
}


code:
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<bada>
    <type>0</type>
    <sdk>E:\bada\1.0.0</sdk>
    <model>Wave_LP2</model>
    <properties/>
</bada>