I'm analysing the optimizeIncremental algorithm in btDbvt.h .
So I have placed some commentaries in the code:
Code: Select all
void btDbvt::optimizeIncremental(int passes)
{
/* passes is default set to 1+(m_sets[0].m_leaves*m_dupdates)/100),
* where m_dupdates is the percent of dynamic updates per frame.
* Default m_dupdates is 0, so default passes is 1.
*/
if(passes<0) passes=m_leaves;
if(m_root&&(passes>0))
{
do {
btDbvtNode* node=m_root;
unsigned bit=0;
while(node->isinternal())
{
node=sort(node,m_root)->childs[(m_opath>>bit)&1];
/* A) sort compare the volume between the node n and the node's parent p.
*
* 1) : If the p has a bigger volume than n, n is placed in the tree
* just below p and then update child, sibling and parent
* relationsships for p and n.
* Then p is returned.
*
* 2) : If p's parent is NULL, then p is the root.
*
* 3) : If n is not bigger than p, then n is returned and no inserting
* is performed.
*
*
* B) According to the bit pattern, one of the child to the returned node
* is picked and is set to n. Then the sequence starts over.
* This is done while n is a internal node.
*
* C) The bit pattern is simple but not randomized: m_opath is initialized
* to zero and raised by one when the traversal has reach the bottom of
* the tree.
* In each loop where the sort traverse down the tree the bit is raised
* by one. To make sure the mask for the descend rule is inside the
* range of m_opath: (sizeof(unsigned)*8-1) = 31 (if unsigned is 4 bit).
* Example of bit pattern when:
* m_opath = 0 bit = 0,0,0,0,0,0, ...
* m_opath = 1 bit = 1,0,0,0,0,0, ...
* m_opath = 2 bit = 0,1,0,0,0,0, ...
* m_opath = 3 bit = 1,1,0,0,0,0, ...
* m_opath = 4 bit = 0,0,1,0,0,0, ...
* m_opath = 5 bit = 1,0,1,0,0,0, ...
* m_opath = 6 bit = 0,1,1,0,0,0, ...
* m_opath = 7 bit = 1,1,1,0,0,0, ...
* m_opath = 8 bit = 0,0,0,1,0,0, ...
*/
bit=(bit+1)&(sizeof(unsigned)*8-1);
}
/* Final, the node n is a leaf and it is updated by remove it from tree and
* update its parents volume through the tree to the root.
* Then n is inserted again from the root and traverses down the tree through nodes
* where its volume fits in until it ends as a leaf.
*/
update(node);
++m_opath;
} while(--passes);
}
}
for instance I'm not quite sure I understand the insertleaf() function which is called through the update() function.
As I see it, it finds a place in the tree to put in the leaf. The search is performed by a while loop where a Select() function
is called, but what this function does is not for sure. But it seems Select() calculate the volume for the leaf and a node's two children, and return the index for which volume that fits the leaf best.
If anyone can give me any hint and/or tell me if the description is right, I will be glad
/Jesper