• ### Announcements

#### Archived

This topic is now archived and is closed to further replies.

# Understanding Bresenham's Algorithm

## Recommended Posts

http://graphics.cs.ucdavis.edu/GraphicsNotes/Bresenhams-Algorithm/Bresenhams-Algorithm.html I have gone there to learn about Bresenham''s Algorithm. I think I understand the algorithm, but I''m not sure I understand the order of operation in which things are performed. For instance, the first pixel, or starting point of the line is colored, that I have down, then I''m not sure what is next. Do you increment E(error) then check to see if( E > 0). If thats true, then you increment the y coordinate by 1? Or do you first increment E, then increment the x coordinate, then check to see if(E > 0) and if thats true, you then increment the y coordianate by 1?

##### Share on other sites
It''s 3 AM here in France... so the only thing I can do now is to give my Bresenham''s implementation :

  void line(int x1,int y1,int x2,int y2,int color){    int error;    int xinc=1;    int yinc=1;    int deltaX=x2-x1;    int deltaY=y2-y1;    int deltaX2,deltaY2;    if(deltaX<0)    {        xinc=-xinc;        deltaX=-deltaX;    }    if(deltaY<0)    {        yinc=-yinc;        deltaY=-deltaY;    }    deltaX2=deltaX<<1;    deltaY2=deltaY<<1;    if(deltaX>deltaY)    {        error=deltaX;        pixel(x1,y1,color);        while(deltaX--)        {            x1+=xinc;            error+=deltaY2;            if(error>=deltaX2)            {                y1+=yinc;                error-=deltaX2;            }            pixel(x1,y1,color);        }    }    else    {        error=deltaY;        pixel(x1,y1,color);        while(deltaY--)        {            y1+=yinc;            error+=deltaX2;            if(error>=deltaY2)            {                x1+=xinc;                error-=deltaY2;            }            pixel(x1,y1,color);        }    }}

It''s not the best nor the fastest but if it can help you...
I''ll try to answer you really when I''ll be back!

##### Share on other sites
Dammit, I thought I had a patent on staying up too late answering questions.

Here are a couple of links from this very site about Bresenham:
One
Two

Alimonster

"If anyone can show me, and prove to me, that I am wrong in thought or deed, I will gladly change. I seek the truth, which never yet hurt anybody. It is only persistence in self-delusion and ignorance which does harm." -- Marcus Aurelius

[edited by - Alimonster on March 24, 2002 9:44:43 PM]

##### Share on other sites
quote:
Original post by Brian Jones
Do you increment E(error) then check to see if( E > 0).

No. Your error E is initialised to have the value of 1-m (where m is the gradient, deltaY/deltaX), which corresponds to the distance below the top of the first pixel that the line exits the pixel on the right hand side. I hope that made sense. It won't be positive to start with because you choose the driving axis as that which has the higher rate of change relative to the other.

Anyway... the order of operations goes like this:
x_i <- x1;y_i <- y1;m <- (y2-y1)/(x2-x1);Loop   Illuminate the current pixel: (x_i,y_i);   (test for E>0)   If E>0      Increment y coordinate (y_i <- y_i + 1)      E = E - 1;   Increment E (E <- E + m)   Increment X coordinate (x_i <- x_i + 1)until (x_i==x2)

Then there's the integer version...

The operations follow the same order, but are scaled so that only integer values are needed in the computation.

Personally, I find it interesting that while Bresenham's Algorithm provides an aesthetically pleasing approximation to a straight line, statistically the pixels are not the best fit.

Cheers,

Timkin

[edited by - Timkin on March 25, 2002 2:02:19 AM]

##### Share on other sites
It is a best fit vertically isn''t it? You are minimizing the error vertically to the line rather than perpendicular. At least that is my understanding of it, but then I just copy the algorithm out of a book when I need it.

##### Share on other sites
Ahh, I understand it now. Sorry for the laaaaaaaaattttteeee reply.

##### Share on other sites
Quick question, what if xinc!=1? hehe, for example, in my game, the character moves on a line. I am using bressenham and I want to make it smoother.

##### Share on other sites
Bresenham take advantage of the "discrete" number of pixels on a screen. That''s the reason why it uses incremental step of 1 and error term. So...

##### Share on other sites
Yeah, but I can''t just have my character move 1 pixel at a time! I want to divide the line into minilines I guess you could say. Here''s my code:

  if(deltax>deltay) {		xinc=xinc2;		error+=deltay2;		if(error>=deltax2) {			yinc=yinc2;			error-=deltax2;		} else			yinc=0;	} else {		yinc=yinc2;		error+=deltax2;		if(error>=deltay2) {			xinc=xinc2;			error-=deltay2;		} else			xinc=0;	}

Now, the character moves 3 pixels, because thats the absolute bounciest I can have it without it bugging me too much. The
if(error>=deltay2) {
xinc=xinc2;
error-=deltay2;
}
is what I want to change so that it can increment by every third. So the natural idea to do is:
if(error>=deltay2/3) {
xinc=xinc2/3;
error-=deltay2/3;
}

This is close, but still doesn''t get it. The character doesn''t move exactly to the target. Does anyone know how to fix this?

##### Share on other sites
Bresenham's line algorithm uses integers instead of floats, that makes its interest...

"Yeah, but I can't just have my character move 1 pixel at a time!" -> WHY?

[edited by - bloodscourge on April 14, 2002 7:44:00 PM]

##### Share on other sites
I cannot have my character move one pixel at a time because at 800*600 resolution, it takes the character forever to walk across the screen! and if I speed up the whole game, it just doesn''t work right. The other sprites would go too fast because it''s sleeping less, and it would just be a big mess re organizing it.

##### Share on other sites
Forget the sleeps. Locking framerate is a bad way to go. There''s a simple way to fix this though.

You''re currently moving v pixels per frame for a given unit. You sleep for t0 seconds each frame. Now, let''s fix this.

Don''t sleep at all. Instead, record the time since last frame deltaT. Then, change all your ... += v code to ... += (v/t0) * deltaT.

Yeah, why not!

##### Share on other sites
What if I were to do it this way: Lets say I did the line with xinc and yinc as 1. Then, I would find the point corresponding with the character on it. How would I achieve this?

Sponge Factory
--Muzlack

##### Share on other sites
I understand this way, but what is DeltaT?

• ### Forum Statistics

• Total Topics
627702
• Total Posts
2978712

• 21
• 14
• 12
• 10
• 12