ch05 二维图形变换及裁剪0402.ppt

1、1,第5章 二维图形变换及裁剪,2,第5章 二维图形变换及裁剪,5.1 变换的数学基础 5.2 二维几何变换 5.3 二维图形裁剪,3,5.1 变换的数学基础,5.1.1 矢量及其运算 5.1.2 矩阵及其运算 5.1.3 齐次坐标,4,5.1.1 矢量及其运算,矢量的定义 矢量：n元组。(由n个实数组成的集合) 如：二维矢量(x,y)，三维矢量(x,y,z),5,5.1.1 矢量及其运算,矢量 矢量的加法,6,5.1.1 矢量及其运算,矢量的数乘 矢量的点积(内积) U V=|U | |V | cos,7,5.1.1 矢量及其运算,矢量点积(内积)的性质：,8,5.1.1 矢量及其运算,矢量

2、点积(内积)的性质： 交换律 结合律 分配律,9,5.1.1 矢量及其运算,矢量的长度 单位矢量：长度为1的矢量(i,j,k,e,) 矢量的夹角:,10,5.1.1 矢量及其运算,矢量的叉积(向量积) 2个互不平行的矢量，其叉积形成一个与2个矢量都垂直的新的矢量，它的方向符合右手判别法，大小为： | UV |=|U|*|V|*Sin 如果U平行于V，则UV=(0,0,0),11,5.1.1 矢量及其运算,矢量叉积的性质： 结合律 分配律,12,5.1.1 矢量及其运算,矢量叉积的性质： 在直角坐标系下：,13,5.1 变换的数学基础,5.1.1 矢量及其运算 5.1.2 矩阵及其运算 5.1.

3、3 齐次坐标,14,5.1.2 矩阵及其运算,矩阵的定义： 由mn个数按m行n列排列的一个整体，简称mn矩阵。 其中，aij 称为矩阵A的第i 行第j 列元素,15,矩阵运算 加法 设A，B为两个具有相同行和列数的矩阵， 数乘 kA = k*aij |i=1.m, j=1,. n,5.1.2 矩阵及其运算,16,乘法 设A为mn矩阵，B为np矩阵 单位矩阵 在一矩阵中，主对角线各元素aii =1，其余元素皆为0的矩阵称为单位矩阵。n阶单位矩阵通常记作In 。 Am n = Am n In,5.1.2 矩阵及其运算,17,逆矩阵 若矩阵A存在AA-1=A-1A=I，则称A-1为A的逆矩阵。 矩阵

4、的转置 把矩阵A=(aij)mn的行和列互换而得到的nm矩阵称为A的转置矩阵，记作AT 。 (AT) T = A (A+B)T = AT + BT (aA)T = aAT (AB)T = BT AT 当A为n阶矩阵，且A=AT ，则A是对称矩阵。,5.1.2 矩阵及其运算,18,矩阵运算的基本性质 加法的交换律与结合律 A+B=B+A; A+(B+C)=(A+B)+C 数乘的分配律及结合律 a(A+B) = aA+aB; a(A B) = (aA) B=A (aB) (a+b)A = aA + bA a(bA) = (ab)A,5.1.2 矩阵及其运算,19,矩阵乘法的结合律及分配律 A(B

5、C) = (A B)C (A+B) C = A C+ B C C (A+B) = C A + C B 矩阵的乘法不满足交换律！,5.1.2 矩阵及其运算,20,5.1 变换的数学基础,5.1.1 矢量及其运算 5.1.2 矩阵及其运算 5.1.3 齐次坐标,21,5.1.3 齐次坐标,所谓齐次坐标表示法就是由n+1维向量表示一个n 维向量。如n 维向量(P1,P2, ,Pn)表示为（hP1,hP2,hPn，h），其中h是任一不为0的比例系数，称为哑坐标或比例因子。 h可以取不同的值，所以同一点的齐次坐标不是唯一的。如普通坐标系下的点（2,3）变换为齐次坐标可以是(1,1.5,0.5)、(4,6

6、,2)、(6,9,3)等等。 普通坐标与齐次坐标的关系为“一对多” 由普通坐标h齐次坐标 由齐次坐标h普通坐标 当h=1时，称为规格化的齐次坐标。 在计算机图形学中，通常使用规格化的齐次坐标。,22,例：(x,y)点对应的齐次坐标为: (x,y)点对应的齐次坐标为三维空间的一条直线：,5.1.3 齐次坐标,23,齐次坐标的作用 1. 将各种变换用阶数统一的矩阵来表示。使变换矩阵具有统一的表示形式，便于变换的合成(组合变换)及软、硬件实现。 2. 便于表示n维无穷远点。 例如：(xh, yh, h)，令h等于0时，表示二维平面中的无穷远点。,5.1.3 齐次坐标,24,第5章 二维图形变换及裁剪

