19 #ifndef BT_AXIS_SWEEP_3_H 20 #define BT_AXIS_SWEEP_3_H 30 #define USE_OVERLAP_TEST_ON_REMOVES 1 35 template <
typename BP_FP_INT_TYPE>
53 BP_FP_INT_TYPE
IsMax()
const {
return static_cast<BP_FP_INT_TYPE
>(m_pos & 1);}
63 BP_FP_INT_TYPE m_minEdges[3], m_maxEdges[3];
108 bool testOverlap2D(
const Handle* pHandleA,
const Handle* pHandleB,
int axis0,
int axis1);
110 #ifdef DEBUG_BROADPHASE 111 void debugPrintAxis(
int axis,
bool checkCardinality=
true);
112 #endif //DEBUG_BROADPHASE 137 BP_FP_INT_TYPE
addHandle(
const btVector3& aabbMin,
const btVector3& aabbMax,
void* pOwner,
short int collisionFilterGroup,
short int collisionFilterMask,
btDispatcher* dispatcher,
void* multiSapProxy);
173 m_userPairCallback = pairCallback;
205 #ifdef DEBUG_BROADPHASE 208 template <
typename BP_FP_INT_TYPE>
212 printf(
"SAP Axis %d, numEdges=%d\n",axis,numEdges);
215 for (i=0;i<numEdges+1;i++)
218 Handle* pHandlePrev =
getHandle(pEdge->m_handle);
219 int handleIndex = pEdge->IsMax()? pHandlePrev->m_maxEdges[axis] : pHandlePrev->m_minEdges[axis];
221 beginOrEnd=pEdge->IsMax()?
'E':
'B';
222 printf(
" [%c,h=%d,p=%x,i=%d]\n",beginOrEnd,pEdge->m_handle,pEdge->m_pos,handleIndex);
225 if (checkCardinality)
228 #endif //DEBUG_BROADPHASE 230 template <
typename BP_FP_INT_TYPE>
234 BP_FP_INT_TYPE handleId =
addHandle(aabbMin,aabbMax, userPtr,collisionFilterGroup,collisionFilterMask,dispatcher,multiSapProxy);
241 handle->m_dbvtProxy = rayProxy;
248 template <
typename BP_FP_INT_TYPE>
251 Handle* handle =
static_cast<Handle*
>(proxy);
254 removeHandle(static_cast<BP_FP_INT_TYPE>(handle->m_uniqueId), dispatcher);
257 template <
typename BP_FP_INT_TYPE>
260 Handle* handle =
static_cast<Handle*
>(proxy);
261 handle->m_aabbMin = aabbMin;
262 handle->m_aabbMax = aabbMax;
263 updateHandle(static_cast<BP_FP_INT_TYPE>(handle->m_uniqueId), aabbMin, aabbMax,dispatcher);
269 template <
typename BP_FP_INT_TYPE>
278 BP_FP_INT_TYPE axis = 0;
290 template <
typename BP_FP_INT_TYPE>
299 BP_FP_INT_TYPE axis = 0;
317 template <
typename BP_FP_INT_TYPE>
320 Handle* pHandle =
static_cast<Handle*
>(proxy);
321 aabbMin = pHandle->m_aabbMin;
322 aabbMax = pHandle->m_aabbMax;
326 template <
typename BP_FP_INT_TYPE>
329 Handle* pHandle =
static_cast<Handle*
>(proxy);
331 unsigned short vecInMin[3];
332 unsigned short vecInMax[3];
351 template <
typename BP_FP_INT_TYPE>
361 BP_FP_INT_TYPE maxHandles =
static_cast<BP_FP_INT_TYPE
>(userMaxHandles+1);
370 if (!disableRaycastAccelerator)
399 m_pHandles[i].SetNextFree(static_cast<BP_FP_INT_TYPE>(i + 1));
405 for (
int i = 0; i < 3; i++)
417 for (
int axis = 0; axis < 3; axis++)
426 #ifdef DEBUG_BROADPHASE 427 debugPrintAxis(axis);
428 #endif //DEBUG_BROADPHASE 434 template <
typename BP_FP_INT_TYPE>
445 for (
int i = 2; i >= 0; i--)
458 template <
typename BP_FP_INT_TYPE>
461 #ifdef OLD_CLAMPING_METHOD 476 #endif //OLD_CLAMPING_METHOD 480 template <
typename BP_FP_INT_TYPE>
492 template <
typename BP_FP_INT_TYPE>
504 template <
typename BP_FP_INT_TYPE>
508 BP_FP_INT_TYPE min[3], max[3];
518 pHandle->m_uniqueId =
static_cast<int>(handle);
520 pHandle->m_clientObject = pOwner;
521 pHandle->m_collisionFilterGroup = collisionFilterGroup;
522 pHandle->m_collisionFilterMask = collisionFilterMask;
523 pHandle->m_multiSapParentProxy = multiSapProxy;
526 BP_FP_INT_TYPE limit =
static_cast<BP_FP_INT_TYPE
>(
m_numHandles * 2);
530 for (BP_FP_INT_TYPE axis = 0; axis < 3; axis++)
543 pHandle->m_minEdges[axis] =
static_cast<BP_FP_INT_TYPE
>(limit - 1);
544 pHandle->m_maxEdges[axis] = limit;
548 sortMinDown(0, pHandle->m_minEdges[0], dispatcher,
false);
549 sortMaxDown(0, pHandle->m_maxEdges[0], dispatcher,
false);
550 sortMinDown(1, pHandle->m_minEdges[1], dispatcher,
false);
551 sortMaxDown(1, pHandle->m_maxEdges[1], dispatcher,
false);
552 sortMinDown(2, pHandle->m_minEdges[2], dispatcher,
true);
553 sortMaxDown(2, pHandle->m_maxEdges[2], dispatcher,
true);
560 template <
typename BP_FP_INT_TYPE>
579 for (axis = 0;axis<3;axis++)
585 for ( axis = 0; axis < 3; axis++)
588 BP_FP_INT_TYPE max = pHandle->m_maxEdges[axis];
594 BP_FP_INT_TYPE i = pHandle->m_minEdges[axis];
600 pEdges[limit-1].m_handle = 0;
603 #ifdef DEBUG_BROADPHASE 604 debugPrintAxis(axis,
false);
605 #endif //DEBUG_BROADPHASE 617 template <
typename BP_FP_INT_TYPE>
625 m_pHandles[i].SetNextFree(static_cast<BP_FP_INT_TYPE>(i + 1));
635 template <
typename BP_FP_INT_TYPE>
659 for (i=0;i<overlappingPairArray.
size();i++)
664 bool isDuplicate = (pair == previousPair);
668 bool needsRemoval =
false;
677 needsRemoval =
false;
705 #define CLEAN_INVALID_PAIRS 1 706 #ifdef CLEAN_INVALID_PAIRS 713 #endif//CLEAN_INVALID_PAIRS 721 template <
typename BP_FP_INT_TYPE>
724 const Handle* pHandleA =
static_cast<Handle*
>(proxy0);
725 const Handle* pHandleB =
static_cast<Handle*
>(proxy1);
729 for (
int axis = 0; axis < 3; axis++)
731 if (pHandleA->m_maxEdges[axis] < pHandleB->m_minEdges[axis] ||
732 pHandleB->m_maxEdges[axis] < pHandleA->m_minEdges[axis])
740 template <
typename BP_FP_INT_TYPE>
745 if (pHandleA->m_maxEdges[axis0] < pHandleB->m_minEdges[axis0] ||
746 pHandleB->m_maxEdges[axis0] < pHandleA->m_minEdges[axis0] ||
747 pHandleA->m_maxEdges[axis1] < pHandleB->m_minEdges[axis1] ||
748 pHandleB->m_maxEdges[axis1] < pHandleA->m_minEdges[axis1])
755 template <
typename BP_FP_INT_TYPE>
764 BP_FP_INT_TYPE min[3], max[3];
769 for (
int axis = 0; axis < 3; axis++)
771 BP_FP_INT_TYPE emin = pHandle->m_minEdges[axis];
772 BP_FP_INT_TYPE emax = pHandle->m_maxEdges[axis];
794 #ifdef DEBUG_BROADPHASE 795 debugPrintAxis(axis);
796 #endif //DEBUG_BROADPHASE 806 template <
typename BP_FP_INT_TYPE>
810 Edge* pEdge =
m_pEdges[axis] + edge;
811 Edge* pPrev = pEdge - 1;
812 Handle* pHandleEdge =
getHandle(pEdge->m_handle);
814 while (pEdge->m_pos < pPrev->m_pos)
816 Handle* pHandlePrev =
getHandle(pPrev->m_handle);
821 const int axis1 = (1 << axis) & 3;
822 const int axis2 = (1 << axis1) & 3;
823 if (updateOverlaps &&
testOverlap2D(pHandleEdge, pHandlePrev,axis1,axis2))
834 pHandlePrev->m_maxEdges[axis]++;
837 pHandlePrev->m_minEdges[axis]++;
839 pHandleEdge->m_minEdges[axis]--;
851 #ifdef DEBUG_BROADPHASE 852 debugPrintAxis(axis);
853 #endif //DEBUG_BROADPHASE 858 template <
typename BP_FP_INT_TYPE>
861 Edge* pEdge =
m_pEdges[axis] + edge;
862 Edge* pNext = pEdge + 1;
863 Handle* pHandleEdge =
getHandle(pEdge->m_handle);
865 while (pNext->m_handle && (pEdge->m_pos >= pNext->m_pos))
867 Handle* pHandleNext =
getHandle(pNext->m_handle);
871 Handle* handle0 =
getHandle(pEdge->m_handle);
872 Handle* handle1 =
getHandle(pNext->m_handle);
873 const int axis1 = (1 << axis) & 3;
874 const int axis2 = (1 << axis1) & 3;
880 #endif //USE_OVERLAP_TEST_ON_REMOVES 893 pHandleNext->m_maxEdges[axis]--;
896 pHandleNext->m_minEdges[axis]--;
898 pHandleEdge->m_minEdges[axis]++;
914 template <
typename BP_FP_INT_TYPE>
918 Edge* pEdge =
m_pEdges[axis] + edge;
919 Edge* pPrev = pEdge - 1;
920 Handle* pHandleEdge =
getHandle(pEdge->m_handle);
922 while (pEdge->m_pos < pPrev->m_pos)
924 Handle* pHandlePrev =
getHandle(pPrev->m_handle);
929 Handle* handle0 =
getHandle(pEdge->m_handle);
930 Handle* handle1 =
getHandle(pPrev->m_handle);
931 const int axis1 = (1 << axis) & 3;
932 const int axis2 = (1 << axis1) & 3;
937 #endif //USE_OVERLAP_TEST_ON_REMOVES 952 pHandlePrev->m_minEdges[axis]++;;
955 pHandlePrev->m_maxEdges[axis]++;
957 pHandleEdge->m_maxEdges[axis]--;
970 #ifdef DEBUG_BROADPHASE 971 debugPrintAxis(axis);
972 #endif //DEBUG_BROADPHASE 977 template <
typename BP_FP_INT_TYPE>
980 Edge* pEdge =
m_pEdges[axis] + edge;
981 Edge* pNext = pEdge + 1;
982 Handle* pHandleEdge =
getHandle(pEdge->m_handle);
984 while (pNext->m_handle && (pEdge->m_pos >= pNext->m_pos))
986 Handle* pHandleNext =
getHandle(pNext->m_handle);
988 const int axis1 = (1 << axis) & 3;
989 const int axis2 = (1 << axis1) & 3;
994 if (updateOverlaps &&
testOverlap2D(pHandleEdge, pHandleNext,axis1,axis2))
996 Handle* handle0 =
getHandle(pEdge->m_handle);
997 Handle* handle1 =
getHandle(pNext->m_handle);
1004 pHandleNext->m_minEdges[axis]--;
1007 pHandleNext->m_maxEdges[axis]--;
1009 pHandleEdge->m_maxEdges[axis]++;
virtual void aabbTest(const btVector3 &aabbMin, const btVector3 &aabbMax, btBroadphaseAabbCallback &callback)
virtual void resetPool(btDispatcher *dispatcher)
reset broadphase internal structures, to ensure determinism/reproducability
void quantize(BP_FP_INT_TYPE *out, const btVector3 &point, int isMax) 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))
btBroadphaseProxy * createProxy(const btVector3 &aabbMin, const btVector3 &aabbMax, int shapeType, void *userPtr, short int collisionFilterGroup, short int collisionFilterMask, btDispatcher *dispatcher, void *multiSapProxy)
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 cleanOverlappingPair(btBroadphasePair &pair, btDispatcher *dispatcher)=0
void setValue(const btScalar &_x, const btScalar &_y, const btScalar &_z)
The btAxisSweep3 is an efficient implementation of the 3d axis sweep and prune broadphase.
btBroadphaseProxy * m_dbvtProxy
virtual bool hasDeferredRemoval()=0
btNullPairCache skips add/removal of overlapping pairs. Userful for benchmarking and unit testing...
void sortMaxUp(int axis, BP_FP_INT_TYPE edge, btDispatcher *dispatcher, bool updateOverlaps)
#define USE_OVERLAP_TEST_ON_REMOVES
virtual void printStats()
virtual void getAabb(btBroadphaseProxy *proxy, btVector3 &aabbMin, btVector3 &aabbMax) const
void freeHandle(BP_FP_INT_TYPE handle)
BP_FP_INT_TYPE IsMax() const
#define SIMD_FORCE_INLINE
const btScalar & getY() const
Return the y value.
The btDbvtBroadphase implements a broadphase using two dynamic AABB bounding volume hierarchies/trees...
BP_FP_INT_TYPE m_handleSentinel
void processAllOverlappingPairs(btOverlapCallback *callback)
BP_FP_INT_TYPE m_firstFreeHandle
bool TestAabbAgainstAabb2(const btVector3 &aabbMin1, const btVector3 &aabbMax1, const btVector3 &aabbMin2, const btVector3 &aabbMax2)
conservative test for overlap between two aabbs
void removeHandle(BP_FP_INT_TYPE handle, btDispatcher *dispatcher)
BP_FP_INT_TYPE m_minEdges[3]
BP_FP_INT_TYPE addHandle(const btVector3 &aabbMin, const btVector3 &aabbMax, void *pOwner, short int collisionFilterGroup, short int collisionFilterMask, btDispatcher *dispatcher, void *multiSapProxy)
BP_FP_INT_TYPE GetNextFree() const
The btOverlappingPairCache provides an interface for overlapping pair management (add, remove, storage), used by the btBroadphaseInterface broadphases.
const btScalar & getZ() const
Return the z value.
bool testAabbOverlap(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)
BP_FP_INT_TYPE getNumHandles() const
virtual void setAabb(btBroadphaseProxy *proxy, const btVector3 &aabbMin, const btVector3 &aabbMax, btDispatcher *dispatcher)
BP_FP_INT_TYPE m_maxHandles
virtual btBroadphasePairArray & getOverlappingPairArray()=0
virtual void calculateOverlappingPairs(btDispatcher *dispatcher)
calculateOverlappingPairs is optional: incremental algorithms (sweep and prune) might do it during th...
virtual void destroyProxy(btBroadphaseProxy *proxy, btDispatcher *dispatcher)
virtual void destroyProxy(btBroadphaseProxy *proxy, btDispatcher *dispatcher)
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))
void updateHandle(BP_FP_INT_TYPE handle, const btVector3 &aabbMin, const btVector3 &aabbMax, btDispatcher *dispatcher)
#define btAlignedFree(ptr)
BP_FP_INT_TYPE m_maxEdges[3]
void sortMinUp(int axis, BP_FP_INT_TYPE edge, btDispatcher *dispatcher, bool updateOverlaps)
virtual void setAabb(btBroadphaseProxy *proxy, const btVector3 &aabbMin, const btVector3 &aabbMax, btDispatcher *dispatcher)
void setOverlappingPairUserCallback(btOverlappingPairCallback *pairCallback)
bool testOverlap2D(const Handle *pHandleA, const Handle *pHandleB, int axis0, int axis1)
BP_FP_INT_TYPE m_bpHandleMask
virtual void removeOverlappingPairsContainingProxy(btBroadphaseProxy *proxy0, btDispatcher *dispatcher)=0
The btBroadphaseInterface class provides an interface to detect aabb-overlapping object pairs...
const btOverlappingPairCache * getOverlappingPairCache() const
virtual ~btOverlappingPairCache()
Handle * getHandle(BP_FP_INT_TYPE index) const
The btBroadphaseProxy is the main class that can be used with the Bullet broadphases.
btBroadphaseProxy * m_pProxy1
void sortMinDown(int axis, BP_FP_INT_TYPE edge, btDispatcher *dispatcher, bool updateOverlaps)
btCollisionAlgorithm * m_algorithm
btOverlappingPairCache * m_nullPairCache
btVector3 can be used to represent 3D points and vectors.
virtual bool process(const btBroadphaseProxy *proxy)=0
int size() const
return the number of elements in the array
btOverlappingPairCache * m_pairCache
btBroadphaseProxy * m_pProxy0
const btOverlappingPairCallback * getOverlappingPairUserCallback() const
btDbvtBroadphase * m_raycastAccelerator
additional dynamic aabb structure, used to accelerate ray cast queries.
virtual btBroadphasePair * addOverlappingPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)=0
BP_FP_INT_TYPE allocHandle()
void sortMaxDown(int axis, BP_FP_INT_TYPE edge, btDispatcher *dispatcher, bool updateOverlaps)
void resize(int newsize, const T &fillData=T())
The internal templace class btAxisSweep3Internal implements the sweep and prune broadphase.
The bt32BitAxisSweep3 allows higher precision quantization and more objects compared to the btAxisSwe...
btOverlappingPairCache * getOverlappingPairCache()
void SetNextFree(BP_FP_INT_TYPE next)
#define btAlignedAlloc(size, alignment)
BP_FP_INT_TYPE m_numHandles
void setMax(const btVector3 &other)
Set each element to the max of the current values and the values of another btVector3.
virtual ~btAxisSweep3Internal()
void unQuantize(btBroadphaseProxy *proxy, btVector3 &aabbMin, btVector3 &aabbMax) const
unQuantize should be conservative: aabbMin/aabbMax should be larger then 'getAabb' result ...
The btDispatcher interface class can be used in combination with broadphase to dispatch calculations ...
BT_DECLARE_ALIGNED_ALLOCATOR()
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 void getBroadphaseAabb(btVector3 &aabbMin, btVector3 &aabbMax) const
getAabb returns the axis aligned bounding box in the 'global' coordinate frame will add some transfor...
Hash-space based Pair Cache, thanks to Erin Catto, Box2D, http://www.box2d.org, and Pierre Terdiman...
const btScalar & getX() const
Return the x value.
The btOverlappingPairCallback class is an additional optional broadphase user callback for adding/rem...
void setMin(const btVector3 &other)
Set each element to the min of the current values and the values of another btVector3.
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
void quickSort(const L &CompareFunc)
virtual void * removeOverlappingPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1, btDispatcher *dispatcher)=0
virtual void aabbTest(const btVector3 &aabbMin, const btVector3 &aabbMax, btBroadphaseAabbCallback &callback)
btOverlappingPairCallback * m_userPairCallback
btOverlappingPairCallback is an additional optional user callback for adding/removing overlapping pai...
The btBroadphasePair class contains a pair of aabb-overlapping objects.