1、本 章 重 點(diǎn),9-1 3D坐標(biāo)系 9-2 坐標(biāo)矩陣 9-3 投影轉(zhuǎn)換 9-4 裁剪 9-5 隱藏面消除,9-1 3D坐標(biāo)系,坐標(biāo)轉(zhuǎn)換的作用是用來產(chǎn)生對(duì)象讓我們可以看到，其中不同的坐標(biāo)系統(tǒng)所呈現(xiàn)出來的方式會(huì)有所不同，如同我們以不同的角度去觀看一個(gè)特定的目標(biāo)，以不同角度所看到的對(duì)象顯示效果會(huì)有所不同。,9.1.1 坐標(biāo)轉(zhuǎn)換,坐標(biāo)系統(tǒng)必須要有一個(gè)基本的原點(diǎn)位置，從原點(diǎn)再延伸出去兩個(gè)或三個(gè)坐標(biāo)軸，形成一個(gè)特定的空間，這個(gè)空間即是我們所謂的2D空間或3D空間。,如果在空間中形成了兩個(gè)以上的坐標(biāo)系統(tǒng)，我們就必須要使用其中的一個(gè)坐標(biāo)系統(tǒng)來描述其它不同的坐標(biāo)系統(tǒng)，這些不同的坐標(biāo)系統(tǒng)必須要經(jīng)過一些特殊的轉(zhuǎn)換才

2、能讓這個(gè)坐標(biāo)系統(tǒng)所接受，而這種轉(zhuǎn)換的過程我們就稱為坐標(biāo)轉(zhuǎn)換。,9.1.2 Model坐標(biāo)系統(tǒng),即是物體本身中的坐標(biāo)環(huán)境，物體本身也有一個(gè)原點(diǎn)坐標(biāo)，而物體其它的參考頂點(diǎn)是由原點(diǎn)所衍生出來的，如下圖所示：,9.1.3 World坐標(biāo)系統(tǒng),在3D的世界里，有幾個(gè)目標(biāo)物體就會(huì)有幾個(gè)Model坐標(biāo)系統(tǒng)，而這些Model坐標(biāo)又不能表示自己在3D世界里的真正位置，所以必須再定義出另外一個(gè)可供3D世界里的物體參考之坐標(biāo)系統(tǒng)，并且使得所有的物體可以正確地被擺放自己應(yīng)該的位置坐標(biāo)上，這種另外再定義出來的坐標(biāo)系統(tǒng)則稱為World坐標(biāo)系統(tǒng)。,9.1.4 View坐標(biāo)系統(tǒng),當(dāng)我們有了物體本身的Model坐標(biāo)系統(tǒng)與能夠表

3、現(xiàn)物體在3D世界的位置坐標(biāo)之World坐標(biāo)系統(tǒng)，接下來必須要有一個(gè)觀看上述兩者的坐標(biāo)系統(tǒng)，這樣屏幕的顯示才會(huì)有依據(jù)，而這個(gè)可以觀看的坐標(biāo)系統(tǒng)我們稱為View坐標(biāo)系統(tǒng)。,9.1.5 坐標(biāo)轉(zhuǎn)換,在3D世界中，坐標(biāo)轉(zhuǎn)換過程是相當(dāng)復(fù)雜的，它必須經(jīng)過4個(gè)不同的轉(zhuǎn)換步驟，最后才能顯示在屏幕上，這才是我們所要的畫面。流程：,Model坐標(biāo)系統(tǒng),World坐標(biāo)系統(tǒng),View坐標(biāo)系統(tǒng),投影空間坐標(biāo),Projection transform,最后的二維坐標(biāo),Dispaly,Viewport參數(shù),9-2 坐標(biāo)矩陣,矩陣的表示方式是以4*4矩陣來呈現(xiàn)的，因?yàn)檫@種矩陣的表現(xiàn)方式可以用來表示平移、旋轉(zhuǎn)及縮放等三種轉(zhuǎn)換功能

4、，而這就已經(jīng)包含了3D世界的轉(zhuǎn)換型式了。這一種矩陣的運(yùn)算對(duì)象及所產(chǎn)生的結(jié)果坐標(biāo)，我們稱之為齊次坐標(biāo)(Homogeneous Coordinate)。,9.2.1 齊次坐標(biāo),齊次坐標(biāo)具有四個(gè)不同的元素，簡稱四元素，其表示法為（x,y,z,w），如果將齊次坐標(biāo)表示成3D坐標(biāo)的話，其表示法則為（x/w,y/w,z/w）。通常w元素都會(huì)被設(shè)成1。 W用意是用來表示一個(gè)比例因子。,9.2.2 矩陣平移（Translation）,即是物體在3D世界里向著某一個(gè)向量方向移動(dòng)，如下圖,矩陣平移運(yùn)算的表示法如下列所示：,9.2.3 矩陣旋轉(zhuǎn)（Rotation）,定義是3D世界里的某一個(gè)物體繞著一個(gè)特定的坐標(biāo)軸旋

5、轉(zhuǎn)，如下圖所示：,繞著x軸旋轉(zhuǎn),繞著y軸旋轉(zhuǎn),繞著z軸旋轉(zhuǎn),X,Y,(x,y),a,(x,y),Y=r*sin（a+ ） =r*sina*cos +r*sina*cos* =x*cos +y*cos ,9.2.4 矩陣縮放（Scaling）,即是物體沿著某一個(gè)軸進(jìn)行一定比例縮放的運(yùn)算。如下圖所示：,物體向著X軸放大,矩陣的表示法如下列所示：,希臘字母 伊塔,9.2.5 矩陣的結(jié)合律,平移矩陣為A、旋轉(zhuǎn)矩陣為B、縮放矩陣為C，而原來的頂點(diǎn)坐標(biāo)為K、最后得到的頂點(diǎn)坐標(biāo)為K，其矩陣相乘的公式如下列所示：,K=CBAK,其實(shí)我們可以將這種特定的矩陣相乘過程簡化，因?yàn)榫仃囅喑说倪\(yùn)算是可以符合數(shù)學(xué)上所說的

6、結(jié)合律，也就是將A、B、C三個(gè)矩陣先結(jié)合成另一個(gè)矩陣，如下：,=CBA K=K,9.2.6 Direct3D矩陣,在Direct3D定義里，矩陣被宣告成一個(gè)名為D3DMATRIX的數(shù)據(jù)結(jié)構(gòu)，如下：,typedef struct _D3DMATRIX ,union ,struct ,float _11, _12, _13, _14;,float _21, _22, _23, _24;,float _31, _32, _33, _34;,float _41, _42, _43, _44;,;,float m44;,;, D3DMATRIX;,#define D3D_OVERLOADS #inclu

7、de D3DMATRIX mat; /下面三種表示方式的意思都是一樣的 mat._13 = 0.8f; mat13 = 0.8f; mat(1,3) = 0.8f;,索引值從“0”開始，先row，后col,如果我們要建立一個(gè)平移的矩陣，其表示法如下圖所示：,在程序代碼里，我們就可以將它編寫成如下列所示：,D3DMATRIX mat = 1, 0, 0, D3DVAL(4.0) 0, 1, 0, D3DVAL(8.0) 0, 0, 1, D3DVAL(16.0) 0, 0, 0, 1 ;,9.2.7 向量表示法,在Direct3D定義里，向量被聲明成一個(gè)名為D3DVECTOR的數(shù)據(jù)結(jié)構(gòu)，如下列所

