A recent post by Simo Santavirta featured an algorithm with an irresistible name: Extremely Fast Line Argorithm. A comment on that article piqued my interest and I decided to test the algorithm out against Adobe’s Graphics.lineTo.

I did a little formatting on the efla function and one substantive tweak to take the BitmapData to draw on as a function parameter. One bit that is different about the AS3 version from the original version by Po-Han Lin is the replacement of Math.abs with a well-known bitwise trick for AS3. The static Math.abs call would certainly be a performance killer.

For the competition, I simply included a Graphics.moveTo/Graphics.lineTo pair and drew the result to a Shape. See here for why Shape is better than Sprite in simple cases like these. I’ve also included test cases at various stage qualities, which affects the lineTo drawing. At the end of the line drawing loop I record the time elapsed, draw the result to a BitmapData, and record the time elapsed again. The reason for the draw to a BitmapData is to achieve parity with the efla algorithm, since it results in lines drawn to a BitmapData. Unfortunately, there is no possibility of converting the efla output to vector graphics to achieve parity the other way. This makes the Graphics.lineTo more flexible overall. But is it faster? We shall see after the test code:

package
{
    import flash.display.*;
    import flash.text.*;
    import flash.utils.*;
 
    /**
    *   A test comparing the performance of the "Extremely Fast Line Algorithm" (EFLA) to 
    *   @author Jackson Dunstan (EFLA by Po-Han Lin, AS3 port by Simo Santavirta)
    */
    public class LineDrawingTest extends Sprite
    {
        public function LineDrawingTest()
        {
            var logger:TextField = new TextField();
            logger.autoSize = TextFieldAutoSize.LEFT;
            addChild(logger);
            function log(msg:*): void { logger.appendText(msg + "\n"); }
 
            var bmd:BitmapData = new BitmapData(1000, 1000, false, 0xffffff);
            const NUM_ITERATIONS:int = 3000;
            var i:int;
            var beforeTime:int;
            var lineToTime:int;
 
            var shape:Shape = new Shape();
            var graphics:Graphics = shape.graphics;
            graphics.lineStyle(1, 0x00ff00, 1);
 
            beforeTime = getTimer();
            for (i = 0; i < NUM_ITERATIONS; ++i)
            {
                efla(0, 0, 999, 999, 0x00ff00, bmd);
            }
            log("efla: " + (getTimer()-beforeTime));
 
            stage.quality = StageQuality.LOW;
            beforeTime = getTimer();
            for (i = 0; i < NUM_ITERATIONS; ++i)
            {
                graphics.moveTo(0, 0);
                graphics.lineTo(999, 999);
            }
            lineToTime = getTimer() - beforeTime;
            bmd.draw(shape);
            log("(low) lineTo vector: " + lineToTime + ", bitmap: " + (getTimer()-beforeTime));
 
            stage.quality = StageQuality.MEDIUM;
            beforeTime = getTimer();
            for (i = 0; i < NUM_ITERATIONS; ++i)
            {
                graphics.moveTo(0, 0);
                graphics.lineTo(999, 999);
            }
            lineToTime = getTimer() - beforeTime;
            bmd.draw(shape);
            log("(medium) lineTo vector: " + lineToTime + ", bitmap: " + (getTimer()-beforeTime));
 
            stage.quality = StageQuality.HIGH;
            beforeTime = getTimer();
            for (i = 0; i < NUM_ITERATIONS; ++i)
            {
                graphics.moveTo(0, 0);
                graphics.lineTo(999, 999);
            }
            lineToTime = getTimer() - beforeTime;
            bmd.draw(shape);
            log("(high) lineTo vector: " + lineToTime + ", bitmap: " + (getTimer()-beforeTime));
 
            stage.quality = StageQuality.BEST;
            beforeTime = getTimer();
            for (i = 0; i < NUM_ITERATIONS; ++i)
            {
                graphics.moveTo(0, 0);
                graphics.lineTo(999, 999);
            }
            lineToTime = getTimer() - beforeTime;
            bmd.draw(shape);
            log("(best) lineTo vector: " + lineToTime + ", bitmap: " + (getTimer()-beforeTime));
        }
 
        /**
        *   "Extremely Fast Line Algorithm"
        *   @author Po-Han Lin (original version: http://www.edepot.com/algorithm.html)
        *   @author Simo Santavirta (AS3 port: http://www.simppa.fi/blog/?p=521)
        *   @author Jackson Dunstan (minor formatting)
        *   @param x X component of the start point
        *   @param y Y component of the start point
        *   @param x2 X component of the end point
        *   @param y2 Y component of the end point
        *   @param color Color of the line
        *   @param bmd Bitmap to draw on
        */
        private function efla(x:int, y:int, x2:int, y2:int, color:uint, bmd:BitmapData): void
        {
            var shortLen:int = y2-y;
            var longLen:int = x2-x;
 
            if ((shortLen ^ (shortLen >> 31)) - (shortLen >> 31) > (longLen ^ (longLen >> 31)) - (longLen >> 31))
            {
                shortLen ^= longLen;
                longLen ^= shortLen;
                shortLen ^= longLen;
 
                var yLonger:Boolean = true;
            }
            else
            {
                yLonger = false;
            }
 
            var inc:int = longLen < 0 ? -1 : 1;
 
            var multDiff:Number = longLen == 0 ? shortLen : shortLen / longLen;
 
            if (yLonger)
            {
                for (var i:int = 0; i != longLen; i += inc)
                {
                    bmd.setPixel(x + i*multDiff, y+i, color);
                }
            }
            else
            {
                for (i = 0; i != longLen; i += inc)
                {
                    bmd.setPixel(x+i, y+i*multDiff, color);
                }
            }
        }
    }
}

Now for the results:

Environment efla lineTo (low) lineTo (medium) lineTo (high) lineTo (best)
3.0 Ghz Intel Core 2 Duo, 4 GB RAM, Windows XP 64 1 vector/79 bitmap 1 vector/325 bitmap 1 vector/2588 bitmap 1 vector/5403 bitmap

Since the lineTo calls simply queue drawing for later, it is natural to expect them to execute extremely quickly. As we see with the different stage quality settings, the bitmap drawing takes longer and longer as we raise the quality while the vector time remains constant. So a fair evaluation of the lineTo performance is really the time to draw to the bitmap since that, as previously stated, brings the two tests into parity with an equivalent output. Given that, we can easily see that the efla algorithm is indeed a good deal quicker than its closest equivalent: lineTo on LOW stage quality settings. The difference becomes wide even at MEDIUM stage quality and extreme on HIGH and BEST quality settings. So, if you need a really fast and basic line drawing algorithm, you may as well have a look at efla as it truly is an “Extremely Fast Line Algorithm”.