计算机图形学 裁剪解析.ppt

二维裁剪 直线段裁剪 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)若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。 中点分割算法 基本思想： 当对直线段不能简取也不能简弃时，简单地把线段等分为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外。? 例 中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点。 Nicholl-Lee-Nicholl算法 消除C-S算法中多次求交的情况。 基本想法：对2D平面的更细的划分。 多边形裁剪 用直线段裁剪算法，可以吗？ 新的问题： Sutherland-Hodgman算法 分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。 流水线过程(左上右下)：左边的结果是右边的开始。 Sutherland-Hodgman算法 可见一侧空间和不可见一侧空间 沿多边形依次处理顶点会遇到四种情况 Sutherland-Hodgman算法 裁剪结果的顶点构成：裁剪边内侧的原顶点；多 边形的边与裁剪边的交点。 顺序连接。 例子：对多边形ABCDEFGH进行裁剪 练习：试用S-H算法裁剪下图多边形，要求画出每次裁剪对应的图形，并表明输入输出的顶点。 解：用左边界裁剪前后为： * xl xr yb yt x y 则点P在矩形窗口内；否则，点P在矩形窗口外。 xl xr yb yt x y P(x,y) 为提高效率，算法设计时应考虑： (一）快速判断情形(1)(2)； (二) 设法减少情形(3)求交次数和每次求交时所需的计算量。 p1 p2 (3) 若直线段既不满足“简取”的条件，也不满足“简弃”的条件，则该直线段可能与窗口相交。此时，求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束。