8、示：,typedef struct _D3DVECTOR ,float x;,float y;,float z; D3DVECTOR;,矩陣相乘,/將矩陣pM1與矩陣pM2相乘之后的結(jié)果傳給矩陣pOut,D3DXMATRIX* D3DXMatrixMultiply(,D3DXMATRIX* pOut,CONST D3DXMATRIX* pM1,CONST D3DXMATRIX* pM2 );,基本的矩陣及向量運(yùn)算函數(shù),向量相乘,/將向量pV1與向量pV2相乘之后的結(jié)果傳給向量pOut,D3DXVECTOR3* D3DXVec3Cross(,D3DXVECTOR3* pOut,CONST D3D

9、XVECTOR3* pV1,CONST D3DXVECTOR3* pV2 );,基本的矩陣及向量運(yùn)算函數(shù),兩個(gè)向量進(jìn)行dot product的運(yùn)算,FLOAT D3DXVec3Dot(,CONST D3DXVECTOR3* pV1,CONST D3DXVECTOR3* pV2 );,基本的矩陣及向量運(yùn)算函數(shù),計(jì)算向量的長度,FLOAT D3DXVec3Length(,CONST D3DXVECTOR3* pV );,基本的矩陣及向量運(yùn)算函數(shù),計(jì)算向量的單位向量,D3DXVECTOR3* D3DXVec3Normalize(,D3DXVECTOR3* pOut,CONST D3DXVECTOR3

10、* pV );,基本的矩陣及向量運(yùn)算函數(shù),向量相加,D3DXVECTOR3* D3DXVec3Add(,D3DXVECTOR3* pOut,CONST D3DXVECTOR3* pV1,CONST D3DXVECTOR3* pV2 );,基本的矩陣及向量運(yùn)算函數(shù),9-3 投影轉(zhuǎn)換,將三維的坐標(biāo)系統(tǒng)轉(zhuǎn)換成二維的坐標(biāo)，并將3D世界里的坐標(biāo)單位映像到2D屏幕的坐標(biāo)單位上，才能在計(jì)算機(jī)屏幕上看到所謂的3D世界，而這整個(gè)轉(zhuǎn)換的過程我們稱之為投影。,9.3.1 平行投影,當(dāng)我們省略掉三維空間里的一維元素之后，我們就可以得到了一個(gè)平行投影的圖形坐標(biāo)，在這個(gè)時(shí)候，三維空間中的所有頂點(diǎn)都會(huì)從三維空間映像到2D平

11、面的并行線上，因此我們就稱這種方式為平行投影。,平行投影,我們可以在投影線與投影面交叉角度的基礎(chǔ)上更進(jìn)一步地細(xì)分平行投影。如果交叉的角度是直角的話，我們則稱之為正交投影（orthographic）；不是直角的話，我們則稱為傾斜投影（oblique）。,9.3.2 透視投影,透視投影所建立出來的對(duì)象投影圖像之大小必須依賴對(duì)象與觀察者的距離。,原點(diǎn)與圖像上的頂點(diǎn)相聯(lián)系之關(guān)系。如下圖所示：,無深度投影,具深度投影,焦點(diǎn)距離越小則視角寬度越廣，而焦點(diǎn)距離越大則視角寬度越窄。,9-4 裁剪,2D裁剪 裁剪是對(duì)于某種圖形做出修剪的動(dòng)作，其目的是為了讓看不見的頂點(diǎn)不加以描繪，以提升執(zhí)行的速度。,第三種剪裁法

12、,第二種剪裁法,第一種剪裁法,線段的裁剪,線段裁剪的方法可以分析圖形的相對(duì)約束位置，并且找出符合這一點(diǎn)的圖形部分。在線段裁剪的情況下，它需要找出其交叉點(diǎn)或線段與裁剪邊界的交叉點(diǎn)，通常不是直接就能夠把這種交叉發(fā)生的地方看得一清二楚的。如下圖所示：,在光柵處理階段之前，先進(jìn)行裁剪處理，適合處理簡單的圖形單位。（如多邊形） 在光柵處理階段同時(shí)進(jìn)行，適合于復(fù)雜圖形。 當(dāng)裁剪區(qū)域中幾何結(jié)構(gòu)比較復(fù)雜時(shí)，選擇較大的Buffer光柵圖形。然后在Buffer中選擇在該復(fù)雜裁剪區(qū)域內(nèi)部的圖形。,光柵處理：投影轉(zhuǎn)換把物體圖形坐標(biāo)從3D空間映射到屏幕的2D空間，這些圖形必須在2D空間中被繪制，使觀察者可見。既然我們考

