#### Archived

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

# Line Drawing Algorithms

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

## Recommended Posts

Hi there, I''ve been trying to use Bresenham''s line drawing algorithm in a 16-bit mode on a 640x480 screen. But when I use it, the diagonal lines have these gaping "holes" in them (a couple pixels wide at least). Needless to say, it looks like crap. Anyone have any suggestions? Sorry if this is a lame question, but I couldn''t find any decent answers elsewhere.

##### Share on other sites
post the crappy line plotter code you are using and maybe someone can point out what the problem(s) might be.

or email me the code to look over at orion76@hot.rr.com

I have a made a 16 bit color line plotter myself in Direct Draw 7
and it works fine

##### Share on other sites
I can think of several vague reasons why it would behave like that. So, can''t say anything until I see some code. A while ago I posted a complete line drawing function, which perhaps can help you. Look at the second-to-last post in this thread: http://www.gamedev.net/community/forums/topic.asp?topic_id=111209

##### Share on other sites
His problem with the gaps seems to be happenning because he's using a byte pointer to plot the pixels instead of using a word pointer or casting the byte pointer to a word pointer.

I had this sort of problem myself.

also the way the deltas are calculated

dx = x1 - x0; // if x1=0 and x1=2 then dx = 1 and not 2 pixels

should be

dx = x1 - x0 + 1; // this will calculate the range of pixels correctly

[edited by - CodeJunkie on December 8, 2002 8:26:06 PM]

##### Share on other sites
I''m not quite sure how Brensenham''s algorithim works myself, (if anyone could expalin it, that would be great) but shouldn''t the deltas be...

DeltaX = abs(EndX - StartX);
DeltaY = abs(EndY - StartY);

???

##### Share on other sites
exactly, thanks MattS423

otherwise a negative delta would cause weird side effects maybe even gaps

[EDIT]
this code would work as well
if(x1>=x0) // fixed it was wrong x1<=x0 sorry
{dx = x1 - x0 + 1;}
else
{dx = x0 - x1 + 1;}

and if the deltas aren't calculated with the right pixel ranges
the line's slope ratio will be off

Here's the heart of plotting a line:

    ShortAccum = 0; // maintains short/long range ratiopixels = longPixelRange;while(pixels--) // repeat until no more pixels to plot{ buffer[offset] = pixClr; // plot a pixel of course offset += longPixelDistance; // move to next pixel along the long range// Once the accumlator is equal or greater then the long range you can move towards the short distance ShortAccum += shortPixelRange;  if(ShortAccum>=longPixelRange)   {   offset += shortPixelDistance; // move to next pixel along the short range   ShortAccum -= longPixelRange; // maintain the short/long range ratio  }}

Well at least that's how I see it.

[edited by - CodeJunkie on December 8, 2002 9:12:21 PM]

[edited by - CodeJunkie on December 8, 2002 9:29:55 PM]

No problem.

##### Share on other sites
Well Code, I tried your WORD pointer idea such that:

*(WORD*)vbStart = color; // needs (WORD*), not (WORD)

and I divided the lpitch by two.

But, I get this weird-ass behaviour...For one, the coordinates seem off. And for things like polygons, they appear to be in two "pieces" across the screen from each other (right y coords, wrong x coords). I''m going to have a look at this, but God knows what''s going on. Oh the joys of it all.

##### Share on other sites
if you cast to a word pointer then don''t divide the pitch by 2 it can remain as it is

only if you choose to use a word pointer divide pitch by 2...Okay

sorry for the confusion

##### Share on other sites
Ok, well, I guess that really isn''t the problem then. I left the casting in *(WORD*)vbstart = color; and left the lpitch alone...But the gaping holes still appear. :\ I guess it''s back to the drawing board...Gah.

##### Share on other sites
try the above formulas for the deltas first okay

##### Share on other sites
Yeah, I already had that anyways. Well, except for the +1 thing, which I tried, and didn''t effect things really. Oh well. Just not my day!

Post the code.

##### Share on other sites

<textarea>
int BasicGraphics::drawLine(int x0, int y0, // starting position
int x1, int y1, // ending position
UCHAR color, // color index
UCHAR *vbStart, 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,
xInc, // amount in pixel space to move during drawing
yInc, // 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
vbStart = vbStart + 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)
{
xInc = 1;

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

} // end else moving left

