minioctree
click to toggle between collision testing and 3D wireframe view
/**
* Copyright mutantleg ( http://wonderfl.net/user/mutantleg )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/5fTj
*/
package {
import flash.display.StageQuality;
import flash.geom.Vector3D;
import flash.geom.Matrix3D;
import flash.events.MouseEvent;
import flash.events.Event;
import flash.display.Sprite;
public class FlashTest extends Sprite {
public function FlashTest() {
stage.quality = StageQuality.MEDIUM;
oct = new xOctTree();
oct.maxx = 460; oct.maxy = 460; oct.maxz = 460;
var i:int; var num:int; var a:xBox;
num = 32;
for (i = 0; i < num; i++)
{
a = new xBox();
a.minx = Math.random() * 256;
a.miny = Math.random() * 256;
a.minz = Math.random() * 256;
a.maxx = a.minx + Math.random() * 64;
a.maxy = a.miny + Math.random() * 64;
a.maxz = a.minz + Math.random() * 64;
oct.addBox(a, 8);
}//nexti
wire = new xWire();
wire.g = graphics;
stage.addEventListener(MouseEvent.CLICK, onClick);
stage.addEventListener(Event.ENTER_FRAME, onEnter);
}//ctor
public function onClick(e:MouseEvent):void
{ mode = 1 - mode;}
public var oct:xOctTree;
public var wire:xWire;
public var mode:int = 0;
public var trans:Matrix3D = new Matrix3D();
public function onEnter(e:Event):void
{
graphics.clear();
graphics.lineStyle(2, 0);
var mx:Number; var my:Number;
mx = stage.mouseX; my = stage.mouseY;
if (mode == 1) { draw2DMode(); return; }
var deg:Number;
deg = 230 - mx ;
deg /= 3;
if (deg < -90) { deg = -90;}
if (deg > 90) {deg =90;}
trans.identity();
trans.appendRotation(deg, Vector3D.Y_AXIS);
trans.appendRotation(45, Vector3D.X_AXIS);
trans.appendScale(0.5,0.5,0.5);
wire.mat = trans.rawData;
oct.debRenderWire(wire);
}//onenter
public function draw2DMode():void
{
oct.debRenderXY(graphics);
var mx:Number; var my:Number;
mx = stage.mouseX; my = stage.mouseY;
graphics.drawCircle(mx, my, 8);
if (oct.isOverXY(mx - 8, my - 8, 16, 16))
{
graphics.beginFill(0xFF, 1);
graphics.drawCircle(mx, my, 8);
graphics.endFill();
}//endif
}//draw2d
}//classend
}
import flash.display.Graphics;
internal class xWire
{
//transform matrix
//(default is the identity matrix)
public var mat:Vector.<Number> = Vector.<Number>([
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
0, 0, 0, 1]);
public var scrw:Number = 460/2;
public var scrh:Number = 460/2;
public var g:Graphics;
public function drawProjLine(ax:Number, ay:Number, az:Number,
bx:Number, by:Number, bz:Number):void
{
var rx0:Number; var ry0:Number;
var rx1:Number; var ry1:Number;
var w:Number;
//hack to rotate it in center
ax -= scrw; ay -= scrh; az -= 256;
bx -= scrw; by -= scrh; bz -= 256;
rx0 = ax * mat[0] + ay * mat[4] + az * mat[8] + mat[12];
ry0 = ax * mat[1] + ay * mat[5] + az * mat[9] + mat[13];
w = ax * mat[3] + ay * mat[7] + az * mat[11] + mat[15];
if (w == 0) { return; }
rx0 /= w; ry0 /= w;
rx1 = bx * mat[0] + by * mat[4] + bz * mat[8] + mat[12];
ry1 = bx * mat[1] + by * mat[5] + bz * mat[9] + mat[13];
w = bx * mat[3] + by * mat[7] + bz * mat[11] + mat[15];
if (w == 0) { return; }
rx1 /= w; ry1 /= w;
g.moveTo(rx0+scrw, ry0+scrh);
g.lineTo(rx1+scrw, ry1+scrh);
}//drawprojline
public function drawBox2(a:xBox):void
{
drawBox(a.minx, a.miny, a.minz, a.maxx, a.maxy, a.maxz);
}//dbox2
public function drawBox(minx:Number, miny:Number, minz:Number,
maxx:Number, maxy:Number, maxz:Number):void
{
drawProjLine(minx, miny, minz, maxx, miny, minz);
drawProjLine(minx, maxy, minz, maxx, maxy, minz);
drawProjLine(minx, miny, maxz, maxx, miny, maxz);
drawProjLine(minx, maxy, maxz, maxx, maxy, maxz);
drawProjLine(minx, miny, minz, minx, maxy, minz);
drawProjLine(maxx, miny, minz, maxx, maxy, minz);
drawProjLine(minx, miny, maxz, minx, maxy, maxz);
drawProjLine(maxx, miny, maxz, maxx, maxy, maxz);
drawProjLine(minx, miny, minz, minx, miny, maxz);
drawProjLine(maxx, miny, minz, maxx, miny, maxz);
drawProjLine(minx, maxy, minz, minx, maxy, maxz);
drawProjLine(maxx, maxy, minz, maxx, maxy, maxz);
}//drawbox
}//xwire
internal class xBox
{
public var minx:Number = 0; public var miny:Number = 0; public var minz:Number = 0;
public var maxx:Number = 0; public var maxy:Number = 0; public var maxz:Number = 0;
}//box
internal class xOctTree
{
public var minx:Number = 0; public var miny:Number = 0; public var minz:Number = 0;
public var maxx:Number = 0; public var maxy:Number = 0; public var maxz:Number = 0;
public var depth:int = 0;
public var vecBox:Vector.<xBox>;
public var child:Vector.<xOctTree>;
public function xOctTree()
{
depth = 0; vecBox = new Vector.<xBox>(0, false);
}//ctor
public function genChild():void
{
var sx:Number; var sy:Number; var sz:Number;
var hx:Number; var hy:Number; var hz:Number;
sx = maxx - minx; sy = maxy - miny; sz = maxz - minz;
hx = sx * 0.5; hy = sy * 0.5; hz = sz * 0.5;
child = new Vector.<xOctTree>(8, false);
var i:int; var a:xOctTree;
for (i = 0; i < 8; i++)
{
a = new xOctTree();
child[i] = a;
a.minx = minx; a.miny = miny; a.minz = minz;
a.maxx = minx+hx; a.maxy = miny+hy; a.maxz = minz+hz;
a.depth = depth + 1;
}//nexti
//child[0] is same as default
child[1].minx += hx; child[1].maxx += hx;
child[2].minz += hz; child[2].maxz += hz;
child[3].minx += hx; child[3].maxx += hx;
child[3].minz += hz; child[3].maxz += hz;
child[4].miny += hy; child[4].maxy += hy;
child[5].minx += hx; child[5].maxx += hx;
child[5].miny += hy; child[5].maxy += hy;
child[6].minz += hz; child[6].maxz += hz;
child[6].miny += hy; child[6].maxy += hy;
child[7].minx += hx; child[7].maxx += hx;
child[7].minz += hz; child[7].maxz += hz;
child[7].miny += hy; child[7].maxy += hy;
}//genchild
public function addBox(a:xBox, maxd:int=8):Boolean
{
///aabb inside test
if (a.minx < minx) { return false; } if (a.minx > maxx) { return false; }
if (a.miny < miny) { return false; } if (a.miny > maxy) { return false; }
if (a.minz < minz) { return false; } if (a.minz > maxz) { return false; }
if (a.maxx < minx) { return false; } if (a.maxx > maxx) { return false; }
if (a.maxy < miny) { return false; } if (a.maxy > maxy) { return false; }
if (a.maxz < minz) { return false; } if (a.maxz > maxz) { return false; }
//check if we below max depth
//if so make children for this node
if (child == null && depth < maxd) { genChild(); }
//reached max depth (and box fits)
if (child == null) { vecBox.push(a); return true; }
//check if box fits inside a child node
var i:int; for (i = 0; i < 8; i++)
{ if (child[i].addBox(a, maxd)) { return true; } }
//box didnt fit inside any children
vecBox.push(a);
return true;
}//addmesh
public function isOverXY(ax:Number, ay:Number, aw:Number, ah:Number):Boolean
{
var i:int; var num:int; var a:xOctTree; var m:xBox;
if (maxx < ax) { return false; }
if (maxy < ay ) { return false; }
if (ax + aw < minx) { return false; }
if (ay + ah < miny) { return false; }
num = vecBox.length;
for (i = 0; i < num; i++)
{
m = vecBox[i];
if (m.maxx < ax) { continue; }
if (m.maxy < ay ) { continue; }
if (ax + aw < m.minx) { continue; }
if (ay + ah < m.miny) { continue; }
return true;
}//nexti
if (child == null) { return false; }
for (i = 0; i < 8; i++) { a = child[i]; if (a.isOverXY(ax, ay, aw, ah)) { return true; } }
return false;
}//isoverxy
public function debRenderXY(g:Graphics):void
{
var i:int; var num:int; var a:xOctTree; var m:xBox;
num = vecBox.length;
g.drawRect(minx, miny, maxx - minx, maxy - miny);
for (i = 0; i < num; i++)
{
m = vecBox[i];
g.beginFill(0, 0.5);
g.drawRect(m.minx, m.miny, m.maxx - m.minx, m.maxy - m.miny);
g.endFill();
}//nexti
if (child == null) { return; }
for (i = 0; i < 8; i++) { a = child[i]; a.debRenderXY(g); }
}//debrender
public function debRenderWire(w:xWire):void
{
var i:int; var num:int; var a:xOctTree; var m:xBox;
num = vecBox.length;
w.g.lineStyle(1,0xFF,0.25);
w.drawBox(minx,miny,minz,maxx,maxy,maxz);
w.g.lineStyle(2,0);
for (i = 0; i < num; i++)
{
m = vecBox[i];
w.drawBox2(m);
}//nexti
if (child == null) { return; }
for (i = 0; i < 8; i++) { a = child[i]; a.debRenderWire(w); }
}//debrenderwire
}//octtree