13、慮的是由一系列整齊地鑲嵌的小方塊組成的光柵圖形，因此我們要確定這種幾何像素的模擬描述要如何能夠被正確地轉(zhuǎn)換成一系列的離散圖形，而這種過程我們稱之為“光柵處理”（rasterization）,9.4.2 點(diǎn)的裁剪,點(diǎn)的裁剪可以利用這4個(gè)有限線段的約束來檢查點(diǎn)的坐標(biāo)是否應(yīng)該要被裁剪。,9.4.3 線段的裁剪,我們可以將線段的裁剪擴(kuò)展到上述方法，然而增加內(nèi)循環(huán)的復(fù)雜性。 這種線段裁剪方法可以分析圖形的相對(duì)約束位置，并且找出符合這一點(diǎn)的圖形部分。在線段裁剪的情況下，它需要找出交叉點(diǎn)或線段與裁剪邊界的交叉點(diǎn)，通常不是直接就能夠把這種交叉的地方看清楚。如下圖：,剪裁線,剪裁線,剪裁線,剪裁線,區(qū)域外編碼（

14、region out code）,第一步，區(qū)域編碼 延長窗口邊界，將平面分成9個(gè)區(qū)域，每個(gè)區(qū)域用4位二進(jìn)制代碼表示，稱為區(qū)域碼。其作用是識(shí)別點(diǎn)相對(duì)于裁剪窗口邊界的位置。,約定4位碼中最右邊一位為第1位，則編碼規(guī)則如下：,1000,0000,1001,1010,0001,0010,0101,0100,0110,left,right,above,below,第二步 ，建立線段端點(diǎn)的區(qū)域編碼。,設(shè)(x,y)是線段端點(diǎn)的坐標(biāo)，則第1位取,的符號(hào)位。,第2位取,的符號(hào)位。,第3位取,的符號(hào)位。,第4位取,的符號(hào)位。,第三步，判斷線段與窗口間的位置關(guān)系。 （1）若線段兩端點(diǎn)的編碼均為“ 0000”, 則線

15、段全部位于窗口內(nèi)。 （2）若線段兩端點(diǎn)編碼的邏輯“與”不是0000，則線段必位于窗口外。,（3）若根據(jù)（1）、（2）不能直接判定線段在窗口內(nèi)或窗口外，我們需要計(jì)算線段與窗口邊界的交。由下圖可知，這些線段可能穿入窗口的內(nèi)部，也可能不穿過窗口的內(nèi)部。,P1,P1,P3,P4,P2,P2,P3,這類線段的處理過程： 將線段的位于窗口外端點(diǎn)與窗口邊界進(jìn)行比較，以確定線段的多大部分被舍棄。對(duì)剩余的部分線段繼續(xù)按（1）、（2）和（3）進(jìn)行處理。直到線段完全在窗口內(nèi)或完全在窗口外為止。,具體操作： （1）可以按照left,right, bottom, top的順序檢查線段端點(diǎn)與窗口邊界之間的關(guān)系。 現(xiàn)通過例

16、子對(duì)該算法進(jìn)行說明?？紤]線段P1P2的端點(diǎn)P1,依次檢查P1與窗口的左、右和下邊界間的位置關(guān)系，發(fā)現(xiàn)P1點(diǎn)在裁剪窗口的下面。于是求出該線段與窗口底邊界的交點(diǎn)P1。這時(shí)，線段變?yōu)镻1P2。由于P2在裁剪窗口之外，通過檢查該端點(diǎn)與窗口邊界的關(guān)系發(fā)現(xiàn)，它在窗口的左側(cè)。可以計(jì)算出線段P1P2與窗口左邊界的交點(diǎn)為P2，該點(diǎn)位于窗口的上部，因此最后的交點(diǎn)為P2。線段P1P2保留。,P1,P1,P3,P4,P2,P2,P3,P2,或,或,類似地，線段與水平邊界交點(diǎn)的x坐標(biāo)為：,其中，,（2） 線段與邊界的求交算法 一般地，由(x1, y1)到(x2,y2)的截距式表示可求出該線段與垂直邊界交點(diǎn)的y坐標(biāo)為：,

