发布时间 : 星期一 文章计算机图形学各种算法的作业（偏于理论）更新完毕开始阅读d669a0c2d5bbfd0a795673b5
LH计算机图形学作业：共九道题
2.3.3 算法程序描述
具体程序实现见附录5。
3 直线段裁剪算法综述
裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。
直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。 3.1 Sutherland-Cohen裁剪算法 3.1.1 Sutherland-Cohen算法基本原理
Sutherland–Cohen算法分成两步。第一步是判断直线段是否完全在窗口内，若在则该线段称为完全可见的；或可显然的决定线段完全在窗口的外边，称为完全不可见；对不能判断完全可见或完全不可见的线段则要进行第二步处理。这时需要计算出直线段和窗口边界的一个交点，这个交点把直线分成两段，把其中一段显然完全不可见的线段抛弃，对余下的部分再作第一步判断，重复上述过程，直到直线段最后余下的部分可以用第一步的判断得出肯定结论为止。 3.1.2 Sutherland-Cohen算法实现步骤
基本思想：对于每条线段p1p2分为三种情况处理分为三种情况处理:
（1）若p1p2完全在窗口内，则显示该线段p1p2，简称“取”之。 （2）若p1p2明显在窗口外，则丢弃该线段，简称“弃”之。 （3）若线段不满足“取”或 “弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 为快速判断，采用如下编码方法：
每个区域赋予4位编码（如图3.1所示）：
CtCbCrCl
其中：
?1Ct???0y?ymaxother?1Cb???0y?ymin other 11
LH计算机图形学作业：共九道题
?1Cr???0x?xmaxother?1Cl???0x?xminother
yT yB 1001 1000 0001 0101 0000 0100 1010 0010 0110 xL xR
x
图3.1 区域编码 图3.2 线段不能用编码确定
若p1p2完全在窗口内code1=0,且code2=0,则“取” 若p1p2明显在窗口外code1&code2≠0，则“弃”
在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。
计算线段p1?x1,y1?p2?x2,y2?与窗口边界的交点
if(LEFT&code !=0)
{ x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} else if(RIGHT&code !=0)
{ x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} else if(BOTTOM&code !=0)
{ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);} else if(TOP & code !=0)
{ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);} 3.1.3 算法程序（或伪程序）描述
过程clip描述了这一算法。其中用一个集合(top,bottom,right,left)来表示端点的编码。具体程序见附录6。 3.1.4 算法流程图
（略）
3.2 中点分割裁剪算法
3.2.1 中点分割算法基本原理与实现步骤
与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，
12
LH计算机图形学作业：共九道题
并把线段与窗口的关系分为三种情况：完全可见、完全不可见和线段与窗口有交。对前两种情况，进行一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。
求线段与窗口的交点如下：
设要裁剪的线段是P0P1。中点分割算法可分成两个过程平行进行，即从P0出发找出离P0最近的可见点（图3.3中的A点），和从P1出发找出离P1最近的可见点（图3.3中的B点）。这两个最近可见点的连线就是原线段的可见部分。
从P0出发找出最近可见点的办法是先求P0P1的中点Pm，若P0Pm不能定为显然不可见，则取P0Pm代替P0P1，否则取PmP1代替P0P1，再对新的P0P1求中点Pm。重复上述过程，直到P1Pm长度小于给定的小数?为止。
图3.4是求P0的最近可见点P的算法框图。求P1的最近可见点的算法框图是一样的，只要把P0和P1交换即可。
在显示时?可取成一个像素的宽度，对分辨率为2N?2N的显示器来说，上面讲的二分的过程最多只要做N次。由于计算机过程只要做加法和除2，所以特别适合用硬件来实现。
如果允许两个找最近点的过程平行进行，这样的话可使裁剪速度加快，增加算法效率。
图3.3 中点分割算法
3.2.2 算法程序（或伪程序）描述
具体程序见附录7。 3.2.3 算法流程图
中点分割算法框图如图3.4。
13
LH计算机图形学作业：共九道题
P0可见否? 否 是 P?P0 exit 是 显然不可P0P1否 原线完全不可Pm?(P0?P1)/2是 P1?Pm??否 P0?Pm exit P0Pm显然不可见? 是 否 P0?PmP1?Pm
图3.4 中点分割算法框图
3.3 梁友栋－Barskey算法
3.3.1 梁友栋－Barskey算法基本原理与实现步骤
设要裁剪的线段是P0P1，Pi的坐标是?xi,yi?,i?0,1。P0P1和窗口边界交于A、B、C、D四点，见图3.5。算法基本思想是从A，B和P0三点中找出最靠近P1的点，图3.5中要找的点是P0，从C，D和P1三点中找出最靠近P0的点，图3.5中要找的点是C点。那么P0C就是P0P1上的可见部分。
y D y
P1 C P0y
B A xL xR x
图3.5 P0C是可见部分
14