lib/Oimo.js
function(leaf){
        if(this.root==null){
            this.root=leaf;
            return;
        }
        var lb=leaf.aabb;
        var sibling=this.root;
        var oldArea;
        var newArea;
        while(sibling.proxy==null){ // descend the node to search the best pair
            var c1=sibling.child1;
            var c2=sibling.child2;
            var b=sibling.aabb;
            var c1b=c1.aabb;
            var c2b=c2.aabb;
            oldArea=b.surfaceArea();
            this.aabb.combine(lb,b);
            newArea=this.aabb.surfaceArea();
            var creatingCost=newArea*2;
            var incrementalCost=(newArea-oldArea)*2; // cost of creating a new pair with the node
            var discendingCost1=incrementalCost;
            this.aabb.combine(lb,c1b);
            if(c1.proxy!=null){
                // leaf cost = area(combined aabb)
                discendingCost1+=this.aabb.surfaceArea();
            }else{
                // node cost = area(combined aabb) - area(old aabb)
                discendingCost1+=this.aabb.surfaceArea()-c1b.surfaceArea();
            }
            var discendingCost2=incrementalCost;
            this.aabb.combine(lb,c2b);
            if(c2.proxy!=null){
                // leaf cost = area(combined aabb)
                discendingCost2+=this.aabb.surfaceArea();
            }else{
                // node cost = area(combined aabb) - area(old aabb)
                discendingCost2+=this.aabb.surfaceArea()-c2b.surfaceArea();
            }
            if(discendingCost1<discendingCost2){
                if(creatingCost<discendingCost1){
                    break;// stop descending
                }else{
                    sibling=c1;// descend into first child
                }
            }else{
                if(creatingCost<discendingCost2){
                    break;// stop descending
                }else{
                    sibling=c2;// descend into second child
                }
            }
        }
        var oldParent=sibling.parent;
        var newParent;
        if(this.numFreeNodes>0){
            newParent=this.freeNodes[--this.numFreeNodes];
        }else{
            newParent=new OIMO.DBVTNode();
        }
        newParent.parent=oldParent;
        newParent.child1=leaf;
        newParent.child2=sibling;
        newParent.aabb.combine(leaf.aabb,sibling.aabb);
        newParent.height=sibling.height+1;
        sibling.parent=newParent;
        leaf.parent=newParent;
        if(sibling==this.root){
            // replace root
            this.root=newParent;
        }else{
            // replace child
            if(oldParent.child1==sibling){
                oldParent.child1=newParent;
            }else{
                oldParent.child2=newParent;
            }
        }
        // update whole tree
        do{
            newParent=this.balance(newParent);
            this.fix(newParent);
            newParent=newParent.parent;
        }while(newParent!=null);
    }
function(leaf){
        if(this.root==null){
            this.root=leaf;
            return;
        }
        var lb=leaf.aabb;
        var sibling=this.root;
        var oldArea;
        var newArea;
        while(sibling.proxy==null){ // descend the node to search the best pair
            var c1=sibling.child1;
            var c2=sibling.child2;
            var b=sibling.aabb;
            var c1b=c1.aabb;
            var c2b=c2.aabb;
            oldArea=b.surfaceArea();
            this.aabb.combine(lb,b);
            newArea=this.aabb.surfaceArea();
            var creatingCost=newArea*2;
            var incrementalCost=(newArea-oldArea)*2; // cost of creating a new pair with the node
            var discendingCost1=incrementalCost;
            this.aabb.combine(lb,c1b);
            if(c1.proxy!=null){
                // leaf cost = area(combined aabb)
                discendingCost1+=this.aabb.surfaceArea();
            }else{
                // node cost = area(combined aabb) - area(old aabb)
                discendingCost1+=this.aabb.surfaceArea()-c1b.surfaceArea();
            }
            var discendingCost2=incrementalCost;
            this.aabb.combine(lb,c2b);
            if(c2.proxy!=null){
                // leaf cost = area(combined aabb)
                discendingCost2+=this.aabb.surfaceArea();
            }else{
                // node cost = area(combined aabb) - area(old aabb)
                discendingCost2+=this.aabb.surfaceArea()-c2b.surfaceArea();
            }
            if(discendingCost1<discendingCost2){
                if(creatingCost<discendingCost1){
                    break;// stop descending
                }else{
                    sibling=c1;// descend into first child
                }
            }else{
                if(creatingCost<discendingCost2){
                    break;// stop descending
                }else{
                    sibling=c2;// descend into second child
                }
            }
        }
        var oldParent=sibling.parent;
        var newParent;
        if(this.numFreeNodes>0){
            newParent=this.freeNodes[--this.numFreeNodes];
        }else{
            newParent=new OIMO.DBVTNode();
        }
        newParent.parent=oldParent;
        newParent.child1=leaf;
        newParent.child2=sibling;
        newParent.aabb.combine(leaf.aabb,sibling.aabb);
        newParent.height=sibling.height+1;
        sibling.parent=newParent;
        leaf.parent=newParent;
        if(sibling==this.root){
            // replace root
            this.root=newParent;
        }else{
            // replace child
            if(oldParent.child1==sibling){
                oldParent.child1=newParent;
            }else{
                oldParent.child2=newParent;
            }
        }
        // update whole tree
        do{
            newParent=this.balance(newParent);
            this.fix(newParent);
            newParent=newParent.parent;
        }while(newParent!=null);
    }
