# Building a Better Line Algorithm Than Bresenham

The traditional Bresenham line function revolves around something called the incremental which is related to taking the derivative of a function and iterating through the function. This algorithm is generally accepted as the most optimized line algorithm.void LineBresenham(int x1, int y1, int x2, int y2, int color) { int dy = y2 - y1; int dx = x2 - x1; int stepx, stepy; if (dy < 0) { dy = -dy; stepy = -1; } else { stepy = 1; } if (dx < 0) { dx = -dx; stepx = -1; } else { stepx = 1; } dy <<= 1; // dy is now 2*dy dx <<= 1; // dx is now 2*dx drawpixel(x1,y1, color); if (dx > dy) { int fraction = dy - (dx >> 1); // same as 2*dy - dx while (x1 != x2) { if (fraction >= 0) { y1 += stepy; fraction -= dx; // same as fraction -= 2*dx } x1 += stepx; fraction += dy; // same as fraction -= 2*dy drawpixel(x1, y1, color); } } else { int fraction = dx - (dy >> 1); while (y1 != y2) { if (fraction >= 0) { x1 += stepx; fraction -= dy; } y1 += stepy; fraction += dx; drawpixel(x1, y1, color); } } }

The problem with this approach is that it has to brach on each iteration on whether it should keep going or not on the current scan. By reversing the logic so that we write a span of pixels at a time then make the decision to branch we can optimize this further. This approach also takes better advantage of modern cpu caches and branch prediction. We can also optimize special cases of vertical and horizontal lines. I've tested the following algorithm to be rougly 10-12% faster than Bresenham on a pentium 3 chipset.

// this code was originally written in 2000 void LineOptimized(int x1, int y1, int x2, int y2, int color) { int cx, cy, ix, iy, dx, dy, ddx= x2-x1, ddy= y2-y1; if (!ddx) { //vertical line special case if (ddy > 0) { cy= y1; do drawpixel(x1, cy++, color); while (cy <= y2); return; } else { cy= y2; do drawpixel(x1, cy++, color); while (cy <= y1); return; } } if (!ddy) { //horizontal line special case if (ddx > 0) { cx= x1; do drawpixel(cx, y1, color); while (++cx <= x2); return; } else { cx= x2; do drawpixel(cx, y1, color); while (++cx <= x1); return; } } if (ddy < 0) { iy= -1; ddy= -ddy; }//pointing up else iy= 1; if (ddx < 0) { ix= -1; ddx= -ddx; }//pointing left else ix= 1; dx= dy= ddx*ddy; cy= y1, cx= x1; if (ddx < ddy) { // < 45 degrees, a tall line do { dx-=ddy; do { drawpixel(cx, cy, color); cy+=iy, dy-=ddx; } while (dy >=dx); cx+=ix; } while (dx > 0); } else { // >= 45 degrees, a wide line do { dy-=ddx; do { drawpixel(cx, cy, color); cx+=ix, dx-=ddy; } while (dx >=dy); cy+=iy; } while (dy > 0); } }

Matheus1 1Please, can you answer why shift here:

dy <<= 1; // dy is now 2*dy

dx <<= 1; // dx is now 2*dx

and here:

(dx >> 1); // same as 2*dy - dx

Since it's works perfectly without it?

Thanks.

2010/10/124 3Tony Barrera2011/05/151 1Tony Barrera2011/05/150 0Toni2012/09/10Contact Me0 0hanno2013/02/20Contact Me1 0hanno2013/02/201 0Will2013/04/09Contact Me0 0cs_man2013/10/190 0cs_man2013/10/190 3<html>

<head>

<script type="text/JavaScript">

function Bresenham(x1,y1,x2,y2,d){

var canvas = document.getElementById("canvas");

var ctx = canvas.getContext("2d");

ctx.fillStyle="red";

function lineBres(x1,y1,x2,y2){

var dy = Math.abs(y2-y1);

var dx = Math.abs(x2-x1);

var p = 2*dy=dx;

var TwoDyMinusDx = 2*(dy - dx);

var TwoDy =2*dy;

var x ;

var y;

if(x1 > x2)

{

x = x2;

y = y2;

x2 = x1;

}

else{

x = x1;

y = y1;

}

setPixel(x,y);

while(x < x2){

x++;

if(p < 0)

p += TwoDy;

else{

y++;

p += TwoDyMinusDx;

}

setPixel(x,y);

}

}

</script>

</head>

<body onload="Bresenham(250,50,50,100);">

<canvas id="canvas" width="500px" height="500px" style="background:cyan; border: 2px solid black;">

Your browser does not support the HTML5 canvas tag.

</canvas>

</body>

</html>

cs_man2013/10/190 3Duy2013/11/06Contact Me0 7internet2014/04/172 5MR.pal2014/07/1653 0MR.pal2014/07/160 0