dx++;

// test y component of slope

if (dy>=0)
{
yInc = lpitch;
} // end if line is moving down
else
{
yInc = -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
*(WORD*)vbStart = color;
//*vbStart = color;

// test if error has overflowed
if (error >= 0)
{
error-=dx2;

// move to next line
vbStart+=yInc;

} // end if error overflowed

error+=dy2;

// move to the next pixel
vbStart+=xInc;

} // 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
//*vbStart = color;
*(WORD*)vbStart = color;

// test if error overflowed
if (error >= 0)
{
error-=dy2;

// move to next line
vbStart+=xInc;

} // end if error overflowed

error+=dx2;

// move to the next pixel
vbStart+=yInc;

} // end for

} // end else |slope| > 1

// return success
return 1;

} // end
</textarea>

...welcome to hell, kids!

##### Share on other sites
because shifting the deltas left drops the sign bit (not good thing)

old code:

      // compute horizontal and vertical deltasdx = x1-x0;dy = y1-y0;// test which direction the line is going in i.e. slope angleif (dx>=0)   {   xInc = 1;   } // end if line is moving rightelse   {   xInc = -1;   dx    = -dx;  // need absolute value   } // end else moving left// test y component of slopeif (dy>=0)   {   yInc = lpitch;   } // end if line is moving downelse   {   yInc = -lpitch;   dy    = -dy;  // need absolute value   } // end else moving up// compute (dx,dy) * 2dx2 = dx << 1; // you lose the sign bit by shifting 1 to the leftdy2 = dy << 1;

New code:

  // compute horizontal and vertical deltasif(x1>=x0){dx = x1-x0+1;}else{dx=x0-x1+1;}if(y1>=y0){dy = y1-y0+1;}else{dy=y0-y1+1;}// test which direction the line is going in i.e. slope angleif (dx>=0)   {   xInc = 1;   } // end if line is moving rightelse   {   xInc = -1;   dx    = -dx;  // need absolute value   } // end else moving left// test y component of slopeif (dy>=0)   {   yInc = lpitch;   } // end if line is moving downelse   {   yInc = -lpitch;   dy    = -dy;  // need absolute value   } // end else moving up// compute (dx,dy) * 2dx2 = dx * 2;  // maintains sign bitdy2 = dy * 2;

[edited by - CodeJunkie on December 8, 2002 9:52:34 PM]

[edited by - CodeJunkie on December 8, 2002 9:54:28 PM]

##### Share on other sites
No dice, dood. It''s actually worse, now. I had no idea 16-bit crap would be this annoying.

##### Share on other sites
Besides, doing dx << 1 is ok, since by now I have the absolute value (according to my code)...

##### Share on other sites
Geez this is annoying, I think my brain hurts now man

try changing error initialization

from:
x range(error = dy2 - dx
y range(error = dx2 - dy

to:
x range(error = dy2 - dx2 // remember the ratio must be maintained... I think!
y range(error = dx2 - dy2

Good Luck Man, now I''m spent

##### Share on other sites
WOW, Finally I think I got it!

don''t need to multiply deltas by 2, that will just expand the ratio

multiply xInc by 2 because its only moving one byte at a time and needs to move 2 bytes at a time (so every move in the x range is only a half step)

Geez, sorry took so long for me to get it but hopefully you understand a lot more about line plotting.

Good Luck.

##### Share on other sites
*sigh* I tried that, too, but alas, to no avail. I really appreciate all the help you''ve given me! I think the problem might be more fundamental/something else than what we''re going after here. I tried your Line16 algorithm you gave me, and I got the same results as my code. Maybe 16-bit surfaces don''t like being cast as UCHAR*''s or something. I''ll take a look at it later. Thanks again!

##### Share on other sites
Are you sure its a 16 bit surface?? (not 24 or 32 bit)

maybe it's some weird kind of surface

[edited by - CodeJunkie on December 9, 2002 2:56:30 AM]

##### Share on other sites
Yes! Got it! I was right about the casting...It didn''t like the UCHAR* bit. I changed all the pointers to surfaces from UCHAR* to WORD*, and it came out great! Thanks for all the help!

##### Share on other sites
Excellent!!!

Glad to help those who want to learn what little I know.