计算机图形学裁剪:关于梁友栋-Barsky算法(Liang-Barsky算法)

直线的裁剪: 梁友栋-Barsky算法(Liang-Barsky算法)

1. 算法的基本思想

以直线的参数方程为基础,对不同情况下的裁剪求得相应的参数值。

2. 算法的推导过程

情形一 pk=0

(1)p1=p2=0

若q1<0或q2<0,则可删除直线段 若q1>=0且q2>=0,则进一步判断

u=qk/pk(k=3,4)

令 u1=max(0,u|pk<0) u2=min(1,u|pk>0)

若u1>u2,则可删除直线段

若u1<=u2,将u1,u2代入直线方程,得到直线段的两个可见端点。 (2)p3=p4=0 若q3<0或q4<0,则可删除直线段 若q3>=0且q4>=0,则进一步判断

u=qk/pk(k=1,2)

令 u1=max(0,u|pk<0) u2=min(1,u|pk>0)

若u1>u2,则可删除直线段

若u1<=u2,将u1,u2代入直线方程,得到直线段的两个可见端点。 情形二 pk不为0 u=qk/pk(k=1,2,3,4) 令 u1=max(0,u|pk<0,u|pk<0) u2=min(1,u|pk>0, u|pk>0)

若u1>u2,则可删除直线段

若u1<=u2,将u1,u2代入直线方程,得到直线段的两个可见端点。 3. 算法步骤 (1)输入直线段的两端点坐标以及窗口的四条边界坐标。 (2)若Δx=0,则p1=p2=0。进一步判断是否满足q1<0或q2<0,若满足,则该直线段不在窗口内,转(7)。否则,满足q1>0且q2>0,则进一步计算u1和u2。转(5)。

(3)若Δy=0,则p3=p4=0。进一步判断是否满足q3<0或q4<0,若满足,则该直线段不在窗口内,转(7)。否则,满足q1>0且q2>0,则进一步计算u1和u2。转(5)。

(4)若上述两条均不满足,则有pk≠0(k=1,2,3,4)。此时计算u1和u2。

(5)求得u1和u2后,进行判断:若u1>u2,则直线段在窗口外,转(7)。若u1TC 下的源程序:

#include "graphics.h"
#include "stdio.h"
#include "conio.h"

int ClipT(float p,float q,float *u1,float *u2)
{
int flag=1;
float r;
if(p<0.0) { r=q/p; if(r>*u2) flag=0;
else if(r>*u1)
*u1=r;
}
else if(p>0.0)
{
r=q/p;
if(r<*u1) flag=0; else if(r<*u2) *u2=r; } else if(q<0.0) flag=0; return flag; } void LiangLine(int xwmin,int ywmin,int xwmax,int ywmax,int x1,int y1,int x2,int y2) { float dx,dy,u1,u2; u1=0.0;u2=1.0; dx=x2-x1; if(ClipT(-dx,x1-xwmin,&u1,&u2)) if(ClipT(dx,xwmax-x1,&u1,&u2)) { dy=y2-y1; if(ClipT(-dy,y1-ywmin,&u1,&u2)) if(ClipT(dy,ywmax-y1,&u1,&u2)) { if(u2<1.0) { x2=x1+u2*dx; y2=y1+u2*dy; } if(u1>0.0)
{
x1=x1+u1*dx;
y1=y1+u1*dy;
}
line(x1,y1,x2,y2);
getch();
}
}
}

void main(void)
{
int XL,XR,YB,YT;
int x0,y0,x1,y1;
int gd=DETECT,gm=0;
initgraph(&gd,&gm,"");
cleardevice();
printf("Please input the rectangle point(XL,YT,XR,YB):n");
scanf("%d%d%d%d",&XL,&YT,&XR,&YB);
setcolor(10);
rectangle(XL,YT,XR,YB);
getch();
printf("Please input the line node(x0,y0,x1,y1):n");
scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
LiangLine(XL,YT,XR,YB,x0,y0,x1,y1);
}

liang-brisky算法VC中的函数实现代码:
此方法简要实现平面矩形区域直线的的裁剪,VC中程序主体部分函数代码如下:


bool CMyView::ClipT(float p,float q,float *u1,float *u2)
//判断区域
{
bool flag=1;
float r;
{
if(p<0.0) { r=q/p; if(r>*u2) flag=0;
else if(r>*u1)
*u1=r;
}
else if(p>0.0)
{
r=q/p;
if(r<*u1) flag=0; else if(r<*u2) *u2=r; } else if(q<0.0) flag=0; } return flag; } void CMyView::LiangLine(int xwmin,int ywmin,int xwmax,int ywmax,int x1,int y1,int x2,int y2) //Liang-Barsky裁剪算法 { CDC* pDC = GetDC(); pDC->Rectangle(xwmin,ywmin,xwmax,ywmax); //画出裁剪区域(长方)
int sx,sy,ex,ey;
float dx,dy,u1,u2;
u1=0.0;u2=1.0;
dx=x2-x1;
sx=x1;sy=y1;ex=x2;ey=y2;
if(ClipT(-dx,sx-xwmin,&u1,&u2))
{
if(ClipT(dx,xwmax-sx,&u1,&u2))
{
dy=ey-sy;
if(ClipT(-dy,sy-ywmin,&u1,&u2))
if(ClipT(dy,ywmax-sy,&u1,&u2))
{
if(u2<1.0) { ex=sx+u2*dx; ey=sy+u2*dy; } if(u1>0.0)
{
sx+=u1*dx;
sy+=u1*dy;
}
//画出裁剪后的线
pDC->MoveTo(ex,ey);
pDC->LineTo(sx,sy);
}
}
}
}

点赞 (1)

发表评论

电子邮件地址不会被公开。 必填项已用*标注