文档介绍：多边形裁剪算法
第1页，本讲稿共40页
裁剪
裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。
图形裁剪算法，直接影响图形系统的效率。
要的，决定了算法的速度。另外，本算法对于其它形状的窗口未必同样有效。
特点：用编码方法可快速判断线段的完全可见和显然不可见。
第13页，本讲稿共40页
中点分割裁剪算法
基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。
与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0 、 P1最近的可见点，Pm为P0P1中点。
第14页，本讲稿共40页
中点分割算法-求线段与窗口的交点
从P0出发找距离P0最近可见点采用中点分割方法
先求出P0P1的中点Pm,
若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；
否则取PmP1代替P0P1。
再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。
从P1出发找距离P1最近可见点采用上面类似方法。
第15页，本讲稿共40页
中点分割裁剪算法
第16页，本讲稿共40页
对分辩率为2N*2N的显示器，上述二分过程至多进行N次。
主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。
中点分割裁剪算法
第17页，本讲稿共40页
设要裁剪的线段是P0P1。 P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。
梁友栋-Barsky算法
第18页，本讲稿共40页
梁友栋-Barsky算法
线段的参数表示
x=x0+t△x
y=y0+t△y 0<=t<=1
△x=x1-x0 △y=y1-y0
窗口边界的四条边分为两类：始边和终边。
第19页，本讲稿共40页
求出P0P1与两条始边的交点参数t0, t1 , 令tl=max(t0 ,t1,0)，则tl即为三者中离p1最近的
点的参数
求出p0p1与两条终边的交点参数t2, t3, 令tu=min(t2,t3,1) ，则tu即为三者中离p0最近的
点的参数
若tu > tl,则可见线段区间
[tl , tu]
t0
t1
t2
t3
0
1
梁友栋-Barsky算法：交点计算
第20页，本讲稿共40页
梁友栋-Barsky算法
始边和终边的确定及交点计算：
令 QL= - △x DL= x0-xL
QR= △x DR= xR-x0
QB= - △y DB= y0-yB
QT= △y DT= yT-y0
交点为 ti= Di / Qi i=L,R,B,T
Qi <0 ti为与始边交点参数
Qi >0 ti为与终边交点参数
Qi =0 Di <0 时,线段不可见
Di >0 时, 分析另一D,
E
F
A
B
第21页，本讲稿共40页
梁友栋-Barsky算法
当Qi =0时
若Di <0 时,线段不可见
（如图中AB，有QR=0，DR<0）
若Di >0 时, 分析另一D,
（如图中的EF就是这种情况，它使QL=0，DL>0和QR=0，DR>0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）
E
F
A
B
第22页，本讲稿共40页
第5章 图形变换与裁剪
齐次坐标
窗口到视区的变换
图形几何变换
三维图形的基本问题
平面几何投影
直线段裁剪
多边形裁剪
第23页，本讲稿共40页
错觉：直线段裁剪的组合？
新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？
第24页，本讲稿共40页