第三章(3D圖形-變換)

第三章、三維圖形3.1坐標(biāo)系3.2三維變換3.3坐標(biāo)系變換3.4投影變換3.5視變換3.6三維剪取3.7消隱第三章1第三章2坐標(biāo)系坐標(biāo)系現(xiàn)實(shí)的物體具有高度、寬度、和深度。它們可以用三維坐標(biāo)系的x軸、y軸和z軸來表示。三維坐標(biāo)系是一個(gè)直角坐標(biāo)系；坐標(biāo)系內(nèi)任何一點(diǎn)可以由一個(gè)有序的三元組(x,y,z)來表示。每個(gè)坐標(biāo)表示該點(diǎn)與坐標(biāo)原點(diǎn)之間沿相應(yīng)坐標(biāo)軸的正向或反向的距離。在現(xiàn)實(shí)世界中，人們通常使用右手坐標(biāo)系表示物體的位置，因此它又經(jīng)常被稱為世界坐標(biāo)系(WorldCoordinateSystem)。在計(jì)算機(jī)圖形顯示時(shí)，一般采用另一種三維坐標(biāo)系：計(jì)算機(jī)的屏幕是一個(gè)平面。指定它的左下角為原點(diǎn)，x軸正向向右延伸，y軸正向向上延伸。另外，定義z軸從原點(diǎn)開始，指向屏幕內(nèi)部，表示深度。這個(gè)坐標(biāo)系稱作左手坐標(biāo)系。zxyxyz第三章3三維圖形3.2

三維變換

一、平移變換二、縮放變換三、旋轉(zhuǎn)變換四、變形變換第三章4平移變換平移變換每個(gè)三維點(diǎn)(x,y,z)對應(yīng)于一個(gè)齊次坐標(biāo)[x,y,z,1]。所有的三維變換都可通過乘以一個(gè)4×4的變換矩陣來進(jìn)行。平移變換

點(diǎn)(x,y,z)沿x軸方向平移Tx距離，沿y軸方向平移Ty距離，沿z軸方向平移Tz距離，變成點(diǎn)(x′,y′,z′)，這一變換過程的變換矩陣為:

T3(Tx,Ty,Tz)=

[x′,y′,z′,1]=[x,y,z,1]×T3[Tx,Ty,Tz]=[x+Tx,y+Ty,z+Tz,1]1

0

0

0

0

1

0

0

0

0

1

0

TxTyTz1TxTzTy第三章5三維圖形3.2

三維變換

一、平移變換二、縮放變換三、旋轉(zhuǎn)變換四、變形變換第三章6縮放變換縮放變換幾何圖形的三維縮放變換是通過對構(gòu)成圖形的各個(gè)點(diǎn)同時(shí)進(jìn)行坐標(biāo)值的縮放來實(shí)現(xiàn)的。設(shè)一個(gè)點(diǎn)沿x,y,z軸縮放的比例分別為Sx,Sy,Sz,則縮放變換矩陣可表示為：

S3(Sx,Sy,Sz)=

[x′,y′,z′,1]=[x,y,z,1]×S3[Sx,Sy,Sz]=[x·Sx,y·Sy,z·Sz,1]當(dāng)|Sx|,|Sy|,|Sz|分別大于1時(shí)，為物體的放大，小于1時(shí)，為縮小變換;

當(dāng)|Sx|,|Sy|,|Sz|皆等于1時(shí)，即為恒等變換；

當(dāng)|Sx|,|Sy|,|Sz|分別小于0時(shí)，作相應(yīng)坐標(biāo)軸的鏡面變換。Sx0

0

0

0

Sx0

0

0

0

Sx0

0

0

0

1第三章3三維圖形3.2

三維變換

一、平移變換二、縮放變換三、旋轉(zhuǎn)變換四、變形變換第三章8旋轉(zhuǎn)變換繞坐標(biāo)軸旋轉(zhuǎn)旋轉(zhuǎn)角度θ為正時(shí)，點(diǎn)的旋轉(zhuǎn)方向：在右手坐標(biāo)系中

旋轉(zhuǎn)軸 相應(yīng)的旋轉(zhuǎn)方向

x軸 從y軸到z軸

y軸 從z軸到x軸

z軸 從x軸到y(tǒng)軸在左手坐標(biāo)系中

從旋轉(zhuǎn)軸的正向看去，旋轉(zhuǎn)方向是順時(shí)針方向。

這樣定義旋轉(zhuǎn)方向的原因是為了保證無論在在

右手坐標(biāo)系中還是在左手坐標(biāo)系中，所用的旋

轉(zhuǎn)矩陣是相同的。yzxzxy第三章9旋轉(zhuǎn)變換繞坐標(biāo)軸旋轉(zhuǎn)繞z軸旋轉(zhuǎn)的變換矩陣是

Rz(θ)=繞x軸旋轉(zhuǎn)的變換矩陣是

Rx(θ)=

繞y軸旋轉(zhuǎn)的變換矩陣是

Ry(θ)=cosθ

sinθ

00

-sinθ

cosθ

0

0

0

0

1

0

0

0

0

11

0

00

0

cosθ

sinθ

0

0

-sinθ

cosθ

0

0

0

0

1cosθ

0

-sinθ

0

0

1

0

0

sinθ

0

cosθ0

0

0

0

1第三章10旋轉(zhuǎn)變換繞任意軸旋轉(zhuǎn)求繞任意直線旋轉(zhuǎn)矩陣的原則任意變換的問題基本幾何變換的問題饒任意直線旋轉(zhuǎn)的問題繞正軸旋轉(zhuǎn)的問題第三章10旋轉(zhuǎn)變換繞任意軸旋轉(zhuǎn)yzxP1P2P′1P′2zyxP′2(a,b,c)P′′2abcyxzP′′2αyxzθ第三章10旋轉(zhuǎn)變換繞任意軸旋轉(zhuǎn)繞直線P1P2旋轉(zhuǎn)θ角的過程可分解為下列步驟：把點(diǎn)P1

(x1,y1,z1)移至原點(diǎn)；繞x軸旋轉(zhuǎn)，使直線與xz平面重合；繞y軸旋轉(zhuǎn)，使直線與z軸重合；繞z軸旋轉(zhuǎn)θ角；執(zhí)行步驟(3)的逆變換；執(zhí)行步驟(2)的逆變換；執(zhí)行步驟(1)的逆變換；第三章11旋轉(zhuǎn)變換繞任意軸旋轉(zhuǎn)步驟(1)把點(diǎn)P1(x1,y1,z1)移至原點(diǎn):變換矩陣為：

T3(-x1,-y1,-z1)=

步驟(2)繞x軸旋轉(zhuǎn)，使直線與xz平面重合：設(shè)此刻P2(x2,y2,z2)的坐標(biāo)變?yōu)镻’2(a,b,c)?？芍? cosφ=c/(b2+c2)1/2；sinφ=b/(b2+c2)1/2；

設(shè)d1=(b2+c2)1/2，則變換矩陣為:

Rx(φ)=1

0

0

0

0

c/d1b/d10

0

-b/d1c/d10

-x1

-y1

-z111

0

0

0

0

1

0

0

0

0

1

0

-x1-y1-z11yzxP1P2P’1P’2zyxP’2(a,b,c)P’’2abc第三章12繞任意軸旋轉(zhuǎn)步驟(3)繞y軸旋轉(zhuǎn)，使直線與z軸重合：

此刻P’2的坐標(biāo)為P’’2(a,0,d1),可知：

cosα=-d1/(a2+d12)1/2=(b2+c2)1/2/(a2+b2+c2)1/2；

sinα=a/(a2+b2+c2)1/2；

令d2

=(a2+b2+c2)1/2，則變換矩陣為:

Ry(α)=

步驟(4)繞z軸旋轉(zhuǎn)θ角，變換矩陣為:

Rz(θ)=旋轉(zhuǎn)變換d1/d2

0

a/d2

0

0

1

0

0

-a

0

d1/d2

0

0

0

0

1cosθ

0

-sinθ

0

0

1

0

0

