第3章二维图形裁剪.ppt
《第3章二维图形裁剪.ppt》由会员分享,可在线阅读,更多相关《第3章二维图形裁剪.ppt(57页珍藏版)》请在三一文库上搜索。
1、计算机图形学基础,第3章 二维图形裁剪,本章主要内容,3.1 裁剪概述 3.2 线段裁剪 直接求交算法; Cohen-Sutherland算法;(重点,算法实现) 中点算法 3.3 多边形裁剪 Sutlerland_Hodgman算法(难点,算法实现) Weiler-Athenton算法 3. 4 字符裁剪,三维裁剪,被裁剪对象:直线段、多边形、三维实体,1.裁剪:是裁去窗口之外物体或物体部分的一种操作。,3.1 裁剪概述,“取景器”=窗口,视区1 视区2 (viewport),裁剪的目的 判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分 裁剪处理的基础 图元关于窗口内外关系的判别 图元
2、与窗口的求交 假定条件 矩形裁剪窗口:xmin,xmaxymin,ymax 待裁剪点或线段:,2.裁剪概述,点裁剪 点(x, y)在窗口内的充分必要条件是: 问题:对于任何多边形窗口,如何判别?,线段相对于该窗口的情况有: 线段全部位于窗口的内部(A); 线段全部位于窗口外部(B、C); 线段的中间部分在窗口内,而二端点在窗口外部(D); 线段的一端在窗口内,而另一端在窗口外(E)。,3.2 线段裁剪,待裁剪线段和窗口的关系 线段完全可见 显然不可见 线段至少有一端点在窗口之外,但非显然不可见,保留,为提高效率,算法设计时应考虑: (一)快速判断线段完全在窗口内或处的情形; (二) 设法减少裁
3、剪情形中求交次数和每次求交时所需的计算量。,3.2.1 直接求交算法,基本思想是:判断直线与窗口的位置关系,确定该直线是完全可见、部分可见或完全不可见,然后输出处于窗口内线段的端点,并显示此线段。 根据直线段和窗口的关系可知: (1)整条线在窗口之内。此时,不需剪裁,显示整条线段。 (2)整条线在窗口之外,此时,不需剪裁,不显示整条线段。 (3)部分线在窗口之内,部分线在窗口之外。此时,需要求出线段与窗口边界的交点,并将窗口外的线段部分剪裁掉,显示窗口内的部分。,例1 设有直线段P0P1,有一个矩形裁剪窗口,写出对该线段裁剪的算法。,1)判断线段端点的位置,由图4-2(a)可知:P0不在窗口内
4、,P1在窗口内。 2)保持线段起始点在裁剪窗口内:交换两点,使P0在内,如图4-2(b)所示。 3)求出直线与窗口的交点I,如图4-2(c)所示。 4)取P0 I线段显示,擦除I P1线段,并将P1替换I,即得P0P1线段,裁剪结束。如图4-2(d)所示。,求线段与窗口交点,设线段两端点坐标为: 和 则过这两点的直线方程为: 其中k为斜率。上述直线方程与窗口各边界的交点为: 左: 右: 下: 上:,基本思想:对于每条待裁剪的线段P1P2分三种情况处理:若P1P2完全在窗口内,则显示该线段P1P2,简称“取”之;若P1P2完全在窗口外,则丢弃该线段,简称“舍”之;若线段既不满足“取”的条件,也不
5、满足“舍”的条件,则求线段与窗口边界的交点,在交点处把线段分为两段,其中一段完全在窗口外,可舍弃之,然后对另一段重复上述处理。 核心思想:分区编码和线段分割。,3.2.2 Cohen-Sutherland 算法 (编码算法),分区编码方法:图形区域划分成九个区域。 四位编码 表示端点所处的位置: (-) 上 下 右 左 第一位为“1”时,表示点在y=yT的上方; 第二位为“1”时,表示点在y=yB的下方; 第三位为“1”时,表示点在x=xR的右方; 第四位为“1”时,表示点在x=xL的左方。,1111,编码原则,每个区域赋予一个四位编码,CtCbCrCl,上下右左;,编码方法,练习:请给出右图
6、的线段端点编码(端点编码:定义为它所在区域的编码),第一步 判别线段两端点是否都落在窗口内,如果是, 则线段完全可见;否则进入第二步; 第二步 判别线段是否为显然不可见,如果是,则裁 剪结束;否则进行第三步 ; 第三步 求线段与窗口边延长线的交点,这个交点将 线段分为两段,其中一段显然不可见,丢弃。 对余下的另一段重新进行第一步,第二步判断, 直至结束,Cohen-Sutherland 算法步骤,当线段的两个端点的编码的逻辑“与”非零时 ,线段为显然不可见的。也可以进行“按位与”运算,可知这两个端点是否同在视区的上、下、左、右; 如code1=0101,code2=0110,则code1&co
7、de2=0100,表示在窗口下方。 问题:显然可见的编码如何判断?,编码判断,对一条线段的可见性测试方法: (1)若线段两个端点的四位二进制编码全为0000,即两端点编码逻辑或运算为0,那么该线段完全位于窗口内,可直接保留; (2)对两端点的四位二进制编码进行逻辑与运算,若结果不为零,那么整条线段必位于窗口外,可直接舍弃; (3)否则,这条线段既不能直接保留,也不能直接舍弃,它可能与窗口相交。此时,需要对线段进行再分割,即找到与窗口边线的一个交点,根据交点位置,赋予四位二进制编码,并对分割后的线段按照一定的顺序(如左右下上)进行检查,决定保留、舍弃或再次进行分割。重复这一过程,直到全部线段均被
8、舍弃或保留为止。,裁剪过程是递归的,Cohen-Sutherland裁剪算法,如何判定应该与窗口的哪条边求交呢? 编码中对应位为1的边。 计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点 if(LEFT,左交点,右交点,下交点,上交点,例:分别给下列直线段编码,并判断是否需要剪裁。,例:Cohen-SutherLand算法过程:,过程: 1)输入线段AB的两端点坐标A(x0,y0)、B(x1,y1),以及裁剪窗口的四条边界:yt,yb,xl,xr。 2)对AB编码,A的编码codeA=0001,B的编码为codeB=0110。 3)线段AB裁剪的基本过程(按左右下上的顺序): 由于
9、codeA | codeB0,对AB不能全部保留;又因为codeA & codeB=0,对AB不能全部舍弃,因此要对AB进行求交处理。 由codeA=0001知A在窗口左边外侧,按左右下上的顺序求AB与窗口左边交点为P1,AP1必在窗口外,故裁剪掉,并用A替换P1。如图(b)所示。(交点替换是为了方便编程循环)。 对P1B重复上述处理。A(原P1)编码为0000,B编码为0110;由于A(原P1)已在窗口内,交换A和B的坐标值与编码,则B编码为0000,A编码变为0110,按左右下上顺序求得右交点为P3;A(原B)P3必在窗口外,故裁剪掉,并用A替换P3。如图(c)所示。 A的编码还没有达到0
10、000,再求得下边交点为P2,AP2必定在窗口外,故裁剪掉,并用A替换P2。如图(d)所示。 对剩下的直线段AB再进行判断,现在A编码为0000,B编码为0000,由于codeA | codeB=0,全在窗口中,故全部保留。 最后得到裁剪后的线段为AB,算法结束。,求交测试顺序固定(左上右下) 最坏情形,线段求交四次。,对于那些非完全可见、又非显然不可见的线段,需要 求交(如线段AD),求交前先测试与窗口哪条边所在 直线有交?(按序判断端点编码中各位的值ClCtCrCb),1)特点:用编码方法可快速判断线段- 完全可见和显然不可见。 2)特别适用二种场合: 大窗口场合; 窗口特别小的场合(如,
11、 光标拾取图形时, 光标看作小的裁剪窗口。),编码算法特点,算法的思路: 采用与前相似的线段端点编码和相应的检查方法,先判定完全可见线段和显然不可见线段。 否则,将线段分割成相等的两段,然后对每一小段重复上述的检查,直至找到每段与窗口边界的交点或分割小段的长度充分小,可以视为一点时为止。 相当于:对分查找法求交,分割次数最多不超过线段端点的表示精度。,3.2.3 中点分割算法,算法过程: 1)输入线段AB的两端点坐标A(x0,y0)、B(x1,y1),以及裁剪窗口的四条边界:yt,yb,xl,xr。 2)对AB编码,A的编码codeA=0001,B的编码为codeB=0110。 3)线段AB裁
12、剪的基本过程:,例:中点算法裁剪过程:,由于codeA | codeB0,对AB不能全部保留;又因为codeA & codeB=0,对AB不能全部舍弃,因此要对AB求中点处理; 求AB中点。 判断中点Pm1是否在窗口内,若不在窗口内,则将中点和离窗口最远点构成的线段去掉,以线段另一端点和该中点再构成线段,求其中点;若中点Pm1在窗口内,如上页左图所示。则以中点和最远点构成线段APm1,并求其中点Pm2,直至中点与窗口边界的坐标值在规定的误差范围内,则该中点就是线段落在窗口内的一个端点,用原线段端点A替代每一次保留的中点。 若另一端点在窗口内,则经即可确定该线段在窗口内的部分;若不在窗口内,如右
13、图,交换两端点,则该点和所求出的在窗口上的那一点构成一条线段AB,重复步骤,即可求出落进窗口的另外一点。并用原线段端点A替代每一次保留的中点。 最后得到裁剪后的线段为AB,算法结束。,对分辩率为2N*2N的显示器,上述二分过程至多进行N次。 主要过程只用到加法和除法运算,适合硬件实现,它可以用左右移位来代替乘除法,这样就大大加快了速度。,中点分割裁剪算法特点,设要裁剪的线段是P0P1。 P0P1和窗口边界交于A,B,C,D四点,见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点,图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二维 图形 裁剪
链接地址:https://www.31doc.com/p-2979406.html