计算机图形学第四章课件

1、计算机图形学第四章第四章第四章 窗口与裁剪技术窗口与裁剪技术教学目的：教学目的： 通过本章的学习，应让学生掌通过本章的学习，应让学生掌握窗口与视区的概念以及它们之间的转握窗口与视区的概念以及它们之间的转换过程；熟练掌握二维直线段的裁剪算换过程；熟练掌握二维直线段的裁剪算法及多边形的裁剪。法及多边形的裁剪。本章重点：本章重点： 二维直线段的裁剪算法及多边形的裁二维直线段的裁剪算法及多边形的裁剪剪本章难点：本章难点： 逐次多边形裁剪算法，中点再分直线逐次多边形裁剪算法，中点再分直线法法计算机图形学第四章内内 容容4.1 4.1 坐标系统坐标系统4.2 4.2 窗口窗口- -视区变换视区变换4.3

2、4.3 图形裁剪图形裁剪 直线段裁剪直线段裁剪 多边形裁剪多边形裁剪 字符裁剪字符裁剪计算机图形学第四章4.14.1 坐标系统坐标系统在计算机图形学中，常使用以下几种直角坐标系：在计算机图形学中，常使用以下几种直角坐标系：一、世界坐标系一、世界坐标系wc wc （world coordinateworld coordinate）（用户坐标系）（用户坐标系）图形学中常用的坐标系统，是右手三维直角坐标系图形学中常用的坐标系统，是右手三维直角坐标系 ，长，长度单位由用户自定，取值范围是整个实数域度单位由用户自定，取值范围是整个实数域二、目标系二、目标系ecec（eye coordinateeye c

3、oordinate）（观察坐标法）（观察坐标法）是左手三维直角坐标系是左手三维直角坐标系ecec三、设备坐标系三、设备坐标系dc dc （device coordinatedevice coordinate）是关于图形设备用的坐标，一般都采用二维直角坐标系，是关于图形设备用的坐标，一般都采用二维直角坐标系，但坐标原点及坐标轴方向都因具体设备的不同而不同。取值范但坐标原点及坐标轴方向都因具体设备的不同而不同。取值范围是整数的有限区域。围是整数的有限区域。 四、规格化设备坐标系四、规格化设备坐标系ndcndc（normalized device coordinatenormalized devic

4、e coordinate）是一种虚拟的坐标系统，它与具体的设备无关，通过它可是一种虚拟的坐标系统，它与具体的设备无关，通过它可以把以把wcwc与与dcdc联系起来，联系起来，ndcndc的坐标值在的坐标值在0101之间。之间。计算机图形学第四章三种坐标系间的关系三种坐标系间的关系dcdcdcpn（xn，yn）ndc11wcpw（xw，yw）hwww（wxl，wyb）计算机图形学第四章坐标系统坐标系统通过通过ndcndc，可以建立两种坐标系之间一一对应的相互关系，可以建立两种坐标系之间一一对应的相互关系，使用户在用使用户在用wcwc描述物体图形时，能在具体的物理图形设备上正描述物体图形时，能在具

5、体的物理图形设备上正取输出。这两种坐标系的转换分别为：取输出。这两种坐标系的转换分别为：（1 1）wcwc到到dncdnc的转换的转换如上图，从如上图，从wcwc中一点中一点p pw w（x xw w，y yw w）变换到）变换到ndcndc中一点中一点pnpn（xnxn，ynyn）的关系为）的关系为xn=(xw-wxl)/wwxn=(xw-wxl)/wwyn=(yw-wyb)/hwyn=(yw-wyb)/hw（2 2）ndcndc到到dcdc的转换的转换实际上，对每一个具体设备而言，这两种坐标系的坐标值实际上，对每一个具体设备而言，这两种坐标系的坐标值也仅差一个比例因子，把前者的坐标值乘上这

6、一比例因子即可也仅差一个比例因子，把前者的坐标值乘上这一比例因子即可得后者的坐标值。得后者的坐标值。计算机图形学第四章4.24.2 窗口视区变换窗口视区变换一、用户域和窗口一、用户域和窗口用户域是指整个自然空间，实数域，连续的，无用户域是指整个自然空间，实数域，连续的，无限的。限的。窗口是其中的一部分（子集）一般为矩形。窗口是其中的一部分（子集）一般为矩形。二、屏幕域和视图区屏幕域和视图区：屏幕域是设备输出的最大区域，整数域，有限的。屏幕域是设备输出的最大区域，整数域，有限的。视区只是其中的一部分。视区只是其中的一部分。三、窗口与视区：三、窗口与视区：视区是窗口影射到显示设备上的（矩形）区域。

