Bullet 引擎 详解 DBVT 分析

DBVT 在bullet 引擎中是很基础且重要的一个数据结构，本质上是一个可以动态更新的AABB树。在bullet的远距阶段是很高效的碰撞检测数据结构（比较OOB，K- DOP）。是组成dbvtbroadphase的重要成员。

首先看看树中节点的定义

struct btDbvtNode{ btDbvtVolume volume; // point to the bounding volume btDbvtNode* parent; // point to parent node DBVT_INLINE bool isleaf() const { return(childs[1]==0); } DBVT_INLINE bool isinternal() const { return(!isleaf()); } union { btDbvtNode* childs[2]; // point to child nodes if node is internal type void* data; // point to Dbvtproxy object if node is leaf node int dataAsInt; // padding ? };};

很明显这是一个典型的二叉树节点，同时当node是内部节点时将指向2个子结点，node是叶子节点时，将指向用户定义数据（具体见后续分析）

 

 

---

 

接下来是DBVT 的部分基础定义

struct btDbvt{ // Fields btDbvtNode* m_root; // root node of the tree btDbvtNode* m_free; // node buffer last one deleted int m_lkhd; // number of look ahead int m_leaves; // number of nodes unsigned m_opath; // bitmap, mean the path to the node }

这里的look ahead 基本没有在代码中用到。 m_opath将在优化中使用，主要用于纪录通往特定节点的路径。

 

---

 

创建节点比较直接，唯一值得注意的就是利用到了m_free 这个最后被从树中删除的节点(节点分配内存未释放)

如果m_free仍未被释放就重复利用，节省一次malloc调用。

 

static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt, btDbvtNode* parent, void* data){ btDbvtNode* node; //if the node pool is avaliable if(pdbvt->m_free) { node=pdbvt->m_free;pdbvt->m_free=0; } // if yes, use it and reset the pointer else { node=new(btAlignedAlloc(sizeof(btDbvtNode),16)) btDbvtNode(); } // otherwise alloc memory to node node->parent = parent; // set the parent node->data = data; // set the data node->childs[1] = 0; // set the right child pointer as null return(node);}

---

 

插入节点到树中较为复杂，主要算法是插入到树中距离被插入节点距离(曼哈顿距离)最近的节点，并且合成新的父节点，并且向上传导包围体的变化(复习一下AABB)。

---

 

删除节点和插入节点比较类似，主要算法是用兄弟节点替换父节点，同时向上传导产生的包围体变化。

 

---

节点排序，检查父节点和字节点对象的地址，如果父节点地址高于子节点，则交换父子节点，

 

//make sure the parent's address is smaller than child node static DBVT_INLINE btDbvtNode* sort(btDbvtNode* n,btDbvtNode*& r) // r is reference { btDbvtNode* p=n->parent; btAssert(n->isinternal()); if(p>n) //all idea is swap the postion betwwen p and n . if the n address is smaller than p address. { const int i=indexof(n); const int j=1-i; btDbvtNode* s=p->childs[j]; // get the sibling node btDbvtNode* q=p->parent; // get the grand father node btAssert(n==p->childs[i]); // confirm again! if(q) q->childs[indexof(p)]=n; else r=n; s->parent=n; // reset the sibling node's parent to node p->parent=n; // reset the parent's parent to node n->parent=q; // reset the node's parent to grand father p->childs[0]=n->childs[0]; //reset parent node' child node to node's child p->childs[1]=n->childs[1]; //reset parent node' child node to node's child n->childs[0]->parent=p; //reset node's child node's parent node to parent n->childs[1]->parent=p; //reset node's child node's parent node to parent n->childs[i]=p; //reset node's child to parent node n->childs[j]=s; //reset node's child to parent node btSwap(p->volume,n->volume); //swap the volume return(p); //make sure return the greater one } return(n); //make sure return the greater one }