图形学课件7中文

《图形学课件7中文》由会员分享，可在线阅读，更多相关《图形学课件7中文（78页珍藏版）》请在金锄头文库上搜索。

1、二维图形裁剪,2019/6/20,2,预备知识,2019/6/20,3,矢量,定义:,2019/6/20,4,续,矢量的模长(Vector Mode),矢量的方向角 非零矢量与三个坐标轴的夹角称为该矢量的方向角,矢量的单位化,2019/6/20,5,续,矢量的方向余弦：非零矢量的方向角的余弦称为该矢量的方向余弦,2019/6/20,6,续,两矢量的夹角,2019/6/20,7,续,两矢量的数积(点积) (Vector Dot Metrix),2019/6/20,8,续,两矢量的矢积(叉积) (Vector Product),2019/6/20,9,续,2019/6/20,10,直线的参数方程,

2、2019/6/20,11,续,2019/6/20,12,二维图形裁剪问题描述,目的：按需显示图形 识别出图形落在显示区域（窗口）内/外部分 图元在窗口区域内外的判别 图元与窗口的求交运算 裁剪窗口：矩形区域,2019/6/20,13,线段裁剪,2019/6/20,二维裁剪的实质:就是决定图形中哪些点、线段、文字、以及多边形在窗口之内。 二维裁剪的基本方法: 将图形元素(如线段）与窗口边界求交点,交点连接起来在窗口内的部分就是裁剪后的显示图形(即求交).,续,2019/6/20,15,裁剪算法的实现,针对点阵图形 算法简单，效率低 适于求交难度大的图形,针对参数表示图形 效率提高 适用于简单图元

3、，如：直线、多边形、字符,2019/6/20,16,内容,线段裁剪 Cohen-Sutherland线段裁剪算法 Nicholl-Lee-Nicholl线段裁剪算法 中点分割算法 Liang-Barsky裁剪算法 多边形裁剪 Sutherland-Hodgman多边形逐边裁剪算法 Wiler-Atherton多边形双边裁剪算法,2019/6/20,17,线段裁剪,2019/6/20,18,直接裁剪算法,算法流程： 若线段两端点均落在窗口内： 线段显然完全可见 若线段两端点均落在窗口外： 计算线段与窗口交点（0个或2个），若无交点，则线段显然完全不可见，否则线段部分可见。 若线段两端点分别落在窗

4、口的内外两侧： 计算线段与窗口边界的交点（1个），确定可见部分线段；,2019/6/20,19,点的裁剪,点(x,y)在窗口内的充分必要条件,2019/6/20,20,直线段与窗口边界交点的计算,2019/6/20,21,CohenSutherland线段裁剪算法,编码法：最早的、最流行的裁剪算法，可推广到三维空间。,原理：利用判别规则(位置编码)确定线段端点与窗口边框及其延长线的位置关系，从而实现线段裁剪。,2019/6/20,22,流程： 线段端点编码； 利用位置编码进行裁剪 计算线段与窗口边框及其延长线的交点 实现裁剪,CohenSutherland线段裁剪算法,2019/6/20,23

5、,方法: 扩展窗口的边界把平面划分为9个区域，如下编码各区域（从左到右）,编码区域和端点,第1个比特位 上边界外侧，上边界以上 y ymax 第2个比特位 下边界外侧，下边界下方 y xmax 第4个比特位 左边界外侧, 左边界的左侧 x xmin,2019/6/20,24,区域编码,1010,0010,0110,2019/6/20,25,端点编码,encode（P，code）：端点的编码是其所在的区域编码 线段1：两个端点编码都为（0000） 线段2：左端点（1000）， 右端点（1010） 线段3：左端点（0100） 右端点（0010） 线段4和线段3一样 线段5：左端点（1001） 右端

6、点（0000） 规律： 1）显然完全可见的线段其两端点编码都为（0000） 2）线段两端点编码中相同位同为1，则线段一定在相同边界外侧，其显然完全不可见。,2019/6/20,26,算法:(1)对直线的两个端点编码C1,C2; (2)若C1=C2=0000,则直线完全保留,返回; (3)否则判断直线与边界有无交点:将C1逻辑乘C2, 即C1C2,若C1C20,则说明C1,C2有某相 同位同为“1”,即两端点同在某边界的外侧,此时 直线与边界无交点,抛弃直线,返回; (4)否则C1C2=0且C10或C20,此时与边界有交点, 求交.用交点替代端点.GOTO (1).,CohenSutherlan

7、d线段裁剪算法,2019/6/20,27,CohenSutherland算法流程图,exit,Encoding endpoints: encode(p1,code1);encode(p2,code2),code1=0000&code2=0000,trivially accepted,exit,y,code1&code2!=0000,Trivially rejected,y,N,Computing the intersections and replacing the respective endpoint,2019/6/20,28,Example(1),用CS算法裁剪AB和CD 一、求AB 1

8、.编码 A: (0010) B: (0100) 2.判断A、B点编码是否全为零（ 即二者是否同在窗口内） A和B都不在窗口内，继续步骤3 3.判断A和B是否在窗口某边界同外侧（显 然完全不可见，即二者编码逻辑乘不等于0） A和B编码逻辑乘等于0，不同在某边界外侧， 不是显然完全不可见，不能抛弃，继续步骤4,2019/6/20,29,Example(1),4.求交点 只对编码不全为0端点找替代其的交点 (但不能将窗口内端点（编码为全0）向 外找其替代交点)。 因为A的编码(0010)不全为0，对 其为1的那些边界从左向右（或从右向 左）求交点。交点使其相应位为0。线 段AB与右边界求出交点E，令

9、AE。 回步骤1。 5.编码 A: (0000) B: (0100),2019/6/20,30,Example(1),6.判断A、B点编码是否全为零（ 即二者是否同在窗口内） A (0000)在窗口内，但B (0100) 不在窗口内，继续步骤3 7.判断A和B是否在窗口某边界同外侧 （即是否显然完全不可见，此时二者编 码逻辑乘不等于0 ） A和B编码逻辑乘等于0，不同在某边 界外侧，不是完全不可见，不能抛 弃，继续步骤4,2019/6/20,31,Example(1),8.求交点 因为A的编码(0000)全为0，不用求交 点。只需对B (0100)中为1的那些边界 从左向右（或从右向左）求交点

10、，交点使 其相应位为0。线段AB与右边界求出交点 F，令BF。回步骤1。 9.编码 A: (0000) B: (0000) 10.因为A=B=0000,则直线段完全保留,返回;,2019/6/20,32,Example(2),二、求CD 1.编码 C: (0010) D: (0100) 2.判断C、D点编码是否全为零（ 即二者是否同在窗口内） C和D都不在窗口内，继续步骤3 3.判断C和D是否在窗口某边界同外侧（显 然完全不可见，此时二者编码逻辑乘不等于0） C和D编码逻辑乘等于0，不同在某边界外侧， 不是显然完全不可见，不能抛弃，继续步骤4,2019/6/20,33,Example(2),4

11、.求交点 只对编码不全为0端点找替代其的交点 ，不能将窗口内端点（编码为全0）向外 找其替代交点。 因为C的编码(0010)不全为0，对 其为1的那些边界从左向右（或从右向 左）求交点，交点使其相应位为0。线 段CD与右边界求出交点I，令CI。 回步骤1。 5.编码 C: (0100) D: (0100),2019/6/20,34,Example(2),6.判断C、D点编码是否全为零（ 即二者是否同在窗口内） C (0100)和D (0100)都 不在窗 口内，继续步骤3 7.判断C和D是否在窗口某边界同外侧 （显然完全不可见，此时二者编码逻 辑乘不等于0 ） C和D编码逻辑乘不等于0，同在下

12、边 界外侧，是完全不可见，抛弃，返回；,2019/6/20,35,边框线与线段交点的计算,线段参数表达式：,2019/6/20,36,特点分析：,快速实现完全可见与完全不可见线段的裁剪 适用于：裁剪窗口特别大或小的情形 可推广到三维线段的裁剪,2019/6/20,37,Nicholl-Lee-Nicholl线段裁剪算法（1）,原理： 引入更多的区域测试来降低求交计算开销。,划分平面为9个区域，并根据线段端点的位置判别裁剪结果。,2019/6/20,38,Nicholl-Lee-Nicholl线段裁剪算法（2）,2019/6/20,39,确定p0所在的区域。,Nicholl-Lee-Nichol

13、l线段裁剪算法（3）,2019/6/20,40,第二步，从p0点向窗口的四个角点引出射线，它们与窗口的四条边一起将二维平面划分为更多的小区域。此时，p1的位置（所在的区域）决定了p0 p1和窗口边（不是延长线）的相交关系。,Nicholl-Lee-Nicholl线段裁剪算法（4）,p0,.,2019/6/20,41,L,R,T,B,L,LR,LB,LT,Nicholl-Lee-Nicholl线段裁剪算法（5）,2019/6/20,42,L,LR,TR,T,LB,T,L,LB,TB,TR,Nicholl-Lee-Nicholl线段裁剪算法（6）,2019/6/20,43,第三步，确定p1所在区域

14、。 根据窗口四边的坐标值以及p0 p1和各射线的斜率可确定p1所在的区域。 第四步，求交点，确定p0 p1的可见部分。,Nicholl-Lee-Nicholl线段裁剪算法（7）,2019/6/20,44,P1属于区域R的充要条件是：,pTR,pRB,pLT,pBL,Nicholl-Lee-Nicholl线段裁剪算法（8）,2019/6/20,45,Nicholl-Lee-Nicholl线段裁剪算法（9）,特点分析: 效率高 不适宜向三维裁剪推广,2019/6/20,该方法与CS法的不同之处在于第三步的处理: 设要裁剪的线段是P1P2,中点分割法分成两个平行的过程进行,即从P1出发找出离P1最近

15、的可见点(如图中A点),和从P2出发找出离P2最近的可见点(如图中B点).若这两点存在,那么它们的连线就是原线段的可见部分.,中点分割法,2019/6/20,Liang-Barsky裁剪算法,Cyrus&Beck提出了一种完全不同的,通常更有效的线段裁剪方法 Liang 和 Barshy 后来各自独立地提出一种更有效的参数化线段裁剪方法,2019/6/20,点在区域内或外,对于任意由点构成边界的封闭区域,规则: 点在区域内: 点在所有边界点的内侧 点在区域外: 点在某个边界点的外侧,2019/6/20,49,点在凸区域内部应满足的条件,记号：,针对单个边界点的判别规则：,区域内部点应满足条件：

16、 对于任意凸区域边界点A，被判别点满足以上第（1）或（2）式,A,N,2019/6/20,50,Liang-Barsky裁剪算法原理,利用线段的参数表达形式直接判别落在窗口内的部分线段,2019/6/20,51,Liang-Barsky线段裁剪模型,根据矩形窗口特点，点在窗口内的条件得以简化：,满足上述条件的点即落在矩形窗口内。 可简化线段裁剪模型为：,2019/6/20,52,Liang-Barsky裁剪算法实现(1),线段参数方程代入上式后，线段裁剪模型变形如下：,2019/6/20,53,以i=1为例，对应方程化简为：,Liang-Barsky裁剪算法实现(2),可令：,2019/6/20,54,Liang-Barsky裁剪算法实现(3),化简后的方程组为：,该方程组的解区间即为线段上落在窗口内的点所在参数区间。,2019/6/20,55,Liang-Barsky裁剪算法实现(4),方程无解，即线段整体在下边框线外侧；,方程有无穷解