17、剪裁線,Y1=y2-y（x2-x1）/ x,對(duì)于圖形的應(yīng)用而言，不涉及到乘法或除法的方法通?？梢栽黾舆\(yùn)算速度，在裁剪這種情況中，我們可以使用“二元搜尋”這種方法來運(yùn)算。,第一次運(yùn)算的終點(diǎn),第二次運(yùn)算的終點(diǎn),第三次運(yùn)算的終點(diǎn),9.4.4 多邊形的裁剪,在矩形屏幕情形下，我們將每一個(gè)裁剪邊緣計(jì)算裁剪例程一次，最后獲得符合所有強(qiáng)制標(biāo)準(zhǔn)的多邊形。如下圖所示：,原來線段,剪裁后線段,3D裁剪,9-5隱藏面消除,背面剔除(back culling)算法 許多三維物體中，它們所占據(jù)的空間都被一些連續(xù)的表面所包圍著。當(dāng)我們觀察這些物體的時(shí)候，只能看到這些包圍表面中的正面部分，背面則無法看到。背面剔除算法就是將

18、這些我們看不到的背面多邊形去除掉。如下圖所示：,我們只能看見三為物體中的其中一面而已,凸面體,凹面體,這個(gè)面被其它面擋住了,對(duì)于透視投影而言，投影線會(huì)相交在觀察者的眼中，它們的方向是不同的。我們可以在世界或觀察空間中的任意一點(diǎn)上構(gòu)造一個(gè)指向觀察者眼睛的向量，并且使它指向該點(diǎn)的方向，如此一來，我們就得到了這一點(diǎn)的觀察方向了。如下圖所示：,9.5.2 排序,另一種方法也可以用來剔除這些看不到的頂點(diǎn)，其方法可以充分的利用圖形硬件的緩沖儲(chǔ)存結(jié)構(gòu)來加速其運(yùn)算。不管場景中的多邊形有沒有擋住其它的多邊形，只要按照從后面到前面的順序光柵化圖形就可以正確的顯示所有可見的圖形了，也就是將離觀察者最近的一個(gè)多邊形最

19、后進(jìn)行光柵化處理。這種方法就是我們稱它為畫家算法。,從前邊節(jié)已經(jīng)看到，一般多邊形模型隱藏面消除的代價(jià)極高，然而在大多數(shù)情況下，我們要處理的對(duì)象有一些特殊的屬性，利用這些屬性可以減輕隱藏面的消除工作量。例如在以“高度值運(yùn)算“來處理表面的地形曲面時(shí)。就很容易地獲得多邊形視點(diǎn)從前到后的頂點(diǎn)順序。 由于這種表面方法具有矩形自然的屬性，地形就可以被分割成許多正方形的單元格。,9.5.3 八叉樹,當(dāng)觀察者在一些單元邊界內(nèi)位于虛擬地形表面上或表面的上方。我們能夠把整個(gè)的地形分割為四個(gè)規(guī)則的子地形，如下圖。,我們可以將地形單元的光柵處理順序編列成如下所示：,第一次：1、2、3、4。第二次：5、6、7、8、9、

20、10。第三次：11、12、13、14、15、16;第四次：17、18、19、20、21、22、23、24、25。,光柵處理的順序?qū)?huì)依據(jù)觀察者在場景中角度的不同而有所改變。如下圖所示：,有這種規(guī)律的特性，我們可以將它作為由后到前尋找地形順序的依據(jù)，而這種特性就可以使用“八叉樹”的存儲(chǔ)規(guī)則，或者也可以用在空間占有的矩形來描述映射。 在這種情況下，我們利用類似高度場的方法，擴(kuò)展成為處理三維頂點(diǎn)而不是二維頂點(diǎn)。,八叉樹的處理規(guī)則就是利用遞歸結(jié)構(gòu)的方式來進(jìn)行的，在每個(gè)細(xì)分的層次上有著同樣規(guī)則的屬性。因此，在每個(gè)層次上我們可以利用同樣的編列順序，以獲得整個(gè)結(jié)構(gòu)元素由后到前的順序依據(jù)。,9.5.4 二元空