7、,5.1 变换的数学基础 5.2 二维几何变换 5.3 二维图形裁剪,25,5.2 二维几何变换,1. 平移变换 2. 缩放变换 3. 旋转变换 4. 变形变换 5. 反射(对称)变换 6. 组合变换,26,总结以上这些变换后的图形结果，可以得到这样的结论： 图形变化了，但原图形的构成规则（拓扑关系）没有改变； 图形发生的变化，是其顶点位置（几何信息）的改变决定的。 这种通过维持图形的拓扑关系不变，而仅改变图形的几何位置来实现图形改变的方法，我们称之为图形的几何变换。,几种常见的几何变换：旋转、错切、缩放。,5.2 二维几何变换 概 述,27,几何变换： 在二维图形处理过程中，常常需要对平面图

8、形的形状、尺寸、方向和位置进行修改，来达到改变图形的目的。 几何变换：是一种线性变换。 对原来图形中一点的坐标通过变换生成一个新的点坐标；对原来图形中的一条直线的变换是通过直线上的两点作变换生成新的端点坐标，然后连接这两个新的端点，便得到变换后的直线；类似的，可以进行各种图形的几何变换。 几何变换的表示采用矩阵形式，称为变换矩阵；点的坐标表示采用齐次坐标形式。故几何变换操作的过程是将变换矩阵M作用于齐次坐标点P生成新的坐标点P,即P=MP。,5.2 二维几何变换 概 述,28,P(x,y),1. 平移变换,点的平移变换是指该点在X轴和Y轴方向上分别移动一段距离。设图形上点P(x,y)，在X轴和

9、Y轴方向分别移动Tx和Ty，结果生成新的点P(x,y),如图所示，则有,y,x,P(x,y),Tx,Ty,其中TX,TY称为点在X轴和Y轴上的位移。 用齐次坐标和矩阵形式可表示为：,29,令二维平移变换矩阵为： 如果Tx 或Ty大于零，则点向右或向上移动； 如果Tx或Ty小于零，则点向左或向下移动。,1. 平移变换,30,2. 缩放变换,点的缩放是指将该点沿X轴和Y轴方向按比例缩小或放大。 设图形上的点P(x,y)，在X轴和Y轴方向分别作Sx和Sy的缩放，结果生成新的点坐标P(x,y)，如图所示，则： 其中Sx，Sy称为点在X轴和Y轴上的缩放比例。 用齐次坐标和矩阵形式可表示为：,以坐标原点为

10、放缩参照点，不仅改变了物体的大小和形状，也改变了它离原点的距离。,当|Sx|=|Sy|时，变换前的图形与变换后的图形相似。 当|Sx|=|Sy|1时，图形将放大，并远离坐标原点； 当|Sx|=|Sy|1时，图形将缩小，并靠近坐标原点； 当|Sx|Sy|时，图形将发生畸变。,令二维缩放变换矩阵为：,2. 缩放变换,32,点的旋转变换是将点绕坐标原点旋转一角度的坐标变换。,用齐次坐标和矩阵形式可表示为,二维旋转矩阵R2(),3. 旋转变换,设有图形上点P(x,y)，将其绕原点旋转角度(逆时针旋转为正)，结果生成的新的点坐标P(x,y)。顺时针时的变换矩阵？,33,4. 变形变换,变形变换是用来产生

11、一个目标图形的失真，也称错切变换。现考虑y-变形和x-变形两种： y-变形是将点P(x,y)变换到点P(x,y)，使x=xy=xshy+y(shy0) 其中shy为变形系数。,shy0， shy0，,错切参数shy=tg ，表示y方向的错切程度。,34,4. 变形变换,x-变形变换是指将点P(x,y)变换到点P(x,y)，应有 x=x+yshx (shx0) y=y 其中shx为变形系数，shx的符号决定了图形向右或向左变形。,shx0， shx0，,错切变换引起图形角度关系的改变，甚至导致图形发生变形。,错切参数shx=tg ，表示X方向的错切程度。,35,5.对称变换(反射变换),当b=d

12、=0,a=-1,e=1时，(x y 1)=(-x y 1)： 与y轴对称的反射变换。 当b=d=0,a=1,e=-1时，(x y 1)=( x -y 1)： 与x轴对称的反射变换。 当b=d=0,a=e=-1时，(x y 1)=(-x -y 1)： 与原点对称的反射变换。 当b=d=1,a=e=0时，(x y 1)=(y x 1)： 与y=x对称的反射变换。 当b=d=-1,a=e=0时，(x y 1)=(-y -x 1)： 与y=-x对称的反射变换。,36,6. 组合变换,如何实现复杂变换？ 实际上，一般的图形变换更多的是组合变换，即由一系列基本的几何变换组合而成。 则组合变换矩阵也可由一系

