| | |
Drawing a Demi-Death Star: Questions About Bresenham's Line Algorithm in C++
Please support our C++ advertiser: Intel Parallel Studio Home
![]() |
•
•
Join Date: Aug 2008
Posts: 3
Reputation:
Solved Threads: 0
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 code's resulting image
My instructor has a working version of rasterizeLine for all slopes, but this uses floats.
My instructor's code's resulting image. (The color difference is OK.) 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.
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 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 } }
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> }
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.
Re: Drawing a Demi-Death Star: Questions About Bresenham's Line Algorithm in C++
0
#2 Sep 11th, 2008
•
•
Join Date: Aug 2008
Posts: 3
Reputation:
Solved Threads: 0
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;
}
}
}Re: Drawing a Demi-Death Star: Questions About Bresenham's Line Algorithm in C++
0
#4 Sep 12th, 2008
Must be
That's why broken lines...
C++ Syntax (Toggle Plain Text)
for(x; x <= x1; x++) // not < !!!
•
•
Join Date: Aug 2008
Posts: 3
Reputation:
Solved Threads: 0
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.
I changed imagex to this which allowed it to work.
C++ Syntax (Toggle Plain Text)
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)))); } }
![]() |
Other Threads in the C++ Forum
- Previous Thread: Moore's Law Problem
- Next Thread: Template functions conditional compilation
| Thread Tools | Search this Thread |
api array arrays based beginner binary bitmap c++ c/c++ calculator char class classes code compile compiler console conversion count delete deploy desktop directshow dll download dynamic dynamiccharacterarray encryption error file forms fstream function functions game getline givemetehcodez google graph gui homeworkhelp homeworkhelper iamthwee ifstream input int integer java lib linkedlist linker linux list loop looping loops map math matrix memory news node output parameter pointer problem program programming project proxy python read recursion recursive reference return rpg string strings struct temperature template templates test text text-file tree unix url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets






