Drawing a Demi-Death Star: Questions About Bresenham's Line Algorithm in C++

[Congartis]

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)));
	}

	else //quad 2 or 3
	{
		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))));
	}

	else //quad 1 or 2
	{
		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.

[ArkM]

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

[Congartis]

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;
		}
	}	
}

[ArkM]

Must be

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

That's why broken lines...

[Congartis]

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)));
	}

	else //quad 2 or 3
	{
		return(rti((hn) - (ABS(xcoord*hn))));
	}
}