sinθ

0

cosθ0

0

0

0

1yxzyxzP’’2(a,0,d1)αθ第三章13繞任意軸旋轉(zhuǎn)步驟(5)執(zhí)行步驟(3)的逆變換,變換矩陣為Ry(-α)；步驟(6)執(zhí)行步驟(2)的逆變換,變換矩陣為Rx(-φ)；步驟(7)執(zhí)行步驟(1)的逆變換,變換矩陣為T3(x1,y1,z1)；

綜上，繞直線P1P2旋轉(zhuǎn)θ角的變換矩陣為：

R(θ)=T3(-x1,-y1,-z1)Rx(φ)Ry(α)Ry(θ)Ry(-α)Rx(-φ)T3(x1,y1,z1)注意：變換的過程有多種選擇，但如果中間的幾個(gè)旋轉(zhuǎn)次序變了，則各個(gè)矩陣參數(shù)的對應(yīng)矩陣參數(shù)也會完全不同。旋轉(zhuǎn)變換第三章14三維圖形3.2

三維變換

一、平移變換二、縮放變換三、旋轉(zhuǎn)變換四、變形變換第三章15變形變換變形變換對于過原點(diǎn)的一條直線，如果希望把它

變換成另一條不同的過原點(diǎn)的直線，可

以通過變形變換來實(shí)現(xiàn)。它可以產(chǎn)生變形

的效果。例如：一個(gè)正方體可通過三維變形變換變成一個(gè)平行六面體。這里只考慮比較簡單的情況。把一條不在x，y平面上的過原點(diǎn)的直線變換成z軸，對應(yīng)的z軸坐標(biāo)都保持不變。這樣z-變形變換的矩陣可以考慮在yoz平面和xoz平面上的組合變形情況。zxy第三章15變形變換變形變換對于yoz平面上的變形情況，考慮直線y=-bz， 則變形后的直線方程為：

y’=y-(-bz)=y+bz z’=z對于xoz平面上的變形情況，考慮直線x=-az， 則變形后的直線方程為：

x’=x-(-az)=x+az z’=zzyy=-bzzxx=-az第三章15變形變換變形變換則z-變形變換的矩陣表達(dá)式如下：

shz=

其中a,b參數(shù)由直線方程所決定。設(shè)直線上任一點(diǎn)P(x1,y1,z1)≠0經(jīng)過z變形變換，將變成P(0,0,z1)，即：

[x1,y1,z1,1]×shz=[x1+az1,y1+bz1,z1,1]=[0,0,z1,1]

即 x1+az1=0 則 a=-x1/z1 y1+bz1=0 b=-y1/z1如果該直線位于x，y平面，則z1=0，無法把它變換成z軸。1000

0100

ab10

0001zxy第三章16坐標(biāo)系變換坐標(biāo)系變換同一物體在不同的坐標(biāo)系中描述時(shí)，會有不同的坐標(biāo)值。在甲坐標(biāo)系中定義一個(gè)物體，那么只要把乙坐標(biāo)系的坐標(biāo)軸變換成甲坐標(biāo)系的坐標(biāo)軸，就可以在乙坐標(biāo)系中定義物體了。坐標(biāo)系平移例1：新坐標(biāo)系x’o’y’的原點(diǎn)o’在坐標(biāo)系xoy的坐標(biāo)為(2,4),則從x’o’y’到xoy的變換矩陣為T2(-2,-4),xoy坐標(biāo)系中一點(diǎn)P(4,5),在x’o’y’坐標(biāo)系中的坐標(biāo)矢量為：

[4,5,1]×T2(-2,-4)=[2,1,1]

yy’oo’x’xP(4,5)(2,4)第三章16坐標(biāo)系變換坐標(biāo)系變換坐標(biāo)系旋轉(zhuǎn)例2：x’o’y’坐標(biāo)系與xoy坐標(biāo)系原點(diǎn)重合，將x’o’y’坐標(biāo)系逆時(shí)針旋轉(zhuǎn)45°就變成了xoy坐標(biāo)系，則變換矩陣為：

R(π/4)= =cosπ/4

sinπ/4

0

-sinπ/4

cosπ/4

0

0

0

121/2/2

21/2/2

0

-21/2/2

21/2/2

0

0

0

1y’xx’yo(o’)45。第三章17坐標(biāo)系變換坐標(biāo)系復(fù)合變換例3：求變換矩陣為平移矩陣和旋轉(zhuǎn) 矩陣的乘積矩陣：

T2(-2,-4)×R2(π/4)分析 根據(jù)旋轉(zhuǎn)矩陣， 其中，第一列(cosπ/4,-sinπ/4,0)和第二列(sinπ/4,cosπ/4,0)分別是新坐標(biāo)x’軸和y’軸在原坐標(biāo)中方向矢量，且為正交單位矢量。坐標(biāo)系變換cosπ/4

sinπ/4

0

-sinπ/4

cosπ/4

0

0

0

1yy’oo’x’x第三章17坐標(biāo)系變換三維坐標(biāo)的推廣比較適合于給出了旋轉(zhuǎn)角度或很容易求出旋轉(zhuǎn)角度的情況在新坐標(biāo)系的旋轉(zhuǎn)角度沒有給出時(shí)，且不易計(jì)算。這時(shí)一般會給出新坐標(biāo)系的原點(diǎn)坐標(biāo)和三個(gè)坐標(biāo)的方向矢量。坐標(biāo)系變換坐標(biāo)系變換把給出的新坐標(biāo)的3個(gè)方向矢量分別規(guī)格化，

得到用原坐標(biāo)系定義的3個(gè)正交單位矢量： u=(ux,uy,uz)

v=(vx,vy,vz)

w=(wx,wy,wz)

新的坐標(biāo)原點(diǎn)位置是(x,y,z)，則變換矩陣為：

T3×R3=

1

0

0

0

0

1

0

0

0

0

1

0

-x

-y

-z

1ux

vx

wx

0

uy

vy

wy

0

uz

vz

wz

0

0

0

0

1第三章18坐標(biāo)系變換XYZWZVYUX(X,Y,Z)第三章18三維圖形3.4

投影變換

一、概述二、平行投影三、透視投影第三章19概述概述要把現(xiàn)實(shí)世界的三維物體在計(jì)算機(jī)的二維屏幕上顯示出來，必須經(jīng)過投影變化這一步驟，把物體從三維表示形式轉(zhuǎn)化為二維表示形式。投影變換常用平行投影以及透視投影、椎頂投影等多種。投影面投影中心投影線ABA’B’投影面投影中心投影線ABA’B’第三章20三維圖形3.4

投影變換

一、概述二、平行投影三、透視投影投影變換根據(jù)投影線是否平行，

可分為：正平行投影斜平行投影等距平行投影

正平行投影

投影方向垂直于投影平面時(shí)稱為正平行投影

三視圖（正視圖、頂視圖、側(cè)視圖）均屬于正平行投影第三章21平行投影正平行投影頂視圖側(cè)視圖正視圖第三章22平行投影正平行投影三視圖的生成就是把x、y、z

坐標(biāo)系下的形體投影到z=0的平面，變換到u、v、w

坐標(biāo)系。一般還需將三視圖在一個(gè)平面上畫出。zyxa2c2b2a1b1c1第三章22平行投影正平行投影變換矩陣（其中(a,b)為u、v坐標(biāo)下的值） 正視圖(uvw1)=(xyz1)頂視圖(uvw1)=(xyz1)

側(cè)視圖(uvw1)=(xyz1)-1

0

0

0

0

-1

0

0

0

0

0

0

a-tx

b-ty

0

10

0

0

0

1

0

0

0

0

1

0

0

a+ty

b+tz

0

1-1

0

0

0

0

0

0

0

0

1

0

0

a-tx

b+tz

0

1uzyyxozyyxoo’vtztztxtxtyty(a,b)第三章23平行投影斜平行投影如果投影方向不垂直于投影平面，則稱為斜平行投影。在斜平行投影中，投影平面一般取坐標(biāo)平面。以下用兩種方法推導(dǎo)斜平行投影的公式。設(shè)投影方向矢量為(xp,yp,zp),若形體被投影到xoy平面上，形體上的一點(diǎn)為(x,y,z)，要確定其投影(xs,ys)。可知投影線的方程為：

