CG No6-图形变换 3.ppt

《CG No6-图形变换 3.ppt》由会员分享，可在线阅读，更多相关《CG No6-图形变换 3.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、CG No6-图形变换图形变换 3Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo本章内容本章内容 u 1、图形变换的数学基础、图形变换的数学基础u 2、二维图形变换、二维图形变换u 3、三维图形变换、三维图形变换u 4、投影变换、投影变换u 5、裁剪、裁剪Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo七、裁剪七、裁剪u裁剪：确定图形中哪些部分落在显示区之内，哪些落在显裁剪：确定

2、图形中哪些部分落在显示区之内，哪些落在显示区之外示区之外, ,以便只显示落在显示区内的那部分图形。这个以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。选择过程称为裁剪。Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo预备知识预备知识 u 交点计算交点计算u 1. 两直线段的交点两直线段的交点u 设有两线段设有两线段S1，S2。S1的端点分别为的端点分别为P1(x1,y1),P2(x2,y2), S2的端点分别的端点分别为为P3(x3,y3), P4(x4,y4).则两直线段的参

3、数方程为：则两直线段的参数方程为： 13)43()12(13)43()12(:;3)34(1)12(;3)34(1)12(:)10(3)34(3)34(:2)10(;1)12(;1)12(:1yyvyyuyyxxvxxuxxyvyyyuyyxvxxxuxx，vyvyyyxvxxxSuyuyyyxuxxxS上式可进一步整理成则应满足如果两直线段能相交显然Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou 讨论：讨论：u 无解：此时意味两线段平行或重合；无解：此时意味两线段平行或重合；u 有

4、唯一解：但不一定是有效解，有效解应该是交点必须位于两直线段上。有唯一解：但不一定是有效解，有效解应该是交点必须位于两直线段上。此时应满足如下条件：此时应满足如下条件： 0u1.0 0v1.0 0u1.0 0v1.0 。根据。根据u,vu,v的值，即的值，即可获得交点的坐标。可获得交点的坐标。u 2. 直线段与圆弧的交点直线段与圆弧的交点。tryytyyrxxtxx：ryyrxxr、yxctytyyyxtxxxccescccc值和联立求解即可获得则有如果直线段和圆弧相交的圆弧方程为半径为圆心为假定直线段的方程如下sin*1)12(cos*1)12()(sin*cos*:),()0.10(1)12

5、(1)12(:Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo点的裁剪点的裁剪u是图形裁剪中最基本的问题。是图形裁剪中最基本的问题。 u假设窗口的左下角坐标为假设窗口的左下角坐标为(xL,yB),右上角坐标为右上角坐标为(xR,yT)，对，对于给定点于给定点P(x,y),则则P点在窗口内的条件是要满足下列不等式：点在窗口内的条件是要满足下列不等式： xL = x = xR并且并且yB = y xr线段的起点坐标可能线段的起点坐标可能位于位于6区、区、7区、区、8区。区。而新起点的坐标可能

6、在而新起点的坐标可能在直线直线y= yb和线段的交点上和线段的交点上直线直线y= yt和线段的交点上和线段的交点上直线直线x= xr和线段的交点上和线段的交点上012345678(x1,y1)ybytxlxrComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou第一种情况：第一种情况：u 此时，若此时，若xlxs xr 则则(xs ys)为有效新起点。为有效新起点。u第二种情况：第二种情况：u 此时，若此时，若xlxs xr 则则(xs ys)为有效新起点。为有效新起点。u第三种情况：第三种

7、情况：u u 此时，若此时，若ybys yt 则则(xs ys)为有效新起点。为有效新起点。u若此三种情况都不满足，则此线段不在窗口区内。若此三种情况都不满足，则此线段不在窗口区内。bsbyyyyxxyyxx)/()(121211ststyyyyxxyyxx)/()(121211s)/()(y121211sxxyyxxyxxrrsComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou若若Xl=X=Xru线段的起点坐标可能线段的起点坐标可能u位于位于1区和区和2区。区。u而新起点的坐标可能在而

8、新起点的坐标可能在u直线直线y= yb和线段的交点上和线段的交点上u直线直线y= yt和线段的交点上和线段的交点上012345678(x1,y1)ybytxlxrComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo第一种情况：第一种情况： 此时，若此时，若xlxs xr 则则(xs ys)为有效新起点。为有效新起点。第二种情况：第二种情况： 此时，若此时，若xlxs xr 则则(xs ys)为有效新起点。为有效新起点。若此二种情况都不满足，则此线段不在窗口区内。若此二种情况都不满足，则此线段

9、不在窗口区内。使用同样的方法，可得到直线在窗口的另一个可见端点。使用同样的方法，可得到直线在窗口的另一个可见端点。xxxxyyyyyystst010010()() /()xxxxyyyyyysbsb010010()()/()Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo（二）（二）Cohen - SutherLand 算法（编码法）算法（编码法）基本思想是：基本思想是：1)1)首先判断线段是否完全位于窗口内，如果是，则输出原线首先判断线段是否完全位于窗口内，如果是，则输出原线段，如果不