13、列基本几何变换矩阵的乘积来表示。 矩阵的乘法满足结合律，但不满足交换律。 下面将举例说明组合变换的方法。,37,6. 组合变换 例1,例:对一线段先放大2倍(即Sx=Sy=2)，再平移Tx=10，Ty=0。 解:设点(x,y)为线段上的任意一点，点(x,y)为点(x,y)放大后的坐标，则：x,y,1T=S2(2,2)x,y,1T 设点(x,y)为点(x,y)经平移后的坐标，则：x,y,1T= T2(10,0) x,y,1T， 即：x,y,1T= T2(10,0) S2(2,2) x,y,1T,38,6. 组合变换 例1（续）,令： M即为组合变换矩阵。 设线段的两端点坐标为(x1,y1) 和(

14、x2,y2)，经M变换后，得到新的坐标(x1,y1)和(x2,y2)，连接这两个新的坐标点便生成了变换后的线段。,39,6. 组合变换 例2,例：对一图形，绕平面上的一点(Cx,Cy) 作旋转变换，旋转角度为， 计算其变换矩阵。 解：旋转变换是绕坐标原点旋转的，此处不能直接使用旋转变换矩阵，应先将点(Cx,Cy)平移至原点，然后作旋转变换，最后再把该点移回原处。设点(x,y)为图形中的点，点(x,y)为点(x,y)经变换后的坐标，则: x,y,1T = T2(Cx,Cy) R2()T2(-Cx,-Cy) x,y,1T 组合变换矩阵为：,40,6. 组合变换 例3,图形关于任意的反射轴y =a

15、+bx 的反射(对称)变换。,41,6. 组合变换 例3（续）,解： 1. 将坐标原点平移到(0,a)处 2. 将反射轴（已平移后的直线）按顺时针方向旋转角，使之与x轴重合 3. 图形关于x轴的反射变换 4. 将反射轴逆时针旋转角 5. 恢复反射轴的原始位置 组合变换矩阵为：,42,6. 组合变换 例4,通用固定点缩放 平移物体使固定点与坐标原点重合； 对于坐标原点缩放； 用步骤1的反向平移将物体移回原始位置。,43,6. 组合变换 例5,通用定向缩放 比例变换中的比例因子Sx，Sy只能在x轴方向或y轴方向起作用。实际图形变换中，不仅是在x，y方向变换，往往要求在任意方向进行比例变换。通过旋转

16、变换和比例变换的组合，可以实现任意方向的比例变换。,绕=450方向缩放,s1,s2,44,6. 组合变换 小结,矩阵运算满足结合律，但不满足交换律。所以，一般情况下，不同顺序的变换将得到不同的结果。,刚体变换。 直线段或多边形的变换可通过每个顶点的变换，再在新位置重画图形得到。曲线的变换：变换矩阵乘以曲线的参数方程。,45,5.2.1 二维几何变换 小结,整体比例 变换,用规范化齐次坐标表示的二维基本几何变换矩阵是一个33的方阵：,46,5.2.1 二维几何变换 小结,上面讨论的五种基本变换(平移、比例、旋转、反射(对称)和错切)给出的都是点变换的公式，对于复杂对象(如线框模型)，图形的变换实

17、际上都可以通过点变换来完成。 例如直线段的变换可以通过对两个顶点坐标进行变换，连接新顶点得到变换后的新直线； 多边形的变换可以通过对每个顶点进行变换，连接新顶点得到变换后的新多边形来实现。 曲线的变换可通过变换控制多边形的控制点并重新画线来完成。,47,5.2.1 二维几何变换 小结,符合下面形式的坐标变换称为二维仿射变换（Affine Transformation）。 变换后的坐标x和y都是变换前的坐标x和y的线性函数。参数aij是由变换类型确定的常数。 仿射变换具有平行线变换成平行线，有限点映射到有限点的一般特性。平移、比例、旋转、反射(对称)和错切五种变换都是二维仿射变换的特例。 任何一