xs=x+xp·t 因?yàn)?xs,ys,zs)在z=0平面上，故t=-z/zp,

ys=y+yp·t 由此 xs=x-xp/zp·z

zs=z+zp·t ys=y-yp/zp·z若令Sxp=xp/zp,Syp=yp/zp,則有：

[xs,ys,zs,1]=[x,y,z,1]

1

0

0

0

0

1

0

0

-Sxp-Syp1

0

0

0

0

1yzx(xs,ys)(x,y,z)(xp,yp,zp)第三章24平行投影斜平行投影在左手坐標(biāo)系中求斜平行投影的坐標(biāo)變換

設(shè)其投影平面為xcocyyc，立方體上的一點(diǎn)P(0,0,1)在平面xcocyycxcocyyc上的坐標(biāo)為P’(lcosα,lsinα,0)，投影方向?yàn)镻P’，與投影平面的夾角為β，其方向余弦為(lcosα,lsinα,-1)?，F(xiàn)考慮任意一點(diǎn)(xc,yc,zc)在平面xcocyyc上的投影(xs,ys)，因?yàn)橥队胺较蚺c投影線平行，且投影線的方程為：

zc-zs

yc-ys

xc-xs

───=───=───

-1 lsinαlcosα

且zs=0，所以xs=xc+zc(lcosα)，ys=yc+zc(lsinα)矩陣形式為：

[xsyszs1]=[xcyczc1]1

0

0

0

0

1

0

0

lcosαlsinα0

0

0

0

0

1xcyczcocαlzcαycxcP’P(0,0,1)βl第三章25三維圖形3.4

投影變換

一、概述二、平行投影三、透視投影一點(diǎn)透視兩點(diǎn)透視第三章26透視投影透視投影單位立方體透視投影的視線是從視點(diǎn)(觀察點(diǎn))出發(fā)，視線是不平行的，透視投影按照滅點(diǎn)的個(gè)數(shù)分為一點(diǎn)透視，兩點(diǎn)透視和三點(diǎn)透視。任何一束不平行于投影平面的平行線的投影將匯聚在一點(diǎn)稱之為滅點(diǎn)，在坐標(biāo)系上的滅點(diǎn)稱為主滅點(diǎn)。第三章27透視投影透視投影主滅點(diǎn)數(shù)是和投影平面切割坐標(biāo)軸的數(shù)量相對應(yīng)的。如投影平面僅切割z軸，則z軸是投影平面的法線，因而只在z軸上有一個(gè)滅點(diǎn)，平行于x軸或y軸的直線也平行于投影平面，因而沒有滅點(diǎn)。yxzo第三章28透視投影一點(diǎn)透視假設(shè)投影中心為原點(diǎn)，投影面平行于xy平面，方程為z=D。設(shè)物體上一點(diǎn)P(x1,y1,z1),它的投影點(diǎn)為P′(x′,y′,z′)，則z′=D。投影線的方程為:

x=x1t

y=y1t

z=z1t： 把z=D代入的，得t=D/z1,則:

x1

y1

x=─×D；y=D×─

z1

z1xyDzP′(x′,y′,z′)P(x1,y1,z1)第三章29透視投影一點(diǎn)透視得到投影點(diǎn)的坐標(biāo)為：((x1/z1)D,(y1/z1)D,D),由相似三角形原理，得：x′/x1=y′/y1=D/z1即：

x1

y1

x′=─×D；y′=─×D

z1

z1

若D固定，z1↑，則x′↓，y′↓即對象越遠(yuǎn)，成像越小。若視點(diǎn)取無窮遠(yuǎn)(z≈D)時(shí)，則：x′=x，y′=y

此時(shí)，透視投影變?yōu)檎黄叫型队癉oxzz1P′(x′,y′,z′)P(x1,y1,z1)投影面Doyzz1P′(x′,y′,z′)P(x1,y1,z1)投影面第三章26透視投影一點(diǎn)投影Per(D)=

由上面分析，設(shè)透視投影的變換矩陣為：齊次點(diǎn)P[x,y,z,1]乘以矩陣Per(D)，得到：

x′=x/z·D

y′=y/z·D

z′=D

與前面的結(jié)果相吻合。1

0

0

0

0

1

0

0

0

0

1

1/D

0

0

0

0xyDzP′(x′,y′,z′)P(x1,y1,z1)第三章31三維圖形3.5

視變換

一、數(shù)學(xué)預(yù)備知識二、視變換參數(shù)三、視變換矩陣四、剪取五、透視投影第三章32數(shù)學(xué)預(yù)備知識矢量點(diǎn)積設(shè)v1(x1,y1,z1)和v2(x2,y2,z2)是兩個(gè)三維矢量，則其點(diǎn)積定義為： v1·v2=x1x2+y1y2+z1z2 （標(biāo)量）矢量v(x,y,z)的長度定義為：

|v|=(v·v)1/2=(x2+y2+z2)1/2兩個(gè)矢量間所成的角θ的余弦值可通過矢量長度和點(diǎn)積來表示 v1-v2

cosθ=

────或v1·v2=|v1|·|v2|·cosθ

|v1|·|v2|

當(dāng)v1與v2相互垂直時(shí)，點(diǎn)積為0。θv1v2第三章33數(shù)學(xué)預(yù)備知識矢量點(diǎn)積點(diǎn)積具有分配律： 設(shè)u,v,w為3個(gè)矢量，r為實(shí)數(shù)。有： u·(v+rw)=u·v+r(u·w)構(gòu)造一個(gè)新矢量： 給定長度為1的單位矢量n和一個(gè)不平行于n的矢量w，則w在垂直于n的平面上的投影v表示為:

v=w-(n·w)·n

證明：n·v=n·(w-(n·w)·n) =n·w-(n·w)(n·n) =n·w-(n·w)·l2=0 所以v垂直于n。wnv(n·

w)n第三章34數(shù)學(xué)預(yù)備知識矢量叉積矢量叉積定義如下：

v1×v2=(y1z2-z1y2,z1x2-x1z2,x1y2-y1x2)（矢量）2個(gè)互不平行的矢量，其叉積形成一個(gè)與2個(gè)矢量都垂直的新的矢量，它的方向符合右手判別法如果v1平行于v2，則

v1×v2=(0,0,0)v1xv2v1v2第三章35三維圖形3.5

視變換

一、數(shù)學(xué)預(yù)備知識二、視變換參數(shù)三、視變換矩陣四、剪取五、透視投影第三章36視變換參數(shù)視變換參數(shù)右手世界坐標(biāo)系：在進(jìn)行視變換時(shí)，需要一系列的參數(shù)來確定投影面的位置、方向和投影中心的位置。這些參數(shù)用來定義右手世界坐標(biāo)系定義視平面（也稱投影面）：由平面上的一點(diǎn)和平面的法線來定義。視平面上的點(diǎn)為視圖參考點(diǎn)(VRP)，視平面法線為平面方向(VPN)定義左手眼睛坐標(biāo)系：（用于投影變換）軸VPN：一根坐標(biāo)軸方向就是視平面的法線方向軸v：用一條不平行于的VPN視圖上方矢量(VUP)在視平面上 的投影來構(gòu)造，即：v=VUP-(VPN·VUP)VPN軸u：使得u,v,VPN形成一個(gè)左手坐標(biāo)系，即VPN,v,u形成一 個(gè)右手坐標(biāo)系，則：u=VPN×vVPNVUPVRPuvCOP視平面視平面窗口第三章37視變換參數(shù)窗口和投影中心定義了一個(gè)無限四棱錐體，稱為視體積只有在視體積內(nèi)的物體才會被投影到視平面窗口內(nèi)顯示出來通過制定平行于視平面的前后剪取平面來截取視體積，以刪除離視平面過近和過遠(yuǎn)的物體這樣視平面體積是有限的視變換參數(shù)后剪取窗口視平面窗口前剪取窗口BFCOP第三章38三維圖形3.5