10、是，那么再进而判断是否完全位于窗口外，若段，如果不是，那么再进而判断是否完全位于窗口外，若是，则排除该线段，无输出。是，则排除该线段，无输出。2)2)如果以上测试都不满足的话，那么就将该线段用窗口边线如果以上测试都不满足的话，那么就将该线段用窗口边线分割为二段，然后再回到分割为二段，然后再回到1)1)进行上述测试。进行上述测试。Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou实现方法：实现方法：u u将窗口边线两边沿长，得到九个区域，每一个区域都将窗口边线两边沿长，得到九个区域，每一个

11、区域都用一四位二进制数标识，直线的端点都按其所处区域用一四位二进制数标识，直线的端点都按其所处区域赋予相应的标识码。赋予相应的标识码。100100010101100000000100101000100110ABCDw1w2w4w3Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo第一位第一位 1：点处于左边框线的左边；：点处于左边框线的左边；第二位第二位 1：点处于右边框线的右边；：点处于右边框线的右边；第三位第三位 1：点处于下边框线的下边；：点处于下边框线的下边；第四位第四位 1：点处

12、于上边框线的上边；：点处于上边框线的上边；显然：显然：如果某线段的两端点的两个四位代码全为零时那么该线段如果某线段的两端点的两个四位代码全为零时那么该线段完全位于窗口内；如果两端点的标识码的逻辑乘不为零，完全位于窗口内；如果两端点的标识码的逻辑乘不为零，那么该线段必位于窗口外。那么该线段必位于窗口外。如果线段被分割，端点有了新的代码，然后再进行上述测试，如果线段被分割，端点有了新的代码，然后再进行上述测试，测试结果是必有一段在窗口之外，可被排除，另一段再重测试结果是必有一段在窗口之外，可被排除，另一段再重复上述处理过程。复上述处理过程。Computer Graphics 计算机图形学计算机图形

13、学LinYi University School of Informatics Wang Libo裁剪步骤：裁剪步骤：1.编码：计算端点坐标与窗口边界之差编码：计算端点坐标与窗口边界之差 用每次差运算结果的符号位来设置区域代码的对应位置。用每次差运算结果的符号位来设置区域代码的对应位置。即第一位为即第一位为x-w1的符号位，第二位为的符号位，第二位为w2-x的符号位，第三的符号位，第三位为位为y-w3的符号位，第四位为的符号位，第四位为w4-y的符号位。的符号位。2.判别：判别： 线段两端点均在窗口内，两端点编码均为线段两端点均在窗口内，两端点编码均为0000 线段两端点均不在窗口内，两端点编

14、码均不为线段两端点均不在窗口内，两端点编码均不为0000 线段只有一个端点在窗口内，则只有一个端点编码为线段只有一个端点在窗口内，则只有一个端点编码为00003.裁剪原则：裁剪原则： 1）两点均为）两点均为0000，保留，保留 2）两端点编码进行）两端点编码进行“与与”运算，如果结果不为运算，如果结果不为0000，则在，则在窗口外窗口外 3） 若若“与与”的结果为的结果为0000，要求交点，要求交点Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo4.求交点求交点 对需要求交点的线段，逐步

