Hello all, I have a problem understanding this algorithem that I found in a book called Tricks Of The Windows Game Programming Gurus. This is the function : int Draw_Line(int x0, int y0, // starting position int x1, int y1, // ending position UCHAR color, // color index UCHAR *vb_start, int lpitch) // video buffer and memory pitch { // this function draws a line from xo,yo to x1,y1 using differential error // terms (based on Bresenahams work) int dx, // difference in x''s dy, // difference in y''s dx2, // dx,dy * 2 dy2, x_inc, // amount in pixel space to move during drawing y_inc, // amount in pixel space to move during drawing error, // the discriminant i.e. error i.e. decision variable index; // used for looping // pre-compute first pixel address in video buffer vb_start = vb_start + x0 + y0*lpitch; // compute horizontal and vertical deltas dx = x1-x0; dy = y1-y0; // test which direction the line is going in i.e. slope angle if (dx>=0) { x_inc = 1; } // end if line is moving right else { x_inc = -1; dx = -dx; // need absolute value } // end else moving left // test y component of slope if (dy>=0) { y_inc = lpitch; } // end if line is moving down else { y_inc = -lpitch; dy = -dy; // need absolute value } // end else moving up // compute (dx,dy) * 2 dx2 = dx << 1; dy2 = dy << 1; // now based on which delta is greater we can draw the line if (dx > dy) { // initialize error term error = dy2 - dx; // draw the line for (index=0; index <= dx; index++) { // set the pixel *vb_start = color; // test if error has overflowed if (error >= 0) { error-=dx2; // move to next line vb_start+=y_inc; } // end if error overflowed // adjust the error term error+=dy2; // move to the next pixel vb_start+=x_inc; } // end for } // end if /slope/ <= 1 else { // initialize error term error = dx2 - dy; // draw the line for (index=0; index <= dy; index++) { // set the pixel *vb_start = color; // test if error overflowed if (error >= 0) { error-=dy2; // move to next line vb_start+=x_inc; } // end if error overflowed // adjust the error term error+=dx2; // move to the next pixel vb_start+=y_inc; } // end for } // end else /slope/ > 1 // return success return(1); } // end Draw_Line I am not sure what error is for? Its says this function will fill in the pixels from point p1 to point p2 with the pixels that most closely fit the real line. For one thing, I am really new to this, if your going from point a to point b, how is that not straight? It says a point from a and b has holes in it? Is this what the error thing is for? What does error calculate? Thanks you ahead of time for everyones help. braves

Ok, let''s say I''m drawing a line from (0,0) to (4,3) If I want to draw a pixel every x coordinate, I''d have to draw (0, 0) (1, 0.75) (2, 1.5) (3, 2.25) and (4, 3) to be precisly along the line. However, there isn''t such an animal as a pixel with a fractional coordinate, so you''d have to approximate to: (0,0) (1,1) (2,2) (3,2) (4,3). In this case I just rounded. But rounding needs floating point, and floating point is slower than integer ops (especially when converting from floats to ints). So an integer only algorithm has to keep track of fractions of pixels and do the rounding decision off of that.

SiCrane,
So your saying that error keeps track of the fraction and the rounding decision? If that''s the case, shouldn''t error be a float and not a int?
braves

I have that ecxact same function (and the exact same book )
the function uses the points to calculate the slope of the line, and then the function uses the slope of the line to draw the line.
lets say you have (0,0) and (10,13), and you want to draw a line between them. the slope of that line would be 13/10.
using the point-slope formuala, (y-y0) = m*(x-x0).
so y would be, in this case:
y = 13/10*(x-0)+0,
y = 13/10*x
ok, so examin the table:
x / y
--------------
1 1.3
2 2.6
3 3.9
4 5.2

and etc. if you were to graph each point on graph paper, you''d have the points defining a line, but not actaully creating one, which is what we have to do with our line drawing function!
so, the algoritm you have is called Bresenham''s Algorithm, and it actually works very well. what it does is that it still increments the x value by 1 each loop, but instead of plotting the calculated y value (which gives up our choppy line), it decides whether to change the y value (from -1 to 1, inclusive) so it looks like its heading towards our calculated y values. this way, each y value in between the start and end points are drawn to, and the algorithm makes sure the points are graphed out using the calculated y values as a guidline.
the error value is what tells the algorithm when to change the y value (by 0, -1, or 1, depending on if the first point is higher/lower the end point, etc.).
i know this probably wasn''t the easiest explanation (or the best ) on your question, but it still makes sense.
i had trouble seeing how the error value worked and stuff, so what i did was i went to my graph paper, and used the algorithm to actually draw a line on graph paper (using each box as a pixel), and you know what?
it worked
it drew me a great line

It doesn''t have to be a float if it only hase the float part of the number. That may sound stupid. Look at this example (its not code *gasp*)

3.14
^ ^-------Float part (everything after the decimal)
/---------Int part, (everything before the decimal)

if you take that and split it into two parts, you get:

3 (an int)
14 (also an int)

I think SiCrane means the error variable holds the 14 (or whatever else it may be) There is probably a better term for it than float part too, but that is what my TI-83 calculator calls it...

--------------------


You are not a real programmer until you end all your sentences with semicolons;

Yanroy@usa.com

Actually the error term is fractions of dx. let''s say you''re graphing y = mx + b. Then m = (dy / dx). If we keep in incrementing x by one, then we increment y by dy / dx. However if have an accumulator of the number of 1 / dx''s that we store, then we only need to increment y by 1 whenever the 1 / dx''s exceeds .5 dx. To simplify we increment our accumulator by 2 * dy every pixel step and increment y whenever the 1 / dx''s exceeds dx. So the accumulator as in integer because we always know that it will be a fraction of the form a / dx.

So it''s not like it''s storing the 14 in 3.14, it''s more like it''s storing the 1/7 in 22/7. (But because we know it''s over 7, we just need the 1.)

Hello,
I am still not getting this 100%. Ok, the first thing I don''t understand is thisif (dx>=0)
{
x_inc = 1;

} // end if line is moving right
else
{
x_inc = -1;
dx = -dx; // need absolute value

} // end else moving left

why is he doing this dx = -dx?
if (dy>=0)
{
y_inc = lpitch;
} // end if line is moving down
else
{
y_inc = -lpitch;
dy = -dy; // need absolute value
Same thing here, why is he doing this dy = -dy;
I guess I am trying to figure out why he needs the absolute value?
Now this :
// compute (dx,dy) * 2
dx2 = dx << 1;
dy2 = dy << 1;
why does he have to multiply by 2(or shift once to the left rather)?
The other part I don''t get is this
// initialize error term
error = dy2 - dx;
why does he use thse two and not dy2 - dy1 or somethng like that? I understand what the error variable is for, I just don''t see the things he is doing is making a more straighter line?
braves

Ok, the reason it takes a absolute value:
You''ve got an error term and every time we increment our x by one spot, we increment our error by dy2, and increment the y value if the error is greater than 0. Well if dy2 is negative, then your error will never be greater than 0. It will keep going down. We could fix it by flipping test so that we''re checking error less than 0. But that would be annoying and slows things down. You don''t want if statements in a tight loop. A similar thing happens with dx, but we subrtract dx''s from the error term to check rounding. So once we need to increment the y position, we subtract a negative, which adds to error. Then error will always go up and we will continue to increment y regardless of whether or not it needs it.

As for the dx2 and dy2:
Every time we increment x, we accumulate the error term. If the error term reaches 0.5 then we increment y and reset the error term. Well the rounding rule is on 0.5 or higher you round, right? Since the error term is in terms of 1 / dx''s if dx is odd then we''d need to check the rounding rule against a fraction. Instead if we accumulate the rounding rule against 1 / (2 * dx) then you can check against an integer.

As for the dy2 - dx:
The starting value for error would be equal to the slope. (dy / dx). However, we decided to accumulate error in terms of 1 / (2 * dx) instead of 1 / dx. So the starting value is dy2.

It''s fastest to do an check against 0 rathar than a another variable or an integer. So instead of checking error against dx, (1 / 2 of dx2) if you rebase the error term against .5 being 0 instead of dx, then we need to decrement it''s starting value by dx.

Hence: dy2 - dx.