圖形學(xué)算法復(fù)習(xí)2016

2.1直線的生成2.1.2中點畫線算法

消除DDA算法中的浮點運算（浮點數(shù)取整運算，不利于硬件實現(xiàn)；DDA算法，效率低）。

中點畫線算法條件：同DDA算法斜率：直線段的隱式方程（(x0,y0)(x1,y1)兩端點）

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

式中a=y0-y1,b=x1-x0,c=x0y1-x1y0。中點畫線算法直線的正負(fù)劃分性直線上方點：F(X，Y)＞0直線下方的點F(X，Y)＜0中點畫線算法問題：判斷距直線最近的下一個象素點構(gòu)造判別式：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(xiàn)(x0，y0)=0,所以，d0=a+0.5b中點畫線算法d的增量都是整數(shù)，只有初始值包含小數(shù)，可以用2d代替d,2a改寫成a+a。算法中只有整數(shù)變量，不含乘除法，可用硬件實現(xiàn)。中點畫線算法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)（取上點）中點畫線算法例：設(shè)第一象限直線OE，起點為(2，1)，終點坐標(biāo)為(12，9)試用中點畫線算法計算，并作出走步軌跡圖。

初始決策參數(shù)的計算為:計算后繼決策參數(shù)的增量為：

繪制初始點（x0,y0）=(2,1),并從決策參數(shù)中確定沿線路徑的后繼像素位置為：中點畫線算法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）基本概念邊的連貫性：某條邊與當(dāng)前掃描線相交，很可能與下一條掃描線也相交。掃描線的連貫性：當(dāng)前掃描線與各邊的交點順序與下一條掃描線與各邊的交點順序很可能相同或類似。區(qū)間連貫性：同一區(qū)間上的像素很可能取同一顏色屬性。有效邊表掃描線填充算法（1）基本概念邊表（EdgeTableET）：用來存放多邊形邊的信息的表，包括除水平邊以外的所有邊。有效邊（ActiveEdge）:與當(dāng)前掃描線相交的多邊形的邊，也稱為活性邊。有效邊表（AET）：將有效邊與掃描線交點x坐標(biāo)遞增順序存放在一個鏈表中，此鏈表就是有效邊表。有效邊表掃描線填充算法（2）有效邊表的構(gòu)造有效邊表的每個結(jié)點：Ymax：所交邊的最高掃描線的Y值。X：所交邊在當(dāng)前掃描線中的x值。△x：從當(dāng)前掃描線到下條掃描線之間的x增量。next：指向下一節(jié)點。ymax

x|ymin△xnext有效邊表掃描線填充算法（2）有效邊表的構(gòu)造△x：從當(dāng)前掃描線到下條掃描線之間的x增量。設(shè)該邊的直線方程為：ax+by+c=0，當(dāng)前掃描線及下一條掃描線與邊的交點分別為(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為常數(shù)

xi+1,yi+1xi,yi有效邊表掃描線填充算法為了方便有效邊表的建立和更新，構(gòu)造邊表：（1）構(gòu)造一個縱向鏈表，長度為多邊形所占有的最大掃描線數(shù)。（2）按照邊的下端點y坐標(biāo)對非水平邊進(jìn)行分類的指針數(shù)組,下端點y坐標(biāo)值等于i的邊屬于第i類。繪圖窗口中有多少條掃描線，ET就分為多少類。（3）同一類中的邊按x值（x值相等的，按△x值）遞增的順序排列。二維圖形幾何變換基本的幾何變換有平移、旋轉(zhuǎn)、縮放、對稱和錯切。二維變換的齊次坐標(biāo)表示齊次坐標(biāo)所謂齊次坐標(biāo)就是將一個原本是n維的向量用一個n+1維向量來表示。如向量(x1,x2,…,xn)的齊次坐標(biāo)表示為(hx1,hx2,…h(huán)xn,h),其中h是一個實數(shù)。顯然一個向量的齊次表示是不唯一的，齊次坐標(biāo)的h取不同的值都表示的是同一個點，比如齊次坐標(biāo)[8,4,4]、[4,2,2]表示的都是二維點[2,1]。二維變換的齊次坐標(biāo)表示齊次坐標(biāo)

用P=[xy1]代表齊次坐標(biāo)表示法中二維平面內(nèi)一個未被變換的點，用3×3矩陣表示變換矩陣。二維變換的齊次坐標(biāo)表示平移變換

令變換矩陣中，l=tx,m=ty，即l,m分別表示點(x,y)沿X，Y方向的平移量，則平移變換可以表示為：

二維變換的齊次坐標(biāo)表示縮放變換在變換矩陣中，取a=sx,d=sy,它們分別表示P(x,y)沿X，Y方向相對于原點的比例變換系數(shù)。

二維變換的齊次坐標(biāo)表示縮放變換

二維變換的齊次坐標(biāo)表示縮放變換當(dāng)sx=sy時，T可以寫成：

二維變換的齊次坐標(biāo)表示縮放變換當(dāng)sx=sy時，T可以寫成：

當(dāng)S<1時，圖形產(chǎn)生整體比例放大當(dāng)S>1時，圖形產(chǎn)生整體比例縮小當(dāng)S=1時，圖形大小不變二維變換的齊次坐標(biāo)表示通用固定點縮放變換

前面公式是相對于坐標(biāo)原點縮放功能，產(chǎn)生關(guān)于所選擇的固定位置(xf,yf)縮放的變換順序。二維變換的齊次坐標(biāo)表示通用固定點縮放變換

1、平移對象使固定點與坐標(biāo)原點重合；二維變換的齊次坐標(biāo)表示通用固定點縮放變換

2、對于坐標(biāo)原點縮放；二維變換的齊次坐標(biāo)表示通用固定點縮放變換

3、反向平移將對象返回到原始位置；二維變換的齊次坐標(biāo)表示旋轉(zhuǎn)變換在變換矩陣中，令

二維變換的齊次坐標(biāo)表示通用基準(zhǔn)點的旋轉(zhuǎn)變換利用平移-旋轉(zhuǎn)-平移來實現(xiàn)繞任意選擇的基準(zhǔn)點(xr,yr)的旋轉(zhuǎn)。

二維變換的齊次坐標(biāo)表示通用基準(zhǔn)點的旋轉(zhuǎn)變換1、平移對象使基準(zhǔn)點位置移動到坐標(biāo)原點。

二維變換的齊次坐標(biāo)表示通用基準(zhǔn)點的旋轉(zhuǎn)變換2、繞坐標(biāo)原點旋轉(zhuǎn)。

二維變換的齊次坐標(biāo)表示通用基準(zhǔn)點的旋轉(zhuǎn)變換3、平移對象，使基準(zhǔn)點回到其原始位置。

二維變換的齊次坐標(biāo)表示對稱變換對稱于y軸變換矩陣中b=c=0,a=-1,d=1,s=1時：二維變換的齊次坐標(biāo)表示對稱變換對稱于x軸變換矩陣中b=c=0,a=1,d=-1,s=1時：二維變換的齊次坐標(biāo)表示對稱變換對稱于原點變換矩陣中b=c=0,a=-1,d=-1,s=1時：二維變換的齊次坐標(biāo)表示對稱變換對稱于直線y=x變換矩陣中a=d=0,b=c=1,s=1時：二維變換的齊次坐標(biāo)表示對稱變換關(guān)于直線y=mx+b對稱平移直線使其經(jīng)過原點將直線旋轉(zhuǎn)到坐標(biāo)軸之一關(guān)于坐標(biāo)軸對稱逆旋轉(zhuǎn)，平移錯切變換錯切是一種使對象形狀發(fā)生變化的變換。經(jīng)過錯切對象好象是由已經(jīng)相滑動的內(nèi)部夾層組成。常用的錯切有兩種：改變x坐標(biāo)值改變y坐標(biāo)值錯切變換相對于x軸的x方向錯切,圖形的y坐標(biāo)不變，x坐標(biāo)隨初值

（x，y）及變換系數(shù)c作線性變化。變換矩陣為：錯切變換相對于y軸的y方向錯切,圖形的x坐標(biāo)不變，y坐標(biāo)隨初值

（x，y）及變換系數(shù)b作線性變化。變換矩陣為：二維變換的齊次坐標(biāo)表示齊次坐標(biāo)

變換矩陣中，各元素的取值不同，可以表示不同的變換：可以對圖形進(jìn)行縮放、旋轉(zhuǎn)、對稱、錯切等變換;是對圖形進(jìn)行投影變換；[lm]是對圖形作平移變換;[s]則是對圖形整體進(jìn)行縮放變換

二維變換的齊次坐標(biāo)表示注意

變換合成時，矩陣相乘的順序。先作用的變換放在連乘式的左端，后作用的變換放在連乘式的右端。對于兩個基本變換M1，M2，由于矩陣乘法不滿足交換律，通常M1?M2≠M2?M1，只有在下列特殊情況下，順序才是可交換的。

二維變換的齊次坐標(biāo)表示注意

M1M2平移變換縮放變換旋轉(zhuǎn)變換縮放變換（Sx=Sy）平移變換縮放變換旋轉(zhuǎn)變換旋轉(zhuǎn)變換二維變換的齊次坐標(biāo)表示練習(xí)：常用的幾何變換有_________、_________、_________、_________等。

簡述關(guān)于任意一條直線對稱的變換矩陣的求解過程。寫出關(guān)于直線-x+2y+3=0對稱的變換矩陣。

三維圖形的幾何變換三維幾何變換包括平移、旋轉(zhuǎn)和縮放等變換。與二維圖形變換一樣，我們用齊次坐標(biāo)技術(shù)來描述空間的各點坐標(biāo)及各種變換。

三維圖形的幾何變換三維齊次坐標(biāo)(x,y,z)點對應(yīng)的齊次坐標(biāo)為標(biāo)準(zhǔn)齊次坐標(biāo)(x,y,z,1)右手坐標(biāo)系

三維圖形的幾何變換三維空間中點P(x,y,z)，用齊次坐標(biāo)表示應(yīng)是[xyz1],描述三維空間中各種變換的變換矩陣T應(yīng)是4×4形式。

三維圖形的幾何變換齊次坐標(biāo)可以對圖形進(jìn)行縮放、旋轉(zhuǎn)、對稱、錯切等變換;是對圖形進(jìn)行投影變換；[lmn]是對圖形作平移變換;[s]則是對圖形整體進(jìn)行縮放變換

三維圖形的幾何變換平移參照二維的平移變換，我們很容易得到三維平移變換矩陣：三維圖形的幾何變換縮放令a=sx,e=sy,i=sz，則變換矩陣為：當(dāng)sx,sy,sz大于1時，對象被放大；當(dāng)sx,sy,sz小于1時，對象被縮??；三維圖形的幾何變換整體縮放當(dāng)sx,sy,sz相等的時候，變換矩陣可寫為：當(dāng)s大于1時，對象被整體縮??；當(dāng)s小于1時，對象被整體放大；三維圖形的幾何變換通用固定點的縮放相對于（xf，yf，zf）的縮放將平移到坐標(biāo)原點處；進(jìn)行相對于縮放變換；將固定點（xf，yf，zf）移回原來位置

三維圖形的幾何變換通用固定點的縮放

三維圖形的幾何變換通用固定點的縮放相對于（xf，yf，zf）的縮放將平移到坐標(biāo)原點處；三維圖形的幾何變換通用固定點的縮放相對于（xf，yf，zf）的縮放進(jìn)行相對于原點的縮放變換；三維圖形的幾何變換通用固定點的縮放相對于（xf，yf，zf）的縮放將固定點（xf，yf，zf）移回原來位置

三維圖形的幾何變換對稱變換相對于x軸的對稱變換：

x坐標(biāo)不變，y,z坐標(biāo)取反三維圖形的幾何變換對稱變換相對于y軸的對稱變換：

y坐標(biāo)不變，x,z坐標(biāo)取反三維圖形的幾何變換對稱變換相對于z軸的對稱變換：

z坐標(biāo)不變，x,y坐標(biāo)取反三維圖形的幾何變換對稱變換相對于坐標(biāo)原點的對稱變換：

x,y，z坐標(biāo)取反三維圖形的幾何變換對稱變換相對于xy平面的對稱變換：

x,y坐標(biāo)不變，z坐標(biāo)取反三維圖形的幾何變換對稱變換相對于XZ平面的對稱變換：

x,z坐標(biāo)不變，y坐標(biāo)取反xyz三維圖形的幾何變換對稱變換相對于YZ平面的對稱變換：

y,z坐標(biāo)不變，x坐標(biāo)取反xyz三維圖形的幾何變換對稱變換相對于其它平面的對稱變換：將此平面平移使其通過原點將此平面旋轉(zhuǎn)成與某一坐標(biāo)面重合進(jìn)行某坐標(biāo)面的對稱變換逆旋轉(zhuǎn)，逆平移三維圖形的幾何變換旋轉(zhuǎn)變換決定旋轉(zhuǎn)角度正負(fù)號的因素：采用的坐標(biāo)系是右手系還是左手系旋轉(zhuǎn)對象是形體還是坐標(biāo)系；順時針還是逆時針旋轉(zhuǎn)；

在右手坐標(biāo)系，物體繞某坐標(biāo)軸逆時針方向旋轉(zhuǎn)為正三維圖形的幾何變換旋轉(zhuǎn)變換繞z軸正方向旋轉(zhuǎn)γ角：基準(zhǔn)點在坐標(biāo)軸上三維圖形的幾何變換旋轉(zhuǎn)變換繞X軸正方向旋轉(zhuǎn)α角：基準(zhǔn)點在坐標(biāo)軸上三維圖形的幾何變換旋轉(zhuǎn)變換繞y軸正方向旋轉(zhuǎn)α角：基準(zhǔn)點在坐標(biāo)軸上三維圖形的幾何變換繞任意軸旋轉(zhuǎn)變換如果旋轉(zhuǎn)所繞的軸不是坐標(biāo)軸，而是一根任意軸，則變換過程變顯得較復(fù)雜。對物體作平移和繞軸旋轉(zhuǎn)變換，使得所繞之軸與某一標(biāo)準(zhǔn)坐標(biāo)軸重合。繞該標(biāo)準(zhǔn)坐標(biāo)軸作所需角度的旋轉(zhuǎn)。通過逆變換使所繞之軸恢復(fù)到原來位置。三維圖形的幾何變換繞任意軸旋轉(zhuǎn)變換設(shè)旋轉(zhuǎn)所繞的任意軸為p1,p2兩點所定義的矢量。旋轉(zhuǎn)角度為。平移T(-x1,-y1,-z1)使p1點與原點重合

旋轉(zhuǎn)Rx(α)使得軸p1p2落入平面xoz內(nèi)旋轉(zhuǎn)Ry(β)，使p1p2與z軸重合旋轉(zhuǎn)Rz(θ)，執(zhí)行繞p1p2軸的θ角度旋轉(zhuǎn)；旋轉(zhuǎn)Ry(－β)；旋轉(zhuǎn)Rx(－α)；平移T(x1,y1,z1)。三維圖形的幾何變換繞任意軸旋轉(zhuǎn)變換三維圖形的幾何變換繞任意軸旋轉(zhuǎn)變換設(shè)旋轉(zhuǎn)所繞的任意軸為p1(x1,y1,z1),p2(x2,y2,z2)兩點所定義的矢量。旋轉(zhuǎn)角度為。

T使p1點與原點重合三維圖形的幾何變換繞任意軸旋轉(zhuǎn)變換