🔒 Locked

Understanding Bresenham's Algorithm

Started by Brian Jones Mar 23, 2002 at 6:48 PM 13 replies 1k views

Original Post

Mar 23, 2002 at 6:48 PM

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?

BloodScourge

Mar 24, 2002 at 7:52 PM

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!

Alimonster

Mar 24, 2002 at 8:42 PM

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]

Timkin

Mar 25, 2002 at 12:59 AM

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]

LilBudyWizer

Mar 25, 2002 at 7:15 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.

Brian Jones

Mar 26, 2002 at 7:12 PM

Ahh, I understand it now. Sorry for the laaaaaaaaattttteeee reply.

Muzlack

Apr 14, 2002 at 2:37 PM

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.

BloodScourge

Apr 14, 2002 at 3:48 PM

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...

Muzlack

Apr 14, 2002 at 6:02 PM

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?

BloodScourge

Apr 14, 2002 at 6:43 PM

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]

Muzlack

Apr 14, 2002 at 7:18 PM

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.

TerranFury

Apr 14, 2002 at 8:43 PM

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 t₀ 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/t₀) * deltaT.

BloodScourge

Apr 14, 2002 at 8:51 PM

Yeah, why not!

Muzlack

Apr 14, 2002 at 8:56 PM

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

Muzlack

Apr 14, 2002 at 8:58 PM

I understand this way, but what is DeltaT?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.