Greetings! My task is to impement Bresenham's line algorithm by mapping floats to integers, but be able to draw lines of any slope, including horizontal (zero slope) and vertical (infinite slope) lines. (The near-bottom of the page has an integer-only version of this.) My implementation of the linked pseudocode works partially and I'm almost certain the problem is in my mapping or/and rasterization function(s).

The line begins at x0,y0 and ends at x1,y1. The command line reads in a square image resolution like 999 for 999x999 pixels ABS (absolute value), MAX, and MIN are defined elsewhere in my program.

Function headers are bolded for easy finding.

``````[b]My Line Rasterization Function[/b]
/*
RASTERIZELINE
Rasterize lines and call Pixel to display them.  My version.
*/

//MY BRESENHAM VERSION: This is my version of Bresenham's algorithm which doesn't entirely work.
[b]void rasterizeLine( Image &I, int x0, int y0, int x1, int y1 )[/b]
{
int dx = x1-x0;
int x0mx1 = x0-x1;
int dy = y1-y0;
int y0my1 = y0-y1;
int slope = dy/dx;
int d = 2*(y0-y1)*(1+x0)+(x1-x0)*(2*y0+1)+(2*x0*y1)-(2*x1*y0);	//from the Tiger book, p60
int D = 2*(y1-y0) - (x1-x0);
bool steep = (ABS(dy) > ABS(dx));		//higher rise than run?
int delta_x = x1 - x0;					//
int delta_y = ABS(dy);					//
int error = delta_x/2;					//pixel to color
int x = x0;								//
int y = y0;								//
int ystep;								//line moves up or down
int xhold, yhold;						//for swapping

//not slanting down right
if (steep)
{	//swap x values
//		cout << "\nSTEEP: swapping x and y values\n";

xhold=x0;
x0=x1;
x1=xhold;

//swap y values
yhold=y0;
y0=y1;
y1=yhold;
}

//right to left
if(x0 > x1)
{
//		cout << "\nRIGHT TO LEFT: swapping x and y values to draw left to right\n";

xhold=x0;
x0=x1;
x1=xhold;

//swap y values
yhold=y0;
y0=y1;
y1=yhold;
}

//line moves up to down - check midpoint
if(y0 < y1)
{
//		cout << "\nYSTEP IS POSITIVE\n";
ystep=1;
}

//line moves down to up - check midpoint
else
{
//		"\nYSTEP IS NEGATIVE\n";
ystep=-1;
}

for(x; x < x1; x++)
{
//x0 and y0 swapped with x1 and y1
if(steep)
{
//			"\nSTEEP PIXELIZATION\n";
I(y, x) = Pixel(255, 255, 255);
}

//no swapping
else
{
//			"\nPIXELIZATION, NOT STEEP\n";
I(x, y) = Pixel(255, 255, 255);
}

error = error - delta_y;

if(error < 0)
{
y = y + ystep;
error += delta_x;
}
}
}``````

My code's resulting image

My instructor has a working version of rasterizeLine for all slopes, but this uses floats.

``````[b]My Instructor's Line Rasterization Function[/b]

[b]void rasterizeLine( Image &I, int x0, int y0, int x1, int y1 )[/b]
{
int delta_x = x1 - x0;
int delta_y = y1 - y0; //slope defined
int steps = MAX( ABS(delta_x), ABS(delta_y) ); //greater rise or run?
double c = 1.0 / MAX( 1, steps ); //c is always at least 1

for( int i = 0; i <= steps; i++ )
{
int x = int( x0 + ( i * delta_x * c ) + 0.5 ); //x is the int version of the counter * change in x * (i) or (the greater absolute value of delta x or delta y) rounded up
int y = int( y0 + ( i * delta_y * c ) + 0.5 );
I( x, y ) = Pixel( 125, 255, 255 ); //plot point on screen
}
}``````

My instructor's code's resulting image. (The color difference is OK.)

``````[b]Float to Integer Mapping[/b]
/*
IMAGEX
Convert to image space's x coordinate
*/
[B]int imagex(int resolution, float xcoord)[/B] //coord is x0 or x1[/b]
{
int n = resolution;
int hn = resolution/2; //half n

if(xcoord >= 0) //quad 1 or 4 - at least half n
{
return(rti((hn) + (xcoord*hn)));
}

{
return(rti((hn) - (ABS(xcoord*hn))));
}
}

