图形学算法复习2016

2.1直线的生成2.1.2中点画线算法

消除DDA算法中的浮点运算（浮点数取整运算，不利于硬件实现；DDA算法，效率低）。

中点画线算法条件：同DDA算法斜率：直线段的隐式方程（(x0,y0)(x1,y1)两端点）

F(x,y)=ax+by+c=0

式中a=y0-y1,b=x1-x0,c=x0y1-x1y0。中点画线算法直线的正负划分性直线上方点：F(X，Y)＞0直线下方的点F(X，Y)＜0中点画线算法问题：判断距直线最近的下一个象素点构造判别式：di=F(M)=F(Xp+1,Yp+0.5)

由di＞0，＜0可判定下一个象素，PP2P1中点画线算法要判定再下一个象素，分两种情形考虑： 1）若di>0，取右下方象素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）若di≤0，取右上方象素P2，再下一个象素，由：di+1=F(Xp+2,Yp+1.5)=a(Xp+1)+b(Yp+0.5)+c+a+b=di+a+bdi的增量为a+bPP2P1中点画线算法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-2Δyd>0di+1=di+2a=di-2Δy(取下点)d≤0di+1=di+2(a+b)=di-2(Δy-Δx)（取上点）中点画线算法例：设第一象限直线OE，起点为(2，1)，终点坐标为(12，9)试用中点画线算法计算，并作出走步轨迹图。

初始决策参数的计算为:计算后继决策参数的增量为：

绘制初始点（x0,y0）=(2,1),并从决策参数中确定沿线路径的后继像素位置为：中点画线算法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）基本概念边的连贯性：某条边与当前扫描线相交，很可能与下一条扫描线也相交。扫描线的连贯性：当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或类似。区间连贯性：同一区间上的像素很可能取同一颜色属性。有效边表扫描线填充算法（1）基本概念边表（EdgeTableET）：用来存放多边形边的信息的表，包括除水平边以外的所有边。有效边（ActiveEdge）:与当前扫描线相交的多边形的边，也称为活性边。有效边表（AET）：将有效边与扫描线交点x坐标递增顺序存放在一个链表中，此链表就是有效边表。有效边表扫描线填充算法（2）有效边表的构造有效边表的每个结点：Ymax：所交边的最高扫描线的Y值。X：所交边在当前扫描线中的x值。△x：从当前扫描线到下条扫描线之间的x增量。next：指向下一节点。ymax

x|ymin△xnext有效边表扫描线填充算法（2）有效边表的构造△x：从当前扫描线到下条扫描线之间的x增量。设该边的直线方程为：ax+by+c=0，当前扫描线及下一条扫描线与边的交点分别为(xi,yi)、(xi+1,yi+1)，则：

axi+byi+c=0

axi+1+byi+1+c=0

由于yi+1=yi+1

所以

其中△x=-b/a=dx/dy为常数

xi+1,yi+1xi,yi有效边表扫描线填充算法为了方便有效边表的建立和更新，构造边表：（1）构造一个纵向链表，长度为多边形所占有的最大扫描线数。（2）按照边的下端点y坐标对非水平边进行分类的指针数组,下端点y坐标值等于i的边属于第i类。绘图窗口中有多少条扫描线，ET就分为多少类。（3）同一类中的边按x值（x值相等的，按△x值）递增的顺序排列。二维图形几何变换基本的几何变换有平移、旋转、缩放、对称和错切。二维变换的齐次坐标表示齐次坐标所谓齐次坐标就是将一个原本是n维的向量用一个n+1维向量来表示。如向量(x1,x2,…,xn)的齐次坐标表示为(hx1,hx2,…hxn,h),其中h是一个实数。显然一个向量的齐次表示是不唯一的，齐次坐标的h取不同的值都表示的是同一个点，比如齐次坐标[8,4,4]、[4,2,2]表示的都是二维点[2,1]。二维变换的齐次坐标表示齐次坐标

用P=[xy1]代表齐次坐标表示法中二维平面内一个未被变换的点，用3×3矩阵表示变换矩阵。二维变换的齐次坐标表示平移变换

令变换矩阵中，l=tx,m=ty，即l,m分别表示点(x,y)沿X，Y方向的平移量，则平移变换可以表示为：

二维变换的齐次坐标表示缩放变换在变换矩阵中，取a=sx,d=sy,它们分别表示P(x,y)沿X，Y方向相对于原点的比例变换系数。

二维变换的齐次坐标表示缩放变换

二维变换的齐次坐标表示缩放变换当sx=sy时，T可以写成：

二维变换的齐次坐标表示缩放变换当sx=sy时，T可以写成：

当S<1时，图形产生整体比例放大当S>1时，图形产生整体比例缩小当S=1时，图形大小不变二维变换的齐次坐标表示通用固定点缩放变换

前面公式是相对于坐标原点缩放功能，产生关于所选择的固定位置(xf,yf)缩放的变换顺序。二维变换的齐次坐标表示通用固定点缩放变换

1、平移对象使固定点与坐标原点重合；二维变换的齐次坐标表示通用固定点缩放变换

2、对于坐标原点缩放；二维变换的齐次坐标表示通用固定点缩放变换

3、反向平移将对象返回到原始位置；二维变换的齐次坐标表示旋转变换在变换矩阵中，令

二维变换的齐次坐标表示通用基准点的旋转变换利用平移-旋转-平移来实现绕任意选择的基准点(xr,yr)的旋转。

二维变换的齐次坐标表示通用基准点的旋转变换1、平移对象使基准点位置移动到坐标原点。

二维变换的齐次坐标表示通用基准点的旋转变换2、绕坐标原点旋转。

二维变换的齐次坐标表示通用基准点的旋转变换3、平移对象，使基准点回到其原始位置。

二维变换的齐次坐标表示对称变换对称于y轴变换矩阵中b=c=0,a=-1,d=1,s=1时：二维变换的齐次坐标表示对称变换对称于x轴变换矩阵中b=c=0,a=1,d=-1,s=1时：二维变换的齐次坐标表示对称变换对称于原点变换矩阵中b=c=0,a=-1,d=-1,s=1时：二维变换的齐次坐标表示对称变换对称于直线y=x变换矩阵中a=d=0,b=c=1,s=1时：二维变换的齐次坐标表示对称变换关于直线y=mx+b对称平移直线使其经过原点将直线旋转到坐标轴之一关于坐标轴对称逆旋转，平移错切变换错切是一种使对象形状发生变化的变换。经过错切对象好象是由已经相滑动的内部夹层组成。常用的错切有两种：改变x坐标值改变y坐标值错切变换相对于x轴的x方向错切,图形的y坐标不变，x坐标随初值

（x，y）及变换系数c作线性变化。变换矩阵为：错切变换相对于y轴的y方向错切,图形的x坐标不变，y坐标随初值

（x，y）及变换系数b作线性变化。变换矩阵为：二维变换的齐次坐标表示齐次坐标

变换矩阵中，各元素的取值不同，可以表示不同的变换：可以对图形进行缩放、旋转、对称、错切等变换;是对图形进行投影变换；[lm]是对图形作平移变换;[s]则是对图形整体进行缩放变换

二维变换的齐次坐标表示注意

变换合成时，矩阵相乘的顺序。先作用的变换放在连乘式的左端，后作用的变换放在连乘式的右端。对于两个基本变换M1，M2，由于矩阵乘法不满足交换律，通常M1•M2≠M2•M1，只有在下列特殊情况下，顺序才是可交换的。

二维变换的齐次坐标表示注意

M1M2平移变换缩放变换旋转变换缩放变换（Sx=Sy）平移变换缩放变换旋转变换旋转变换二维变换的齐次坐标表示练习：常用的几何变换有_________、_________、_________、_________等。

简述关于任意一条直线对称的变换矩阵的求解过程。写出关于直线-x+2y+3=0对称的变换矩阵。

三维图形的几何变换三维几何变换包括平移、旋转和缩放等变换。与二维图形变换一样，我们用齐次坐标技术来描述空间的各点坐标及各种变换。

三维图形的几何变换三维齐次坐标(x,y,z)点对应的齐次坐标为标准齐次坐标(x,y,z,1)右手坐标系

三维图形的几何变换三维空间中点P(x,y,z)，用齐次坐标表示应是[xyz1],描述三维空间中各种变换的变换矩阵T应是4×4形式。

三维图形的几何变换齐次坐标可以对图形进行缩放、旋转、对称、错切等变换;是对图形进行投影变换；[lmn]是对图形作平移变换;[s]则是对图形整体进行缩放变换

三维图形的几何变换平移参照二维的平移变换，我们很容易得到三维平移变换矩阵：三维图形的几何变换缩放令a=sx,e=sy,i=sz，则变换矩阵为：当sx,sy,sz大于1时，对象被放大；当sx,sy,sz小于1时，对象被缩小；三维图形的几何变换整体缩放当sx,sy,sz相等的时候，变换矩阵可写为：当s大于1时，对象被整体缩小；当s小于1时，对象被整体放大；三维图形的几何变换通用固定点的缩放相对于（xf，yf，zf）的缩放将平移到坐标原点处；进行相对于缩放变换；将固定点（xf，yf，zf）移回原来位置

三维图形的几何变换通用固定点的缩放

三维图形的几何变换通用固定点的缩放相对于（xf，yf，zf）的缩放将平移到坐标原点处；三维图形的几何变换通用固定点的缩放相对于（xf，yf，zf）的缩放进行相对于原点的缩放变换；三维图形的几何变换通用固定点的缩放相对于（xf，yf，zf）的缩放将固定点（xf，yf，zf）移回原来位置

三维图形的几何变换对称变换相对于x轴的对称变换：

x坐标不变，y,z坐标取反三维图形的几何变换对称变换相对于y轴的对称变换：

y坐标不变，x,z坐标取反三维图形的几何变换对称变换相对于z轴的对称变换：

z坐标不变，x,y坐标取反三维图形的几何变换对称变换相对于坐标原点的对称变换：

x,y，z坐标取反三维图形的几何变换对称变换相对于xy平面的对称变换：

x,y坐标不变，z坐标取反三维图形的几何变换对称变换相对于XZ平面的对称变换：

x,z坐标不变，y坐标取反xyz三维图形的几何变换对称变换相对于YZ平面的对称变换：

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

在右手坐标系，物体绕某坐标轴逆时针方向旋转为正三维图形的几何变换旋转变换绕z轴正方向旋转γ角：基准点在坐标轴上三维图形的几何变换旋转变换绕X轴正方向旋转α角：基准点在坐标轴上三维图形的几何变换旋转变换绕y轴正方向旋转α角：基准点在坐标轴上三维图形的几何变换绕任意轴旋转变换如果旋转所绕的轴不是坐标轴，而是一根任意轴，则变换过程变显得较复杂。对物体作平移和绕轴旋转变换，使得所绕之轴与某一标准坐标轴重合。绕该标准坐标轴作所需角度的旋转。通过逆变换使所绕之轴恢复到原来位置。三维图形的几何变换绕任意轴旋转变换设旋转所绕的任意轴为p1,p2两点所定义的矢量。旋转角度为。平移T(-x1,-y1,-z1)使p1点与原点重合

旋转Rx(α)使得轴p1p2落入平面xoz内旋转Ry(β)，使p1p2与z轴重合旋转Rz(θ)，执行绕p1p2轴的θ角度旋转；旋转Ry(－β)；旋转Rx(－α)；平移T(x1,y1,z1)。三维图形的几何变换绕任意轴旋转变换三维图形的几何变换绕任意轴旋转变换设旋转所绕的任意轴为p1(x1,y1,z1),p2(x2,y2,z2)两点所定义的矢量。旋转角度为。

T使p1点与原点重合三维图形的几何变换绕任意轴旋转变换