18、组二维仿射变换总可表示为这五种变换的组合。因此，平移、比例、旋转、反射(对称)的仿射变换保持变换前后两直线间的角度、平行关系和长度之比不改变。,48,第5章 二维图形变换及裁剪,5.1 变换的数学基础 5.2 二维几何变换 5.3 二维图形裁剪,49,5.3 二维图形裁剪,5.3.1 图形学中常用的坐标系 5.3.2 直线段的裁剪 5.3.3 多边形的裁剪 5.3.4 字符的裁剪,50,裁剪：确定图形中哪些部分落在裁剪窗口之内，哪些落在裁剪窗口之外,以便只显示落在裁剪窗口内/外的那部分图形。这个选择过程称为裁剪。 图形裁剪算法，直接影响图形系统的效率。,5.1 二维图形的裁剪,51,Displ

19、ay Window,Window3,Window2,Window1,外裁剪在多窗口场合较常用。例如： Display Window：内裁剪，针对Window13外裁剪； Window2：内裁剪，针对Window1、3外裁剪； Window1、3：各自内裁剪。,内裁剪、外裁剪,52,第5章 二维光栅图形的处理,5.1 二维图形的裁剪 5.1.1 直线段的裁剪 5.1.2 多边形的裁剪 5.1.3 字符的裁剪 5.2 走样与反走样,53,5.1.1 直线段的裁剪,1. 直接求交算法 2. Cohen-SutherLand算法(编码法) 3. 中点分割算法 4. Nicholl-Lee-Nichol

20、l算法 5. Cyrus-Beck算法(参数法) 6. LiangBarskey算法 7. 凹多边形窗口的裁剪,54,5.1.1 直线段的裁剪,任何图形都可能包含点、直线、曲线、字符和多边形等图元， 但它们都可以分解成点的集合。 能否将直线段裁剪问题简化为点的裁剪问题？ 假设窗口的左下角坐标为(xL,yB ),右上角坐标为(xR,yT )，对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式： xL = x = xRand yB = y = yT否则，P点就在窗口外。,问题：对于任意多边形窗口，如何判别？ 点与多边形的内外关系判别。,55,5.1.1 直线段的裁剪,直线段裁剪是复杂图

21、形裁剪的基础。 直线段常见； 可构成多边形； 复杂的曲线可以通过直线段来逼近。 曲线裁剪可否化为直线段的裁剪？,56,5.1.1 直线段的裁剪,直线段与窗口的关系通常有以下三种情况： 整个线段全在窗口内； 整个线段全在窗口外； 线段部分在窗口外，部分在窗口内。 当窗口为凸多边形时，任何一条直线段只会至多有一段在窗口内： 当一条直线段的两个端点全在窗口内时，该直线段整个在窗口内； 当一条直线段的两个端点，一个在窗口内，一个在窗口外时，该直线段部分在窗口内，部分在窗口外； 当一条直线段的两个端点全在窗口外时，该直线段可能整个在窗口外，也可能部分在窗口内，部分在窗口外。,57,5.1.1 直线段的裁

22、剪,直线段裁剪：实质上就是快速判断出线段与裁剪窗口的关系； (1)线段完全可见； (2)显然不可见； (3)其它。 然后对于可见部分，求出端点，绘制线段。 为提高效率： 快速判断情形(1)、(2)； 对于情形(3)，应设法快速求出线段和裁剪窗口的交点。,58,1. 直接求交算法,如何判断线段是否显然不可见？ 直线与窗口边如何求交？,59,1. 直接求交算法,直线段与窗口边如何求交？两线段求交 参数式、非参数式 设直线过P1(x1,y1)，P2(x2,y2)，m为斜率，则：,直线与窗口各边的交点为： L，xL，y=m(xL-x1)+y1，m R，xR，y=m(xR-x1)+y1，m 用斜率解释

23、Y, yT，x=x1+(1/m)(yT-y1)，m0 B，yB，x=x1+(1/m)(yB-y1)，m0 总会求出一个交点，即使交点位于窗口外。,60,1. 直接求交算法,解方程组求出交点参数 tl、te0,1,61,2. Cohen-SutherLand算法,这是一个最早最流行的线段裁剪算法。自1968年以来被公认为是一个好的算法也称编码算法。 该算法通过初始测试来减少要计算的交点数目从而加快线段裁剪算法的速度。 基本思想： 对于每条线段P1P2分为三种情况处理: （1）若P1P2完全在窗口内，则显示该线段P1P2 。 （2）若P1P2明显在窗口外，则丢弃该线段。 （3）若线段不满足（1）或

24、（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 递归的裁剪过程,62,2. Cohen-SutherLand算法,为快速判断，采用如下编码方法： 由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码： CtCbCrCl（上下右左）； 直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪窗口边界的位置。 各位编码含义，端点坐标(x,y)： 上：if yyT, Ct=1, else, 0; 下：if yxR, Cr=1, else, 0; 左：if xxL, Cl=1, else, 0;,63,2. Cohen-Sut

25、herLand算法,任何位赋值为1，代表端点落在相应的位置上，否则该位为0。 例如：端点B：区域码为 0000； 端点A：区域码为 1001；,64,2. Cohen-SutherLand算法原理,编码将窗口及其邻域分为5个区域： 内域：区域(0000)。 上域：区域(1001, 1000, 1010)。 下域：区域(0101, 0100, 0110)。 右域：区域(1010, 0010, 0110)。 左域：区域(1001, 0001, 0101)。 对线段的两个端点的区号进行“位与”运算，可知这两个端点是否同在窗口的同一侧(上、下、左、右)； 如果两端点的编码均为0000，表示直线在窗口内

26、。 如果两端点的编码相与不为0000，表示直线在窗口外。 如果两端点的编码不全为0000，但相与为0000，则该直线可能部分可见，需计算直线段与窗口的交点，确定哪一部分可见。,65,2. Cohen-SutherLand算法原理,若code1=0，且code2=0，则P1P2完全在窗口内，“取”； 若code1 /*done: 完成；draw: 可见；*/Unsigned char code1,code2； /*端点1，端点2的编码*/ While (!done) if (判断code1,code2,若为第一种情况) done = TRUE; draw = TRUE; else if (为第二

27、种情况) done = TRUE; draw = FALSE; else if (检查code1 ,若在窗口内) 交换端点及端点的编码；以左，右，下，上的次序对端点1进行判断及求交；将交点的值赋给端点1 /*End of while*/,69,2. Cohen-SutherLand算法小结,最坏情形，线段求交四次。（左、右、下、上）,P1（0101）,P2（1010）,70,2. Cohen-SutherLand算法小结,本算法的优点在于简单，易于实现。 用编码方法来快速判断线段和裁剪窗口的关系。 他也可以简单的描述为将直线段在窗口外的部分删去(按左、右、下、上的顺序依次进行)，剩余部分就是可

28、见部分。 在这个算法中求交点是很重要的，他决定了算法的速度。 尤其适用于大窗口场合及小窗口场合。 大部分线段完全可见或完全不可见。 本算法对于其他形状的窗口是否同样有效就值得讨论了。这也说明了在图形算法中，没有几个是对大多数情况有效的。,71,3. 中点分割算法,基本思想：从P0点出发找出离P0最近的可见点，从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。 可看作Cohen-Sutherland算法一个硬件实现的特例。,A,B,72,3. 中点分割算法,与Cohen-Sutherland算法一样，首先对线段端点进行编码，并把线段与窗口的关系分为三种情况： (1)线段

29、完全可见； (2)显然不可见； (3)其它 对前两种情况，进行一样 的处理； 对于第三种情况， 用中点分割的方法求出线 段与窗口的交点。（A、B分别为距P0 、 P1最近的可见点，Pm为P0P1中点）,73,3. 中点分割算法,求距离P0最近可见点P,74,3. 中点分割算法,中点分割法：从P0出发找距离P0最近可见点： 先求出P0P1的中点Pm, 若P0Pm不是显然不可见的，并且P0Pm在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1； 否则取PmP1代替P0P1。 再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时P

30、m收敛于交点。 从P1出发找距离P1最近可见点的方法类似。,75,3. 中点分割算法小结,与Cohen-Sutherlang算法在思想上没有任何区别。 采用编码的方法快速判断直线段与裁剪窗口的关系。 区别在于两者求与裁剪窗口交点的方法不同。 中点分割算法：二分查找 Cohen-Sutherlang算法：直接计算 更利于硬件实现，可看作C-S算法的一个特例。,76,从P0 出发找最近可见点的方法: 先求出P0 P1 的中点Pm 若P0 Pm 不是显然不可见的，并且P0 Pm 在窗口有 可见部分，则距P0 最近的可见点一定落在P0 Pm 上，所以用P0 Pm 代替P0 P1； 否则取PmP1 代替

31、P0 P1 再对新的P0 P1 求中点Pm 。重复上述过程，直到长度小 于给定的控制常数为止，此时Pm 收敛于交点。 从p1出发找最近可见点采用上面类似方法。,中点分割法,可取为1个象素,77,5. Cyrus-Beck算法,前述算法均假设裁剪窗口为一规则的矩形窗口。 若裁剪窗口为非规则矩形的任意凸多边形时，以上算法不再完全适用。,78,5. Cyrus-Beck算法,考虑直线段的参数方程：,直线上任一点的参数t为：,79,5. Cyrus-Beck算法,裁剪线段P1P2：tL=1/6；tR=5/6 tB=-1/5；tT=7/5 部分t0,1。,0,裁剪线段P3P4： tL=3/8；tR=7/