/*
IMAGEY
Convert to image space's y coordinate
*/
[b]int imagey(int resolution, float ycoord)[/b] //coord is y0 or y1
{
int n = resolution;
int hn = resolution/2; //half n

if(ycoord >= 0) //quad 3 or 4 - at least half n
{
return(rti((hn) + (ABS(ycoord*hn))));
}

{
return(rti((hn) - (ABS(ycoord*hn))));
}
}

/*
RTI
Round a float to the nearest integer.  I couldn't find an official round() function in a standard library.
*/
[b]int rti(float floater)[/b]
{
if(floater >= 0.0)
{
return static_cast<int> (floater+0.5);
}

else
{
return static_cast<int> (floater-0.5);
}
}

[b]int main(int argc, char *argv[])[/b] //arguments are unimportant for your purposes
{
<snip>

//N is input image resolution, like 999 for a 999x999 pixel image
//ix0, etc. are the integer versions of their respective floats, x0, etc.
ix0=imagex(N, x0);
ix1=imagex(N, x1);
iy0=imagey(N, y0);
iy1=imagey(N, y1);

rasterizeLine( I, ix0, iy0, ix1, iy1 );
<snip>
}``````

Attachments
data.txt is my instructor's test data which he used to produce a sphere. cli_bresenham.cpp is my primary file containing this problem code. getopt.h and getopt-long.c are files my instructor included with this assignment; don't mess with them.

All 4 Replies

Bresenhamn's optimized algorithm initializes deltax, deltay and error AFTER swappings. Your program initializes them BEFORE swappings.
Why?..

I moved the appropriate declarations after checking steep and swapping x and y, but the image is still far wrong.

``````[b]My rasterizeLine Version 2[/b]

/*
RASTERIZELINE
Rasterize lines and call Pixel to display them.
*/

//MY BRESENHAM VERSION: This is my version of Bresenham's algorithm which doesn't entirely work.
void rasterizeLine( Image &I, int x0, int y0, int x1, int y1 )
{
int dx = x1-x0;
int dy = y1-y0;
int slope = dy/dx;
//int d = 2*(y0-y1)*(1+x0)+(x1-x0)*(2*y0+1)+(2*x0*y1)-(2*x1*y0);	//from the Tiger book, p60
//int D = 2*(y1-y0) - (x1-x0);
bool steep = (ABS(dy) > ABS(dx));		//higher rise than run?
//int x = x0;								//
//int y = y0;								//
//int ystep;								//line moves up or down
int xhold, yhold;						//for swapping

//	cout << "\nPRE-STEEP TEST\n";

//not slanting down right
if (steep)
{	//swap x values
//		cout << "\nSTEEP: swapping x and y values\n";

xhold=x0;
x0=x1;
x1=xhold;

//swap y values
yhold=y0;
y0=y1;
y1=yhold;
}

//right to left
if(x0 > x1)
{
//		cout << "\nRIGHT TO LEFT: swapping x and y values to draw left to right\n";

xhold=x0;
x0=x1;
x1=xhold;

//swap y values
yhold=y0;
y0=y1;
y1=yhold;
}

int delta_x = x1 - x0;					//
int delta_y = ABS(y1-y0);				//
int error = delta_x/2;
int x = x0;								//
int y = y0;								//
int ystep;								//line moves up or down

//line moves up to down - check midpoint
if(y0 < y1)
{
//		cout << "\nYSTEP IS POSITIVE\n";
ystep=1;
}

//line moves down to up - check midpoint
else
{
//		"\nYSTEP IS NEGATIVE\n";
ystep=-1;
}

for(x; x < x1; x++)
{
//x0 and y0 swapped with x1 and y1
if(steep)
{
//			"\nSTEEP PIXELIZATION\n";
I(y, x) = Pixel(255, 255, 255);
//I(x, y) = Pixel(255, 255, 255);
}

//no swapping
else
{
//			"\nPIXELIZATION, NOT STEEP\n";
I(x, y) = Pixel(255, 255, 255);
}

error = error - delta_y;

if(error < 0)
{
y = y + ystep;
error += delta_x;
}
}
}``````

Must be

``for(x; x <= x1; x++) // not < !!!``

That's why broken lines...

With your suggestion and other tweaks, I got it to work! I noticed I didn't properly swap (x0 and y0) and (x1 and y1) the first time around. I tried swapping (x0 and x1) and (y0 and y1) both times to produce ickiness.

I changed imagex to this which allowed it to work.

``````int imagex(int resolution, float xcoord) //coord is x0 or x1
{
int hn = resolution/2; //half resolution (half n)

if(xcoord >= 0) //quad 1 or 4 - at least half n
{
return(rti((hn) + (xcoord*hn)));
}