package { import flash.display.Graphics; import flash.display.Sprite; import flash.events.MouseEvent; import flash.geom.Point; import flash.geom.Rectangle; import flash.text.TextField; import flash.text.TextFormat; import flash.utils.getTimer; [SWF(frameRate="100", backgroundColor="0x000000", width="500", height="500")] public class TriangleAABBSpeedTest extends Sprite { public var outputText : TextField; public function TriangleAABBSpeedTest() { super(); outputText = new TextField(); x = y = 250; outputText.defaultTextFormat = new TextFormat("Arial"); outputText.textColor = 0xffffff; outputText.text = "Click to start test"; outputText.x = outputText.y = -250; outputText.width = 500; addChild(outputText); stage.addEventListener(MouseEvent.MOUSE_DOWN, startTest); } // I'm thinking that storing these values as properties rather than declaring them as local vars // should be faster... private var x0 : Number; private var y0 : Number; private var x1 : Number; private var y1 : Number; private var x2 : Number; private var y2 : Number; private var l : Number; private var r : Number; private var t : Number; private var b : Number; private var top_intersection:Number ; private var bottom_intersection : Number; private var toptrianglepoint : Number; private var bottomtrianglepoint : Number; private var m: Number; private var c : Number // THESE ARE THE TWO FUNCTIONS YOU CAN OPTIMISE. // I realise that you could inline the lineRectangleIntersect method, but I'd rather not do that just yet... // I'm looking for maths/logic improvements. public function triangleAABBIntersectionTest(rect:Rectangle, vertex0:Point, vertex1:Point, vertex2:Point ) : Boolean { // YOU MUST LEAVE THESE DECLARATIONS; they simulate necessary data exchange within PV3D l = rect.left; r = rect.right; t = rect.top; b = rect.bottom; x0 = vertex0.x; y0 = vertex0.y; x1 = vertex1.x; y1 = vertex1.y; x2 = vertex2.x; y2 = vertex2.y; return lineRectangleIntersect(x0,y0,x1,y1) || lineRectangleIntersect(x1,y1,x2,y2) || lineRectangleIntersect(x2,y2,x0,y0); } public function lineRectangleIntersect(x0: Number,y0: Number,x1: Number,y1: Number):Boolean //, left:Number, right:Number, top:Number, bottom:Number) : Boolean { // Calculate m and c for the equation for the line (y = mx+c) m = (y1-y0) / (x1-x0); c = y0 -(m*x0); // if the line is going up from right to left then the top intersect point is on the left if(m>0) { top_intersection = (m*l + c); bottom_intersection = (m*r + c); } // otherwise it's on the right else { top_intersection = (m*r + c); bottom_intersection = (m*l + c); } // work out the top and bottom extents for the triangle if(y0<y1) { toptrianglepoint = y0; bottomtrianglepoint = y1; } else { toptrianglepoint = y1; bottomtrianglepoint = y0; } var topoverlap : Number; var botoverlap : Number; // and calculate the overlap between those two bounds topoverlap = top_intersection>toptrianglepoint ? top_intersection : toptrianglepoint; botoverlap = bottom_intersection<bottomtrianglepoint ? bottom_intersection : bottomtrianglepoint; // (topoverlap<botoverlap) : // if the intersection isn't the right way up then we have no overlap // (!((botoverlap<t) || (topoverlap>b)) : // If the bottom overlap is higher than the top of the rectangle or the top overlap is // lower than the bottom of the rectangle we don't have intersection. So return the negative // of that. Much faster than checking each of the points is within the bounds of the rectangle. return (topoverlap<botoverlap) && (!((botoverlap<t) || (topoverlap>b))); } public function startTest(e:MouseEvent = null) : void { var g : Graphics = graphics; g.clear(); var cullingRect : Rectangle = new Rectangle(-100,-75,200,150); var iterations : int = 100000; var timerIntersecting : int = 0 ; var timerNotIntersecting : int = 0 ; var intersectCount : int = 0; var v0 : Point = new Point(); var v1 : Point = new Point(); var v2 : Point = new Point(); var i : int = iterations; while(--i>-1) { v0.x = Math.random()*400 - 200; v0.y = Math.random()*400 - 200; v1.x = v0.x+ (Math.random()*300 -150); v1.y = v0.y+ (Math.random()*300 -150); v2.x = v0.x+ (Math.random()*300 -150); v2.y = v0.y+ (Math.random()*300 -150); var startTimer : int = getTimer(); var intersecting : Boolean = triangleAABBIntersectionTest(cullingRect, v0, v1, v2); if(intersecting) { timerIntersecting += (getTimer() - startTimer); intersectCount++; } else { timerNotIntersecting += (getTimer() - startTimer); } if(i<300) { g.lineStyle(0,0x000000); g.beginFill(intersecting ? 0x006600 : 0x660000,0.5); g.moveTo(x0,y0); g.lineTo(x1,y1); g.lineTo(x2,y2); g.lineTo(x0,y0); g.endFill(); } } g.lineStyle(0,0xffffff,0.5); g.drawRect(cullingRect.x, cullingRect.y, cullingRect.width, cullingRect.height); outputText.text = "Average time per triangle : "+(timerIntersecting+timerNotIntersecting)/iterations; outputText.appendText("\nAverage time per intersecting triangle : "+(timerIntersecting)/intersectCount); outputText.appendText("\nAverage time per non-intersecting triangle : "+(timerNotIntersecting)/(iterations-intersectCount)); } } }