text:
/*
Copyright (c) 2003-2006 Gino van den Bergen / Erwin Coumans  http://continuousphysics.com/Bullet/

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

#ifndef BT_TRANSFORM_H
#define BT_TRANSFORM_H

#include "btMatrix3x3.h"

#ifdef BT_USE_DOUBLE_PRECISION
#define btTransformData btTransformDoubleData
#else
#define btTransformData btTransformFloatData
#endif

/**@brief The btTransform class supports rigid transforms with only translation and rotation and no scaling/shear.
 *It can be used in combination with btVector3, btQuaternion and btMatrix3x3 linear algebra classes. */
ATTRIBUTE_ALIGNED16(class) btTransform {

  ///Storage for the rotation
	btMatrix3x3 m_basis;
  ///Storage for the translation
	btVector3   m_origin;

public:

  /**@brief No initialization constructor */
	btTransform() {}
  /**@brief Constructor from btQuaternion (optional btVector3 )
   * @param q Rotation from quaternion
   * @param c Translation from Vector (default 0,0,0) */
	explicit SIMD_FORCE_INLINE btTransform(const btQuaternion& q,
		const btVector3& c = btVector3(btScalar(0), btScalar(0), btScalar(0)))
		: m_basis(q),
		m_origin(c)
	{}

  /**@brief Constructor from btMatrix3x3 (optional btVector3)
   * @param b Rotation from Matrix
   * @param c Translation from Vector default (0,0,0)*/
	explicit SIMD_FORCE_INLINE btTransform(const btMatrix3x3& b,
		const btVector3& c = btVector3(btScalar(0), btScalar(0), btScalar(0)))
		: m_basis(b),
		m_origin(c)
	{}
  /**@brief Copy constructor */
	SIMD_FORCE_INLINE btTransform (const btTransform& other)
		: m_basis(other.m_basis),
		m_origin(other.m_origin)
	{
	}
  /**@brief Assignment Operator */
	SIMD_FORCE_INLINE btTransform& operator=(const btTransform& other)
	{
		m_basis = other.m_basis;
		m_origin = other.m_origin;
		return *this;
	}

  /**@brief Set the current transform as the value of the product of two transforms
   * @param t1 Transform 1
   * @param t2 Transform 2
   * This = Transform1 * Transform2 */
		SIMD_FORCE_INLINE void mult(const btTransform& t1, const btTransform& t2) {
			m_basis = t1.m_basis * t2.m_basis;
			m_origin = t1(t2.m_origin);
		}

/*		void multInverseLeft(const btTransform& t1, const btTransform& t2) {
			btVector3 v = t2.m_origin - t1.m_origin;
			m_basis = btMultTransposeLeft(t1.m_basis, t2.m_basis);
			m_origin = v * t1.m_basis;
		}
		*/

/**@brief Return the transform of the vector */
	SIMD_FORCE_INLINE btVector3 operator()(const btVector3& x) const
	{
        return x.dot3(m_basis[0], m_basis[1], m_basis[2]) + m_origin;
	}

  /**@brief Return the transform of the vector */
	SIMD_FORCE_INLINE btVector3 operator*(const btVector3& x) const
	{
		return (*this)(x);
	}

  /**@brief Return the transform of the btQuaternion */
	SIMD_FORCE_INLINE btQuaternion operator*(const btQuaternion& q) const
	{
		return getRotation() * q;
	}

  /**@brief Return the basis matrix for the rotation */
	SIMD_FORCE_INLINE btMatrix3x3&       getBasis()          { return m_basis; }
  /**@brief Return the basis matrix for the rotation */
	SIMD_FORCE_INLINE const btMatrix3x3& getBasis()    const { return m_basis; }

  /**@brief Return the origin vector translation */
	SIMD_FORCE_INLINE btVector3&         getOrigin()         { return m_origin; }
  /**@brief Return the origin vector translation */
	SIMD_FORCE_INLINE const btVector3&   getOrigin()   const { return m_origin; }

  /**@brief Return a quaternion representing the rotation */
	btQuaternion getRotation() const
	{
		btQuaternion q;
		m_basis.getRotation(q);
		return q;
	}

  /**@brief Set from an array
   * @param m A pointer to a 16 element array (12 rotation(row major padded on the right by 1), and 3 translation */
	void setFromOpenGLMatrix(const btScalar *m)
	{
		m_basis.setFromOpenGLSubMatrix(m);
		m_origin.setValue(m[12],m[13],m[14]);
	}

  /**@brief Fill an array representation
   * @param m A pointer to a 16 element array (12 rotation(row major padded on the right by 1), and 3 translation */
	void getOpenGLMatrix(btScalar *m) const
	{
		m_basis.getOpenGLSubMatrix(m);
		m[12] = m_origin.x();
		m[13] = m_origin.y();
		m[14] = m_origin.z();
		m[15] = btScalar(1.0);
	}

  /**@brief Set the translational element
   * @param origin The vector to set the translation to */
	SIMD_FORCE_INLINE void setOrigin(const btVector3& origin)
	{
		m_origin = origin;
	}

	SIMD_FORCE_INLINE btVector3 invXform(const btVector3& inVec) const;

  /**@brief Set the rotational element by btMatrix3x3 */
	SIMD_FORCE_INLINE void setBasis(const btMatrix3x3& basis)
	{
		m_basis = basis;
	}

  /**@brief Set the rotational element by btQuaternion */
	SIMD_FORCE_INLINE void setRotation(const btQuaternion& q)
	{
		m_basis.setRotation(q);
	}

  /**@brief Set this transformation to the identity */
	void setIdentity()
	{
		m_basis.setIdentity();
		m_origin.setValue(btScalar(0.0), btScalar(0.0), btScalar(0.0));
	}

  /**@brief Multiply this Transform by another(this = this * another)
   * @param t The other transform */
	btTransform& operator*=(const btTransform& t)
	{
		m_origin += m_basis * t.m_origin;
		m_basis *= t.m_basis;
		return *this;
	}

  /**@brief Return the inverse of this transform */
	btTransform inverse() const
	{
		btMatrix3x3 inv = m_basis.transpose();
		return btTransform(inv, inv * -m_origin);
	}

  /**@brief Return the inverse of this transform times the other transform
   * @param t The other transform
   * return this.inverse() * the other */
	btTransform inverseTimes(const btTransform& t) const;

  /**@brief Return the product of this transform and the other */
	btTransform operator*(const btTransform& t) const;

  /**@brief Return an identity transform */
	static const btTransform&	getIdentity()
	{
		static const btTransform identityTransform(btMatrix3x3::getIdentity());
		return identityTransform;
	}

	void	serialize(struct	btTransformData& dataOut) const;

	void	serializeFloat(struct	btTransformFloatData& dataOut) const;

	void	deSerialize(const struct	btTransformData& dataIn);

	void	deSerializeDouble(const struct	btTransformDoubleData& dataIn);

	void	deSerializeFloat(const struct	btTransformFloatData& dataIn);

};

SIMD_FORCE_INLINE btVector3
btTransform::invXform(const btVector3& inVec) const
{
	btVector3 v = inVec - m_origin;
	return (m_basis.transpose() * v);
}

SIMD_FORCE_INLINE btTransform
btTransform::inverseTimes(const btTransform& t) const
{
	btVector3 v = t.getOrigin() - m_origin;
		return btTransform(m_basis.transposeTimes(t.m_basis),
			v * m_basis);
}

SIMD_FORCE_INLINE btTransform
btTransform::operator*(const btTransform& t) const
{
	return btTransform(m_basis * t.m_basis,
		(*this)(t.m_origin));
}

/**@brief Test if two transforms have all elements equal */
SIMD_FORCE_INLINE bool operator==(const btTransform& t1, const btTransform& t2)
{
   return ( t1.getBasis()  == t2.getBasis() &&
            t1.getOrigin() == t2.getOrigin() );
}

///for serialization
struct	btTransformFloatData
{
	btMatrix3x3FloatData	m_basis;
	btVector3FloatData	m_origin;
};

struct	btTransformDoubleData
{
	btMatrix3x3DoubleData	m_basis;
	btVector3DoubleData	m_origin;
};

SIMD_FORCE_INLINE	void	btTransform::serialize(btTransformData& dataOut) const
{
	m_basis.serialize(dataOut.m_basis);
	m_origin.serialize(dataOut.m_origin);
}

SIMD_FORCE_INLINE	void	btTransform::serializeFloat(btTransformFloatData& dataOut) const
{
	m_basis.serializeFloat(dataOut.m_basis);
	m_origin.serializeFloat(dataOut.m_origin);
}

SIMD_FORCE_INLINE	void	btTransform::deSerialize(const btTransformData& dataIn)
{
	m_basis.deSerialize(dataIn.m_basis);
	m_origin.deSerialize(dataIn.m_origin);
}

SIMD_FORCE_INLINE	void	btTransform::deSerializeFloat(const btTransformFloatData& dataIn)
{
	m_basis.deSerializeFloat(dataIn.m_basis);
	m_origin.deSerializeFloat(dataIn.m_origin);
}

SIMD_FORCE_INLINE	void	btTransform::deSerializeDouble(const btTransformDoubleData& dataIn)
{
	m_basis.deSerializeDouble(dataIn.m_basis);
	m_origin.deSerializeDouble(dataIn.m_origin);
}

#endif //BT_TRANSFORM_H


text:
/*
Copyright (c) 2003-2014 Erwin Coumans  http://bullet.googlecode.com

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

#ifndef BT_THREADS_H
#define BT_THREADS_H

#include "btScalar.h" // has definitions like SIMD_FORCE_INLINE

#if defined (_MSC_VER) && _MSC_VER >= 1600
// give us a compile error if any signatures of overriden methods is changed
#define BT_OVERRIDE override
#endif

#ifndef BT_OVERRIDE
#define BT_OVERRIDE
#endif

const unsigned int BT_MAX_THREAD_COUNT = 64;  // only if BT_THREADSAFE is 1

// for internal use only
bool btIsMainThread();
bool btThreadsAreRunning();
unsigned int btGetCurrentThreadIndex();
void btResetThreadIndexCounter(); // notify that all worker threads have been destroyed

///
/// btSpinMutex -- lightweight spin-mutex implemented with atomic ops, never puts
///               a thread to sleep because it is designed to be used with a task scheduler
///               which has one thread per core and the threads don't sleep until they
///               run out of tasks. Not good for general purpose use.
///
class btSpinMutex
{
    int mLock;

public:
    btSpinMutex()
    {
        mLock = 0;
    }
    void lock();
    void unlock();
    bool tryLock();
};

//
// NOTE: btMutex* is for internal Bullet use only
//
// If BT_THREADSAFE is undefined or 0, should optimize away to nothing.
// This is good because for the single-threaded build of Bullet, any calls
// to these functions will be optimized out.
//
// However, for users of the multi-threaded build of Bullet this is kind
// of bad because if you call any of these functions from external code
// (where BT_THREADSAFE is undefined) you will get unexpected race conditions.
//
SIMD_FORCE_INLINE void btMutexLock( btSpinMutex* /* mutex */ )
{
#if BT_THREADSAFE
    mutex->lock();
#endif // #if BT_THREADSAFE
}

SIMD_FORCE_INLINE void btMutexUnlock( btSpinMutex* /* mutex */ )
{
#if BT_THREADSAFE
    mutex->unlock();
#endif // #if BT_THREADSAFE
}

SIMD_FORCE_INLINE bool btMutexTryLock( btSpinMutex* /* mutex */ )
{
#if BT_THREADSAFE
    return mutex->tryLock();
#else
    return true;
#endif // #if BT_THREADSAFE
}

//
// btIParallelForBody -- subclass this to express work that can be done in parallel
//
class btIParallelForBody
{
public:
    virtual ~btIParallelForBody() {}
    virtual void forLoop( int iBegin, int iEnd ) const = 0;
};

//
// btITaskScheduler -- subclass this to implement a task scheduler that can dispatch work to
//                     worker threads
//
class btITaskScheduler
{
public:
    btITaskScheduler( const char* name );
    virtual ~btITaskScheduler() {}
    const char* getName() const { return m_name; }

    virtual int getMaxNumThreads() const = 0;
    virtual int getNumThreads() const = 0;
    virtual void setNumThreads( int numThreads ) = 0;
    virtual void parallelFor( int iBegin, int iEnd, int grainSize, const btIParallelForBody& body ) = 0;

    // internal use only
    virtual void activate();
    virtual void deactivate();

protected:
    const char* m_name;
    unsigned int m_savedThreadCounter;
    bool m_isActive;
};

// set the task scheduler to use for all calls to btParallelFor()
// NOTE: you must set this prior to using any of the multi-threaded "Mt" classes
void btSetTaskScheduler( btITaskScheduler* ts );

// get the current task scheduler
btITaskScheduler* btGetTaskScheduler();

// get non-threaded task scheduler (always available)
btITaskScheduler* btGetSequentialTaskScheduler();

// get OpenMP task scheduler (if available, otherwise returns null)
btITaskScheduler* btGetOpenMPTaskScheduler();

// get Intel TBB task scheduler (if available, otherwise returns null)
btITaskScheduler* btGetTBBTaskScheduler();

// get PPL task scheduler (if available, otherwise returns null)
btITaskScheduler* btGetPPLTaskScheduler();

// btParallelFor -- call this to dispatch work like a for-loop
//                 (iterations may be done out of order, so no dependencies are allowed)
void btParallelFor( int iBegin, int iEnd, int grainSize, const btIParallelForBody& body );

#endif

repo_name: JoshParnell/libphx

repo_language: C

mime_type: text/x-c++