視變換

一、數(shù)學(xué)預(yù)備知識二、視變換參數(shù)三、視變換矩陣四、剪取五、透視投影第三章39視變換矩陣視變換矩陣把右手世界坐標(biāo)系里的圖像變換為左手眼睛坐標(biāo)系里的圖像的全過程如下：

用三維世界坐標(biāo)系定義圖像模式變換把圖像變成三維眼睛

坐標(biāo)系，原點(diǎn)為觀察

者，觀察方向?yàn)閆軸視變換

截取視體積，執(zhí)行三維剪取剪取

執(zhí)行透視投影，

把三維物體投

影到視平面上投影變換視窗口內(nèi)圖像變

換到屏幕坐標(biāo)系

加以顯示顯示第三章40視變換矩陣模式變換在變換開始時(shí)，輸入視變換參數(shù)：視圖參考點(diǎn)(VRP)，視圖上方矢量(VUP)和投影中心(cop)，然后輸入視窗口在u,VPN,v坐標(biāo)系中的位置：輸入窗口坐下角的位置(umin,vmin)和右上角的位置(umax,vmax)；

以及輸入前后剪取平面與視平面的距離F和B：

計(jì)算矢量u,v。v為VUP

在視平面上的投影。先

把視平面方向矢量進(jìn)行

規(guī)格化，再計(jì)算v,u：

v=VUP-(VPN·VUP)VPN

u=VPN×vVPNVUPVRPuvcop視平面視平面窗口當(dāng)F<0時(shí) 當(dāng)F>0時(shí)

前剪取平面

前剪取平面

視平面

視平面

后剪取平面

后剪取平面FFBB第三章41視變換矩陣視變換視變換的目的是：把以cop為原點(diǎn)，

為坐標(biāo)軸方向的左手系變換成右

手世界坐標(biāo)系。變換矩陣是一個(gè)平

移矩陣和一個(gè)旋轉(zhuǎn)矩陣的乘積。設(shè)

左手坐標(biāo)系原點(diǎn)cop在世界坐標(biāo)系中的坐標(biāo)為：(VRP[x]+cop[x],VRP[y]+cop[y],VRP[z]+cop[z])則此平移矩陣為：

T=1

0

0

0

0

1

0

0

0

0

1

0

-(VRP[x]

-(VRP[y]

-(VRP[z]

1

+cop[x])

+cop[y])

+cop[z])

uVPNvcopuVPNvVRPzxoyzxoyuVPNvcopuVPNvVRP第三章42視變換矩陣視變換設(shè)u,v,VPN為規(guī)格化后的3個(gè)

正交單位矢量,則旋轉(zhuǎn)矩陣為：

R=

改變z軸符號的矩陣為：

ch=

R與ch相乘得到的矩陣：

Rot=

經(jīng)過以上三步，視圖參考點(diǎn)VRP變換為視平面上的點(diǎn)VRP′:VRP′=VRP×T×R×ch=VRP×T×Rotu(x)

v(x)

-VPN(x)

0

u(y)

v(y)

-VPN(y)

0

u(z)

v(z)

-VPN(z)

0

0

0

0

11

0

0

0

0

1

0

0

0

0

-1

0

0

0

0

1u(x)

v(x)

VPN(x)

0

u(y)

v(y)

VPN(y)

0

u(z)

v(z)

VPN(z)

0

0

0

0

1xzoyuVPNvcopuVPNvVRPzxoyuvcop

視方向中心還要進(jìn)行z-變形變換，使視方向與z軸平行。首先，計(jì)算出視平面窗口相對于的位置VRP′的中心：

Ucenter=(umin+umax)/2

Vcenter=(vmin+vmax)/2

它在左手眼睛坐標(biāo)系中的x,y坐標(biāo)為： Center[x]=VRP′[x]+(umin+umax)/2

Center[y]=VRP′[y]+(vmin+vmax)/2

所以得到變換的變換矩陣：

sh=

窗口右上角xy坐標(biāo)為：

x=(Umax-Umin)/2

y=(Vmax-Vmin)/21

0

0

0

0

1 0

0

-Center[x]/VRP′[z]

-Center[y]/VRP′[z]

1

0

0

0

0

1zxoyuvcop

視方向中心視線方向中心zxy第三章43視變換矩陣視變換第三章44三維圖形3.5

視變換

一、數(shù)學(xué)預(yù)備知識二、視變換參數(shù)三、視變換矩陣四、剪取五、透視投影第三章45剪取剪取先對圖像在視體積內(nèi)的部分進(jìn)行三維剪取。第一步是要求出現(xiàn)視體積的6個(gè)平面方程，然后求交剪取方法將在以后介紹。為了使求交過程相對方便一些，可對視體積進(jìn)行縮放變換，把視體積變成有以下6個(gè)平面構(gòu)成：前平面：z=a；后平面：z=1；頂平面：y=z；底平面：y=-z；左平面：x=-z；右平面：x=z；zyxFB前

視窗口后xyzy=zz=az=1y=-z第三章46剪取剪取z的縮放因子Sz把平面z=VRP′[z]變換成，

1

Sz=────

VRP′[z]+B所以：由此可得：

VRP′[z]+F

a=────

VRP′[z]+B

后剪裁平面的右上角的y坐標(biāo),將從原來((VRP′[z]+B)/VRP′[z],(Vmax-Vmin)/2)的變?yōu)?，

所以得到y(tǒng)的縮放因子：

2VRP′[z]

Sy=

───────────

(VRP′[z]+B)(Vmax-Vmin)

同理：

2VRP′[z]

Sx=───────────

(VRP′[z]+B)(Umax-Umin)yxFB前

視窗口后xyzy=zz=az=1y=-z第三章47剪取剪取縮放矩陣為

Sc=

然后進(jìn)行三維圖像的裁剪(方法見后一節(jié))最后進(jìn)行縮放變換的逆變換，把圖像恢復(fù)原狀。逆變換的矩陣為:

Sc=Sx

0

0

0

0

Sy

0

0

0

0

Sz

0

0

0

0

11/Sx

0

0

0

0

1/Sy

0

0

0

0

1/Sz

0

0

0

0

1yxFB前

視窗口后xyzy=zz=az=1y=-z第三章48三維圖形3.5

視變換

一、數(shù)學(xué)預(yù)備知識二、視變換參數(shù)三、視變換矩陣四、剪取五、透視投影第三章49透視投影透視投影裁剪后的圖像還需經(jīng)過投影變換。

采用透視投影，需要決定的視變換矩陣中的D值。投影面(即視平面)到投影中心的距離為VRP′[z]，所以D=VRP′[z]。

投影矩陣為：

Per=1

0

0

0

0

1

0

0

0

0

1

1/VRP′[z]

0

0

0

1第三章50三維圖形3.6

三維剪取

一、三維剪取體的形狀二、三維Cohen-Sutherland

直線剪取算法三、三維Cyrus-Beck算法第三章51三維剪取體的形狀三維剪取體的形狀通常的三維剪取體有長方體和棱錐臺體。其中長方體適用于平行投影，棱錐臺體適用于透視投影，這兩種剪取體均為六面體，包括左側(cè)面、右側(cè)面、頂面、底面、前面和后面。其他形狀的剪取體并不常見。頂面左面后面右面前面底面頂面左面后面右面前面底面yyxxzz第三章52三維圖形3.6

三維剪取

一、三維剪取體的形狀二、三維Cohen-Sutherland

