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

2.1直線(xiàn)的生成2.1.2中點(diǎn)畫(huà)線(xiàn)算法

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

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

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

式中a=y0-y1,b=x1-x0,c=x0y1-x1y0。中點(diǎn)畫(huà)線(xiàn)算法直線(xiàn)的正負(fù)劃分性直線(xiàn)上方點(diǎn)：F(X，Y)＞0直線(xiàn)下方的點(diǎn)F(X，Y)＜0中點(diǎn)畫(huà)線(xiàn)算法問(wèn)題：判斷距直線(xiàn)最近的下一個(gè)象素點(diǎn)構(gòu)造判別式：di=F(M)=F(Xp+1,Yp+0.5)

由di＞0，＜0可判定下一個(gè)象素，PP2P1中點(diǎn)畫(huà)線(xiàn)算法要判定再下一個(gè)象素，分兩種情形考慮： 1）若di>0，取右下方象素P1，再下一個(gè)象素判定，由：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中點(diǎn)畫(huà)線(xiàn)算法要判定再下一個(gè)象素，分兩種情形考慮：

2）若di≤0，取右上方象素P2，再下一個(gè)象素，由：di+1=F(Xp+2,Yp+1.5)=a(Xp+1)+b(Yp+0.5)+c+a+b=di+a+bdi的增量為a+bPP2P1中點(diǎn)畫(huà)線(xiàn)算法d的初始值d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=

F(x0,y0)+a+0.5b因(x0,y0)在直線(xiàn)上，F(xiàn)(x0，y0)=0,所以，d0=a+0.5b中點(diǎn)畫(huà)線(xiàn)算法d的增量都是整數(shù)，只有初始值包含小數(shù)，可以用2d代替d,2a改寫(xiě)成a+a。算法中只有整數(shù)變量，不含乘除法，可用硬件實(shí)現(xiàn)。中點(diǎn)畫(huà)線(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(取下點(diǎn))d≤0di+1=di+2(a+b)=di-2(Δy-Δx)（取上點(diǎn)）中點(diǎn)畫(huà)線(xiàn)算法例：設(shè)第一象限直線(xiàn)OE，起點(diǎn)為(2，1)，終點(diǎn)坐標(biāo)為(12，9)試用中點(diǎn)畫(huà)線(xiàn)算法計(jì)算，并作出走步軌跡圖。

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

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

x|ymin△xnext有效邊表掃描線(xiàn)填充算法（2）有效邊表的構(gòu)造△x：從當(dāng)前掃描線(xiàn)到下條掃描線(xiàn)之間的x增量。設(shè)該邊的直線(xiàn)方程為：ax+by+c=0，當(dāng)前掃描線(xiàn)及下一條掃描線(xiàn)與邊的交點(diǎn)分別為(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有效邊表掃描線(xiàn)填充算法為了方便有效邊表的建立和更新，構(gòu)造邊表：（1）構(gòu)造一個(gè)縱向鏈表，長(zhǎng)度為多邊形所占有的最大掃描線(xiàn)數(shù)。（2）按照邊的下端點(diǎn)y坐標(biāo)對(duì)非水平邊進(jìn)行分類(lèi)的指針數(shù)組,下端點(diǎn)y坐標(biāo)值等于i的邊屬于第i類(lèi)。繪圖窗口中有多少條掃描線(xiàn)，ET就分為多少類(lèi)。（3）同一類(lèi)中的邊按x值（x值相等的，按△x值）遞增的順序排列。二維圖形幾何變換基本的幾何變換有平移、旋轉(zhuǎn)、縮放、對(duì)稱(chēng)和錯(cuò)切。二維變換的齊次坐標(biāo)表示齊次坐標(biāo)所謂齊次坐標(biāo)就是將一個(gè)原本是n維的向量用一個(gè)n+1維向量來(lái)表示。如向量(x1,x2,…,xn)的齊次坐標(biāo)表示為(hx1,hx2,…h(huán)xn,h),其中h是一個(gè)實(shí)數(shù)。顯然一個(gè)向量的齊次表示是不唯一的，齊次坐標(biāo)的h取不同的值都表示的是同一個(gè)點(diǎn)，比如齊次坐標(biāo)[8,4,4]、[4,2,2]表示的都是二維點(diǎn)[2,1]。二維變換的齊次坐標(biāo)表示齊次坐標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

變換合成時(shí)，矩陣相乘的順序。先作用的變換放在連乘式的左端，后作用的變換放在連乘式的右端。對(duì)于兩個(gè)基本變換M1，M2，由于矩陣乘法不滿(mǎn)足交換律，通常M1?M2≠M(fèi)2?M1，只有在下列特殊情況下，順序才是可交換的。

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

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

簡(jiǎn)述關(guān)于任意一條直線(xiàn)對(duì)稱(chēng)的變換矩陣的求解過(guò)程。寫(xiě)出關(guān)于直線(xiàn)-x+2y+3=0對(duì)稱(chēng)的變換矩陣。

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

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

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

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

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

三維圖形的幾何變換通用固定點(diǎn)的縮放

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

三維圖形的幾何變換對(duì)稱(chēng)變換相對(duì)于x軸的對(duì)稱(chēng)變換：

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

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

z坐標(biāo)不變，x,y坐標(biāo)取反三維圖形的幾何變換對(duì)稱(chēng)變換相對(duì)于坐標(biāo)原點(diǎn)的對(duì)稱(chēng)變換：

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

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

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

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

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

旋轉(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)兩點(diǎn)所定義的矢量。旋轉(zhuǎn)角度為。

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