Saturday, March 31, 2012

Liang-Barsky Line Clipping Algorithm with C/C++

Theory
In Liang-Barsky algorithm, we first write the point-clipping conditions in parametric form as 
Parametric Form
Each of these for inequalities can be expressed as inequalities , k = 1, 2, 3, …..
where parameter p and q are defined as
Boundaryparameter
Any line that is parallel to one of the clipping boundaries has pk = 0 for the value of k corresponding to that boundary. If, for that value of k, we also find qk < 0, then the line is completely outside the boundary and can be eliminated from further consideration. If qk >=0, the line is inside the parallel clipping boundary.
When pk <0, the infinite extension of the line proceeds from the outside to the inside of the inside of the infinite extension of this particular boundary. If pk > 0, the line proceeds from the insides to the outside. For a nonzero value of pk, we can calculate the value of u that corresponds to the point where the infinitely extended line intersects the extension of boundary k as u = qk / pk.

For each line, we calculate values of parameters u1 and u2 that define that part of the line that lies within the clip rectangle. The value of u1 is determined by looking at the rectangle edges for which the line proceeds from the outside to inside (p < 0). For these edges, we calculate rk = qk / pk. The value of u1 is taken as the largest of the set consisting of 0 and the various values of r. Conversely, the value of u2 is determined by examining the boundaries for which the line proceeds from inside to outside (p > 0). A value of rk is calculated for each of these boundaries, and the value of u2 is minimum of the set consisting of 1 and the calculated r values. If u1 > u2, the line is completely outside the clip window and it can be rejected. Otherwise, the endpoints of the clipped line are calculated from the two values of parameter u.
Source Code
#include <windows.h> #include <cmath> #define ROUND(a) ((int) (a + 0.5)) static HWND sHwnd; static COLORREF redColor=RGB(255,0,0); static COLORREF blueColor=RGB(0,0,255); static COLORREF greenColor=RGB(0,255,0); typedef struct Point {     int x;     int y; }pt; pt winMin = {100, 100}; pt winMax = {800, 400}; pt p1 = {50, 200}; pt p2 = {900, 300}; 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; } void LineBresenham (int xa, int ya, int xb, int yb){     int dx = (xb - xa), dy = (yb - ya);     int x, y, xEnd, yEnd;     int p = 2 * abs(dy) - abs(dx);     int twoDy = 2 * abs(dy), twoDyDx = 2 * (abs(dy) - abs(dx));     int tFactor = dx*dy;     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{             if(tFactor > 0) //for positive slope                 y++;             else //for negative slope                 y--;             p += twoDyDx;         }         setPixel(x, y);     } } void drawBoundary(pt winMin, pt winMax){     int x, y;     x = winMin.x;     for(y = winMin.y; y < winMax.y; y++){         setPixel(x,y, blueColor);     }     y = winMin.y;     for(x = winMin.x; x < winMax.x; x++){         setPixel(x,y, blueColor);     }     x = winMax.x;     for(y = winMin.y; y < winMax.y; y++){         setPixel(x,y, blueColor);     }     y = winMax.y;     for(x = winMin.x; x < winMax.x; x++){         setPixel(x,y, blueColor);     } } int clipTest(float p, float q, float *u1, float *u2){     float r;     int retVal = TRUE;     if(p < 0.0){         r = q / p;         if(r > *u2)             retVal = FALSE;         else             if (r > *u1)                 *u1 = r;     }     else         if (p > 0.0){             r = q / p;             if (r < *u1)                 retVal = FALSE;             else if (r < *u2)                 *u2 = r;         }         else             if(q < 0.0)                 retVal = FALSE;         return (retVal); } void clipLine(pt winMin, pt winMax, pt p1, pt p2){     float u1 = 0.0, u2 = 1.0, dx = p2.x - p1.x, dy;     if(clipTest(-dx, p1.x - winMin.x, &u1, &u2))         if(clipTest(dx, winMax.x - p1.x, &u1, &u2)){             dy = p2.y - p1.y;             if(clipTest(-dy, p1.y - winMin.y, &u1, &u2))                 if(clipTest(dy, winMax.y - p1.y, &u1, &u2)){                     if(u2 < 1.0){                         p2.x = p1.x + u2 * dx;                         p2.y = p1.y + u2 * dy;                     }                     if(u1 > 0.0){                         p1.x += u1 * dx;                         p1.y += u1 * dy;                     }                     LineBresenham(ROUND(p1.x), ROUND(p1.y), ROUND(p2.x), ROUND(p2.y));                 }         } } /* Window Procedure WndProc */ LRESULT CALLBACK WndProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam){     switch(message){         case WM_PAINT:             SetWindowHandle(hwnd);             drawBoundary(winMin, winMax);             clipLine(winMin, winMax, p1, p2 );             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("Line Clipping");     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,"Liang-Barsky 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; }

Output

Liang-Barksy

No comments:

Post a Comment