直線剪取算法三、三維Cyrus-Beck算法第三章53三維Cohen-Sutherland直線剪取算法Cohen-Sutherland算法原理與二維直線剪取算法一樣，三維Cohen-Sutherland直線剪取算法也采用斷點(diǎn)編碼方法來判斷線段的可見性。三維剪取中，按剪取體的每一面把整個(gè)空間劃分成27個(gè)子空間，每個(gè)子空間都用唯一編碼來標(biāo)識，采用六位編碼，具體編碼規(guī)則為：第1位為“1”表示端點(diǎn)位于剪取體的左邊；第2位為“1”表示端點(diǎn)位于剪取體的右邊；第3位為“1”表示端點(diǎn)位于剪取體的下邊；第4位為“1”表示端點(diǎn)位于剪取體的上邊；第5位為“1”表示端點(diǎn)位于剪取體的前邊；第6位為“1”表示端點(diǎn)位于剪取體的后邊；否則相應(yīng)位為零。若一線段的兩端點(diǎn)編碼均為零，則此線段的兩端點(diǎn)可見，此線段也可見。若線段兩端點(diǎn)編碼相與(AND)不為零，則該線段為完全不可見線段；否則該線段可能部分可見或完全不可見,此時(shí)需要計(jì)算剪取體與線段交點(diǎn)，方可最后決定。第三章54三維Cohen-Sutherland直線剪取算法Cohen-Sutherland算法原理對于長方體剪取體，三維剪取算法決定線段端點(diǎn)編碼只是二維剪取算法的直接推廣。但是對棱錐臺體剪取體，情況會復(fù)雜一些。一個(gè)有效的處理方法是作一個(gè)規(guī)范變換，使6個(gè)面的方程為：

y頂=z；y底=-z；

x右=z；x左=-z；

z后=1，z前=a(0＜a≤1)；

且投影中心為坐標(biāo)系原點(diǎn)。這樣情況變得簡單多了。第三章55三維Cohen-Sutherland直線剪取算法Cohen-Sutherland算法原理假設(shè)未經(jīng)變換前6個(gè)面的方程分別為：

右側(cè)面：x=α1z+α2；左側(cè)面：x=β1z+β2；

頂面：y=γ1z+γ2；底面：y=δ1z+δ2；

前面：z=zH；后

面：z=zY；

判斷點(diǎn)P(x,y,z)位于平面的那一側(cè)可以用下列函數(shù)測試: P位于平面 P位于平面 ＞0，右方； ＞0，右方；fR=x-α1z-α2

＝0，上方； fL=x-β1z-β2

＝0，上方； ＜0，左方； ＜0，左方；第三章56三維Cohen-Sutherland直線剪取算法Cohen-Sutherland算法原理 P位于平面 P位于平面 ＞0，上方； ＞0，前方；fT=y-γ1z-γ2

＝0，上方；fB=y-δ1z-δ2

＝0，上方； ＜0，下方； ＜0，下方；

P位于平面 P位于平面 ＞0，前方； ＞0，前方；

fH=z-zH

＝0，上方； fγ=z-zγ

＝0，上方； ＜0，后方； ＜0，面后方；

可以看出，本算法與二維算法是一樣的，只是空間區(qū)域被標(biāo)識為六部分。所以在算法實(shí)現(xiàn)過程中多了兩個(gè)面的判斷，其它部分也只有求交點(diǎn)時(shí)多求一個(gè)z分量。第三章57Cohen-Sutherland算法描述三維Cohen-Sutherland直線剪取算法 booldone，draw；done表示是否完成，draw表示是否可見,unsignedcharcode1，code2；分別為端點(diǎn)1，端點(diǎn)2的編碼

while(!done)begin

if(判斷code1，code2，若為第一種情況)begin

done=TRUE；

draw=TRUE；

end

elseif(為第二種情況)begin

done=TRUE；

draw=FALSE；

end

elsebegin

if(檢查code1，若在窗口內(nèi))begin

交換端點(diǎn)及端點(diǎn)的編碼；

end

以左右下上前后的次序?qū)Χ它c(diǎn)1進(jìn)行判斷及交；

將交點(diǎn)的值賦給端點(diǎn)1；

end

end第三章58三維Cohen-Sutherland直線剪取算法Cohen-Sutherland算法分析可以看出，本算法與二維算法是一樣的，只是空間區(qū)域被標(biāo)識為六部分。所以在算法實(shí)現(xiàn)過程中多了兩個(gè)面的判斷，其它部分也只有求交點(diǎn)時(shí)多求一個(gè)z分量。由于與二維時(shí)算法是一致的，所以它的優(yōu)缺點(diǎn)也是一樣的。Cohen-Sutherland算法的優(yōu)點(diǎn)在于簡單，易于實(shí)現(xiàn)。第三章59三維圖形3.6

三維剪取

一、三維剪取體的形狀二、三維Cohen-Sutherland

直線剪取算法三、三維Cyrus-Beck算法第三章60三維Cyrus-Beck直線剪取算法Cyrus-Beck算法原理在上一章介紹了Cyrus-Beck二維剪取算法，他除了要求剪取區(qū)域?yàn)橥箙^(qū)域外，對剪取區(qū)域的形狀沒有其他任何限制。所以，剪取區(qū)域可以是三維凸體(包括長方體，棱錐臺體)，上一章的算法可以直接用于三維情形。不過原來的窗口邊，現(xiàn)在為剪取體的面，原來矢量只有x,y兩個(gè)分量，現(xiàn)在矢量均具有x,y,z三個(gè)分量。如上一章所述，在二維情形下，可以采用旋轉(zhuǎn)和平移方法決定多邊形的凹凸性以及內(nèi)法矢量。這種方法同樣也可以推廣到三維情形。Cyrus-Beck算法描述第三章61三維Cyrus-Beck直線剪取算法while對于剪取體的每一個(gè)多邊形表面do

begin

平移剪取體，使多邊形表面的一個(gè)頂點(diǎn)重合于坐標(biāo)系原點(diǎn)繞原點(diǎn)旋轉(zhuǎn)多邊形，使該頂點(diǎn)相鄰的兩邊中，有一邊重合于某坐 標(biāo)軸(如x軸或y軸)

繞此坐標(biāo)軸旋轉(zhuǎn)，使多邊形表面與一坐標(biāo)平面(如z=0)重合

if

所有頂點(diǎn)的相應(yīng)坐標(biāo)分量同號或?yàn)榱?/p>

then對于此多邊形平面，剪取體為凸體

else對于此多邊形平面，標(biāo)志剪取體為凹體goto9

end標(biāo)志剪取體為凸體計(jì)算剪取體各多邊形表面的內(nèi)法向量endofalgorithm

第三章62三維Cyrus-Beck直線剪取算法Cyrus-Beck算法分析本算法的實(shí)現(xiàn)是簡單的，只要將二維算法擴(kuò)充一下即可。然而，當(dāng)涉及到圖形輸出時(shí)就碰到了很大的障礙，即如何將對每個(gè)凸體實(shí)施算法后合成并顯示。這里碰到的問題是消隱，包括物體間消隱和自消隱。這個(gè)問題將在后面的章節(jié)中涉及到，這里不再說明。第三章63三維圖形3.7

消隱

一、消隱的考慮二、Roberts算法三、Warnock算法四、表優(yōu)先級算法五、Z緩沖區(qū)算法六、光線跟蹤算法七、掃描線算法用計(jì)算機(jī)生成三維形體的真實(shí)圖形，是計(jì)算機(jī)圖形學(xué)研究的重要內(nèi)容之一。在使用顯示設(shè)備描繪三維圖形時(shí)，必須把三維信息作某種投影變換，在二顯示表面上繪制出來。由于投影變換失去了深度信息，往往導(dǎo)致圖形的二義性：

要消除二義性，必須在繪制時(shí)消隱實(shí)際不可見得線和面，即消隱。經(jīng)過消隱的投影圖稱為物體的真實(shí)圖形。投影變換的二義性消隱的考慮第三章65第三章66消隱的考慮消隱的考慮選擇不同的消隱算法

消隱問題有不同的算法，有些算法要求速度快，有些要求圖形的真實(shí)度高。例如，快速消隱算法可用于實(shí)時(shí)模擬如飛行模擬等；具有高度真實(shí)感圖形的消隱算法可用于計(jì)算機(jī)動(dòng)畫等領(lǐng)域，所生成的圖形一般具有連續(xù)色調(diào)，并能產(chǎn)生陰影、透明、表面紋理及反射、折射等視覺效果。不過這類算法比較慢。產(chǎn)生一幅圖可能需要幾分鐘甚至幾小時(shí)。所以，在進(jìn)行消隱算法的設(shè)計(jì)時(shí)，應(yīng)在計(jì)算速度和圖形細(xì)節(jié)之間進(jìn)行權(quán)衡，任何一種算法都不能兼顧兩者。第三章66消隱的考慮消隱的考慮消隱算法的實(shí)現(xiàn)空間

消隱算法可以在對象空間或圖像空間中實(shí)現(xiàn)。對象空間算法是在定義對象的坐標(biāo)系中實(shí)現(xiàn)的，而圖像空間算法是在對象顯示的屏幕坐標(biāo)系中實(shí)現(xiàn)的。對象空間算法以盡可能高的精度完成幾何計(jì)算，所以可以把圖像放大許多倍而不致?lián)p害其準(zhǔn)確性，但是圖像空間算法只能以與顯示屏的分辨率相適應(yīng)的精度來完成計(jì)算，所以其圖像的放大效果較差。另外，這兩類算法的性能特性也是不同的。對象空間算法所需的計(jì)算時(shí)間隨場量中物體的個(gè)數(shù)而增加，而圖像空間的計(jì)算時(shí)間則隨圖像中可見部分的復(fù)雜程度而增加。第三章67三維圖形3.7

消隱

一、消隱的考慮二、Roberts算法三、Warnock算法四、表優(yōu)先級算法五、Z緩沖區(qū)算法六、光線跟蹤算法七、掃描線算法第三章68Roberts算法原理Roberts算法Roberts消隱算法是在圖像空間實(shí)現(xiàn)的消隱算法，數(shù)學(xué)處理嚴(yán)謹(jǐn)，計(jì)算量甚大。Roberts算法要求所有被顯示的物體都是凸的，因此對凹體要先分割成許多個(gè)凸體的組合。此算法的基本步驟是：逐個(gè)的獨(dú)立的考慮每個(gè)物體自身，找出為其自身所遮擋的邊和面；將每一物體上留下的邊再與其它物體逐個(gè)的進(jìn)行比較，以確定其是完全可見還是部分或全部被遮擋；確定由于物體之間的相互貫穿等原因，是否要形成新的顯示邊等。從而使被顯示各物體更接近現(xiàn)實(shí)。下面先介紹一些用到的一些基本概念以及有關(guān)的數(shù)學(xué)方法。第三章69Roberts算法原理Roberts算法體矩陣

假設(shè)在三維空間中，一平面的方程表示為：ax+by+cz+d=0,令P=[a,b,c,d]，表示平面的系數(shù)向量；又令S=[x,y,z,1]，表示三維空間重點(diǎn)的其次坐標(biāo)。上式改寫為：S·PT=0。所以凸體可由平面方程系數(shù)組成的體矩陣表示：

矩陣的每一列表示物體的對

[V]= 應(yīng)平面方程的系數(shù)，其列數(shù) 與物體的面數(shù)一致。

由于當(dāng)PT是一平面系數(shù)時(shí)，-PT也是該平面的系數(shù)，因此為了計(jì)算的需要，Roberts算法規(guī)定：對平面多面體內(nèi)部的任一點(diǎn)S0，要使得[S0]·[V]=[Q]=[q1,q2,q3,…,qn]式中的每一個(gè)分量qi都不小于零(i=1,2,…,n)。

適當(dāng)選取物體內(nèi)部一點(diǎn)S0，用以測試單調(diào)態(tài)平面系數(shù)的符號，使其滿足Roberts算法的規(guī)定，這是本算法最基本的一步。a1

a2

a3

…

an

b1

b2

b3

…

bn

c1

c2

c3

…

cn

d1

d2

d3

…

dn第三章70Roberts算法原理Roberts算法

平面系數(shù)的計(jì)算方法方法一：根據(jù)平面上的已知點(diǎn)，求解線性方程組。已知平面上不共線三點(diǎn)(x1,y1,z1)，(x2,y2,z2)，(x3,y3,z3)，得到規(guī)范方程組:

ax1+by1+cz1=-1 寫成矩陣形式為：

ax2+by2+cz2=-1 =

ax3+by3+cz3=-1[X][C]=[D]

解得平面方程系數(shù)為：

[C]=[X]-1[D]方法二：根據(jù)平面的法矢量和平面上一已知點(diǎn)，求得平面系數(shù)。已知平面的法矢量為：n=ai+bj+ck，其中i，j，k分別為x，y，z方向的單位矢量，且又已知平面上一點(diǎn)(x1,y1,z1)。則平面方程是：

ax+by+cz+d=0，其中

d=-(ax1+by1+cz1)x1y1z1

x2y2z2

x3y3z3a

b

c-1

-1

-1第三章71Roberts算法原理Roberts算法方法三：采用MartinNewell方法，即最佳逼近法，計(jì)算任何平面多邊形所在平面的精確方程或接近于平面的多邊形的最佳逼近平面方程。

假設(shè)給定n個(gè)點(diǎn)(xi,yi,zi)(i=1,2,…,n)，則平面系數(shù)可用于下式計(jì)算：

n

a=∑(yi-yj)(zi+zj)

i=1n

b=∑(zi-xj)(xi+xj)

i=n

c=∑(xi-xj)(yi+yj)

i=1

其中：若i≠n，則j=i+1，否則j=1。d可由下式求得：

d=-(ax1+by1+cz1)第三章72Roberts算法原理Roberts算法體矩陣的變換

在消隱算法執(zhí)行之前，為了得到從一指定的試點(diǎn)以給定的觀察方向來看所需要顯示的物體，常常先要對物體進(jìn)行三維坐標(biāo)變換。因此，在變換確定之后，或給定了變換矩陣[T]以后，需要對每一個(gè)物體的體矩陣[V]作一個(gè)相應(yīng)的變換，得到變換后的體矩陣[VT]。

同時(shí)，還要對物體的頂點(diǎn)齊次坐標(biāo)矩陣[B]作一個(gè)相應(yīng)的變換，得到變換后的頂點(diǎn)齊次坐標(biāo)矩陣[BT]。

有兩種常用的計(jì)算[VT]的方法。第三章73Roberts算法原理Roberts算法方法一：假設(shè)[B]與[BT]分別為在體矩陣變換前后的物體頂點(diǎn)齊次坐標(biāo)構(gòu)成的矩陣，則[BT]=[B][T]

因?yàn)橛衃X][C]=[D]，所以可得到該物體原各平面的方程為：[B][V]=[D]其中：[D]為零矩陣。

同樣，變換后的平面方程也可表示為：[BT][VT]=[D]

并且：[BT][VT]=[B][V]代入到[BT]=[B][T]，方程兩邊消去[B]并左乘[T]-1，得到：[VT]=[T]-1[V];所以，變換后的體矩陣是由原來的體矩陣左乘變換矩陣的逆矩陣而得到的。方法二：假設(shè)原先并未計(jì)算形體矩陣[V]，也不希望計(jì)算[T]的逆矩陣，則可光計(jì)算：[BT]=[B][T],然后用變換后的物體頂點(diǎn)坐標(biāo)[BT]，按照前面介紹的MartinNewell方法，直接計(jì)算變換后的體矩陣[VT]，兩種方法所得結(jié)果完全一致。Roberts算法原理第三章74自消隱方法:自消隱是對物體自身所遮擋的面(自隱面)和邊(自隱邊)的消除。對于不同的視點(diǎn)及視方向，既是對同一個(gè)物體來說，也會產(chǎn)生不同的自隱面和自隱邊。因此自隱面和自隱邊不僅取決于物體的形狀，而且與視點(diǎn)方向相關(guān)。

