Sign in to follow this  
Nokturnal

Bresenhams Algorithm

Recommended Posts

Hey guys , i ve translated the bresenham algorithm which i had read from the following text. [url]http://gamedev.cs.colorado.edu/tutorials/Bresenham.pdf[/url]

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 types
typedef 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 window
int window_closed = 0; // tracks if window is closed
HINSTANCE hinstance_app = NULL; // globally track hinstance

// directdraw stuff
LPDIRECTDRAW7 lpdd = NULL; // dd object
LPDIRECTDRAWSURFACE7 lpddsprimary = NULL; // dd primary surface
LPDIRECTDRAWSURFACE7 lpddsback = NULL; // dd back surface
LPDIRECTDRAWPALETTE lpddpal = NULL; // a pointer to the created dd palette
LPDIRECTDRAWCLIPPER lpddclipper = NULL; // dd clipper
PALETTEENTRY palette[256]; // color palette
PALETTEENTRY save_palette[256]; // used to save palettes
DDSURFACEDESC2 ddsd; // a direct draw surface description struct
DDBLTFX ddbltfx; // used to fill
DDSCAPS2 ddscaps; // a direct draw surface capabilities struct
HRESULT ddrval; // result back from dd calls
DWORD start_clock_count = 0; // used for timing


char 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 color

video_buffer[x + y*lpitch] = color;

// return success
return(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 color
ddbltfx.dwFillColor = color;

// ready to blt to surface
lpdds->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 success
return(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 buffer
vb_start = vb_start + x0 + y0*lpitch;

// compute horizontal and vertical deltas
dx = x1-x0;
dy = y1-y0;

// test which direction the line is going in i.e. slope angle
if (dx>=0)
{
x_inc = 1;

} // end if line is moving right
else
{
x_inc = -1;
dx = -dx; // need absolute value

} // end else moving left

// test y component of slope

if (dy>=0)
{
y_inc = lpitch;
} // end if line is moving down
else
{
y_inc = -lpitch;
dy = -dy; // need absolute value

} // end else moving up

// compute (dx,dy) * 2
dx2 = dx << 1;
dy2 = dy << 1;

// now based on which delta is greater we can draw the line
if (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| <= 1
else
{
// 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 success
return(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 palette

HDC xdc; // the working dc

// get the dc from surface
if (FAILED(lpdds->GetDC(&xdc)))
return(0);

// set the colors for the text up
SetTextColor(xdc,color);

// set background mode to transparent so black isn't copied
SetBkMode(xdc, TRANSPARENT);

// draw the text a
TextOut(xdc,x,y,text,strlen(text));

// release the dc
lpdds->ReleaseDC(xdc);

// return success
return(1);
} // end Draw_Text_GDI




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+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 system
PAINTSTRUCT ps; // used in WM_PAINT
HDC hdc; // handle to a device context
char 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 again
if (window_closed)
return(0);

// for now test if user is hitting ESC and send WM_CLOSE
if (KEYDOWN(VK_ESCAPE))
{
PostMessage(main_window_handle,WM_CLOSE,0,0);
window_closed = 1;
} // end if


// lock primary buffer
DDRAW_INIT_STRUCT(ddsd);

if (FAILED(lpddsprimary->Lock(NULL,&ddsd,
DDLOCK_WAIT | DDLOCK_SURFACEMEMORYPTR,
NULL)))
return(0);
/*
// draw 1000 random lines
for (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 buffer
if (FAILED(lpddsprimary->Unlock(NULL)))
return(0);

// wait a sec
Sleep(33);

// return success or failure or your own return code here
return(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 error
if (FAILED(DirectDrawCreateEx(NULL, (void **)&lpdd, IID_IDirectDraw7, NULL)))
return(0);

// set cooperation to full screen
if (FAILED(lpdd->SetCooperativeLevel(main_window_handle,
DDSCL_FULLSCREEN | DDSCL_ALLOWMODEX |
DDSCL_EXCLUSIVE | DDSCL_ALLOWREBOOT)))
return(0);

// set display mode to 640x480x8
if (FAILED(lpdd->SetDisplayMode(SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_BPP,0,0)))
return(0);

// clear ddsd and set size
DDRAW_INIT_STRUCT(ddsd);

// enable valid fields
ddsd.dwFlags = DDSD_CAPS;

// request primary surface
ddsd.ddsCaps.dwCaps = DDSCAPS_PRIMARYSURFACE;

// create the primary surface
if (FAILED(lpdd->CreateSurface(&ddsd, &lpddsprimary, NULL)))
return(0);

// build up the palette data array
for (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 white
palette[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 object
if (FAILED(lpdd->CreatePalette(DDPCAPS_8BIT | DDPCAPS_ALLOW256 |
DDPCAPS_INITIALIZE,
palette,&lpddpal, NULL)))
return(0);

// finally attach the palette to the primary surface
if (FAILED(lpddsprimary->SetPalette(lpddpal)))
return(0);

// clear the primary surface off
DDraw_Fill_Surface(lpddsprimary, 0 );


// return success or failure or your own return code here
return(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 palette
if (lpddpal)
{
lpddpal->Release();
lpddpal = NULL;
} // end if

// now the primary surface
if (lpddsprimary)
{
lpddsprimary->Release();
lpddsprimary = NULL;
} // end if

// now blow away the IDirectDraw4 interface
if (lpdd)
{
lpdd->Release();
lpdd = NULL;
} // end if

// return success or failure or your own return code here
return(1);

} // end Game_Shutdown

// WINMAIN ////////////////////////////////////////////////

int WINAPI WinMain( HINSTANCE hinstance,
HINSTANCE hprevinstance,
LPSTR lpcmdline,
int ncmdshow)
{

WNDCLASSEX winclass; // this will hold the class we create
HWND hwnd; // generic window handle
MSG msg; // generic message
HDC hdc; // graphics device context

// first fill in the window class stucture
winclass.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 global
hinstance_app = hinstance;

// register the window class
if (!RegisterClassEx(&winclass))
return(0);

// create the window
if (!(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 parms
return(0);

// save main window handle
main_window_handle = hwnd;

// initialize game here
Game_Init();

// enter main event loop
while(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 here
Game_Shutdown();

// return to Windows like this
return(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 this post


Link to post
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 :\

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this