text:
/*
Bullet Continuous Collision Detection and Physics Library
Copyright (c) 2003-2009 Erwin Coumans  http://bulletphysics.org

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

#ifndef BT_SERIALIZER_H
#define BT_SERIALIZER_H

#include "btScalar.h" // has definitions like SIMD_FORCE_INLINE
#include "btHashMap.h"

#if !defined( __CELLOS_LV2__) && !defined(__MWERKS__)
#include <memory.h>
#endif
#include <string.h>

extern char sBulletDNAstr[];
extern int sBulletDNAlen;
extern char sBulletDNAstr64[];
extern int sBulletDNAlen64;

SIMD_FORCE_INLINE	int btStrLen(const char* str)
{
    if (!str)
		return(0);
	int len = 0;

	while (*str != 0)
	{
        str++;
        len++;
    }

    return len;
}

class btChunk
{
public:
	int		m_chunkCode;
	int		m_length;
	void	*m_oldPtr;
	int		m_dna_nr;
	int		m_number;
};

enum	btSerializationFlags
{
	BT_SERIALIZE_NO_BVH = 1,
	BT_SERIALIZE_NO_TRIANGLEINFOMAP = 2,
	BT_SERIALIZE_NO_DUPLICATE_ASSERT = 4
};

class	btSerializer
{

public:

	virtual ~btSerializer() {}

	virtual	const unsigned char*		getBufferPointer() const = 0;

	virtual	int		getCurrentBufferSize() const = 0;

	virtual	btChunk*	allocate(size_t size, int numElements) = 0;

	virtual	void	finalizeChunk(btChunk* chunk, const char* structType, int chunkCode,void* oldPtr)= 0;

	virtual	 void*	findPointer(void* oldPtr)  = 0;

	virtual	void*	getUniquePointer(void*oldPtr) = 0;

	virtual	void	startSerialization() = 0;

	virtual	void	finishSerialization() = 0;

	virtual	const char*	findNameForPointer(const void* ptr) const = 0;

	virtual	void	registerNameForPointer(const void* ptr, const char* name) = 0;

	virtual void	serializeName(const char* ptr) = 0;

	virtual int		getSerializationFlags() const = 0;

	virtual void	setSerializationFlags(int flags) = 0;

	virtual int getNumChunks() const = 0;

	virtual const btChunk* getChunk(int chunkIndex) const = 0;

};

#define BT_HEADER_LENGTH 12
#if defined(__sgi) || defined (__sparc) || defined (__sparc__) || defined (__PPC__) || defined (__ppc__) || defined (__BIG_ENDIAN__)
#	define BT_MAKE_ID(a,b,c,d) ( (int)(a)<<24 | (int)(b)<<16 | (c)<<8 | (d) )
#else
#	define BT_MAKE_ID(a,b,c,d) ( (int)(d)<<24 | (int)(c)<<16 | (b)<<8 | (a) )
#endif

#define BT_MULTIBODY_CODE       BT_MAKE_ID('M','B','D','Y')
#define BT_SOFTBODY_CODE		BT_MAKE_ID('S','B','D','Y')
#define BT_COLLISIONOBJECT_CODE BT_MAKE_ID('C','O','B','J')
#define BT_RIGIDBODY_CODE		BT_MAKE_ID('R','B','D','Y')
#define BT_CONSTRAINT_CODE		BT_MAKE_ID('C','O','N','S')
#define BT_BOXSHAPE_CODE		BT_MAKE_ID('B','O','X','S')
#define BT_QUANTIZED_BVH_CODE	BT_MAKE_ID('Q','B','V','H')
#define BT_TRIANLGE_INFO_MAP	BT_MAKE_ID('T','M','A','P')
#define BT_SHAPE_CODE			BT_MAKE_ID('S','H','A','P')
#define BT_ARRAY_CODE			BT_MAKE_ID('A','R','A','Y')
#define BT_SBMATERIAL_CODE		BT_MAKE_ID('S','B','M','T')
#define BT_SBNODE_CODE			BT_MAKE_ID('S','B','N','D')
#define BT_DYNAMICSWORLD_CODE	BT_MAKE_ID('D','W','L','D')
#define BT_DNA_CODE				BT_MAKE_ID('D','N','A','1')

struct	btPointerUid
{
	union
	{
		void*	m_ptr;
		int		m_uniqueIds[2];
	};
};

struct btBulletSerializedArrays
{
	btBulletSerializedArrays()
	{
	}
	btAlignedObjectArray<struct btQuantizedBvhDoubleData*>	m_bvhsDouble;
	btAlignedObjectArray<struct btQuantizedBvhFloatData*>	m_bvhsFloat;
	btAlignedObjectArray<struct btCollisionShapeData*> m_colShapeData;
	btAlignedObjectArray<struct btDynamicsWorldDoubleData*> m_dynamicWorldInfoDataDouble;
	btAlignedObjectArray<struct btDynamicsWorldFloatData*> m_dynamicWorldInfoDataFloat;
	btAlignedObjectArray<struct btRigidBodyDoubleData*> m_rigidBodyDataDouble;
	btAlignedObjectArray<struct btRigidBodyFloatData*> m_rigidBodyDataFloat;
	btAlignedObjectArray<struct btCollisionObjectDoubleData*> m_collisionObjectDataDouble;
	btAlignedObjectArray<struct btCollisionObjectFloatData*> m_collisionObjectDataFloat;
	btAlignedObjectArray<struct btTypedConstraintFloatData*> m_constraintDataFloat;
	btAlignedObjectArray<struct btTypedConstraintDoubleData*> m_constraintDataDouble;
	btAlignedObjectArray<struct btTypedConstraintData*> m_constraintData;//for backwards compatibility
	btAlignedObjectArray<struct btSoftBodyFloatData*> m_softBodyFloatData;
	btAlignedObjectArray<struct btSoftBodyDoubleData*> m_softBodyDoubleData;

};

///The btDefaultSerializer is the main Bullet serialization class.
///The constructor takes an optional argument for backwards compatibility, it is recommended to leave this empty/zero.
class btDefaultSerializer	:	public btSerializer
{

protected:

	btAlignedObjectArray<char*>			mTypes;
	btAlignedObjectArray<short*>			mStructs;
	btAlignedObjectArray<short>			mTlens;
	btHashMap<btHashInt, int>			mStructReverse;
	btHashMap<btHashString,int>	mTypeLookup;

	btHashMap<btHashPtr,void*>	m_chunkP;

	btHashMap<btHashPtr,const char*>	m_nameMap;

	btHashMap<btHashPtr,btPointerUid>	m_uniquePointers;
	int	m_uniqueIdGenerator;

	int					m_totalSize;
	unsigned char*		m_buffer;
	bool                m_ownsBuffer;
	int					m_currentSize;
	void*				m_dna;
	int					m_dnaLength;

	int					m_serializationFlags;

	btAlignedObjectArray<btChunk*>	m_chunkPtrs;

protected:

	virtual	void*	findPointer(void* oldPtr)
	{
		void** ptr = m_chunkP.find(oldPtr);
		if (ptr && *ptr)
			return *ptr;
		return 0;
	}

		virtual void	writeDNA()
		{
			btChunk* dnaChunk = allocate(m_dnaLength,1);
			memcpy(dnaChunk->m_oldPtr,m_dna,m_dnaLength);
			finalizeChunk(dnaChunk,"DNA1",BT_DNA_CODE, m_dna);
		}

		int getReverseType(const char *type) const
		{

			btHashString key(type);
			const int* valuePtr = mTypeLookup.find(key);
			if (valuePtr)
				return *valuePtr;

			return -1;
		}

		void initDNA(const char* bdnaOrg,int dnalen)
		{
			///was already initialized
			if (m_dna)
				return;

			int littleEndian= 1;
			littleEndian= ((char*)&littleEndian)[0];

			m_dna = btAlignedAlloc(dnalen,16);
			memcpy(m_dna,bdnaOrg,dnalen);
			m_dnaLength = dnalen;

			int *intPtr=0;
			short *shtPtr=0;
			char *cp = 0;int dataLen =0;
			intPtr = (int*)m_dna;

			/*
				SDNA (4 bytes) (magic number)
				NAME (4 bytes)
				<nr> (4 bytes) amount of names (int)
				<string>
				<string>
			*/

			if (strncmp((const char*)m_dna, "SDNA", 4)==0)
			{
				// skip ++ NAME
				intPtr++; intPtr++;
			}

			// Parse names
			if (!littleEndian)
				*intPtr = btSwapEndian(*intPtr);

			dataLen = *intPtr;

			intPtr++;

			cp = (char*)intPtr;
			int i;
			for ( i=0; i<dataLen; i++)
			{

				while (*cp)cp++;
				cp++;
			}
			cp = btAlignPointer(cp,4);

			/*
				TYPE (4 bytes)
				<nr> amount of types (int)
				<string>
				<string>
			*/

			intPtr = (int*)cp;
			btAssert(strncmp(cp, "TYPE", 4)==0); intPtr++;

			if (!littleEndian)
				*intPtr =  btSwapEndian(*intPtr);

			dataLen = *intPtr;
			intPtr++;

			cp = (char*)intPtr;
			for (i=0; i<dataLen; i++)
			{
				mTypes.push_back(cp);
				while (*cp)cp++;
				cp++;
			}

			cp = btAlignPointer(cp,4);

			/*
				TLEN (4 bytes)
				<len> (short) the lengths of types
				<len>
			*/

			// Parse type lens
			intPtr = (int*)cp;
			btAssert(strncmp(cp, "TLEN", 4)==0); intPtr++;

			dataLen = (int)mTypes.size();

			shtPtr = (short*)intPtr;
			for (i=0; i<dataLen; i++, shtPtr++)
			{
				if (!littleEndian)
					shtPtr[0] = btSwapEndian(shtPtr[0]);
				mTlens.push_back(shtPtr[0]);
			}

			if (dataLen & 1) shtPtr++;

			/*
				STRC (4 bytes)
				<nr> amount of structs (int)
				<typenr>
				<nr_of_elems>
				<typenr>
				<namenr>
				<typenr>
				<namenr>
			*/

			intPtr = (int*)shtPtr;
			cp = (char*)intPtr;
			btAssert(strncmp(cp, "STRC", 4)==0); intPtr++;

			if (!littleEndian)
				*intPtr = btSwapEndian(*intPtr);
			dataLen = *intPtr ;
			intPtr++;

			shtPtr = (short*)intPtr;
			for (i=0; i<dataLen; i++)
			{
				mStructs.push_back (shtPtr);

				if (!littleEndian)
				{
					shtPtr[0]= btSwapEndian(shtPtr[0]);
					shtPtr[1]= btSwapEndian(shtPtr[1]);

					int len = shtPtr[1];
					shtPtr+= 2;

					for (int a=0; a<len; a++, shtPtr+=2)
					{
							shtPtr[0]= btSwapEndian(shtPtr[0]);
							shtPtr[1]= btSwapEndian(shtPtr[1]);
					}

				} else
				{
					shtPtr+= (2*shtPtr[1])+2;
				}
			}

			// build reverse lookups
			for (i=0; i<(int)mStructs.size(); i++)
			{
				short *strc = mStructs.at(i);
				mStructReverse.insert(strc[0], i);
				mTypeLookup.insert(btHashString(mTypes[strc[0]]),i);
			}
		}