假設(shè)視點(diǎn)位于z的負(fù)無窮遠(yuǎn)處，視方向?yàn)閦軸的正向，即視方向朝z軸正向無窮遠(yuǎn)處，在齊次坐標(biāo)系中，該方向矢量為：[E]=[0,0,1,0]顯然，若視方向[E]和體矩陣[VT]的乘積中有負(fù)的元素，則[E]在這此元素對應(yīng)的面與形體相對的另一側(cè)，而這正說明這些面被物體自身所遮擋。所以利用[E]·[VT]=[w1,w2,…,wn](表示視線與表面內(nèi)法線矢量夾角關(guān)系)尋找所有wi＜0的i值，其對應(yīng)面即為自隱面，可被消除。Roberts算法

視方向朝向z軸負(fù)向無窮遠(yuǎn)處

視方向朝向z軸正向無窮遠(yuǎn)處

結(jié)果圖第三章75Roberts算法原理Roberts算法當(dāng)找到了所有的自隱面之后，就可以確定自隱線，自隱線的確定方法是：若相交的兩各平面都是自隱面的話，它們的相交邊線就是自隱線，可以消除，否則為物體的可見邊線。

在確定了自隱面和自隱線之后，該物體余下的邊線應(yīng)當(dāng)與其它物體一一比較，以確定他們是否為其他物體所遮擋。為了提高算法的執(zhí)行效率，應(yīng)先將一些很明顯由很容易確定的不必要的比較排除在外，常用的一些方法是最大最小測試法和邊框測試法等。

最大最小測試法是對要被顯示的每一個(gè)物體，以其最小Z值(即最靠近視點(diǎn)的點(diǎn))進(jìn)行排序，由大到小組成一個(gè)Z值的表，比較某一邊線，若它的最大Z值小于表中某一元素，則從該元素起及其以后的元素所對應(yīng)的物體均不可能遮擋該邊線，所以不用進(jìn)一步的比較。

邊框測試法是為較復(fù)雜物體加上如球或長方體之類的邊框，這樣只要能確定某些邊線完全處于這些框的上面、下面、左面、右面后前面時(shí)，邊框內(nèi)的物體就不會遮擋該邊線。Roberts算法原理第三章76最大最小測試法如下：

若物體1的最大Z值≤物體2的最小Z值,則物體1的優(yōu)先級為1,物體2的優(yōu)先級為2優(yōu)先級小的物體離視點(diǎn)距離較近優(yōu)先級小的物體可能遮擋優(yōu)先極大的物體優(yōu)先級小的物體先投影Roberts算法優(yōu)先級1優(yōu)先級2分割平面yzRoberts算法原理Roberts算法第三章77邊框測試法如下：

判斷下式：x_minp＞x_maxe

OR

x_mine＞x_maxpOR

y_minp＞y_maxeORy_mine＞y_maxp

若上式為真，邊與多邊形不相交；若上式為假，二邊框相交，但邊與多邊形可能相交，可能不相交，需進(jìn)行第二次邊框測試。

框第二次邊測試：把邊的邊框和多邊形的每條邊的邊框進(jìn)行比較，進(jìn)行交點(diǎn)測試。

交點(diǎn)測試：對求出的交點(diǎn)，判別其是否同時(shí)在邊或多邊形邊上(交點(diǎn)的x,y值是否在邊的范圍內(nèi))若是，邊與多邊形的邊相交若不是，邊與多邊形的邊不相(x_maxp,

y_maxp)(x_maxe,

y_maxe)(x_mine,

y_mine)(x_minp,

y_minp)Roberts算法原理Roberts算法第三章78

邊線與物體的比較方法:完成上述工作

后，還有一定數(shù)量的邊要通過與其它

物體的比較后方能確定其可見性。假設(shè)

考慮邊線P1P2的可見性，被比較的物體

體矩陣為[VT]。采用直線的參數(shù)表示形式：

P(t)=P1+(P2-P1)t0≤t≤1或v=s+dt

0≤t≤1

其中：v是邊線上點(diǎn)的位置矢量，s是起始點(diǎn)，d為直線的方向。再構(gòu)造由P1P2上一點(diǎn)至視點(diǎn)的直線，其參數(shù)表示形式為：Q(α,t)=u=v+gα=s+dt+gα(0≤t≤1,α＞0)

其中：g=[0,0,-1,0],與視線方向[E]=[0,0,1,0]相反，且α與t的意義相同。給定一個(gè)t值，對應(yīng)邊線P1P2上的一點(diǎn)P(t)，同樣對于給定一個(gè)α值，則決定了從該點(diǎn)至視點(diǎn)線段上的一點(diǎn)。所以Q(α,t)可以看作是定義了這平面π上的一點(diǎn)集,給定α和t，就確定了這個(gè)平面上的一點(diǎn)。α總是取正值，這是因?yàn)橹挥衅矫娴倪@一區(qū)域才能包含遮擋上述邊線的物體。如果物體于平面π的交集不定，且落在點(diǎn)集Q(α,t)中，則這個(gè)物體部分或全部地遮擋邊線P1P2。否則，P1P2就不會被這個(gè)物體所遮擋。p1p2πg(shù)ERoberts算法原理第三章79現(xiàn)在把邊線的對于給定物體的可見性問題，轉(zhuǎn)為物體與整個(gè)點(diǎn)集之交是否為空集的問題。因?yàn)榍懊嬉呀?jīng)規(guī)定：物體中的點(diǎn)與體矩陣的乘積所產(chǎn)生的向量中所有元素均為非負(fù)數(shù)。所以，只H=u·[VT]=s·[VT]+t·d[VT]+α·g[VT]≥0

(0≤t≤1，α≥0)

對于物體中的每個(gè)面j=1,2,…n，使得hj=pj+tqj+αwj≥0

(0≤t≤1，α≥0)

其中pj，qj，wj，hj分別為向量P，Q，W，H的分量：P=(p1,p2,…,pn)=s·[VT]

Q=(q1,q2,…,qn)=d·[VT]

W=(w1,w2,…,wn)=g·[VT]

H=(h1,h2,…,hn)=Q(α,t)·[VT]Roberts算法第三章79Roberts算法原理Roberts算法第三章80于是，可見與不可見的臨界條件是hj=0。

當(dāng)hj=0時(shí)，該點(diǎn)恰好位于對應(yīng)的平面上。若對物體的每一平面取hj=0，可得有關(guān)α和t的聯(lián)立方程組。

為了求解這個(gè)方程組，可將其中的方程兩兩聯(lián)立，得到所有可能的α和t值?？赡艿慕獾目倲?shù)為n(n-1)/2。然后在(0≤t≤1,α≥0)范圍內(nèi)求出t的最小值tmin和最大值tmax和相應(yīng)的α值。

對于tmin≤t≤tmax,必須α≥0，使得Q(α,t)落在物體中，所有這樣的t值是邊線上被遮擋的點(diǎn)，對于那些α=0的解，說明邊線真正貫穿了物體。要保存這些貫穿點(diǎn)，然后連接這些貫穿點(diǎn)，得到的貫穿線再與其它物體相比較，其中可見部分就是可見貫穿線。

可見貫穿線若下圖所示:

紅色處為貫穿點(diǎn)的位置紫色為可見貫穿線，黃色為不可見貫穿線(不可見貫穿線僅列出幾條)第三章84Roberts算法Roberts算法原理

上述方法的計(jì)算量很大，下面介紹一種判別完全可見線段的方法，可節(jié)省計(jì)算量。該方法的基本思想是判斷一線段的兩端點(diǎn)是否位于視點(diǎn)和一可見面之間，若是，則完全可見。

根據(jù)u=s+dt+gα(0≤t≤1,α＞0)當(dāng)α=0時(shí)，u表示該邊線本身，

此時(shí)當(dāng)t=0和t=1是，分別表示該邊線的兩個(gè)端點(diǎn)，則：hj=u·[VT]=pj+qj·t+w·α

當(dāng)α=0和t=1時(shí)，pj+qj表示該邊線另一端點(diǎn)和物體上j個(gè)平面的點(diǎn)積。

因?yàn)閣j≤0表示物體的第j個(gè)平面可見，所以，

如果wj≤0和pj+qj≤0，則表示該端點(diǎn)位于可見面上或位于視點(diǎn)與可見面之間。

