Will Perone

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);
    }
}
16 Comments
Matheus 5 1
Hi,

Please, 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/126 5
for speed i think
Tony Barrera 2011/05/152 1
In here and looking i might have good news here too!
Tony Barrera 2011/05/150 0
The 2's in Bresenhams line algorithm is for rounding!
Toni 2012/09/10 Contact Me0 0
This posting koncked my socks off
hanno 2013/02/20 Contact Me1 0
A quick benchmark on my Core i7 in linux with gcc v4.7 showed different results - the "optimized" line algorithm needs approximately double the time of the standard bresenham algorithm. I tested 2.4 million lines of length 2000, where the "drawpixel" command just incremented a variable. The Bresenham algorithm took 1.48s, the optimized algorithm about 2.9s. Compilation was done with all optimization flags I could think of.
hanno 2013/02/201 0
By the way: Your Bresenham implementation is much faster than others that are available on the internet, e.g. http://rosettacode.org/wiki/Bitmap/Bresenham's_line_algorithm .
Will 2013/04/09 Contact Me0 0
Thanks for the speed test hanno. I wrote this algorithm in 2000 on processors which are very different than today. I'm sure depending on the processor architecture one or the other is faster; both of these were my best optimizations to the algorithms. The basic difference is that they are inversions of the branch/loop. One accumulates error each look then renders while the other renders a span then accumulates error. The span rendering version allows one to make optimizations where you can copy faster to the render surface by using 64 or 128 bit copies.
cs_man 2013/10/190 0
can anyone write this code in javascript plzzzz
cs_man 2013/10/190 5
can anyone tell me what is missing in my code cauz i'm not expert in javascript i need fast reply plzzz

<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_man 2013/10/190 3
this code above doesn't drawing the line in the canvas can anyone tell me why!!!
Duy 2013/11/06 Contact Me0 7
Can you help me please ? I can't find "2D_Graphic_Driver.h" file.
internet 2014/04/172 5
@cs_man: This line looks like a typo? --- var p = 2*dy=dx;
MR.pal 2014/07/1653 0
just check directory and execute it will draw line.
MR.pal 2014/07/160 0
palvadi-MR.BAlakrishnan BE
BernardAvews 2016/10/25 Contact Me0 0
Help with personal statement http://www.farbara.rs/college-essays - College essays, Essay writing about internet Buy papers online http://www.farbara.rs/the-best-writing-service - The best writing service, Buy college papers Online professional resume writing services http://www.farbara.rs/buying-an-essay - Buying an essay, Custom essay meister prices Nursing assignment help http://www.farbara.rs/where-can-i-buy-essays - Where can i buy essays, Website writing Essay review http://www.farbara.rs/what-is-the-best-custom-essay-writing-service - What is the best custom essay writing service, Essay buy

<- for private contact