计算机图形学裁剪算法寒假

裁剪算法

直线裁剪算法

暴力裁剪法

点的裁剪
线的裁剪

判断直线段与窗口的关系

三个算法

Cohen Sutherland算法/编码裁剪算法——通过二进制编码及运算，对直线与窗口的关系进行分类。

处理方法

1.简取
2.简弃
3.既不简取也不简弃

编码
运算

适用范围

中点分割法——二分逼近的方法确定直线段与窗口的交点

处理方法

中点不在窗口内
中点在窗口内

Liang Barsky算法——直线方程参数化、给直线赋方向

算法分析

P~k~=0时

==若此时还满足q~k~<0==，则线段完全在边界外，舍弃该线段。
==若此时满足q~k~≥0==，则进一步判断。

P~k~!=0时

P~k~<0时
P~k~>0时

U~k~=q~k~/p~k~（p~k~!=0,k=1,2,3,4)

U~max~=max(0,U~k~|~pk<0~,U~k~|~pk<0~)
U~min~=min(U~k~|~pk<0~,U~k~|~pk<0~,1)

在家听网课的第三章。
中国农业大学赵明老师。
直线裁剪算法

文章图片

如上图，屏幕显示的只是图形的一部分。需要确定图形哪些部分落在显示区之内，哪些落在显示区之外。
选择的过程就称为裁剪。
暴力裁剪法最暴力的裁剪方法：判断图形所有的点是不是都在窗口内。
点的裁剪

文章图片

只要点的x,y满足在窗口矩形区域内的条件（x左≤x≤x右且y下≤y≤y上），就可取。
线的裁剪
判断直线段与窗口的关系

文章图片

全部在窗口内:EF
全部在窗口外:IJ,CD
与窗口边界相交:AB,GH
如果相交，则计算它与边界的交点（以确定这条线段的哪一部分可显示）。

三个算法以下。
Cohen Sutherland算法/编码裁剪算法——通过二进制编码及运算，对直线与窗口的关系进行分类。处理方法
分三类处理线段
1.简取

文章图片

线段两端点都在窗口内时，线段必全在窗口内。
2.简弃

文章图片

线段两端点全在窗口左边/右边/上面/下面时，线段必在窗口外
3.既不简取也不简弃对直线段按照交点进行分段，分段后判断直线是简取还是简弃。
编码线段的两个端点赋四位二进制码 D3D2D1D0.
D3D2D1D0代表的意义如图

文章图片

赋值准则

文章图片

运算

若或运算为0，则直线段简取；
若与运算非0，则直线段简弃；
若两条件均不成立，则直线段要被一分为二，需求出直线段与窗口边界的交点，进行取舍。

适用范围

大部分线段完全可见时；
大部分线段完全不可见时。

中点分割法——二分逼近的方法确定直线段与窗口的交点处理方法
不断求线段的中点，逼近交点（直到中点与窗口边界的坐标值在规定的误差范围内相等）。
中点不在窗口内

文章图片

舍弃中点和离窗口边界最远点构成的线段。
中点在窗口内

文章图片

舍弃中点和离窗口边界最近点构成的线段。
Liang Barsky算法——直线方程参数化、给直线赋方向

p1 = -Δx, q1 = x1-xleft
p2 =+Δx, q2 = xright-x1
p3 = -Δy, q3 = y1-ybottom
p4 =+Δy, q4 = ytop-y1

u*pk≤qk，其中k=1,2,3,4
入边：左边和下边(1,3)
出边：右边和上边(2,4)
算法分析
Pk=0时

当P1=P2=0时：表示直线平行于y轴
文章图片
当P1=P2=0时：表示直线平行于x轴

文章图片

若此时还满足qk<0，则线段完全在边界外，舍弃该线段。

文章图片

若此时满足qk≥0，则进一步判断。若Δx=0（p1=p2=0），有q1≥0且q2≥0；
若Δy=0（p3=p4=0），有q1≥0且q2≥0；

文章图片

Pk!=0时 Pk<0时线段从裁剪边界延长线的外部延伸到内部，有入边交点。
Pk>0时线段从裁剪边界延长线的内部延伸到外部，有出边交点。
Uk=qk/pk（pk!=0,k=1,2,3,4) Umax=max(0,Uk|pk<0,Uk|pk<0) Umin=min(Uk|pk<0,Uk|pk<0,1)