public:

	btHashMap<btHashPtr,void*> m_skipPointers;

		btDefaultSerializer(int totalSize=0, unsigned char*	buffer=0)
			:m_uniqueIdGenerator(0),
			m_totalSize(totalSize),
			m_currentSize(0),
			m_dna(0),
			m_dnaLength(0),
			m_serializationFlags(0)
		{
		    if (buffer==0)
            {
                m_buffer = m_totalSize?(unsigned char*)btAlignedAlloc(totalSize,16):0;
                m_ownsBuffer = true;
            } else
            {
                m_buffer = buffer;
                m_ownsBuffer = false;
            }

			const bool VOID_IS_8 = ((sizeof(void*)==8));

#ifdef BT_INTERNAL_UPDATE_SERIALIZATION_STRUCTURES
			if (VOID_IS_8)
			{
#if _WIN64
				initDNA((const char*)sBulletDNAstr64,sBulletDNAlen64);
#else
				btAssert(0);
#endif
			} else
			{
#ifndef _WIN64
				initDNA((const char*)sBulletDNAstr,sBulletDNAlen);
#else
				btAssert(0);
#endif
			}

#else //BT_INTERNAL_UPDATE_SERIALIZATION_STRUCTURES
			if (VOID_IS_8)
			{
				initDNA((const char*)sBulletDNAstr64,sBulletDNAlen64);
			} else
			{
				initDNA((const char*)sBulletDNAstr,sBulletDNAlen);
			}
#endif //BT_INTERNAL_UPDATE_SERIALIZATION_STRUCTURES

		}

		virtual ~btDefaultSerializer()
		{
			if (m_buffer && m_ownsBuffer)
				btAlignedFree(m_buffer);
			if (m_dna)
				btAlignedFree(m_dna);
		}

		static int getMemoryDnaSizeInBytes()
		{
			const bool VOID_IS_8 = ((sizeof(void*) == 8));

			if (VOID_IS_8)
			{
				return sBulletDNAlen64;
			}
			return sBulletDNAlen;
		}
		static const char* getMemoryDna()
		{
			const bool VOID_IS_8 = ((sizeof(void*) == 8));
			if (VOID_IS_8)
			{
				return (const char*)sBulletDNAstr64;
			}
			return (const char*)sBulletDNAstr;
		}

		void	insertHeader()
		{
			writeHeader(m_buffer);
			m_currentSize += BT_HEADER_LENGTH;
		}

		void	writeHeader(unsigned char* buffer) const
		{

#ifdef  BT_USE_DOUBLE_PRECISION
			memcpy(buffer, "BULLETd", 7);
#else
			memcpy(buffer, "BULLETf", 7);
#endif //BT_USE_DOUBLE_PRECISION

			int littleEndian= 1;
			littleEndian= ((char*)&littleEndian)[0];

			if (sizeof(void*)==8)
			{
				buffer[7] = '-';
			} else
			{
				buffer[7] = '_';
			}

			if (littleEndian)
			{
				buffer[8]='v';
			} else
			{
				buffer[8]='V';
			}

			buffer[9] = '2';
			buffer[10] = '8';
			buffer[11] = '7';

		}

		virtual	void	startSerialization()
		{
			m_uniqueIdGenerator= 1;
			if (m_totalSize)
			{
				unsigned char* buffer = internalAlloc(BT_HEADER_LENGTH);
				writeHeader(buffer);
			}

		}

		virtual	void	finishSerialization()
		{
			writeDNA();

			//if we didn't pre-allocate a buffer, we need to create a contiguous buffer now
			int mysize = 0;
			if (!m_totalSize)
			{
				if (m_buffer)
					btAlignedFree(m_buffer);

				m_currentSize += BT_HEADER_LENGTH;
				m_buffer = (unsigned char*)btAlignedAlloc(m_currentSize,16);

				unsigned char* currentPtr = m_buffer;
				writeHeader(m_buffer);
				currentPtr += BT_HEADER_LENGTH;
				mysize+=BT_HEADER_LENGTH;
				for (int i=0;i<	m_chunkPtrs.size();i++)
				{
					int curLength = sizeof(btChunk)+m_chunkPtrs[i]->m_length;
					memcpy(currentPtr,m_chunkPtrs[i], curLength);
					btAlignedFree(m_chunkPtrs[i]);
					currentPtr+=curLength;
					mysize+=curLength;
				}
			}

			mTypes.clear();
			mStructs.clear();
			mTlens.clear();
			mStructReverse.clear();
			mTypeLookup.clear();
			m_skipPointers.clear();
			m_chunkP.clear();
			m_nameMap.clear();
			m_uniquePointers.clear();
			m_chunkPtrs.clear();
		}

		virtual	void*	getUniquePointer(void*oldPtr)
		{
			btAssert(m_uniqueIdGenerator >= 0);
			if (!oldPtr)
				return 0;

			btPointerUid* uptr = (btPointerUid*)m_uniquePointers.find(oldPtr);
			if (uptr)
			{
				return uptr->m_ptr;
			}

			void** ptr2 = m_skipPointers[oldPtr];
            if (ptr2)
			{
				return 0;
			}

			m_uniqueIdGenerator++;

			btPointerUid uid;
			uid.m_uniqueIds[0] = m_uniqueIdGenerator;
			uid.m_uniqueIds[1] = m_uniqueIdGenerator;
			m_uniquePointers.insert(oldPtr,uid);
			return uid.m_ptr;

		}

		virtual	const unsigned char*		getBufferPointer() const
		{
			return m_buffer;
		}

		virtual	int					getCurrentBufferSize() const
		{
			return	m_currentSize;
		}

		virtual	void	finalizeChunk(btChunk* chunk, const char* structType, int chunkCode,void* oldPtr)
		{
			if (!(m_serializationFlags&BT_SERIALIZE_NO_DUPLICATE_ASSERT))
			{
				btAssert(!findPointer(oldPtr));
			}

			chunk->m_dna_nr = getReverseType(structType);

			chunk->m_chunkCode = chunkCode;

			void* uniquePtr = getUniquePointer(oldPtr);

			m_chunkP.insert(oldPtr,uniquePtr);//chunk->m_oldPtr);
			chunk->m_oldPtr = uniquePtr;//oldPtr;

		}

		virtual unsigned char* internalAlloc(size_t size)
		{
			unsigned char* ptr = 0;

			if (m_totalSize)
			{
				ptr = m_buffer+m_currentSize;
				m_currentSize += int(size);
				btAssert(m_currentSize<m_totalSize);
			} else
			{
				ptr = (unsigned char*)btAlignedAlloc(size,16);
				m_currentSize += int(size);
			}
			return ptr;
		}

		virtual	btChunk*	allocate(size_t size, int numElements)
		{

			unsigned char* ptr = internalAlloc(int(size)*numElements+sizeof(btChunk));

			unsigned char* data = ptr + sizeof(btChunk);

			btChunk* chunk = (btChunk*)ptr;
			chunk->m_chunkCode = 0;
			chunk->m_oldPtr = data;
			chunk->m_length = int(size)*numElements;
			chunk->m_number = numElements;

			m_chunkPtrs.push_back(chunk);

			return chunk;
		}

		virtual	const char*	findNameForPointer(const void* ptr) const
		{
			const char*const * namePtr = m_nameMap.find(ptr);
			if (namePtr && *namePtr)
				return *namePtr;
			return 0;

		}

		virtual	void	registerNameForPointer(const void* ptr, const char* name)
		{
			m_nameMap.insert(ptr,name);
		}

		virtual void	serializeName(const char* name)
		{
			if (name)
			{
				//don't serialize name twice
				if (findPointer((void*)name))
					return;

				int len = btStrLen(name);
				if (len)
				{

					int newLen = len+1;
					int padding = ((newLen+3)&~3)-newLen;
					newLen += padding;

					//serialize name string now
					btChunk* chunk = allocate(sizeof(char),newLen);
					char* destinationName = (char*)chunk->m_oldPtr;
					for (int i=0;i<len;i++)
					{
						destinationName[i] = name[i];
					}
					destinationName[len] = 0;
					finalizeChunk(chunk,"char",BT_ARRAY_CODE,(void*)name);
				}
			}
		}

		virtual int		getSerializationFlags() const
		{
			return m_serializationFlags;
		}

		virtual void	setSerializationFlags(int flags)
		{
			m_serializationFlags = flags;
		}
		int getNumChunks() const
		{
			return m_chunkPtrs.size();
		}

		const btChunk* getChunk(int chunkIndex) const
		{
			return m_chunkPtrs[chunkIndex];
		}
};

///In general it is best to use btDefaultSerializer,
///in particular when writing the data to disk or sending it over the network.
///The btInMemorySerializer is experimental and only suitable in a few cases.
///The btInMemorySerializer takes a shortcut and can be useful to create a deep-copy
///of objects. There will be a demo on how to use the btInMemorySerializer.
#ifdef ENABLE_INMEMORY_SERIALIZER

struct btInMemorySerializer : public btDefaultSerializer
{
    btHashMap<btHashPtr,btChunk*> m_uid2ChunkPtr;
    btHashMap<btHashPtr,void*> m_orgPtr2UniqueDataPtr;
    btHashMap<btHashString,const void*> m_names2Ptr;

    btBulletSerializedArrays    m_arrays;

    btInMemorySerializer(int totalSize=0, unsigned char*	buffer=0)
    :btDefaultSerializer(totalSize,buffer)
    {

    }

    virtual void startSerialization()
    {
        m_uid2ChunkPtr.clear();
        //todo: m_arrays.clear();
        btDefaultSerializer::startSerialization();
    }

    btChunk* findChunkFromUniquePointer(void* uniquePointer)
    {
        btChunk** chkPtr = m_uid2ChunkPtr[uniquePointer];
        if (chkPtr)
        {
            return *chkPtr;
        }
        return 0;
    }

	virtual	void	registerNameForPointer(const void* ptr, const char* name)
    {
       btDefaultSerializer::registerNameForPointer(ptr,name);
       m_names2Ptr.insert(name,ptr);
    }

    virtual void finishSerialization()
    {
    }

    virtual void* getUniquePointer(void*oldPtr)
    {
        if (oldPtr==0)
            return 0;

        // void* uniquePtr = getUniquePointer(oldPtr);
        btChunk* chunk = findChunkFromUniquePointer(oldPtr);
        if (chunk)
        {
            return chunk->m_oldPtr;
        } else
        {
            const char* n = (const char*) oldPtr;
            const void** ptr = m_names2Ptr[n];
            if (ptr)
            {
                return oldPtr;
            } else
            {
            		void** ptr2 = m_skipPointers[oldPtr];
            		if (ptr2)
								{
									return 0;
								} else
								{
									//If this assert hit, serialization happened in the wrong order
									// 'getUniquePointer'
									btAssert(0);
								}

            }
            return 0;
        }
				return oldPtr;
    }

    virtual void finalizeChunk(btChunk* chunk, const char* structType, int chunkCode,void* oldPtr)
    {
        if (!(m_serializationFlags&BT_SERIALIZE_NO_DUPLICATE_ASSERT))
        {
            btAssert(!findPointer(oldPtr));
        }

        chunk->m_dna_nr = getReverseType(structType);
        chunk->m_chunkCode = chunkCode;
        //void* uniquePtr = getUniquePointer(oldPtr);
        m_chunkP.insert(oldPtr,oldPtr);//chunk->m_oldPtr);
        // chunk->m_oldPtr = uniquePtr;//oldPtr;

        void* uid = findPointer(oldPtr);
        m_uid2ChunkPtr.insert(uid,chunk);

        switch (chunk->m_chunkCode)
			{
			case BT_SOFTBODY_CODE:
			{
	#ifdef BT_USE_DOUBLE_PRECISION
					m_arrays.m_softBodyDoubleData.push_back((btSoftBodyDoubleData*) chunk->m_oldPtr);
	#else
					m_arrays.m_softBodyFloatData.push_back((btSoftBodyFloatData*) chunk->m_oldPtr);
	#endif
					break;
				}
			case BT_COLLISIONOBJECT_CODE:
				{
	#ifdef BT_USE_DOUBLE_PRECISION
					m_arrays.m_collisionObjectDataDouble.push_back((btCollisionObjectDoubleData*)chunk->m_oldPtr);
	#else//BT_USE_DOUBLE_PRECISION
					m_arrays.m_collisionObjectDataFloat.push_back((btCollisionObjectFloatData*)chunk->m_oldPtr);
	#endif //BT_USE_DOUBLE_PRECISION
					break;
				}
			case BT_RIGIDBODY_CODE:
				{
	#ifdef BT_USE_DOUBLE_PRECISION
					m_arrays.m_rigidBodyDataDouble.push_back((btRigidBodyDoubleData*)chunk->m_oldPtr);
	#else
					m_arrays.m_rigidBodyDataFloat.push_back((btRigidBodyFloatData*)chunk->m_oldPtr);
	#endif//BT_USE_DOUBLE_PRECISION
					break;
				};
			case BT_CONSTRAINT_CODE:
				{
	#ifdef BT_USE_DOUBLE_PRECISION
					m_arrays.m_constraintDataDouble.push_back((btTypedConstraintDoubleData*)chunk->m_oldPtr);
	#else
					m_arrays.m_constraintDataFloat.push_back((btTypedConstraintFloatData*)chunk->m_oldPtr);
	#endif
					break;
				}
			case BT_QUANTIZED_BVH_CODE:
				{
	#ifdef BT_USE_DOUBLE_PRECISION
					m_arrays.m_bvhsDouble.push_back((btQuantizedBvhDoubleData*) chunk->m_oldPtr);
	#else
					m_arrays.m_bvhsFloat.push_back((btQuantizedBvhFloatData*) chunk->m_oldPtr);
	#endif
					break;
				}

			case BT_SHAPE_CODE:
				{
					btCollisionShapeData* shapeData = (btCollisionShapeData*) chunk->m_oldPtr;
					m_arrays.m_colShapeData.push_back(shapeData);
					break;
				}
			case BT_TRIANLGE_INFO_MAP:
			case BT_ARRAY_CODE:
			case BT_SBMATERIAL_CODE:
			case BT_SBNODE_CODE:
			case BT_DYNAMICSWORLD_CODE:
			case BT_DNA_CODE:
				{
					break;
				}
			default:
				{
				}
			};
    }

    int getNumChunks() const
    {
        return m_uid2ChunkPtr.size();
    }

    const btChunk* getChunk(int chunkIndex) const
    {
        return *m_uid2ChunkPtr.getAtIndex(chunkIndex);
    }

};
#endif //ENABLE_INMEMORY_SERIALIZER

#endif //BT_SERIALIZER_H


