计算机图形学 (7).ppt

1、湖北大学数计学院,1,计算机图形学,余 敦 辉 湖北大学 数计学院,湖北大学数计学院,2,第六章 二维图形的运算,6.1 交点计算 6.2 几何图形的关系判别 6.2 直线段裁剪 直接求交算法； Cohen-Sutherland算法； Nicholl-Lee-Nicholl算法 中点算法 6.3 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法 6.4 字符裁剪,湖北大学数计学院,3,6.1 交点计算 1. 两直线段的交点,设有两线段S1，S2。S1的端点分别为P1(x1,y1), P2(x2,y2), S2的端点分别为P3(x3,y3), P4(x4,

2、y4). 则两直线段的参数方程为：,湖北大学数计学院,4,6.1 交点计算 1. 两直线段的交点,讨论： 无解，此时意味两线段平行或重合； 有唯一解，但不一定是有效解，有效解应该是交点必须位于两直线段上。此时应满足如下条件： 0u1.0 0v1.0 根据u,v的值，即可获得交点的坐标。,湖北大学数计学院,5,6.1 交点计算 2. 直线段与圆弧的交点,湖北大学数计学院,6,6.1 交点计算 2. 直线段与圆弧的交点,讨论： 无解，第一种情况； 一解，第三种情况； 两解，第二种情况。 当有解时，还须进一步判断： 0t1.0 , se,湖北大学数计学院,7,6.1 交点计算 3. 两圆弧的交点,设

3、有两段圆弧A，B。A圆弧的圆心坐标(xa,ya),半径为ra, B圆弧的圆心坐标(xb,yb),半径为rb 。 则有如下方程：,如果两圆相交，则应有：,湖北大学数计学院,8,6.1 交点计算 3. 两圆弧的交点,讨论： 两圆之间的关系存在以上三种。 而对圆弧来说，有效解应在圆弧的定义域内： 即：,湖北大学数计学院,9,6.2 关系判别1. 点的包含性检验,点的包含性检验是指：判断一个点是否被包含在某一个区域内。为讨论方便，我们定义该区域为一多边形。但所采用的方法可推广到曲线边界。 夹角和法 设有一个点P和多边形ABCDE，如下图所示：,A,B,C,D,E,湖北大学数计学院,10,6.2 关系判

4、别1. 点的包含性检验,若依次将P点与多边形各顶点相连，且令i为多边形各相邻顶点与点P相连所形成的夹角。 则有如下结论： 若 i = 0, 则点P在多边形之外； 若 i = 2, 则点P在多边形之内； 夹角i的计算可采用余弦定理获得。而其方向则可按右手法则确定，用公式表示如下： 连线为两矢量Vi, V i+1 ,则Vi V i+1=,湖北大学数计学院,11,6.2 关系判别1. 点的包含性检验,因此，可用如下判别式判断夹角的方向： 当T0时，为逆时针方向； 当T0时，为顺时针方向。 交点数判别法,A,B,C,D,E,A,B,C,D,E,湖北大学数计学院,12,6.2 关系判别1. 点的包含性检

5、验,交点数法所利用的原理： 由P点向任一方向作一条射线，然后求出该射线与多边形边的交点数。则有： 1）当交点数为偶数（0）时，则说明点P在多边形外； 2）当交点数为奇数时，则说明点P在多边形内。 为处理简单，通常射线的与坐标轴平行。,湖北大学数计学院,13,6.2 关系判别1. 点的包含性检验,奇异情况处理： 即当射线穿过多边形顶点时的特殊处理。 当射线穿过的顶点两边在射线两侧，此时认为相交一次。而在同侧时，则认为相交两次。,湖北大学数计学院,14,6.2 关系判别 2. 多边形重叠性检验,通常采用“最小最大试验法”，也称为“排斥试验法”。这种方法可迅速排除掉不可能相互重叠的情况，从而减少计算

