BtDbvt dynamic aabb tree

From Physics Simulation Wiki

Dynamic AABB tree (btDbvt)

The btDbvt dynamic AABB tree is a fast dynamic general purpose aabb tree. It is currently used in Bullet to accelerate collision detection between soft bodies. Also, the btDbvtBroadphase uses two btDbvt trees: one for static/non-moving and one for dynamic/moving objects. The btDbvt has very fast insertion, removal and update of nodes, and it exploits temporal coherence.

btDbvt dynamic AABB tree supports the following queries:

• enumerate leafs from a root, 'enumLeafs'.
• Tree/tree collision, 'collideTT'.
• Tree/Volume collision, 'collideTV'.
• Ray cast, 'collideRAY'
• KDOP culling, 'collideKDOP'
• Occlusion parse, (KDOP + front to back + call to ::Descent for each nodes), 'collideOCL'.
• Tree/user collision, 'collideTU'

Some information about the btDbvt inner workings:

Insert:
    
    let 'L' be the leaf to insert
    let 'R' the current root of insertion
    while 'R' is an internal node
        if cost(L,R->left) < cost(L,R->right) [!]
            'R'	=	R->left
        else
            'R'	=	R->right
        end
    end	
    create new internal node 'N'
    'N'->left	=	'L'
    'N'->right	=	'R'
    return 'L'
    
    Notes:
    [!]-	Using Manhattan distance (|x|+|y|+...) between nodes as a cost function greatly speed up insertion.
            Doesn't take in account volume,	but work well in practice even for scales heterogenous setup.
        
Remove:

    let SIDE(n) be a function returning left or right depending on which side 'n' is.
    let 'L' be the leaf to remove
    let 'S' be 'L' sibling node
    let 'P' be 'L' parent node
    let 'Q' be 'P' parent node
    'Q'->SIDE(P)	=	'S'
    'S'->parent		=	'Q'
    delete node 'P'
    while 'Q' != null
        'V0'		=	Q->volume
        'Q'->volume	=	union of 'Q'->left and 'Q'->right
        if 'Q'->volume == 'V0' [!]
            return 'Q'
        else
            'S'	=	'Q'
            'Q'	=	'Q'->parent
        end
    end
    return 'Q'
    
    Notes:	
    [!]-	We stop as soon as 'Q'->volume == 'V0', compare for strict equality (memcmp like)
    
Update (with velocity and margin):
    let 'L' be the leaf to update
    let 'V' be the new volume of 'L'
    let 'D' be the the velocity of 'L' [*]
    let 'M' be the margin of 'L'
    if 'L'->volume containt 'V' [!]
        return
    else
        expand 'V' with margin 'M'		[!!]
        expand 'V' with velocity 'D'	[!!!]
        'R'			=	Remove('L')
        'L'->volume	=	'V'
        Insert('L') at 'R'				[!!!!]
    end
    
    Notes:
    [*]-	'D' can be implicitly calculated as follow: 'D' = ('L'->center - 'V'->center) * predicted frames.
    [!]-	We do nothing if the new volume 'V' is contained in the old one.
    [!!]-	Using a non-zero margin handle the case of jitter or small random motions.
    [!!!]-	Using a non-zero velocity handle the case of linear motion over few frames.
    [!!!!]-	We re-insert 'L' at 'R' so we do not have to walk all the tree from the root.