text:
/*
Bullet Continuous Collision Detection and Physics Library
Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

#ifndef BT_QUANTIZED_BVH_H
#define BT_QUANTIZED_BVH_H

class btSerializer;

//#define DEBUG_CHECK_DEQUANTIZATION 1
#ifdef DEBUG_CHECK_DEQUANTIZATION
#ifdef __SPU__
#define printf spu_printf
#endif //__SPU__

#include <stdio.h>
#include <stdlib.h>
#endif //DEBUG_CHECK_DEQUANTIZATION

#include "LinearMath/btVector3.h"
#include "LinearMath/btAlignedAllocator.h"

#ifdef BT_USE_DOUBLE_PRECISION
#define btQuantizedBvhData btQuantizedBvhDoubleData
#define btOptimizedBvhNodeData btOptimizedBvhNodeDoubleData
#define btQuantizedBvhDataName "btQuantizedBvhDoubleData"
#else
#define btQuantizedBvhData btQuantizedBvhFloatData
#define btOptimizedBvhNodeData btOptimizedBvhNodeFloatData
#define btQuantizedBvhDataName "btQuantizedBvhFloatData"
#endif

//http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang/html/vclrf__m128.asp

//Note: currently we have 16 bytes per quantized node
#define MAX_SUBTREE_SIZE_IN_BYTES  2048

// 10 gives the potential for 1024 parts, with at most 2^21 (2097152) (minus one
// actually) triangles each (since the sign bit is reserved
#define MAX_NUM_PARTS_IN_BITS 10

///btQuantizedBvhNode is a compressed aabb node, 16 bytes.
///Node can be used for leafnode or internal node. Leafnodes can point to 32-bit triangle index (non-negative range).
ATTRIBUTE_ALIGNED16	(struct) btQuantizedBvhNode
{
	BT_DECLARE_ALIGNED_ALLOCATOR();

	//12 bytes
	unsigned short int	m_quantizedAabbMin[3];
	unsigned short int	m_quantizedAabbMax[3];
	//4 bytes
	int	m_escapeIndexOrTriangleIndex;

	bool isLeafNode() const
	{
		//skipindex is negative (internal node), triangleindex >=0 (leafnode)
		return (m_escapeIndexOrTriangleIndex >= 0);
	}
	int getEscapeIndex() const
	{
		btAssert(!isLeafNode());
		return -m_escapeIndexOrTriangleIndex;
	}
	int	getTriangleIndex() const
	{
		btAssert(isLeafNode());
		unsigned int x=0;
		unsigned int y = (~(x&0))<<(31-MAX_NUM_PARTS_IN_BITS);
		// Get only the lower bits where the triangle index is stored
		return (m_escapeIndexOrTriangleIndex&~(y));
	}
	int	getPartId() const
	{
		btAssert(isLeafNode());
		// Get only the highest bits where the part index is stored
		return (m_escapeIndexOrTriangleIndex>>(31-MAX_NUM_PARTS_IN_BITS));
	}
}
;

/// btOptimizedBvhNode contains both internal and leaf node information.
/// Total node size is 44 bytes / node. You can use the compressed version of 16 bytes.
ATTRIBUTE_ALIGNED16 (struct) btOptimizedBvhNode
{
	BT_DECLARE_ALIGNED_ALLOCATOR();

	//32 bytes
	btVector3	m_aabbMinOrg;
	btVector3	m_aabbMaxOrg;

	//4
	int	m_escapeIndex;

	//8
	//for child nodes
	int	m_subPart;
	int	m_triangleIndex;

//pad the size to 64 bytes
	char	m_padding[20];
};

///btBvhSubtreeInfo provides info to gather a subtree of limited size
ATTRIBUTE_ALIGNED16(class) btBvhSubtreeInfo
{
public:
	BT_DECLARE_ALIGNED_ALLOCATOR();

	//12 bytes
	unsigned short int	m_quantizedAabbMin[3];
	unsigned short int	m_quantizedAabbMax[3];
	//4 bytes, points to the root of the subtree
	int			m_rootNodeIndex;
	//4 bytes
	int			m_subtreeSize;
	int			m_padding[3];

	btBvhSubtreeInfo()
	{
		//memset(&m_padding[0], 0, sizeof(m_padding));
	}

	void	setAabbFromQuantizeNode(const btQuantizedBvhNode& quantizedNode)
	{
		m_quantizedAabbMin[0] = quantizedNode.m_quantizedAabbMin[0];
		m_quantizedAabbMin[1] = quantizedNode.m_quantizedAabbMin[1];
		m_quantizedAabbMin[2] = quantizedNode.m_quantizedAabbMin[2];
		m_quantizedAabbMax[0] = quantizedNode.m_quantizedAabbMax[0];
		m_quantizedAabbMax[1] = quantizedNode.m_quantizedAabbMax[1];
		m_quantizedAabbMax[2] = quantizedNode.m_quantizedAabbMax[2];
	}
}
;

class btNodeOverlapCallback
{
public:
	virtual ~btNodeOverlapCallback() {};

	virtual void processNode(int subPart, int triangleIndex) = 0;
};

#include "LinearMath/btAlignedAllocator.h"
#include "LinearMath/btAlignedObjectArray.h"

///for code readability:
typedef btAlignedObjectArray<btOptimizedBvhNode>	NodeArray;
typedef btAlignedObjectArray<btQuantizedBvhNode>	QuantizedNodeArray;
typedef btAlignedObjectArray<btBvhSubtreeInfo>		BvhSubtreeInfoArray;

///The btQuantizedBvh class stores an AABB tree that can be quickly traversed on CPU and Cell SPU.
///It is used by the btBvhTriangleMeshShape as midphase.
///It is recommended to use quantization for better performance and lower memory requirements.
ATTRIBUTE_ALIGNED16(class) btQuantizedBvh
{
public:
	enum btTraversalMode
	{
		TRAVERSAL_STACKLESS = 0,
		TRAVERSAL_STACKLESS_CACHE_FRIENDLY,
		TRAVERSAL_RECURSIVE
	};

protected:

	btVector3			m_bvhAabbMin;
	btVector3			m_bvhAabbMax;
	btVector3			m_bvhQuantization;

	int					m_bulletVersion;	//for serialization versioning. It could also be used to detect endianess.

	int					m_curNodeIndex;
	//quantization data
	bool				m_useQuantization;

	NodeArray			m_leafNodes;
	NodeArray			m_contiguousNodes;
	QuantizedNodeArray	m_quantizedLeafNodes;
	QuantizedNodeArray	m_quantizedContiguousNodes;

	btTraversalMode	m_traversalMode;
	BvhSubtreeInfoArray		m_SubtreeHeaders;

	//This is only used for serialization so we don't have to add serialization directly to btAlignedObjectArray
	mutable int m_subtreeHeaderCount;

	///two versions, one for quantized and normal nodes. This allows code-reuse while maintaining readability (no template/macro!)
	///this might be refactored into a virtual, it is usually not calculated at run-time
	void	setInternalNodeAabbMin(int nodeIndex, const btVector3& aabbMin)
	{
		if (m_useQuantization)
		{
			quantize(&m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMin[0] ,aabbMin,0);
		} else
		{
			m_contiguousNodes[nodeIndex].m_aabbMinOrg = aabbMin;

		}
	}
	void	setInternalNodeAabbMax(int nodeIndex,const btVector3& aabbMax)
	{
		if (m_useQuantization)
		{
			quantize(&m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMax[0],aabbMax,1);
		} else
		{
			m_contiguousNodes[nodeIndex].m_aabbMaxOrg = aabbMax;
		}
	}

	btVector3 getAabbMin(int nodeIndex) const
	{
		if (m_useQuantization)
		{
			return unQuantize(&m_quantizedLeafNodes[nodeIndex].m_quantizedAabbMin[0]);
		}
		//non-quantized
		return m_leafNodes[nodeIndex].m_aabbMinOrg;

	}
	btVector3 getAabbMax(int nodeIndex) const
	{
		if (m_useQuantization)
		{
			return unQuantize(&m_quantizedLeafNodes[nodeIndex].m_quantizedAabbMax[0]);
		}
		//non-quantized
		return m_leafNodes[nodeIndex].m_aabbMaxOrg;

	}

	void	setInternalNodeEscapeIndex(int nodeIndex, int escapeIndex)
	{
		if (m_useQuantization)
		{
			m_quantizedContiguousNodes[nodeIndex].m_escapeIndexOrTriangleIndex = -escapeIndex;
		}
		else
		{
			m_contiguousNodes[nodeIndex].m_escapeIndex = escapeIndex;
		}

	}

	void mergeInternalNodeAabb(int nodeIndex,const btVector3& newAabbMin,const btVector3& newAabbMax)
	{
		if (m_useQuantization)
		{
			unsigned short int quantizedAabbMin[3];
			unsigned short int quantizedAabbMax[3];
			quantize(quantizedAabbMin,newAabbMin,0);
			quantize(quantizedAabbMax,newAabbMax,1);
			for (int i=0;i<3;i++)
			{
				if (m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMin[i] > quantizedAabbMin[i])
					m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMin[i] = quantizedAabbMin[i];

				if (m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMax[i] < quantizedAabbMax[i])
					m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMax[i] = quantizedAabbMax[i];

			}
		} else
		{
			//non-quantized
			m_contiguousNodes[nodeIndex].m_aabbMinOrg.setMin(newAabbMin);
			m_contiguousNodes[nodeIndex].m_aabbMaxOrg.setMax(newAabbMax);
		}
	}

	void	swapLeafNodes(int firstIndex,int secondIndex);

	void	assignInternalNodeFromLeafNode(int internalNode,int leafNodeIndex);

protected:

	void	buildTree	(int startIndex,int endIndex);

	int	calcSplittingAxis(int startIndex,int endIndex);

	int	sortAndCalcSplittingIndex(int startIndex,int endIndex,int splitAxis);

	void	walkStacklessTree(btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const;

	void	walkStacklessQuantizedTreeAgainstRay(btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget, const btVector3& aabbMin, const btVector3& aabbMax, int startNodeIndex,int endNodeIndex) const;
	void	walkStacklessQuantizedTree(btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax,int startNodeIndex,int endNodeIndex) const;
	void	walkStacklessTreeAgainstRay(btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget, const btVector3& aabbMin, const btVector3& aabbMax, int startNodeIndex,int endNodeIndex) const;

	///tree traversal designed for small-memory processors like PS3 SPU
	void	walkStacklessQuantizedTreeCacheFriendly(btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax) const;

	///use the 16-byte stackless 'skipindex' node tree to do a recursive traversal
	void	walkRecursiveQuantizedTreeAgainstQueryAabb(const btQuantizedBvhNode* currentNode,btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax) const;

	///use the 16-byte stackless 'skipindex' node tree to do a recursive traversal
	void	walkRecursiveQuantizedTreeAgainstQuantizedTree(const btQuantizedBvhNode* treeNodeA,const btQuantizedBvhNode* treeNodeB,btNodeOverlapCallback* nodeCallback) const;

	void	updateSubtreeHeaders(int leftChildNodexIndex,int rightChildNodexIndex);

public:

	BT_DECLARE_ALIGNED_ALLOCATOR();

	btQuantizedBvh();

	virtual ~btQuantizedBvh();

	///***************************************** expert/internal use only *************************
	void	setQuantizationValues(const btVector3& bvhAabbMin,const btVector3& bvhAabbMax,btScalar quantizationMargin=btScalar(1.0));
	QuantizedNodeArray&	getLeafNodeArray() {			return	m_quantizedLeafNodes;	}
	///buildInternal is expert use only: assumes that setQuantizationValues and LeafNodeArray are initialized
	void	buildInternal();
	///***************************************** expert/internal use only *************************

	void	reportAabbOverlappingNodex(btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const;
	void	reportRayOverlappingNodex (btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget) const;
	void	reportBoxCastOverlappingNodex(btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget, const btVector3& aabbMin,const btVector3& aabbMax) const;

		SIMD_FORCE_INLINE void quantize(unsigned short* out, const btVector3& point,int isMax) const
	{

		btAssert(m_useQuantization);

		btAssert(point.getX() <= m_bvhAabbMax.getX());
		btAssert(point.getY() <= m_bvhAabbMax.getY());
		btAssert(point.getZ() <= m_bvhAabbMax.getZ());

		btAssert(point.getX() >= m_bvhAabbMin.getX());
		btAssert(point.getY() >= m_bvhAabbMin.getY());
		btAssert(point.getZ() >= m_bvhAabbMin.getZ());

		btVector3 v = (point - m_bvhAabbMin) * m_bvhQuantization;
		///Make sure rounding is done in a way that unQuantize(quantizeWithClamp(...)) is conservative
		///end-points always set the first bit, so that they are sorted properly (so that neighbouring AABBs overlap properly)
		///@todo: double-check this
		if (isMax)
		{
			out[0] = (unsigned short) (((unsigned short)(v.getX()+btScalar(1.)) | 1));
			out[1] = (unsigned short) (((unsigned short)(v.getY()+btScalar(1.)) | 1));
			out[2] = (unsigned short) (((unsigned short)(v.getZ()+btScalar(1.)) | 1));
		} else
		{
			out[0] = (unsigned short) (((unsigned short)(v.getX()) & 0xfffe));
			out[1] = (unsigned short) (((unsigned short)(v.getY()) & 0xfffe));
			out[2] = (unsigned short) (((unsigned short)(v.getZ()) & 0xfffe));
		}

#ifdef DEBUG_CHECK_DEQUANTIZATION
		btVector3 newPoint = unQuantize(out);
		if (isMax)
		{
			if (newPoint.getX() < point.getX())
			{
				printf("unconservative X, diffX = %f, oldX=%f,newX=%f\n",newPoint.getX()-point.getX(), newPoint.getX(),point.getX());
			}
			if (newPoint.getY() < point.getY())
			{
				printf("unconservative Y, diffY = %f, oldY=%f,newY=%f\n",newPoint.getY()-point.getY(), newPoint.getY(),point.getY());
			}
			if (newPoint.getZ() < point.getZ())
			{

				printf("unconservative Z, diffZ = %f, oldZ=%f,newZ=%f\n",newPoint.getZ()-point.getZ(), newPoint.getZ(),point.getZ());
			}
		} else
		{
			if (newPoint.getX() > point.getX())
			{
				printf("unconservative X, diffX = %f, oldX=%f,newX=%f\n",newPoint.getX()-point.getX(), newPoint.getX(),point.getX());
			}
			if (newPoint.getY() > point.getY())
			{
				printf("unconservative Y, diffY = %f, oldY=%f,newY=%f\n",newPoint.getY()-point.getY(), newPoint.getY(),point.getY());
			}
			if (newPoint.getZ() > point.getZ())
			{
				printf("unconservative Z, diffZ = %f, oldZ=%f,newZ=%f\n",newPoint.getZ()-point.getZ(), newPoint.getZ(),point.getZ());
			}
		}
#endif //DEBUG_CHECK_DEQUANTIZATION

	}

	SIMD_FORCE_INLINE void quantizeWithClamp(unsigned short* out, const btVector3& point2,int isMax) const
	{

		btAssert(m_useQuantization);

		btVector3 clampedPoint(point2);
		clampedPoint.setMax(m_bvhAabbMin);
		clampedPoint.setMin(m_bvhAabbMax);

		quantize(out,clampedPoint,isMax);

	}

	SIMD_FORCE_INLINE btVector3	unQuantize(const unsigned short* vecIn) const
	{
			btVector3	vecOut;
			vecOut.setValue(
			(btScalar)(vecIn[0]) / (m_bvhQuantization.getX()),
			(btScalar)(vecIn[1]) / (m_bvhQuantization.getY()),
			(btScalar)(vecIn[2]) / (m_bvhQuantization.getZ()));
			vecOut += m_bvhAabbMin;
			return vecOut;
	}

	///setTraversalMode let's you choose between stackless, recursive or stackless cache friendly tree traversal. Note this is only implemented for quantized trees.
	void	setTraversalMode(btTraversalMode	traversalMode)
	{
		m_traversalMode = traversalMode;
	}

	SIMD_FORCE_INLINE QuantizedNodeArray&	getQuantizedNodeArray()
	{
		return	m_quantizedContiguousNodes;
	}

	SIMD_FORCE_INLINE BvhSubtreeInfoArray&	getSubtreeInfoArray()
	{
		return m_SubtreeHeaders;
	}

////////////////////////////////////////////////////////////////////

	/////Calculate space needed to store BVH for serialization
	unsigned calculateSerializeBufferSize() const;

	/// Data buffer MUST be 16 byte aligned
	virtual bool serialize(void *o_alignedDataBuffer, unsigned i_dataBufferSize, bool i_swapEndian) const;

	///deSerializeInPlace loads and initializes a BVH from a buffer in memory 'in place'
	static btQuantizedBvh *deSerializeInPlace(void *i_alignedDataBuffer, unsigned int i_dataBufferSize, bool i_swapEndian);

	static unsigned int getAlignmentSerializationPadding();
//////////////////////////////////////////////////////////////////////

	virtual	int	calculateSerializeBufferSizeNew() const;

	///fills the dataBuffer and returns the struct name (and 0 on failure)
	virtual	const char*	serialize(void* dataBuffer, btSerializer* serializer) const;

	virtual	void deSerializeFloat(struct btQuantizedBvhFloatData& quantizedBvhFloatData);

	virtual	void deSerializeDouble(struct btQuantizedBvhDoubleData& quantizedBvhDoubleData);

////////////////////////////////////////////////////////////////////

	SIMD_FORCE_INLINE bool isQuantized()
	{
		return m_useQuantization;
	}

private:
	// Special "copy" constructor that allows for in-place deserialization
	// Prevents btVector3's default constructor from being called, but doesn't inialize much else
	// ownsMemory should most likely be false if deserializing, and if you are not, don't call this (it also changes the function signature, which we need)
	btQuantizedBvh(btQuantizedBvh &other, bool ownsMemory);

}
;

struct	btBvhSubtreeInfoData
{
	int			m_rootNodeIndex;
	int			m_subtreeSize;
	unsigned short m_quantizedAabbMin[3];
	unsigned short m_quantizedAabbMax[3];
};

struct btOptimizedBvhNodeFloatData
{
	btVector3FloatData	m_aabbMinOrg;
	btVector3FloatData	m_aabbMaxOrg;
	int	m_escapeIndex;
	int	m_subPart;
	int	m_triangleIndex;
	char m_pad[4];
};

struct btOptimizedBvhNodeDoubleData
{
	btVector3DoubleData	m_aabbMinOrg;
	btVector3DoubleData	m_aabbMaxOrg;
	int	m_escapeIndex;
	int	m_subPart;
	int	m_triangleIndex;
	char	m_pad[4];
};

struct btQuantizedBvhNodeData
{
	unsigned short m_quantizedAabbMin[3];
	unsigned short m_quantizedAabbMax[3];
	int	m_escapeIndexOrTriangleIndex;
};

struct	btQuantizedBvhFloatData
{
	btVector3FloatData			m_bvhAabbMin;
	btVector3FloatData			m_bvhAabbMax;
	btVector3FloatData			m_bvhQuantization;
	int					m_curNodeIndex;
	int					m_useQuantization;
	int					m_numContiguousLeafNodes;
	int					m_numQuantizedContiguousNodes;
	btOptimizedBvhNodeFloatData	*m_contiguousNodesPtr;
	btQuantizedBvhNodeData		*m_quantizedContiguousNodesPtr;
	btBvhSubtreeInfoData	*m_subTreeInfoPtr;
	int					m_traversalMode;
	int					m_numSubtreeHeaders;

};

struct	btQuantizedBvhDoubleData
{
	btVector3DoubleData			m_bvhAabbMin;
	btVector3DoubleData			m_bvhAabbMax;
	btVector3DoubleData			m_bvhQuantization;
	int							m_curNodeIndex;
	int							m_useQuantization;
	int							m_numContiguousLeafNodes;
	int							m_numQuantizedContiguousNodes;
	btOptimizedBvhNodeDoubleData	*m_contiguousNodesPtr;
	btQuantizedBvhNodeData			*m_quantizedContiguousNodesPtr;

	int							m_traversalMode;
	int							m_numSubtreeHeaders;
	btBvhSubtreeInfoData		*m_subTreeInfoPtr;
};

SIMD_FORCE_INLINE	int	btQuantizedBvh::calculateSerializeBufferSizeNew() const
{
	return sizeof(btQuantizedBvhData);
}

#endif //BT_QUANTIZED_BVH_H


text:
/*
Bullet Continuous Collision Detection and Physics Library
Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

#ifndef BT_SIMPLE_BROADPHASE_H
#define BT_SIMPLE_BROADPHASE_H

#include "btOverlappingPairCache.h"

struct btSimpleBroadphaseProxy : public btBroadphaseProxy
{
	int			m_nextFree;

//	int			m_handleId;

	btSimpleBroadphaseProxy() {};

	btSimpleBroadphaseProxy(const btVector3& minpt,const btVector3& maxpt,int shapeType,void* userPtr, int collisionFilterGroup, int collisionFilterMask)
	:btBroadphaseProxy(minpt,maxpt,userPtr,collisionFilterGroup,collisionFilterMask)
	{
		(void)shapeType;
	}

	SIMD_FORCE_INLINE void SetNextFree(int next) {m_nextFree = next;}
	SIMD_FORCE_INLINE int GetNextFree() const {return m_nextFree;}

};

///The SimpleBroadphase is just a unit-test for btAxisSweep3, bt32BitAxisSweep3, or btDbvtBroadphase, so use those classes instead.
///It is a brute force aabb culling broadphase based on O(n^2) aabb checks
class btSimpleBroadphase : public btBroadphaseInterface
{

protected:

	int		m_numHandles;						// number of active handles
	int		m_maxHandles;						// max number of handles
	int		m_LastHandleIndex;

	btSimpleBroadphaseProxy* m_pHandles;						// handles pool

	void* m_pHandlesRawPtr;
	int		m_firstFreeHandle;		// free handles list

	int allocHandle()
	{
		btAssert(m_numHandles < m_maxHandles);
		int freeHandle = m_firstFreeHandle;
		m_firstFreeHandle = m_pHandles[freeHandle].GetNextFree();
		m_numHandles++;
		if(freeHandle > m_LastHandleIndex)
		{
			m_LastHandleIndex = freeHandle;
		}
		return freeHandle;
	}

	void freeHandle(btSimpleBroadphaseProxy* proxy)
	{
		int handle = int(proxy-m_pHandles);
		btAssert(handle >= 0 && handle < m_maxHandles);
		if(handle == m_LastHandleIndex)
		{
			m_LastHandleIndex--;
		}
		proxy->SetNextFree(m_firstFreeHandle);
		m_firstFreeHandle = handle;

		proxy->m_clientObject = 0;

		m_numHandles--;
	}

	btOverlappingPairCache*	m_pairCache;
	bool	m_ownsPairCache;

	int	m_invalidPair;

	inline btSimpleBroadphaseProxy*	getSimpleProxyFromProxy(btBroadphaseProxy* proxy)
	{
		btSimpleBroadphaseProxy* proxy0 = static_cast<btSimpleBroadphaseProxy*>(proxy);
		return proxy0;
	}

	inline const btSimpleBroadphaseProxy*	getSimpleProxyFromProxy(btBroadphaseProxy* proxy) const
	{
		const btSimpleBroadphaseProxy* proxy0 = static_cast<const btSimpleBroadphaseProxy*>(proxy);
		return proxy0;
	}

	///reset broadphase internal structures, to ensure determinism/reproducability
	virtual void resetPool(btDispatcher* dispatcher);

	void	validate();

protected:

public:
	btSimpleBroadphase(int maxProxies=16384,btOverlappingPairCache* overlappingPairCache=0);
	virtual ~btSimpleBroadphase();

		static bool	aabbOverlap(btSimpleBroadphaseProxy* proxy0,btSimpleBroadphaseProxy* proxy1);

	virtual btBroadphaseProxy*	createProxy(  const btVector3& aabbMin,  const btVector3& aabbMax,int shapeType,void* userPtr , int collisionFilterGroup, int collisionFilterMask, btDispatcher* dispatcher);

	virtual void	calculateOverlappingPairs(btDispatcher* dispatcher);

	virtual void	destroyProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
	virtual void	setAabb(btBroadphaseProxy* proxy,const btVector3& aabbMin,const btVector3& aabbMax, btDispatcher* dispatcher);
	virtual void	getAabb(btBroadphaseProxy* proxy,btVector3& aabbMin, btVector3& aabbMax ) const;

	virtual void	rayTest(const btVector3& rayFrom,const btVector3& rayTo, btBroadphaseRayCallback& rayCallback, const btVector3& aabbMin=btVector3(0,0,0),const btVector3& aabbMax=btVector3(0,0,0));
	virtual void	aabbTest(const btVector3& aabbMin, const btVector3& aabbMax, btBroadphaseAabbCallback& callback);

	btOverlappingPairCache*	getOverlappingPairCache()
	{
		return m_pairCache;
	}
	const btOverlappingPairCache*	getOverlappingPairCache() const
	{
		return m_pairCache;
	}

	bool	testAabbOverlap(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);

	///getAabb returns the axis aligned bounding box in the 'global' coordinate frame
	///will add some transform later
	virtual void getBroadphaseAabb(btVector3& aabbMin,btVector3& aabbMax) const
	{
		aabbMin.setValue(-BT_LARGE_FLOAT,-BT_LARGE_FLOAT,-BT_LARGE_FLOAT);
		aabbMax.setValue(BT_LARGE_FLOAT,BT_LARGE_FLOAT,BT_LARGE_FLOAT);
	}

	virtual void	printStats()
	{
//		printf("btSimpleBroadphase.h\n");
//		printf("numHandles = %d, maxHandles = %d\n",m_numHandles,m_maxHandles);
	}
};

#endif //BT_SIMPLE_BROADPHASE_H


text:
/*
Bullet Continuous Collision Detection and Physics Library
Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

#ifndef BT_DISPATCHER_H
#define BT_DISPATCHER_H
#include "LinearMath/btScalar.h"

class btCollisionAlgorithm;
struct btBroadphaseProxy;
class btRigidBody;
class btCollisionObject;
class btOverlappingPairCache;
struct btCollisionObjectWrapper;

class btPersistentManifold;
class btPoolAllocator;

struct btDispatcherInfo
{
	enum DispatchFunc
	{
		DISPATCH_DISCRETE = 1,
		DISPATCH_CONTINUOUS
	};
	btDispatcherInfo()
	    : m_timeStep(btScalar(0.)),
	      m_stepCount(0),
	      m_dispatchFunc(DISPATCH_DISCRETE),
	      m_timeOfImpact(btScalar(1.)),
	      m_useContinuous(true),
	      m_debugDraw(0),
	      m_enableSatConvex(false),
	      m_enableSPU(true),
	      m_useEpa(true),
	      m_allowedCcdPenetration(btScalar(0.04)),
	      m_useConvexConservativeDistanceUtil(false),
	      m_convexConservativeDistanceThreshold(0.0f)
	{
	}
	btScalar            m_timeStep;
	int                 m_stepCount;
	int                 m_dispatchFunc;
	mutable btScalar    m_timeOfImpact;
	bool                m_useContinuous;
	class btIDebugDraw* m_debugDraw;
	bool                m_enableSatConvex;
	bool                m_enableSPU;
	bool                m_useEpa;
	btScalar            m_allowedCcdPenetration;
	bool                m_useConvexConservativeDistanceUtil;
	btScalar            m_convexConservativeDistanceThreshold;
};

enum ebtDispatcherQueryType
{
	BT_CONTACT_POINT_ALGORITHMS = 1,
	BT_CLOSEST_POINT_ALGORITHMS = 2
};

/// The btDispatcher interface class can be used in combination with broadphase
/// to dispatch calculations for overlapping pairs. For example for pairwise
/// collision detection, calculating contact points stored in
/// btPersistentManifold or user callbacks (game logic).
class btDispatcher
{
public:
	virtual ~btDispatcher();

	virtual btCollisionAlgorithm*  findAlgorithm(const btCollisionObjectWrapper* body0Wrap, const btCollisionObjectWrapper* body1Wrap, btPersistentManifold* sharedManifold, ebtDispatcherQueryType queryType) = 0;
	virtual btPersistentManifold*  getNewManifold(const btCollisionObject* b0, const btCollisionObject* b1)                                                                                = 0;
	virtual void                   releaseManifold(btPersistentManifold* manifold)                                                                                = 0;
	virtual void                   clearManifold(btPersistentManifold* manifold)                                                                                = 0;
	virtual bool                   needsCollision(const btCollisionObject* body0, const btCollisionObject* body1)                                                                                = 0;
	virtual bool                   needsResponse(const btCollisionObject* body0, const btCollisionObject* body1)                                                                                = 0;
	virtual void                   dispatchAllCollisionPairs(btOverlappingPairCache* pairCache, const btDispatcherInfo& dispatchInfo, btDispatcher* dispatcher)                                                = 0;
	virtual int                    getNumManifolds() const                                                                                = 0;
	virtual btPersistentManifold*  getManifoldByIndexInternal(int index)                                                                                = 0;
	virtual btPersistentManifold** getInternalManifoldPointer()                                                                                = 0;
	virtual btPoolAllocator*       getInternalManifoldPool()                                                                                = 0;
	virtual const btPoolAllocator* getInternalManifoldPool() const                                                                                = 0;
	virtual void*                  allocateCollisionAlgorithm(int size)                                                                                = 0;
	virtual void                   freeCollisionAlgorithm(void* ptr)                                                                                = 0;
};

#endif //BT_DISPATCHER_H


text:
/*
Bullet Continuous Collision Detection and Physics Library
Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

#ifndef BT_BROADPHASE_INTERFACE_H
#define BT_BROADPHASE_INTERFACE_H

struct btDispatcherInfo;
class btDispatcher;
#include "btBroadphaseProxy.h"

class btOverlappingPairCache;

struct btBroadphaseAabbCallback
{
	virtual ~btBroadphaseAabbCallback() {}
	virtual bool process(const btBroadphaseProxy* proxy) = 0;
};

struct btBroadphaseRayCallback : public btBroadphaseAabbCallback
{
	// added some cached data to accelerate ray-AABB tests

	btVector3    m_rayDirectionInverse;
	unsigned int m_signs[3];
	btScalar     m_lambda_max;

	virtual ~btBroadphaseRayCallback() {}

protected:
	btBroadphaseRayCallback() {}
};

#include "LinearMath/btVector3.h"

/// The btBroadphaseInterface class provides an interface to detect
/// aabb-overlapping object pairs. Some implementations for this broadphase
/// interface include btAxisSweep3, bt32BitAxisSweep3 and btDbvtBroadphase. The
/// actual overlapping pair management, storage, adding and removing of pairs is
/// dealt by the btOverlappingPairCache class.
class btBroadphaseInterface
{
public:
	virtual ~btBroadphaseInterface() {}

	virtual btBroadphaseProxy* createProxy(const btVector3& aabbMin, const btVector3& aabbMax, int shapeType, void* userPtr, int collisionFilterGroup, int collisionFilterMask, btDispatcher* dispatcher) = 0;
	virtual void               destroyProxy(btBroadphaseProxy* proxy, btDispatcher* dispatcher)                                                                                = 0;
	virtual void               setAabb(btBroadphaseProxy* proxy, const btVector3& aabbMin, const btVector3& aabbMax, btDispatcher* dispatcher)                                                            = 0;
	virtual void               getAabb(btBroadphaseProxy* proxy, btVector3& aabbMin, btVector3& aabbMax) const                                                                                = 0;

	virtual void rayTest(const btVector3& rayFrom, const btVector3& rayTo, btBroadphaseRayCallback& rayCallback, const btVector3& aabbMin = btVector3(0, 0, 0), const btVector3& aabbMax = btVector3(0, 0, 0)) = 0;

	virtual void aabbTest(const btVector3& aabbMin, const btVector3& aabbMax, btBroadphaseAabbCallback& callback) = 0;

	/// calculateOverlappingPairs is optional: incremental algorithms (sweep and
	/// prune) might do it during the set aabb
	virtual void calculateOverlappingPairs(btDispatcher* dispatcher) = 0;

	virtual btOverlappingPairCache*       getOverlappingPairCache()       = 0;
	virtual const btOverlappingPairCache* getOverlappingPairCache() const = 0;

	/// getAabb returns the axis aligned bounding box in the 'global' coordinate
	/// frame will add some transform later
	virtual void getBroadphaseAabb(btVector3& aabbMin, btVector3& aabbMax) const = 0;

	/// reset broadphase internal structures, to ensure determinism/reproducibility
	virtual void resetPool(btDispatcher* dispatcher) { (void) dispatcher; };

	virtual void printStats() = 0;
};

#endif //BT_BROADPHASE_INTERFACE_H


text:
//Bullet Continuous Collision Detection and Physics Library
//Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/

//
// btAxisSweep3.h
//
// Copyright (c) 2006 Simon Hobbs
//
// This software is provided 'as-is', without any express or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software.
//
// Permission is granted to anyone to use this software for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to the following restrictions:
//
// 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
//
// 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
//
// 3. This notice may not be removed or altered from any source distribution.

#ifndef BT_AXIS_SWEEP_3_INTERNAL_H
#define BT_AXIS_SWEEP_3_INTERNAL_H

#include "LinearMath/btVector3.h"
#include "btOverlappingPairCache.h"
#include "btBroadphaseInterface.h"
#include "btBroadphaseProxy.h"
#include "btOverlappingPairCallback.h"
#include "btDbvtBroadphase.h"

//#define DEBUG_BROADPHASE 1
#define USE_OVERLAP_TEST_ON_REMOVES 1

/// The internal templace class btAxisSweep3Internal implements the sweep and prune broadphase.
/// It uses quantized integers to represent the begin and end points for each of the 3 axis.
/// Dont use this class directly, use btAxisSweep3 or bt32BitAxisSweep3 instead.
template <typename BP_FP_INT_TYPE>
class btAxisSweep3Internal : public btBroadphaseInterface
{
protected:

	BP_FP_INT_TYPE	m_bpHandleMask;
	BP_FP_INT_TYPE	m_handleSentinel;

public:

 BT_DECLARE_ALIGNED_ALLOCATOR();

	class Edge
	{
	public:
		BP_FP_INT_TYPE m_pos;			// low bit is min/max
		BP_FP_INT_TYPE m_handle;

		BP_FP_INT_TYPE IsMax() const {return static_cast<BP_FP_INT_TYPE>(m_pos & 1);}
	};

public:
	class	Handle : public btBroadphaseProxy
	{
	public:
	BT_DECLARE_ALIGNED_ALLOCATOR();

		// indexes into the edge arrays
		BP_FP_INT_TYPE m_minEdges[3], m_maxEdges[3];		// 6 * 2 = 12
//		BP_FP_INT_TYPE m_uniqueId;
		btBroadphaseProxy*	m_dbvtProxy;//for faster raycast
		//void* m_pOwner; this is now in btBroadphaseProxy.m_clientObject

		SIMD_FORCE_INLINE void SetNextFree(BP_FP_INT_TYPE next) {m_minEdges[0] = next;}
		SIMD_FORCE_INLINE BP_FP_INT_TYPE GetNextFree() const {return m_minEdges[0];}
	};		// 24 bytes + 24 for Edge structures = 44 bytes total per entry

protected:
	btVector3 m_worldAabbMin;						// overall system bounds
	btVector3 m_worldAabbMax;						// overall system bounds

	btVector3 m_quantize;						// scaling factor for quantization

	BP_FP_INT_TYPE m_numHandles;						// number of active handles
	BP_FP_INT_TYPE m_maxHandles;						// max number of handles
	Handle* m_pHandles;						// handles pool

	BP_FP_INT_TYPE m_firstFreeHandle;		// free handles list

	Edge* m_pEdges[3];						// edge arrays for the 3 axes (each array has m_maxHandles * 2 + 2 sentinel entries)
	void* m_pEdgesRawPtr[3];

	btOverlappingPairCache* m_pairCache;

	///btOverlappingPairCallback is an additional optional user callback for adding/removing overlapping pairs, similar interface to btOverlappingPairCache.
	btOverlappingPairCallback* m_userPairCallback;

	bool	m_ownsPairCache;

	int	m_invalidPair;

	///additional dynamic aabb structure, used to accelerate ray cast queries.
	///can be disabled using a optional argument in the constructor
	btDbvtBroadphase*	m_raycastAccelerator;
	btOverlappingPairCache*	m_nullPairCache;

	// allocation/deallocation
	BP_FP_INT_TYPE allocHandle();
	void freeHandle(BP_FP_INT_TYPE handle);

	bool testOverlap2D(const Handle* pHandleA, const Handle* pHandleB,int axis0,int axis1);

#ifdef DEBUG_BROADPHASE
	void debugPrintAxis(int axis,bool checkCardinality=true);
#endif //DEBUG_BROADPHASE

	//Overlap* AddOverlap(BP_FP_INT_TYPE handleA, BP_FP_INT_TYPE handleB);
	//void RemoveOverlap(BP_FP_INT_TYPE handleA, BP_FP_INT_TYPE handleB);

	void sortMinDown(int axis, BP_FP_INT_TYPE edge, btDispatcher* dispatcher, bool updateOverlaps );
	void sortMinUp(int axis, BP_FP_INT_TYPE edge, btDispatcher* dispatcher, bool updateOverlaps );
	void sortMaxDown(int axis, BP_FP_INT_TYPE edge, btDispatcher* dispatcher, bool updateOverlaps );
	void sortMaxUp(int axis, BP_FP_INT_TYPE edge, btDispatcher* dispatcher, bool updateOverlaps );

public:

	btAxisSweep3Internal(const btVector3& worldAabbMin,const btVector3& worldAabbMax, BP_FP_INT_TYPE handleMask, BP_FP_INT_TYPE handleSentinel, BP_FP_INT_TYPE maxHandles = 16384, btOverlappingPairCache* pairCache=0,bool disableRaycastAccelerator = false);

	virtual	~btAxisSweep3Internal();

	BP_FP_INT_TYPE getNumHandles() const
	{
		return m_numHandles;
	}

	virtual void	calculateOverlappingPairs(btDispatcher* dispatcher);

	BP_FP_INT_TYPE addHandle(const btVector3& aabbMin,const btVector3& aabbMax, void* pOwner, int collisionFilterGroup, int collisionFilterMask,btDispatcher* dispatcher);
	void removeHandle(BP_FP_INT_TYPE handle,btDispatcher* dispatcher);
	void updateHandle(BP_FP_INT_TYPE handle, const btVector3& aabbMin,const btVector3& aabbMax,btDispatcher* dispatcher);
	SIMD_FORCE_INLINE Handle* getHandle(BP_FP_INT_TYPE index) const {return m_pHandles + index;}

	virtual void resetPool(btDispatcher* dispatcher);

	void	processAllOverlappingPairs(btOverlapCallback* callback);

	//Broadphase Interface
	virtual btBroadphaseProxy*	createProxy(  const btVector3& aabbMin,  const btVector3& aabbMax,int shapeType,void* userPtr , int collisionFilterGroup, int collisionFilterMask,btDispatcher* dispatcher);
	virtual void	destroyProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
	virtual void	setAabb(btBroadphaseProxy* proxy,const btVector3& aabbMin,const btVector3& aabbMax,btDispatcher* dispatcher);
	virtual void  getAabb(btBroadphaseProxy* proxy,btVector3& aabbMin, btVector3& aabbMax ) const;

	virtual void	rayTest(const btVector3& rayFrom,const btVector3& rayTo, btBroadphaseRayCallback& rayCallback, const btVector3& aabbMin=btVector3(0,0,0), const btVector3& aabbMax = btVector3(0,0,0));
	virtual void	aabbTest(const btVector3& aabbMin, const btVector3& aabbMax, btBroadphaseAabbCallback& callback);

	void quantize(BP_FP_INT_TYPE* out, const btVector3& point, int isMax) const;
	///unQuantize should be conservative: aabbMin/aabbMax should be larger then 'getAabb' result
	void unQuantize(btBroadphaseProxy* proxy,btVector3& aabbMin, btVector3& aabbMax ) const;

	bool	testAabbOverlap(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);

	btOverlappingPairCache*	getOverlappingPairCache()
	{
		return m_pairCache;
	}
	const btOverlappingPairCache*	getOverlappingPairCache() const
	{
		return m_pairCache;
	}

	void	setOverlappingPairUserCallback(btOverlappingPairCallback* pairCallback)
	{
		m_userPairCallback = pairCallback;
	}
	const btOverlappingPairCallback*	getOverlappingPairUserCallback() const
	{
		return m_userPairCallback;
	}

	///getAabb returns the axis aligned bounding box in the 'global' coordinate frame
	///will add some transform later
	virtual void getBroadphaseAabb(btVector3& aabbMin,btVector3& aabbMax) const
	{
		aabbMin = m_worldAabbMin;
		aabbMax = m_worldAabbMax;
	}

	virtual void	printStats()
	{
/*		printf("btAxisSweep3.h\n");
		printf("numHandles = %d, maxHandles = %d\n",m_numHandles,m_maxHandles);
		printf("aabbMin=%f,%f,%f,aabbMax=%f,%f,%f\n",m_worldAabbMin.getX(),m_worldAabbMin.getY(),m_worldAabbMin.getZ(),
			m_worldAabbMax.getX(),m_worldAabbMax.getY(),m_worldAabbMax.getZ());
			*/

	}

};

////////////////////////////////////////////////////////////////////

#ifdef DEBUG_BROADPHASE
#include <stdio.h>

template <typename BP_FP_INT_TYPE>
void btAxisSweep3<BP_FP_INT_TYPE>::debugPrintAxis(int axis, bool checkCardinality)
{
	int numEdges = m_pHandles[0].m_maxEdges[axis];
	printf("SAP Axis %d, numEdges=%d\n",axis,numEdges);

	int i;
	for (i=0;i<numEdges+1;i++)
	{
		Edge* pEdge = m_pEdges[axis] + i;
		Handle* pHandlePrev = getHandle(pEdge->m_handle);
		int handleIndex = pEdge->IsMax()? pHandlePrev->m_maxEdges[axis] : pHandlePrev->m_minEdges[axis];
		char beginOrEnd;
		beginOrEnd=pEdge->IsMax()?'E':'B';
		printf("	[%c,h=%d,p=%x,i=%d]\n",beginOrEnd,pEdge->m_handle,pEdge->m_pos,handleIndex);
	}

	if (checkCardinality)
		btAssert(numEdges == m_numHandles*2+1);
}
#endif //DEBUG_BROADPHASE

template <typename BP_FP_INT_TYPE>
btBroadphaseProxy*	btAxisSweep3Internal<BP_FP_INT_TYPE>::createProxy(  const btVector3& aabbMin,  const btVector3& aabbMax,int shapeType,void* userPtr, int collisionFilterGroup, int collisionFilterMask,btDispatcher* dispatcher)
{
		(void)shapeType;
		BP_FP_INT_TYPE handleId = addHandle(aabbMin,aabbMax, userPtr,collisionFilterGroup,collisionFilterMask,dispatcher);

		Handle* handle = getHandle(handleId);

		if (m_raycastAccelerator)
		{
			btBroadphaseProxy* rayProxy = m_raycastAccelerator->createProxy(aabbMin,aabbMax,shapeType,userPtr,collisionFilterGroup,collisionFilterMask,dispatcher);
			handle->m_dbvtProxy = rayProxy;
		}
		return handle;
}

template <typename BP_FP_INT_TYPE>
void	btAxisSweep3Internal<BP_FP_INT_TYPE>::destroyProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
{
	Handle* handle = static_cast<Handle*>(proxy);
	if (m_raycastAccelerator)
		m_raycastAccelerator->destroyProxy(handle->m_dbvtProxy,dispatcher);
	removeHandle(static_cast<BP_FP_INT_TYPE>(handle->m_uniqueId), dispatcher);
}

template <typename BP_FP_INT_TYPE>
void	btAxisSweep3Internal<BP_FP_INT_TYPE>::setAabb(btBroadphaseProxy* proxy,const btVector3& aabbMin,const btVector3& aabbMax,btDispatcher* dispatcher)
{
	Handle* handle = static_cast<Handle*>(proxy);
	handle->m_aabbMin = aabbMin;
	handle->m_aabbMax = aabbMax;
	updateHandle(static_cast<BP_FP_INT_TYPE>(handle->m_uniqueId), aabbMin, aabbMax,dispatcher);
	if (m_raycastAccelerator)
		m_raycastAccelerator->setAabb(handle->m_dbvtProxy,aabbMin,aabbMax,dispatcher);

}

template <typename BP_FP_INT_TYPE>
void	btAxisSweep3Internal<BP_FP_INT_TYPE>::rayTest(const btVector3& rayFrom,const btVector3& rayTo, btBroadphaseRayCallback& rayCallback,const btVector3& aabbMin,const btVector3& aabbMax)
{
	if (m_raycastAccelerator)
	{
		m_raycastAccelerator->rayTest(rayFrom,rayTo,rayCallback,aabbMin,aabbMax);
	} else
	{
		//choose axis?
		BP_FP_INT_TYPE axis = 0;
		//for each proxy
		for (BP_FP_INT_TYPE i=1;i<m_numHandles*2+1;i++)
		{
			if (m_pEdges[axis][i].IsMax())
			{
				rayCallback.process(getHandle(m_pEdges[axis][i].m_handle));
			}
		}
	}
}

