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

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

Join Date: Aug 2008
Posts: 3
Reputation: Congartis is an unknown quantity at this point 
Solved Threads: 0
Congartis Congartis is offline Offline
Newbie Poster

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

 
0
  #1
Sep 10th, 2008
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.
My Line Rasterization Function
/*
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.
void rasterizeLine( Image &I, int x0, int y0, int x1, int y1 )
{
	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.
My Instructor's Line Rasterization Function

void rasterizeLine( Image &I, int x0, int y0, int x1, int y1 )
{
  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.)
Float to Integer Mapping
/*
IMAGEX
	Convert to image space's x coordinate
*/
int imagex(int resolution, float xcoord) //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
*/
int imagey(int resolution, float ycoord) //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.
*/
int rti(float floater)
{
	if(floater >= 0.0)
	{
		return static_cast<int> (floater+0.5);
	}

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

int main(int argc, char *argv[]) //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.
Attached Files
File Type: txt data.txt (33.2 KB, 5 views)
File Type: cpp cli_bresenham.cpp (10.9 KB, 4 views)
File Type: h getopt.h (3.5 KB, 3 views)
File Type: c getopt-long.c (17.6 KB, 3 views)
Reply With Quote Quick reply to this message  
Join Date: Jul 2008
Posts: 2,001
Reputation: ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of 
Solved Threads: 343
ArkM's Avatar
ArkM ArkM is offline Offline
Postaholic

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

 
0
  #2
Sep 11th, 2008
Bresenhamn's optimized algorithm initializes deltax, deltay and error AFTER swappings. Your program initializes them BEFORE swappings.
Why?..
Reply With Quote Quick reply to this message  
Join Date: Aug 2008
Posts: 3
Reputation: Congartis is an unknown quantity at this point 
Solved Threads: 0
Congartis Congartis is offline Offline
Newbie Poster

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

 
0
  #3
Sep 11th, 2008
I moved the appropriate declarations after checking steep and swapping x and y, but the image is still far wrong.

My rasterizeLine Version 2

/*
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;
		}
	}	
}
Reply With Quote Quick reply to this message  
Join Date: Jul 2008
Posts: 2,001
Reputation: ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of 
Solved Threads: 343
ArkM's Avatar
ArkM ArkM is offline Offline
Postaholic

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

 
0
  #4
Sep 12th, 2008
Must be
  1. for(x; x <= x1; x++) // not < !!!
That's why broken lines...
Reply With Quote Quick reply to this message  
Join Date: Aug 2008
Posts: 3
Reputation: Congartis is an unknown quantity at this point 
Solved Threads: 0
Congartis Congartis is offline Offline
Newbie Poster

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

 
0
  #5
Sep 12th, 2008
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.
  1. int imagex(int resolution, float xcoord) //coord is x0 or x1
  2. {
  3. int hn = resolution/2; //half resolution (half n)
  4.  
  5. if(xcoord >= 0) //quad 1 or 4 - at least half n
  6. {
  7. return(rti((hn) + (xcoord*hn)));
  8. }
  9.  
  10. else //quad 2 or 3
  11. {
  12. return(rti((hn) - (ABS(xcoord*hn))));
  13. }
  14. }
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:



Other Threads in the C++ Forum
Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC