计算机图形学裁剪算法初步.ppt

5.5 裁剪算法 5.1.1 线段裁剪算法 5.1.2 多边形裁剪算法 确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形,这个选择过程称为裁剪。 该显示区被称为裁剪窗口。 5.5.1 线段裁剪算法 假设矩形窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，则点P(x,y)在窗口内的条件是： (xL,yB ) (xR,yT ) P 点的位置是裁剪中最基本的问题 否则，P点就在窗口外。 满足： xL = x = xR 和 yB = y = yT 直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。 常用的线段裁剪方法 Cohen-Sutherland、 中点分割算法、 梁友栋－barskey算法。 5.5.1 线段裁剪算法 快速判断情形(1)(2)，对于情 形(3)，设法减少求交次数和 每次求交时所需的计算量。 a b c 裁剪线段与窗口的关系： (1) 线段完全可见； (2) 显然不可见； (3) 线段至少有一端点在窗口之外，但非显然不可见。 如何提高裁剪效率？ 线段裁剪有多种算法，但基本思想都是： （1）线段是否全不在窗口内，是则结束。 （2）线段是否全在窗口内，是则显示该线段，结束。 （3）计算该线段与窗口边界延长线的交点，以此将线段分成两部分；丢弃不可见的部分；对剩下的部分转（2）。 它又称为Sutherland-Cohen分割线算法. 5.5.1.1 Cohen-Sutherland 端点编码算法 将矩形窗口的四边分别延长后，得到九个区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。 1.线段的端点编码 它是最早最流行的裁剪算法, 可以扩展为三维裁剪. 区域码为： 上 下 右 左 X X X X 任何位赋值为1，代表端点落在相应的位置上，否则该位为0。这一编码的特点是对于窗口的某一条边外侧的三个区域的四位编码中有一位全为1。 线段的端点编码 1001 1000 1010 0001 0101 0010 0110 0100 y x yT yB xL xB 0000  上 下 右 左 P1 □ □ □ □ Y=YT  P2 Y=YB P4 P3 X=XL X=XR 线段的各端点编码？ 对于三维裁剪,需要6位编码。 (1010) (1001) P3： 0110 P1: 1001  P4： 1010 P2: 0010 0010 0000 (0110) (0010) 一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律： 否则，在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 若P1P2明显在窗口外：code1code2≠0，则“弃” 若P1P2完全在窗口内：code1=0,且code2=0,则“取” (1)若线段P1P2两端点的四位编码均为0,则两端点均在窗口内,该线段完全可见,显示该线段,算法结束; P6 P5 P2 P1 P4 P3 Cohen-Sutherland端点编码算法 (3)若线段两端点的四位编码按位“与”结果为0, 找到P1P2在窗口外的一个端点P1(或P2),用窗口相应的边与P1P2的交点取代该端点P1（或P2）, 返回(1)步。 (2) 若线段P1P2两端点的四位编码按位“与”结果为非0,则该线段完全不可见,算法结束。 裁剪一条线段时，先求出端点p1和p2的编