6、工作量，加快图形处理速度。 1）多边形的最小包含矩形 是指平面上能包含多边形的最小的矩形。如下图所示。,最小包含矩形,湖北大学数计学院,15,6.2 关系判别 2. 多边形重叠性检验,2）重叠性检验 利用最小包含矩形，可排除两个多边形不重叠情况。 如果两个多边形的最小包含矩形，不发生重叠，则这两个多边形必不重叠。,湖北大学数计学院,16,6.2 关系判别 2. 多边形重叠性检验,假定两个多变形的最小矩形为a和b,左下角和右上角的坐标分别为：,湖北大学数计学院,17,6.2 关系判别 2. 多边形重叠性检验,则当a,b两矩形满足下列条件之一时，a和b不重叠 Xamax=Xbmax Yamin=Y

7、bmax 当a、b两矩形不满足上述条件，即意味两多边形可能重叠。此时需通过两多边形的边边求交来判断是否重叠。当存在交点时，既表明两多边形重叠，否则不重叠。,湖北大学数计学院,18,6.3 直线段裁剪,裁剪的目的 判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分 裁剪的处理的基础 图元关于窗口内外关系的判别 图元与窗口的求交 假定条件 矩形裁剪窗口：xmin,xmaxXymin,ymax 待裁剪线段：,湖北大学数计学院,19,6.3 直线段裁剪,在二维坐标系中，需要在观察坐标系下对窗口进行裁剪，即只保留窗口内的那部分图形，去掉窗口外的图形。 假设窗口是标准矩形，即边与坐标轴平行的矩形，由上