32、8 tB=0；tT=2/3 所有的t0,1。,部分可见线段：,可否简单利用交点的t值进行判断？,80,5. Cyrus-Beck算法,裁剪线段P1P2： tL=-1/2；tR=3/2 tB=3/2；tT=-1/2 不是所有的t 0,1 。,0,裁剪线段P3P4： tL=-5；tR=-4 tB=-1/2；tT=3/2 不是所有的t 0,1。,完全可见及完全不可见线段：,可见，不能简单的利用交点的t值来进行裁剪。必须找到一个可靠的方法，用来判定线段上的一点是位于窗口之内、之外或边界上。,81,5. Cyrus-Beck算法原理,下限： 上限： D=P2P1,82,5. Cyrus-Beck算法,C

33、yrus-Beck算法的基本思想是采用法矢量的概念来判定线段上的一点是在窗口之内，之外，还是在窗口的边界上。 对任意凸多边形，其边界上任一点a处的内法矢量ni满足： ni(ba)0其中： b为多边形边界上另外一点。 ni为过a点边界的内法矢量； no为外法矢量。,V1V2=|V1| |V2| cos,83,如果f是凸区域边界上的一点，n是凸区域边界在f点的内法向量，则对于线段P1P2 上的一点P(t)，满足下式： 若nP(t)f0，则表示P(t)f指向区域的外部(相对当前边)； 若nP(t)f=0，则表示P(t)f与包含f的边界重合且与内法矢量n垂直； 若nP(t)f0，则表示P(t)f指向区

34、域的内部(相对当前边) 。 由此可知，P(t)满足nP(t)f=0的t值的点即为直线与边界的交点。,nP(t)f0,5. Cyrus-Beck算法原理,84,Cyrus-Beck算法中对于线段的可见性是这样判断的： 设：内法矢量ni与连接线段上一点P(t)至边界上一点fi的矢量的点积为： ni P(t)-fi，(i=1,2,3.) 与式子P(t)=P1 +(P2P1)t，(0t1) 合并得： ni P1+(P2P1)t - fi，(i=1,2,3.) 则线段上一点在边界上的条件为： ni P1 +(P2P1)t-fi=0 (i=1,2,3.),nP(t)f0,nP(t)f=0,nP(t)f0,

35、fi,5. Cyrus-Beck算法原理,85,线段上点在边界上的条件为： ni P1 +(P2P1)t - fi=0 (i=1,2,3.) 令：D=P2P1；wi=P1fi，可得交点： 如果D ni=0，则 要么D垂直于ni， 要么P2=P1，线段退化为一点： 如果wini0，表示点位于区域和窗口之外； 如果wini0，表示点位于区域和窗口边界上； 如果wini0，表示点位于区域和窗口之内。,5. Cyrus-Beck算法原理,nP(t)f0,nP(t)f=0,nP(t)f0,fi,式5.1.11,86,否则，可根据“式5.1.11”求出线段和裁剪窗口的交点。对于交点的t值选择： 首先，要符

36、合0t1； 其次，对于凸窗口来说，每一个线段与其至多有两个交点（既有两个相应的t值）。所以我们可以把计算出的t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。 这样，只要找出下限组中的最大值及上限组中的最小值，就可确定可见线段部分了。 有了这些，整个算法就可以建立了。 分组的依据？,5. Cyrus-Beck算法原理,87,5. Cyrus-Beck算法原理,下限： 上限： D=P2P1,下限组以D ni0 为特征，表示在该处沿 P1P2方向前进将接近或 进入多边形内侧。,上限组以D ni0为特征，表示在该处沿P1P2方向前进将越来越远地离开多边形区域。

37、,88,置下限最小值 tL=0；上限最大值 tU=1 while 对于每一个窗口边i do begin if Dni=0 then If wini0 then /*寻找下限组的tL值*/ If t 0 then tL=max(t,tL) else /*寻找上限组的tU值*/ if t 1 then tU=min(t,tU) end if tL tU then 画从P(tL)至P(tU)的线段 end of algorithm,5. Cyrus-Beck算法算法描述,89,该算法比Cohen-Sutherland等算法适用的范围更广一些，它可以对任何凸多边形适用，但对于凹多边形就失效了。为了解决

38、这个问题，又引入对凹多边形进行判断和分割的算法：叉积法，旋转法。 当凸多边形是矩形窗口且矩形的边与坐标轴平行时，该算法退化为Liang-Barsky算法。,5. Cyrus-Beck算法小结,90,6. Liang-Barsky算法,写入图形学教科书的中国人的算法。 设要裁剪的线段是P1P2。P1P2和窗口边界交于A,B,C,D四点，见图。,算法的基本思想是从A,B和P1三点中找出最靠近P2的点，图中要找的点是P1。从C,D和P2中找出最靠近P1的点。图中要找的点是C点。那么P1C就是P1P2线段上的可见部分。,本质上，可看作是一种特殊形式的Cyrus-Beck算法。,91,6. Liang-

39、Barsky算法,线段的参数表示： x=x1 + tx y=y1 + ty 0t 1, x = x2-x1, y=y2-y1 窗口边界的四条边分为两类：始边和终边。,92,求出P1P2与两条始边的交点参数t1、 t2 ，令tL=max(t1 ,t2,0)，则tL即为三者中离p2最近的点的参数； 求出p1p2与两条终边的交点参数t3、 t4，令tU=min(t3,t4,1) ，则tU即为三者中离p1最近的点的参数； 若tU tL,则可见线段区间为tL , tU；否则，p1p2完全不可见，如： p1p2，tL=t2 , tU=t3, tUtL,6. Liang-Barsky算法,93,6. Lia

40、ng-Barsky算法,裁剪区域的内部可表示为： xLxxR ，yByyT 直线段的参数表示为： x=x1+tx，y=y1+ty， 0t1,x=x2-x1 ,y=y2-y1 ； 若直线段上一点位于窗口内，则：,xL x1+tx xR and yB y1+ty yT ； 即：-txx1-xL , txxR-x1 ；-tyy1-yB , tyyT-x1 ； 记为： tiDi / Qi ，i=L,R,B,T QL= - xQR= x QB= - y QT= y DL= x1-xLDR= xR-x1DB= y1-yB DT= yT-y1,94,6. Liang-Barsky算法,xL x1+tx xR

41、 and yB y1+ty yT ； 交点计算： QL= - x DL= x1-xL QR= x DR= xR-x1 QB= - y DB= y1-yB QT= y DT= yT-y1 交点为：ti= Di / Qi ,i=L,R,B,T 如果Qi 0 ，则ti为与终边交点参数,95,6. Liang-Barsky算法,有Qi =0的情况时(线段与窗口边平行)： 若有任意一个i , (i=L,R,B,T) 使得Di 0和QR=0，DR0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。,QL= -x D

42、L= x1-xL QR= x DR= xR-x1 QB= -y DB= y1-yB QT= y DT= yT-y1,96,6. Liang-Barsky算法,对于每条直线，可以计算出参数tL和tU，它们定义了在裁剪矩形内的线段部分： tL的值由线段从外到内遇到的矩形边界(始边：Qi 0 )所决定；对这些边界计算ti= Di / Qi；tU取1和各个ti值之中的最小值。 如果tL tU ，则线段完全落在裁剪窗口之外，被舍弃。 否则裁剪线段为tL,tU。,97,6. Liang-Barsky算法小结,一种特殊形式的Cyrus-Beck算法； Cohen-Sutherland与中点法在区域码测试阶段

43、能以位运算方式高效率地进行，因而当大多数线段能够简单的取舍时，效率较好； 梁友栋Barskey算法只能应用于矩形窗口的情形，通常其效率比前两者要高，这是因为运算仅到必要时才进行求交计算。 两者都可推广到三维空间。,98,7. 凹多边形窗口的裁剪,上述算法都假定裁剪窗口为凸多边形，对于凹多边形窗口，线段如何裁剪？ 如何判断凸、凹多边形？ 将凹多边形分割为凸多边形，利用已有算法进行裁剪。,99,矢量叉积定义如下： 2个互不平行的矢量，其叉积形成一个与2个矢量都垂直的新的矢量，它的方向符合右手判别法 | v1v2 |=|v1|*|v2|*Sin 如果v1平行于v2，则 v1v2=(0,0,0),7.

44、 凹多边形窗口的裁剪,100,如果各叉积全部为零，则多边形各边共线； 如果各叉积一部分为正，一部分为负，则多边形为凹多边形； 如果所有叉积全部大于零或等于零，则多边形为凸多边形。此时沿着边的正向，内法矢量指向其左侧； 如果所有叉积全部小于零或等于零，则多边形为凸多边形，此时沿着边的正向，内法矢量指向其右侧。,凸多边形,凹多边形,+,+,+,+,+,+,+,+,-,7. 凹多边形窗口的裁剪,凸多边形判定叉积法,101,第5章 二维光栅图形的处理,5.1 二维图形的裁剪 5.1.1 直线段的裁剪 5.1.2 多边形的裁剪 5.1.3 字符的裁剪 5.2 走样与反走样,102,多边形的裁剪可分解为一

