计算机图形学裁剪

二维裁剪直线段裁剪Cohen-Sutherland算法；中点算法Nicholl-Lee-Nicholl算法多边形裁剪Sutlerland_Hodgman算法Weiler-Athenton算法假设窗口是矩形，即边与坐标轴平行的矩形，由上（y=yt）、下（y=yb）、左（x=xl）、右（x=xr）四条边描述。xlxrybytxy点的裁剪对于任意一点P(x,y),若满足下列不等式则点P在矩形窗口内；否则，点P在矩形窗口外。xlxrybytxyP(x,y)直线段的裁剪直线段和剪裁窗口的可能关系：(1)完全落在窗口内(2)完全落在窗口外(3)与窗口边界相交  为提高效率，算法时应考虑：(一）快速判断情形(1)(2)；(二)设法减少情形(3)求交次数和每次求交时所需的计算量。基本：对每条直线段p1(x1,y1)p2(x2,y2)分三步处理：(1)判断点P1和P2是否完全在裁减窗口内，若是，直线段完全可见，“简取”之。否则进入步骤（2）。x1xrx2xry1>ybandy1ybandy2xrandx2>xry1ytandy2>yt若是，则该直线段完全不可见，“简弃”之。否则进入第三步Cohen-Sutherland算法(3)若直线段既不满足“简取”的条件，也不满足“简弃”的条件，则该直线段可能与窗口相交。此时，求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束。特点：对完全可见和不可见线段的快速判别。编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个4位的二进制编码D4D3D2D1。编码规则如下:若xxr，则D2=1，否则D2=0；若yyt，则D4=1，否则D4=0。D4D3D2D1上下右左Cohen-Sutherland算法0000窗口01000101100100011010011010000010D3D2D1D0ABCDEFCohen-Sutherland算法GH端点编码：定义为端点所在区域的编码结论：当线段的两个端点的编码的逻辑“与”非零时，线段为显然不可见的当线段的两个端点的编码的逻辑”或“为零时，线段为完全可见的IJ求交测试顺序固定最坏情形，线段求交四次。Cohen-SutherLand算法对于那些非完全可见、又非显然不可见的线段，需要求交求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值D4D3D2D1）0000窗口01000101100100011010011010000010D3D2D1D0裁剪一条线段时，先求出端点p1和p2的编码code1和code2，然后：(1)若code1|code2=0，对直线段应“简取”之。(2)若code1&code2≠0，对直线段可“简弃”之。(3)若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。Cohen-Sutherland算法中点分割算法基本思想：当对直线段不能简取也不能简弃时，简单地把线段等分为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外。 p1p2p3p4p5p6p7例×××p1p2中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点。Nicholl-Lee-Nicholl算法消除C-S算法中多次求交的情况。基本想法：对2D平面的更细的划分。更快的线段裁剪算法基于线段的参数化方程的分析，它是由粱友栋和Barsky提出的，也称为粱友栋-Barsky线段裁剪算法。设线段两端点坐标分别为P1(x1,y1)和P2(x2,y2),则其参数化直线方程可写成下列形式：0≤u≤1参数化线段裁剪算法坐标(x,y)

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf

示直线上两端点之间的任一点。当u=0时，得点P1，当u=1时，得点P2。线段的裁剪条件可以由下面的不等式表示：Wxl≤x1﹢uΔx≤WxrWyb≤y1﹢uΔy≤Wyt这四个不等式可以表示为：upk≤qkk=1,2,3,4Δx=x2-x1;Δy=y2-y1;其中，参数p,q定义为：p1﹦-Δx,q1﹦x1﹣Wxlp2﹦Δx,q2﹦Wxr﹣x1p3﹦-Δy,q3﹦y1﹣Wybp4﹦Δy,q4﹦Wyt﹣y1下标k=1,2,3,4分别对应裁剪窗口的左、右、下、上四条边界线。如果线段平行于裁剪窗口的某两边界，则必有相应的pk﹦0，如果还满足qk＜0，则线段的端点位于窗口外部，即线段在窗口外，应该舍弃。如果qk≥0，线段在窗口内。当pk＜0时，若直线与裁剪窗口第k条边界线相遇，则必是从边界线外部延伸到内部。例如当p1＜0时，则x2＞x1,直线必然从裁剪窗口的左边界线的外部进入内部，如下图中的线段P1P2。当pk＞0时，若直线与裁剪窗口第k条边界线相遇，则必是从边界线的内部延伸到外部。例如p2＞0时，则x2＞x1,直线必然从裁剪窗口的右边界线的内部进入外部,如下图中的线段P3P4。当pk不等于零时，可以计算出线段与第k条裁剪窗口边界线的交点参数：根据定义，对于每条线段，pk中必有两个小于零，而另两个大于零。对于小于零的pk，直线同第k条裁剪窗口边线是从外到内相遇的，此时如果线段同第k条裁剪窗口边界线有交点的话，是参数u从0变大时遇到的，这时计算出相应的rk值，取0和各个rk值之中的最大值记为u1。对于大于零的pk，计算出相应的rk值，取1和各个rk值之中的最小值记为u2。两个参数u1和u2定义了在裁剪窗口内的线段部分。如果u1＞u2，则线段完全落在裁剪窗口之外，应被舍弃。否则被裁剪线段可见部分的端点由参数u1和u2计算出来。梁友栋线的裁剪算法例子设：Wxl=2;Wxr=4;Wyb=2;Wyt=4被裁剪线段的两端点：（1，2），（5，3）计算：Δx=5-1=4Δy=3-2=1p1=-4，q1=-1p2=4，q2=3p3=-1，q3=0p4=1，q4=2p1﹦-Δx,q1﹦x1﹣Wxlp2﹦Δx,q2﹦Wxr﹣x1p3﹦-Δy,q3﹦y1﹣Wybp4﹦Δy,q4﹦Wyt﹣y1ABp1，p3小于0，决定u1(max)，取0与r1和r3中的大者，u1=1/4p2，p4大于0，决定u2，取1与r2和r4中的小者，u2=3/4两交点由u1，u2决定：计算：(1)(2)通常粱友栋-Barsky算法比Cohen-Sutherland算法更有效，因为需要计算的交点数目减少了。一次计算就可以确定出线段的可见性及可见部分。这两种线段裁剪算法都可以扩展为三维线段裁剪算法。多边形裁剪用直线段裁剪算法，可以吗？新的问题：图1因丢失顶点信息而去法确定裁剪区域ABAB图2原来封闭的多边形变成了孤立的线段关键：求出新的顶点，删去界外顶点形成正确的顶点序列Sutherland-Hodgman算法分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：左边的结果是右边的开始。亦称逐边裁剪算法Sutherland-Hodgman算法可见一侧空间和不可见一侧空间沿多边形依次处理顶点会遇到四种情况线段与当前裁剪边的位置关系可见一侧窗口(a)输出Pi+1当前裁剪边Pi+1Pi可见一侧窗口(a)无输出当前裁剪边Pi+1Pi可见一侧窗口(a)输出I当前裁剪边Pi+1Pi可见一侧窗口(a)输出I和Pi+1当前裁剪边Pi+1PiSutherland-Hodgman算法裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点。顺序连接。几点说明：裁剪算法采用流水线方式，适合硬件实现。可推广到任意凸多边形裁剪窗口例子：对多边形ABCDEFGH进行裁剪ABCDEFGH练习：试用S-H算法裁剪下图多边形，要求画出每次裁剪对应的图形，并表明输入输出的顶点。A(4,1)B(5,4)022xy66E(1,5)D(6,8)C(8,1)解：用左边界裁剪前后为：C(8,1)A(4,1)B(5,4)022xy66M(2,5.6)D(6,8)N(2,3.6)A(4,1)B(5,4)022xy66E(1,5)D(6,8)C(8,1)输入为：ABCDE输出为：BCDMNA2.如下图所示，裁减窗口为正方形，采用逐边裁件算法，依次按左、下、右、上的顺序，用四条窗口边界裁减多边形ABCDE。试写出每条框口边界裁减后输出的新的多边形的顶点序列。答：左边界裁减后：ABCD12下边界裁减后：4B56D123右边界裁减后：4B7D123上边界裁减后：4B789123