Friday, January 20, 2012

Implementing Bresenham’s Line Drawing Algorithm in C/C++

Bresenham’s Line Drawing Algorithm is an accurate and efficient raster line-generating algorithm developed by Bresenham. In this algorithm, we first consider the scan – conversion process for lines with positive slope less than 1. Pixel positions along a line path are then determined by sampling at unit x intervals. Starting from the left end point (x0, y0) of a given line, we step to each successive column (x position) and plot the pixel whose scan – line y values is closet to the line path. Assuming we have determined that the pixel at (x(k), y(k)) is to be displayed, we next need to decide which pixel to plot in column x(k+1). Our choices are the pixels at positions (x(k) + 1, y(k)) and (x(k) + 1, y(k) + 1).

The following section implements Bresenham’s  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.
#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 drawLineBresenham(int xa, int ya, int xb, int yb){
    int dx = abs(xa - xb), dy = abs(ya - yb);
    int p = 2 * dy - dx;
    int twoDy = 2 * dy, twoDyDx = 2 * (dy - dx);
    int x, y, xEnd;

    if (xa > xb){
        x = xb;
        y = yb;
        xEnd = xa;
    }else{
        x = xa;
        y = ya;
        xEnd = xb;
    }
    setPixel(x, y);
    while(x < xEnd){
        x++;
        if(p < 0)
            p += twoDy;
        else{
            y++;
            p += twoDyDx;
        }
        setPixel(x, y);
    }
}
/* Window Procedure WndProc */
LRESULT CALLBACK WndProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam){
    switch(message){
        case WM_PAINT:
            SetWindowHandle(hwnd);
            drawLineBresenham(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,"Bresenham's Algorithm - 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 generated by above program is 

Bresenham

1 comment:

  1. Hey
    Does Bresenham's Line Drawing Algorithm generate vertical lines?
    I've tried running your code in my pc but it doesn't compile!
    void drawLineBresenham(int xa, int ya, int xb, int yb){

    int dx = abs(xa - xb), dy = abs(ya - yb);

    int p = 2 * dy - dx;

    int twoDy = 2 * dy, twoDyDx = 2 * (dy - dx);

    int x, y, xEnd;


    if (xa > xb){

    x = xb;

    y = yb;

    xEnd = xa;

    }else{

    x = xa;

    y = ya;

    xEnd = xb;

    }

    setPixel(x, y);

    while(x < xEnd){

    x++;

    if(p < 0)

    p += twoDy;

    else{

    y++;

    p += twoDyDx;

    }

    setPixel(x, y);

    }

    }
    in verticle line x1=x2
    so xend=0
    :(
    Please help

    ReplyDelete