綜上，在物體中只要存在一個(gè)j，使得wj≤0&pj≤0&pj+qj≤0成立，則該邊線完全可見。Roberts算法第三章84Roberts算法原理

邊與多邊體相交情況有以下幾種：邊在多邊體的內(nèi)部邊的一個(gè)端點(diǎn)邊完全在多變邊貫穿多變體 在多邊體的內(nèi)部體的外部 第三章84Roberts算法Roberts算法描述完整的Roberts算法分為三個(gè)部分：對每一個(gè)物體進(jìn)行分析，消去自隱面和自隱線；對余留下的邊與其它所有物體一一比較以確定被其他物體所遮擋的部分；確定物體見可能由于相互穿透而增加的貫穿線是否可見。假定物體是由面構(gòu)成的，而面是由邊構(gòu)成，邊則由頂點(diǎn)構(gòu)成。所有頂點(diǎn)、棱邊、面都是已知的。

Roberts算法第三章82Roberts算法描述（續(xù)）/*消除自隱線和自隱面*/while對于要被顯示的每一個(gè)物體do

begin

物體的頂點(diǎn)表構(gòu)造各表面多邊形及棱邊

計(jì)算物體上每一多邊形表面的平面方程

/*檢查平面方程的符號*/

取物體各頂點(diǎn)的平均值，作為一個(gè)物體內(nèi)部點(diǎn)

計(jì)算該物體內(nèi)部點(diǎn)與平面方程的點(diǎn)積

if點(diǎn)積＜0then改變平面方程系數(shù)的符號

建立物體的體矩陣體矩陣左乘包括透視變換在內(nèi)的視變換的逆矩陣計(jì)算并保存變換后物體包圍盒值xmin,xmax,ymin,ymax,zmin,zmaxRoberts算法第三章83Roberts算法描述（續(xù)）/*判斷自消隱面和線*/

取位于負(fù)無窮處的試驗(yàn)點(diǎn)和變換后體矩陣的點(diǎn)積

if點(diǎn)積＜0then標(biāo)志相應(yīng)平面為隱藏面

消除相應(yīng)與該平面的多邊形(也消除兩隱藏面相交形成的隱藏線)end

/*消除每一物體被其他物體遮擋面產(chǎn)生的隱藏線*/if要顯示的物體只有一個(gè)thengoto結(jié)束

/*建立物體的優(yōu)先級*/while對于優(yōu)先表上的每一個(gè)物體do

begin

/*檢查每一非自隱線的棱邊是否被其他物體遮擋。含被檢查棱邊的物體稱試驗(yàn)體，所有用來判斷遮擋關(guān)系的其他物體稱檢查體。試驗(yàn)體通常只需對比它優(yōu)先級低的檢查體進(jìn)行遮擋檢查*/Roberts算法第三章84/*對試驗(yàn)體和檢查體進(jìn)行包圍盒試驗(yàn)*/

ifxmin(檢查體)＞xmax(試驗(yàn)體)或xmax(檢查體)＜xmin(試驗(yàn)體)或 ymin(檢查體)＞ymax

(試驗(yàn)體) 或ymax

(檢查體)＜ymin(試驗(yàn)體) then檢查體不可能遮擋試驗(yàn)體任何棱邊goto14

/*進(jìn)行初步的貫穿檢查判斷試驗(yàn)體是否貫穿檢查體而部分的被遮擋*/

/*比較試驗(yàn)體上的最小z值和檢查體的最大z值*/

ifzmin

(試驗(yàn)體)＞zmax

(檢查體)then試驗(yàn)體和檢查體不可能形成 貫穿goto14

/*檢查是否存在可見性貫穿*/

ifzmin

(試驗(yàn)體)＜zmax

(檢查體)then檢查體可能貫穿試驗(yàn)體的前 面，建立可見性貫穿標(biāo)志goto20

ifxmax

(試驗(yàn)體)＞xmin

(檢查體)或xmin

(試驗(yàn)體)＜xmax

(檢查體) then檢查體可能貫穿試驗(yàn)體的側(cè)面，建立可見性貫穿標(biāo)志 goto20Roberts算法描述（續(xù)）Roberts算法第三章85Roberts算法描述（續(xù)）

ifymax

(試驗(yàn)體)＞ymin

(檢查體)或ymin

(試驗(yàn)體)＜ymax

(檢查體) then檢查體可能貫穿試驗(yàn)體的底面或頂面，建立可見性貫穿 標(biāo)志goto20

if可見性貫穿標(biāo)志非空，then檢查體記入貫穿表

/*進(jìn)行試驗(yàn)體棱邊檢查*/

while對于試驗(yàn)體中每一條棱邊do

begin

計(jì)算試驗(yàn)體棱邊的s和d

計(jì)算檢查體的每一表面的p,q,w

/*檢查試驗(yàn)體棱邊是否完全可見*/

if完全可見thengoto21

計(jì)算聯(lián)立的方程組hj=0的解

while對于每一組(α,t)解doRoberts算法第三章86Roberts算法描述（續(xù)） begin

if0≤t≤1&α≥0&hj＞0(j=1,2,…,n)then計(jì)算tmin和tmax

if(α=0)

then計(jì)算和保存貫穿點(diǎn)

end

計(jì)算和保存棱邊上的可見段

end

/*決定貫穿體之間的可見相貫線*/

if可見性貫穿標(biāo)志為空thengoto32

if無貫穿點(diǎn)存在thengoto32

else將兩貫穿提上的全部貫穿注意連接，構(gòu)成可能的相貫邊； 對兩個(gè)貫穿體逐一檢查每一相貫邊的可見性；對其它物體，檢 查余留下的相貫邊的可見性并保存其可見段

顯示剩下棱邊上的可見段

endendofalgorithm第三章87Roberts算法分析Roberts算法Roberts消隱算法是在圖像空間實(shí)現(xiàn)的消隱算法，數(shù)學(xué)處理嚴(yán)謹(jǐn)，計(jì)算量甚大。

Roberts算法要求所有被顯示的物體都是凸的，因此對凹體要先分割成許多個(gè)凸體的組合。

由于Roberts算法的計(jì)算量隨著被顯示物體數(shù)的平方遞增以及人們對光柵掃描顯示的興趣與日俱增，使得Roberts算法大為遜色。

但Roberts算法數(shù)學(xué)處理簡單、精確、適用性強(qiáng)，在結(jié)合一些使用的技巧，使該算法的計(jì)算量幾乎只與顯示物體個(gè)數(shù)呈線性增長關(guān)系。第三章63三維圖形3.7

消隱

一、消隱的考慮二、Roberts算法三、Warnock算法四、表優(yōu)先級算法五、Z緩沖區(qū)算法六、光線跟蹤算法七、掃描線算法Warnock算法原理Warnock算法第三章89考慮圖象空間中的一個(gè)窗口，判定窗口是否為空,或者該窗口所包含的畫面足夠簡單可以立即顯示；否則，分割該窗口，直到子窗口內(nèi)所包含的畫面相當(dāng)簡單以致可以立即顯

示或者其尺寸已達(dá)到給定的分辨率為止。

這里稱畫面足夠簡單的條件：窗口中僅包含一個(gè)多邊形；窗口與一個(gè)多邊形相交，且窗口內(nèi)無其他多邊形；窗口為一個(gè)多邊形所包圍且窗口內(nèi)無其他多邊形；窗口至少為一個(gè)多邊形所包圍且此多邊形離視點(diǎn)最近。多邊形與窗口之間的關(guān)系:zminzmax第三章90Warnock算法原理Warnock算法分為5部分：控制程序：控制檢測窗口，當(dāng)檢測失敗時(shí)，繼續(xù)分割窗口，保證整個(gè)屏幕都被檢測到。檢查程序：檢查全部對象的所有多邊形，將它們分成分離、包圍、內(nèi)含和相交多邊形，并建立3個(gè)表：包圍多邊形表，分離多邊形表，相交及內(nèi)含多邊形表，供分析程序進(jìn)一步處理。分析程序：分析檢查程序提供的信息，分析結(jié)果：畫面足夠簡單，調(diào)用計(jì)