Will Perone

Optimized Oriented Bounding Box intersection testing in AS3 through the Seperating Axis Theorem

So you've exhaustively read about the separating axis theorem and are still like 'How the hell do I actually code this?'. Well thankfully it's actually not that difficult if you have an understanding of vector math. Basically what you have to do is project each object onto each side of the other object. For oriented bounding boxes we can simplify this a lot. When you have a rotated rectangle, the projection of it onto a vector only has 2 parts: the vector along the width of the rectangle and the vector along the height.

public var widthOrig:Number;   // this is the width of the object before it is rotated, you will need to set this when you construct the object
public var heightOrig:Number;  // this is the height of the object before it is rotated, you will need to set this when you construct the object

// Assume 'this' is derived from a DisplayObject
public function intersect_obb(d:MyDerivedDisplayObject):Boolean
{
	var A:Point= new Point(Math.cos(this.rotation*Math.PI/180), Math.sin(this.rotation*Math.PI/180));  // axis2= (-axis1.y,axis1.x)
	var B:Point= new Point(Math.cos(d.rotation*Math.PI/180), Math.sin(d.rotation*Math.PI/180)); // axis2= (-axis1.y,axis1.x)
	// Compute difference of box centers, D = C1-C0.
	var D:Point = new Point(d.x-this.x, d.y-this.y);
	var AbsAdB:Vector.<Number>= new Vector.<Number>(4,true); 

	// axis C0+t*A0 (proj B onto Ax axis)  =>  w0 + proj(B->A0)  =>  w0 + A0*B0 + A0*B1
	AbsAdB[0]= Math.abs(A.x*B.x + A.y*B.y); //A0*B0
	AbsAdB[1]= Math.abs(A.x*-B.y + A.y*B.x); //A0*B1
	if (Math.abs(-A.y*D.x + A.x*D.y)*2 > widthOrig + d.widthOrig*AbsAdB[0] + d.heightOrig*AbsAdB[1]) return false;

	// axis C0+t*A1 (proj B onto Ay axis)  => h0 + proj(B->A1)  =>  h0 + A1*B0 + A1*B1
	AbsAdB[2] = Math.abs(-A.y*B.x + A.x*B.y); // A1*B0 
	AbsAdB[3] = AbsAdB[0]; //A1*B1 = -Ay*-By + Ax*Bx
	if (Math.abs(A.x*D.x + A.y*D.y)*2 > heightOrig + d.widthOrig*AbsAdB[2] + d.heightOrig*AbsAdB[3]) return false;

	// axis C0+t*B0 (proj A onto Bx axis)   => w1 + proj(A->B0)  =>  w1 + B0*A0 + B0*A1
	if (Math.abs(-B.y*D.x + B.x*D.y)*2 > d.widthOrig + widthOrig*AbsAdB[0] + heightOrig*AbsAdB[2]) return false;

	// axis C0+t*B1 (proj A onto By axis)   => h1 + proj(A->B1)  => h1 + B1*A0 + B1*A1
	if (Math.abs(B.x*D.x + B.y*D.y)*2 > d.heightOrig + widthOrig*AbsAdB[1] + heightOrig*AbsAdB[3]) return false;

	return true;
}


Now if we know we will be checking against an axis aligned bounding box (aabb) like a bunch of static map tiles, we can simplify a bunch of things.
public function intersect_aabb(r:Rectangle):Boolean
{
	// this is a simplification of the general intersect algorithm
	var A:Point= new Point(Math.cos(this.rotation), Math.sin(this.rotation));  // axis2= (-axis1.y,axis1.x)
	var D:Point= new Point((r.left+r.right)/2-display.x, (r.top+r.bottom)/2-display.y);
	var absax:Number= Math.abs(A.x);
	var absay:Number= Math.abs(A.y);

	if (Math.abs(A.x*D.y - A.y*D.x)*2 > heightOrig + r.height*absax + r.width*absay || 
		Math.abs(A.x*D.x + A.y*D.y)*2 > widthOrig + r.height*absay + r.width*absax ||
		Math.abs(D.y)*2 > r.height + heightOrig*absax + widthOrig*absay ||
		Math.abs(D.x)*2 > r.width + heightOrig*absay + widthOrig*absax)
		return false;

return true;
}
No Comments yet, be the first!
<- for private contact