Friday, January 20, 2012

Drawing Straight Line using DDA Algorithm in C/C++

The digital differentia analyzer (DDA) is a scan-conversion line algorithm. In this algorithm, we sample the line at unit intervals in one coordinate and determine corresponding integer values nearest the line path of the other coordinate and plot those coordinate (pixel) in computer screen. Consider first a line with positive slope. If the slope is less than or equal to 1, we sample at unit x intervals (dx = 1) and computer each successive y value as y(k+1) = y(k) + m. Subscript k takes integer values starting from 1, for the first point, and increases by 1 until the final endpoint is reached. For lines with a positive slope greater than 1, we reverse the roles of x and y.That is, we sample at unit y intervals (dy = 1) and calculate each succeeding x value as x(k+1) = x(k) + (1/m)

The following section implements DDA Algorithm in C/C++. The source code is complied using gcc Compiler and Code::Blocks IDE. To print a pixel, SetPixel() function of windows.h is used.

Note

To run this code in your machine with Code::blocks IDE, add a link library libgdi32.a (it is usually inside MinGW\lib )  in linker setting and make the file extension .cpp but not .c. For C user, here is a link to download C file of this tutorial. Download


#include <windows.h>
#include <cmath>
#define ROUND(a) ((int) (a + 0.5))
/* set window handle */
static HWND sHwnd;
static COLORREF redColor=RGB(255,0,0);
static COLORREF blueColor=RGB(0,0,255);
static COLORREF greenColor=RGB(0,255,0);
void SetWindowHandle(HWND hwnd){
sHwnd=hwnd;
}
/* SetPixel */
void setPixel(int x,int y,COLORREF& color=redColor){
if(sHwnd==NULL){
MessageBox(NULL,"sHwnd was not initialized !","Error",MB_OK|MB_ICONERROR);
exit(0);
}
HDC hdc=GetDC(sHwnd);
SetPixel(hdc,x,y,color);
ReleaseDC(sHwnd,hdc);
return;
// NEVERREACH //
}
void drawLineDDA(int xa, int ya, int xb, int yb){
int dx = xb - xa, dy = yb - ya, steps, k;
float xIncrement, yIncrement, x = xa, y = ya;
if(abs(dx) > abs(dy)) steps = abs(dx);
else steps = abs(dy);
xIncrement = dx / (float) steps;
yIncrement = dy / (float) steps;
setPixel(ROUND(x), ROUND(y));
for(int k = 0; k < steps; k++){
x += xIncrement;
y += yIncrement;
setPixel(x, y);
}
}
/* Window Procedure WndProc */
LRESULT CALLBACK WndProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam){
switch(message){
case WM_PAINT:
SetWindowHandle(hwnd);
drawLineDDA(10, 20, 250, 300);
break;
case WM_CLOSE: // FAIL THROUGH to call DefWindowProc
break;
case WM_DESTROY:
PostQuitMessage(0);
return 0;
default:
break; // FAIL to call DefWindowProc //
}
return DefWindowProc(hwnd,message,wParam,lParam);
}
int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,LPSTR lpCmdLine,int iCmdShow){
static TCHAR szAppName[] = TEXT("Straight Line");
WNDCLASS wndclass;
wndclass.style         = CS_HREDRAW|CS_VREDRAW ;
wndclass.lpfnWndProc   = WndProc ;
wndclass.cbClsExtra    = 0 ;
wndclass.cbWndExtra    = 0 ;
wndclass.hInstance     = hInstance ;
wndclass.hIcon         = LoadIcon (NULL, IDI_APPLICATION) ;
wndclass.hCursor       = LoadCursor (NULL, IDC_ARROW) ;
wndclass.hbrBackground = (HBRUSH) GetStockObject (WHITE_BRUSH) ;
wndclass.lpszMenuName  = NULL ;
wndclass.lpszClassName = szAppName ;
// Register the window //
if(!RegisterClass(&wndclass)){
MessageBox(NULL,"Registering the class failled","Error",MB_OK|MB_ICONERROR);
exit(0);
}
// CreateWindow //
HWND hwnd=CreateWindow(szAppName,"DDA - Programming Techniques",
WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT,
CW_USEDEFAULT,
CW_USEDEFAULT,
CW_USEDEFAULT,
NULL,
NULL,
hInstance,
NULL);
if(!hwnd){
MessageBox(NULL,"Window Creation Failed!","Error",MB_OK);
exit(0);
}
// ShowWindow and UpdateWindow //
ShowWindow(hwnd,iCmdShow);
UpdateWindow(hwnd);
// Message Loop //
MSG msg;
while(GetMessage(&msg,NULL,0,0)){
TranslateMessage(&msg);
DispatchMessage(&msg);
}
/* return no error to the operating system */
return 0;
}

The output of this program is looks like

DDADDA algorithm is faster than the direct use of equation y = mx + c however, the rounding operations and floating-point arithmetic makes it still time consuming. To overcome this limitation of DDA Algorithm, Bresenham discovered Bresenham’s Line Drawing Algorithm.

9 comments:

  1. I tried to compile this using CodeBlocks 10.5, but failed to do so, can you give any hints on how to compile this? thanks for this great tutorials!

    ReplyDelete
  2. @Mi Blog de prueba, the problem can be solved by adding a link library libgdi32.a (it is usually inside MinGW\lib ) in linker setting. Hope this will remove your problem.

    ReplyDelete
  3. Hey Bibek123, I still can't get it running,"cmath: No such file or directory|"

    and cant seem to find the way to run the Setpixel method, can you give some kind of brief tutorial whenever you have some spare time? thank you so much for what you're doing.

    ReplyDelete
  4. cmath is for .cpp file, its c++ header file actually. If you use C then change it to math.h

    ReplyDelete
  5. I see what my problem was, I was trying to compile using C, not C++, now I finally got it running Bibek123

    You see, I'm taking this class called "Graphing" and the teacher wants us to generate this same Line using the DDA algorithm, but for some reason, she wants us to compile it using C,not c++, I asked her what library should I use to compile it on C, and she hasn't given me a straight answer (I don't think she even knows) so my question is, is there someway to run this same code but using C instead of C++? even possible to run it on CodeBlocks?

    thank you very much Bibek, that algorithm is amazing!

    ReplyDelete
  6. Yes there is a way so that you can run the same code in C but not in C++ with little modification. I have updated my article and included a link to download the C version of my code. Plz download the C version of the code and run it and I am 100% sure that this time you won't get any error.

    And thank u very very much for keeping interest in my blog article. If you have any problem in programming, then feel free to ask me.

    ReplyDelete
  7. Sir, I wanna thank you so much for this! I FINALLY GOT IT WORKING!! this is truly amazing!, you see, so far in my classroom no body has been able to compile this code successfully in code blocks, because we were having problems finding the right library and getting the set pixel method working, but with your code it runs like a charm, I wanna thank you for taking your time to write this amazing code, I'm definitely gonna advertise you around my mates, and thank you for providing your help in programming topics, I already have your blog on my favorites list, and gonna come very often cause I wanna learn more about programming in general, especially data structures, so thanks again and gonna tell my friends about how much your blog rocks!, thanks Bibek123! :)

    ReplyDelete
  8. Do you know how to convert this with C++?

    ReplyDelete
  9. how to develop different styles of lines using DDA??

    ReplyDelete