15、与窗口边界比较，分别令对需要求交点的线段，逐步与窗口边界比较，分别令x=w1,或或x=w2，或，或y=w3,或或y=w4 并代入两直线的交点方程：并代入两直线的交点方程： (y-y1)/(y2-y1)=(x-x1)/(x2-x1) 求出交点求出交点(x,y)5.循环测试裁剪，直到结束。循环测试裁剪，直到结束。Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo（三）中点分割算法（三）中点分割算法u定义：线段端点的最远可见点是指任一线段被窗口裁剪后定义：线段端点的最远可见点是指任一线段被窗口裁

16、剪后所得两个新端点中离该端点较远的一个点。如下图所示。所得两个新端点中离该端点较远的一个点。如下图所示。uA的最远可见点为的最远可见点为a, uB的最远可见点为的最远可见点为b.u中点分割法的基本思想即是：中点分割法的基本思想即是：u从从A点出发找出距点出发找出距A最近的可见点最近的可见点u从从B点出发找出距点出发找出距B最近的可见点最近的可见点u不断地在中点处将线段一分为二，对每段线段重复不断地在中点处将线段一分为二，对每段线段重复Cohen-Sutherland裁剪算法的线段可见性测试方法，直至找到每裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视

17、段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止为一点为止 ABabComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo实现算法实现算法从从P0出发找距离出发找距离P0最近可见点采用中点分割方法最近可见点采用中点分割方法u先求出先求出P0P1的中点的中点Pm,u若若P0Pm不是显然不可见的，并且不是显然不可见的，并且P0P1在窗口中有可见部分，则距在窗口中有可见部分，则距P0最近的可见点一定落在最近的可见点一定落在P0Pm上，所以用上，所以用P0Pm代替代替P0P1；u否则取否则

18、取PmP1代替代替P0P1。u再对新的再对新的P0P1求中点求中点Pm。重复上述过程，直到。重复上述过程，直到PmP1长度小于给定长度小于给定的控制常数为止，此时的控制常数为止，此时Pm收敛于交点。收敛于交点。u 从从P1出发找距离出发找距离P1最近可见点采用上面类似方法。最近可见点采用上面类似方法。P0P1PmABComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang LiboComputer Graphics 计算机图形学计算机图形学LinYi University School of Inform

19、atics Wang Libo（四）梁友栋（四）梁友栋-Barsky算法算法uCohen-Sutherland算法用编码的方法实现了对完全可见和算法用编码的方法实现了对完全可见和不可见直线段的快速接受和拒绝。比较适合两种情况：一不可见直线段的快速接受和拒绝。比较适合两种情况：一是大部分线段完全可见；二是大部分线段完全不可见。是大部分线段完全可见；二是大部分线段完全不可见。u在在Cohen-Sutherland算法提出后，算法提出后，Cyrus和和Beck用参数化用参数化方法提出了针对凸多边形的裁剪算法，它比编码算法更有方法提出了针对凸多边形的裁剪算法，它比编码算法更有效。而梁友栋和效。而梁友栋

20、和Barsky 又针对标准矩形窗口提出了更快的又针对标准矩形窗口提出了更快的Liang-Barsky直线段裁剪算法。直线段裁剪算法。Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo设要裁剪的线段是设要裁剪的线段是P0P1。P0P1和窗口边界交于和窗口边界交于A,B,C,D四点，见图。算法的基本思想四点，见图。算法的基本思想是从是从A,B和和P0三点中找出最靠三点中找出最靠近的近的P1点，图中要找的点是点，图中要找的点是P0。从。从C,D和和P1中找出最靠近中找出最靠近P0的点。图中要找的

21、点是的点。图中要找的点是C点。点。那么那么P0C就是就是P0P1线段上的可线段上的可见部分。见部分。Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo线段的参数表示线段的参数表示x=x0+txy=y0+ty 0=t tl,则可见线段区间则可见线段区间 tl , tut0t1t2t301Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo始边和终边的确定及交点计算：始边和终边的确定及交点计

22、算：令令 QL= - x DL= x0-xL QR= x DR= xR-x0 QB= - y DB= y0-yB QT= y DT= yT-y0交点为交点为 ti= Di / Qi i=L,R,B,TQi 0 ti为与终边交点参数为与终边交点参数Qi =0 Di 0 时时, 分析另一分析另一D,EFABComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo当当Qi =0时时 若若Di 0 时时,线段不可见线段不可见（如图中（如图中AB，有，有QR=0，DR0 时时, 分析另一分析另一D, （如

23、图中的（如图中的EF就是这种情况，它使就是这种情况，它使QL=0，DL0和和QR=0，DR0。这时。这时由于由于EF和和x=xL及及x=xR平行，故不必平行，故不必去求出去求出EF和和x=xL及及x=xR的交点，而的交点，而让让EF和和y=yT及及y=yB的交点决定直线的交点决定直线段上的可见部分。）段上的可见部分。）EFABComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo（五）多边形的布尔运算（五）多边形的布尔运算1 1） 布尔运算的概念布尔运算的概念 多边形的布尔运算指的是在两个多边

24、形之间进行的并、交、差运算。多边形的布尔运算指的是在两个多边形之间进行的并、交、差运算。下图分别表示了三种运算的含义下图分别表示了三种运算的含义。ABABABA-BComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo2） 多边形的描述多边形的描述 多边形可看成是由一组顶点按一定顺序连接而成的有向点列。多边形可看成是由一组顶点按一定顺序连接而成的有向点列。为以后处理方便，将多边形的顶点按逆时针方向顺序连接成一为以后处理方便，将多边形的顶点按逆时针方向顺序连接成一个环来描述多边形的组成。而顺序连

25、接两点的直线段，表示了个环来描述多边形的组成。而顺序连接两点的直线段，表示了一有向线段。该环可用一链表结构描述。一有向线段。该环可用一链表结构描述。上面多边形可描述为：上面多边形可描述为：1-2-3-4-1的链表形式。的链表形式。1243Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo3） 布尔运算规则布尔运算规则 两个多边形能进行布尔运算的前提是这两个多边形必两个多边形能进行布尔运算的前提是这两个多边形必须有相互重叠部分。这可通过多边形重叠性检验来判断。须有相互重叠部分。这可通过多边形

26、重叠性检验来判断。以下讨论假定两个多边形重叠。以下讨论假定两个多边形重叠。u出点、入点出点、入点 当两个多边形重叠时，可用描述多边形的两个环相交来当两个多边形重叠时，可用描述多边形的两个环相交来描述。其交点将相交的两条有向线段分为环内部分和环描述。其交点将相交的两条有向线段分为环内部分和环外部分。外部分。a1a2a3a4a5b1b2b3b4Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo 当一个环的有向线段经过交点进入另一环，该交点相对当一个环的有向线段经过交点进入另一环，该交点相对于该

27、有向线段称为入点，而当走出另一环时，该点则称于该有向线段称为入点，而当走出另一环时，该点则称为出点。为出点。运算规则运算规则 为说明方便，以下图为例说明，并假定交点为为说明方便，以下图为例说明，并假定交点为9， 10。a1a2a3a4a5b1b2b3b4Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo两多边形相交产生新的顶点，各环两多边形相交产生新的顶点，各环的结构发生如下变化：的结构发生如下变化：多变形多变形A：1-9-2-10-3-4-1；多边形；多边形B：5-6-7-10-8-9-

28、5；布尔运算就是要根据布尔运算类型，布尔运算就是要根据布尔运算类型，由由A、B两环构造两环构造一新的环一新的环C，它由上述点重新组合而，它由上述点重新组合而成。在进行布尔运算成。在进行布尔运算时，搜索路径应从交点开始。时，搜索路径应从交点开始。12345678910ABComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou并运算规则并运算规则 顺着一环的方向搜索，当遇到一交点时，分以下两种情况：顺着一环的方向搜索，当遇到一交点时，分以下两种情况： 1）当该点为环的入点时，则从该点在另一环上的

29、对应点转入另一环，）当该点为环的入点时，则从该点在另一环上的对应点转入另一环，而沿另一环的方向搜索；而沿另一环的方向搜索； 2）当该点为环的出点时，则继续沿原环搜索。）当该点为环的出点时，则继续沿原环搜索。123456789101-9-2-10-3-4-15-6-7-10-8-9-5 9-5-6-7-10-3-4-1-9Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou交运算规则交运算规则 顺着一环的方向搜索，当遇到一交点时，分以下两种情况：顺着一环的方向搜索，当遇到一交点时，分以下两种

30、情况： 1）当该点为环的出点时，则从该点在另一环上的对应点转入另一）当该点为环的出点时，则从该点在另一环上的对应点转入另一环，而沿另一环的方向搜索；环，而沿另一环的方向搜索； 2）当该点为环的入点时，则继续沿原环搜索。）当该点为环的入点时，则继续沿原环搜索。1-9-2-10-3-4-15-6-7-10-8-9-510-8-9-2-1012345678910Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou差运算差运算 在进行差运算的时候，首先要将差环的方向倒转过来，在进行差运算的时候，首

31、先要将差环的方向倒转过来，( (但环上交点的属性不变但环上交点的属性不变) )然后按照并运算相同规则进行然后按照并运算相同规则进行处理。如下图所示。处理。如下图所示。123456789101-9-2-10-3-4-15-6-7-10-8-9-510-3-4-1-9-8-10环1环2Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo4） 算法步骤算法步骤（1）建立参加布尔运算的多边形的环表；）建立参加布尔运算的多边形的环表；（2）判断两多边形的重叠关系；）判断两多边形的重叠关系；（3）求出两

32、多边形的有效交点，扩充各多边形的环表，并标）求出两多边形的有效交点，扩充各多边形的环表，并标识交点的属性（出点、入点）；识交点的属性（出点、入点）；（4）以一个交点为出发点，按布尔运算规则进行搜索；）以一个交点为出发点，按布尔运算规则进行搜索；（5）按照搜索路径，在顶点之间连线输出。）按照搜索路径，在顶点之间连线输出。Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo( (六六) )多边形裁剪多边形裁剪u裁剪裁剪就是将指定窗口作为图形边界，将窗口内的图形保留，就是将指定窗口作为图形边界，将

33、窗口内的图形保留，而窗口外的图形则被舍弃。而窗口外的图形则被舍弃。u多边形裁剪多边形裁剪是指任意多边形经裁剪以后落在裁剪窗口内的是指任意多边形经裁剪以后落在裁剪窗口内的一系列可见线段一系列可见线段, ,正确地连接成一个或数个封闭的多边形。正确地连接成一个或数个封闭的多边形。u多边形边界是直线段的组合，那么能否利用线段裁剪算多边形边界是直线段的组合，那么能否利用线段裁剪算法？法？Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo主多边形主多边形Computer Graphics 计算机图形学

34、计算机图形学LinYi University School of Informatics Wang Libo(a)(a)裁剪前裁剪前(b)(b)直接采用直线段裁剪的结果直接采用直线段裁剪的结果Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo问题问题u1 1）因为边界不再封闭，需要用窗口边界的恰当部分来封）因为边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？闭它，如何确定其边界？裁剪结果多边形的边由裁剪多边形和主多边形的边裁剪结果多边形的边由裁剪多边形和主多边形的边（边的一

35、部分）构成（边的一部分）构成Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou2 2）一个凹多边形可能被裁剪成几个小的多边形，如何确）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？定这些小多边形的边界？Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang LiboSutherland-Hodgman算法算法uSutherland-Hodgman算法也叫逐边裁剪法，该算法是萨

36、瑟算法也叫逐边裁剪法，该算法是萨瑟兰德兰德(IESutherland)和霍德曼和霍德曼(Hodgman)在在1974年提出年提出的。这种算法采用了分割处理、逐边裁剪的方法。的。这种算法采用了分割处理、逐边裁剪的方法。u其其基本思想基本思想是将多边形边界作为一个整体，每次用窗口的是将多边形边界作为一个整体，每次用窗口的一条边界对要裁剪的多边形进行裁剪。窗口各边界裁剪的一条边界对要裁剪的多边形进行裁剪。窗口各边界裁剪的多边形存储在输入与输出顶点表。在窗口的一条裁剪边界多边形存储在输入与输出顶点表。在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界处理完所有顶点后，其输出顶点表将