7、视区是窗口影射到显示设备上的（矩形）区域。计算机图形学第四章窗口视区变换窗口视区变换四、窗口四、窗口- -视区的变换视区的变换：1 1、变换的意义：、变换的意义：用户在用户在wcwc中绘图时，可以选择不同的度量单位，中绘图时，可以选择不同的度量单位，而显示屏上的图形是以屏幕为坐标系，使用整数而显示屏上的图形是以屏幕为坐标系，使用整数坐标的象素来度量的。对某种显示器来说，显示坐标的象素来度量的。对某种显示器来说，显示数据的范围是固定的。所以，在将窗口的原始图数据的范围是固定的。所以，在将窗口的原始图形变换到视区显示时，必须进行此变换。形变换到视区显示时，必须进行此变换。 计算机图形学第四章窗口视

8、区变换窗口视区变换2 2、变换公式：、变换公式： 计算机图形学第四章窗口视区变换窗口视区变换变换应在保持一定比例关系的前提下进行，即：变换应在保持一定比例关系的前提下进行，即：整理，化简得：整理，化简得： ybytybsybytybwxlxrxlsxlxrxlwvvvywwwyvvvxwwwx dcyybaxxwsws 计算机图形学第四章窗口视区变换窗口视区变换其中：其中：ybytyxlxrxybytyxlxrxyyybybyyxxxlxlxxvvvvvvwwswwssvwvdsvcsvwvbsva,a,c分别反映了视区和窗口在x和y方向上的伸缩比c,d则分别反映了定位点在x和y方向上的偏移量

9、计算机图形学第四章窗口视区变换窗口视区变换五、窗口五、窗口-ndc-视区变换视区变换 系统有多系统有多个输出设个输出设备时采用备时采用计算机图形学第四章窗口视区变换窗口视区变换考虑到输出设备的分辨率，为了使图形程序设计考虑到输出设备的分辨率，为了使图形程序设计与设备无关，将视区设置在规格化设备坐标中，用户与设备无关，将视区设置在规格化设备坐标中，用户设计的图形首先变换到规格化设备坐标上，它能适应设计的图形首先变换到规格化设备坐标上，它能适应任何一种具体的图形输出设备。任何一种具体的图形输出设备。变换公式为：变换公式为： x xs s= =（x xw w-w-wxlxl）/s/sx x y ys

10、 s= =（y yw w-w-wybyb）/s/sy y（因为：（因为：v vx x=v=vy y=1=1， v vxlxl=v=vybyb=0=0）然后，根据物理输出设备坐标或具体显示器屏幕然后，根据物理输出设备坐标或具体显示器屏幕尺寸和分辨率，再将规格化设备坐标变换到具体视区尺寸和分辨率，再将规格化设备坐标变换到具体视区上，显示输出图形（教材上，显示输出图形（教材p364p364）计算机图形学第四章窗口视区变换窗口视区变换六、窗口六、窗口- -视区的变换过程：视区的变换过程：用户坐标系统用户坐标系统 相对窗口相对窗口 将窗口内图形将窗口内图形 将规格化将规格化 输出输出下设计的图形下设计的

11、图形 作裁剪作裁剪 变换成规格化变换成规格化 坐标变换坐标变换 图形图形 设备坐标设备坐标 成设备坐标成设备坐标 开窗变换开窗变换 视区变换视区变换 窗口到视区的映射结果，视区中显示的只是窗口内部的那窗口到视区的映射结果，视区中显示的只是窗口内部的那部分图景，窗口外的所有部分都被去掉了。把位于给定区域外部分图景，窗口外的所有部分都被去掉了。把位于给定区域外的所有图形部分全部删除的过程称为裁剪。窗口变换的过程通的所有图形部分全部删除的过程称为裁剪。窗口变换的过程通常是先对窗口进行裁剪，然后把窗口内部映象到视区中。常是先对窗口进行裁剪，然后把窗口内部映象到视区中。计算机图形学第四章4.34.3 图

12、形裁剪图形裁剪一、一、 裁剪的基本概念裁剪的基本概念二、二、 点的裁剪点的裁剪三、三、 线段裁剪线段裁剪cohen-sutherlandcohen-sutherland算法；算法；中点算法中点算法参数化裁剪算法（略）参数化裁剪算法（略）四、四、 多边形裁剪多边形裁剪sutlerland_hodgmansutlerland_hodgman算法算法五、五、 字符裁剪字符裁剪计算机图形学第四章一、一、 裁剪的基本概念裁剪的基本概念 裁剪的目的裁剪的目的 判断图形元素是否落在裁判断图形元素是否落在裁剪窗口之内并找出其位于剪窗口之内并找出其位于内部的部分内部的部分 裁剪的处理的基础裁剪的处理的基础 图元

13、关于窗口内外关系的图元关于窗口内外关系的判别判别 图元与窗口的求交图元与窗口的求交 假定条件假定条件 矩形裁剪窗口：矩形裁剪窗口：wwxlxl , w , wxrxr &w &wybyb , w , wytyt 计算机图形学第四章二、二、 点的裁剪点的裁剪点点(x, y)(x, y)在窗口内的充分必要条件是：在窗口内的充分必要条件是： w wxlxlxwxwxrxr w wybybywywytyt问题：对于任何多边形窗口，如何判别？问题：对于任何多边形窗口，如何判别？计算机图形学第四章三、线段裁剪三、线段裁剪 假定条件假定条件 待裁剪线段：待裁剪线段： 裁剪的任务裁剪的任务 要求确定这条直线是

14、完全可见、部要求确定这条直线是完全可见、部分可见或完全不可见分可见或完全不可见 若完全可见：输出其已知的两个端点坐标，若完全可见：输出其已知的两个端点坐标，并显示该直线并显示该直线 若部分可见：输出可见部分的两个端点，若部分可见：输出可见部分的两个端点，并显示该线段并显示该线段 若完全不可见：则不显示若完全不可见：则不显示),(),(111000yxpyxp计算机图形学第四章待裁剪线段和窗口的关系待裁剪线段和窗口的关系 要判断一条直线的可见性，必须根据直要判断一条直线的可见性，必须根据直线的两个端点与窗口的相对位置来进行判断。线的两个端点与窗口的相对位置来进行判断。计算机图形学第四章待裁剪线段

15、和窗口的关系待裁剪线段和窗口的关系直线相对于窗口位置的五种情况：直线相对于窗口位置的五种情况： 1 1）两端点均在窗口内）两端点均在窗口内直线直线abab（应全保留）（应全保留） 2 2）两端点均在窗口同侧）两端点均在窗口同侧直线直线efef（全舍弃）（全舍弃） 3 3）一个端点在窗口内，一个在窗口外）一个端点在窗口内，一个在窗口外直线直线dcdc（分段讨论）（分段讨论） 4 4）直线贯穿窗口与窗口的两条边线相交）直线贯穿窗口与窗口的两条边线相交直线直线ghgh（分段讨论）（分段讨论） 5 5）直线与窗口边线的交点均在窗口外）直线与窗口边线的交点均在窗口外直线直线ijij（分段讨论）（分段讨论

16、）为提高效率，算法设计时应考虑：(一）快速判断情形1），2）；(二) 设法减少情形3）5）求交次数和每次求交时所需的计算量。计算机图形学第四章（一）（一）cohen-sutherland cohen-sutherland 算算法法 该算法是用区域检查的办法有效的该算法是用区域检查的办法有效的识别可以直接接受或直接舍弃的线段，只有识别可以直接接受或直接舍弃的线段，只有不属于这两种情况的线段才需要计算交点。不属于这两种情况的线段才需要计算交点。 特点：用编码方法可快速判断线段特点：用编码方法可快速判断线段-完完全可见和显然不可见。全可见和显然不可见。 特别适用二种场合：特别适用二种场合：大窗口场合

17、和窗口特别小的场合大窗口场合和窗口特别小的场合( (如如, , 光标拾光标拾取图形时取图形时, ,光标看作小的裁剪窗口。）光标看作小的裁剪窗口。）( (编码算法编码算法) )计算机图形学第四章算法原理算法原理 对于每条线段对于每条线段p p1 1p p2 2分为三种情况处理：分为三种情况处理： 若若p p1 1，p p2 2完全在窗口内，则完全在窗口内，则“取取”之之 ，即，即 线段完全可见，否则进入线段完全可见，否则进入2 2）；）；若若p p1 1，p p2 2明显在窗口外，则明显在窗口外，则 “ “弃弃”之，即线之，即线段显然不可见，裁剪结束，否则进行段显然不可见，裁剪结束，否则进行3

18、3）；）；1)1) 若不满足上述两条件，则求线段与窗口边延若不满足上述两条件，则求线段与窗口边延长线的交点，把线段分为两段，其中一段显长线的交点，把线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新重复然不可见，丢弃。对余下的另一段重新重复上述处理直到全保留或全舍弃。上述处理直到全保留或全舍弃。裁剪过程是递归的裁剪过程是递归的计算机图形学第四章具体实现具体实现编码方法编码方法 为了使计算机能够快速的判断一条线段与为了使计算机能够快速的判断一条线段与窗口何种关系，采用编码方法：由窗口四条边所在窗口何种关系，采用编码方法：由窗口四条边所在直线把二维平面分成直线把二维平面分成9 9个区域，每

19、个区域赋予一个个区域，每个区域赋予一个四位编码，四位编码，c ct tc cb bc cr rc cl l （上下右左）（上下右左）elseyyct0max1当elseyycb0min1当elsexxcr0max1当elsexxcl0min1当计算机图形学第四章具体实现具体实现算法步骤算法步骤算法步骤：算法步骤： 裁剪一条线段时，先求出端点裁剪一条线段时，先求出端点p p1 1p p2 2所所在的区号在的区号code1code1和和code2 code2 若若code1=0code1=0且且code2=0 code2=0 则说明则说明p p1 1和和p p2 2均在窗均在窗口内，全保留口内，全

20、保留 若若code10 code20code10 code20且且code1code20code1code20则说明则说明p p1 1和和p p2 2均在窗口外侧，全舍弃均在窗口外侧，全舍弃1)1) 若上述两条件均不成立，则求出线段与窗若上述两条件均不成立，则求出线段与窗口某边的交点，在交点处把线段一分为二，口某边的交点，在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之，其中必有一段完全在窗口外，可以弃之，再对另一段重复进行上述处理。再对另一段重复进行上述处理。 计算机图形学第四章具体实现具体实现求交点求交点 求交运算是计算机图形学求交运算是计算机图形学中比较复杂的一个算法，现中比较

21、复杂的一个算法，现通过右图简单推导出交点的通过右图简单推导出交点的坐标。坐标。已知线段已知线段p p1 1p p2 2，现欲求其与现欲求其与窗口左边线的交点窗口左边线的交点s s（x x，y y）如图所示：如图所示：pp1 1sbpsbp1 1p p2 2a asb/psb/p2 2a=pa=p1 1b/pb/p1 1a a即：即：211121xxwxyyyyxl稍稍加加整整理理即即可可得得，左左交交点点为为： 111212)(yxwxxyyywxxlxl计算机图形学第四章具体实现具体实现求交点求交点同同理理，可可推推导导出出： 右右交交点点为为： 111212)(yxwxxyyywxxrxr

22、 下下交交点点为为： ybybwyxywyyxxx111212)( 上上交交点点为为： ytytwyxywyyxxx111212)( 对于那些非完全可见、对于那些非完全可见、又非显然不可见的线段，需又非显然不可见的线段，需要求交，求交前先测试与窗要求交，求交前先测试与窗口哪条边所在直线有交？口哪条边所在直线有交？( (按序判断端点编码中各位按序判断端点编码中各位的值的值c cl lc ct tc cr rc cb b）求交测试顺序固定求交测试顺序固定( (左上右左上右下）下）最坏情形，线段求交四次。最坏情形，线段求交四次。计算机图形学第四章done=0done=0accept=0accept=

23、0reject=0reject=0退出退出初始化初始化求求p1p1，p2p2的编码的编码c1c1，c2c2c1c2=0c1c2=0？c1=0c1=0且且c2=0c2=0c1=0?c1=0?p1p1与与p2p2交换交换done=1?done=1?accept=1?accept=1?显示显示 p1p2p1p2开始开始y yn再分割再分割n ny yp1p1在窗口内在窗口内 n nyyn np1p1在在w w之之 求交求交 （丢弃）（丢弃）reject=1reject=1 done=1 done=1（接受）（接受）accept=1accept=1 done=1 done=1p1p1、p2p2均在均在

24、w w内内 y yn np1p1、p2p2均在均在w w外外y1=wyty1=wytx1=x1=y1=wyby1=wybx1=x1=x1=wxrx1=wxry1=y1=x1=wxlx1=wxly1=y1=左左上上右右下下新新p1p1说明：在线段再分割求交的过程中，说明：在线段再分割求交的过程中，保证保证p1p1始终在窗口之外，得到的交始终在窗口之外，得到的交点（边界上的点）为新的点（边界上的点）为新的p1p1，重复，重复判断判断p1p1、p2p2的代码，舍弃在窗口外的代码，舍弃在窗口外的，显示在窗口内的线段。的，显示在窗口内的线段。计算机图形学第四章nicholl-lee-nicholl算法

25、消除c-s算法中多次求交的情况。 基本想法：对2d平面的更细的划分。计算机图形学第四章nicholl-lee-nicholl算法假定待裁剪线段p0p1为非完全可见且非显然不可见。 步骤：步骤：第一步，窗口四边所在的直线将二维平面划分成第一步，窗口四边所在的直线将二维平面划分成9 9个区域，假定个区域，假定 落在区域落在区域0 0、4 4、5 5 p0计算机图形学第四章nicholl-lee-nicholl算法第二步：从第二步：从p p0 0点向窗口点向窗口的四个角点发出射的四个角点发出射线，这四条射线和线，这四条射线和窗口的四条边所在窗口的四条边所在的直线一起将二维的直线一起将二维平面划分为更

26、多的平面划分为更多的小区域小区域 。此时此时p1p1的位置决定了的位置决定了p p0 0p p1 1和和窗口边的相交关系。窗口边的相交关系。计算机图形学第四章nicholl-lee-nicholl算法第三步，确定第三步，确定p p1 1所在的区域所在的区域（判断p1所在区域位置，可判定p0、p1与窗口那条边求交) 。根据窗口四边的坐标值及p p0 0p p1 1和各射线的斜率可确定p1所在的区域。第四步，求交点，确定第四步，求交点，确定p p0 0p p1 1的可见部分的可见部分 。特点：效率较高，但仅适合二维矩形窗口。计算机图形学第四章（二）中点分割法（二）中点分割法原理：原理： 与与csc

27、s算法一样对线段端点进行编码，算法一样对线段端点进行编码，并把线段与窗口的关系一样分为三种情并把线段与窗口的关系一样分为三种情况，并对当前两种情况进行一样的处理。况，并对当前两种情况进行一样的处理。对于第三种情况，则简单的把线段等分对于第三种情况，则简单的把线段等分为二段，对两段重复上述测试处理，直为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口至每条线段完全在窗口内或完全在窗口外。外。计算机图形学第四章中点分割法中点分割法如图所示，为求线段如图所示，为求线段p1p2p1p2的的看见部分看见部分abab，算法可分为两个过，算法可分为两个过程平行进行，即：程平行进行，即：（1

28、 1）从）从p1p1出发，找出离出发，找出离p1p1最远最远的可见点的可见点b b（2 2）从）从p2p2出发，找出离出发，找出离p2p2最远最远的可见点的可见点a a算法对两个端点的处理是相算法对两个端点的处理是相同的。同的。算法实质：用对分的方法不断排算法实质：用对分的方法不断排除线段的不可见部分，即处于窗除线段的不可见部分，即处于窗口同侧外面的部分，目的是用中口同侧外面的部分，目的是用中点逼近线段与窗口边的交点点逼近线段与窗口边的交点p1p2ab计算机图形学第四章具体实现具体实现 在编码时，应避免把线段裁剪在编码时，应避免把线段裁剪成许多零碎的小段，这可以通过求成许多零碎的小段，这可以通

29、过求可见线段的端点来实现。可见线段的端点来实现。对线段对线段p p1 1p p2 2：1 1）若）若p p2 2可见，则可见，则p p2 2就是离就是离p p1 1最远的最远的可见点。可见点。2 2）对两端点的区号作按位与运算，）对两端点的区号作按位与运算，若结果不为若结果不为0 0，则全弃之，否则继续。，则全弃之，否则继续。3 3）在中点）在中点p pm m处把线段处把线段p p1 1p p2 2分为两段，分为两段，若若p pm m 可见，把原问题转化为对可见，把原问题转化为对p pm mp p2 2求离求离p1p1最远的可见点。若最远的可见点。若p pm m不可见，不可见，则把原问题转化为

30、求则把原问题转化为求p p1 1p pm m上离上离p1p1最远最远的可见点。重复执行的可见点。重复执行2 2），），3 3），直），直到分点与线段端点距离达到分辨率到分点与线段端点距离达到分辨率精度为止。精度为止。p1 p2 pm 待求点 p1 p2 pm 待求点 计算机图形学第四章中点分割法中点分割法计算机图形学第四章四、四、 多边形裁剪多边形裁剪 错觉：直线段裁剪的组合？错觉：直线段裁剪的组合？ 新的问题新的问题： 1 1）边界不再封闭，需要用窗口边界的恰当部分）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？来封闭它，如何确定其边界？计算机图形学第四章四、多边形裁剪四、

31、多边形裁剪2 2）一个凹多边形可能被裁剪成几个小的多边形，）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？如何确定这些小多边形的边界？计算机图形学第四章sutherland-hodgmansutherland-hodgman算法算法（rpcrpc算法，逐边裁剪算法）算法，逐边裁剪算法）原理：原理： 一次用窗口的一条边裁剪多边形，一次用窗口的一条边裁剪多边形，输出是一个顶点序列，再将其中作为下输出是一个顶点序列，再将其中作为下一条裁剪边处理过程的输入，直至几条一条裁剪边处理过程的输入，直至几条边线全部处理完。边线全部处理完。 计算机图形学第四章sutherland-hodg

32、mansutherland-hodgman算法算法 分割处理策略分割处理策略：将多边形关于矩形窗口的裁剪分解将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。为多边形关于窗口四边所在直线的裁剪。 流水线过程流水线过程( (左上右下左上右下) )：左边的结果是上边的开始左边的结果是上边的开始。计算机图形学第四章sutherland-hodgmansutherland-hodgman算法算法 内侧空间与外侧空间内侧空间与外侧空间 多边形的边与半空间的关系多边形的边与半空间的关系输出：输出：p p点点 （1 1个）个）输出：交点输出：交点i i（1 1个）个）输出：输出：0 0个顶个

33、顶点点输出：输出：i i点，点，p p点点 （2 2个）个）计算机图形学第四章sutherland-hodgmansutherland-hodgman算法算法 裁剪结果的顶点构成裁剪结果的顶点构成：裁剪边内侧的原顶点；多裁剪边内侧的原顶点；多 边形的边与裁剪边的交边形的边与裁剪边的交点。点。 顺序连接顺序连接几点说明：几点说明：l裁剪算法采用流水线方式，裁剪算法采用流水线方式， 适合硬件实现。适合硬件实现。l可推广到任意凸多边形裁剪可推广到任意凸多边形裁剪 窗口窗口计算机图形学第四章算法示例算法示例顶点序列顶点序列裁剪前：裁剪前：p p1 1，p p2 2，p p3 3，p p4 4，p p5

34、 5，p p6 6，p p7 7，p p1 1相对于左边线裁剪：相对于左边线裁剪：i i1 1，i i2 2，p p3 3，p p4 4，p p5 5，p p6 6，p p7 7，p p1 1相对于下边线裁剪：相对于下边线裁剪：i i2 2，p p3 3，i i3 3，i i4 4，p p6 6，p p7 7，p p1 1，i i1 1相对于右边线裁剪：相对于右边线裁剪：p p3 3，i i3 3，i i4 4，p p6 6，i i5 5，i i6 6，p p1 1，i i1 1，i i2 2相对于上边线裁剪：相对于上边线裁剪：i i3 3，i i4 4，p p6 6，i i5 5，i i6

35、6，i i7 7，i i8 8，i i1 1，i i2 2，p p3 3计算机图形学第四章weiler-athentonweiler-athenton算法算法裁剪窗口为任意多边形（裁剪窗口为任意多边形（凸、凹、带内环）的情况：的情况： 主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为a a 裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为b b 计算机图形学第四章 主多边形和裁剪多边形把二维平面分成两部分。 内裁剪内裁剪：ab 外裁剪外裁剪：a-bweiler-athentonweiler-athenton算法算法裁剪结果区域的边界由裁剪结果区域的边界由a a的部分的部分边界和边界

36、和b b的部分边界两部分构成，的部分边界两部分构成，并且在交点处边界发生交替，并且在交点处边界发生交替，即由即由a a的边界转至的边界转至b b的边界，或的边界，或由由b b的边界转至的边界转至a a的边界的边界 计算机图形学第四章weiler-athentonweiler-athenton算法算法 如果主多边形与裁剪多边形有交点，则交点成对出如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：现，它们被分为如下两类： 进点：主多边形边界由此进入裁剪多边形内进点：主多边形边界由此进入裁剪多边形内 如，如，i i1,1,i i3, 3, i i5, 5, i i7, 7, i i9, 9, i i1111 出点：主多边形边界由出点：主多边形边界由此离开裁剪多边形区域此离开裁剪多边形区域. . 如，如， i i0,0,i i2, 2, i i4, 4, i i6, 6, i i8, 8, i i1010 计算机图形学第四章weiler-athentonweiler-athenton算法算法1）建顶点表；2）求交点；3）裁剪 weiler_athentonweiler_athenton