btDbvtBroadphase
bullet刚体的碰撞检测用的就是这个
更新aabb
更新aabb后就和树测试，collideTV，碰撞就放入overlapping pair
计算overlapping pairs
因为更新aabb的过程是顺序的，所以要删除某些实际上没有发生的碰撞。如果是更新全部aabb在测试，就没这个问题，但是比较慢？？
btAxisSweep3Internal
bullet柔体的碰撞检测使用_sweep and prune_算法（排序扫掠法），柔体的demo里用的都是这个。这个算法在aabb变化较小时，使用插入排序更新变动的aabb，最快可达到O(n+k)，n是aabb个数，k是碰撞的个数。最慢O(n^2),有说法使用快排等全部重新排序
算法原理
- 三个数组/链表保存三个坐标轴上每个aabb端点的坐标，并按照大小排序，每个端点要表明是区间的起点还是终点
- 对每个轴，遍历所有顶点，每遇到一个起点，就将起点放到一个active数组里，并且这个起点对应的区间和active数组里其他起点对应的区间是__重叠__的，因为这时已有的起点还没到终点
- 如果遇到一个终点，就将对应的起点从active数组里删除，因为遇到终点后，这个区间不可能再和后面的区间重叠了
- 三个轴上的区间都重叠的aabb相交
来张图看一下，遇到s4时，已有s3，所以I3和I4是重叠的；遇到e3时将s3删除了，后面再遇到s2，I2和I3就不会重合了；而e4在s2之后，所以I2和I4重叠
算法复杂度
如果aabb更新时变化不大，每个区间端点只和另一个端点比较，相当于插入排序的插入过程只比了一次，所以最快O(n)；最坏情况下，每个端点要和n个端点比较，复杂度O(n^2)。
bullet实现
Edge的m_pos保存端点的位置，最低一位标示是起始端点还是结束端点。BP_FP_INT_TYPE是模板参数，bullet提供两个精度的版本。
btAxisSweep3Internal中保存三个Edge的数组
class Edge
{
public:
BP_FP_INT_TYPE m_pos;
BP_FP_INT_TYPE m_handle;
BP_FP_INT_TYPE IsMax() const {return static_cast<BP_FP_INT_TYPE>(m_pos & 1);}
};Handle除了proxy的功能，还保存了proxy在3个坐标轴上端点数组中的索引，例如m_minEdges[0]就表示proxy管理的aabb的表较小的顶点的x值在数组中的索引。在btAxisSweep3Internal中有一个Handle的数组，初始就有两个Handle标示边界（哨兵）
class Handle : public btBroadphaseProxy
{
BP_FP_INT_TYPE m_minEdges[3], m_maxEdges[3];
BP_FP_INT_TYPE m_uniqueId;
btBroadphaseProxy* m_dbvtProxy;
btBroadphaseProxy.m_clientObject
};更新aabb
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)
{
Handle* pHandle = getHandle(handle);
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);
}
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);
}
// 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--;
}
}添加和删除aabb类似
