AS3 Bresenhams line algorithm

February 23rd, 2006

here is an implementation of the bresenhams line algorithm. I tried to avoid the Math.abs, which I found in most source or pseudo codes. I think, this couldn't be much faster in AS3. I'm developing a custom line algorithm, cause its the first step trying to code an own texture mapper, since the one I used is ported from C.

Here it is:

 
private function bresenham( x0: int, y0: int, x1: int, y1: int, value: int ): void
{
	var error: int;
 
	var dx: int = x1 - x0;
	var dy: int = y1 - y0;
 
	var yi: int = 1;
 
	if( dx < dy )
	{
		//-- swap end points
		x0 ^= x1; x1 ^= x0; x0 ^= x1;
		y0 ^= y1; y1 ^= y0; y0 ^= y1;
	}
 
	if( dx < 0 )
	{
		dx = -dx; yi = -yi;
	}
 
	if( dy < 0 )
	{
		dy = -dy; yi = -yi;
	}
 
	if( dy > dx )
	{
		error = -( dy >> 1 );
 
		for( ; y1 < y0 ; y1++ )
		{
			output.setPixel32( x1, y1, value );
			error += dx;
			if( error > 0 )
			{
				x1 += yi;
				error -= dy;
			}
		}
	}
	else
	{
		error = -( dx >> 1 );
 
		for( ; x0 < x1 ; x0++ )
		{
			output.setPixel32( x0, y0, value );
			error += dy;
			if( error > 0 )
			{
				y0 += yi;
				error -= dx;
			}
		}
	}
}
 

watch here Flash8.5Player required

Filed under: actionscript

11 Responses to “AS3 Bresenhams line algorithm”

  1. joa Says:
    February 23rd, 2006 at 6:03 pm

    “The fastest method of handling all cases is to write a custom routine for each of the 8 line types:

    1) x1 = deltay
    2) x1 y2, deltax &gt;= deltay
    4) x1 y2, deltax x2, y1 = deltay
    6) x1 &gt; x2, y1 x2, y1 &gt; y2, deltax &gt;= deltay
    8) x1 &gt; x2, y1 &gt; y2, deltax

  2. joa Says:
    February 23rd, 2006 at 6:05 pm

    Hm, this is only the half comment?
    gamedev article

    I think you will have a lot of fun andre :)

  3. André Michelle Says:
    February 23rd, 2006 at 6:09 pm

    The fastest method of handling all cases is to write a custom routine for each of the 8 line types
    Yes, of course. You are right. Didn’t thought about this ugly solution :)

  4. Miha L Says:
    February 23rd, 2006 at 6:28 pm

    Wow, nice and fast indeed! :)

  5. Jon B Says:
    February 23rd, 2006 at 7:58 pm

    Great example Andre – I saw an article about line drawign algorithms somewhere and it looked really good, covered many different types, can’t find it now tho :(

    So is there a reason this code wouldn’t work in AS2 as well (obviously some rewriting would be needed).

    Also how does thge speed get affected by multiple lines (in particular I’m thinking a 3D wireframe demo)

  6. ekameleon Says:
    March 1st, 2006 at 11:45 am

    Yes :)
    I use for the moment a simple algorithm. in AS2 to create an Array.

    static public function getLine(p1, p2):Array {

    var dx,dy,x,y,s1,s2,e,temp,swap:Number ;

    dy = Math.abs( p2.y - p1.y ) ;
    dx = Math.abs( p2.x - p1.x ) ;
    s1 = MathsUtil.sign( p2.x - p1.x ) ;
    s2 = MathsUtil.sign ( p2.y - p1.y ) ;
    x = p1.x ;
    y = p1.y ;
    if (dy&gt;dx) {
    temp = dx ;
    dx = dy ;
    dy = temp ;
    swap = 1 ;
    } else {
    swap = 0 ;
    }
    e = 2 * dy - dx ;
    var ar:Array = [] ;
    for ( var i:Number = 0 ; i=0) {
    if (swap==1) x+= s1 ;
    else y+=s2 ;
    e-=2*dx;
    }
    if (swap==1) y+=s2 ;
    else x += s1 ;
    e+=2*dy ;
    }
    return ar ;
    }

    But your code is really interesting ! Thanks :)

  7. toxi Says:
    March 5th, 2006 at 5:25 pm

    andré, you should check out this algorithm by po han lin, which i’ve used as basis for the one used in Processing: http://www.edepot.com/algorithm.htm – it beats bresenham speedwise and also is not much more lengthy codewise… hth!

  8. joa Says:
    March 5th, 2006 at 5:55 pm

    It is http://www.edepot.com/algorithm.htm :o)

  9. joa Says:
    March 5th, 2006 at 5:56 pm

    Mhm, that was your URL in the clipboard. :-\
    http://www.edepot.com/algorithm.html

  10. Jalava Says:
    December 15th, 2006 at 3:36 pm

    I just noticed that there is something wrong with this algo, it does not support 45 degree lines.

  11. simppa.fi/blog » Extremely Fast Line Algorithm AS3 Optimized Says:
    November 26th, 2009 at 4:44 pm

    [...] have used (a little modified version of) the Andre Michelle’s port from Bresenhams line algorithm and always thought it would be the fastest way to draw a line on BitmapData in [...]

Leave a Reply