function ( leaf ) { if ( this . root == null ) { this . root = leaf ; return ; } var lb = leaf . aabb ; var sibling = this . root ; var oldArea ; var newArea ; while ( sibling . proxy == null ) { // descend the node to search the best pair var c1 = sibling . child1 ; var c2 = sibling . child2 ; var b = sibling . aabb ; var c1b = c1 . aabb ; var c2b = c2 . aabb ; oldArea = b . surfaceArea ( ) ; this . aabb . combine ( lb , b ) ; newArea = this . aabb . surfaceArea ( ) ; var creatingCost = newArea * 2 ; var incrementalCost = ( newArea - oldArea ) * 2 ; // cost of creating a new pair with the node var discendingCost1 = incrementalCost ; this . aabb . combine ( lb , c1b ) ; if ( c1 . proxy != null ) { // leaf cost = area(combined aabb) discendingCost1 += this . aabb . surfaceArea ( ) ; } else { // node cost = area(combined aabb) - area(old aabb) discendingCost1 += this . aabb . surfaceArea ( ) - c1b . surfaceArea ( ) ; } var discendingCost2 = incrementalCost ; this . aabb . combine ( lb , c2b ) ; if ( c2 . proxy != null ) { // leaf cost = area(combined aabb) discendingCost2 += this . aabb . surfaceArea ( ) ; } else { // node cost = area(combined aabb) - area(old aabb) discendingCost2 += this . aabb . surfaceArea ( ) - c2b . surfaceArea ( ) ; } if ( discendingCost1 < discendingCost2 ) { if ( creatingCost < discendingCost1 ) { break ; // stop descending } else { sibling = c1 ; // descend into first child } } else { if ( creatingCost < discendingCost2 ) { break ; // stop descending } else { sibling = c2 ; // descend into second child } } } var oldParent = sibling . parent ; var newParent ; if ( this . numFreeNodes > 0 ) { newParent = this . freeNodes [ -- this . numFreeNodes ] ; } else { newParent = new OIMO . DBVTNode ( ) ; } newParent . parent = oldParent ; newParent . child1 = leaf ; newParent . child2 = sibling ; newParent . aabb . combine ( leaf . aabb , sibling . aabb ) ; newParent . height = sibling . height + 1 ; sibling . parent = newParent ; leaf . parent = newParent ; if ( sibling == this . root ) { // replace root this . root = newParent ; } else { // replace child if ( oldParent . child1 == sibling ) { oldParent . child1 = newParent ; } else { oldParent . child2 = newParent ; } } // update whole tree do { newParent = this . balance ( newParent ) ; this . fix ( newParent ) ; newParent = newParent . parent ; } while ( newParent != null ) ; }
Insert a leaf to the tree.
@param   node
Insert a leaf to the tree .