（转）Bullet 引擎 详解 DBVT 分析

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

首先看看树中节点的定义

view plaincopy to clipboardprint?
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 ?   
    };  
}; 
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 的部分基础定义

view plaincopy to clipboardprint?
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   
} 
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调用。

view plaincopy to clipboardprint?
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);  
} 
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)。

--------------------------------------------------------------------------------

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

--------------------------------------------------------------------------------

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

view plaincopy to clipboardprint?
//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   
} 

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/superwiles/archive/2010/02/18/5310655.aspx