插入
求曼哈顿距离，插入时选节点用到了
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()));
}用a和b去扩展r，r的max等于a和b中更大的max，r的min等于a和b中更小的min
DBVT_INLINE void Merge(const btDbvtAabbMm& a, const btDbvtAabbMm& b, btDbvtAabbMm& r)
{
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];
}
}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就是被插得节点
root->childs[0]->volume, // Select就是比较leaf与两个孩子的曼哈顿距离，选小的那个
root->childs[1]->volume)];
} while (!root->isleaf());
}
btDbvtNode* prev = root->parent;
btDbvtNode* node = createnode(pdbvt,prev,leaf->volume,root->volume,0); // 将root和leaf合并成一个节点node
if(prev)
{
// node替换到被插入的位置上
prev->childs[indexof(root)] = node;
// 插入的root和被插入的leaf是node的两个孩子
node->childs[0] = root;root->parent=node;
node->childs[1] = leaf;leaf->parent=node;
do{ // 这个循环是更新整个aabb树
if(!prev->volume.Contain(node->volume)) // 因为插入的节点可能超过了他父节点的范围，
Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume); // Merge函数可能是用前两个volume去更新第三个
else
break;
node=prev;
} while(0!=(prev=node->parent)); // 自底向上的更新aabb树
}
else
{
node->childs[0] = root;root->parent=node; // 如果原来树只有一个节点，则新合成的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; // 删leaf，则爸爸也一起删
sibling->parent=prev; // 兄弟直接成爷爷的儿子，占据之前爸爸的位置
deletenode(pdbvt,parent);
while(prev) // 自底向上更新树，和插入类似
{
const btDbvtVolume pb=prev->volume; // 先保存一下爷爷的aabb
Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume); // 爷爷的新aabb
if(NotEqual(pb,prev->volume)) // 爷爷确实变了，则继续向上更新
{
prev=prev->parent;
} else break;
}
return(prev?prev:pdbvt->m_root);
}
else
{
pdbvt->m_root=sibling; // 如果没有爷爷
sibling->parent=0; // 爸爸也不要了，因为爸爸是leaf和兄弟Merge成的
deletenode(pdbvt,parent); // 只剩兄弟了爸爸也没意义
return(pdbvt->m_root);
}
}
}
更新
先删除在插入
