Bresenham's Line Drawing Algorithm
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;
}
}
}
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.
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;
}
}
for (x = x1; x <= x2; x++)
{
glVertex2i( x, y );
if (p < 0)
{
p += increaseSameY;
}
else
{
p += increaseNewY;
y += mSlope;
}
}
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.
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;
}
}
}
}
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;
}
}
}
}
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
good luck
If line rasterization is your thing, you might be interested in Xiaolin Wu's algorithm, which supports anti-aliased lines.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement