Public Group

# Bresenham's Line Drawing Algorithm

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

## Recommended Posts

I am having trouble getting my code to work with steep slopes. It works fine for -1 <= m <= 1 but not for large values. Any advice is appreciated. void doBresenham( int x1, int y1, int x2, int y2 ) { int mSlope, increaseSameY, increaseNewY; int dX, dY, p, x, y; if (x1 > x2) { doBresenham(x2, y2, x1, y1); return; } dX = x2 - x1; dY = y2 - y1; if (dY < 0) { dY = -dY; mSlope = -1.0; } else { mSlope = 1.0; } increaseSameY = 2 * dY; increaseNewY = 2 * dY - 2 * dX; p = 2 * dY - dX; y = y1; for (x = x1; x <= x2; x++) { glVertex2i( x, y ); if (p < 0) { p += increaseSameY; } else { p += increaseNewY; y += mSlope; } } }

##### Share on other sites
Bresenham's only works for shallow slopes. To make it work for m > 1, change the algorithm around so that it walks up y while conditionally incrementing x, instead of the other way around. Essentially, you're reflecting the algorithm around the line x=y.

##### Share on other sites
I've been attempting to do that but I'm not sure at which point to do the flip. Should I set a conditional at the very beginning of the code or just create a second block like this (only switch x and y):

for (x = x1; x <= x2; x++)
{
glVertex2i( x, y );
if (p < 0)
{
p += increaseSameY;
}
else
{
p += increaseNewY;
y += mSlope;
}
}

##### Share on other sites
Your conditional should be at the beginning of your function, and choose from the move-along-x and move-along-y versions of the algorithm; otherwise your performance will drop.

##### Share on other sites
I tried this but it seems to working the same, maybe a bit better but there are still plenty of holes.

void doBresenham( int x1, int y1, int x2, int y2 )
{
int mSlope, increaseSameY, increaseNewY, increaseSameX, increaseNewX;
int dX, dY, p, x, y;

if (x1 > x2)
{
doBresenham(x2, y2, x1, y1);
return;
}

dX = x2 - x1;
dY = y2 - y1;

if ( (dY/dX) <= 1.0 && (dY/dX) >= -1.0 ) {

if (dY < 0) {
dY = -dY;
mSlope = -1.0;
}
else {
mSlope = 1.0;
}

increaseSameY = 2 * dY;
increaseNewY = 2 * dY - 2 * dX;
p = 2 * dY - dX;
y = y1;

for (x = x1; x <= x2; x++)
{
glVertex2i( x, y );
if (p < 0)
{
p += increaseSameY;
}
else
{
p += increaseNewY;
y += mSlope;
}
}

}
else {

if (dX < 0) {
dX = -dX;
mSlope = -1.0;
}
else {
mSlope = 1.0;
}

increaseSameX = 2 * dX;
increaseNewX = 2 * dX - 2 * dY;
p = 2 * dX - dY;
x = x1;

for (y = y1; y <= y2; y++)
{
glVertex2i( x, y );
if (p < 0)
{
p += increaseSameX;
}
else
{
p += increaseNewX;
x += mSlope;
}
}
}

}

##### Share on other sites
sorry this just took me back to when I did 'scan conversion of a circle' at uni. I think I had Besenham nitemares ever since

good luck

##### Share on other sites
If line rasterization is your thing, you might be interested in Xiaolin Wu's algorithm, which supports anti-aliased lines.

1. 1
2. 2
Rutin
20
3. 3
4. 4
A4L
15
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633737
• Total Posts
3013614
×