37、用窗口的下一条边界继续裁剪。继续裁剪。Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou每次裁剪时把落在窗口外部区域的图形去掉，只保留落在每次裁剪时把落在窗口外部区域的图形去掉，只保留落在窗口内部区域的图形，并把它作为下一次裁剪的多边形。窗口内部区域的图形，并把它作为下一次裁剪的多边形。依次用窗口的四条边界对要裁剪的多边形进行裁剪，则原依次用窗口的四条边界对要裁剪的多边形进行裁剪，则原始多边形即被裁剪完毕。始多边形即被裁剪完毕。u窗口的一条边及其延长线构成的裁剪线把平面分为两个区窗口的一

38、条边及其延长线构成的裁剪线把平面分为两个区域：包含有窗口区域的一个域称为可见侧；不包含窗口区域：包含有窗口区域的一个域称为可见侧；不包含窗口区域的域为不可见侧。域的域为不可见侧。Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo输入：ABCDEFGHABCDEFGH输出：A12DEFGH12(a)用左边界裁剪输出：A134D56FGHADEFGH输入：A12DEFGH12(b)用下边界裁剪3456Computer Graphics 计算机图形学计算机图形学LinYi University

39、School of Informatics Wang Libou沿着多边形依次处理顶点会遇到四种情况：沿着多边形依次处理顶点会遇到四种情况：u 一是第一点一是第一点S S在不可见侧面而第二点在不可见侧面而第二点P P在可见侧，则多边形的该边与窗在可见侧，则多边形的该边与窗口边界的交点口边界的交点I I与第二点与第二点P P均被加入到输出顶点表中。均被加入到输出顶点表中。u 二是二是S S和和P P都在可见侧，则都在可见侧，则P P被加入到输出顶点表中；被加入到输出顶点表中；u 三是三是S S在可见侧，而在可见侧，而P P在不可见侧，则交点在不可见侧，则交点I I被加入到输出顶点表中。被加入到输

40、出顶点表中。u 四是如果四是如果S S和和P P都在不可见侧，输出顶点表中不增加任何顶点都在不可见侧，输出顶点表中不增加任何顶点。SPI(a)输出I、P可见侧SP(b)输出P可见侧SPI(c)输出I可见侧SP(d)不输出可见侧Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou算法算法u将顶点序列将顶点序列P P1 1P P2 2P Pn n作为输入作为输入u依次对窗口的每条裁剪线作下列处理依次对窗口的每条裁剪线作下列处理u输入顶点序列输入顶点序列u依次顶点序列中相邻顶点构成的边依次顶点序

41、列中相邻顶点构成的边P Pi iP Pi i+1+1进行裁剪处进行裁剪处理理u输出顶点序列（下条裁剪线的输入）输出顶点序列（下条裁剪线的输入）Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libo例子例子上：输入上：输入 I1P2P3P4P5P6P7P8I2 输出输出 P2I3I4P4P5P6P7P8I2I1下：输入下：输入 I3I4P4I5I6P6P7P8I2I1P2 输出输出 I4P4I5I6I7I8P8I2I1P2I3左：输入左：输入 P1P2P3P4P5P6P7P8 输出输出 I1P2

42、P3P4P5P6P7P8I2右：输入右：输入 P2I3I4P4P5P6P7P8I2I1 输出输出 I3I4P4I5I6P6P7P8I2I1P2注意：注意：（1）交点是边与裁剪线的交点）交点是边与裁剪线的交点（2）边的顶点是有序的）边的顶点是有序的Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou特点特点u裁剪算法采用流水线方式，算法简单裁剪算法采用流水线方式，算法简单u推广到任意凸多边形裁剪窗口推广到任意凸多边形裁剪窗口 原因是：凸多边形的边能将平面空间分成原因是：凸多边形的边能将平面空

43、间分成2 2部分，其部分，其中一部分含裁剪窗口中一部分含裁剪窗口Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这几个多边形沿边框产生多余的线段？这几个多边形沿边框产生多余的线段？ 逐边裁剪法对凹多边形裁剪时可能出现的问题逐边裁剪法对凹多边形裁剪时可能出现的问题321876954103217654108932174108956原图对左边裁对顶边裁32174108956对右边裁对底边裁