21、間分割樹,二元空間分割樹，Binary Space Partitioning Tree是一種空間分割的方法，簡稱BSP Tree。 BSP Tree在一開始將資料文件讀進(jìn)來的時(shí)候，就將整個(gè)數(shù)據(jù)文件中的數(shù)據(jù)（即是墻的數(shù)值）先建成一個(gè)二元樹的數(shù)據(jù)結(jié)構(gòu)。如下圖所示：,Front,back,Node中的數(shù)據(jù)代表一面墻,當(dāng)?shù)匦螖?shù)據(jù)被讀進(jìn)來時(shí)，BSP Tree會(huì)同時(shí)被建立（只一次）,當(dāng)視點(diǎn)開始移動(dòng)時(shí)，平面景象就必須被重新繪制。而重繪就是以視點(diǎn)為基礎(chǔ)，對(duì)此BSP Tree加以分析，只要在BSP Tree中，且位于此視點(diǎn)前方，它就會(huì)被存放在一個(gè)串行當(dāng)中，最后我們只要按照串行的順序逐個(gè)地將它們繪制在平面上就可以

22、了。 另一種方法：利用深度測試來顯示室內(nèi)環(huán)境及場景。,A區(qū)域顯示在X多邊形上,B區(qū)域顯示在Y多邊形上,此圖的現(xiàn)象在現(xiàn)實(shí)中視不可能存在的,使用OpenGL或Direct3D的函數(shù)庫去顯示此多邊形，它們就會(huì)自動(dòng)做深度探測（Z-Buffer），但是效率極差，這就是要使用二元空間分割樹的原因。 二元空間分割樹可以利用節(jié)點(diǎn)（Node）來快速和有效的排序多邊形，而且在計(jì)算機(jī)運(yùn)行時(shí)，我們又可以簡單的了解camera到最遠(yuǎn)多邊形之間的關(guān)系。,需要深度測試,當(dāng)二元空間分割樹建立時(shí)，必須完成下面幾項(xiàng)任務(wù)：,從函數(shù)中選擇一個(gè)多邊形。 通過平面方程（Ax+Bx+Cx+D=0）轉(zhuǎn)換多邊形為平面數(shù)據(jù)。 通過函數(shù)分類所有的

23、多邊形（前、后、重疊、穿越）。 分割跨越平面的多邊形。 如果任何一個(gè)多邊形在平面的前方，回到（1）并處理這些多邊形。 如果任何一個(gè)多邊形在平面的后方，回到（1）并處理這些多邊形。 在目前的節(jié)點(diǎn)中加入與平面重疊的多邊形與串中。,詳細(xì)的二元素,再利用D平面為主Node來做分割的動(dòng)作。在分類和切割后的結(jié)果如下圖所示：,現(xiàn)在的二元空間分割樹看起來就如下圖：,再繼續(xù)分割上述二元樹結(jié)構(gòu)的話，二元樹結(jié)構(gòu)就會(huì)變成如下圖所示：,當(dāng)映射多邊形時(shí)，我們可以利用camera的位置與每個(gè)平面比較，然后再以距離為基本順序原則。 一開始，基本節(jié)點(diǎn)是B多邊形，接著執(zhí)行下面步驟：,(1)求出平面與camera之間的距離。 (2)如果距離大于0： 移向后面節(jié)點(diǎn)并回到步驟（1）。 顯示目前節(jié)點(diǎn)內(nèi)的多邊形。 移向前面節(jié)點(diǎn)并回到步驟（1） (3)如果（2）是錯(cuò)誤的： 移向前面節(jié)點(diǎn)并回到步驟（1） 顯示目前節(jié)點(diǎn)內(nèi)的多邊形。 移向后面節(jié)點(diǎn)并回到步驟（1）,完成上面步驟，繪