Public Group

# Bresenhams Algorithm

This topic is 4825 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 :)

##### Share on other sites
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

##### Share on other sites
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]

##### Share on other sites
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 :)

##### Share on other sites
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[color].peRed   = rand()%256;    palette[color].peGreen = rand()%256;    palette[color].peBlue  = rand()%256;    // set flags field to PC_NOCOLLAPSE    palette[color].peFlags = PC_NOCOLLAPSE;    } // end for color// now fill in entry 0 and 255 with black and whitepalette[0].peRed     = 0;palette[0].peGreen   = 0;palette[0].peBlue    = 0;palette[0].peFlags   = PC_NOCOLLAPSE;palette[255].peRed   = 255;palette[255].peGreen = 255;palette[255].peBlue  = 255;palette[255].peFlags = PC_NOCOLLAPSE;// create the palette objectif (FAILED(lpdd->CreatePalette(DDPCAPS_8BIT | DDPCAPS_ALLOW256 |                                 DDPCAPS_INITIALIZE,                                 palette,&lpddpal, NULL)))return(0);// finally attach the palette to the primary surfaceif (FAILED(lpddsprimary->SetPalette(lpddpal)))   return(0);// clear the primary surface offDDraw_Fill_Surface(lpddsprimary, 0 );// return success or failure or your own return code herereturn(1);} // end Game_Init/////////////////////////////////////////////////////////////int Game_Shutdown(void *parms = NULL, int num_parms = 0){// this is called after the game is exited and the main event// loop while is exited, do all you cleanup and shutdown here// first the paletteif (lpddpal)   {   lpddpal->Release();   lpddpal = NULL;   } // end if// now the primary surfaceif (lpddsprimary)   {   lpddsprimary->Release();   lpddsprimary = NULL;   } // end if// now blow away the IDirectDraw4 interfaceif (lpdd)   {   lpdd->Release();   lpdd = NULL;   } // end if// return success or failure or your own return code herereturn(1);} // end Game_Shutdown// WINMAIN ////////////////////////////////////////////////int WINAPI WinMain(	HINSTANCE hinstance,					HINSTANCE hprevinstance,					LPSTR lpcmdline,					int ncmdshow){WNDCLASSEX winclass; // this will hold the class we createHWND	   hwnd;	 // generic window handleMSG		   msg;		 // generic messageHDC        hdc;      // graphics device context// first fill in the window class stucturewinclass.cbSize         = sizeof(WNDCLASSEX);winclass.style			= CS_DBLCLKS | CS_OWNDC |                           CS_HREDRAW | CS_VREDRAW;winclass.lpfnWndProc	= WindowProc;winclass.cbClsExtra		= 0;winclass.cbWndExtra		= 0;winclass.hInstance		= hinstance;winclass.hIcon			= LoadIcon(NULL, IDI_APPLICATION);winclass.hCursor		= LoadCursor(NULL, IDC_ARROW); winclass.hbrBackground	= (HBRUSH)GetStockObject(BLACK_BRUSH);winclass.lpszMenuName	= NULL;winclass.lpszClassName	= WINDOW_CLASS_NAME;winclass.hIconSm        = LoadIcon(NULL, IDI_APPLICATION);// save hinstance in globalhinstance_app = hinstance;// register the window classif (!RegisterClassEx(&winclass))	return(0);// create the windowif (!(hwnd = CreateWindowEx(NULL,                  // extended style                            WINDOW_CLASS_NAME,     // class						    "DirectDraw 8-Bit Line Drawing Demo", // title						    WS_POPUP | WS_VISIBLE,					 	    0,0,	  // initial x,y						    SCREEN_WIDTH,SCREEN_HEIGHT,  // initial width, height						    NULL,	  // handle to parent 						    NULL,	  // handle to menu						    hinstance,// instance of this application						    NULL)))	// extra creation parmsreturn(0);// save main window handlemain_window_handle = hwnd;// initialize game hereGame_Init();// enter main event loopwhile(TRUE)	{    // test if there is a message in queue, if so get it	if (PeekMessage(&msg,NULL,0,0,PM_REMOVE))	   { 	   // test if this is a quit       if (msg.message == WM_QUIT)           break;		   // translate any accelerator keys	   TranslateMessage(&msg);	   // send the message to the window proc	   DispatchMessage(&msg);	   } // end if           // main game processing goes here       Game_Main();       	} // end while// closedown game hereGame_Shutdown();// return to Windows like thisreturn(msg.wParam);} // end WinMain///////////////////////////////////////////////////////////

I am really getting pathetic at this , its been around 2 days since i am trying to figure this out ......HELLLPP!!!

##### Share on other sites
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 :\

1. 1
2. 2
3. 3
Rutin
18
4. 4
5. 5
JoeJ
13

• 14
• 10
• 25
• 9
• 57
• ### Forum Statistics

• Total Topics
632642
• Total Posts
3007620
• ### Who's Online (See full list)

There are no registered users currently online

×