== SoC Bullet - Bullet Upgrade to 2.76 ==
authorJoshua Leung <aligorith@gmail.com>
Thu, 17 Jun 2010 02:42:43 +0000 (02:42 +0000)
committerJoshua Leung <aligorith@gmail.com>
Thu, 17 Jun 2010 02:42:43 +0000 (02:42 +0000)
Updated Blender's Bullet to 2.76 in this branch only.

This update was done by:
1) deleting the contents of the existing extern/bullet2/src directory (leaving the .svn folder in place),
2) copy/pasting the contents of the bullet/src directory (from unzipped Bullet archive) into this newly cleared folder.

Hopefully there aren't any patches that are still needed from the Bullet we had in source.

---

Note: I didn't use Moguri's patch, since that was giving me compile errors with headers not being able to be found.

[[Split portion of a mixed commit.]]

384 files changed:
extern/bullet2/Bullet-C-Api.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btAxisSweep3.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btAxisSweep3.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btBroadphaseInterface.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btBroadphaseProxy.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btBroadphaseProxy.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btDbvt.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btDbvt.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btDbvtBroadphase.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btDbvtBroadphase.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btDispatcher.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btDispatcher.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btMultiSapBroadphase.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btMultiSapBroadphase.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btOverlappingPairCache.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btOverlappingPairCache.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btOverlappingPairCallback.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btQuantizedBvh.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btQuantizedBvh.h [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btSimpleBroadphase.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/BroadphaseCollision/btSimpleBroadphase.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CMakeLists.txt [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/SphereTriangleDetector.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/SphereTriangleDetector.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btActivatingCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btActivatingCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btBox2dBox2dCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btBox2dBox2dCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btBoxBoxCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btBoxBoxCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btBoxBoxDetector.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btBoxBoxDetector.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCollisionConfiguration.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCollisionCreateFunc.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCollisionDispatcher.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCollisionDispatcher.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCollisionObject.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCollisionObject.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCollisionWorld.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCollisionWorld.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCompoundCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btCompoundCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btConvex2dConvex2dAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btConvex2dConvex2dAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btConvexConcaveCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btConvexConcaveCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btConvexConvexAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btConvexConvexAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btConvexPlaneCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btConvexPlaneCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btDefaultCollisionConfiguration.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btDefaultCollisionConfiguration.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btEmptyCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btEmptyCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btGhostObject.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btGhostObject.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btInternalEdgeUtility.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btInternalEdgeUtility.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btManifoldResult.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btManifoldResult.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btSimulationIslandManager.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btSimulationIslandManager.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btSphereBoxCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btSphereBoxCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btSphereSphereCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btSphereSphereCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btSphereTriangleCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btSphereTriangleCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btUnionFind.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionDispatch/btUnionFind.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btBox2dShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btBox2dShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btBoxShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btBoxShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btBvhTriangleMeshShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btBvhTriangleMeshShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btCapsuleShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btCapsuleShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btCollisionMargin.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btCollisionShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btCollisionShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btCompoundShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btCompoundShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConcaveShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConcaveShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConeShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConeShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvex2dShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvex2dShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexHullShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexHullShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexInternalShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexInternalShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexPointCloudShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexPointCloudShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexTriangleMeshShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btConvexTriangleMeshShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btCylinderShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btCylinderShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btEmptyShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btEmptyShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btMaterial.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btMinkowskiSumShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btMinkowskiSumShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btMultiSphereShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btMultiSphereShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btMultimaterialTriangleMeshShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btMultimaterialTriangleMeshShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btOptimizedBvh.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btOptimizedBvh.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btPolyhedralConvexShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btPolyhedralConvexShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btScaledBvhTriangleMeshShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btScaledBvhTriangleMeshShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btShapeHull.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btShapeHull.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btSphereShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btSphereShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btStaticPlaneShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btStaticPlaneShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btStridingMeshInterface.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btStridingMeshInterface.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTetrahedronShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTetrahedronShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleBuffer.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleBuffer.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleCallback.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleCallback.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleIndexVertexArray.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleIndexVertexArray.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleIndexVertexMaterialArray.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleIndexVertexMaterialArray.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleInfoMap.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleMesh.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleMesh.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleMeshShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleMeshShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btTriangleShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btUniformScalingShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/CollisionShapes/btUniformScalingShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Doxyfile [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btBoxCollision.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btClipPolygon.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btContactProcessing.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btContactProcessing.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGImpactBvh.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGImpactBvh.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGImpactCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGImpactCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGImpactMassUtil.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGImpactQuantizedBvh.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGImpactQuantizedBvh.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGImpactShape.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGImpactShape.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGenericPoolAllocator.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGenericPoolAllocator.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btGeometryOperations.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btQuantization.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btTriangleShapeEx.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/btTriangleShapeEx.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_array.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_basic_geometry_operations.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_bitset.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_box_collision.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_box_set.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_box_set.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_clip_polygon.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_contact.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_contact.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_geom_types.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_geometry.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_hash_table.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_linear_math.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_math.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_memory.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_memory.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_radixsort.h [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_tri_collision.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/Gimpact/gim_tri_collision.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btContinuousConvexCollision.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btContinuousConvexCollision.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btConvexCast.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btConvexCast.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btConvexPenetrationDepthSolver.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btDiscreteCollisionDetectorInterface.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btGjkConvexCast.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btGjkConvexCast.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btGjkEpa2.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btGjkEpa2.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btGjkEpaPenetrationDepthSolver.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btGjkEpaPenetrationDepthSolver.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btGjkPairDetector.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btGjkPairDetector.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btManifoldPoint.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btMinkowskiPenetrationDepthSolver.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btMinkowskiPenetrationDepthSolver.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btPersistentManifold.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btPersistentManifold.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btPointCollector.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btRaycastCallback.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btRaycastCallback.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btSimplexSolverInterface.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btSubSimplexConvexCast.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btSubSimplexConvexCast.h [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btVoronoiSimplexSolver.cpp [new file with mode: 0644]
extern/bullet2/BulletCollision/NarrowPhaseCollision/btVoronoiSimplexSolver.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/CMakeLists.txt [new file with mode: 0644]
extern/bullet2/BulletDynamics/Character/btCharacterControllerInterface.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Character/btKinematicCharacterController.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/Character/btKinematicCharacterController.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btConeTwistConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btConeTwistConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btConstraintSolver.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btContactConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btContactConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btContactSolverInfo.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btGeneric6DofConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btGeneric6DofConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btGeneric6DofSpringConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btGeneric6DofSpringConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btHinge2Constraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btHinge2Constraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btHingeConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btHingeConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btJacobianEntry.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btPoint2PointConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btPoint2PointConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btSequentialImpulseConstraintSolver.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btSequentialImpulseConstraintSolver.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btSliderConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btSliderConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btSolve2LinearConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btSolve2LinearConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btSolverBody.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btSolverConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btTypedConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btTypedConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btUniversalConstraint.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/ConstraintSolver/btUniversalConstraint.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/Bullet-C-API.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btActionInterface.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btContinuousDynamicsWorld.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btContinuousDynamicsWorld.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btDiscreteDynamicsWorld.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btDiscreteDynamicsWorld.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btDynamicsWorld.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btRigidBody.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btRigidBody.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btSimpleDynamicsWorld.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/Dynamics/btSimpleDynamicsWorld.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Vehicle/btRaycastVehicle.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/Vehicle/btRaycastVehicle.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Vehicle/btVehicleRaycaster.h [new file with mode: 0644]
extern/bullet2/BulletDynamics/Vehicle/btWheelInfo.cpp [new file with mode: 0644]
extern/bullet2/BulletDynamics/Vehicle/btWheelInfo.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/CMakeLists.txt [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/Makefile.original [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/MiniCL.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/MiniCLTask/MiniCLTask.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/MiniCLTask/MiniCLTask.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/MiniCLTaskScheduler.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/MiniCLTaskScheduler.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/PlatformDefinitions.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/PosixThreadSupport.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/PosixThreadSupport.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/PpuAddressSpace.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SequentialThreadSupport.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SequentialThreadSupport.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuCollisionObjectWrapper.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuCollisionObjectWrapper.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuCollisionTaskProcess.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuCollisionTaskProcess.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuContactManifoldCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuContactManifoldCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuDoubleBuffer.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuFakeDma.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuFakeDma.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuGatheringCollisionDispatcher.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuGatheringCollisionDispatcher.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuLibspe2Support.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuLibspe2Support.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/Box.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuCollisionShapes.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuCollisionShapes.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuContactResult.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuContactResult.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuConvexPenetrationDepthSolver.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuGatheringCollisionTask.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuGatheringCollisionTask.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuLocalSupport.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuMinkowskiPenetrationDepthSolver.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuMinkowskiPenetrationDepthSolver.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/SpuPreferredPenetrationDirections.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/boxBoxDistance.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/boxBoxDistance.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuNarrowPhaseCollisionTask/readme.txt [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuSampleTask/SpuSampleTask.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuSampleTask/SpuSampleTask.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuSampleTask/readme.txt [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuSampleTaskProcess.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuSampleTaskProcess.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/SpuSync.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/Win32ThreadSupport.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/Win32ThreadSupport.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btGpu3DGridBroadphase.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btGpu3DGridBroadphase.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btGpu3DGridBroadphaseSharedCode.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btGpu3DGridBroadphaseSharedDefs.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btGpu3DGridBroadphaseSharedTypes.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btGpuDefines.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btGpuUtilsSharedCode.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btGpuUtilsSharedDefs.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btParallelConstraintSolver.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btParallelConstraintSolver.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btThreadSupportInterface.cpp [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/btThreadSupportInterface.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/vectormath/scalar/cpp/boolInVec.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/vectormath/scalar/cpp/floatInVec.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/vectormath/scalar/cpp/mat_aos.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/vectormath/scalar/cpp/quat_aos.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/vectormath/scalar/cpp/vec_aos.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/vectormath/scalar/cpp/vectormath_aos.h [new file with mode: 0644]
extern/bullet2/BulletMultiThreaded/vectormath2bullet.h [new file with mode: 0644]
extern/bullet2/BulletSoftBody/CMakeLists.txt [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftBody.cpp [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftBody.h [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftBodyConcaveCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftBodyConcaveCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftBodyHelpers.cpp [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftBodyHelpers.h [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftBodyInternals.h [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftBodyRigidBodyCollisionConfiguration.cpp [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftBodyRigidBodyCollisionConfiguration.h [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftRigidCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftRigidCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftRigidDynamicsWorld.cpp [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftRigidDynamicsWorld.h [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftSoftCollisionAlgorithm.cpp [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSoftSoftCollisionAlgorithm.h [new file with mode: 0644]
extern/bullet2/BulletSoftBody/btSparseSDF.h [new file with mode: 0644]
extern/bullet2/CMakeLists.txt
extern/bullet2/LinearMath/CMakeLists.txt [new file with mode: 0644]
extern/bullet2/LinearMath/btAabbUtil2.h [new file with mode: 0644]
extern/bullet2/LinearMath/btAlignedAllocator.cpp [new file with mode: 0644]
extern/bullet2/LinearMath/btAlignedAllocator.h [new file with mode: 0644]
extern/bullet2/LinearMath/btAlignedObjectArray.h [new file with mode: 0644]
extern/bullet2/LinearMath/btConvexHull.cpp [new file with mode: 0644]
extern/bullet2/LinearMath/btConvexHull.h [new file with mode: 0644]
extern/bullet2/LinearMath/btDefaultMotionState.h [new file with mode: 0644]
extern/bullet2/LinearMath/btGeometryUtil.cpp [new file with mode: 0644]
extern/bullet2/LinearMath/btGeometryUtil.h [new file with mode: 0644]
extern/bullet2/LinearMath/btHashMap.h [new file with mode: 0644]
extern/bullet2/LinearMath/btIDebugDraw.h [new file with mode: 0644]
extern/bullet2/LinearMath/btList.h [new file with mode: 0644]
extern/bullet2/LinearMath/btMatrix3x3.h [new file with mode: 0644]
extern/bullet2/LinearMath/btMinMax.h [new file with mode: 0644]
extern/bullet2/LinearMath/btMotionState.h [new file with mode: 0644]
extern/bullet2/LinearMath/btPoolAllocator.h [new file with mode: 0644]
extern/bullet2/LinearMath/btQuadWord.h [new file with mode: 0644]
extern/bullet2/LinearMath/btQuaternion.h [new file with mode: 0644]
extern/bullet2/LinearMath/btQuickprof.cpp [new file with mode: 0644]
extern/bullet2/LinearMath/btQuickprof.h [new file with mode: 0644]
extern/bullet2/LinearMath/btRandom.h [new file with mode: 0644]
extern/bullet2/LinearMath/btScalar.h [new file with mode: 0644]
extern/bullet2/LinearMath/btSerializer.cpp [new file with mode: 0644]
extern/bullet2/LinearMath/btSerializer.h [new file with mode: 0644]
extern/bullet2/LinearMath/btStackAlloc.h [new file with mode: 0644]
extern/bullet2/LinearMath/btTransform.h [new file with mode: 0644]
extern/bullet2/LinearMath/btTransformUtil.h [new file with mode: 0644]
extern/bullet2/LinearMath/btVector3.h [new file with mode: 0644]
extern/bullet2/Makefile
extern/bullet2/MiniCL/cl.h [new file with mode: 0644]
extern/bullet2/MiniCL/cl_MiniCL_Defs.h [new file with mode: 0644]
extern/bullet2/MiniCL/cl_gl.h [new file with mode: 0644]
extern/bullet2/MiniCL/cl_platform.h [new file with mode: 0644]
extern/bullet2/SConscript [new file with mode: 0644]
extern/bullet2/btBulletCollisionCommon.h [new file with mode: 0644]
extern/bullet2/btBulletDynamicsCommon.h [new file with mode: 0644]

diff --git a/extern/bullet2/Bullet-C-Api.h b/extern/bullet2/Bullet-C-Api.h
new file mode 100644 (file)
index 0000000..f309aba
--- /dev/null
@@ -0,0 +1,176 @@
+/*
+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.
+*/
+
+/*
+       Draft high-level generic physics C-API. For low-level access, use the physics SDK native API's.
+       Work in progress, functionality will be added on demand.
+
+       If possible, use the richer Bullet C++ API, by including "btBulletDynamicsCommon.h"
+*/
+
+#ifndef BULLET_C_API_H
+#define BULLET_C_API_H
+
+#define PL_DECLARE_HANDLE(name) typedef struct name##__ { int unused; } *name
+
+#ifdef BT_USE_DOUBLE_PRECISION
+typedef double plReal;
+#else
+typedef float  plReal;
+#endif
+
+typedef plReal plVector3[3];
+typedef plReal plQuaternion[4];
+
+#ifdef __cplusplus
+extern "C" { 
+#endif
+
+/**    Particular physics SDK (C-API) */
+       PL_DECLARE_HANDLE(plPhysicsSdkHandle);
+
+/**    Dynamics world, belonging to some physics SDK (C-API)*/
+       PL_DECLARE_HANDLE(plDynamicsWorldHandle);
+
+/** Rigid Body that can be part of a Dynamics World (C-API)*/  
+       PL_DECLARE_HANDLE(plRigidBodyHandle);
+
+/**    Collision Shape/Geometry, property of a Rigid Body (C-API)*/
+       PL_DECLARE_HANDLE(plCollisionShapeHandle);
+
+/** Constraint for Rigid Bodies (C-API)*/
+       PL_DECLARE_HANDLE(plConstraintHandle);
+
+/** Triangle Mesh interface (C-API)*/
+       PL_DECLARE_HANDLE(plMeshInterfaceHandle);
+
+/** Broadphase Scene/Proxy Handles (C-API)*/
+       PL_DECLARE_HANDLE(plCollisionBroadphaseHandle);
+       PL_DECLARE_HANDLE(plBroadphaseProxyHandle);
+       PL_DECLARE_HANDLE(plCollisionWorldHandle);
+
+/**
+       Create and Delete a Physics SDK 
+*/
+
+       extern  plPhysicsSdkHandle      plNewBulletSdk(); //this could be also another sdk, like ODE, PhysX etc.
+       extern  void            plDeletePhysicsSdk(plPhysicsSdkHandle   physicsSdk);
+
+/** Collision World, not strictly necessary, you can also just create a Dynamics World with Rigid Bodies which internally manages the Collision World with Collision Objects */
+
+       typedef void(*btBroadphaseCallback)(void* clientData, void* object1,void* object2);
+
+       extern plCollisionBroadphaseHandle      plCreateSapBroadphase(btBroadphaseCallback beginCallback,btBroadphaseCallback endCallback);
+
+       extern void     plDestroyBroadphase(plCollisionBroadphaseHandle bp);
+
+       extern  plBroadphaseProxyHandle plCreateProxy(plCollisionBroadphaseHandle bp, void* clientData, plReal minX,plReal minY,plReal minZ, plReal maxX,plReal maxY, plReal maxZ);
+
+       extern void plDestroyProxy(plCollisionBroadphaseHandle bp, plBroadphaseProxyHandle proxyHandle);
+
+       extern void plSetBoundingBox(plBroadphaseProxyHandle proxyHandle, plReal minX,plReal minY,plReal minZ, plReal maxX,plReal maxY, plReal maxZ);
+
+/* todo: add pair cache support with queries like add/remove/find pair */
+       
+       extern plCollisionWorldHandle plCreateCollisionWorld(plPhysicsSdkHandle physicsSdk);
+
+/* todo: add/remove objects */
+       
+
+/* Dynamics World */
+
+       extern  plDynamicsWorldHandle plCreateDynamicsWorld(plPhysicsSdkHandle physicsSdk);
+
+       extern  void           plDeleteDynamicsWorld(plDynamicsWorldHandle world);
+
+       extern  void    plStepSimulation(plDynamicsWorldHandle, plReal  timeStep);
+
+       extern  void plAddRigidBody(plDynamicsWorldHandle world, plRigidBodyHandle object);
+
+       extern  void plRemoveRigidBody(plDynamicsWorldHandle world, plRigidBodyHandle object);
+
+
+/* Rigid Body  */
+
+       extern  plRigidBodyHandle plCreateRigidBody(    void* user_data,  float mass, plCollisionShapeHandle cshape );
+
+       extern  void plDeleteRigidBody(plRigidBodyHandle body);
+
+
+/* Collision Shape definition */
+
+       extern  plCollisionShapeHandle plNewSphereShape(plReal radius);
+       extern  plCollisionShapeHandle plNewBoxShape(plReal x, plReal y, plReal z);
+       extern  plCollisionShapeHandle plNewCapsuleShape(plReal radius, plReal height); 
+       extern  plCollisionShapeHandle plNewConeShape(plReal radius, plReal height);
+       extern  plCollisionShapeHandle plNewCylinderShape(plReal radius, plReal height);
+       extern  plCollisionShapeHandle plNewCompoundShape();
+       extern  void    plAddChildShape(plCollisionShapeHandle compoundShape,plCollisionShapeHandle childShape, plVector3 childPos,plQuaternion childOrn);
+
+       extern  void plDeleteShape(plCollisionShapeHandle shape);
+
+       /* Convex Meshes */
+       extern  plCollisionShapeHandle plNewConvexHullShape();
+       extern  void            plAddVertex(plCollisionShapeHandle convexHull, plReal x,plReal y,plReal z);
+/* Concave static triangle meshes */
+       extern  plMeshInterfaceHandle              plNewMeshInterface();
+       extern  void            plAddTriangle(plMeshInterfaceHandle meshHandle, plVector3 v0,plVector3 v1,plVector3 v2);
+       extern  plCollisionShapeHandle plNewStaticTriangleMeshShape(plMeshInterfaceHandle);
+
+       extern  void plSetScaling(plCollisionShapeHandle shape, plVector3 scaling);
+
+/* SOLID has Response Callback/Table/Management */
+/* PhysX has Triggers, User Callbacks and filtering */
+/* ODE has the typedef void dNearCallback (void *data, dGeomID o1, dGeomID o2); */
+
+/*     typedef void plUpdatedPositionCallback(void* userData, plRigidBodyHandle        rbHandle, plVector3 pos); */
+/*     typedef void plUpdatedOrientationCallback(void* userData, plRigidBodyHandle     rbHandle, plQuaternion orientation); */
+
+       /* get world transform */
+       extern void     plGetOpenGLMatrix(plRigidBodyHandle object, plReal* matrix);
+       extern void     plGetPosition(plRigidBodyHandle object,plVector3 position);
+       extern void plGetOrientation(plRigidBodyHandle object,plQuaternion orientation);
+
+       /* set world transform (position/orientation) */
+       extern  void plSetPosition(plRigidBodyHandle object, const plVector3 position);
+       extern  void plSetOrientation(plRigidBodyHandle object, const plQuaternion orientation);
+       extern  void plSetEuler(plReal yaw,plReal pitch,plReal roll, plQuaternion orient);
+       extern  void plSetOpenGLMatrix(plRigidBodyHandle object, plReal* matrix);
+
+       typedef struct plRayCastResult {
+               plRigidBodyHandle               m_body;  
+               plCollisionShapeHandle  m_shape;                
+               plVector3                               m_positionWorld;                
+               plVector3                               m_normalWorld;
+       } plRayCastResult;
+
+       extern  int plRayCast(plDynamicsWorldHandle world, const plVector3 rayStart, const plVector3 rayEnd, plRayCastResult res);
+
+       /* Sweep API */
+
+       /* extern  plRigidBodyHandle plObjectCast(plDynamicsWorldHandle world, const plVector3 rayStart, const plVector3 rayEnd, plVector3 hitpoint, plVector3 normal); */
+
+       /* Continuous Collision Detection API */
+       
+       // needed for source/blender/blenkernel/intern/collision.c
+       double plNearestPoints(float p1[3], float p2[3], float p3[3], float q1[3], float q2[3], float q3[3], float *pa, float *pb, float normal[3]);
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif //BULLET_C_API_H
+
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btAxisSweep3.cpp b/extern/bullet2/BulletCollision/BroadphaseCollision/btAxisSweep3.cpp
new file mode 100644 (file)
index 0000000..7776330
--- /dev/null
@@ -0,0 +1,37 @@
+
+//Bullet Continuous Collision Detection and Physics Library
+//Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
+
+
+//
+// btAxisSweep3
+//
+// 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.
+#include "btAxisSweep3.h"
+
+
+btAxisSweep3::btAxisSweep3(const btVector3& worldAabbMin,const btVector3& worldAabbMax, unsigned short int maxHandles, btOverlappingPairCache* pairCache, bool disableRaycastAccelerator)
+:btAxisSweep3Internal<unsigned short int>(worldAabbMin,worldAabbMax,0xfffe,0xffff,maxHandles,pairCache,disableRaycastAccelerator)
+{
+       // 1 handle is reserved as sentinel
+       btAssert(maxHandles > 1 && maxHandles < 32767);
+
+}
+
+
+bt32BitAxisSweep3::bt32BitAxisSweep3(const btVector3& worldAabbMin,const btVector3& worldAabbMax, unsigned int maxHandles , btOverlappingPairCache* pairCache , bool disableRaycastAccelerator)
+:btAxisSweep3Internal<unsigned int>(worldAabbMin,worldAabbMax,0xfffffffe,0x7fffffff,maxHandles,pairCache,disableRaycastAccelerator)
+{
+       // 1 handle is reserved as sentinel
+       btAssert(maxHandles > 1 && maxHandles < 2147483647);
+}
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btAxisSweep3.h b/extern/bullet2/BulletCollision/BroadphaseCollision/btAxisSweep3.h
new file mode 100644 (file)
index 0000000..07167af
--- /dev/null
@@ -0,0 +1,1051 @@
+//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 AXIS_SWEEP_3_H
+#define AXIS_SWEEP_3_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,short int collisionFilterGroup,short int collisionFilterMask,btDispatcher* dispatcher,void* multiSapProxy);
+       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 ,short int collisionFilterGroup,short int collisionFilterMask,btDispatcher* dispatcher,void* multiSapProxy);
+       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,short int collisionFilterGroup,short int collisionFilterMask,btDispatcher* dispatcher,void* multiSapProxy)
+{
+               (void)shapeType;
+               BP_FP_INT_TYPE handleId = addHandle(aabbMin,aabbMax, userPtr,collisionFilterGroup,collisionFilterMask,dispatcher,multiSapProxy);
+               
+               Handle* handle = getHandle(handleId);
+               
+               if (m_raycastAccelerator)
+               {
+                       btBroadphaseProxy* rayProxy = m_raycastAccelerator->createProxy(aabbMin,aabbMax,shapeType,userPtr,collisionFilterGroup,collisionFilterMask,dispatcher,0);
+                       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,short int collisionFilterGroup,short int collisionFilterMask,btDispatcher* dispatcher,void* multiSapProxy)
+{
+       // 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;
+       pHandle->m_multiSapParentProxy = multiSapProxy;
+
+       // 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++;
+       }
+       
+}
+
+
+
+////////////////////////////////////////////////////////////////////
+
+
+/// The btAxisSweep3 is an efficient implementation of the 3d axis sweep and prune broadphase.
+/// It uses arrays rather then lists for storage of the 3 axis. Also it operates using 16 bit integer coordinates instead of floats.
+/// For large worlds and many objects, use bt32BitAxisSweep3 or btDbvtBroadphase instead. bt32BitAxisSweep3 has higher precision and allows more then 16384 objects at the cost of more memory and bit of performance.
+class btAxisSweep3 : public btAxisSweep3Internal<unsigned short int>
+{
+public:
+
+       btAxisSweep3(const btVector3& worldAabbMin,const btVector3& worldAabbMax, unsigned short int maxHandles = 16384, btOverlappingPairCache* pairCache = 0, bool disableRaycastAccelerator = false);
+
+};
+
+/// The bt32BitAxisSweep3 allows higher precision quantization and more objects compared to the btAxisSweep3 sweep and prune.
+/// This comes at the cost of more memory per handle, and a bit slower performance.
+/// It uses arrays rather then lists for storage of the 3 axis.
+class bt32BitAxisSweep3 : public btAxisSweep3Internal<unsigned int>
+{
+public:
+
+       bt32BitAxisSweep3(const btVector3& worldAabbMin,const btVector3& worldAabbMax, unsigned int maxHandles = 1500000, btOverlappingPairCache* pairCache = 0, bool disableRaycastAccelerator = false);
+
+};
+
+#endif
+
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btBroadphaseInterface.h b/extern/bullet2/BulletCollision/BroadphaseCollision/btBroadphaseInterface.h
new file mode 100644 (file)
index 0000000..fe414ef
--- /dev/null
@@ -0,0 +1,82 @@
+/*
+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                BROADPHASE_INTERFACE_H
+#define        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() {}
+};
+
+#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, short int collisionFilterGroup,short int collisionFilterMask, btDispatcher* dispatcher,void* multiSapProxy) =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/reproducability
+       virtual void resetPool(btDispatcher* dispatcher) { (void) dispatcher; };
+
+       virtual void    printStats() = 0;
+
+};
+
+#endif //BROADPHASE_INTERFACE_H
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btBroadphaseProxy.cpp b/extern/bullet2/BulletCollision/BroadphaseCollision/btBroadphaseProxy.cpp
new file mode 100644 (file)
index 0000000..f4d7341
--- /dev/null
@@ -0,0 +1,17 @@
+/*
+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.
+*/
+
+#include "btBroadphaseProxy.h"
+
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btBroadphaseProxy.h b/extern/bullet2/BulletCollision/BroadphaseCollision/btBroadphaseProxy.h
new file mode 100644 (file)
index 0000000..62d3497
--- /dev/null
@@ -0,0 +1,270 @@
+/*
+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 BROADPHASE_PROXY_H
+#define BROADPHASE_PROXY_H
+
+#include "LinearMath/btScalar.h" //for SIMD_FORCE_INLINE
+#include "LinearMath/btVector3.h"
+#include "LinearMath/btAlignedAllocator.h"
+
+
+/// btDispatcher uses these types
+/// IMPORTANT NOTE:The types are ordered polyhedral, implicit convex and concave
+/// to facilitate type checking
+/// CUSTOM_POLYHEDRAL_SHAPE_TYPE,CUSTOM_CONVEX_SHAPE_TYPE and CUSTOM_CONCAVE_SHAPE_TYPE can be used to extend Bullet without modifying source code
+enum BroadphaseNativeTypes
+{
+       // polyhedral convex shapes
+       BOX_SHAPE_PROXYTYPE,
+       TRIANGLE_SHAPE_PROXYTYPE,
+       TETRAHEDRAL_SHAPE_PROXYTYPE,
+       CONVEX_TRIANGLEMESH_SHAPE_PROXYTYPE,
+       CONVEX_HULL_SHAPE_PROXYTYPE,
+       CONVEX_POINT_CLOUD_SHAPE_PROXYTYPE,
+       CUSTOM_POLYHEDRAL_SHAPE_TYPE,
+//implicit convex shapes
+IMPLICIT_CONVEX_SHAPES_START_HERE,
+       SPHERE_SHAPE_PROXYTYPE,
+       MULTI_SPHERE_SHAPE_PROXYTYPE,
+       CAPSULE_SHAPE_PROXYTYPE,
+       CONE_SHAPE_PROXYTYPE,
+       CONVEX_SHAPE_PROXYTYPE,
+       CYLINDER_SHAPE_PROXYTYPE,
+       UNIFORM_SCALING_SHAPE_PROXYTYPE,
+       MINKOWSKI_SUM_SHAPE_PROXYTYPE,
+       MINKOWSKI_DIFFERENCE_SHAPE_PROXYTYPE,
+       BOX_2D_SHAPE_PROXYTYPE,
+       CONVEX_2D_SHAPE_PROXYTYPE,
+       CUSTOM_CONVEX_SHAPE_TYPE,
+//concave shapes
+CONCAVE_SHAPES_START_HERE,
+       //keep all the convex shapetype below here, for the check IsConvexShape in broadphase proxy!
+       TRIANGLE_MESH_SHAPE_PROXYTYPE,
+       SCALED_TRIANGLE_MESH_SHAPE_PROXYTYPE,
+       ///used for demo integration FAST/Swift collision library and Bullet
+       FAST_CONCAVE_MESH_PROXYTYPE,
+       //terrain
+       TERRAIN_SHAPE_PROXYTYPE,
+///Used for GIMPACT Trimesh integration
+       GIMPACT_SHAPE_PROXYTYPE,
+///Multimaterial mesh
+    MULTIMATERIAL_TRIANGLE_MESH_PROXYTYPE,
+       
+       EMPTY_SHAPE_PROXYTYPE,
+       STATIC_PLANE_PROXYTYPE,
+       CUSTOM_CONCAVE_SHAPE_TYPE,
+CONCAVE_SHAPES_END_HERE,
+
+       COMPOUND_SHAPE_PROXYTYPE,
+
+       SOFTBODY_SHAPE_PROXYTYPE,
+       HFFLUID_SHAPE_PROXYTYPE,
+       HFFLUID_BUOYANT_CONVEX_SHAPE_PROXYTYPE,
+       INVALID_SHAPE_PROXYTYPE,
+
+       MAX_BROADPHASE_COLLISION_TYPES
+       
+};
+
+
+///The btBroadphaseProxy is the main class that can be used with the Bullet broadphases. 
+///It stores collision shape type information, collision filter information and a client object, typically a btCollisionObject or btRigidBody.
+ATTRIBUTE_ALIGNED16(struct) btBroadphaseProxy
+{
+
+BT_DECLARE_ALIGNED_ALLOCATOR();
+       
+       ///optional filtering to cull potential collisions
+       enum CollisionFilterGroups
+       {
+               DefaultFilter = 1,
+               StaticFilter = 2,
+               KinematicFilter = 4,
+               DebrisFilter = 8,
+                       SensorTrigger = 16,
+                       CharacterFilter = 32,
+               AllFilter = -1 //all bits sets: DefaultFilter | StaticFilter | KinematicFilter | DebrisFilter | SensorTrigger
+       };
+
+       //Usually the client btCollisionObject or Rigidbody class
+       void*   m_clientObject;
+       short int m_collisionFilterGroup;
+       short int m_collisionFilterMask;
+       void*   m_multiSapParentProxy;          
+       int                     m_uniqueId;//m_uniqueId is introduced for paircache. could get rid of this, by calculating the address offset etc.
+
+       btVector3       m_aabbMin;
+       btVector3       m_aabbMax;
+
+       SIMD_FORCE_INLINE int getUid() const
+       {
+               return m_uniqueId;
+       }
+
+       //used for memory pools
+       btBroadphaseProxy() :m_clientObject(0),m_multiSapParentProxy(0)
+       {
+       }
+
+       btBroadphaseProxy(const btVector3& aabbMin,const btVector3& aabbMax,void* userPtr,short int collisionFilterGroup, short int collisionFilterMask,void* multiSapParentProxy=0)
+               :m_clientObject(userPtr),
+               m_collisionFilterGroup(collisionFilterGroup),
+               m_collisionFilterMask(collisionFilterMask),
+               m_aabbMin(aabbMin),
+               m_aabbMax(aabbMax)
+       {
+               m_multiSapParentProxy = multiSapParentProxy;
+       }
+
+       
+
+       static SIMD_FORCE_INLINE bool isPolyhedral(int proxyType)
+       {
+               return (proxyType  < IMPLICIT_CONVEX_SHAPES_START_HERE);
+       }
+
+       static SIMD_FORCE_INLINE bool   isConvex(int proxyType)
+       {
+               return (proxyType < CONCAVE_SHAPES_START_HERE);
+       }
+
+       static SIMD_FORCE_INLINE bool   isNonMoving(int proxyType)
+       {
+               return (isConcave(proxyType) && !(proxyType==GIMPACT_SHAPE_PROXYTYPE));
+       }
+
+       static SIMD_FORCE_INLINE bool   isConcave(int proxyType)
+       {
+               return ((proxyType > CONCAVE_SHAPES_START_HERE) &&
+                       (proxyType < CONCAVE_SHAPES_END_HERE));
+       }
+       static SIMD_FORCE_INLINE bool   isCompound(int proxyType)
+       {
+               return (proxyType == COMPOUND_SHAPE_PROXYTYPE);
+       }
+
+       static SIMD_FORCE_INLINE bool   isSoftBody(int proxyType)
+       {
+               return (proxyType == SOFTBODY_SHAPE_PROXYTYPE);
+       }
+
+       static SIMD_FORCE_INLINE bool isInfinite(int proxyType)
+       {
+               return (proxyType == STATIC_PLANE_PROXYTYPE);
+       }
+
+       static SIMD_FORCE_INLINE bool isConvex2d(int proxyType)
+       {
+               return (proxyType == BOX_2D_SHAPE_PROXYTYPE) || (proxyType == CONVEX_2D_SHAPE_PROXYTYPE);
+       }
+
+       
+}
+;
+
+class btCollisionAlgorithm;
+
+struct btBroadphaseProxy;
+
+
+
+///The btBroadphasePair class contains a pair of aabb-overlapping objects.
+///A btDispatcher can search a btCollisionAlgorithm that performs exact/narrowphase collision detection on the actual collision shapes.
+ATTRIBUTE_ALIGNED16(struct) btBroadphasePair
+{
+       btBroadphasePair ()
+               :
+       m_pProxy0(0),
+               m_pProxy1(0),
+               m_algorithm(0),
+               m_internalInfo1(0)
+       {
+       }
+
+BT_DECLARE_ALIGNED_ALLOCATOR();
+
+       btBroadphasePair(const btBroadphasePair& other)
+               :               m_pProxy0(other.m_pProxy0),
+                               m_pProxy1(other.m_pProxy1),
+                               m_algorithm(other.m_algorithm),
+                               m_internalInfo1(other.m_internalInfo1)
+       {
+       }
+       btBroadphasePair(btBroadphaseProxy& proxy0,btBroadphaseProxy& proxy1)
+       {
+
+               //keep them sorted, so the std::set operations work
+               if (proxy0.m_uniqueId < proxy1.m_uniqueId)
+        { 
+            m_pProxy0 = &proxy0; 
+            m_pProxy1 = &proxy1; 
+        }
+        else 
+        { 
+                       m_pProxy0 = &proxy1; 
+            m_pProxy1 = &proxy0; 
+        }
+
+               m_algorithm = 0;
+               m_internalInfo1 = 0;
+
+       }
+       
+       btBroadphaseProxy* m_pProxy0;
+       btBroadphaseProxy* m_pProxy1;
+       
+       mutable btCollisionAlgorithm* m_algorithm;
+       union { void* m_internalInfo1; int m_internalTmpValue;};//don't use this data, it will be removed in future version.
+
+};
+
+/*
+//comparison for set operation, see Solid DT_Encounter
+SIMD_FORCE_INLINE bool operator<(const btBroadphasePair& a, const btBroadphasePair& b) 
+{ 
+    return a.m_pProxy0 < b.m_pProxy0 || 
+        (a.m_pProxy0 == b.m_pProxy0 && a.m_pProxy1 < b.m_pProxy1); 
+}
+*/
+
+
+
+class btBroadphasePairSortPredicate
+{
+       public:
+
+               bool operator() ( const btBroadphasePair& a, const btBroadphasePair& b )
+               {
+                       const int uidA0 = a.m_pProxy0 ? a.m_pProxy0->m_uniqueId : -1;
+                       const int uidB0 = b.m_pProxy0 ? b.m_pProxy0->m_uniqueId : -1;
+                       const int uidA1 = a.m_pProxy1 ? a.m_pProxy1->m_uniqueId : -1;
+                       const int uidB1 = b.m_pProxy1 ? b.m_pProxy1->m_uniqueId : -1;
+
+                        return uidA0 > uidB0 || 
+                               (a.m_pProxy0 == b.m_pProxy0 && uidA1 > uidB1) ||
+                               (a.m_pProxy0 == b.m_pProxy0 && a.m_pProxy1 == b.m_pProxy1 && a.m_algorithm > b.m_algorithm); 
+               }
+};
+
+
+SIMD_FORCE_INLINE bool operator==(const btBroadphasePair& a, const btBroadphasePair& b) 
+{
+        return (a.m_pProxy0 == b.m_pProxy0) && (a.m_pProxy1 == b.m_pProxy1);
+}
+
+
+#endif //BROADPHASE_PROXY_H
+
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btCollisionAlgorithm.cpp b/extern/bullet2/BulletCollision/BroadphaseCollision/btCollisionAlgorithm.cpp
new file mode 100644 (file)
index 0000000..c95d1be
--- /dev/null
@@ -0,0 +1,23 @@
+/*
+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.
+*/
+
+#include "btCollisionAlgorithm.h"
+#include "btDispatcher.h"
+
+btCollisionAlgorithm::btCollisionAlgorithm(const btCollisionAlgorithmConstructionInfo& ci)
+{
+       m_dispatcher = ci.m_dispatcher1;
+}
+
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btCollisionAlgorithm.h b/extern/bullet2/BulletCollision/BroadphaseCollision/btCollisionAlgorithm.h
new file mode 100644 (file)
index 0000000..1618ad9
--- /dev/null
@@ -0,0 +1,80 @@
+/*
+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 COLLISION_ALGORITHM_H
+#define COLLISION_ALGORITHM_H
+
+#include "LinearMath/btScalar.h"
+#include "LinearMath/btAlignedObjectArray.h"
+
+struct btBroadphaseProxy;
+class btDispatcher;
+class btManifoldResult;
+class btCollisionObject;
+struct btDispatcherInfo;
+class  btPersistentManifold;
+
+typedef btAlignedObjectArray<btPersistentManifold*>    btManifoldArray;
+
+struct btCollisionAlgorithmConstructionInfo
+{
+       btCollisionAlgorithmConstructionInfo()
+               :m_dispatcher1(0),
+               m_manifold(0)
+       {
+       }
+       btCollisionAlgorithmConstructionInfo(btDispatcher* dispatcher,int temp)
+               :m_dispatcher1(dispatcher)
+       {
+               (void)temp;
+       }
+
+       btDispatcher*   m_dispatcher1;
+       btPersistentManifold*   m_manifold;
+
+       int     getDispatcherId();
+
+};
+
+
+///btCollisionAlgorithm is an collision interface that is compatible with the Broadphase and btDispatcher.
+///It is persistent over frames
+class btCollisionAlgorithm
+{
+
+protected:
+
+       btDispatcher*   m_dispatcher;
+
+protected:
+       int     getDispatcherId();
+       
+public:
+
+       btCollisionAlgorithm() {};
+
+       btCollisionAlgorithm(const btCollisionAlgorithmConstructionInfo& ci);
+
+       virtual ~btCollisionAlgorithm() {};
+
+       virtual void processCollision (btCollisionObject* body0,btCollisionObject* body1,const btDispatcherInfo& dispatchInfo,btManifoldResult* resultOut) = 0;
+
+       virtual btScalar calculateTimeOfImpact(btCollisionObject* body0,btCollisionObject* body1,const btDispatcherInfo& dispatchInfo,btManifoldResult* resultOut) = 0;
+
+       virtual void    getAllContactManifolds(btManifoldArray& manifoldArray) = 0;
+};
+
+
+#endif //COLLISION_ALGORITHM_H
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btDbvt.cpp b/extern/bullet2/BulletCollision/BroadphaseCollision/btDbvt.cpp
new file mode 100644 (file)
index 0000000..ff32ec1
--- /dev/null
@@ -0,0 +1,1295 @@
+/*
+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.
+*/
+///btDbvt implementation by Nathanael Presson
+
+#include "btDbvt.h"
+
+//
+typedef btAlignedObjectArray<btDbvtNode*>                      tNodeArray;
+typedef btAlignedObjectArray<const btDbvtNode*>        tConstNodeArray;
+
+//
+struct btDbvtNodeEnumerator : btDbvt::ICollide
+{
+       tConstNodeArray nodes;
+       void Process(const btDbvtNode* n) { nodes.push_back(n); }
+};
+
+//
+static DBVT_INLINE int                 indexof(const btDbvtNode* node)
+{
+       return(node->parent->childs[1]==node);
+}
+
+//
+static DBVT_INLINE btDbvtVolume        merge(  const btDbvtVolume& a,
+                                                                         const btDbvtVolume& b)
+{
+#if (DBVT_MERGE_IMPL==DBVT_IMPL_SSE)
+       ATTRIBUTE_ALIGNED16(char locals[sizeof(btDbvtAabbMm)]);
+       btDbvtVolume&   res=*(btDbvtVolume*)locals;
+#else
+               btDbvtVolume    res;
+#endif
+       Merge(a,b,res);
+       return(res);
+}
+
+// volume+edge lengths
+static DBVT_INLINE btScalar            size(const btDbvtVolume& a)
+{
+       const btVector3 edges=a.Lengths();
+       return( edges.x()*edges.y()*edges.z()+
+               edges.x()+edges.y()+edges.z());
+}
+
+//
+static void                                            getmaxdepth(const btDbvtNode* node,int depth,int& maxdepth)
+{
+       if(node->isinternal())
+       {
+               getmaxdepth(node->childs[0],depth+1,maxdepth);
+               getmaxdepth(node->childs[0],depth+1,maxdepth);
+       } else maxdepth=btMax(maxdepth,depth);
+}
+
+//
+static DBVT_INLINE void                        deletenode(     btDbvt* pdbvt,
+                                                                                  btDbvtNode* node)
+{
+       btAlignedFree(pdbvt->m_free);
+       pdbvt->m_free=node;
+}
+
+//
+static void                                            recursedeletenode(      btDbvt* pdbvt,
+                                                                                                 btDbvtNode* node)
+{
+       if(!node->isleaf())
+       {
+               recursedeletenode(pdbvt,node->childs[0]);
+               recursedeletenode(pdbvt,node->childs[1]);
+       }
+       if(node==pdbvt->m_root) pdbvt->m_root=0;
+       deletenode(pdbvt,node);
+}
+
+//
+static DBVT_INLINE btDbvtNode* createnode(     btDbvt* pdbvt,
+                                                                                  btDbvtNode* parent,
+                                                                                  void* data)
+{
+       btDbvtNode*     node;
+       if(pdbvt->m_free)
+       { node=pdbvt->m_free;pdbvt->m_free=0; }
+       else
+       { node=new(btAlignedAlloc(sizeof(btDbvtNode),16)) btDbvtNode(); }
+       node->parent    =       parent;
+       node->data              =       data;
+       node->childs[1] =       0;
+       return(node);
+}
+
+//
+static DBVT_INLINE btDbvtNode* createnode(     btDbvt* pdbvt,
+                                                                                  btDbvtNode* parent,
+                                                                                  const btDbvtVolume& volume,
+                                                                                  void* data)
+{
+       btDbvtNode*     node=createnode(pdbvt,parent,data);
+       node->volume=volume;
+       return(node);
+}
+
+//
+static DBVT_INLINE btDbvtNode* createnode(     btDbvt* pdbvt,
+                                                                                  btDbvtNode* parent,
+                                                                                  const btDbvtVolume& volume0,
+                                                                                  const btDbvtVolume& volume1,
+                                                                                  void* data)
+{
+       btDbvtNode*     node=createnode(pdbvt,parent,data);
+       Merge(volume0,volume1,node->volume);
+       return(node);
+}
+
+//
+static void                                            insertleaf(     btDbvt* pdbvt,
+                                                                                  btDbvtNode* root,
+                                                                                  btDbvtNode* leaf)
+{
+       if(!pdbvt->m_root)
+       {
+               pdbvt->m_root   =       leaf;
+               leaf->parent    =       0;
+       }
+       else
+       {
+               if(!root->isleaf())
+               {
+                       do      {
+                               root=root->childs[Select(       leaf->volume,
+                                       root->childs[0]->volume,
+                                       root->childs[1]->volume)];
+                       } while(!root->isleaf());
+               }
+               btDbvtNode*     prev=root->parent;
+               btDbvtNode*     node=createnode(pdbvt,prev,leaf->volume,root->volume,0);
+               if(prev)
+               {
+                       prev->childs[indexof(root)]     =       node;
+                       node->childs[0]                         =       root;root->parent=node;
+                       node->childs[1]                         =       leaf;leaf->parent=node;
+                       do      {
+                               if(!prev->volume.Contain(node->volume))
+                                       Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
+                               else
+                                       break;
+                               node=prev;
+                       } while(0!=(prev=node->parent));
+               }
+               else
+               {
+                       node->childs[0] =       root;root->parent=node;
+                       node->childs[1] =       leaf;leaf->parent=node;
+                       pdbvt->m_root   =       node;
+               }
+       }
+}
+
+//
+static btDbvtNode*                             removeleaf(     btDbvt* pdbvt,
+                                                                                  btDbvtNode* leaf)
+{
+       if(leaf==pdbvt->m_root)
+       {
+               pdbvt->m_root=0;
+               return(0);
+       }
+       else
+       {
+               btDbvtNode*     parent=leaf->parent;
+               btDbvtNode*     prev=parent->parent;
+               btDbvtNode*     sibling=parent->childs[1-indexof(leaf)];                        
+               if(prev)
+               {
+                       prev->childs[indexof(parent)]=sibling;
+                       sibling->parent=prev;
+                       deletenode(pdbvt,parent);
+                       while(prev)
+                       {
+                               const btDbvtVolume      pb=prev->volume;
+                               Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
+                               if(NotEqual(pb,prev->volume))
+                               {
+                                       prev=prev->parent;
+                               } else break;
+                       }
+                       return(prev?prev:pdbvt->m_root);
+               }
+               else
+               {                                                               
+                       pdbvt->m_root=sibling;
+                       sibling->parent=0;
+                       deletenode(pdbvt,parent);
+                       return(pdbvt->m_root);
+               }                       
+       }
+}
+
+//
+static void                                            fetchleaves(btDbvt* pdbvt,
+                                                                                       btDbvtNode* root,
+                                                                                       tNodeArray& leaves,
+                                                                                       int depth=-1)
+{
+       if(root->isinternal()&&depth)
+       {
+               fetchleaves(pdbvt,root->childs[0],leaves,depth-1);
+               fetchleaves(pdbvt,root->childs[1],leaves,depth-1);
+               deletenode(pdbvt,root);
+       }
+       else
+       {
+               leaves.push_back(root);
+       }
+}
+
+//
+static void                                            split(  const tNodeArray& leaves,
+                                                                         tNodeArray& left,
+                                                                         tNodeArray& right,
+                                                                         const btVector3& org,
+                                                                         const btVector3& axis)
+{
+       left.resize(0);
+       right.resize(0);
+       for(int i=0,ni=leaves.size();i<ni;++i)
+       {
+               if(btDot(axis,leaves[i]->volume.Center()-org)<0)
+                       left.push_back(leaves[i]);
+               else
+                       right.push_back(leaves[i]);
+       }
+}
+
+//
+static btDbvtVolume                            bounds( const tNodeArray& leaves)
+{
+#if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
+       ATTRIBUTE_ALIGNED16(char        locals[sizeof(btDbvtVolume)]);
+       btDbvtVolume&   volume=*(btDbvtVolume*)locals;
+       volume=leaves[0]->volume;
+#else
+       btDbvtVolume volume=leaves[0]->volume;
+#endif
+       for(int i=1,ni=leaves.size();i<ni;++i)
+       {
+               Merge(volume,leaves[i]->volume,volume);
+       }
+       return(volume);
+}
+
+//
+static void                                            bottomup(       btDbvt* pdbvt,
+                                                                                tNodeArray& leaves)
+{
+       while(leaves.size()>1)
+       {
+               btScalar        minsize=SIMD_INFINITY;
+               int                     minidx[2]={-1,-1};
+               for(int i=0;i<leaves.size();++i)
+               {
+                       for(int j=i+1;j<leaves.size();++j)
+                       {
+                               const btScalar  sz=size(merge(leaves[i]->volume,leaves[j]->volume));
+                               if(sz<minsize)
+                               {
+                                       minsize         =       sz;
+                                       minidx[0]       =       i;
+                                       minidx[1]       =       j;
+                               }
+                       }
+               }
+               btDbvtNode*     n[]     =       {leaves[minidx[0]],leaves[minidx[1]]};
+               btDbvtNode*     p       =       createnode(pdbvt,0,n[0]->volume,n[1]->volume,0);
+               p->childs[0]            =       n[0];
+               p->childs[1]            =       n[1];
+               n[0]->parent            =       p;
+               n[1]->parent            =       p;
+               leaves[minidx[0]]       =       p;
+               leaves.swap(minidx[1],leaves.size()-1);
+               leaves.pop_back();
+       }
+}
+
+//
+static btDbvtNode*                     topdown(btDbvt* pdbvt,
+                                                                       tNodeArray& leaves,
+                                                                       int bu_treshold)
+{
+       static const btVector3  axis[]={btVector3(1,0,0),
+               btVector3(0,1,0),
+               btVector3(0,0,1)};
+       if(leaves.size()>1)
+       {
+               if(leaves.size()>bu_treshold)
+               {
+                       const btDbvtVolume      vol=bounds(leaves);
+                       const btVector3                 org=vol.Center();
+                       tNodeArray                              sets[2];
+                       int                                             bestaxis=-1;
+                       int                                             bestmidp=leaves.size();
+                       int                                             splitcount[3][2]={{0,0},{0,0},{0,0}};
+                       int i;
+                       for( i=0;i<leaves.size();++i)
+                       {
+                               const btVector3 x=leaves[i]->volume.Center()-org;
+                               for(int j=0;j<3;++j)
+                               {
+                                       ++splitcount[j][btDot(x,axis[j])>0?1:0];
+                               }
+                       }
+                       for( i=0;i<3;++i)
+                       {
+                               if((splitcount[i][0]>0)&&(splitcount[i][1]>0))
+                               {
+                                       const int       midp=(int)btFabs(btScalar(splitcount[i][0]-splitcount[i][1]));
+                                       if(midp<bestmidp)
+                                       {
+                                               bestaxis=i;
+                                               bestmidp=midp;
+                                       }
+                               }
+                       }
+                       if(bestaxis>=0)
+                       {
+                               sets[0].reserve(splitcount[bestaxis][0]);
+                               sets[1].reserve(splitcount[bestaxis][1]);
+                               split(leaves,sets[0],sets[1],org,axis[bestaxis]);
+                       }
+                       else
+                       {
+                               sets[0].reserve(leaves.size()/2+1);
+                               sets[1].reserve(leaves.size()/2);
+                               for(int i=0,ni=leaves.size();i<ni;++i)
+                               {
+                                       sets[i&1].push_back(leaves[i]);
+                               }
+                       }
+                       btDbvtNode*     node=createnode(pdbvt,0,vol,0);
+                       node->childs[0]=topdown(pdbvt,sets[0],bu_treshold);
+                       node->childs[1]=topdown(pdbvt,sets[1],bu_treshold);
+                       node->childs[0]->parent=node;
+                       node->childs[1]->parent=node;
+                       return(node);
+               }
+               else
+               {
+                       bottomup(pdbvt,leaves);
+                       return(leaves[0]);
+               }
+       }
+       return(leaves[0]);
+}
+
+//
+static DBVT_INLINE btDbvtNode* sort(btDbvtNode* n,btDbvtNode*& r)
+{
+       btDbvtNode*     p=n->parent;
+       btAssert(n->isinternal());
+       if(p>n)
+       {
+               const int               i=indexof(n);
+               const int               j=1-i;
+               btDbvtNode*     s=p->childs[j];
+               btDbvtNode*     q=p->parent;
+               btAssert(n==p->childs[i]);
+               if(q) q->childs[indexof(p)]=n; else r=n;
+               s->parent=n;
+               p->parent=n;
+               n->parent=q;
+               p->childs[0]=n->childs[0];
+               p->childs[1]=n->childs[1];
+               n->childs[0]->parent=p;
+               n->childs[1]->parent=p;
+               n->childs[i]=p;
+               n->childs[j]=s;
+               btSwap(p->volume,n->volume);
+               return(p);
+       }
+       return(n);
+}
+
+#if 0
+static DBVT_INLINE btDbvtNode* walkup(btDbvtNode* n,int count)
+{
+       while(n&&(count--)) n=n->parent;
+       return(n);
+}
+#endif
+
+//
+// Api
+//
+
+//
+btDbvt::btDbvt()
+{
+       m_root          =       0;
+       m_free          =       0;
+       m_lkhd          =       -1;
+       m_leaves        =       0;
+       m_opath         =       0;
+}
+
+//
+btDbvt::~btDbvt()
+{
+       clear();
+}
+
+//
+void                   btDbvt::clear()
+{
+       if(m_root)      
+               recursedeletenode(this,m_root);
+       btAlignedFree(m_free);
+       m_free=0;
+       m_lkhd          =       -1;
+       m_stkStack.clear();
+       m_opath         =       0;
+       
+}
+
+//
+void                   btDbvt::optimizeBottomUp()
+{
+       if(m_root)
+       {
+               tNodeArray leaves;
+               leaves.reserve(m_leaves);
+               fetchleaves(this,m_root,leaves);
+               bottomup(this,leaves);
+               m_root=leaves[0];
+       }
+}
+
+//
+void                   btDbvt::optimizeTopDown(int bu_treshold)
+{
+       if(m_root)
+       {
+               tNodeArray      leaves;
+               leaves.reserve(m_leaves);
+               fetchleaves(this,m_root,leaves);
+               m_root=topdown(this,leaves,bu_treshold);
+       }
+}
+
+//
+void                   btDbvt::optimizeIncremental(int passes)
+{
+       if(passes<0) passes=m_leaves;
+       if(m_root&&(passes>0))
+       {
+               do      {
+                       btDbvtNode*             node=m_root;
+                       unsigned        bit=0;
+                       while(node->isinternal())
+                       {
+                               node=sort(node,m_root)->childs[(m_opath>>bit)&1];
+                               bit=(bit+1)&(sizeof(unsigned)*8-1);
+                       }
+                       update(node);
+                       ++m_opath;
+               } while(--passes);
+       }
+}
+
+//
+btDbvtNode*    btDbvt::insert(const btDbvtVolume& volume,void* data)
+{
+       btDbvtNode*     leaf=createnode(this,0,volume,data);
+       insertleaf(this,m_root,leaf);
+       ++m_leaves;
+       return(leaf);
+}
+
+//
+void                   btDbvt::update(btDbvtNode* leaf,int lookahead)
+{
+       btDbvtNode*     root=removeleaf(this,leaf);
+       if(root)
+       {
+               if(lookahead>=0)
+               {
+                       for(int i=0;(i<lookahead)&&root->parent;++i)
+                       {
+                               root=root->parent;
+                       }
+               } else root=m_root;
+       }
+       insertleaf(this,root,leaf);
+}
+
+//
+void                   btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume)
+{
+       btDbvtNode*     root=removeleaf(this,leaf);
+       if(root)
+       {
+               if(m_lkhd>=0)
+               {
+                       for(int i=0;(i<m_lkhd)&&root->parent;++i)
+                       {
+                               root=root->parent;
+                       }
+               } else root=m_root;
+       }
+       leaf->volume=volume;
+       insertleaf(this,root,leaf);
+}
+
+//
+bool                   btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity,btScalar margin)
+{
+       if(leaf->volume.Contain(volume)) return(false);
+       volume.Expand(btVector3(margin,margin,margin));
+       volume.SignedExpand(velocity);
+       update(leaf,volume);
+       return(true);
+}
+
+//
+bool                   btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity)
+{
+       if(leaf->volume.Contain(volume)) return(false);
+       volume.SignedExpand(velocity);
+       update(leaf,volume);
+       return(true);
+}
+
+//
+bool                   btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,btScalar margin)
+{
+       if(leaf->volume.Contain(volume)) return(false);
+       volume.Expand(btVector3(margin,margin,margin));
+       update(leaf,volume);
+       return(true);
+}
+
+//
+void                   btDbvt::remove(btDbvtNode* leaf)
+{
+       removeleaf(this,leaf);
+       deletenode(this,leaf);
+       --m_leaves;
+}
+
+//
+void                   btDbvt::write(IWriter* iwriter) const
+{
+       btDbvtNodeEnumerator    nodes;
+       nodes.nodes.reserve(m_leaves*2);
+       enumNodes(m_root,nodes);
+       iwriter->Prepare(m_root,nodes.nodes.size());
+       for(int i=0;i<nodes.nodes.size();++i)
+       {
+               const btDbvtNode* n=nodes.nodes[i];
+               int                     p=-1;
+               if(n->parent) p=nodes.nodes.findLinearSearch(n->parent);
+               if(n->isinternal())
+               {
+                       const int       c0=nodes.nodes.findLinearSearch(n->childs[0]);
+                       const int       c1=nodes.nodes.findLinearSearch(n->childs[1]);
+                       iwriter->WriteNode(n,i,p,c0,c1);
+               }
+               else
+               {
+                       iwriter->WriteLeaf(n,i,p);
+               }       
+       }
+}
+
+//
+void                   btDbvt::clone(btDbvt& dest,IClone* iclone) const
+{
+       dest.clear();
+       if(m_root!=0)
+       {       
+               btAlignedObjectArray<sStkCLN>   stack;
+               stack.reserve(m_leaves);
+               stack.push_back(sStkCLN(m_root,0));
+               do      {
+                       const int               i=stack.size()-1;
+                       const sStkCLN   e=stack[i];
+                       btDbvtNode*                     n=createnode(&dest,e.parent,e.node->volume,e.node->data);
+                       stack.pop_back();
+                       if(e.parent!=0)
+                               e.parent->childs[i&1]=n;
+                       else
+                               dest.m_root=n;
+                       if(e.node->isinternal())
+                       {
+                               stack.push_back(sStkCLN(e.node->childs[0],n));
+                               stack.push_back(sStkCLN(e.node->childs[1],n));
+                       }
+                       else
+                       {
+                               iclone->CloneLeaf(n);
+                       }
+               } while(stack.size()>0);
+       }
+}
+
+//
+int                            btDbvt::maxdepth(const btDbvtNode* node)
+{
+       int     depth=0;
+       if(node) getmaxdepth(node,1,depth);
+       return(depth);
+}
+
+//
+int                            btDbvt::countLeaves(const btDbvtNode* node)
+{
+       if(node->isinternal())
+               return(countLeaves(node->childs[0])+countLeaves(node->childs[1]));
+       else
+               return(1);
+}
+
+//
+void                   btDbvt::extractLeaves(const btDbvtNode* node,btAlignedObjectArray<const btDbvtNode*>& leaves)
+{
+       if(node->isinternal())
+       {
+               extractLeaves(node->childs[0],leaves);
+               extractLeaves(node->childs[1],leaves);
+       }
+       else
+       {
+               leaves.push_back(node);
+       }       
+}
+
+//
+#if DBVT_ENABLE_BENCHMARK
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "LinearMath/btQuickProf.h"
+
+/*
+q6600,2.4ghz
+
+/Ox /Ob2 /Oi /Ot /I "." /I "..\.." /I "..\..\src" /D "NDEBUG" /D "_LIB" /D "_WINDOWS" /D "_CRT_SECURE_NO_DEPRECATE" /D "_CRT_NONSTDC_NO_DEPRECATE" /D "WIN32"
+/GF /FD /MT /GS- /Gy /arch:SSE2 /Zc:wchar_t- /Fp"..\..\out\release8\build\libbulletcollision\libbulletcollision.pch"
+/Fo"..\..\out\release8\build\libbulletcollision\\"
+/Fd"..\..\out\release8\build\libbulletcollision\bulletcollision.pdb"
+/W3 /nologo /c /Wp64 /Zi /errorReport:prompt
+
+Benchmarking dbvt...
+World scale: 100.000000
+Extents base: 1.000000
+Extents range: 4.000000
+Leaves: 8192
+sizeof(btDbvtVolume): 32 bytes
+sizeof(btDbvtNode):   44 bytes
+[1] btDbvtVolume intersections: 3499 ms (-1%)
+[2] btDbvtVolume merges: 1934 ms (0%)
+[3] btDbvt::collideTT: 5485 ms (-21%)
+[4] btDbvt::collideTT self: 2814 ms (-20%)
+[5] btDbvt::collideTT xform: 7379 ms (-1%)
+[6] btDbvt::collideTT xform,self: 7270 ms (-2%)
+[7] btDbvt::rayTest: 6314 ms (0%),(332143 r/s)
+[8] insert/remove: 2093 ms (0%),(1001983 ir/s)
+[9] updates (teleport): 1879 ms (-3%),(1116100 u/s)
+[10] updates (jitter): 1244 ms (-4%),(1685813 u/s)
+[11] optimize (incremental): 2514 ms (0%),(1668000 o/s)
+[12] btDbvtVolume notequal: 3659 ms (0%)
+[13] culling(OCL+fullsort): 2218 ms (0%),(461 t/s)
+[14] culling(OCL+qsort): 3688 ms (5%),(2221 t/s)
+[15] culling(KDOP+qsort): 1139 ms (-1%),(7192 t/s)
+[16] insert/remove batch(256): 5092 ms (0%),(823704 bir/s)
+[17] btDbvtVolume select: 3419 ms (0%)
+*/
+
+struct btDbvtBenchmark
+{
+       struct NilPolicy : btDbvt::ICollide
+       {
+               NilPolicy() : m_pcount(0),m_depth(-SIMD_INFINITY),m_checksort(true)             {}
+               void    Process(const btDbvtNode*,const btDbvtNode*)                            { ++m_pcount; }
+               void    Process(const btDbvtNode*)                                                                      { ++m_pcount; }
+               void    Process(const btDbvtNode*,btScalar depth)
+               {
+                       ++m_pcount;
+                       if(m_checksort)
+                       { if(depth>=m_depth) m_depth=depth; else printf("wrong depth: %f (should be >= %f)\r\n",depth,m_depth); }
+               }
+               int                     m_pcount;
+               btScalar        m_depth;
+               bool            m_checksort;
+       };
+       struct P14 : btDbvt::ICollide
+       {
+               struct Node
+               {
+                       const btDbvtNode*       leaf;
+                       btScalar                        depth;
+               };
+               void Process(const btDbvtNode* leaf,btScalar depth)
+               {
+                       Node    n;
+                       n.leaf  =       leaf;
+                       n.depth =       depth;
+               }
+               static int sortfnc(const Node& a,const Node& b)
+               {
+                       if(a.depth<b.depth) return(+1);
+                       if(a.depth>b.depth) return(-1);
+                       return(0);
+               }
+               btAlignedObjectArray<Node>              m_nodes;
+       };
+       struct P15 : btDbvt::ICollide
+       {
+               struct Node
+               {
+                       const btDbvtNode*       leaf;
+                       btScalar                        depth;
+               };
+               void Process(const btDbvtNode* leaf)
+               {
+                       Node    n;
+                       n.leaf  =       leaf;
+                       n.depth =       dot(leaf->volume.Center(),m_axis);
+               }
+               static int sortfnc(const Node& a,const Node& b)
+               {
+                       if(a.depth<b.depth) return(+1);
+                       if(a.depth>b.depth) return(-1);
+                       return(0);
+               }
+               btAlignedObjectArray<Node>              m_nodes;
+               btVector3                                               m_axis;
+       };
+       static btScalar                 RandUnit()
+       {
+               return(rand()/(btScalar)RAND_MAX);
+       }
+       static btVector3                RandVector3()
+       {
+               return(btVector3(RandUnit(),RandUnit(),RandUnit()));
+       }
+       static btVector3                RandVector3(btScalar cs)
+       {
+               return(RandVector3()*cs-btVector3(cs,cs,cs)/2);
+       }
+       static btDbvtVolume     RandVolume(btScalar cs,btScalar eb,btScalar es)
+       {
+               return(btDbvtVolume::FromCE(RandVector3(cs),btVector3(eb,eb,eb)+RandVector3()*es));
+       }
+       static btTransform              RandTransform(btScalar cs)
+       {
+               btTransform     t;
+               t.setOrigin(RandVector3(cs));
+               t.setRotation(btQuaternion(RandUnit()*SIMD_PI*2,RandUnit()*SIMD_PI*2,RandUnit()*SIMD_PI*2).normalized());
+               return(t);
+       }
+       static void                             RandTree(btScalar cs,btScalar eb,btScalar es,int leaves,btDbvt& dbvt)
+       {
+               dbvt.clear();
+               for(int i=0;i<leaves;++i)
+               {
+                       dbvt.insert(RandVolume(cs,eb,es),0);
+               }
+       }
+};
+
+void                   btDbvt::benchmark()
+{
+       static const btScalar   cfgVolumeCenterScale            =       100;
+       static const btScalar   cfgVolumeExentsBase                     =       1;
+       static const btScalar   cfgVolumeExentsScale            =       4;
+       static const int                cfgLeaves                                       =       8192;
+       static const bool               cfgEnable                                       =       true;
+
+       //[1] btDbvtVolume intersections
+       bool                                    cfgBenchmark1_Enable            =       cfgEnable;
+       static const int                cfgBenchmark1_Iterations        =       8;
+       static const int                cfgBenchmark1_Reference         =       3499;
+       //[2] btDbvtVolume merges
+       bool                                    cfgBenchmark2_Enable            =       cfgEnable;
+       static const int                cfgBenchmark2_Iterations        =       4;
+       static const int                cfgBenchmark2_Reference         =       1945;
+       //[3] btDbvt::collideTT
+       bool                                    cfgBenchmark3_Enable            =       cfgEnable;
+       static const int                cfgBenchmark3_Iterations        =       512;
+       static const int                cfgBenchmark3_Reference         =       5485;
+       //[4] btDbvt::collideTT self
+       bool                                    cfgBenchmark4_Enable            =       cfgEnable;
+       static const int                cfgBenchmark4_Iterations        =       512;
+       static const int                cfgBenchmark4_Reference         =       2814;
+       //[5] btDbvt::collideTT xform
+       bool                                    cfgBenchmark5_Enable            =       cfgEnable;
+       static const int                cfgBenchmark5_Iterations        =       512;
+       static const btScalar   cfgBenchmark5_OffsetScale       =       2;
+       static const int                cfgBenchmark5_Reference         =       7379;
+       //[6] btDbvt::collideTT xform,self
+       bool                                    cfgBenchmark6_Enable            =       cfgEnable;
+       static const int                cfgBenchmark6_Iterations        =       512;
+       static const btScalar   cfgBenchmark6_OffsetScale       =       2;
+       static const int                cfgBenchmark6_Reference         =       7270;
+       //[7] btDbvt::rayTest
+       bool                                    cfgBenchmark7_Enable            =       cfgEnable;
+       static const int                cfgBenchmark7_Passes            =       32;
+       static const int                cfgBenchmark7_Iterations        =       65536;
+       static const int                cfgBenchmark7_Reference         =       6307;
+       //[8] insert/remove
+       bool                                    cfgBenchmark8_Enable            =       cfgEnable;
+       static const int                cfgBenchmark8_Passes            =       32;
+       static const int                cfgBenchmark8_Iterations        =       65536;
+       static const int                cfgBenchmark8_Reference         =       2105;
+       //[9] updates (teleport)
+       bool                                    cfgBenchmark9_Enable            =       cfgEnable;
+       static const int                cfgBenchmark9_Passes            =       32;
+       static const int                cfgBenchmark9_Iterations        =       65536;
+       static const int                cfgBenchmark9_Reference         =       1879;
+       //[10] updates (jitter)
+       bool                                    cfgBenchmark10_Enable           =       cfgEnable;
+       static const btScalar   cfgBenchmark10_Scale            =       cfgVolumeCenterScale/10000;
+       static const int                cfgBenchmark10_Passes           =       32;
+       static const int                cfgBenchmark10_Iterations       =       65536;
+       static const int                cfgBenchmark10_Reference        =       1244;
+       //[11] optimize (incremental)
+       bool                                    cfgBenchmark11_Enable           =       cfgEnable;
+       static const int                cfgBenchmark11_Passes           =       64;
+       static const int                cfgBenchmark11_Iterations       =       65536;
+       static const int                cfgBenchmark11_Reference        =       2510;
+       //[12] btDbvtVolume notequal
+       bool                                    cfgBenchmark12_Enable           =       cfgEnable;
+       static const int                cfgBenchmark12_Iterations       =       32;
+       static const int                cfgBenchmark12_Reference        =       3677;
+       //[13] culling(OCL+fullsort)
+       bool                                    cfgBenchmark13_Enable           =       cfgEnable;
+       static const int                cfgBenchmark13_Iterations       =       1024;
+       static const int                cfgBenchmark13_Reference        =       2231;
+       //[14] culling(OCL+qsort)
+       bool                                    cfgBenchmark14_Enable           =       cfgEnable;
+       static const int                cfgBenchmark14_Iterations       =       8192;
+       static const int                cfgBenchmark14_Reference        =       3500;
+       //[15] culling(KDOP+qsort)
+       bool                                    cfgBenchmark15_Enable           =       cfgEnable;
+       static const int                cfgBenchmark15_Iterations       =       8192;
+       static const int                cfgBenchmark15_Reference        =       1151;
+       //[16] insert/remove batch
+       bool                                    cfgBenchmark16_Enable           =       cfgEnable;
+       static const int                cfgBenchmark16_BatchCount       =       256;
+       static const int                cfgBenchmark16_Passes           =       16384;
+       static const int                cfgBenchmark16_Reference        =       5138;
+       //[17] select
+       bool                                    cfgBenchmark17_Enable           =       cfgEnable;
+       static const int                cfgBenchmark17_Iterations       =       4;
+       static const int                cfgBenchmark17_Reference        =       3390;
+
+       btClock                                 wallclock;
+       printf("Benchmarking dbvt...\r\n");
+       printf("\tWorld scale: %f\r\n",cfgVolumeCenterScale);
+       printf("\tExtents base: %f\r\n",cfgVolumeExentsBase);
+       printf("\tExtents range: %f\r\n",cfgVolumeExentsScale);
+       printf("\tLeaves: %u\r\n",cfgLeaves);
+       printf("\tsizeof(btDbvtVolume): %u bytes\r\n",sizeof(btDbvtVolume));
+       printf("\tsizeof(btDbvtNode):   %u bytes\r\n",sizeof(btDbvtNode));
+       if(cfgBenchmark1_Enable)
+       {// Benchmark 1 
+               srand(380843);
+               btAlignedObjectArray<btDbvtVolume>      volumes;
+               btAlignedObjectArray<bool>                      results;
+               volumes.resize(cfgLeaves);
+               results.resize(cfgLeaves);
+               for(int i=0;i<cfgLeaves;++i)
+               {
+                       volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
+               }
+               printf("[1] btDbvtVolume intersections: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark1_Iterations;++i)
+               {
+                       for(int j=0;j<cfgLeaves;++j)
+                       {
+                               for(int k=0;k<cfgLeaves;++k)
+                               {
+                                       results[k]=Intersect(volumes[j],volumes[k]);
+                               }
+                       }
+               }
+               const int time=(int)wallclock.getTimeMilliseconds();
+               printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark1_Reference)*100/time);
+       }
+       if(cfgBenchmark2_Enable)
+       {// Benchmark 2 
+               srand(380843);
+               btAlignedObjectArray<btDbvtVolume>      volumes;
+               btAlignedObjectArray<btDbvtVolume>      results;
+               volumes.resize(cfgLeaves);
+               results.resize(cfgLeaves);
+               for(int i=0;i<cfgLeaves;++i)
+               {
+                       volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
+               }
+               printf("[2] btDbvtVolume merges: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark2_Iterations;++i)
+               {
+                       for(int j=0;j<cfgLeaves;++j)
+                       {
+                               for(int k=0;k<cfgLeaves;++k)
+                               {
+                                       Merge(volumes[j],volumes[k],results[k]);
+                               }
+                       }
+               }
+               const int time=(int)wallclock.getTimeMilliseconds();
+               printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark2_Reference)*100/time);
+       }
+       if(cfgBenchmark3_Enable)
+       {// Benchmark 3 
+               srand(380843);
+               btDbvt                                          dbvt[2];
+               btDbvtBenchmark::NilPolicy      policy;
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
+               dbvt[0].optimizeTopDown();
+               dbvt[1].optimizeTopDown();
+               printf("[3] btDbvt::collideTT: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark3_Iterations;++i)
+               {
+                       btDbvt::collideTT(dbvt[0].m_root,dbvt[1].m_root,policy);
+               }
+               const int time=(int)wallclock.getTimeMilliseconds();
+               printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark3_Reference)*100/time);
+       }
+       if(cfgBenchmark4_Enable)
+       {// Benchmark 4
+               srand(380843);
+               btDbvt                                          dbvt;
+               btDbvtBenchmark::NilPolicy      policy;
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               printf("[4] btDbvt::collideTT self: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark4_Iterations;++i)
+               {
+                       btDbvt::collideTT(dbvt.m_root,dbvt.m_root,policy);
+               }
+               const int time=(int)wallclock.getTimeMilliseconds();
+               printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark4_Reference)*100/time);
+       }
+       if(cfgBenchmark5_Enable)
+       {// Benchmark 5 
+               srand(380843);
+               btDbvt                                                          dbvt[2];
+               btAlignedObjectArray<btTransform>       transforms;
+               btDbvtBenchmark::NilPolicy                      policy;
+               transforms.resize(cfgBenchmark5_Iterations);
+               for(int i=0;i<transforms.size();++i)
+               {
+                       transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark5_OffsetScale);
+               }
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
+               dbvt[0].optimizeTopDown();
+               dbvt[1].optimizeTopDown();
+               printf("[5] btDbvt::collideTT xform: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark5_Iterations;++i)
+               {
+                       btDbvt::collideTT(dbvt[0].m_root,dbvt[1].m_root,transforms[i],policy);
+               }
+               const int time=(int)wallclock.getTimeMilliseconds();
+               printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark5_Reference)*100/time);
+       }
+       if(cfgBenchmark6_Enable)
+       {// Benchmark 6 
+               srand(380843);
+               btDbvt                                                          dbvt;
+               btAlignedObjectArray<btTransform>       transforms;
+               btDbvtBenchmark::NilPolicy                      policy;
+               transforms.resize(cfgBenchmark6_Iterations);
+               for(int i=0;i<transforms.size();++i)
+               {
+                       transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark6_OffsetScale);
+               }
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               printf("[6] btDbvt::collideTT xform,self: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark6_Iterations;++i)
+               {
+                       btDbvt::collideTT(dbvt.m_root,dbvt.m_root,transforms[i],policy);                
+               }
+               const int time=(int)wallclock.getTimeMilliseconds();
+               printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark6_Reference)*100/time);
+       }
+       if(cfgBenchmark7_Enable)
+       {// Benchmark 7 
+               srand(380843);
+               btDbvt                                                          dbvt;
+               btAlignedObjectArray<btVector3>         rayorg;
+               btAlignedObjectArray<btVector3>         raydir;
+               btDbvtBenchmark::NilPolicy                      policy;
+               rayorg.resize(cfgBenchmark7_Iterations);
+               raydir.resize(cfgBenchmark7_Iterations);
+               for(int i=0;i<rayorg.size();++i)
+               {
+                       rayorg[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
+                       raydir[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
+               }
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               printf("[7] btDbvt::rayTest: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark7_Passes;++i)
+               {
+                       for(int j=0;j<cfgBenchmark7_Iterations;++j)
+                       {
+                               btDbvt::rayTest(dbvt.m_root,rayorg[j],rayorg[j]+raydir[j],policy);
+                       }
+               }
+               const int       time=(int)wallclock.getTimeMilliseconds();
+               unsigned        rays=cfgBenchmark7_Passes*cfgBenchmark7_Iterations;
+               printf("%u ms (%i%%),(%u r/s)\r\n",time,(time-cfgBenchmark7_Reference)*100/time,(rays*1000)/time);
+       }
+       if(cfgBenchmark8_Enable)
+       {// Benchmark 8 
+               srand(380843);
+               btDbvt                                                          dbvt;
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               printf("[8] insert/remove: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark8_Passes;++i)
+               {
+                       for(int j=0;j<cfgBenchmark8_Iterations;++j)
+                       {
+                               dbvt.remove(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0));
+                       }
+               }
+               const int       time=(int)wallclock.getTimeMilliseconds();
+               const int       ir=cfgBenchmark8_Passes*cfgBenchmark8_Iterations;
+               printf("%u ms (%i%%),(%u ir/s)\r\n",time,(time-cfgBenchmark8_Reference)*100/time,ir*1000/time);
+       }
+       if(cfgBenchmark9_Enable)
+       {// Benchmark 9 
+               srand(380843);
+               btDbvt                                                                          dbvt;
+               btAlignedObjectArray<const btDbvtNode*> leaves;
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               dbvt.extractLeaves(dbvt.m_root,leaves);
+               printf("[9] updates (teleport): ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark9_Passes;++i)
+               {
+                       for(int j=0;j<cfgBenchmark9_Iterations;++j)
+                       {
+                               dbvt.update(const_cast<btDbvtNode*>(leaves[rand()%cfgLeaves]),
+                                       btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale));
+                       }
+               }
+               const int       time=(int)wallclock.getTimeMilliseconds();
+               const int       up=cfgBenchmark9_Passes*cfgBenchmark9_Iterations;
+               printf("%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark9_Reference)*100/time,up*1000/time);
+       }
+       if(cfgBenchmark10_Enable)
+       {// Benchmark 10        
+               srand(380843);
+               btDbvt                                                                          dbvt;
+               btAlignedObjectArray<const btDbvtNode*> leaves;
+               btAlignedObjectArray<btVector3>                         vectors;
+               vectors.resize(cfgBenchmark10_Iterations);
+               for(int i=0;i<vectors.size();++i)
+               {
+                       vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1))*cfgBenchmark10_Scale;
+               }
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               dbvt.extractLeaves(dbvt.m_root,leaves);
+               printf("[10] updates (jitter): ");
+               wallclock.reset();
+
+               for(int i=0;i<cfgBenchmark10_Passes;++i)
+               {
+                       for(int j=0;j<cfgBenchmark10_Iterations;++j)
+                       {                       
+                               const btVector3&        d=vectors[j];
+                               btDbvtNode*             l=const_cast<btDbvtNode*>(leaves[rand()%cfgLeaves]);
+                               btDbvtVolume            v=btDbvtVolume::FromMM(l->volume.Mins()+d,l->volume.Maxs()+d);
+                               dbvt.update(l,v);
+                       }
+               }
+               const int       time=(int)wallclock.getTimeMilliseconds();
+               const int       up=cfgBenchmark10_Passes*cfgBenchmark10_Iterations;
+               printf("%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark10_Reference)*100/time,up*1000/time);
+       }
+       if(cfgBenchmark11_Enable)
+       {// Benchmark 11        
+               srand(380843);
+               btDbvt                                                                          dbvt;
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               printf("[11] optimize (incremental): ");
+               wallclock.reset();      
+               for(int i=0;i<cfgBenchmark11_Passes;++i)
+               {
+                       dbvt.optimizeIncremental(cfgBenchmark11_Iterations);
+               }
+               const int       time=(int)wallclock.getTimeMilliseconds();
+               const int       op=cfgBenchmark11_Passes*cfgBenchmark11_Iterations;
+               printf("%u ms (%i%%),(%u o/s)\r\n",time,(time-cfgBenchmark11_Reference)*100/time,op/time*1000);
+       }
+       if(cfgBenchmark12_Enable)
+       {// Benchmark 12        
+               srand(380843);
+               btAlignedObjectArray<btDbvtVolume>      volumes;
+               btAlignedObjectArray<bool>                              results;
+               volumes.resize(cfgLeaves);
+               results.resize(cfgLeaves);
+               for(int i=0;i<cfgLeaves;++i)
+               {
+                       volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
+               }
+               printf("[12] btDbvtVolume notequal: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark12_Iterations;++i)
+               {
+                       for(int j=0;j<cfgLeaves;++j)
+                       {
+                               for(int k=0;k<cfgLeaves;++k)
+                               {
+                                       results[k]=NotEqual(volumes[j],volumes[k]);
+                               }
+                       }
+               }
+               const int time=(int)wallclock.getTimeMilliseconds();
+               printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark12_Reference)*100/time);
+       }
+       if(cfgBenchmark13_Enable)
+       {// Benchmark 13        
+               srand(380843);
+               btDbvt                                                          dbvt;
+               btAlignedObjectArray<btVector3>         vectors;
+               btDbvtBenchmark::NilPolicy                      policy;
+               vectors.resize(cfgBenchmark13_Iterations);
+               for(int i=0;i<vectors.size();++i)
+               {
+                       vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized();
+               }
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               printf("[13] culling(OCL+fullsort): ");
+               wallclock.reset();      
+               for(int i=0;i<cfgBenchmark13_Iterations;++i)
+               {
+                       static const btScalar   offset=0;
+                       policy.m_depth=-SIMD_INFINITY;
+                       dbvt.collideOCL(dbvt.m_root,&vectors[i],&offset,vectors[i],1,policy);
+               }
+               const int       time=(int)wallclock.getTimeMilliseconds();
+               const int       t=cfgBenchmark13_Iterations;
+               printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark13_Reference)*100/time,(t*1000)/time);
+       }
+       if(cfgBenchmark14_Enable)
+       {// Benchmark 14        
+               srand(380843);
+               btDbvt                                                          dbvt;
+               btAlignedObjectArray<btVector3>         vectors;
+               btDbvtBenchmark::P14                            policy;
+               vectors.resize(cfgBenchmark14_Iterations);
+               for(int i=0;i<vectors.size();++i)
+               {
+                       vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized();
+               }
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               policy.m_nodes.reserve(cfgLeaves);
+               printf("[14] culling(OCL+qsort): ");
+               wallclock.reset();      
+               for(int i=0;i<cfgBenchmark14_Iterations;++i)
+               {
+                       static const btScalar   offset=0;
+                       policy.m_nodes.resize(0);
+                       dbvt.collideOCL(dbvt.m_root,&vectors[i],&offset,vectors[i],1,policy,false);
+                       policy.m_nodes.quickSort(btDbvtBenchmark::P14::sortfnc);
+               }
+               const int       time=(int)wallclock.getTimeMilliseconds();
+               const int       t=cfgBenchmark14_Iterations;
+               printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark14_Reference)*100/time,(t*1000)/time);
+       }
+       if(cfgBenchmark15_Enable)
+       {// Benchmark 15        
+               srand(380843);
+               btDbvt                                                          dbvt;
+               btAlignedObjectArray<btVector3>         vectors;
+               btDbvtBenchmark::P15                            policy;
+               vectors.resize(cfgBenchmark15_Iterations);
+               for(int i=0;i<vectors.size();++i)
+               {
+                       vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized();
+               }
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               policy.m_nodes.reserve(cfgLeaves);
+               printf("[15] culling(KDOP+qsort): ");
+               wallclock.reset();      
+               for(int i=0;i<cfgBenchmark15_Iterations;++i)
+               {
+                       static const btScalar   offset=0;
+                       policy.m_nodes.resize(0);
+                       policy.m_axis=vectors[i];
+                       dbvt.collideKDOP(dbvt.m_root,&vectors[i],&offset,1,policy);
+                       policy.m_nodes.quickSort(btDbvtBenchmark::P15::sortfnc);
+               }
+               const int       time=(int)wallclock.getTimeMilliseconds();
+               const int       t=cfgBenchmark15_Iterations;
+               printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark15_Reference)*100/time,(t*1000)/time);
+       }
+       if(cfgBenchmark16_Enable)
+       {// Benchmark 16        
+               srand(380843);
+               btDbvt                                                          dbvt;
+               btAlignedObjectArray<btDbvtNode*>       batch;
+               btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
+               dbvt.optimizeTopDown();
+               batch.reserve(cfgBenchmark16_BatchCount);
+               printf("[16] insert/remove batch(%u): ",cfgBenchmark16_BatchCount);
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark16_Passes;++i)
+               {
+                       for(int j=0;j<cfgBenchmark16_BatchCount;++j)
+                       {
+                               batch.push_back(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0));
+                       }
+                       for(int j=0;j<cfgBenchmark16_BatchCount;++j)
+                       {
+                               dbvt.remove(batch[j]);
+                       }
+                       batch.resize(0);
+               }
+               const int       time=(int)wallclock.getTimeMilliseconds();
+               const int       ir=cfgBenchmark16_Passes*cfgBenchmark16_BatchCount;
+               printf("%u ms (%i%%),(%u bir/s)\r\n",time,(time-cfgBenchmark16_Reference)*100/time,int(ir*1000.0/time));
+       }
+       if(cfgBenchmark17_Enable)
+       {// Benchmark 17
+               srand(380843);
+               btAlignedObjectArray<btDbvtVolume>      volumes;
+               btAlignedObjectArray<int>                       results;
+               btAlignedObjectArray<int>                       indices;
+               volumes.resize(cfgLeaves);
+               results.resize(cfgLeaves);
+               indices.resize(cfgLeaves);
+               for(int i=0;i<cfgLeaves;++i)
+               {
+                       indices[i]=i;
+                       volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
+               }
+               for(int i=0;i<cfgLeaves;++i)
+               {
+                       btSwap(indices[i],indices[rand()%cfgLeaves]);
+               }
+               printf("[17] btDbvtVolume select: ");
+               wallclock.reset();
+               for(int i=0;i<cfgBenchmark17_Iterations;++i)
+               {
+                       for(int j=0;j<cfgLeaves;++j)
+                       {
+                               for(int k=0;k<cfgLeaves;++k)
+                               {
+                                       const int idx=indices[k];
+                                       results[idx]=Select(volumes[idx],volumes[j],volumes[k]);
+                               }
+                       }
+               }
+               const int time=(int)wallclock.getTimeMilliseconds();
+               printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark17_Reference)*100/time);
+       }
+       printf("\r\n\r\n");
+}
+#endif
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btDbvt.h b/extern/bullet2/BulletCollision/BroadphaseCollision/btDbvt.h
new file mode 100644 (file)
index 0000000..2bb8ef5
--- /dev/null
@@ -0,0 +1,1256 @@
+/*
+Bullet Continuous Collision Detection and Physics Library
+Copyright (c) 2003-2007 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.
+*/
+///btDbvt implementation by Nathanael Presson
+
+#ifndef BT_DYNAMIC_BOUNDING_VOLUME_TREE_H
+#define BT_DYNAMIC_BOUNDING_VOLUME_TREE_H
+
+#include "LinearMath/btAlignedObjectArray.h"
+#include "LinearMath/btVector3.h"
+#include "LinearMath/btTransform.h"
+#include "LinearMath/btAabbUtil2.h"
+
+//
+// Compile time configuration
+//
+
+
+// Implementation profiles
+#define DBVT_IMPL_GENERIC              0       // Generic implementation       
+#define DBVT_IMPL_SSE                  1       // SSE
+
+// Template implementation of ICollide
+#ifdef _WIN32
+#if (defined (_MSC_VER) && _MSC_VER >= 1400)
+#define        DBVT_USE_TEMPLATE               1
+#else
+#define        DBVT_USE_TEMPLATE               0
+#endif
+#else
+#define        DBVT_USE_TEMPLATE               0
+#endif
+
+// Use only intrinsics instead of inline asm
+#define DBVT_USE_INTRINSIC_SSE 1
+
+// Using memmov for collideOCL
+#define DBVT_USE_MEMMOVE               1
+
+// Enable benchmarking code
+#define        DBVT_ENABLE_BENCHMARK   0
+
+// Inlining
+#define DBVT_INLINE                            SIMD_FORCE_INLINE
+
+// Specific methods implementation
+
+//SSE gives errors on a MSVC 7.1
+#if defined (BT_USE_SSE) && defined (_WIN32)
+#define DBVT_SELECT_IMPL               DBVT_IMPL_SSE
+#define DBVT_MERGE_IMPL                        DBVT_IMPL_SSE
+#define DBVT_INT0_IMPL                 DBVT_IMPL_SSE
+#else
+#define DBVT_SELECT_IMPL               DBVT_IMPL_GENERIC
+#define DBVT_MERGE_IMPL                        DBVT_IMPL_GENERIC
+#define DBVT_INT0_IMPL                 DBVT_IMPL_GENERIC
+#endif
+
+#if    (DBVT_SELECT_IMPL==DBVT_IMPL_SSE)||     \
+       (DBVT_MERGE_IMPL==DBVT_IMPL_SSE)||      \
+       (DBVT_INT0_IMPL==DBVT_IMPL_SSE)
+#include <emmintrin.h>
+#endif
+
+//
+// Auto config and checks
+//
+
+#if DBVT_USE_TEMPLATE
+#define        DBVT_VIRTUAL
+#define DBVT_VIRTUAL_DTOR(a)
+#define DBVT_PREFIX                                    template <typename T>
+#define DBVT_IPOLICY                           T& policy
+#define DBVT_CHECKTYPE                         static const ICollide&  typechecker=*(T*)1;(void)typechecker;
+#else
+#define        DBVT_VIRTUAL_DTOR(a)            virtual ~a() {}
+#define DBVT_VIRTUAL                           virtual
+#define DBVT_PREFIX
+#define DBVT_IPOLICY                           ICollide& policy
+#define DBVT_CHECKTYPE
+#endif
+
+#if DBVT_USE_MEMMOVE
+#if !defined( __CELLOS_LV2__) && !defined(__MWERKS__)
+#include <memory.h>
+#endif
+#include <string.h>
+#endif
+
+#ifndef DBVT_USE_TEMPLATE
+#error "DBVT_USE_TEMPLATE undefined"
+#endif
+
+#ifndef DBVT_USE_MEMMOVE
+#error "DBVT_USE_MEMMOVE undefined"
+#endif
+
+#ifndef DBVT_ENABLE_BENCHMARK
+#error "DBVT_ENABLE_BENCHMARK undefined"
+#endif
+
+#ifndef DBVT_SELECT_IMPL
+#error "DBVT_SELECT_IMPL undefined"
+#endif
+
+#ifndef DBVT_MERGE_IMPL
+#error "DBVT_MERGE_IMPL undefined"
+#endif
+
+#ifndef DBVT_INT0_IMPL
+#error "DBVT_INT0_IMPL undefined"
+#endif
+
+//
+// Defaults volumes
+//
+
+/* btDbvtAabbMm                        */ 
+struct btDbvtAabbMm
+{
+       DBVT_INLINE btVector3                   Center() const  { return((mi+mx)/2); }
+       DBVT_INLINE btVector3                   Lengths() const { return(mx-mi); }
+       DBVT_INLINE btVector3                   Extents() const { return((mx-mi)/2); }
+       DBVT_INLINE const btVector3&    Mins() const    { return(mi); }
+       DBVT_INLINE const btVector3&    Maxs() const    { return(mx); }
+       static inline btDbvtAabbMm              FromCE(const btVector3& c,const btVector3& e);
+       static inline btDbvtAabbMm              FromCR(const btVector3& c,btScalar r);
+       static inline btDbvtAabbMm              FromMM(const btVector3& mi,const btVector3& mx);
+       static inline btDbvtAabbMm              FromPoints(const btVector3* pts,int n);
+       static inline btDbvtAabbMm              FromPoints(const btVector3** ppts,int n);
+       DBVT_INLINE void                                Expand(const btVector3& e);
+       DBVT_INLINE void                                SignedExpand(const btVector3& e);
+       DBVT_INLINE bool                                Contain(const btDbvtAabbMm& a) const;
+       DBVT_INLINE int                                 Classify(const btVector3& n,btScalar o,int s) const;
+       DBVT_INLINE btScalar                    ProjectMinimum(const btVector3& v,unsigned signs) const;
+       DBVT_INLINE friend bool                 Intersect(      const btDbvtAabbMm& a,
+               const btDbvtAabbMm& b);
+       
+       DBVT_INLINE friend bool                 Intersect(      const btDbvtAabbMm& a,
+               const btVector3& b);
+
+       DBVT_INLINE friend btScalar             Proximity(      const btDbvtAabbMm& a,
+               const btDbvtAabbMm& b);
+       DBVT_INLINE friend int                  Select(         const btDbvtAabbMm& o,
+               const btDbvtAabbMm& a,
+               const btDbvtAabbMm& b);
+       DBVT_INLINE friend void                 Merge(          const btDbvtAabbMm& a,
+               const btDbvtAabbMm& b,
+               btDbvtAabbMm& r);
+       DBVT_INLINE friend bool                 NotEqual(       const btDbvtAabbMm& a,
+               const btDbvtAabbMm& b);
+private:
+       DBVT_INLINE void                                AddSpan(const btVector3& d,btScalar& smi,btScalar& smx) const;
+private:
+       btVector3       mi,mx;
+};
+
+// Types       
+typedef        btDbvtAabbMm    btDbvtVolume;
+
+/* btDbvtNode                          */ 
+struct btDbvtNode
+{
+       btDbvtVolume    volume;
+       btDbvtNode*             parent;
+       DBVT_INLINE bool        isleaf() const          { return(childs[1]==0); }
+       DBVT_INLINE bool        isinternal() const      { return(!isleaf()); }
+       union
+       {
+               btDbvtNode*     childs[2];
+               void*   data;
+               int             dataAsInt;
+       };
+};
+
+///The btDbvt class implements a fast dynamic bounding volume tree based on axis aligned bounding boxes (aabb tree).
+///This btDbvt is used for soft body collision detection and for the btDbvtBroadphase. It has a fast insert, remove and update of nodes.
+///Unlike the btQuantizedBvh, nodes can be dynamically moved around, which allows for change in topology of the underlying data structure.
+struct btDbvt
+{
+       /* Stack element        */ 
+       struct  sStkNN
+       {
+               const btDbvtNode*       a;
+               const btDbvtNode*       b;
+               sStkNN() {}
+               sStkNN(const btDbvtNode* na,const btDbvtNode* nb) : a(na),b(nb) {}
+       };
+       struct  sStkNP
+       {
+               const btDbvtNode*       node;
+               int                     mask;
+               sStkNP(const btDbvtNode* n,unsigned m) : node(n),mask(m) {}
+       };
+       struct  sStkNPS
+       {
+               const btDbvtNode*       node;
+               int                     mask;
+               btScalar        value;
+               sStkNPS() {}
+               sStkNPS(const btDbvtNode* n,unsigned m,btScalar v) : node(n),mask(m),value(v) {}
+       };
+       struct  sStkCLN
+       {
+               const btDbvtNode*       node;
+               btDbvtNode*             parent;
+               sStkCLN(const btDbvtNode* n,btDbvtNode* p) : node(n),parent(p) {}
+       };
+       // Policies/Interfaces
+
+       /* ICollide     */ 
+       struct  ICollide
+       {               
+               DBVT_VIRTUAL_DTOR(ICollide)
+                       DBVT_VIRTUAL void       Process(const btDbvtNode*,const btDbvtNode*)            {}
+               DBVT_VIRTUAL void       Process(const btDbvtNode*)                                      {}
+               DBVT_VIRTUAL void       Process(const btDbvtNode* n,btScalar)                   { Process(n); }
+               DBVT_VIRTUAL bool       Descent(const btDbvtNode*)                                      { return(true); }
+               DBVT_VIRTUAL bool       AllLeaves(const btDbvtNode*)                                    { return(true); }
+       };
+       /* IWriter      */ 
+       struct  IWriter
+       {
+               virtual ~IWriter() {}
+               virtual void            Prepare(const btDbvtNode* root,int numnodes)=0;
+               virtual void            WriteNode(const btDbvtNode*,int index,int parent,int child0,int child1)=0;
+               virtual void            WriteLeaf(const btDbvtNode*,int index,int parent)=0;
+       };
+       /* IClone       */ 
+       struct  IClone
+       {
+               virtual ~IClone()       {}
+               virtual void            CloneLeaf(btDbvtNode*) {}
+       };
+
+       // Constants
+       enum    {
+               SIMPLE_STACKSIZE        =       64,
+               DOUBLE_STACKSIZE        =       SIMPLE_STACKSIZE*2
+       };
+
+       // Fields
+       btDbvtNode*             m_root;
+       btDbvtNode*             m_free;
+       int                             m_lkhd;
+       int                             m_leaves;
+       unsigned                m_opath;
+
+       
+       btAlignedObjectArray<sStkNN>    m_stkStack;
+
+
+       // Methods
+       btDbvt();
+       ~btDbvt();
+       void                    clear();
+       bool                    empty() const { return(0==m_root); }
+       void                    optimizeBottomUp();
+       void                    optimizeTopDown(int bu_treshold=128);
+       void                    optimizeIncremental(int passes);
+       btDbvtNode*             insert(const btDbvtVolume& box,void* data);
+       void                    update(btDbvtNode* leaf,int lookahead=-1);
+       void                    update(btDbvtNode* leaf,btDbvtVolume& volume);
+       bool                    update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity,btScalar margin);
+       bool                    update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity);
+       bool                    update(btDbvtNode* leaf,btDbvtVolume& volume,btScalar margin);  
+       void                    remove(btDbvtNode* leaf);
+       void                    write(IWriter* iwriter) const;
+       void                    clone(btDbvt& dest,IClone* iclone=0) const;
+       static int              maxdepth(const btDbvtNode* node);
+       static int              countLeaves(const btDbvtNode* node);
+       static void             extractLeaves(const btDbvtNode* node,btAlignedObjectArray<const btDbvtNode*>& leaves);
+#if DBVT_ENABLE_BENCHMARK
+       static void             benchmark();
+#else
+       static void             benchmark(){}
+#endif
+       // DBVT_IPOLICY must support ICollide policy/interface
+       DBVT_PREFIX
+               static void             enumNodes(      const btDbvtNode* root,
+               DBVT_IPOLICY);
+       DBVT_PREFIX
+               static void             enumLeaves(     const btDbvtNode* root,
+               DBVT_IPOLICY);
+       DBVT_PREFIX
+               void            collideTT(      const btDbvtNode* root0,
+               const btDbvtNode* root1,
+               DBVT_IPOLICY);
+
+       DBVT_PREFIX
+               void            collideTTpersistentStack(       const btDbvtNode* root0,
+                 const btDbvtNode* root1,
+                 DBVT_IPOLICY);
+#if 0
+       DBVT_PREFIX
+               void            collideTT(      const btDbvtNode* root0,
+               const btDbvtNode* root1,
+               const btTransform& xform,
+               DBVT_IPOLICY);
+       DBVT_PREFIX
+               void            collideTT(      const btDbvtNode* root0,
+               const btTransform& xform0,
+               const btDbvtNode* root1,
+               const btTransform& xform1,
+               DBVT_IPOLICY);
+#endif
+
+       DBVT_PREFIX
+               void            collideTV(      const btDbvtNode* root,
+               const btDbvtVolume& volume,
+               DBVT_IPOLICY);
+       ///rayTest is a re-entrant ray test, and can be called in parallel as long as the btAlignedAlloc is thread-safe (uses locking etc)
+       ///rayTest is slower than rayTestInternal, because it builds a local stack, using memory allocations, and it recomputes signs/rayDirectionInverses each time
+       DBVT_PREFIX
+               static void             rayTest(        const btDbvtNode* root,
+               const btVector3& rayFrom,
+               const btVector3& rayTo,
+               DBVT_IPOLICY);
+       ///rayTestInternal is faster than rayTest, because it uses a persistent stack (to reduce dynamic memory allocations to a minimum) and it uses precomputed signs/rayInverseDirections
+       ///rayTestInternal is used by btDbvtBroadphase to accelerate world ray casts
+       DBVT_PREFIX
+               void            rayTestInternal(        const btDbvtNode* root,
+                                                               const btVector3& rayFrom,
+                                                               const btVector3& rayTo,
+                                                               const btVector3& rayDirectionInverse,
+                                                               unsigned int signs[3],
+                                                               btScalar lambda_max,
+                                                               const btVector3& aabbMin,
+                                                               const btVector3& aabbMax,
+                                                               DBVT_IPOLICY) const;
+
+       DBVT_PREFIX
+               static void             collideKDOP(const btDbvtNode* root,
+               const btVector3* normals,
+               const btScalar* offsets,
+               int count,
+               DBVT_IPOLICY);
+       DBVT_PREFIX
+               static void             collideOCL(     const btDbvtNode* root,
+               const btVector3* normals,
+               const btScalar* offsets,
+               const btVector3& sortaxis,
+               int count,                                                              
+               DBVT_IPOLICY,
+               bool fullsort=true);
+       DBVT_PREFIX
+               static void             collideTU(      const btDbvtNode* root,
+               DBVT_IPOLICY);
+       // Helpers      
+       static DBVT_INLINE int  nearest(const int* i,const btDbvt::sStkNPS* a,btScalar v,int l,int h)
+       {
+               int     m=0;
+               while(l<h)
+               {
+                       m=(l+h)>>1;
+                       if(a[i[m]].value>=v) l=m+1; else h=m;
+               }
+               return(h);
+       }
+       static DBVT_INLINE int  allocate(       btAlignedObjectArray<int>& ifree,
+               btAlignedObjectArray<sStkNPS>& stock,
+               const sStkNPS& value)
+       {
+               int     i;
+               if(ifree.size()>0)
+               { i=ifree[ifree.size()-1];ifree.pop_back();stock[i]=value; }
+               else
+               { i=stock.size();stock.push_back(value); }
+               return(i); 
+       }
+       //
+private:
+       btDbvt(const btDbvt&)   {}      
+};
+
+//
+// Inline's
+//
+
+//
+inline btDbvtAabbMm                    btDbvtAabbMm::FromCE(const btVector3& c,const btVector3& e)
+{
+       btDbvtAabbMm box;
+       box.mi=c-e;box.mx=c+e;
+       return(box);
+}
+
+//
+inline btDbvtAabbMm                    btDbvtAabbMm::FromCR(const btVector3& c,btScalar r)
+{
+       return(FromCE(c,btVector3(r,r,r)));
+}
+
+//
+inline btDbvtAabbMm                    btDbvtAabbMm::FromMM(const btVector3& mi,const btVector3& mx)
+{
+       btDbvtAabbMm box;
+       box.mi=mi;box.mx=mx;
+       return(box);
+}
+
+//
+inline btDbvtAabbMm                    btDbvtAabbMm::FromPoints(const btVector3* pts,int n)
+{
+       btDbvtAabbMm box;
+       box.mi=box.mx=pts[0];
+       for(int i=1;i<n;++i)
+       {
+               box.mi.setMin(pts[i]);
+               box.mx.setMax(pts[i]);
+       }
+       return(box);
+}
+
+//
+inline btDbvtAabbMm                    btDbvtAabbMm::FromPoints(const btVector3** ppts,int n)
+{
+       btDbvtAabbMm box;
+       box.mi=box.mx=*ppts[0];
+       for(int i=1;i<n;++i)
+       {
+               box.mi.setMin(*ppts[i]);
+               box.mx.setMax(*ppts[i]);
+       }
+       return(box);
+}
+
+//
+DBVT_INLINE void               btDbvtAabbMm::Expand(const btVector3& e)
+{
+       mi-=e;mx+=e;
+}
+
+//
+DBVT_INLINE void               btDbvtAabbMm::SignedExpand(const btVector3& e)
+{
+       if(e.x()>0) mx.setX(mx.x()+e[0]); else mi.setX(mi.x()+e[0]);
+       if(e.y()>0) mx.setY(mx.y()+e[1]); else mi.setY(mi.y()+e[1]);
+       if(e.z()>0) mx.setZ(mx.z()+e[2]); else mi.setZ(mi.z()+e[2]);
+}
+
+//
+DBVT_INLINE bool               btDbvtAabbMm::Contain(const btDbvtAabbMm& a) const
+{
+       return( (mi.x()<=a.mi.x())&&
+               (mi.y()<=a.mi.y())&&
+               (mi.z()<=a.mi.z())&&
+               (mx.x()>=a.mx.x())&&
+               (mx.y()>=a.mx.y())&&
+               (mx.z()>=a.mx.z()));
+}
+
+//
+DBVT_INLINE int                btDbvtAabbMm::Classify(const btVector3& n,btScalar o,int s) const
+{
+       btVector3                       pi,px;
+       switch(s)
+       {
+       case    (0+0+0):        px=btVector3(mi.x(),mi.y(),mi.z());
+               pi=btVector3(mx.x(),mx.y(),mx.z());break;
+       case    (1+0+0):        px=btVector3(mx.x(),mi.y(),mi.z());
+               pi=btVector3(mi.x(),mx.y(),mx.z());break;
+       case    (0+2+0):        px=btVector3(mi.x(),mx.y(),mi.z());
+               pi=btVector3(mx.x(),mi.y(),mx.z());break;
+       case    (1+2+0):        px=btVector3(mx.x(),mx.y(),mi.z());
+               pi=btVector3(mi.x(),mi.y(),mx.z());break;
+       case    (0+0+4):        px=btVector3(mi.x(),mi.y(),mx.z());
+               pi=btVector3(mx.x(),mx.y(),mi.z());break;
+       case    (1+0+4):        px=btVector3(mx.x(),mi.y(),mx.z());
+               pi=btVector3(mi.x(),mx.y(),mi.z());break;
+       case    (0+2+4):        px=btVector3(mi.x(),mx.y(),mx.z());
+               pi=btVector3(mx.x(),mi.y(),mi.z());break;
+       case    (1+2+4):        px=btVector3(mx.x(),mx.y(),mx.z());
+               pi=btVector3(mi.x(),mi.y(),mi.z());break;
+       }
+       if((btDot(n,px)+o)<0)           return(-1);
+       if((btDot(n,pi)+o)>=0)  return(+1);
+       return(0);
+}
+
+//
+DBVT_INLINE btScalar   btDbvtAabbMm::ProjectMinimum(const btVector3& v,unsigned signs) const
+{
+       const btVector3*        b[]={&mx,&mi};
+       const btVector3         p(      b[(signs>>0)&1]->x(),
+               b[(signs>>1)&1]->y(),
+               b[(signs>>2)&1]->z());
+       return(btDot(p,v));
+}
+
+//
+DBVT_INLINE void               btDbvtAabbMm::AddSpan(const btVector3& d,btScalar& smi,btScalar& smx) const
+{
+       for(int i=0;i<3;++i)
+       {
+               if(d[i]<0)
+               { smi+=mx[i]*d[i];smx+=mi[i]*d[i]; }
+               else
+               { smi+=mi[i]*d[i];smx+=mx[i]*d[i]; }
+       }
+}
+
+//
+DBVT_INLINE bool               Intersect(      const btDbvtAabbMm& a,
+                                                                 const btDbvtAabbMm& b)
+{
+#if    DBVT_INT0_IMPL == DBVT_IMPL_SSE
+       const __m128    rt(_mm_or_ps(   _mm_cmplt_ps(_mm_load_ps(b.mx),_mm_load_ps(a.mi)),
+               _mm_cmplt_ps(_mm_load_ps(a.mx),_mm_load_ps(b.mi))));
+       const __int32*  pu((const __int32*)&rt);
+       return((pu[0]|pu[1]|pu[2])==0);
+#else
+       return( (a.mi.x()<=b.mx.x())&&
+               (a.mx.x()>=b.mi.x())&&
+               (a.mi.y()<=b.mx.y())&&
+               (a.mx.y()>=b.mi.y())&&
+               (a.mi.z()<=b.mx.z())&&          
+               (a.mx.z()>=b.mi.z()));
+#endif
+}
+
+
+
+//
+DBVT_INLINE bool               Intersect(      const btDbvtAabbMm& a,
+                                                                 const btVector3& b)
+{
+       return( (b.x()>=a.mi.x())&&
+               (b.y()>=a.mi.y())&&
+               (b.z()>=a.mi.z())&&
+               (b.x()<=a.mx.x())&&
+               (b.y()<=a.mx.y())&&
+               (b.z()<=a.mx.z()));
+}
+
+
+
+
+
+//////////////////////////////////////
+
+
+//
+DBVT_INLINE btScalar   Proximity(      const btDbvtAabbMm& a,
+                                                                 const btDbvtAabbMm& b)
+{
+       const btVector3 d=(a.mi+a.mx)-(b.mi+b.mx);
+       return(btFabs(d.x())+btFabs(d.y())+btFabs(d.z()));
+}
+
+
+
+//
+DBVT_INLINE int                        Select( const btDbvtAabbMm& o,
+                                                          const btDbvtAabbMm& a,
+                                                          const btDbvtAabbMm& b)
+{
+#if    DBVT_SELECT_IMPL == DBVT_IMPL_SSE
+       static ATTRIBUTE_ALIGNED16(const unsigned __int32)      mask[]={0x7fffffff,0x7fffffff,0x7fffffff,0x7fffffff};
+       ///@todo: the intrinsic version is 11% slower
+#if DBVT_USE_INTRINSIC_SSE
+
+       union btSSEUnion ///NOTE: if we use more intrinsics, move btSSEUnion into the LinearMath directory
+       {
+          __m128               ssereg;
+          float                floats[4];
+          int                  ints[4];
+       };
+
+       __m128  omi(_mm_load_ps(o.mi));
+       omi=_mm_add_ps(omi,_mm_load_ps(o.mx));
+       __m128  ami(_mm_load_ps(a.mi));
+       ami=_mm_add_ps(ami,_mm_load_ps(a.mx));
+       ami=_mm_sub_ps(ami,omi);
+       ami=_mm_and_ps(ami,_mm_load_ps((const float*)mask));
+       __m128  bmi(_mm_load_ps(b.mi));
+       bmi=_mm_add_ps(bmi,_mm_load_ps(b.mx));
+       bmi=_mm_sub_ps(bmi,omi);
+       bmi=_mm_and_ps(bmi,_mm_load_ps((const float*)mask));
+       __m128  t0(_mm_movehl_ps(ami,ami));
+       ami=_mm_add_ps(ami,t0);
+       ami=_mm_add_ss(ami,_mm_shuffle_ps(ami,ami,1));
+       __m128 t1(_mm_movehl_ps(bmi,bmi));
+       bmi=_mm_add_ps(bmi,t1);
+       bmi=_mm_add_ss(bmi,_mm_shuffle_ps(bmi,bmi,1));
+       
+       btSSEUnion tmp;
+       tmp.ssereg = _mm_cmple_ss(bmi,ami);
+       return tmp.ints[0]&1;
+
+#else
+       ATTRIBUTE_ALIGNED16(__int32     r[1]);
+       __asm
+       {
+               mov             eax,o
+                       mov             ecx,a
+                       mov             edx,b
+                       movaps  xmm0,[eax]
+               movaps  xmm5,mask
+                       addps   xmm0,[eax+16]   
+               movaps  xmm1,[ecx]
+               movaps  xmm2,[edx]
+               addps   xmm1,[ecx+16]
+               addps   xmm2,[edx+16]
+               subps   xmm1,xmm0
+                       subps   xmm2,xmm0
+                       andps   xmm1,xmm5
+                       andps   xmm2,xmm5
+                       movhlps xmm3,xmm1
+                       movhlps xmm4,xmm2
+                       addps   xmm1,xmm3
+                       addps   xmm2,xmm4
+                       pshufd  xmm3,xmm1,1
+                       pshufd  xmm4,xmm2,1
+                       addss   xmm1,xmm3
+                       addss   xmm2,xmm4
+                       cmpless xmm2,xmm1
+                       movss   r,xmm2
+       }
+       return(r[0]&1);
+#endif
+#else
+       return(Proximity(o,a)<Proximity(o,b)?0:1);
+#endif
+}
+
+//
+DBVT_INLINE void               Merge(  const btDbvtAabbMm& a,
+                                                         const btDbvtAabbMm& b,
+                                                         btDbvtAabbMm& r)
+{
+#if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
+       __m128  ami(_mm_load_ps(a.mi));
+       __m128  amx(_mm_load_ps(a.mx));
+       __m128  bmi(_mm_load_ps(b.mi));
+       __m128  bmx(_mm_load_ps(b.mx));
+       ami=_mm_min_ps(ami,bmi);
+       amx=_mm_max_ps(amx,bmx);
+       _mm_store_ps(r.mi,ami);
+       _mm_store_ps(r.mx,amx);
+#else
+       for(int i=0;i<3;++i)
+       {
+               if(a.mi[i]<b.mi[i]) r.mi[i]=a.mi[i]; else r.mi[i]=b.mi[i];
+               if(a.mx[i]>b.mx[i]) r.mx[i]=a.mx[i]; else r.mx[i]=b.mx[i];
+       }
+#endif
+}
+
+//
+DBVT_INLINE bool               NotEqual(       const btDbvtAabbMm& a,
+                                                                const btDbvtAabbMm& b)
+{
+       return( (a.mi.x()!=b.mi.x())||
+               (a.mi.y()!=b.mi.y())||
+               (a.mi.z()!=b.mi.z())||
+               (a.mx.x()!=b.mx.x())||
+               (a.mx.y()!=b.mx.y())||
+               (a.mx.z()!=b.mx.z()));
+}
+
+//
+// Inline's
+//
+
+//
+DBVT_PREFIX
+inline void            btDbvt::enumNodes(      const btDbvtNode* root,
+                                                                 DBVT_IPOLICY)
+{
+       DBVT_CHECKTYPE
+               policy.Process(root);
+       if(root->isinternal())
+       {
+               enumNodes(root->childs[0],policy);
+               enumNodes(root->childs[1],policy);
+       }
+}
+
+//
+DBVT_PREFIX
+inline void            btDbvt::enumLeaves(     const btDbvtNode* root,
+                                                                  DBVT_IPOLICY)
+{
+       DBVT_CHECKTYPE
+               if(root->isinternal())
+               {
+                       enumLeaves(root->childs[0],policy);
+                       enumLeaves(root->childs[1],policy);
+               }
+               else
+               {
+                       policy.Process(root);
+               }
+}
+
+//
+DBVT_PREFIX
+inline void            btDbvt::collideTT(      const btDbvtNode* root0,
+                                                                 const btDbvtNode* root1,
+                                                                 DBVT_IPOLICY)
+{
+       DBVT_CHECKTYPE
+               if(root0&&root1)
+               {
+                       int                                                             depth=1;
+                       int                                                             treshold=DOUBLE_STACKSIZE-4;
+                       btAlignedObjectArray<sStkNN>    stkStack;
+                       stkStack.resize(DOUBLE_STACKSIZE);
+                       stkStack[0]=sStkNN(root0,root1);
+                       do      {               
+                               sStkNN  p=stkStack[--depth];
+                               if(depth>treshold)
+                               {
+                                       stkStack.resize(stkStack.size()*2);
+                                       treshold=stkStack.size()-4;
+                               }
+                               if(p.a==p.b)
+                               {
+                                       if(p.a->isinternal())
+                                       {
+                                               stkStack[depth++]=sStkNN(p.a->childs[0],p.a->childs[0]);
+                                               stkStack[depth++]=sStkNN(p.a->childs[1],p.a->childs[1]);
+                                               stkStack[depth++]=sStkNN(p.a->childs[0],p.a->childs[1]);
+                                       }
+                               }
+                               else if(Intersect(p.a->volume,p.b->volume))
+                               {
+                                       if(p.a->isinternal())
+                                       {
+                                               if(p.b->isinternal())
+                                               {
+                                                       stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[0]);
+                                                       stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[0]);
+                                                       stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[1]);
+                                                       stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[1]);
+                                               }
+                                               else
+                                               {
+                                                       stkStack[depth++]=sStkNN(p.a->childs[0],p.b);
+                                                       stkStack[depth++]=sStkNN(p.a->childs[1],p.b);
+                                               }
+                                       }
+                                       else
+                                       {
+                                               if(p.b->isinternal())
+                                               {
+                                                       stkStack[depth++]=sStkNN(p.a,p.b->childs[0]);
+                                                       stkStack[depth++]=sStkNN(p.a,p.b->childs[1]);
+                                               }
+                                               else
+                                               {
+                                                       policy.Process(p.a,p.b);
+                                               }
+                                       }
+                               }
+                       } while(depth);
+               }
+}
+
+
+
+DBVT_PREFIX
+inline void            btDbvt::collideTTpersistentStack(       const btDbvtNode* root0,
+                                                                 const btDbvtNode* root1,
+                                                                 DBVT_IPOLICY)
+{
+       DBVT_CHECKTYPE
+               if(root0&&root1)
+               {
+                       int                                                             depth=1;
+                       int                                                             treshold=DOUBLE_STACKSIZE-4;
+                       
+                       m_stkStack.resize(DOUBLE_STACKSIZE);
+                       m_stkStack[0]=sStkNN(root0,root1);
+                       do      {               
+                               sStkNN  p=m_stkStack[--depth];
+                               if(depth>treshold)
+                               {
+                                       m_stkStack.resize(m_stkStack.size()*2);
+                                       treshold=m_stkStack.size()-4;
+                               }
+                               if(p.a==p.b)
+                               {
+                                       if(p.a->isinternal())
+                                       {
+                                               m_stkStack[depth++]=sStkNN(p.a->childs[0],p.a->childs[0]);
+                                               m_stkStack[depth++]=sStkNN(p.a->childs[1],p.a->childs[1]);
+                                               m_stkStack[depth++]=sStkNN(p.a->childs[0],p.a->childs[1]);
+                                       }
+                               }
+                               else if(Intersect(p.a->volume,p.b->volume))
+                               {
+                                       if(p.a->isinternal())
+                                       {
+                                               if(p.b->isinternal())
+                                               {
+                                                       m_stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[0]);
+                                                       m_stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[0]);
+                                                       m_stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[1]);
+                                                       m_stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[1]);
+                                               }
+                                               else
+                                               {
+                                                       m_stkStack[depth++]=sStkNN(p.a->childs[0],p.b);
+                                                       m_stkStack[depth++]=sStkNN(p.a->childs[1],p.b);
+                                               }
+                                       }
+                                       else
+                                       {
+                                               if(p.b->isinternal())
+                                               {
+                                                       m_stkStack[depth++]=sStkNN(p.a,p.b->childs[0]);
+                                                       m_stkStack[depth++]=sStkNN(p.a,p.b->childs[1]);
+                                               }
+                                               else
+                                               {
+                                                       policy.Process(p.a,p.b);
+                                               }
+                                       }
+                               }
+                       } while(depth);
+               }
+}
+
+#if 0
+//
+DBVT_PREFIX
+inline void            btDbvt::collideTT(      const btDbvtNode* root0,
+                                                                 const btDbvtNode* root1,
+                                                                 const btTransform& xform,
+                                                                 DBVT_IPOLICY)
+{
+       DBVT_CHECKTYPE
+               if(root0&&root1)
+               {
+                       int                                                             depth=1;
+                       int                                                             treshold=DOUBLE_STACKSIZE-4;
+                       btAlignedObjectArray<sStkNN>    stkStack;
+                       stkStack.resize(DOUBLE_STACKSIZE);
+                       stkStack[0]=sStkNN(root0,root1);
+                       do      {
+                               sStkNN  p=stkStack[--depth];
+                               if(Intersect(p.a->volume,p.b->volume,xform))
+                               {
+                                       if(depth>treshold)
+                                       {
+                                               stkStack.resize(stkStack.size()*2);
+                                               treshold=stkStack.size()-4;
+                                       }
+                                       if(p.a->isinternal())
+                                       {
+                                               if(p.b->isinternal())
+                                               {                                       
+                                                       stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[0]);
+                                                       stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[0]);
+                                                       stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[1]);
+                                                       stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[1]);
+                                               }
+                                               else
+                                               {
+                                                       stkStack[depth++]=sStkNN(p.a->childs[0],p.b);
+                                                       stkStack[depth++]=sStkNN(p.a->childs[1],p.b);
+                                               }
+                                       }
+                                       else
+                                       {
+                                               if(p.b->isinternal())
+                                               {
+                                                       stkStack[depth++]=sStkNN(p.a,p.b->childs[0]);
+                                                       stkStack[depth++]=sStkNN(p.a,p.b->childs[1]);
+                                               }
+                                               else
+                                               {
+                                                       policy.Process(p.a,p.b);
+                                               }
+                                       }
+                               }
+                       } while(depth);
+               }
+}
+//
+DBVT_PREFIX
+inline void            btDbvt::collideTT(      const btDbvtNode* root0,
+                                                                 const btTransform& xform0,
+                                                                 const btDbvtNode* root1,
+                                                                 const btTransform& xform1,
+                                                                 DBVT_IPOLICY)
+{
+       const btTransform       xform=xform0.inverse()*xform1;
+       collideTT(root0,root1,xform,policy);
+}
+#endif 
+
+//
+DBVT_PREFIX
+inline void            btDbvt::collideTV(      const btDbvtNode* root,
+                                                                 const btDbvtVolume& vol,
+                                                                 DBVT_IPOLICY)
+{
+       DBVT_CHECKTYPE
+               if(root)
+               {
+                       ATTRIBUTE_ALIGNED16(btDbvtVolume)               volume(vol);
+                       btAlignedObjectArray<const btDbvtNode*> stack;
+                       stack.resize(0);
+                       stack.reserve(SIMPLE_STACKSIZE);
+                       stack.push_back(root);
+                       do      {
+                               const btDbvtNode*       n=stack[stack.size()-1];
+                               stack.pop_back();
+                               if(Intersect(n->volume,volume))
+                               {
+                                       if(n->isinternal())
+                                       {
+                                               stack.push_back(n->childs[0]);
+                                               stack.push_back(n->childs[1]);
+                                       }
+                                       else
+                                       {
+                                               policy.Process(n);
+                                       }
+                               }
+                       } while(stack.size()>0);
+               }
+}
+
+DBVT_PREFIX
+inline void            btDbvt::rayTestInternal(        const btDbvtNode* root,
+                                                               const btVector3& rayFrom,
+                                                               const btVector3& rayTo,
+                                                               const btVector3& rayDirectionInverse,
+                                                               unsigned int signs[3],
+                                                               btScalar lambda_max,
+                                                               const btVector3& aabbMin,
+                                                               const btVector3& aabbMax,
+                                                               DBVT_IPOLICY) const
+{
+        (void) rayTo;
+       DBVT_CHECKTYPE
+       if(root)
+       {
+               btVector3 resultNormal;
+
+               int                                                             depth=1;
+               int                                                             treshold=DOUBLE_STACKSIZE-2;
+               btAlignedObjectArray<const btDbvtNode*> stack;
+               stack.resize(DOUBLE_STACKSIZE);
+               stack[0]=root;
+               btVector3 bounds[2];
+               do      
+               {
+                       const btDbvtNode*       node=stack[--depth];
+                       bounds[0] = node->volume.Mins()-aabbMax;
+                       bounds[1] = node->volume.Maxs()-aabbMin;
+                       btScalar tmin=1.f,lambda_min=0.f;
+                       unsigned int result1=false;
+                       result1 = btRayAabb2(rayFrom,rayDirectionInverse,signs,bounds,tmin,lambda_min,lambda_max);
+                       if(result1)
+                       {
+                               if(node->isinternal())
+                               {
+                                       if(depth>treshold)
+                                       {
+                                               stack.resize(stack.size()*2);
+                                               treshold=stack.size()-2;
+                                       }
+                                       stack[depth++]=node->childs[0];
+                                       stack[depth++]=node->childs[1];
+                               }
+                               else
+                               {
+                                       policy.Process(node);
+                               }
+                       }
+               } while(depth);
+       }
+}
+
+//
+DBVT_PREFIX
+inline void            btDbvt::rayTest(        const btDbvtNode* root,
+                                                               const btVector3& rayFrom,
+                                                               const btVector3& rayTo,
+                                                               DBVT_IPOLICY)
+{
+       DBVT_CHECKTYPE
+               if(root)
+               {
+                       btVector3 rayDir = (rayTo-rayFrom);
+                       rayDir.normalize ();
+
+                       ///what about division by zero? --> just set rayDirection[i] to INF/BT_LARGE_FLOAT
+                       btVector3 rayDirectionInverse;
+                       rayDirectionInverse[0] = rayDir[0] == btScalar(0.0) ? btScalar(BT_LARGE_FLOAT) : btScalar(1.0) / rayDir[0];
+                       rayDirectionInverse[1] = rayDir[1] == btScalar(0.0) ? btScalar(BT_LARGE_FLOAT) : btScalar(1.0) / rayDir[1];
+                       rayDirectionInverse[2] = rayDir[2] == btScalar(0.0) ? btScalar(BT_LARGE_FLOAT) : btScalar(1.0) / rayDir[2];
+                       unsigned int signs[3] = { rayDirectionInverse[0] < 0.0, rayDirectionInverse[1] < 0.0, rayDirectionInverse[2] < 0.0};
+
+                       btScalar lambda_max = rayDir.dot(rayTo-rayFrom);
+
+                       btVector3 resultNormal;
+
+                       btAlignedObjectArray<const btDbvtNode*> stack;
+
+                       int                                                             depth=1;
+                       int                                                             treshold=DOUBLE_STACKSIZE-2;
+
+                       stack.resize(DOUBLE_STACKSIZE);
+                       stack[0]=root;
+                       btVector3 bounds[2];
+                       do      {
+                               const btDbvtNode*       node=stack[--depth];
+
+                               bounds[0] = node->volume.Mins();
+                               bounds[1] = node->volume.Maxs();
+                               
+                               btScalar tmin=1.f,lambda_min=0.f;
+                               unsigned int result1 = btRayAabb2(rayFrom,rayDirectionInverse,signs,bounds,tmin,lambda_min,lambda_max);
+
+#ifdef COMPARE_BTRAY_AABB2
+                               btScalar param=1.f;
+                               bool result2 = btRayAabb(rayFrom,rayTo,node->volume.Mins(),node->volume.Maxs(),param,resultNormal);
+                               btAssert(result1 == result2);
+#endif //TEST_BTRAY_AABB2
+
+                               if(result1)
+                               {
+                                       if(node->isinternal())
+                                       {
+                                               if(depth>treshold)
+                                               {
+                                                       stack.resize(stack.size()*2);
+                                                       treshold=stack.size()-2;
+                                               }
+                                               stack[depth++]=node->childs[0];
+                                               stack[depth++]=node->childs[1];
+                                       }
+                                       else
+                                       {
+                                               policy.Process(node);
+                                       }
+                               }
+                       } while(depth);
+
+               }
+}
+
+//
+DBVT_PREFIX
+inline void            btDbvt::collideKDOP(const btDbvtNode* root,
+                                                                       const btVector3* normals,
+                                                                       const btScalar* offsets,
+                                                                       int count,
+                                                                       DBVT_IPOLICY)
+{
+       DBVT_CHECKTYPE
+               if(root)
+               {
+                       const int                                               inside=(1<<count)-1;
+                       btAlignedObjectArray<sStkNP>    stack;
+                       int                                                             signs[sizeof(unsigned)*8];
+                       btAssert(count<int (sizeof(signs)/sizeof(signs[0])));
+                       for(int i=0;i<count;++i)
+                       {
+                               signs[i]=       ((normals[i].x()>=0)?1:0)+
+                                       ((normals[i].y()>=0)?2:0)+
+                                       ((normals[i].z()>=0)?4:0);
+                       }
+                       stack.reserve(SIMPLE_STACKSIZE);
+                       stack.push_back(sStkNP(root,0));
+                       do      {
+                               sStkNP  se=stack[stack.size()-1];
+                               bool    out=false;
+                               stack.pop_back();
+                               for(int i=0,j=1;(!out)&&(i<count);++i,j<<=1)
+                               {
+                                       if(0==(se.mask&j))
+                                       {
+                                               const int       side=se.node->volume.Classify(normals[i],offsets[i],signs[i]);
+                                               switch(side)
+                                               {
+                                               case    -1:     out=true;break;
+                                               case    +1:     se.mask|=j;break;
+                                               }
+                                       }
+                               }
+                               if(!out)
+                               {
+                                       if((se.mask!=inside)&&(se.node->isinternal()))
+                                       {
+                                               stack.push_back(sStkNP(se.node->childs[0],se.mask));
+                                               stack.push_back(sStkNP(se.node->childs[1],se.mask));
+                                       }
+                                       else
+                                       {
+                                               if(policy.AllLeaves(se.node)) enumLeaves(se.node,policy);
+                                       }
+                               }
+                       } while(stack.size());
+               }
+}
+
+//
+DBVT_PREFIX
+inline void            btDbvt::collideOCL(     const btDbvtNode* root,
+                                                                  const btVector3* normals,
+                                                                  const btScalar* offsets,
+                                                                  const btVector3& sortaxis,
+                                                                  int count,
+                                                                  DBVT_IPOLICY,
+                                                                  bool fsort)
+{
+       DBVT_CHECKTYPE
+               if(root)
+               {
+                       const unsigned                                  srtsgns=(sortaxis[0]>=0?1:0)+
+                               (sortaxis[1]>=0?2:0)+
+                               (sortaxis[2]>=0?4:0);
+                       const int                                               inside=(1<<count)-1;
+                       btAlignedObjectArray<sStkNPS>   stock;
+                       btAlignedObjectArray<int>               ifree;
+                       btAlignedObjectArray<int>               stack;
+                       int                                                             signs[sizeof(unsigned)*8];
+                       btAssert(count<int (sizeof(signs)/sizeof(signs[0])));
+                       for(int i=0;i<count;++i)
+                       {
+                               signs[i]=       ((normals[i].x()>=0)?1:0)+
+                                       ((normals[i].y()>=0)?2:0)+
+                                       ((normals[i].z()>=0)?4:0);
+                       }
+                       stock.reserve(SIMPLE_STACKSIZE);
+                       stack.reserve(SIMPLE_STACKSIZE);
+                       ifree.reserve(SIMPLE_STACKSIZE);
+                       stack.push_back(allocate(ifree,stock,sStkNPS(root,0,root->volume.ProjectMinimum(sortaxis,srtsgns))));
+                       do      {
+                               const int       id=stack[stack.size()-1];
+                               sStkNPS         se=stock[id];
+                               stack.pop_back();ifree.push_back(id);
+                               if(se.mask!=inside)
+                               {
+                                       bool    out=false;
+                                       for(int i=0,j=1;(!out)&&(i<count);++i,j<<=1)
+                                       {
+                                               if(0==(se.mask&j))
+                                               {
+                                                       const int       side=se.node->volume.Classify(normals[i],offsets[i],signs[i]);
+                                                       switch(side)
+                                                       {
+                                                       case    -1:     out=true;break;
+                                                       case    +1:     se.mask|=j;break;
+                                                       }
+                                               }
+                                       }
+                                       if(out) continue;
+                               }
+                               if(policy.Descent(se.node))
+                               {
+                                       if(se.node->isinternal())
+                                       {
+                                               const btDbvtNode* pns[]={       se.node->childs[0],se.node->childs[1]};
+                                               sStkNPS         nes[]={ sStkNPS(pns[0],se.mask,pns[0]->volume.ProjectMinimum(sortaxis,srtsgns)),
+                                                       sStkNPS(pns[1],se.mask,pns[1]->volume.ProjectMinimum(sortaxis,srtsgns))};
+                                               const int       q=nes[0].value<nes[1].value?1:0;                                
+                                               int                     j=stack.size();
+                                               if(fsort&&(j>0))
+                                               {
+                                                       /* Insert 0     */ 
+                                                       j=nearest(&stack[0],&stock[0],nes[q].value,0,stack.size());
+                                                       stack.push_back(0);
+#if DBVT_USE_MEMMOVE
+                                                       memmove(&stack[j+1],&stack[j],sizeof(int)*(stack.size()-j-1));
+#else
+                                                       for(int k=stack.size()-1;k>j;--k) stack[k]=stack[k-1];
+#endif
+                                                       stack[j]=allocate(ifree,stock,nes[q]);
+                                                       /* Insert 1     */ 
+                                                       j=nearest(&stack[0],&stock[0],nes[1-q].value,j,stack.size());
+                                                       stack.push_back(0);
+#if DBVT_USE_MEMMOVE
+                                                       memmove(&stack[j+1],&stack[j],sizeof(int)*(stack.size()-j-1));
+#else
+                                                       for(int k=stack.size()-1;k>j;--k) stack[k]=stack[k-1];
+#endif
+                                                       stack[j]=allocate(ifree,stock,nes[1-q]);
+                                               }
+                                               else
+                                               {
+                                                       stack.push_back(allocate(ifree,stock,nes[q]));
+                                                       stack.push_back(allocate(ifree,stock,nes[1-q]));
+                                               }
+                                       }
+                                       else
+                                       {
+                                               policy.Process(se.node,se.value);
+                                       }
+                               }
+                       } while(stack.size());
+               }
+}
+
+//
+DBVT_PREFIX
+inline void            btDbvt::collideTU(      const btDbvtNode* root,
+                                                                 DBVT_IPOLICY)
+{
+       DBVT_CHECKTYPE
+               if(root)
+               {
+                       btAlignedObjectArray<const btDbvtNode*> stack;
+                       stack.reserve(SIMPLE_STACKSIZE);
+                       stack.push_back(root);
+                       do      {
+                               const btDbvtNode*       n=stack[stack.size()-1];
+                               stack.pop_back();
+                               if(policy.Descent(n))
+                               {
+                                       if(n->isinternal())
+                                       { stack.push_back(n->childs[0]);stack.push_back(n->childs[1]); }
+                                       else
+                                       { policy.Process(n); }
+                               }
+                       } while(stack.size()>0);
+               }
+}
+
+//
+// PP Cleanup
+//
+
+#undef DBVT_USE_MEMMOVE
+#undef DBVT_USE_TEMPLATE
+#undef DBVT_VIRTUAL_DTOR
+#undef DBVT_VIRTUAL
+#undef DBVT_PREFIX
+#undef DBVT_IPOLICY
+#undef DBVT_CHECKTYPE
+#undef DBVT_IMPL_GENERIC
+#undef DBVT_IMPL_SSE
+#undef DBVT_USE_INTRINSIC_SSE
+#undef DBVT_SELECT_IMPL
+#undef DBVT_MERGE_IMPL
+#undef DBVT_INT0_IMPL
+
+#endif
diff --git a/extern/bullet2/BulletCollision/BroadphaseCollision/btDbvtBroadphase.cpp b/extern/bullet2/BulletCollision/BroadphaseCollision/btDbvtBroadphase.cpp
new file mode 100644 (file)
index 0000000..75cfac6
--- /dev/null
@@ -0,0 +1,796 @@
+/*
+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.
+*/
+
+///btDbvtBroadphase implementation by Nathanael Presson
+
+#include "btDbvtBroadphase.h"
+
+//
+// Profiling
+//
+
+#if DBVT_BP_PROFILE||DBVT_BP_ENABLE_BENCHMARK
+#include <stdio.h>
+#endif
+
+#if DBVT_BP_PROFILE
+struct ProfileScope
+{
+       __forceinline ProfileScope(btClock& clock,unsigned long& value) :
+       m_clock(&clock),m_value(&value),m_base(clock.getTimeMicroseconds())
+       {
+       }
+       __forceinline ~ProfileScope()
+       {
+               (*m_value)+=m_clock->getTimeMicroseconds()-m_base;
+       }
+       btClock*                m_clock;
+       unsigned long*  m_value;
+       unsigned long   m_base;
+};
+#define        SPC(_value_)    ProfileScope    spc_scope(m_clock,_value_)
+#else
+#define        SPC(_value_)
+#endif
+
+//
+// Helpers
+//
+
+//
+template <typename T>
+static inline void     listappend(T* item,T*& list)
+{
+       item->links[0]=0;
+       item->links[1]=list;
+       if(list) list->links[0]=item;
+       list=item;
+}
+
+//
+template <typename T>
+static inline void     listremove(T* item,T*& list)
+{
+       if(item->links[0]) item->links[0]->links[1]=item->links[1]; else list=item->links[1];
+       if(item->links[1]) item->links[1]->links[0]=item->links[0];
+}
+
+//
+template <typename T>
+static inline int      listcount(T* root)
+{
+       int     n=0;
+       while(root) { ++n;root=root->links[1]; }
+       return(n);
+}
+
+//
+template <typename T>
+static inline void     clear(T& value)
+{
+       static const struct ZeroDummy : T {} zerodummy;
+       value=zerodummy;
+}
+
+//
+// Colliders
+//
+
+/* Tree collider       */ 
+struct btDbvtTreeCollider : btDbvt::ICollide
+{
+       btDbvtBroadphase*       pbp;
+       btDbvtProxy*            proxy;
+       btDbvtTreeCollider(btDbvtBroadphase* p) : pbp(p) {}
+       void    Process(const btDbvtNode* na,const btDbvtNode* nb)
+       {
+               if(na!=nb)
+               {
+                       btDbvtProxy*    pa=(btDbvtProxy*)na->data;
+                       btDbvtProxy*    pb=(btDbvtProxy*)nb->data;
+#if DBVT_BP_SORTPAIRS
+                       if(pa->m_uniqueId>pb->m_uniqueId) 
+                               btSwap(pa,pb);
+#endif
+                       pbp->m_paircache->addOverlappingPair(pa,pb);
+                       ++pbp->m_newpairs;
+               }
+       }
+       void    Process(const btDbvtNode* n)
+       {
+               Process(n,proxy->leaf);
+       }
+};
+
+//
+// btDbvtBroadphase
+//
+
+//
+btDbvtBroadphase::btDbvtBroadphase(btOverlappingPairCache* paircache)
+{
+       m_deferedcollide        =       false;
+       m_needcleanup           =       true;
+       m_releasepaircache      =       (paircache!=0)?false:true;
+       m_prediction            =       0;
+       m_stageCurrent          =       0;
+       m_fixedleft                     =       0;
+       m_fupdates                      =       1;
+       m_dupdates                      =       0;
+       m_cupdates                      =       10;
+       m_newpairs                      =       1;
+       m_updates_call          =       0;
+       m_updates_done          =       0;
+       m_updates_ratio         =       0;
+       m_paircache                     =       paircache? paircache    : new(btAlignedAlloc(sizeof(btHashedOverlappingPairCache),16)) btHashedOverlappingPairCache();
+       m_gid                           =       0;
+       m_pid                           =       0;
+       m_cid                           =       0;
+       for(int i=0;i<=STAGECOUNT;++i)
+       {
+               m_stageRoots[i]=0;
+       }
+#if DBVT_BP_PROFILE
+       clear(m_profiling);
+#endif
+}
+
+//
+btDbvtBroadphase::~btDbvtBroadphase()
+{
+       if(m_releasepaircache) 
+       {
+               m_paircache->~btOverlappingPairCache();
+               btAlignedFree(m_paircache);
+       }
+}
+
+//
+btBroadphaseProxy*                             btDbvtBroadphase::createProxy(  const btVector3& aabbMin,
+                                                                                                                         const btVector3& aabbMax,
+                                                                                                                         int /*shapeType*/,
+                                                                                                                         void* userPtr,
+                                                                                                                         short int collisionFilterGroup,
+                                                                                                                         short int collisionFilterMask,
+                                                                                                                         btDispatcher* /*dispatcher*/,
+                                                                                                                         void* /*multiSapProxy*/)
+{
+       btDbvtProxy*            proxy=new(btAlignedAlloc(sizeof(btDbvtProxy),16)) btDbvtProxy(  aabbMin,aabbMax,userPtr,
+               collisionFilterGroup,
+               collisionFilterMask);
+
+       btDbvtAabbMm aabb = btDbvtVolume::FromMM(aabbMin,aabbMax);
+
+       //bproxy->aabb                  =       btDbvtVolume::FromMM(aabbMin,aabbMax);
+       proxy->stage            =       m_stageCurrent;
+       proxy->m_uniqueId       =       ++m_gid;
+       proxy->leaf                     =       m_sets[0].insert(aabb,proxy);
+       listappend(proxy,m_stageRoots[m_stageCurrent]);
+       if(!m_deferedcollide)
+       {
+               btDbvtTreeCollider      collider(this);
+               collider.proxy=proxy;
+               m_sets[0].collideTV(m_sets[0].m_root,aabb,collider);
+               m_sets[1].collideTV(m_sets[1].m_root,aabb,collider);
+       }
+       return(proxy);
+}
+
+//
+void                                                   btDbvtBroadphase::destroyProxy( btBroadphaseProxy* absproxy,
+                                                                                                                          btDispatcher* dispatcher)
+{
+       btDbvtProxy*    proxy=(btDbvtProxy*)absproxy;
+       if(proxy->stage==STAGECOUNT)
+               m_sets[1].remove(proxy->leaf);
+       else
+               m_sets[0].remove(proxy->leaf);
+       listremove(proxy,m_stageRoots[proxy->stage]);
+       m_paircache->removeOverlappingPairsContainingProxy(proxy,dispatcher);
+       btAlignedFree(proxy);
+       m_needcleanup=true;
+}
+
+void   btDbvtBroadphase::getAabb(btBroadphaseProxy* absproxy,btVector3& aabbMin, btVector3& aabbMax ) const
+{
+       btDbvtProxy*                                            proxy=(btDbvtProxy*)absproxy;
+       aabbMin = proxy->m_aabbMin;
+       aabbMax = proxy->m_aabbMax;
+}
+
+struct BroadphaseRayTester : btDbvt::ICollide
+{
+       btBroadphaseRayCallback& m_rayCallback;
+       BroadphaseRayTester(btBroadphaseRayCallback& orgCallback)
+               :m_rayCallback(orgCallback)
+       {
+       }
+       void                                    Process(const btDbvtNode* leaf)
+       {
+               btDbvtProxy*    proxy=(btDbvtProxy*)leaf->data;
+               m_rayCallback.process(proxy);
+       }
+};     
+
+void   btDbvtBroadphase::rayTest(const btVector3& rayFrom,const btVector3& rayTo, btBroadphaseRayCallback& rayCallback,const btVector3& aabbMin,const btVector3& aabbMax)
+{
+       BroadphaseRayTester callback(rayCallback);
+
+       m_sets[0].rayTestInternal(      m_sets[0].m_root,
+               rayFrom,
+               rayTo,
+               rayCallback.m_rayDirectionInverse,
+               rayCallback.m_signs,
+               rayCallback.m_lambda_max,
+               aabbMin,
+               aabbMax,
+               callback);
+
+       m_sets[1].rayTestInternal(      m_sets[1].m_root,
+               rayFrom,
+               rayTo,
+               rayCallback.m_rayDirectionInverse,
+               rayCallback.m_signs,
+               rayCallback.m_lambda_max,
+               aabbMin,
+               aabbMax,
+               callback);
+
+}
+
+
+struct BroadphaseAabbTester : btDbvt::ICollide
+{
+       btBroadphaseAabbCallback& m_aabbCallback;
+       BroadphaseAabbTester(btBroadphaseAabbCallback& orgCallback)
+               :m_aabbCallback(orgCallback)
+       {
+       }
+       void                                    Process(const btDbvtNode* leaf)
+       {
+               btDbvtProxy*    proxy=(btDbvtProxy*)leaf->data;
+               m_aabbCallback.process(proxy);
+       }
+};     
+
+void   btDbvtBroadphase::aabbTest(const btVector3& aabbMin,const btVector3& aabbMax,btBroadphaseAabbCallback& aabbCallback)
+{
+       BroadphaseAabbTester callback(aabbCallback);
+
+       const ATTRIBUTE_ALIGNED16(btDbvtVolume) bounds=btDbvtVolume::FromMM(aabbMin,aabbMax);
+               //process all children, that overlap with  the given AABB bounds
+       m_sets[0].collideTV(m_sets[0].m_root,bounds,callback);
+       m_sets[1].collideTV(m_sets[1].m_root,bounds,callback);
+
+}
+
+
+
+//
+void                                                   btDbvtBroadphase::setAabb(              btBroadphaseProxy* absproxy,
+                                                                                                                 const btVector3& aabbMin,
+                                                                                                                 const btVector3& aabbMax,
+                                                                                                                 btDispatcher* /*dispatcher*/)
+{
+       btDbvtProxy*                                            proxy=(btDbvtProxy*)absproxy;
+       ATTRIBUTE_ALIGNED16(btDbvtVolume)       aabb=btDbvtVolume::FromMM(aabbMin,aabbMax);
+#if DBVT_BP_PREVENTFALSEUPDATE
+       if(NotEqual(aabb,proxy->leaf->volume))
+#endif
+       {
+               bool    docollide=false;
+               if(proxy->stage==STAGECOUNT)
+               {/* fixed -> dynamic set        */ 
+                       m_sets[1].remove(proxy->leaf);
+                       proxy->leaf=m_sets[0].insert(aabb,proxy);
+                       docollide=true;
+               }
+               else
+               {/* dynamic set                         */ 
+                       ++m_updates_call;
+                       if(Intersect(proxy->leaf->volume,aabb))
+                       {/* Moving                              */ 
+
+                               const btVector3 delta=aabbMin-proxy->m_aabbMin;
+                               btVector3               velocity(((proxy->m_aabbMax-proxy->m_aabbMin)/2)*m_prediction);
+                               if(delta[0]<0) velocity[0]=-velocity[0];
+                               if(delta[1]<0) velocity[1]=-velocity[1];
+                               if(delta[2]<0) velocity[2]=-velocity[2];
+                               if      (
+#ifdef DBVT_BP_MARGIN                          
+                                       m_sets[0].update(proxy->leaf,aabb,velocity,DBVT_BP_MARGIN)
+#else
+                                       m_sets[0].update(proxy->leaf,aabb,velocity)
+#endif
+                                       )
+                               {
+                                       ++m_updates_done;
+                                       docollide=true;
+                               }
+                       }
+                       else
+                       {/* Teleporting                 */ 
+                               m_sets[0].update(proxy->leaf,aabb);
+                               ++m_updates_done;
+                               docollide=true;
+                       }       
+               }
+               listremove(proxy,m_stageRoots[proxy->stage]);
+               proxy->m_aabbMin = aabbMin;
+               proxy->m_aabbMax = aabbMax;
+               proxy->stage    =       m_stageCurrent;
+               listappend(proxy,m_stageRoots[m_stageCurrent]);
+               if(docollide)
+               {
+                       m_needcleanup=true;
+                       if(!m_deferedcollide)
+                       {
+                               btDbvtTreeCollider      collider(this);
+                               m_sets[1].collideTTpersistentStack(m_sets[1].m_root,proxy->leaf,collider);
+                               m_sets[0].collideTTpersistentStack(m_sets[0].m_root,proxy->leaf,collider);
+                       }
+               }       
+       }
+}
+
+
+//
+void                                                   btDbvtBroadphase::setAabbForceUpdate(           btBroadphaseProxy* absproxy,
+                                                                                                                 const btVector3& aabbMin,
+                                                                                                                 const btVector3& aabbMax,
+                                                                                                                 btDispatcher* /*dispatcher*/)
+{
+       btDbvtProxy*                                            proxy=(btDbvtProxy*)absproxy;
+       ATTRIBUTE_ALIGNED16(btDbvtVolume)       aabb=btDbvtVolume::FromMM(aabbMin,aabbMax);
+       bool    docollide=false;
+       if(proxy->stage==STAGECOUNT)
+       {/* fixed -> dynamic set        */ 
+               m_sets[1].remove(proxy->leaf);
+               proxy->leaf=m_sets[0].insert(aabb,proxy);
+               docollide=true;
+       }
+       else
+       {/* dynamic set                         */ 
+               ++m_updates_call;
+               /* Teleporting                  */ 
+               m_sets[0].update(proxy->leaf,aabb);
+               ++m_updates_done;
+               docollide=true;
+       }
+       listremove(proxy,m_stageRoots[proxy->stage]);
+       proxy->m_aabbMin = aabbMin;
+       proxy->m_aabbMax = aabbMax;
+       proxy->stage    =       m_stageCurrent;
+       listappend(proxy,m_stageRoots[m_stageCurrent]);
+       if(docollide)
+       {
+               m_needcleanup=true;
+               if(!m_deferedcollide)
+               {
+                       btDbvtTreeCollider      collider(this);
+                       m_sets[1].collideTTpersistentStack(m_sets[1].m_root,proxy->leaf,collider);
+                       m_sets[0].collideTTpersistentStack(m_sets[0].m_root,proxy->leaf,collider);
+               }
+       }       
+}
+
+//
+void                                                   btDbvtBroadphase::calculateOverlappingPairs(btDispatcher* dispatcher)
+{
+       collide(dispatcher);
+#if DBVT_BP_PROFILE
+       if(0==(m_pid%DBVT_BP_PROFILING_RATE))
+       {       
+               printf("fixed(%u) dynamics(%u) pairs(%u)\r\n",m_sets[1].m_leaves,m_sets[0].m_leaves,m_paircache->getNumOverlappingPairs());
+               unsigned int    total=m_profiling.m_total;
+               if(total<=0) total=1;
+               printf("ddcollide: %u%% (%uus)\r\n",(50+m_profiling.m_ddcollide*100)/total,m_profiling.m_ddcollide/DBVT_BP_PROFILING_RATE);
+               printf("fdcollide: %u%% (%uus)\r\n",(50+m_profiling.m_fdcollide*100)/total,m_profiling.m_fdcollide/DBVT_BP_PROFILING_RATE);
+               printf("cleanup:   %u%% (%uus)\r\n",(50+m_profiling.m_cleanup*100)/total,m_profiling.m_cleanup/DBVT_BP_PROFILING_RATE);
+               printf("total:     %uus\r\n",total/DBVT_BP_PROFILING_RATE);
+               const unsigned long     sum=m_profiling.m_ddcollide+
+                       m_profiling.m_fdcollide+
+                       m_profiling.m_cleanup;
+               printf("leaked: %u%% (%uus)\r\n",100-((50+sum*100)/total),(total-sum)/DBVT_BP_PROFILING_RATE);
+               printf("job counts: %u%%\r\n",(m_profiling.m_jobcount*100)/((m_sets[0].m_leaves+m_sets[1].m_leaves)*DBVT_BP_PROFILING_RATE));
+               clear(m_profiling);
+               m_clock.reset();
+       }
+#endif
+
+       performDeferredRemoval(dispatcher);
+
+}
+
+void btDbvtBroadphase::performDeferredRemoval(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());
+
+               int 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 perform AABB check that is consistent with the broadphase
+                               btDbvtProxy*            pa=(btDbvtProxy*)pair.m_pProxy0;
+                               btDbvtProxy*            pb=(btDbvtProxy*)pair.m_pProxy1;
+                               bool hasOverlap = Intersect(pa->leaf->volume,pb->leaf->volume);
+
+                               if (hasOverlap)
+                               {
+                                       needsRemoval = false;
+                               } else
+                               {
+                                       needsRemoval = true;
+                               }
+                       } else
+                       {
+                               //remove duplicate
+                               needsRemoval = true;
+                               //should have no algorithm
+                               btAssert(!pair.m_algorithm);
+                       }
+                       
+                       if (needsRemoval)
+                       {
+                               m_paircache->cleanOverlappingPair(pair,dispatcher);
+
+                               pair.m_pProxy0 = 0;
+                               pair.m_pProxy1 = 0;
+                               invalidPair++;
+                       } 
+                       
+               }
+
+               //perform a sort, to sort 'invalid' pairs to the end
+               overlappingPairArray.quickSort(btBroadphasePairSortPredicate());
+               overlappingPairArray.resize(overlappingPairArray.size() - invalidPair);
+       }
+}
+
+//
+void                                                   btDbvtBroadphase::collide(btDispatcher* dispatcher)
+{
+       /*printf("---------------------------------------------------------\n");
+       printf("m_sets[0].m_leaves=%d\n",m_sets[0].m_leaves);
+       printf("m_sets[1].m_leaves=%d\n",m_sets[1].m_leaves);
+       printf("numPairs = %d\n",getOverlappingPairCache()->getNumOverlappingPairs());
+       {
+               int i;
+               for (i=0;i<getOverlappingPairCache()->getNumOverlappingPairs();i++)
+               {
+                       printf("pair[%d]=(%d,%d),",i,getOverlappingPairCache()->getOverlappingPairArray()[i].m_pProxy0->getUid(),
+                               getOverlappingPairCache()->getOverlappingPairArray()[i].m_pProxy1->getUid());
+               }
+               printf("\n");
+       }
+*/
+
+
+
+       SPC(m_profiling.m_total);
+       /* optimize                             */ 
+       m_sets[0].optimizeIncremental(1+(m_sets[0].m_leaves*m_dupdates)/100);
+       if(m_fixedleft)
+       {
+               const int count=1+(m_sets[1].m_leaves*m_fupdates)/100;
+               m_sets[1].optimizeIncremental(1+(m_sets[1].m_leaves*m_fupdates)/100);
+               m_fixedleft=btMax<int>(0,m_fixedleft-count);
+       }
+       /* dynamic -> fixed set */ 
+       m_stageCurrent=(m_stageCurrent+1)%STAGECOUNT;
+       btDbvtProxy*    current=m_stageRoots[m_stageCurrent];
+       if(current)
+       {
+               btDbvtTreeCollider      collider(this);
+               do      {
+                       btDbvtProxy*    next=current->links[1];
+                       listremove(current,m_stageRoots[current->stage]);
+                       listappend(current,m_stageRoots[STAGECOUNT]);
+#if DBVT_BP_ACCURATESLEEPING
+                       m_paircache->removeOverlappingPairsContainingProxy(current,dispatcher);
+                       collider.proxy=current;
+                       btDbvt::collideTV(m_sets[0].m_root,current->aabb,collider);
+                       btDbvt::collideTV(m_sets[1].m_root,current->aabb,collider);
+#endif
+                       m_sets[0].remove(current->leaf);
+                       ATTRIBUTE_ALIGNED16(btDbvtVolume)       curAabb=btDbvtVolume::FromMM(current->m_aabbMin,current->m_aabbMax);
+                       current->leaf   =       m_sets[1].insert(curAabb,current);
+                       current->stage  =       STAGECOUNT;     
+                       current                 =       next;
+               } while(current);
+               m_fixedleft=m_sets[1].m_leaves;
+               m_needcleanup=true;
+       }
+       /* collide dynamics             */ 
+       {
+               btDbvtTreeCollider      collider(this);
+               if(m_deferedcollide)
+               {
+                       SPC(m_profiling.m_fdcollide);
+                       m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[1].m_root,collider);
+               }
+               if(m_deferedcollide)
+               {
+                       SPC(m_profiling.m_ddcollide);
+                       m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[0].m_root,collider);
+               }
+       }
+       /* clean up                             */ 
+       if(m_needcleanup)
+       {
+               SPC(m_profiling.m_cleanup);
+               btBroadphasePairArray&  pairs=m_paircache->getOverlappingPairArray();
+               if(pairs.size()>0)
+               {
+
+                       int                     ni=btMin(pairs.size(),btMax<int>(m_newpairs,(pairs.size()*m_cupdates)/100));
+                       for(int i=0;i<ni;++i)
+                       {
+                               btBroadphasePair&       p=pairs[(m_cid+i)%pairs.size()];
+                               btDbvtProxy*            pa=(btDbvtProxy*)p.m_pProxy0;
+                               btDbvtProxy*            pb=(btDbvtProxy*)p.m_pProxy1;
+                               if(!Intersect(pa->leaf->volume,pb->leaf->volume))
+                               {
+#if DBVT_BP_SORTPAIRS
+                                       if(pa->m_uniqueId>pb->m_uniqueId) 
+                                               btSwap(pa,pb);
+#endif
+                                       m_paircache->removeOverlappingPair(pa,pb,dispatcher);
+                                       --ni;--i;
+                               }
+                       }
+                       if(pairs.size()>0) m_cid=(m_cid+ni)%pairs.size(); else m_cid=0;
+               }
+       }
+       ++m_pid;
+       m_newpairs=1;
+       m_needcleanup=false;
+       if(m_updates_call>0)
+       { m_updates_ratio=m_updates_done/(btScalar)m_updates_call; }
+       else
+       { m_updates_ratio=0; }
+       m_updates_done/=2;
+       m_updates_call/=2;
+}
+
+//
+void                                                   btDbvtBroadphase::optimize()
+{
+       m_sets[0].optimizeTopDown();
+       m_sets[1].optimizeTopDown();
+}
+
+//
+btOverlappingPairCache*                        btDbvtBroadphase::getOverlappingPairCache()
+{
+       return(m_paircache);
+}
+
+//
+const btOverlappingPairCache*  btDbvtBroadphase::getOverlappingPairCache() const
+{
+       return(m_paircache);
+}
+
+//
+void                                                   btDbvtBroadphase::getBroadphaseAabb(btVector3& aabbMin,btVector3& aabbMax) const
+{
+
+       ATTRIBUTE_ALIGNED16(btDbvtVolume)       bounds;
+
+       if(!m_sets[0].empty())
+               if(!m_sets[1].empty())  Merge(  m_sets[0].m_root->volume,
+                       m_sets[1].m_root->volume,bounds);
+               else
+                       bounds=m_sets[0].m_root->volume;
+       else if(!m_sets[1].empty())     bounds=m_sets[1].m_root->volume;
+       else
+               bounds=btDbvtVolume::FromCR(btVector3(0,0,0),0);
+       aabbMin=bounds.Mins();
+       aabbMax=bounds.Maxs();
+}
+
+void btDbvtBroadphase::resetPool(btDispatcher* dispatcher)
+{
+       
+       int totalObjects = m_sets[0].m_leaves + m_sets[1].m_leaves;
+       if (!totalObjects)
+       {
+               //reset internal dynamic tree data structures
+               m_sets[0].clear();
+          &