图形图像学基础4.pptVIP

二维裁剪 直线段裁剪 Cohen-Sutherland算法； 中点算法 Nicholl-Lee-Nicholl算法 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法 假设窗口是标准矩形，即边与坐标轴平行的矩形，由上（y=yt）、下（y=yb）、左（x=xl）、右（x=xr）四条边描述。 点的裁剪 对于任意一点P(x,y),若满足下列不等式 直线段的裁剪 直线段和剪裁窗口的可能关系： (1) 完全落在窗口内 (2) 完全落在窗口外 (3) 与窗口边界相交?? Cohen-Sutherland算法 基本思想： 对每条直线段p1(x1,y1)p2(x2,y2)分三步处理： (1)判断点P1和P2是否完全在裁减窗口内，若是，直线段完全可见，“简取”之。 否则进入步骤（2）。 x1xl and x1xr x2xl and x2xr y1yb and y1yt y2yb and y2yt Cohen-Sutherland算法 (2)若点P1和P2均在窗口外，判断是否满足下列4个条件之一： x1xl and x2xl x1xr and x2xr y1yb and y2yb y1yt and y2yt 若是，则该直线段完全不可见，“简弃”之。否则进入第三步 Cohen-Sutherland算法 特点： 对完全可见和不可见线段的快速判别。 编码方法： 由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个4位的二进制编码D4D3D2D1。编码规则如下: 若xxl，则D1=1，否则D1=0； 若xxr，则D2=1，否则D2=0； 若yyb，则D3=1, 否则D3=0； 若yyt，则D4=1，否则D4=0。 Cohen-Sutherland算法 Cohen-SutherLand算法 求交测试顺序固定 最坏情形，线段求交四次。 Cohen-Sutherland算法 裁剪一条线段时，先求出端点p1和p2的编码code1和code2，然后： (1)若code1|code2=0，对直线段应“简取”之。 (2)若code1code2≠0，对直线段可“简弃”之。 (3)若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。 求交：假定直线的端点坐标为(x1,y1)和(x2,y2) 左、右边界交点y坐标值的计算 练习 Cohen-Sutherland算法 ?算法特点 中点分割算法 基本思想： 当对直线段不能简取也不能简弃时，简单地把线段等分为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外。? 例 中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点。 中点分割算法 算法步骤： (1)输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界坐标：yt、yb、xl和xr。 (2)对p1、p2进行编码：点p1的编码为code1，点p2的编码为code2。 (3)若code1|code2=0，对直线段应简取之，保留当前直线段的端点坐标，转(5)；否则，若code1code2≠0，对直线段可简弃之，转(5)；当上述两条均不满足时，进行步骤(4)。 (4)求出直线段的中点M，将p1M、p2M入栈。 (5)当栈不空时，从栈中弹出一条直线段，取为p1p2，转(2)进行处理。否则，继续(6)。 (6)当栈为空时，合并保留的直线段端点，得到窗口内的直线段p1p2。用直线扫描转换算法画出当前的直线段p1p2，算法结束 中点分割算法的改进 寻找两个端点的最远可见点： （1）找出该直线段位于窗口外的点和该直线段的中点。判中点是否在窗口内：若中点在窗口内，则又以中点和位于窗口外的端点构成线段，并求其中点；若中点不在窗口内，则把中点和位于窗口外的端点构成的线段丢掉，以线段上的另一点和该中点再构成线段求其中点。直到中点与窗口边界的坐标值在规定的误差范围内相等，则该中点就是当前端点的最远可见点即该线段落在窗口内的一个端点坐标。 (2)