45、条一条线段进行吗？ 分解为线段裁剪后多边形不再封闭，无法填充，需要用窗口边界的适当部分来关闭它。 一个凹多边形可能被裁剪成几个小的多边形，因而需要决定这些小多边形的边界。,5.1.2 多边形的裁剪,103,5.1.2 多边形的裁剪,1. Sutherland-Hodgman算法,104,通过对单一边的裁剪来实现多边形的裁剪。 分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。 流水线过程(左上右下)：前边的结果是后边的输入。 亦称逐边裁剪算法。,1. Sutherland-Hodgema算法原理,105,流水线：(左上右下)前边的结果是后边的输入。 算法的每一次输

46、出（包括中间结果）都是一个多边形的顶点表(逆时针排列)， 且所有顶点均位于相应窗口裁剪边的可见一侧。 由于多边形的每一条边需要与裁剪边分别进行比较，因此只需要讨论单条边和单个裁剪边之间可能的位置关系。,1. Sutherland-Hodgema算法原理,106,窗口边界所在直线将平面分为两部分：可见一侧、不可见一侧。 假设S,P为多边形的两个相邻顶点：S为该边的起点，P为该边的终点。则SP与裁剪边之间只有4种可能的关系。,1. Sutherland-Hodgema算法原理,107,由上可见，每一次将多边形的一条边与裁剪边或面比较后，输出一个或两个顶点，也可能无输出点： 如果SP边完全可见，则输

47、出P点，不必输出起点S，因为顶点是按顺序处理的，S是作为前一边的终点输出的； 如果SP边完全不可见，则无输出；,1. Sutherland-Hodgema算法原理,108,如果SP边部分可见，则SP边可能进入或离开裁剪边或面的可见一侧。 如果SP边离开裁剪边或面的可见一侧，则输出SP与裁剪边或面交点。 如果SP边进入裁剪边或面的可见一侧，则输出两点，一个为SP与裁剪边或面的交点，一个是P点。,1. Sutherland-Hodgema算法原理,109,对于多边形的第一个顶点，只需判断其可见性。如果可见，则输出且作为起点S；否则无输出，但还是要作为S保存，以便后续点处理。 对于最后一条边PnP1

48、，其处理方法是：标志第一顶点为F，这样最后一条边则为PnF，可与其他边作相同的处理。,1. Sutherland-Hodgema算法原理,110,while 对于每一个窗口边或面 do begin if P1在窗口边的可见一侧 then 输出P1 for i=1 到 n do begin if Pi在窗口边的可见一侧 then if Pi+1在窗口边的可见一侧 then 输出Pi+1 else 计算交点并输出交点 else if Pi不在可见一侧， Pi+1在可见一侧， then 计算交点并输出交点，同时输出Pi+1 endend end of algorithm,1. Sutherland-

49、Hodgema算法描述,111,实现方法： 设置二个表 输入顶点表：用于存放被裁剪多边形的顶点p1-pm。 输出顶点表：用于存放裁剪过程中及结果的顶点q1-qn。 顶点表中各顶点要求按一定顺序排列，一般采用逆时针方向。 相对于裁剪窗口的各条边界，逐边进行裁剪。 点的可见性判断 交点的计算,1. Sutherland-Hodgema算法示例,112,输入顶点表：p1p2p3 输出顶点表：空 左：q1p2p3q2（逆时针方向） 上：q1p2p3q2 右：q1p2p3q2 下：q3p3q2q4,1. Sutherland-Hodgema算法示例,113,对凸多边形应用本算法可以得到正确的结果，但是对

50、凹多边形的裁剪将如图所示显示出一条多余的直线。 这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表。 解决这个问题有多种方法 一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。 二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。,1. Sutherland-Hodgema算法小结,114,第5章 二维光栅图形的处理,5.1 二维图形的裁剪 5.1.1 直线段的裁剪 5.1.2 多边形的裁剪 5.1.3 字符的裁剪 5.2 几何变换 5.3 二维图形的显示流程 5.4 走样与反走样,115,Stroke,文本是由字符组成的。一般地，字符可分为两种：一种是矢量字符，即由若干个线段或笔画构成；一种是点阵字符，即由点阵来表示。所以文本的裁剪与多边形的裁剪相类似，它按裁剪的精度可分为笔画裁剪、字符裁剪、和字符串裁剪等三种类型。 笔画裁剪是指在显示文本时，把窗口以外的字符予以裁剪，并且对与窗口相交的字符，也把其在窗口以外的部分予以裁剪。若是矢量字符，可以按直线的裁剪方法来裁剪与窗口相交的字符。若是点阵字符，则可按点