forked from: Bounding Volume Hierarchy

by Glidias forked from Bounding Volume Hierarchy (diff: 4)
Bounding volume hierarchy test
@author saharan
♥0 | Line 385 | Modified 2014-07-09 14:36:23 | MIT License
play

ActionScript3 source code

/**
 * Copyright Glidias ( http://wonderfl.net/user/Glidias )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/4dbl
 */

// forked from saharan's Bounding Volume Hierarchy
package  {
    import flash.display.Sprite;
    import flash.display.Stage3D;
    import flash.events.Event;
    import flash.events.KeyboardEvent;
    import flash.events.MouseEvent;
    import flash.text.TextField;
    import flash.text.TextFormat;
    import flash.ui.Keyboard;
    import flash.utils.Dictionary;
    import flash.utils.getTimer;
    import flash.utils.setTimeout;
    import net.hires.debug.Stats;
    /**
     * Bounding volume hierarchy test
     * @author saharan
     */
    [SWF(width = "465", height = "465", frameRate = "60")]
    public class BoundingVolumeHierarchyTest extends Sprite {
        private var count:uint;
        private var tf:TextField;
        private var ts:Dictionary;
        private var tree:DynamicBVTree;
        private var px:Number;
        private var py:Number;
        private var press:Boolean;
        
        public function BoundingVolumeHierarchyTest() {
            if (stage) init();
            else addEventListener(Event.ADDED_TO_STAGE, init);
        }
        
        private function init(e:Event = null):void {
            removeEventListener(Event.ADDED_TO_STAGE, init);
            tf = new TextField();
            tf.selectable = false;
            tf.defaultTextFormat = new TextFormat("Courier New", 11, 0xffffff, null, null, null, null, null, null, null, null, null, -6);
            tf.alpha = 0.4;
            tf.x = 0;
            tf.y = 0;
            tf.width = 465;
            tf.height = 465;
            addChild(tf);
            ts = new Dictionary(true);
            tree = new DynamicBVTree();
            var id:int = 0;
            stage.addEventListener(Event.ENTER_FRAME, frame);
            stage.addEventListener(MouseEvent.MOUSE_DOWN, function(e:Event = null):void {
                if (tree.root != null && deleteNode(tree.root)) return;
                px = mouseX;
                py = mouseY;
                press = true;
            });
            stage.addEventListener(MouseEvent.MOUSE_UP, function(e:Event = null):void {
                if (!press) return;
                press = false;
                var cx:Number = px + mouseX >> 1;
                var cy:Number = py + mouseY >> 1;
                var w:Number = px - mouseX >> 1;
                w = 1;
                var h:Number = py - mouseY >> 1;
                if (w < 0) w = -w;
                if (h < 0) h = -h;
               // if (w < 4 || h < 4) return;
                addText(insert(tree, ++id, new AABB(cx - w, cx + w, cy - h, cy + h)));
            });
        }
        
        private function addText(node:DynamicBVTreeNode):void {
            var txt:TextField = new TextField();
            txt.alpha = 0.6;
            txt.selectable = false;
            txt.defaultTextFormat = new TextFormat("Courier New", 12, 0xffffff);
            txt.width = 100;
            txt.height = 32;
            txt.text = "[" + node.proxy.id + "]";
            txt.x = node.aabb.minX;
            txt.y = node.aabb.minY;
            ts[node] = txt;
            addChild(txt);
        }
        
        private function deleteNode(node:DynamicBVTreeNode):Boolean {
            if (!node.aabb.intersectsWithPoint(mouseX, mouseY, 0)) return false;
            if (node.proxy == null) {
                var c1:DynamicBVTreeNode = node.child1;
                var c2:DynamicBVTreeNode = node.child2;
                return ((deleteNode(c1) ? 1 : 0) | (deleteNode(c2) ? 1 : 0)) != 0;
            } else {
                tree.deleteLeaf(node);
                removeChild(ts[node]);
                return true;
            }
        }
        
        private function frame(e:Event):void {
            graphics.clear();
            graphics.beginFill(0x101010);
            graphics.drawRect(0, 0, 465, 465);
            graphics.endFill();
            if (tree.root != null) {
                render(tree.root, 0, tree.root.height);
                tf.text = tree.print(tree.root, 0, "");
            } else tf.text = "";
            if (press) {
                graphics.lineStyle(1, 0xffff00);
                graphics.drawRect(px, py, mouseX - px, mouseY - py);
            }
        }
        
        private function insert(tree:DynamicBVTree, id:int, aabb:AABB):DynamicBVTreeNode {
            var leaf:DynamicBVTreeNode = new DynamicBVTreeNode();
            leaf.proxy = new Proxy(id);
            leaf.aabb.minX = aabb.minX;
            leaf.aabb.maxX = aabb.maxX;
            leaf.aabb.minY = aabb.minY;
            leaf.aabb.maxY = aabb.maxY;
            tree.insertLeaf(leaf);
            return leaf;
        }
        
        private function render(node:DynamicBVTreeNode, depth:int, maxDepth:int, hit:Boolean = true):void {
            if (hit == true && !node.aabb.intersectsWithPoint(mouseX, mouseY, 0)) {
                hit = false;
            }
            if (node.proxy == null) {
                var c1:DynamicBVTreeNode = node.child1;
                var c2:DynamicBVTreeNode = node.child2;
                render(c1, depth + 1, maxDepth, hit);
                render(c2, depth + 1, maxDepth, hit);
                if (!hit) return;
                graphics.lineStyle(1, 0xff0000, (maxDepth - depth) / maxDepth);
            } else {
                graphics.lineStyle(1, hit ? 0x00ff00 : 0x0000ff);
                if (hit) {
                    var dx:int = Math.random() * 4 - 2; // wriggle around
                    var dy:int = Math.random() * 4 - 2;
                    node.aabb.minX += dx;
                    node.aabb.maxX += dx;
                    node.aabb.minY += dy;
                    node.aabb.maxY += dy;
                    ts[node].x += dx;
                    ts[node].y += dy;
                    tree.deleteLeaf(node); // re-insert the node
                    tree.insertLeaf(node);
                }
            }
            var minX:Number = node.aabb.minX;
            var minY:Number = node.aabb.minY;
            graphics.drawRect(minX, minY, node.aabb.maxX - minX, node.aabb.maxY - minY);
        }
        
    }

}
class DynamicBVTree {
    public var root:DynamicBVTreeNode;
    
    public function DynamicBVTree() {
    }
    
    public function insertLeaf(leaf:DynamicBVTreeNode):void {
        if (root == null) {
            root = leaf;
            return;
        }
        var sibling:DynamicBVTreeNode = root;
        var aabb:AABB = new AABB();
        var oldArea:Number;
        var newArea:Number;
        while (sibling.proxy == null) { // descend the node to search the best pair
            oldArea = sibling.aabb.surfaceArea();
            aabb.combine(leaf.aabb, sibling.aabb);
            newArea = aabb.surfaceArea();
            var creatingCost:Number = newArea; // cost of creating a new pair with the node
            var incrementalCost:Number = newArea - oldArea;
            
            var discendingCost1:Number = incrementalCost;
            aabb.combine(leaf.aabb, sibling.child1.aabb);
            if (sibling.child1.proxy != null) {
                // leaf cost = area(combined aabb)
                discendingCost1 += aabb.surfaceArea();
            } else {
                // node cost = area(combined aabb) - area(old aabb)
                discendingCost1 += aabb.surfaceArea() - sibling.child1.aabb.surfaceArea();
            }
            
            var discendingCost2:Number = incrementalCost;
            aabb.combine(leaf.aabb, sibling.child2.aabb);
            if (sibling.child2.proxy != null) {
                // leaf cost = area(combined aabb)
                discendingCost2 += aabb.surfaceArea();
            } else {
                // node cost = area(combined aabb) - area(old aabb)
                discendingCost2 += aabb.surfaceArea() - sibling.child2.aabb.surfaceArea();
            }
            
            if (discendingCost1 < discendingCost2) {
                if (creatingCost < discendingCost1) {
                    break; // stop descending
                } else {
                    sibling = sibling.child1; // descend into first child
                }
            } else {
                if (creatingCost < discendingCost2) {
                    break; // stop descending
                } else {
                    sibling = sibling.child2; // descend into second child
                }
            }
        }
        var oldParent:DynamicBVTreeNode = sibling.parent;
        var newParent:DynamicBVTreeNode = new DynamicBVTreeNode();
        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 == root) {
            // replace root
            root = newParent;
        } else {
            // replace child
            if (oldParent.child1 == sibling) {
                oldParent.child1 = newParent;
            } else {
                oldParent.child2 = newParent;
            }
        }
        // update whole tree
        do {
            newParent = balance(newParent);
            fix(newParent);
            newParent = newParent.parent;
        } while (newParent != null);
    }
    
    public function print(node:DynamicBVTreeNode, indent:int, text:String):String {
        var hasChild:Boolean = node.proxy == null;
        if (hasChild) text = print(node.child1, indent + 1, text);
        for (var i:int = indent * 2; i >= 0; i--) {
            text += " ";
        }
        text += (hasChild ? getBalance(node) : "[" + node.proxy.id + "]") + "\n";
        if (hasChild) text = print(node.child2, indent + 1, text);
        return text;
    }
    
    public function deleteLeaf(leaf:DynamicBVTreeNode):void {
        if (leaf == root) {
            root = null;
            return;
        }
        var parent:DynamicBVTreeNode = leaf.parent;
        var sibling:DynamicBVTreeNode;
        if (parent.child1 == leaf) {
            sibling = parent.child2;
        } else {
            sibling = parent.child1;
        }
        if (parent == root) {
            root = sibling;
            sibling.parent = null;
            return;
        }
        var grandParent:DynamicBVTreeNode = parent.parent;
        sibling.parent = grandParent;
        if (grandParent.child1 == parent) {
            grandParent.child1 = sibling;
        } else {
            grandParent.child2 = sibling;
        }
        do {
            grandParent = balance(grandParent);
            fix(grandParent);
            grandParent = grandParent.parent;
        } while (grandParent != null);
    }
    
    private function getBalance(node:DynamicBVTreeNode):int {
        if (node.proxy != null) return 0;
        return node.child1.height - node.child2.height;
    }
    
    private function balance(node:DynamicBVTreeNode):DynamicBVTreeNode {
        var balance:int = getBalance(node);
        if (balance > 1) {
            if (getBalance(node.child1) < 0) {
                node.child1 = rotateLeft(node.child1);
            }
            return rotateRight(node);
        } else if (balance < -1) {
            if (getBalance(node.child2) > 0) {
                node.child2 = rotateRight(node.child2);
            }
            return rotateLeft(node);
        }
        return node;
    }
    
    private function fix(node:DynamicBVTreeNode):void {
        var c1:DynamicBVTreeNode = node.child1;
        var c2:DynamicBVTreeNode = node.child2;
        node.aabb.combine(c1.aabb, c2.aabb);
        var h1:int = c1.height;
        var h2:int = c2.height;
        if (h1 < h2) {
            node.height = h2 + 1;
        } else {
            node.height = h1 + 1;
        }
    }
    
    private function rotateRight(node:DynamicBVTreeNode):DynamicBVTreeNode {
        var p:DynamicBVTreeNode = node.parent;
        var l:DynamicBVTreeNode = node.child1;
        var lr:DynamicBVTreeNode = l.child2;
        (node.child1 = lr).parent = node;
        fix(node);
        ((l.child2 = node).parent = l).parent = p;
        fix(l);
        if (p != null) {
            if (p.child2 == node) {
                p.child2 = l;
            } else {
                p.child1 = l;
            }
            fix(p);
        } else root = l;
        return l;
    }
    
    private function rotateLeft(node:DynamicBVTreeNode):DynamicBVTreeNode {
        var p:DynamicBVTreeNode = node.parent;
        var r:DynamicBVTreeNode = node.child2;
        var rl:DynamicBVTreeNode = r.child1;
        (node.child2 = rl).parent = node;
        fix(node);
        ((r.child1 = node).parent = r).parent = p;
        fix(r);
        if (p != null) {
            if (p.child1 == node) {
                p.child1 = r;
            } else {
                p.child2 = r;
            }
            fix(p);
        } else root = r;
        return r;
    }
    
}
class DynamicBVTreeNode {
    public var child1:DynamicBVTreeNode;
    public var child2:DynamicBVTreeNode;
    public var parent:DynamicBVTreeNode;
    
    public var proxy:Proxy;
    
    public var height:int;
    
    public var aabb:AABB;
    
    public function DynamicBVTreeNode() {
        aabb = new AABB();
    }
    
}
class AABB {
    public var minX:Number;
    public var maxX:Number;
    public var minY:Number;
    public var maxY:Number;
    
    public function AABB(
        minX:Number = 0, maxX:Number = 0,
        minY:Number = 0, maxY:Number = 0
    ) {
        this.minX = minX;
        
        this.maxX = maxX;
        this.minY = minY;
        this.maxY = maxY;
    }
    
    public function combine(aabb1:AABB, aabb2:AABB):void {
        if (aabb1.minX < aabb2.minX) {
            minX = aabb1.minX;
        } else {
            minX = aabb2.minX;
        }
        if (aabb1.maxX > aabb2.maxX) {
            maxX = aabb1.maxX;
        } else {
            maxX = aabb2.maxX;
        }
        if (aabb1.minY < aabb2.minY) {
            minY = aabb1.minY;
        } else {
            minY = aabb2.minY;
        }
        if (aabb1.maxY > aabb2.maxY) {
            maxY = aabb1.maxY;
        } else {
            maxY = aabb2.maxY;
        }
        var margin:Number = 3;
        minX -= margin;
        maxX += margin;
        minY -= margin;
        maxY += margin;
    }
    
    public function surfaceArea():Number {
        return 2 * (maxX - minX + maxY - minY);
    }
    
    public function intersectsWithPoint(x:Number, y:Number, z:Number):Boolean {
        return x >= minX && x <= maxX && y >= minY && y <= maxY;
    }
    
}

class Proxy {
    public var id:int;
    
    public function Proxy(id:int) {
        this.id = id;
    }
}