44、Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang LiboWeiler-Atherton算法算法u1977年年Weiler-Atherton提出用主多边形提出用主多边形P（用户图形）的（用户图形）的边裁剪多边形边裁剪多边形C（窗口），某些情况下，用（窗口），某些情况下，用C 的边裁剪的边裁剪P的的算法。算法。裁剪窗口、被裁剪多边形可以是任意多边形：凸的、裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于凹的（内角大于180180o o）、甚至是带有内环的（子区），见）、甚至是带有内环的（

45、子区），见下图。下图。 主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为A A 裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为B BComputer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou主多边形主多边形A和裁剪多边形和裁剪多边形B的边界将整个二维平面分成了四的边界将整个二维平面分成了四个区域：个区域：1、AB（交：属于（交：属于A且属于且属于B）；）；2、AB（差：属于（差：属于A不属于不属于B）；）；3、BA（差：属于（差：属于B不属于不属于A）；）；4、AB(并：属于并：属

46、于A或属于或属于B，取反；即：不属于，取反；即：不属于A且且不属于不属于B)。u内裁剪内裁剪即通常意义上的裁剪，取图元位于窗口之内的即通常意义上的裁剪，取图元位于窗口之内的部分，结果为部分，结果为AB。u外裁剪外裁剪取图元位于窗口之外的部分，结果为取图元位于窗口之外的部分，结果为AB。Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou该算法的基本思想是：该算法的基本思想是：有时沿着多边形的方向来处理顶点，有时沿着多边形的方向来处理顶点，有时沿窗口的边界方向来处理。采用哪一条路径，要根据有

47、时沿窗口的边界方向来处理。采用哪一条路径，要根据多边形处理方向多边形处理方向(顺时针或逆时针顺时针或逆时针)和当前处理的多边形顶和当前处理的多边形顶点对是点对是由外到内由外到内还是还是由内到外由内到外。如果顺时针处理顶点，则。如果顺时针处理顶点，则采用下列规则采用下列规则 u a.对由外到内的顶点对，沿多边形边界的方向对由外到内的顶点对，沿多边形边界的方向 u b.对由内到外的顶点对，按顺时针沿窗口边界的方向对由内到外的顶点对，按顺时针沿窗口边界的方向 Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wa

48、ng Libo裁剪思路：裁剪思路：对于一个顶点集合有序排列的封闭多边形，从其任对于一个顶点集合有序排列的封闭多边形，从其任意一点出发，按照顶点排列顺序（顺时针或逆时针），跟踪检意一点出发，按照顶点排列顺序（顺时针或逆时针），跟踪检测多边形测多边形P的每一条边。当的每一条边。当P的边和窗口的边和窗口C的有效边框相交时，的有效边框相交时，按两种情况处理：按两种情况处理： 1.若若P的边是进入的边是进入C(记下交点记下交点)，则算法继续沿，则算法继续沿P的边往下处理。的边往下处理。 2.若若P的边是从的边是从C出来出来(记下交点记下交点)，则算法从交点开始，沿窗口，则算法从交点开始，沿窗口C边框顺序

49、（顺：向右，逆：向左）检测边框顺序（顺：向右，逆：向左）检测C的边。若的边。若C 的边框的边框与前交点右边的与前交点右边的P的边有交点，则返回到前交点继续处理的边有交点，则返回到前交点继续处理P的边，的边，直到遇到起点为止。直到遇到起点为止。P2P1P3P4P5P6ACBDAP2P3BCDP5Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou内裁剪的特点内裁剪的特点u裁剪结果区域的边界由裁剪结果区域的边界由A的部分边的部分边 界和界和B的部分边界两部分构成，的部分边界两部分构成， 并且在

50、交点处边界发生交替，即由并且在交点处边界发生交替，即由A 的边界转至的边界转至B的边界，或由的边界，或由B的边界的边界 转至转至A的边界的边界Computer Graphics 计算机图形学计算机图形学LinYi University School of Informatics Wang Libou交点交点u交点成对出现：既在交点成对出现：既在A中也在中也在B中中u两类：两类：（1）进点：进点：主多边形边界由此进入裁剪多边形内主多边形边界由此进入裁剪多边形内 如，如，I1, I3, I5, I7, I9, I11（2）出点：出点：主多边形边界由主多边形边界由此离开裁剪多边形区域此离开裁剪多边形