Bresenhams Algorithm

Started by
4 comments, last by Nokturnal 18 years, 9 months ago
Hey guys , i ve translated the bresenham algorithm which i had read from the following text. http://gamedev.cs.colorado.edu/tutorials/Bresenham.pdf


int DrawMyLine(int x0, int y0, // starting position 
              int x1, int y1, // ending position
              UCHAR color,    // color index
              UCHAR *vb_start, int lpitch) // video buffer and memory pitch

{

//x1>x0

int dx,dy,dx2,dy2,x_inc,y_inc,slope,error;

dx=x1-x0;
dy=y1-y0;


error=2*dy-dx;
slope=dy/dx;
y_inc=lpitch+slope;
x_inc=1;
int e_move=2*dy;
int ne_move=2*(dy-dx);

vb_start=vb_start+x0+y0*lpitch;


for(int x=x0;x<=x1;x++)
{	
	*vb_start=color;
	if(error<=0)
	{
	vb_start+=x_inc;
	error+=e_move;
	}
	else
	{
	vb_start+=x_inc;
	vb_start+=y_inc;
	error+=ne_move;	
	}
}

return 0;
}



now the only slight problem i m facing is , the increment for Y , which the text suggests should be 1 , the algorithm dosen't perform well with it , and ends up drawing a blunder.When i take it up logically , the y co-ordinate must increase by the slope , instead of 1 ,per x co-orinate , there must be something i am missing out. (i guess error handling is only what makes this algo differ from mid-point algorithm - which if i am not wrong is just increasing y per x )Though the program works well with the slope , but it adds a division , ok so i dont want to be Mr.Optimization but is there any other way around this ?? (This small section i ve written which is for the first quadrant only , i guess some small changes and this can be incorporated in the others too :)
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
Advertisement
basically, y_delta is only 1 if the line changes more in the y direction than in the x direction. Otherwise it is the x_delta that will be 1. (i.e. you always step by 1 in the longest dimension, while the shorter dimension is only incremented sometimes, based on the "(error < 0)" criterion)

here are some other articles here on gamedev:

article 1
article 2
If I'm reading the code correctly, you have code for the case where the slope is less than or equal to 1.

Here's how I solved it for that case:

for 0 .. dx - 1
draw a pixel at x0, y0

if the error is greater than or equal to 0
then, increment y0 by the y increment and the error becomes error minux 2*dx

increment x0 by the x increment
error becomes error plus 2 * dy
end for

The if statement in the loop check the error. This influences whether the next point should be (xi+1, yi) or (xi+1, yi+1). (note: read the i's as subscripts). This is what lonesock was talking about.

Hope this helps.

[Edited by - arcadion on July 9, 2005 3:39:51 PM]
thanks for the reply's , sorry i forgot to mention , as i was just starting out i constrained my self from passing values which would mess it up.[ie dx << dy ] , i 'll check those articles :)
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
Man , this is really getting to me :'(

This is what the second articel suggests for drawing lines with a bresenham algorithm.

PutPixel(x, y);  { Draw a pixel at the current point }if d < 0 then    d := d + (2 * deltay)else  begin    d := d + 2 * (deltay - deltax);    y := y + 1;  end;x := x + 1;



which is pretty much what i am doing , i guess there is some fault in this line
y_inc=lpitch+1;

right now i am only passing co-ordinates which the program can handle , eg 0,0,320,240.

now when i pass the above set of co-ordinates , i get the perfect result , provided my y_increment is
y_inc=lpitch+slope;

but , if i change the y_inc according to the algorithm , ie
y_inc=lpitch+1;

the line being drawn is not proper.

arcadion , could you please elaborate on the error handling part , as i am completely aware why we are adding 2*dx and 2*(dy-dx) in this case , but i am unable to reach a conclusion why what you suggest is done.I do have a book which suggests exactly what you say but , it dosent carry any information on the subject.

Here's the entire code , those who are too lazy to type :P

