Bounding Volume Hierarchy
Dynamic bounding volume tree test
AABBツリーの階層構造を動的に構築するテスト
ツリーは更新時にAVL木のようになるべくバランスを取ろうとする
Drag & Drop: Add AABB
Click: Remove AABB
/**
* Copyright saharan ( http://wonderfl.net/user/saharan )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/jA37
*/
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;
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;
}
}