Liang-Barsky Line Clipping Algorithm with C/C++
Theory
In Liang-Barsky algorithm, we first write the point-clipping conditions in parametric form as
Each of these for inequalities can be expressed as 
, k = 1, 2, 3, …..
where parameter p and q are defined as
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
<div align="justify">
<b>Source Code</b></div>
#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
