• Advertisement

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.

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

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


Link to post
Share on other sites
Advertisement
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 this post


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


[edit]
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

or any advice if I'm wrong will be helpful, Thanks!!

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

Share this post


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


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

pixels = 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]

Share this post


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


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


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


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

Share this post


Link to post
Share on other sites
Ask and ye shall receive:

<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

// adjust the error term
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

// adjust the error term
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 this post


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

try multiplying by 2 instead...Okay

old code:

      

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


// 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; // you lose the sign bit by shifting 1 to the left

dy2 = dy << 1;


New code:


  
// compute horizontal and vertical deltas

if(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 angle

if (dx>=0)
{
xInc = 1;

} // end if line is moving right

else
{
xInc = -1;
dx = -dx; // need absolute value


} // end else moving left


// 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 * 2; // maintains sign bit

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


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


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


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


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


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


Link to post
Share on other sites

  • Advertisement