template <typename BP_FP_INT_TYPE>
void	btAxisSweep3Internal<BP_FP_INT_TYPE>::aabbTest(const btVector3& aabbMin, const btVector3& aabbMax, btBroadphaseAabbCallback& callback)
{
	if (m_raycastAccelerator)
	{
		m_raycastAccelerator->aabbTest(aabbMin,aabbMax,callback);
	} else
	{
		//choose axis?
		BP_FP_INT_TYPE axis = 0;
		//for each proxy
		for (BP_FP_INT_TYPE i=1;i<m_numHandles*2+1;i++)
		{
			if (m_pEdges[axis][i].IsMax())
			{
				Handle* handle = getHandle(m_pEdges[axis][i].m_handle);
				if (TestAabbAgainstAabb2(aabbMin,aabbMax,handle->m_aabbMin,handle->m_aabbMax))
				{
					callback.process(handle);
				}
			}
		}
	}
}

template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::getAabb(btBroadphaseProxy* proxy,btVector3& aabbMin, btVector3& aabbMax ) const
{
	Handle* pHandle = static_cast<Handle*>(proxy);
	aabbMin = pHandle->m_aabbMin;
	aabbMax = pHandle->m_aabbMax;
}

template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::unQuantize(btBroadphaseProxy* proxy,btVector3& aabbMin, btVector3& aabbMax ) const
{
	Handle* pHandle = static_cast<Handle*>(proxy);

	unsigned short vecInMin[3];
	unsigned short vecInMax[3];

	vecInMin[0] = m_pEdges[0][pHandle->m_minEdges[0]].m_pos ;
	vecInMax[0] = m_pEdges[0][pHandle->m_maxEdges[0]].m_pos +1 ;
	vecInMin[1] = m_pEdges[1][pHandle->m_minEdges[1]].m_pos ;
	vecInMax[1] = m_pEdges[1][pHandle->m_maxEdges[1]].m_pos +1 ;
	vecInMin[2] = m_pEdges[2][pHandle->m_minEdges[2]].m_pos ;
	vecInMax[2] = m_pEdges[2][pHandle->m_maxEdges[2]].m_pos +1 ;

	aabbMin.setValue((btScalar)(vecInMin[0]) / (m_quantize.getX()),(btScalar)(vecInMin[1]) / (m_quantize.getY()),(btScalar)(vecInMin[2]) / (m_quantize.getZ()));
	aabbMin += m_worldAabbMin;

	aabbMax.setValue((btScalar)(vecInMax[0]) / (m_quantize.getX()),(btScalar)(vecInMax[1]) / (m_quantize.getY()),(btScalar)(vecInMax[2]) / (m_quantize.getZ()));
	aabbMax += m_worldAabbMin;
}

template <typename BP_FP_INT_TYPE>
btAxisSweep3Internal<BP_FP_INT_TYPE>::btAxisSweep3Internal(const btVector3& worldAabbMin,const btVector3& worldAabbMax, BP_FP_INT_TYPE handleMask, BP_FP_INT_TYPE handleSentinel,BP_FP_INT_TYPE userMaxHandles, btOverlappingPairCache* pairCache , bool disableRaycastAccelerator)
:m_bpHandleMask(handleMask),
m_handleSentinel(handleSentinel),
m_pairCache(pairCache),
m_userPairCallback(0),
m_ownsPairCache(false),
m_invalidPair(0),
m_raycastAccelerator(0)
{
	BP_FP_INT_TYPE maxHandles = static_cast<BP_FP_INT_TYPE>(userMaxHandles+1);//need to add one sentinel handle

	if (!m_pairCache)
	{
		void* ptr = btAlignedAlloc(sizeof(btHashedOverlappingPairCache),16);
		m_pairCache = new(ptr) btHashedOverlappingPairCache();
		m_ownsPairCache = true;
	}

	if (!disableRaycastAccelerator)
	{
		m_nullPairCache = new (btAlignedAlloc(sizeof(btNullPairCache),16)) btNullPairCache();
		m_raycastAccelerator = new (btAlignedAlloc(sizeof(btDbvtBroadphase),16)) btDbvtBroadphase(m_nullPairCache);//m_pairCache);
		m_raycastAccelerator->m_deferedcollide = true;//don't add/remove pairs
	}

	//btAssert(bounds.HasVolume());

	// init bounds
	m_worldAabbMin = worldAabbMin;
	m_worldAabbMax = worldAabbMax;

	btVector3 aabbSize = m_worldAabbMax - m_worldAabbMin;

	BP_FP_INT_TYPE	maxInt = m_handleSentinel;

	m_quantize = btVector3(btScalar(maxInt),btScalar(maxInt),btScalar(maxInt)) / aabbSize;

	// allocate handles buffer, using btAlignedAlloc, and put all handles on free list
	m_pHandles = new Handle[maxHandles];

	m_maxHandles = maxHandles;
	m_numHandles = 0;

	// handle 0 is reserved as the null index, and is also used as the sentinel
	m_firstFreeHandle = 1;
	{
		for (BP_FP_INT_TYPE i = m_firstFreeHandle; i < maxHandles; i++)
			m_pHandles[i].SetNextFree(static_cast<BP_FP_INT_TYPE>(i + 1));
		m_pHandles[maxHandles - 1].SetNextFree(0);
	}

	{
		// allocate edge buffers
		for (int i = 0; i < 3; i++)
		{
			m_pEdgesRawPtr[i] = btAlignedAlloc(sizeof(Edge)*maxHandles*2,16);
			m_pEdges[i] = new(m_pEdgesRawPtr[i]) Edge[maxHandles * 2];
		}
	}
	//removed overlap management

	// make boundary sentinels

	m_pHandles[0].m_clientObject = 0;

	for (int axis = 0; axis < 3; axis++)
	{
		m_pHandles[0].m_minEdges[axis] = 0;
		m_pHandles[0].m_maxEdges[axis] = 1;

		m_pEdges[axis][0].m_pos = 0;
		m_pEdges[axis][0].m_handle = 0;
		m_pEdges[axis][1].m_pos = m_handleSentinel;
		m_pEdges[axis][1].m_handle = 0;
#ifdef DEBUG_BROADPHASE
		debugPrintAxis(axis);
#endif //DEBUG_BROADPHASE

	}

}

template <typename BP_FP_INT_TYPE>
btAxisSweep3Internal<BP_FP_INT_TYPE>::~btAxisSweep3Internal()
{
	if (m_raycastAccelerator)
	{
		m_nullPairCache->~btOverlappingPairCache();
		btAlignedFree(m_nullPairCache);
		m_raycastAccelerator->~btDbvtBroadphase();
		btAlignedFree (m_raycastAccelerator);
	}

	for (int i = 2; i >= 0; i--)
	{
		btAlignedFree(m_pEdgesRawPtr[i]);
	}
	delete [] m_pHandles;

	if (m_ownsPairCache)
	{
		m_pairCache->~btOverlappingPairCache();
		btAlignedFree(m_pairCache);
	}
}

template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::quantize(BP_FP_INT_TYPE* out, const btVector3& point, int isMax) const
{
#ifdef OLD_CLAMPING_METHOD
	///problem with this clamping method is that the floating point during quantization might still go outside the range [(0|isMax) .. (m_handleSentinel&m_bpHandleMask]|isMax]
	///see http://code.google.com/p/bullet/issues/detail?id=87
	btVector3 clampedPoint(point);
	clampedPoint.setMax(m_worldAabbMin);
	clampedPoint.setMin(m_worldAabbMax);
	btVector3 v = (clampedPoint - m_worldAabbMin) * m_quantize;
	out[0] = (BP_FP_INT_TYPE)(((BP_FP_INT_TYPE)v.getX() & m_bpHandleMask) | isMax);
	out[1] = (BP_FP_INT_TYPE)(((BP_FP_INT_TYPE)v.getY() & m_bpHandleMask) | isMax);
	out[2] = (BP_FP_INT_TYPE)(((BP_FP_INT_TYPE)v.getZ() & m_bpHandleMask) | isMax);
#else
	btVector3 v = (point - m_worldAabbMin) * m_quantize;
	out[0]=(v[0]<=0)?(BP_FP_INT_TYPE)isMax:(v[0]>=m_handleSentinel)?(BP_FP_INT_TYPE)((m_handleSentinel&m_bpHandleMask)|isMax):(BP_FP_INT_TYPE)(((BP_FP_INT_TYPE)v[0]&m_bpHandleMask)|isMax);
	out[1]=(v[1]<=0)?(BP_FP_INT_TYPE)isMax:(v[1]>=m_handleSentinel)?(BP_FP_INT_TYPE)((m_handleSentinel&m_bpHandleMask)|isMax):(BP_FP_INT_TYPE)(((BP_FP_INT_TYPE)v[1]&m_bpHandleMask)|isMax);
	out[2]=(v[2]<=0)?(BP_FP_INT_TYPE)isMax:(v[2]>=m_handleSentinel)?(BP_FP_INT_TYPE)((m_handleSentinel&m_bpHandleMask)|isMax):(BP_FP_INT_TYPE)(((BP_FP_INT_TYPE)v[2]&m_bpHandleMask)|isMax);
#endif //OLD_CLAMPING_METHOD
}

template <typename BP_FP_INT_TYPE>
BP_FP_INT_TYPE btAxisSweep3Internal<BP_FP_INT_TYPE>::allocHandle()
{
	btAssert(m_firstFreeHandle);

	BP_FP_INT_TYPE handle = m_firstFreeHandle;
	m_firstFreeHandle = getHandle(handle)->GetNextFree();
	m_numHandles++;

	return handle;
}

template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::freeHandle(BP_FP_INT_TYPE handle)
{
	btAssert(handle > 0 && handle < m_maxHandles);

	getHandle(handle)->SetNextFree(m_firstFreeHandle);
	m_firstFreeHandle = handle;

	m_numHandles--;
}

template <typename BP_FP_INT_TYPE>
BP_FP_INT_TYPE btAxisSweep3Internal<BP_FP_INT_TYPE>::addHandle(const btVector3& aabbMin,const btVector3& aabbMax, void* pOwner, int collisionFilterGroup, int collisionFilterMask,btDispatcher* dispatcher)
{
	// quantize the bounds
	BP_FP_INT_TYPE min[3], max[3];
	quantize(min, aabbMin, 0);
	quantize(max, aabbMax, 1);

	// allocate a handle
	BP_FP_INT_TYPE handle = allocHandle();

	Handle* pHandle = getHandle(handle);

	pHandle->m_uniqueId = static_cast<int>(handle);
	//pHandle->m_pOverlaps = 0;
	pHandle->m_clientObject = pOwner;
	pHandle->m_collisionFilterGroup = collisionFilterGroup;
	pHandle->m_collisionFilterMask = collisionFilterMask;

	// compute current limit of edge arrays
	BP_FP_INT_TYPE limit = static_cast<BP_FP_INT_TYPE>(m_numHandles * 2);

	// insert new edges just inside the max boundary edge
	for (BP_FP_INT_TYPE axis = 0; axis < 3; axis++)
	{

		m_pHandles[0].m_maxEdges[axis] += 2;

		m_pEdges[axis][limit + 1] = m_pEdges[axis][limit - 1];

		m_pEdges[axis][limit - 1].m_pos = min[axis];
		m_pEdges[axis][limit - 1].m_handle = handle;

		m_pEdges[axis][limit].m_pos = max[axis];
		m_pEdges[axis][limit].m_handle = handle;

		pHandle->m_minEdges[axis] = static_cast<BP_FP_INT_TYPE>(limit - 1);
		pHandle->m_maxEdges[axis] = limit;
	}

	// now sort the new edges to their correct position
	sortMinDown(0, pHandle->m_minEdges[0], dispatcher,false);
	sortMaxDown(0, pHandle->m_maxEdges[0], dispatcher,false);
	sortMinDown(1, pHandle->m_minEdges[1], dispatcher,false);
	sortMaxDown(1, pHandle->m_maxEdges[1], dispatcher,false);
	sortMinDown(2, pHandle->m_minEdges[2], dispatcher,true);
	sortMaxDown(2, pHandle->m_maxEdges[2], dispatcher,true);

	return handle;
}

template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::removeHandle(BP_FP_INT_TYPE handle,btDispatcher* dispatcher)
{

	Handle* pHandle = getHandle(handle);

	//explicitly remove the pairs containing the proxy
	//we could do it also in the sortMinUp (passing true)
	///@todo: compare performance
	if (!m_pairCache->hasDeferredRemoval())
	{
		m_pairCache->removeOverlappingPairsContainingProxy(pHandle,dispatcher);
	}

	// compute current limit of edge arrays
	int limit = static_cast<int>(m_numHandles * 2);

	int axis;

	for (axis = 0;axis<3;axis++)
	{
		m_pHandles[0].m_maxEdges[axis] -= 2;
	}

	// remove the edges by sorting them up to the end of the list
	for ( axis = 0; axis < 3; axis++)
	{
		Edge* pEdges = m_pEdges[axis];
		BP_FP_INT_TYPE max = pHandle->m_maxEdges[axis];
		pEdges[max].m_pos = m_handleSentinel;

		sortMaxUp(axis,max,dispatcher,false);

		BP_FP_INT_TYPE i = pHandle->m_minEdges[axis];
		pEdges[i].m_pos = m_handleSentinel;

		sortMinUp(axis,i,dispatcher,false);

		pEdges[limit-1].m_handle = 0;
		pEdges[limit-1].m_pos = m_handleSentinel;

#ifdef DEBUG_BROADPHASE
			debugPrintAxis(axis,false);
#endif //DEBUG_BROADPHASE

	}

	// free the handle
	freeHandle(handle);

}

