Understanding Bresenham's Algorithm
Author
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?
It''s 3 AM here in France... so the only thing I can do now is to give my Bresenham''s implementation :
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!
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!
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]
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]
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]
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.
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.
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...
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:
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?
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?
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]
"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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
