Archived

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

Understanding Bresenham's Algorithm

This topic is 5726 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites