圖形學算法復習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點與原點重合三維圖形的幾何變換繞任意軸旋轉變換