计算机图形学裁剪算法.doc

《计算机图形学裁剪算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、实验目标1.了解Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的基本思想；2.掌握Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的算法实现；二、实验内容本次实验主要是实现Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法。Cohen-sutherland线段裁剪算法思想：

2、该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。Cohen-sutherland线段裁剪算法步骤：1、分区编码延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。四位二进制代码的编码规则是：(1)第一位置1：区域在左边界

3、外侧(2)第二位置1：区域在右边界外侧(3)第三位置1：区域在下边界外侧(4)第四位置1：区域在上边界外侧裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。2、判别根据C1和C2的具体值，可以有三种情况：（1）C1=C2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C2≠0（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段

4、全在窗外，应予舍弃。（3）不属于上面两种情况，均需要求交点。3、求交点假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第2步，重新判断，如果需要接着进入下一边界的处理。为了规范算法，令线段的端点P1为外端点，如果不是这样，就需要P1和P2交换端点。当条件(C1&0001≠0)成立时，表示端点P1位于窗口左边界外侧，按照求交公式，进行对左边界的求交运算。依次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。求出交点P后，用P1=P来舍去线段

5、的窗外部分，并对P1重新编码得到C1，接下来算法转回第2步继续对其它边界进行判别。Liang-Barsky线段裁剪算法思想：我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示：x=x1+u·（x2-x1）=x1+u·Δxy=y1+u·（y2-y1）=y1+u·Δy0≤u≤1式中，Δx=x2-x1，Δy=y2-y1，参数u在0～1之间取值，P（x，y）代表了该线段上的一个点，其值由参数u确定，由公式可知，当u=0时，该点为P1（x1，y1），当u=1时，该点为P2（x2，y2）。如果点P（x，y）位于

6、由坐标（xwmin，ywmin）和（xwmax，ywmax）所确定的窗口内，那么下式成立：xwmin≤x1+u·Δx≤xwmaxywmin≤y1+u·Δy≤ywmax这四个不等式可以表示为：u·pk≤qk，k=1，2，3，4其中，p、q定义为：p1=-Δx，q1=x1-xwminp2=Δx，q2=xwmax-x1p3=-Δy，q3=y1-ywminp4=Δy，q4=ywmax-y1从上式可以知道：任何平行于窗口某边界的直线，其pk=0，k值对应于相应的边界（k=1，2，3，4对应于左、右、下、上边界）。如果还满足qk<0，则线段完全在边

7、界外，应舍弃该线段。如果pk=0并且qk≥0，则线段平行于窗口某边界并在窗口内，见图中所示。上式还告诉我们：1、当pk<0时，线段从裁剪边界延长线的外部延伸到内部；2、当pk>0时，线段从裁剪边界延长线的内部延伸到外部；对于每条直线，可以计算出参数u1和u2，该值定义了位于窗口内的线段部分：1、u1的值由线段从外到内遇到的矩形边界所决定（pk<0），对这些边界计算rk=qk/pk，u1取0和各个r值之中的最大值。2、u2的值由线段从内到外遇到的矩形边界所决定（pk>0），对这些边界计算rk=qk/pk，u2取0和各个r值之中的最小值。3

8、、如果u1>u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u1和u2计算出来。Liang-Barsky线段裁剪算法实现：1、初始化线段交点的参数：u1=0，u2=1；2、计算出各