8、（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）四条边描述。,湖北大学数计学院,20,6.3 直线段裁剪,待裁剪线段和窗口的关系 线段完全可见 显然不可见 线段至少有一端点在窗口之外，但非显然不可见,为提高效率，算法设计时应考虑： (一）快速判断情形(1)(2)； (二) 设法减少情形(3)求交次数和每次求交时所需的计算量。,湖北大学数计学院,21,6.3 直线段裁剪,实交点是直线段与窗口矩形边界的交点。 虚交点则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点。,湖北大学数计学院,22,6.3 直线段裁剪点裁剪,点裁剪 点(x, y)在窗口内的充分必要条件

9、是：,问题：对于任何多边形窗口，如何判别？,湖北大学数计学院,23,6.3 直线段裁剪直接求交算法,直线与窗口边都写成参数形式，求参数值。,湖北大学数计学院,24,6.3 直线段裁剪 Cohen-SutherLand算法(编码算法),基本思想：对每条直线段p1(x1,y1)p2(x2,y2)分三种情况处理： (1) 直线段完全可见，“简取”之。 (2) 直线段完全不可见，“简弃”之。 (3) 直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。,裁剪过程是递归的。,湖北大学数计学院,25,6.3 直线段裁剪 Cohen-SutherLand算法

10、(编码算法),特点：对显然不可见线段的快速判别 编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；,湖北大学数计学院,26,6.3 直线段裁剪 Cohen-SutherLand算法(编码算法),(1)若code1|code2=0，对直线段应简取之。 (2)若code1 P1:(-1,1/2); 编码(0000) 判别知非完全可见，且P1在窗口内，因此交换P1P2得新线段P1P2； P1：(1/2, 3/2)；编码 (1000) P2：(-1, 1/2)； 编码 (0000),(3) 求上边交点，得 P1(-1/4, 1) P2(-1,

11、1/2)；并编码，两端点编码全部为0，线段完全可见，程序结束,P1,湖北大学数计学院,36,求交测试顺序固定(左上右下） 最坏情形，线段求交四次。,6.3 直线段裁剪 Cohen-SutherLand算法(编码算法),1）特点：用编码方法可快速判断线段- 完全可见和显然不可见。 2）特别适用二种场合： 大窗口场合； 窗口特别小的场合(如, 光标拾取图形时, 光标看作小的裁剪窗口。）,湖北大学数计学院,37,6.3 直线段裁剪 中点分割法,想法：从P0点出发找出 距P0最近的可见点，从 P1点出发找出距P1最近 的可见点。 取中点Pm=(P1+P2)/2。 （算法见框图）,湖北大学数计学院,38

12、,6.3 直线段裁剪 中点分割法,基本思想： 当对直线段不能简取也不能简弃时，简单地把线段等分为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外。,湖北大学数计学院,39,6.3 直线段裁剪 中点分割法,算法步骤： (1)输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。 (2)对p1、p2进行编码：点p1的编码为code1，点p2的编码为code2。 (3)若code1|code2=0，对直线段应简取之，保留当前直线段的端点坐标，转(5)；否则，若code1&code20，对直线段可简弃之，转(5)；当

13、上述两条均不满足时，进行步骤(4)。 (4)求出直线段的中点M，将p1M、p2M入栈。 (5)当栈不空时，从栈中弹出一条直线段，取为p1p2，转(2)进行处理。否则，继续(6)。 (6)当栈为空时，合并保留的直线段端点，得到窗口内的直线段p1p2。用直线扫描转换算法画出当前的直线段p1p2，算法结束。,湖北大学数计学院,40,核心思想：通过二分逼近来确定直线段与窗口的交点。,2.中点分割算法,重新构造算法步骤： (1)若code1|code2=0，对直线段应简取之，结束；否则，若code1&code20，对直线段可简弃之，结束；当这两条均不满足时，进行步骤(2)。 (2)找出该直线段离窗口边界

14、最远的点和该直线段的中点。判中点是否在窗口内：若中点不在窗口内，则把中点和离窗口边界最远点构成的线段丢掉，以线段上的另一点和该中点再构成线段求其中点；如中点在窗口内，则又以中点和最远点构成线段，并求其中点，直到中点与窗口边界的坐标值在规定的误差范围内相等，则该中点就是该线段落在窗口内的一个端点坐标。 (3)如另一点在窗口内，则经(2)即确定了该线段在窗口内的部分。如另一点不在窗口内，则该点和所求出的在窗口上的那一点构成一条线段，重复步骤(2)，即可求出落在窗口内的另一点。,湖北大学数计学院,42,例如：,特点： 1、只需使用加法和移位即可完成，无需乘除，效率高 2、易于用算法实现,湖北大学数计

15、学院,43,6.3 直线段裁剪参数化裁剪方法（Cyrus-Beck 算法）,特点：可对任意凸多边形窗口实现二维和三维裁剪,考虑一个凸多边形 R 和一个线段 P1P2， P1 P2 与 R 最多只有两个交点,设 A 是 R 边界上一点，N 是该区域边界 在 A 点的内法向量,将P1 P2用参数方程表示：P(t) (P2P1) t P1 则线段上任一点P(t), 与 N 的点积有三种可能,(1) P(t) 在多边形外侧：N 。(P(t)A) 0,湖北大学数计学院,44,6.3 直线段裁剪参数化裁剪方法（Cyrus-Beck 算法）,因此，P(t)在凸多边形内的充要条件是：对凸多边形边界上任意一点A

16、和该处内法向量N，都有：N (P(t)A) 0,上述问题是一个线性规划问题，可求得满足条件的一系列 t 值，在实际操作中我们只关心其最大和最小值，它们对应可见线段区间的端点,湖北大学数计学院,45,6.3 直线段裁剪参数化裁剪方法（Cyrus-Beck 算法）,讨论：,(1) 当 Ni (P2P1) 0 时， Ni 垂直于(P2P1) ，第 i 条边与P1P2 平行，无交点,(2) 当 Ni (P2P1) 0 时， P1 在该边外侧 ，可求出交点 t i ，并将其归入下限组,(3) 当 Ni (P2P1) 0 时， P2 在该边外侧 ，可求出交点 t i ，并将其归入上限组,讨论(续)：,当

17、t l t h , 则 t l 和 t h 是可见线段的端点参数，否则线段 在区域之外,前述判别式 0 对应线段与边的交点，因此当 Ni (P2P1) 0 时可求出 t 为:,(5) 可见线段为下限组中的最大值至上限组中的最小值之间的线段 即：,通过上述方法可以求出任意凸多边形对线段的裁剪,湖北大学数计学院,48,6.3 直线段裁剪 Liang-Barsky算法,分析,推导,湖北大学数计学院,49,特殊处理：,算法步骤： (1)输入直线段的两端点坐标：(x1,y1)和(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。 (2)若x=0，则p1=p2=0。此时进一步判断是否满

18、足q10且q20，则进一步计算u1和u2。算法转(5)。 (3)若y=0，则p3=p4=0。此时进一步判断是否满足q30且q20，则进一步计算u1和u2。算法转(5)。 (4)若上述两条均不满足，则有pk0（k=1,2,3,4）。此时计算u1和u2。 (5)求得u1和u2后，进行判断：若u1u2，则直线段在窗口外，算法转(7)。若u1u2，利用直线的参数方程求得直线段在窗口内的两端点坐标。 (6)利用直线的扫描转换算法绘制在窗口内的直线段。算法结束。,湖北大学数计学院,51,6.4 多边形裁剪,错觉：直线段裁剪的组合？ 新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边

19、界？,湖北大学数计学院,52,6.4 多边形裁剪,2）一个凹多边形可能被裁剪成几个小的多边形，如何 确定这些小多边形的边界？,湖北大学数计学院,53,6.4 多边形裁剪Sutherland-Hodgeman多边形裁剪,基本思想,湖北大学数计学院,54,6.4 多边形裁剪Sutherland-Hodgeman多边形裁剪,湖北大学数计学院,55,6.4 多边形裁剪Sutherland-Hodgeman多边形裁剪,算法实施策略： 为窗口各边界裁剪的多边形存储输入与输出顶点表。在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。 窗口的一条边以及延长线构成的裁剪线把平面分为

20、两个区域，包含有窗口区域的一个域称为可见侧；不包含窗口区域的域为不可见侧。,湖北大学数计学院,56,6.4 多边形裁剪Sutherland-Hodgeman多边形裁剪,沿着多边形依次处理顶点会遇到四种情况：,多边形边与裁剪线相对位置的四种情况与处理方法： (1) 位于可见一侧：输出终点，作为新多边形顶点 (2) 位于不可见一侧：不输出 (3) 由可见到不可见：输出与裁剪线的交点 (4) 由不可见到可见：输出与裁剪线的交点及终点,湖北大学数计学院,57,6.4 多边形裁剪Sutherland-Hodgeman多边形裁剪,特点：,湖北大学数计学院,58,6.4 多边形裁剪 Weiler-Athen

21、ton算法,裁剪窗口为任意多边形（凸、凹、带内环）的情况： 主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为B,湖北大学数计学院,59,主多边形和裁剪多边形把二维平面分成两部分。 内裁剪：AB 外裁剪：A-B,6.4 多边形裁剪 Weiler-Athenton算法,裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界,湖北大学数计学院,60,6.4 多边形裁剪 Weiler-Athenton算法,如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类： 进点：主多边形边界由此进入裁剪多边形内

22、 如，I1,I3, I5, I7, I9, I11 出点：主多边形边界由 此离开裁剪多边形区域. 如， I0,I2, I4, I6, I8, I10,湖北大学数计学院,61,6.4 多边形裁剪 Weiler-Athenton算法,1）建顶点表； 2）求交点； 3）裁剪 ,Weiler_Athenton裁剪算法（内裁剪）步骤： 1、建立主多边形和裁剪多边的顶点表 2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。 3、裁剪 如果存在没有被跟踪过的交点，执行以下步骤： (1)建立裁剪结果多边形的顶点表 (2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中 (3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界 (4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多