template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::resetPool(btDispatcher* /*dispatcher*/)
{
	if (m_numHandles == 0)
	{
		m_firstFreeHandle = 1;
		{
			for (BP_FP_INT_TYPE i = m_firstFreeHandle; i < m_maxHandles; i++)
				m_pHandles[i].SetNextFree(static_cast<BP_FP_INT_TYPE>(i + 1));
			m_pHandles[m_maxHandles - 1].SetNextFree(0);
		}
	}
}

extern int gOverlappingPairs;
//#include <stdio.h>

template <typename BP_FP_INT_TYPE>
void	btAxisSweep3Internal<BP_FP_INT_TYPE>::calculateOverlappingPairs(btDispatcher* dispatcher)
{

	if (m_pairCache->hasDeferredRemoval())
	{

		btBroadphasePairArray&	overlappingPairArray = m_pairCache->getOverlappingPairArray();

		//perform a sort, to find duplicates and to sort 'invalid' pairs to the end
		overlappingPairArray.quickSort(btBroadphasePairSortPredicate());

		overlappingPairArray.resize(overlappingPairArray.size() - m_invalidPair);
		m_invalidPair = 0;

		int i;

		btBroadphasePair previousPair;
		previousPair.m_pProxy0 = 0;
		previousPair.m_pProxy1 = 0;
		previousPair.m_algorithm = 0;

		for (i=0;i<overlappingPairArray.size();i++)
		{

			btBroadphasePair& pair = overlappingPairArray[i];

			bool isDuplicate = (pair == previousPair);

			previousPair = pair;

			bool needsRemoval = false;

			if (!isDuplicate)
			{
				///important to use an AABB test that is consistent with the broadphase
				bool hasOverlap = testAabbOverlap(pair.m_pProxy0,pair.m_pProxy1);

				if (hasOverlap)
				{
					needsRemoval = false;//callback->processOverlap(pair);
				} else
				{
					needsRemoval = true;
				}
			} else
			{
				//remove duplicate
				needsRemoval = true;
				//should have no algorithm
				btAssert(!pair.m_algorithm);
			}

			if (needsRemoval)
			{
				m_pairCache->cleanOverlappingPair(pair,dispatcher);

		//		m_overlappingPairArray.swap(i,m_overlappingPairArray.size()-1);
		//		m_overlappingPairArray.pop_back();
				pair.m_pProxy0 = 0;
				pair.m_pProxy1 = 0;
				m_invalidPair++;
				gOverlappingPairs--;
			}

		}

	///if you don't like to skip the invalid pairs in the array, execute following code:
	#define CLEAN_INVALID_PAIRS 1
	#ifdef CLEAN_INVALID_PAIRS

		//perform a sort, to sort 'invalid' pairs to the end
		overlappingPairArray.quickSort(btBroadphasePairSortPredicate());

		overlappingPairArray.resize(overlappingPairArray.size() - m_invalidPair);
		m_invalidPair = 0;
	#endif//CLEAN_INVALID_PAIRS

		//printf("overlappingPairArray.size()=%d\n",overlappingPairArray.size());
	}

}

template <typename BP_FP_INT_TYPE>
bool btAxisSweep3Internal<BP_FP_INT_TYPE>::testAabbOverlap(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
{
	const Handle* pHandleA = static_cast<Handle*>(proxy0);
	const Handle* pHandleB = static_cast<Handle*>(proxy1);

	//optimization 1: check the array index (memory address), instead of the m_pos

	for (int axis = 0; axis < 3; axis++)
	{
		if (pHandleA->m_maxEdges[axis] < pHandleB->m_minEdges[axis] ||
			pHandleB->m_maxEdges[axis] < pHandleA->m_minEdges[axis])
		{
			return false;
		}
	}
	return true;
}

template <typename BP_FP_INT_TYPE>
bool btAxisSweep3Internal<BP_FP_INT_TYPE>::testOverlap2D(const Handle* pHandleA, const Handle* pHandleB,int axis0,int axis1)
{
	//optimization 1: check the array index (memory address), instead of the m_pos

	if (pHandleA->m_maxEdges[axis0] < pHandleB->m_minEdges[axis0] ||
		pHandleB->m_maxEdges[axis0] < pHandleA->m_minEdges[axis0] ||
		pHandleA->m_maxEdges[axis1] < pHandleB->m_minEdges[axis1] ||
		pHandleB->m_maxEdges[axis1] < pHandleA->m_minEdges[axis1])
	{
		return false;
	}
	return true;
}

template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::updateHandle(BP_FP_INT_TYPE handle, const btVector3& aabbMin,const btVector3& aabbMax,btDispatcher* dispatcher)
{
//	btAssert(bounds.IsFinite());
	//btAssert(bounds.HasVolume());

	Handle* pHandle = getHandle(handle);

	// quantize the new bounds
	BP_FP_INT_TYPE min[3], max[3];
	quantize(min, aabbMin, 0);
	quantize(max, aabbMax, 1);

	// update changed edges
	for (int axis = 0; axis < 3; axis++)
	{
		BP_FP_INT_TYPE emin = pHandle->m_minEdges[axis];
		BP_FP_INT_TYPE emax = pHandle->m_maxEdges[axis];

		int dmin = (int)min[axis] - (int)m_pEdges[axis][emin].m_pos;
		int dmax = (int)max[axis] - (int)m_pEdges[axis][emax].m_pos;

		m_pEdges[axis][emin].m_pos = min[axis];
		m_pEdges[axis][emax].m_pos = max[axis];

		// expand (only adds overlaps)
		if (dmin < 0)
			sortMinDown(axis, emin,dispatcher,true);

		if (dmax > 0)
			sortMaxUp(axis, emax,dispatcher,true);

		// shrink (only removes overlaps)
		if (dmin > 0)
			sortMinUp(axis, emin,dispatcher,true);

		if (dmax < 0)
			sortMaxDown(axis, emax,dispatcher,true);

#ifdef DEBUG_BROADPHASE
	debugPrintAxis(axis);
#endif //DEBUG_BROADPHASE
	}

}

// sorting a min edge downwards can only ever *add* overlaps
template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::sortMinDown(int axis, BP_FP_INT_TYPE edge, btDispatcher* /* dispatcher */, bool updateOverlaps)
{

	Edge* pEdge = m_pEdges[axis] + edge;
	Edge* pPrev = pEdge - 1;
	Handle* pHandleEdge = getHandle(pEdge->m_handle);

	while (pEdge->m_pos < pPrev->m_pos)
	{
		Handle* pHandlePrev = getHandle(pPrev->m_handle);

		if (pPrev->IsMax())
		{
			// if previous edge is a maximum check the bounds and add an overlap if necessary
			const int axis1 = (1  << axis) & 3;
			const int axis2 = (1  << axis1) & 3;
			if (updateOverlaps && testOverlap2D(pHandleEdge, pHandlePrev,axis1,axis2))
			{
				m_pairCache->addOverlappingPair(pHandleEdge,pHandlePrev);
				if (m_userPairCallback)
					m_userPairCallback->addOverlappingPair(pHandleEdge,pHandlePrev);

				//AddOverlap(pEdge->m_handle, pPrev->m_handle);

			}

			// update edge reference in other handle
			pHandlePrev->m_maxEdges[axis]++;
		}
		else
			pHandlePrev->m_minEdges[axis]++;

		pHandleEdge->m_minEdges[axis]--;

		// swap the edges
		Edge swap = *pEdge;
		*pEdge = *pPrev;
		*pPrev = swap;

		// decrement
		pEdge--;
		pPrev--;
	}

#ifdef DEBUG_BROADPHASE
	debugPrintAxis(axis);
#endif //DEBUG_BROADPHASE

}

// sorting a min edge upwards can only ever *remove* overlaps
template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::sortMinUp(int axis, BP_FP_INT_TYPE edge, btDispatcher* dispatcher, bool updateOverlaps)
{
	Edge* pEdge = m_pEdges[axis] + edge;
	Edge* pNext = pEdge + 1;
	Handle* pHandleEdge = getHandle(pEdge->m_handle);

	while (pNext->m_handle && (pEdge->m_pos >= pNext->m_pos))
	{
		Handle* pHandleNext = getHandle(pNext->m_handle);

		if (pNext->IsMax())
		{
			Handle* handle0 = getHandle(pEdge->m_handle);
			Handle* handle1 = getHandle(pNext->m_handle);
			const int axis1 = (1  << axis) & 3;
			const int axis2 = (1  << axis1) & 3;

			// if next edge is maximum remove any overlap between the two handles
			if (updateOverlaps
#ifdef USE_OVERLAP_TEST_ON_REMOVES
				&& testOverlap2D(handle0,handle1,axis1,axis2)
#endif //USE_OVERLAP_TEST_ON_REMOVES
				)
			{

				m_pairCache->removeOverlappingPair(handle0,handle1,dispatcher);
				if (m_userPairCallback)
					m_userPairCallback->removeOverlappingPair(handle0,handle1,dispatcher);

			}

			// update edge reference in other handle
			pHandleNext->m_maxEdges[axis]--;
		}
		else
			pHandleNext->m_minEdges[axis]--;

		pHandleEdge->m_minEdges[axis]++;

		// swap the edges
		Edge swap = *pEdge;
		*pEdge = *pNext;
		*pNext = swap;

		// increment
		pEdge++;
		pNext++;
	}

}

// sorting a max edge downwards can only ever *remove* overlaps
template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::sortMaxDown(int axis, BP_FP_INT_TYPE edge, btDispatcher* dispatcher, bool updateOverlaps)
{

	Edge* pEdge = m_pEdges[axis] + edge;
	Edge* pPrev = pEdge - 1;
	Handle* pHandleEdge = getHandle(pEdge->m_handle);

	while (pEdge->m_pos < pPrev->m_pos)
	{
		Handle* pHandlePrev = getHandle(pPrev->m_handle);

		if (!pPrev->IsMax())
		{
			// if previous edge was a minimum remove any overlap between the two handles
			Handle* handle0 = getHandle(pEdge->m_handle);
			Handle* handle1 = getHandle(pPrev->m_handle);
			const int axis1 = (1  << axis) & 3;
			const int axis2 = (1  << axis1) & 3;

			if (updateOverlaps
#ifdef USE_OVERLAP_TEST_ON_REMOVES
				&& testOverlap2D(handle0,handle1,axis1,axis2)
#endif //USE_OVERLAP_TEST_ON_REMOVES
				)
			{
				//this is done during the overlappingpairarray iteration/narrowphase collision

				m_pairCache->removeOverlappingPair(handle0,handle1,dispatcher);
				if (m_userPairCallback)
					m_userPairCallback->removeOverlappingPair(handle0,handle1,dispatcher);

			}

			// update edge reference in other handle
			pHandlePrev->m_minEdges[axis]++;;
		}
		else
			pHandlePrev->m_maxEdges[axis]++;

		pHandleEdge->m_maxEdges[axis]--;

		// swap the edges
		Edge swap = *pEdge;
		*pEdge = *pPrev;
		*pPrev = swap;

		// decrement
		pEdge--;
		pPrev--;
	}

#ifdef DEBUG_BROADPHASE
	debugPrintAxis(axis);
#endif //DEBUG_BROADPHASE

}

// sorting a max edge upwards can only ever *add* overlaps
template <typename BP_FP_INT_TYPE>
void btAxisSweep3Internal<BP_FP_INT_TYPE>::sortMaxUp(int axis, BP_FP_INT_TYPE edge, btDispatcher* /* dispatcher */, bool updateOverlaps)
{
	Edge* pEdge = m_pEdges[axis] + edge;
	Edge* pNext = pEdge + 1;
	Handle* pHandleEdge = getHandle(pEdge->m_handle);

	while (pNext->m_handle && (pEdge->m_pos >= pNext->m_pos))
	{
		Handle* pHandleNext = getHandle(pNext->m_handle);

		const int axis1 = (1  << axis) & 3;
		const int axis2 = (1  << axis1) & 3;

		if (!pNext->IsMax())
		{
			// if next edge is a minimum check the bounds and add an overlap if necessary
			if (updateOverlaps && testOverlap2D(pHandleEdge, pHandleNext,axis1,axis2))
			{
				Handle* handle0 = getHandle(pEdge->m_handle);
				Handle* handle1 = getHandle(pNext->m_handle);
				m_pairCache->addOverlappingPair(handle0,handle1);
				if (m_userPairCallback)
					m_userPairCallback->addOverlappingPair(handle0,handle1);
			}

			// update edge reference in other handle
			pHandleNext->m_minEdges[axis]--;
		}
		else
			pHandleNext->m_maxEdges[axis]--;

		pHandleEdge->m_maxEdges[axis]++;

		// swap the edges
		Edge swap = *pEdge;
		*pEdge = *pNext;
		*pNext = swap;

		// increment
		pEdge++;
		pNext++;
	}

}

#endif


text:
/*
Bullet Continuous Collision Detection and Physics Library
Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

#ifndef OVERLAPPING_PAIR_CALLBACK_H
#define OVERLAPPING_PAIR_CALLBACK_H

class btDispatcher;
struct btBroadphasePair;

/// The btOverlappingPairCallback class is an additional optional broadphase
/// user callback for adding/removing overlapping pairs, similar interface to
/// btOverlappingPairCache.
class btOverlappingPairCallback
{
protected:
	btOverlappingPairCallback() {}

public:
	virtual ~btOverlappingPairCallback() { }

	virtual btBroadphasePair* addOverlappingPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1) = 0;
	virtual void* removeOverlappingPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1, btDispatcher* dispatcher) = 0;
	virtual void removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy0, btDispatcher* dispatcher) = 0;
};

#endif //OVERLAPPING_PAIR_CALLBACK_H