图形学算法复习

1、2.1 2.1 直线的生成直线的生成2.1.2 2.1.2 中点画线算法中点画线算法 消除DDA算法中的浮点运算（浮点数取整运算，不利于硬件实现； DDA算法，效率低）。 中点画线算法中点画线算法n条件：n同DDA算法n斜 率：n直线段的隐式方程（(x0,y0)(x1,y1)两端点）nF(x,y)=ax+by+c=0n 式中 a=y0-y1,b=x1-x0,c=x0y1-x1y0 。 1 , 0m中点画线算法中点画线算法直线的正负划分性直线上方点：F(X，Y)0直线下方的点F(X，Y)0中点画线算法中点画线算法问题：判断距直线最近的下一个象素点 构造判别式：di=F(M)=F(Xp+1,Yp+

2、0.5) 由di0，0可判定下一个象素，PP2P1中点画线算法中点画线算法要判定再下一个象素，分两种情形考虑：1）若di0，取右下方象素P1，再下一个象素判定，由： di= a(Xp+1)+b(Yp+0.5)+c di+1=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = di +a， di的增量是aPP2P1中点画线算法中点画线算法要判定再下一个象素，分两种情形考虑： 2）若di0，取右上方象素P2，再下一个象素，由：di+1=F(Xp+2,Yp+1.5)= a(Xp+1)+b(Yp+0.5)+c+a+b=di+a+b di的增量为a+bPP2P1中点画线算法中点画线

3、算法d的初始值d0=F(x0+1,y0+0.5) =a(x0+1)+b(y0+0.5)+c = F(x0,y0)+a+0.5b因(x0,y0)在直线上，F(x0，y0)=0,所以，d0=a+0.5b中点画线算法中点画线算法d的增量都是整数，只有初始值包含小数，可以用2d代替d, 2a改写成a+a。算法中只有整数变量，不含乘除法，可用硬件实现。中点画线算法中点画线算法a=y0-y1,b=x1-x0, y=y1-y0, x=x1-x0,d0=2(a+0.5b)=2a+b=x -2yd0 di+1= di+2a= di-2y (取下点) d0 di+1= di+2(a+b)= di-2(y- x)（

4、取上点）中点画线算法中点画线算法例：设第一象限直线OE，起点为(2，1)，终点坐标为(12，9)试用中点画线算法计算，并作出走步轨迹图。 初始决策参数的计算为: 计算后继决策参数的增量为： 绘制初始点（x0,y0）=(2,1),并从决策参数中确定沿线路径的后继像素位置为：620bad4b)(a2 ,162a中点画线算法中点画线算法kdk(xk+1,yk+1)kdk(xk+1,yk+1)01234-6-22-14-10（3，2）（4，3）（5，3）（6，4）（7，5）56789-6-22-14-10（8，6）（9，7）（10，7）（11，8）（12，9） 1)y(y 0)( 2ba2)y(y 0

5、)(d 2ai1ii1i1iiiiidddd中点画线算法中点画线算法有效边表扫描线填充算法有效边表扫描线填充算法（1 1）基本概念）基本概念边的连贯性边的连贯性：某条边与当前扫描线相交，：某条边与当前扫描线相交，很可能与下一条扫描线也相交。很可能与下一条扫描线也相交。扫描线的连贯性：扫描线的连贯性：当前扫描线与各边的交当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺点顺序与下一条扫描线与各边的交点顺序很可能相同或类似。序很可能相同或类似。区间连贯性区间连贯性：同一区间上的像素很可能取：同一区间上的像素很可能取同一颜色属性。同一颜色属性。有效边表扫描线填充算法有效边表扫描线填充算法（1 1

6、）基本概念）基本概念边表（边表（Edge Table ETEdge Table ET）：用来存放多边：用来存放多边形边的信息的表，包括除水平边以外的形边的信息的表，包括除水平边以外的所有边。所有边。有效边（有效边（Active EdgeActive Edge）: :与当前扫描线相与当前扫描线相交的多边形的边，也称为活性边。交的多边形的边，也称为活性边。有效边表（有效边表（AETAET）：将有效边与扫描线交：将有效边与扫描线交点点x x坐标递增顺序存放在一个链表中，坐标递增顺序存放在一个链表中，此链表就是有效边表。此链表就是有效边表。有效边表扫描线填充算法有效边表扫描线填充算法（2 2）有效边表

7、的构造）有效边表的构造有效边表的每个结点：有效边表的每个结点：Ymax：所交边的最高扫描线的：所交边的最高扫描线的Y值。值。X：所交边在当前扫描线中的：所交边在当前扫描线中的x值。值。x：从当前扫描线到下条扫描线之间的：从当前扫描线到下条扫描线之间的x增量。增量。 next：指向下一节点。：指向下一节点。ymax x|ymin x next有效边表扫描线填充算法有效边表扫描线填充算法（2 2）有效边表的构造）有效边表的构造x：从当前扫描线到下条扫描线之间的：从当前扫描线到下条扫描线之间的x增量。增量。设该边的直线方程为：设该边的直线方程为：ax+by+c=ax+by+c=0 0，当前扫描线及下

8、一当前扫描线及下一条扫描线与边的交点分别为条扫描线与边的交点分别为( (x xi i, ,y yi i) )、( (x xi+i+1 1, ,y yi+i+1 1) )，则：则： axaxi i+by+byi i+c=+c=0 0 axaxi+i+1 1+by+byi+i+1 1+c=0+c=0 由于由于y yi+i+1 1= =y yi i+1+1 所以所以 其中其中x=-b/a =dx/dyx=-b/a =dx/dy为常数为常数 )(111cybxiaiabiiaixcybx)(111xi+1,yi+1xi,yi有效边表扫描线填充算法有效边表扫描线填充算法为了方便有效边表的建立和更新，构造

9、边为了方便有效边表的建立和更新，构造边表：表：（1 1）构造一个纵向链表，长度为多边形）构造一个纵向链表，长度为多边形所占有的最大扫描线数。所占有的最大扫描线数。（2 2）按照边的下端点）按照边的下端点y y坐标对非水平边进坐标对非水平边进行分类的指针数组行分类的指针数组, ,下端点下端点y y坐标值等于坐标值等于i i的边属于第的边属于第i i类。绘图窗口中有多少条类。绘图窗口中有多少条扫描线，扫描线，ETET就分为多少类。就分为多少类。（3 3）同一类中的边按）同一类中的边按x x值（值（x x值相等的，值相等的，按按x x值）递增的顺序排列。值）递增的顺序排列。二维图形几何变换二维图形几

10、何变换 基本的几何变换有基本的几何变换有平移平移、旋转旋转、缩放缩放、对称对称和和错切错切。二维变换的齐次坐标表示二维变换的齐次坐标表示齐次坐标齐次坐标 所谓所谓齐次坐标齐次坐标就是将一个原本是就是将一个原本是n n维的向维的向量用一个量用一个n n+1+1维向量来表示。如向量维向量来表示。如向量( (x1,x2,x1,x2,xn),xn)的齐次坐标表示为的齐次坐标表示为( (hx1,hx2,hx1,hx2,hxn,h),hxn,h),其中其中h h是一个实数。显然是一个实数。显然一个向量的齐次表示是不唯一的，齐次坐标一个向量的齐次表示是不唯一的，齐次坐标的的h h取不同的值都表示的是同一个点

11、，比如齐取不同的值都表示的是同一个点，比如齐次坐标次坐标8,4,48,4,4、4,2,24,2,2表示的都是二维点表示的都是二维点2,12,1。二维变换的齐次坐标表示二维变换的齐次坐标表示齐次坐标齐次坐标 用用P=x y 1P=x y 1代表齐次坐标表示代表齐次坐标表示法中二维平面内一个未被变换的点，法中二维平面内一个未被变换的点，用用3 33 3矩阵表示变换矩阵。矩阵表示变换矩阵。smlqdcpbaT二维变换的齐次坐标表示二维变换的齐次坐标表示平移变换平移变换 令变换矩阵中，令变换矩阵中，l=tx,m=tyl=tx,m=ty，即即l,ml,m分别表示点分别表示点( (x,y)x,y)沿沿X

12、X，Y Y方向方向的平移量，则平移变换可以表示的平移量，则平移变换可以表示为：为： 1 10100011yxyxtytxttyxHYX二维变换的齐次坐标表示二维变换的齐次坐标表示缩放变换缩放变换 在变换矩阵中，取在变换矩阵中，取a=sx,d=sy,a=sx,d=sy,它们分别表示它们分别表示P(x,y)P(x,y)沿沿X X，Y Y方向相对于原点的比例方向相对于原点的比例变换系数。变换系数。 二维变换的齐次坐标表示二维变换的齐次坐标表示缩放变换缩放变换 11000000 11000000ysxsssyxHYXssTTPPyxyxyx二维变换的齐次坐标表示二维变换的齐次坐标表示缩放变换缩放变换

13、当当sx=sysx=sy时，时，T T可以写成：可以写成： /1/100010001 1/100010001xxxsyxsyxHYXsT二维变换的齐次坐标表示二维变换的齐次坐标表示缩放变换缩放变换 当当sx=sysx=sy时，时，T T可以写成：可以写成： xxsSsT/1/100010001当S1时，图形产生整体比例缩小当S=1时，图形大小不变二维变换的齐次坐标表示二维变换的齐次坐标表示通用固定点缩放变换通用固定点缩放变换 前面公式是相前面公式是相对于坐标原点缩对于坐标原点缩放功能，产生关放功能，产生关于所选择的固定于所选择的固定位置位置( (xf,yf)xf,yf)缩放缩放的变换顺序。的变

14、换顺序。二维变换的齐次坐标表示二维变换的齐次坐标表示通用固定点缩放变通用固定点缩放变换换 1 1、平移对、平移对象使固定点与象使固定点与坐标原点重合；坐标原点重合；1010001ffyxPP二维变换的齐次坐标表示二维变换的齐次坐标表示通用固定点缩放变通用固定点缩放变换换 2 2、对于坐、对于坐标原点缩放标原点缩放；1000000yxssPP二维变换的齐次坐标表示二维变换的齐次坐标表示通用固定点缩放变通用固定点缩放变换换 3 3、反向平、反向平移将对象返回移将对象返回到原始位置到原始位置；1010001 ffyxPP二维变换的齐次坐标表示二维变换的齐次坐标表示旋转变换旋转变换 在变换矩阵中，令在

15、变换矩阵中，令 TPPT1000cossin0sincos二维变换的齐次坐标表示二维变换的齐次坐标表示通用基准点的旋转通用基准点的旋转变换变换 利用平移利用平移- -旋转旋转- -平移来实现绕任平移来实现绕任意选择的基准点意选择的基准点( (xr,yr)xr,yr)的旋转。的旋转。 二维变换的齐次坐标表示二维变换的齐次坐标表示通用基准点的旋通用基准点的旋转变换转变换 1 1、平移对象、平移对象使基准点位置使基准点位置移动到坐标原移动到坐标原点。点。 1010001rryxPP二维变换的齐次坐标表示二维变换的齐次坐标表示通用基准点的旋通用基准点的旋转变换转变换 2 2、绕坐标原、绕坐标原点旋转点

16、旋转。 1000cossin0sincosPP二维变换的齐次坐标表示二维变换的齐次坐标表示通用基准点的旋通用基准点的旋转变换转变换 3 3、平移对象，、平移对象，使基准点回到使基准点回到其原始位置其原始位置。 1010001 rryxPP二维变换的齐次坐标表示二维变换的齐次坐标表示对称变换对称变换对称于对称于y y轴轴 变换矩阵中变换矩阵中b=c=0,a=-1,d=1,s=1b=c=0,a=-1,d=1,s=1时：时：1 100010001 1 100010001yxyxPT二维变换的齐次坐标表示二维变换的齐次坐标表示对称变换对称变换对称于对称于x x轴轴 变换矩阵中变换矩阵中b=c=0,a=

17、1,d=-1,s=1b=c=0,a=1,d=-1,s=1时：时：1 100010001 1 100010001yxyxPT二维变换的齐次坐标表示二维变换的齐次坐标表示对称变换对称变换对称于原点对称于原点 变换矩阵中变换矩阵中b=c=0,a=-1,d=-1,s=1b=c=0,a=-1,d=-1,s=1时：时：1 100010001 1 1000100011000cossin0sincosyxyxPT二维变换的齐次坐标表示二维变换的齐次坐标表示对称变换对称变换对称于直线对称于直线y=xy=x 变换矩阵中变换矩阵中a=d=0,b=c=1,s=1a=d=0,b=c=1,s=1时：时：1 1000010

18、10 1 100001010 xyyxPT二维变换的齐次坐标表示二维变换的齐次坐标表示对称变换对称变换关于直线关于直线y=mx+by=mx+b对称对称v平移直线使其经过原点平移直线使其经过原点v将直线旋转到坐标轴之一将直线旋转到坐标轴之一v关于坐标轴对称关于坐标轴对称v逆旋转，平移逆旋转，平移错切变换错切变换错切是一种使对象形状发生变化的变错切是一种使对象形状发生变化的变换。经过错切对象好象是由已经相换。经过错切对象好象是由已经相滑动的内部夹层组成。常用的错切滑动的内部夹层组成。常用的错切有两种：有两种：v改变改变x x坐标值坐标值v改变改变y y坐标值坐标值错切变换错切变换相对于相对于x x

19、轴的轴的x x方向错切方向错切, ,图形的图形的y y坐标不变，坐标不变，x x坐坐标随初值标随初值 （x x，y y）及变换系数及变换系数c c作线性变作线性变化。化。变换矩阵为变换矩阵为：110001001 1 10001001ycyxcyxPcT错切变换错切变换相对于相对于y y轴的轴的y y方向错切方向错切, ,图形的图形的x x坐标不变，坐标不变，y y坐坐标随初值标随初值 （x x，y y）及变换系数及变换系数b b作线性变作线性变化。化。变换矩阵为变换矩阵为：110001001 1 10001001bxyxbyxPbT二维变换的齐次坐标表示二维变换的齐次坐标表示齐次坐标齐次坐标

20、变换矩阵中，各元素的取值不同，可以变换矩阵中，各元素的取值不同，可以表示不同的变换：表示不同的变换： 可以对图形进行缩放、旋转、对称、错切等可以对图形进行缩放、旋转、对称、错切等变换变换; ; 是对图形进行投影变换；是对图形进行投影变换； l ml m是对图形作平移变换是对图形作平移变换; ;ss则是对图形整体进行缩放变换则是对图形整体进行缩放变换 dcbaqp二维变换的齐次坐标表示二维变换的齐次坐标表示注意注意 变换合成时，矩阵相乘的顺序。先作用变换合成时，矩阵相乘的顺序。先作用的变换放在连乘式的左端，后作用的变换放的变换放在连乘式的左端，后作用的变换放在连乘式的右端。对于两个基本变换在连乘

21、式的右端。对于两个基本变换M1M1，M2M2，由于矩阵乘法不满足交换律，通常由于矩阵乘法不满足交换律，通常M1M1M2 M2 M2M2M1M1，只有在下列特殊情况下，顺序才是只有在下列特殊情况下，顺序才是可交换的。可交换的。 二维变换的齐次坐标表示二维变换的齐次坐标表示注意注意 M1M2平移变换缩放变换旋转变换缩放变换（Sx=Sy）平移变换缩放变换旋转变换旋转变换二维变换的齐次坐标表示二维变换的齐次坐标表示练习：练习：n常用的几何变换有常用的几何变换有_、_、_、_等。等。 n简述关于任意一条直线对称的变换矩阵的求解过程。简述关于任意一条直线对称的变换矩阵的求解过程。n写出关于直线写出关于直线

22、-x+2y+3=0对称的变换矩阵。对称的变换矩阵。 三维图形的几何变换三维图形的几何变换 三维几何变换包括平移、旋三维几何变换包括平移、旋转和缩放等变换。与二维图形变转和缩放等变换。与二维图形变换一样，我们用齐次坐标技术来换一样，我们用齐次坐标技术来描述空间的各点坐标及各种变换。描述空间的各点坐标及各种变换。 三维图形的几何变换三维图形的几何变换三维齐次坐标三维齐次坐标n(x,y,z)点对应的齐次坐标为点对应的齐次坐标为n标准齐次坐标标准齐次坐标(x,y,z,1)右手坐标系右手坐标系 ),(hzyxhhh0,hhzzhyyhxxhhh三维图形的几何变换三维图形的几何变换 三维空间中点三维空间中

23、点P(x,y,z)P(x,y,z)，用齐次坐标表示应是用齐次坐标表示应是 x y z x y z 1,1,描述三维空间中各种变换描述三维空间中各种变换的变换矩阵的变换矩阵T T应是应是4 44 4形式形式。 三维图形的几何变换三维图形的几何变换齐次坐标齐次坐标 可以对图形进行缩放、旋转、对称、错切等可以对图形进行缩放、旋转、对称、错切等变换变换; ; 是对图形进行投影变换；是对图形进行投影变换； l m nl m n是对图形作平移变换是对图形作平移变换; ;ss则是对图形整体进行缩放变换则是对图形整体进行缩放变换 ihgfedcbarqp三维图形的几何变换三维图形的几何变换平移平移参照二维的平

24、移变换，我们很容易得到三参照二维的平移变换，我们很容易得到三维平移变换矩阵维平移变换矩阵：1010000100001zyxttt三维图形的几何变换三维图形的几何变换缩放缩放令令a=sx,e=sy,i=sza=sx,e=sy,i=sz，则变换矩阵为：则变换矩阵为：当当sx,sy,szsx,sy,sz大于大于1 1时，对象被放大；时，对象被放大；当当sx,sy,szsx,sy,sz小于小于1 1时，对象被缩小；时，对象被缩小；1000000000000zyxsss三维图形的几何变换三维图形的几何变换整体缩放整体缩放当当sx,sy,szsx,sy,sz相等的时候，变换矩阵可写为：相等的时候，变换矩阵

25、可写为：当当s s大于大于1 1时，对象被整体缩小时，对象被整体缩小；当当s s小于小于1 1时，对象被整体放大；时，对象被整体放大；s000010000100001三维图形的几何变换三维图形的几何变换通用固定点的缩放通用固定点的缩放相对于（相对于（x xf f，y yf f，z zf f）的缩放的缩放v将平移到坐标原点处；将平移到坐标原点处；v进行相对于缩放变换；进行相对于缩放变换；v将固定点（将固定点（x xf f，y yf f，z zf f）移回原来位置移回原来位置三维图形的几何变换三维图形的几何变换通用固定点的缩放通用固定点的缩放三维图形的几何变换三维图形的几何变换通用固定点的缩放通用

26、固定点的缩放相对于（相对于（x xf f，y yf f，z zf f）的缩放的缩放v将平移到坐标原点将平移到坐标原点处；处；10100001000011fffzyxT三维图形的几何变换三维图形的几何变换通用固定点的缩放通用固定点的缩放相对于（相对于（x xf f，y yf f，z zf f）的缩放的缩放v进行相对于原点的进行相对于原点的缩放变换；缩放变换；10000000000002zyxsssT三维图形的几何变换三维图形的几何变换通用固定点的缩放通用固定点的缩放相对于（相对于（x xf f，y yf f，z zf f）的缩放的缩放v将固定点（将固定点（x xf f，y yf f，z zf f

27、）移回原来位置移回原来位置10100001000013fffzyxT三维图形的几何变换三维图形的几何变换对称变换对称变换相对于相对于x x轴的对称变换：轴的对称变换：x x坐标不变，坐标不变，y,zy,z坐标取反坐标取反1000010000100001T11000010000100001 1zyxzyxTPP三维图形的几何变换三维图形的几何变换对称变换对称变换相对于相对于y y轴的对称变换：轴的对称变换：y y坐标不变，坐标不变，x,zx,z坐标取反坐标取反1000010000100001T11000010000100001 1zyxzyxTPP三维图形的几何变换三维图形的几何变换对称变换对称

28、变换相对于相对于z z轴的对称变换：轴的对称变换：z z坐标不变，坐标不变，x,yx,y坐标取反坐标取反1000010000100001T11000010000100001 1zyxzyxTPP三维图形的几何变换三维图形的几何变换对称变换对称变换相对于坐标原点的对称变换：相对于坐标原点的对称变换：x,yx,y，z z坐标取反坐标取反1000010000100001T11000010000100001 1zyxzyxTPP三维图形的几何变换三维图形的几何变换对称变换对称变换相对于相对于xyxy平面的对称变换：平面的对称变换：x,yx,y坐标不变，坐标不变，z z坐标取反坐标取反100001000

29、0100001T11000010000100001 1zyxzyxTPP三维图形的几何变换三维图形的几何变换对称变换对称变换相对于相对于XZXZ平面的对称变换：平面的对称变换：x,zx,z坐标不变，坐标不变，y y坐标取反坐标取反1000010000100001T11000010000100001 1zyxzyxTPPxyz三维图形的几何变换三维图形的几何变换对称变换对称变换相对于相对于YZYZ平面的对称变换：平面的对称变换：y,zy,z坐标不变，坐标不变，x x坐标取反坐标取反1000010000100001T11000010000100001 1zyxzyxTPPxyz三维图形的几何变换三

30、维图形的几何变换对称变换对称变换相对于其它平面的对称变换：相对于其它平面的对称变换：v将此平面平移使其通过原点将此平面平移使其通过原点v将此平面旋转成与某一坐标面重合将此平面旋转成与某一坐标面重合v进行某坐标面的对称变换进行某坐标面的对称变换v逆旋转，逆平移逆旋转，逆平移三维图形的几何变换三维图形的几何变换旋转变换旋转变换决定旋转角度正负号的因素：决定旋转角度正负号的因素：v采用的坐标系是右手系还是左手系采用的坐标系是右手系还是左手系v旋转对象是形体还是坐标系；旋转对象是形体还是坐标系；v顺时针还是逆时针旋转；顺时针还是逆时针旋转； 在在右手右手坐标系坐标系，物体物体绕某坐标轴绕某坐标轴逆时针

31、逆时针方向旋转为方向旋转为正正三维图形的几何变换三维图形的几何变换旋转变换旋转变换绕绕z z轴正方向旋转轴正方向旋转角：角：1000010000cossin00sincos基准点在坐标轴上基准点在坐标轴上三维图形的几何变换三维图形的几何变换旋转变换旋转变换绕绕X X轴正方向旋转轴正方向旋转角：角：10000cossin00sincos00001基准点在坐标轴上基准点在坐标轴上三维图形的几何变换三维图形的几何变换旋转变换旋转变换绕绕y y轴正方向旋转轴正方向旋转角：角：10000cos0sin00100sin0cos基准点在坐标轴上基准点在坐标轴上三维图形的几何变换三维图形的几何变换绕任意轴旋转

32、变换绕任意轴旋转变换如果旋转所绕的轴不是坐标轴，而是一根如果旋转所绕的轴不是坐标轴，而是一根任意轴，则变换过程变显得较复杂。任意轴，则变换过程变显得较复杂。v对物体作平移和绕轴旋转变换，使得所对物体作平移和绕轴旋转变换，使得所绕之轴与某一标准坐标轴重合。绕之轴与某一标准坐标轴重合。v绕该标准坐标轴作所需角度的旋转。绕该标准坐标轴作所需角度的旋转。v通过逆变换使所绕之轴恢复到原来位置。通过逆变换使所绕之轴恢复到原来位置。三维图形的几何变换三维图形的几何变换绕任意轴旋转变换绕任意轴旋转变换设旋转所绕的任意轴为设旋转所绕的任意轴为p1, p2两点所定义的矢两点所定义的矢量。旋转角度为量。旋转角度为 。 平移平移T(-x1 1,-y,-y1 1,-z,-z1 1) )使使p1 1点与原点重合点与原点重合 旋转旋转Rx x( ()使得轴使得轴p1p2落入平面落入平面xoz内内旋转旋转Ry y( ()，使使p1p2与与z轴重合轴重合旋转旋转Rz z( ()，执行绕执行绕p1p2轴的轴的角度旋转角度旋转；旋转旋转Ry y( () ；旋转旋转Rx x( () ；平移平移T(x1 1,y,y1 1,z,z1 1) ) 。三维图形的几何变换三维图形的几何变换绕任意轴旋转变换绕任意轴旋转变换三维图形的几何变换三维图形的几何变换绕任意轴旋转变换绕任意轴旋转变换设旋转所绕的任意轴设旋转所绕的任意