第五章 裁剪、反走样方法.ppt

二维裁剪 直线段裁剪 直接求交算法 Cohen-Sutherland算法 中点分割算法 参数化裁剪算法 Liang-Barskey算法 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法 裁剪 裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。 图形裁剪算法，直接影响图形系统的效率。 点的裁剪 图形裁剪中最基本的问题。 假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式：xL = x = xR 并且yB = y = yT否则，P点就在窗口外。 问题：对于任意多边形窗口，如何判别？ 直线段裁剪 直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。 直接求交算法 Cohen-Sutherland算法 中点算法 梁友栋－barskey算法 参数化裁剪算法 直线段裁剪 裁剪线段与窗口的关系：(1)线段完全可见；(2)显然不可见；(3)其它 提高裁剪效率： 快速判断情形(1)(2)， 对于情形(3)，设法减 少求交次数和每次求 交时所需的计算量。 直接求交算法 直线与窗口边都 写成参数形式， 求参数值。 Cohen-Sutherland裁剪 基本思想： 对于每条线段P1P2分为三种情况处理: （1）若P1P2完全在窗口内，则显示该线段P1P2。 （2）若P1P2明显在窗口外，则丢弃该线段。 （3）若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 为快速判断，采用如下编码方法： 若P1P2完全在窗口内code1=0,且code2=0,则“取” 若P1P2明显在窗口外code1code2≠0，则“弃” 若code1code2=0， P1P2非完全不可见。在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 如何判定应该与窗口的哪条边求交呢？ 编码中对应位为1的边。 计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点 if(LEFTcode !=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} else if(RIGHTcode !=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} else if(BOTTOMcode !=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);} Cohen-Sutherland 直线裁剪算法小结 本算法的优点在于简单，易于实现。它可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，它决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。 特点：用编码方法可快速判断线段的完全可见和显然不可见。 中点分割裁剪算法 基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。 与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0 、 P1最近的可见点，Pm为P0P1中点。 中点分割裁剪算法-求线段与窗口的交点 从P0出发找距离P0最近可见点采用中点分割方法 先求出P0P1的中点Pm, 若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1； 否则取PmP1代替P0P1。 再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。 从P1出发找距离P1最近可见点采用上面类似方法。 中点分割裁剪算法 中点分割裁剪算法 对分辩率为2N*2N的显示器，上述二分过程至多进行N次。 主要过程只用到加法和除2运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。 线段的参数表示 x=x0+t△x y=y0+t△y 0=t=1 △x=x1-x0 △y=y1