#define WIN32_LEAN_AND_MEAN  #define INITGUID#include <windows.h>   #include <windowsx.h> #include <mmsystem.h>#include <iostream.h> #include <conio.h>#include <stdlib.h>#include <malloc.h>#include <memory.h>#include <string.h>#include <stdarg.h>#include <stdio.h> #include <math.h>#include <io.h>#include <fcntl.h>#include <ddraw.h> // include directdraw// DEFINES ////////////////////////////////////////////////// defines for windows #define WINDOW_CLASS_NAME "WINCLASS1"// default screen size#define SCREEN_WIDTH    640  // size of screen#define SCREEN_HEIGHT   480#define SCREEN_BPP      8    // bits per pixel#define BITMAP_ID            0x4D42 // universal id for a bitmap#define MAX_COLORS_PALETTE   256// TYPES //////////////////////////////////////////////////////// basic unsigned typestypedef unsigned short USHORT;typedef unsigned short WORD;typedef unsigned char  UCHAR;typedef unsigned char  BYTE;// PROTOTYPES  //////////////////////////////////////////////int DDraw_Fill_Surface(LPDIRECTDRAWSURFACE7 lpdds,int color);int Draw_Line(int x0, int y0, int x1, int y1, UCHAR color, UCHAR *vb_start, int lpitch);// MACROS /////////////////////////////////////////////////// tests if a key is up or down#define KEYDOWN(vk_code) ((GetAsyncKeyState(vk_code) & 0x8000) ? 1 : 0)#define KEYUP(vk_code)   ((GetAsyncKeyState(vk_code) & 0x8000) ? 0 : 1)// initializes a direct draw struct#define DDRAW_INIT_STRUCT(ddstruct) { memset(&ddstruct,0,sizeof(ddstruct)); ddstruct.dwSize=sizeof(ddstruct); }// GLOBALS ////////////////////////////////////////////////HWND      main_window_handle = NULL; // globally track main windowint       window_closed      = 0;    // tracks if window is closedHINSTANCE hinstance_app      = NULL; // globally track hinstance// directdraw stuffLPDIRECTDRAW7         lpdd         = NULL;   // dd objectLPDIRECTDRAWSURFACE7  lpddsprimary = NULL;   // dd primary surfaceLPDIRECTDRAWSURFACE7  lpddsback    = NULL;   // dd back surfaceLPDIRECTDRAWPALETTE   lpddpal      = NULL;   // a pointer to the created dd paletteLPDIRECTDRAWCLIPPER   lpddclipper  = NULL;   // dd clipperPALETTEENTRY          palette[256];          // color palettePALETTEENTRY          save_palette[256];     // used to save palettesDDSURFACEDESC2        ddsd;                  // a direct draw surface description structDDBLTFX               ddbltfx;               // used to fillDDSCAPS2              ddscaps;               // a direct draw surface capabilities structHRESULT               ddrval;                // result back from dd callsDWORD                 start_clock_count = 0; // used for timingchar buffer[80];                             // general printing buffer// FUNCTIONS ////////////////////////////////////////////////inline int Draw_Pixel(int x, int y,int color,               UCHAR *video_buffer, int lpitch){// this function plots a single pixel at x,y with colorvideo_buffer[x + y*lpitch] = color;// return successreturn(1);} // end Draw_Pixel/////////////////////////////////////////////////////////////int DDraw_Fill_Surface(LPDIRECTDRAWSURFACE7 lpdds,int color){DDBLTFX ddbltfx; // this contains the DDBLTFX structure// clear out the structure and set the size field DDRAW_INIT_STRUCT(ddbltfx);// set the dwfillcolor field to the desired colorddbltfx.dwFillColor = color; // ready to blt to surfacelpdds->Blt(NULL,       // ptr to dest rectangle           NULL,       // ptr to source surface, NA                       NULL,       // ptr to source rectangle, NA           DDBLT_COLORFILL | DDBLT_WAIT,   // fill and wait                              &ddbltfx);  // ptr to DDBLTFX structure// return successreturn(1);} // end DDraw_Fill_Surface///////////////////////////////////////////////////////////////int Draw_Line(int x0, int y0, // starting position               int x1, int y1, // ending position              UCHAR color,    // color index              UCHAR *vb_start, int lpitch) // video buffer and memory pitch{// this function draws a line from xo,yo to x1,y1 using differential error// terms (based on Bresenahams work)int dx,             // difference in x's    dy,             // difference in y's    dx2,            // dx,dy * 2    dy2,     x_inc,          // amount in pixel space to move during drawing    y_inc,          // amount in pixel space to move during drawing    error,          // the discriminant i.e. error i.e. decision variable    index;          // used for looping// pre-compute first pixel address in video buffervb_start = vb_start + x0 + y0*lpitch;// compute horizontal and vertical deltasdx = x1-x0;dy = y1-y0;// test which direction the line is going in i.e. slope angleif (dx>=0)   {   x_inc = 1;   } // end if line is moving rightelse   {   x_inc = -1;   dx    = -dx;  // need absolute value   } // end else moving left// test y component of slopeif (dy>=0)   {   y_inc = lpitch;   } // end if line is moving downelse   {   y_inc = -lpitch;   dy    = -dy;  // need absolute value   } // end else moving up// compute (dx,dy) * 2dx2 = dx << 1;dy2 = dy << 1;// now based on which delta is greater we can draw the lineif (dx > dy)   {   // initialize error term   error = dy2 - dx;    // draw the line   for (index=0; index <= dx; index++)       {       // set the pixel       *vb_start = color;       // test if error has overflowed       if (error >= 0)           {          error-=dx2;          // move to next line          vb_start+=y_inc;	   } // end if error overflowed       // adjust the error term       error+=dy2;       // move to the next pixel       vb_start+=x_inc;       } // end for   } // end if |slope| <= 1else   {   // initialize error term   error = dx2 - dy;    // draw the line   for (index=0; index <= dy; index++)       {       // set the pixel       *vb_start = color;       // test if error overflowed       if (error >= 0)          {          error-=dy2;          // move to next line          vb_start+=x_inc;          } // end if error overflowed       // adjust the error term       error+=dx2;       // move to the next pixel       vb_start+=y_inc;       } // end for   } // end else |slope| > 1// return successreturn(1);} // end Draw_Line///////////////////////////////////////////////////////////////int Draw_Text_GDI(char *text, int x,int y,                  COLORREF color, LPDIRECTDRAWSURFACE7 lpdds){// this function draws the sent text on the sent surface // using color index as the color in the paletteHDC xdc; // the working dc// get the dc from surfaceif (FAILED(lpdds->GetDC(&xdc)))   return(0);// set the colors for the text upSetTextColor(xdc,color);// set background mode to transparent so black isn't copiedSetBkMode(xdc, TRANSPARENT);// draw the text aTextOut(xdc,x,y,text,strlen(text));// release the dclpdds->ReleaseDC(xdc);// return successreturn(1);} // end Draw_Text_GDIint DrawMyLine(int x0, int y0, // starting position               int x1, int y1, // ending position              UCHAR color,    // color index              UCHAR *vb_start, int lpitch) // video buffer and memory pitch{//x1>x0int dx,dy,dx2,dy2,x_inc,y_inc,slope,error;dx=x1-x0;dy=y1-y0;error=2*dy-dx;slope=dy/dx;y_inc=lpitch+1;x_inc=1;int e_move=2*dy;int ne_move=2*dy-2*dx;vb_start=vb_start+x0+y0*lpitch;int y=0;for(int x=x0;x<=x1-1;x++){		*vb_start=color;	vb_start+=x_inc;	if(error<0)	{	error+=e_move;		}	else	{	vb_start+=y_inc;	error+=ne_move;		y+=1;	}}sprintf(buffer,"Value of x = %d  y=%d",x,y);Draw_Text_GDI(buffer,0,0,255,lpddsprimary);return 0;}LRESULT CALLBACK WindowProc(HWND hwnd, 						    UINT msg,                             WPARAM wparam,                             LPARAM lparam){// this is the main message handler of the systemPAINTSTRUCT		ps;		// used in WM_PAINTHDC				hdc;	// handle to a device contextchar buffer[80];        // used to print strings// what is the message switch(msg)	{		case WM_CREATE:         {		// do initialization stuff here        // return success		return(0);		} break;   	case WM_PAINT: 		{		// simply validate the window    	    hdc = BeginPaint(hwnd,&ps);	                 // end painting        EndPaint(hwnd,&ps);        // return success		return(0);   		} break;	case WM_DESTROY: 		{		// kill the application, this sends a WM_QUIT message 		PostQuitMessage(0);        // return success		return(0);		} break;	default:break;    } // end switch// process any messages that we didn't take care of return (DefWindowProc(hwnd, msg, wparam, lparam));} // end WinProc///////////////////////////////////////////////////////////int Game_Main(void *parms = NULL, int num_parms = 0){// this is the main loop of the game, do all your processing// here// make sure this isn't executed againif (window_closed)   return(0);// for now test if user is hitting ESC and send WM_CLOSEif (KEYDOWN(VK_ESCAPE))   {   PostMessage(main_window_handle,WM_CLOSE,0,0);   window_closed = 1;   } // end if// lock primary bufferDDRAW_INIT_STRUCT(ddsd);if (FAILED(lpddsprimary->Lock(NULL,&ddsd,                              DDLOCK_WAIT | DDLOCK_SURFACEMEMORYPTR,                              NULL)))return(0);/*// draw 1000 random linesfor (int index=0; index < 1000; index++)    {    Draw_Line(rand()%SCREEN_WIDTH, rand()%SCREEN_HEIGHT,              rand()%SCREEN_WIDTH, rand()%SCREEN_HEIGHT,              rand()%256,              (UCHAR *)ddsd.lpSurface, ddsd.lPitch);    } // end for index*/DrawMyLine(0,0,320,240,255,(UCHAR*)ddsd.lpSurface,ddsd.lPitch);//DrawMyLine(0,0,320,240,255,(UCHAR*)ddsd.lpSurface,ddsd.lPitch);// unlock primary bufferif (FAILED(lpddsprimary->Unlock(NULL)))   return(0);// wait a secSleep(33);// return success or failure or your own return code herereturn(1);} // end Game_Main////////////////////////////////////////////////////////////int Game_Init(void *parms = NULL, int num_parms = 0){// this is called once after the initial window is created and// before the main event loop is entered, do all your initialization// here// create IDirectDraw interface 7.0 object and test for errorif (FAILED(DirectDrawCreateEx(NULL, (void **)&lpdd, IID_IDirectDraw7, NULL)))   return(0);// set cooperation to full screenif (FAILED(lpdd->SetCooperativeLevel(main_window_handle,                                       DDSCL_FULLSCREEN | DDSCL_ALLOWMODEX |                                       DDSCL_EXCLUSIVE | DDSCL_ALLOWREBOOT)))   return(0);// set display mode to 640x480x8if (FAILED(lpdd->SetDisplayMode(SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_BPP,0,0)))   return(0);// clear ddsd and set sizeDDRAW_INIT_STRUCT(ddsd); // enable valid fieldsddsd.dwFlags = DDSD_CAPS;// request primary surfaceddsd.ddsCaps.dwCaps = DDSCAPS_PRIMARYSURFACE;// create the primary surfaceif (FAILED(lpdd->CreateSurface(&ddsd, &lpddsprimary, NULL)))   return(0);// build up the palette data arrayfor (int color=1; color < 255; color++)    {    // fill with random RGB values    palette.peRed   = rand()%<span class="cpp-number">256</span>;<br>    palette.peGreen = rand()%<span class="cpp-number">256</span>;<br>    palette.peBlue  = rand()%<span class="cpp-number">256</span>;<br><br>    <span class="cpp-comment">// set flags field to PC_NOCOLLAPSE</span><br>    palette.peFlags = PC_NOCOLLAPSE;<br>    } <span class="cpp-comment">// end for color</span><br><br><span class="cpp-comment">// now fill in entry 0 and 255 with black and white</span><br>palette[<span class="cpp-number">0</span>].peRed     = <span class="cpp-number">0</span>;<br>palette[<span class="cpp-number">0</span>].peGreen   = <span class="cpp-number">0</span>;<br>palette[<span class="cpp-number">0</span>].peBlue    = <span class="cpp-number">0</span>;<br>palette[<span class="cpp-number">0</span>].peFlags   = PC_NOCOLLAPSE;<br><br>palette[<span class="cpp-number">255</span>].peRed   = <span class="cpp-number">255</span>;<br>palette[<span class="cpp-number">255</span>].peGreen = <span class="cpp-number">255</span>;<br>palette[<span class="cpp-number">255</span>].peBlue  = <span class="cpp-number">255</span>;<br>palette[<span class="cpp-number">255</span>].peFlags = PC_NOCOLLAPSE;<br><br><span class="cpp-comment">// create the palette object</span><br><span class="cpp-keyword">if</span> (FAILED(lpdd-&gt;CreatePalette(DDPCAPS_8BIT | DDPCAPS_ALLOW256 | <br>                                DDPCAPS_INITIALIZE, <br>                                palette,&amp;lpddpal, NULL)))<br><span class="cpp-keyword">return</span>(<span class="cpp-number">0</span>);<br><br><span class="cpp-comment">// finally attach the palette to the primary surface</span><br><span class="cpp-keyword">if</span> (FAILED(lpddsprimary-&gt;SetPalette(lpddpal)))<br>   <span class="cpp-keyword">return</span>(<span class="cpp-number">0</span>);<br><br><span class="cpp-comment">// clear the primary surface off</span><br>DDraw_Fill_Surface(lpddsprimary, <span class="cpp-number">0</span> );<br><br><br><span class="cpp-comment">// return success or failure or your own return code here</span><br><span class="cpp-keyword">return</span>(<span class="cpp-number">1</span>);<br><br>} <span class="cpp-comment">// end Game_Init</span><br><br><span class="cpp-comment">/////////////////////////////////////////////////////////////</span><br><br><span class="cpp-keyword">int</span> Game_Shutdown(<span class="cpp-keyword">void</span> *parms = NULL, <span class="cpp-keyword">int</span> num_parms = <span class="cpp-number">0</span>)<br>{<br><span class="cpp-comment">// this is called after the game is exited and the main event</span><br><span class="cpp-comment">// loop while is exited, do all you cleanup and shutdown here</span><br><br><br><span class="cpp-comment">// first the palette</span><br><span class="cpp-keyword">if</span> (lpddpal)<br>   {<br>   lpddpal-&gt;Release();<br>   lpddpal = NULL;<br>   } <span class="cpp-comment">// end if</span><br><br><span class="cpp-comment">// now the primary surface</span><br><span class="cpp-keyword">if</span> (lpddsprimary)<br>   {<br>   lpddsprimary-&gt;Release();<br>   lpddsprimary = NULL;<br>   } <span class="cpp-comment">// end if</span><br><br><span class="cpp-comment">// now blow away the IDirectDraw4 interface</span><br><span class="cpp-keyword">if</span> (lpdd)<br>   {<br>   lpdd-&gt;Release();<br>   lpdd = NULL;<br>   } <span class="cpp-comment">// end if</span><br><br><span class="cpp-comment">// return success or failure or your own return code here</span><br><span class="cpp-keyword">return</span>(<span class="cpp-number">1</span>);<br><br>} <span class="cpp-comment">// end Game_Shutdown</span><br><br><span class="cpp-comment">// WINMAIN ////////////////////////////////////////////////</span><br><br><span class="cpp-keyword">int</span> WINAPI WinMain(	HINSTANCE hinstance,<br>					HINSTANCE hprevinstance,<br>					LPSTR lpcmdline,<br>					<span class="cpp-keyword">int</span> ncmdshow)<br>{<br><br>WNDCLASSEX winclass; <span class="cpp-comment">// this will hold the class we create</span><br>HWND	   hwnd;	 <span class="cpp-comment">// generic window handle</span><br>MSG		   msg;		 <span class="cpp-comment">// generic message</span><br>HDC        hdc;      <span class="cpp-comment">// graphics device context</span><br><br><span class="cpp-comment">// first fill in the window class stucture</span><br>winclass.cbSize         = <span class="cpp-keyword">sizeof</span>(WNDCLASSEX);<br>winclass.style			= CS_DBLCLKS | CS_OWNDC | <br>                          CS_HREDRAW | CS_VREDRAW;<br>winclass.lpfnWndProc	= WindowProc;<br>winclass.cbClsExtra		= <span class="cpp-number">0</span>;<br>winclass.cbWndExtra		= <span class="cpp-number">0</span>;<br>winclass.hInstance		= hinstance;<br>winclass.hIcon			= LoadIcon(NULL, IDI_APPLICATION);<br>winclass.hCursor		= LoadCursor(NULL, IDC_ARROW); <br>winclass.hbrBackground	= (HBRUSH)GetStockObject(BLACK_BRUSH);<br>winclass.lpszMenuName	= NULL;<br>winclass.lpszClassName	= WINDOW_CLASS_NAME;<br>winclass.hIconSm        = LoadIcon(NULL, IDI_APPLICATION);<br><br><span class="cpp-comment">// save hinstance in global</span><br>hinstance_app = hinstance;<br><br><span class="cpp-comment">// register the window class</span><br><span class="cpp-keyword">if</span> (!RegisterClassEx(&amp;winclass))<br>	<span class="cpp-keyword">return</span>(<span class="cpp-number">0</span>);<br><br><span class="cpp-comment">// create the window</span><br><span class="cpp-keyword">if</span> (!(hwnd = CreateWindowEx(NULL,                  <span class="cpp-comment">// extended style</span><br>                            WINDOW_CLASS_NAME,     <span class="cpp-comment">// class</span><br>						    <span class="cpp-literal">"DirectDraw 8-Bit Line Drawing Demo"</span>, <span class="cpp-comment">// title</span><br>						    WS_POPUP | WS_VISIBLE,<br>					 	    <span class="cpp-number">0</span>,<span class="cpp-number">0</span>,	  <span class="cpp-comment">// initial x,y</span><br>						    SCREEN_WIDTH,SCREEN_HEIGHT,  <span class="cpp-comment">// initial width, height</span><br>						    NULL,	  <span class="cpp-comment">// handle to parent </span><br>						    NULL,	  <span class="cpp-comment">// handle to menu</span><br>						    hinstance,<span class="cpp-comment">// instance of this application</span><br>						    NULL)))	<span class="cpp-comment">// extra creation parms</span><br><span class="cpp-keyword">return</span>(<span class="cpp-number">0</span>);<br><br><span class="cpp-comment">// save main window handle</span><br>main_window_handle = hwnd;<br><br><span class="cpp-comment">// initialize game here</span><br>Game_Init();<br><br><span class="cpp-comment">// enter main event loop</span><br><span class="cpp-keyword">while</span>(<span class="cpp-keyword">TRUE</span>)<br>	{<br>    <span class="cpp-comment">// test if there is a message in queue, if so get it</span><br>	<span class="cpp-keyword">if</span> (PeekMessage(&amp;msg,NULL,<span class="cpp-number">0</span>,<span class="cpp-number">0</span>,PM_REMOVE))<br>	   { <br>	   <span class="cpp-comment">// test if this is a quit</span><br>       <span class="cpp-keyword">if</span> (msg.message == WM_QUIT)<br>           <span class="cpp-keyword">break</span>;<br>	<br>	   <span class="cpp-comment">// translate any accelerator keys</span><br>	   TranslateMessage(&amp;msg);<br><br>	   <span class="cpp-comment">// send the message to the window proc</span><br>	   DispatchMessage(&amp;msg);<br>	   } <span class="cpp-comment">// end if</span><br>    <br>       <span class="cpp-comment">// main game processing goes here</span><br>       Game_Main();<br>       <br>	} <span class="cpp-comment">// end while</span><br><br><span class="cpp-comment">// closedown game here</span><br>Game_Shutdown();<br><br><span class="cpp-comment">// return to Windows like this</span><br><span class="cpp-keyword">return</span>(msg.wParam);<br><br>} <span class="cpp-comment">// end WinMain</span><br><br><span class="cpp-comment">///////////////////////////////////////////////////////////</span><br><br><br><br><br></pre></div><!–ENDSCRIPT–><br><br><br><br>I am really getting pathetic at this , its been around 2 days since i am trying to figure this out ……HELLLPP!!!
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
I hate to make this a blog kind of thing , but since there were over 100 views & no solution , i finally figured out what was wrong, so here it goes :)

in the line y_inc=lpitch+1 , i was stepping in the y direction by 1 more , as x was being incremented at every iteration , thus i needed to plot the pixel at (x+1,y) or (x+1,y+1) , what y_inc=lpitch+1 did was plot the pixel at (x+1,y+2) as a result a whole mess :D

but heck it was 4 am when i was trying to debug it :\
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943

This topic is closed to new replies.

Advertisement