基于DSP的3D圖形芯片的算法原理分析

三維圖形處理已成了熱門話題，一些報(bào)刊雜志連篇累牘地刊出有關(guān)文章，但綜觀其內(nèi)容，似缺乏系統(tǒng)性和深度。在本期每月專題中，董社勤、石教英和陳爽三位專家的二篇文章，對(duì)圖形學(xué)的基本原理和圖形芯片結(jié)構(gòu)做了深入淺出的介紹，可為你今后理解3D圖形處理和圖形硬件打下基礎(chǔ)。建議你認(rèn)真閱讀，一遍讀不懂再讀一遍，相信會(huì)有收獲。

一、引言

3D芯片的處理對(duì)象是多邊形表示的物體。用多邊形表示物體有兩個(gè)優(yōu)點(diǎn)：首先是直接（盡管繁瑣），多邊形表示的物體其表面的分段線性特征除輪廓外可以通過明暗處理(shading)技術(shù)消除；其次是僅存儲(chǔ)多邊形頂點(diǎn)的幾何信息，多邊形內(nèi)部每個(gè)象素的明暗顏色計(jì)算所需的信息由這些頂點(diǎn)信息插值而來，這正是易于用圖形硬件支持的快速明暗處理技術(shù)。支持多邊形繪制的圖形硬件同樣也可以繪制由雙三次曲面片表示的物體，通過對(duì)這種物體的表面進(jìn)行三角剖分，用逼近的三角形網(wǎng)格代替原物體的曲面表示就可以做到這一點(diǎn)。當(dāng)然，用多邊形表示物體也有其缺點(diǎn)，如增加了紋理映射和陰影生成的難度，當(dāng)需要詳細(xì)表示復(fù)雜物體時(shí)所需的三角形數(shù)量將變得非常龐大。

將多邊形表示的物體顯示到計(jì)算機(jī)屏幕上，這一過程涉及物體在計(jì)算機(jī)內(nèi)部的表示方式即物體的數(shù)據(jù)結(jié)構(gòu)，由物體組成的場(chǎng)景的組織結(jié)構(gòu)，物體從場(chǎng)景到屏幕空間要經(jīng)過的一系列變換，以及產(chǎn)生最終屏幕圖象要經(jīng)過的一系列光柵化處理。這些方面都涉及到特定的處理算法,相應(yīng)的算法又有許多不同的變種。下面僅就3D芯片涉及的圖形處理過程及相關(guān)算法做一簡(jiǎn)單分析介紹，這些是理解3D圖形處理及圖形硬件的基礎(chǔ)。

二、3D物體的表示法

具有復(fù)雜外形的物體其表面可以由多邊形面片來近似表示。以圖1的圓柱為例，其柱面可以由2N個(gè)三角形近似，其兩端可以由兩個(gè)N邊形來近似。多邊形模型在其輪廓上的分段線性特征是這一表示法主要的視覺缺陷,改進(jìn)的唯一途徑是增加多邊形的分辨率。對(duì)于一個(gè)復(fù)雜形體來說，為了充分表示其細(xì)節(jié)，常常要用到十萬個(gè)以上的多邊形。這將耗費(fèi)許多數(shù)據(jù)庫(kù)訪問時(shí)間和繪制時(shí)間。當(dāng)將多邊形模型進(jìn)行放大處理時(shí)，會(huì)產(chǎn)生連接問題。這就是所謂的“幾何走樣”。物體的多邊形表示既可以通過交互設(shè)計(jì)人工提取，也可以通過激光掃描設(shè)備得到?？傊?，多邊形表示的物體并不特別適合于交互操作或做自由的形狀改變。當(dāng)改變物體的形狀時(shí)很難保證多邊形表示的完整性得到保持。

對(duì)多邊形明暗著色所需要的信息存儲(chǔ)在一個(gè)分層的數(shù)據(jù)結(jié)構(gòu)中，每一個(gè)物體表面由指向多邊形表的指針定義，該多邊形表包含了近似該表面的一組多邊形，每一個(gè)多邊形由指向頂點(diǎn)表的指針定義，頂點(diǎn)表包含了每個(gè)多邊形的所有頂點(diǎn)。具體來說需要為每個(gè)多邊形存儲(chǔ)以下信息:

1)多邊形的頂點(diǎn)表，每一個(gè)頂點(diǎn)是一個(gè)三維坐標(biāo)，該坐標(biāo)定義在創(chuàng)建該物體時(shí)的局部坐標(biāo)系中。

2)頂點(diǎn)的法向量表，這是明暗處理算法所要求的信息。向量由同一局部坐標(biāo)系中的三分量表示。

3)多邊形的法向量，它是包含該多邊形的平面的真正的幾何法向量。這是背面刪除操作所需要的信息。

繪制多邊形物體的傳統(tǒng)方法是將多邊形作為獨(dú)立的繪制實(shí)體，這樣多邊形之間的共享邊就要被處理兩次。為避免這種情況，可采用基于邊的繪制方法，這時(shí)多邊形的表示是基于多邊形的邊而不是多邊形本身。基于邊的方法意味著繪制過程的組織要采用基于掃描線的算法，基于掃描線的算法將同時(shí)處理與當(dāng)前掃描線相交的所有多邊形。這時(shí)存儲(chǔ)器中能存儲(chǔ)的可被同時(shí)處理的多邊形的最大數(shù)目將成為可繪制的場(chǎng)景復(fù)雜度的上限。使用全屏Z-buffer并將掃描線算法局限在物體所包含的多邊形上就可以解決這一問題。

三、坐標(biāo)系統(tǒng)

繪制過程的幾何處理部分可被看成應(yīng)用一系列的坐標(biāo)變換將物體數(shù)據(jù)庫(kù)變換到一系列的坐標(biāo)系下，這些坐標(biāo)系對(duì)所有繪制系統(tǒng)都是公用的，是理解3D圖形學(xué)的基礎(chǔ)。用計(jì)算機(jī)生成圖象的一系列基本操作與繪制過程要經(jīng)歷的一系列空間即坐標(biāo)系有關(guān)。隨著繪制過程的進(jìn)行處理將從一個(gè)空間進(jìn)入下一個(gè)空間。已完整地建立起描述這些變換的方法。在對(duì)物體實(shí)施變換時(shí)希望對(duì)頂點(diǎn)和頂點(diǎn)的法向量使用相同的變換矩陣。事實(shí)上，當(dāng)變換在所有方向并不相同時(shí)，頂點(diǎn)法向量必須采用不同的變換矩陣。由于單位法向量經(jīng)過變換之后其長(zhǎng)度不一定仍保持不變，因而必須對(duì)其進(jìn)行重新單位化處理(單位法向量是光照計(jì)算所要求的)。

1.局部坐標(biāo)系（局部空間）

為了建模和進(jìn)行局部變換的方便可選擇被建模物體之內(nèi)或附近的某一點(diǎn)作為局部坐標(biāo)系的原點(diǎn)。例如可選擇一個(gè)立方體的某一頂點(diǎn)作為坐標(biāo)原點(diǎn)，三個(gè)坐標(biāo)軸即是與該頂點(diǎn)相連的立方體的三條邊。在局部坐標(biāo)系選定之后，物體各頂點(diǎn)的局部坐標(biāo)以及相對(duì)于該局部坐標(biāo)系的各頂點(diǎn)的法向量和物體上多邊形的法向量就可以被提取并存儲(chǔ)起來。

2.世界坐標(biāo)系（世界空間）

當(dāng)每一個(gè)物體在其局部坐標(biāo)系中被建立起來之后，就需要將其放置到將要繪制的場(chǎng)景之中。組成場(chǎng)景的每個(gè)物體都有自己獨(dú)立的局部坐標(biāo)系。整個(gè)場(chǎng)景的坐標(biāo)系就是所謂的世界坐標(biāo)系。場(chǎng)景中的所有物體都必須從自己的局部坐標(biāo)系中變換到世界坐標(biāo)系中以定義場(chǎng)景中物體之間的空間相對(duì)關(guān)系。如果一個(gè)物體在場(chǎng)景中被定義為運(yùn)動(dòng)的，則必須為該物體定義一個(gè)隨時(shí)間變化的變換序列以便在每一幀將該物體變換到世界坐標(biāo)系中的不同位置。場(chǎng)景中的光源也在世界坐標(biāo)系中定義。如果光照計(jì)算是在世界空間中進(jìn)行，則對(duì)物體法向量的變換到此為止。對(duì)物體表面屬性如紋理、顏色等的定義和調(diào)整也在世界空間中進(jìn)行。

3.眼睛坐標(biāo)系、相機(jī)坐標(biāo)系或觀察坐標(biāo)系（眼睛空間）

眼睛坐標(biāo)系統(tǒng)是用來建立對(duì)世界空間進(jìn)行觀察時(shí)的觀察參數(shù)和觀察范圍的。在圖形學(xué)中通常用假想的相機(jī)來輔助對(duì)觀察系統(tǒng)的理解。一個(gè)假想的相機(jī)可以以任意方向放置在世界空間的任何位置，膠片平面在圖形學(xué)中就是觀察平面，也就是場(chǎng)景將投影到其上的平面。建立一個(gè)普遍適用的觀察空間相當(dāng)繁瑣，在多數(shù)情況下是對(duì)眼睛坐標(biāo)空間做許多限制。一個(gè)最小的實(shí)用系統(tǒng)可以這樣建立，首先要求眼睛坐標(biāo)系的原點(diǎn)和投影中心是世界坐標(biāo)系中的同一個(gè)坐標(biāo)點(diǎn)；其次要求觀察平面的法向量和觀察方向在眼睛空間中與Z坐標(biāo)軸重合；最后，觀察方向必須是這樣的，當(dāng)相機(jī)朝著Z軸的正向時(shí)Z值的增加將遠(yuǎn)離眼睛的位置，同時(shí)在左手坐標(biāo)系的前提下，X軸指向右，Y軸向上。滿足這一要求的系統(tǒng)就可以使假想的相機(jī)以任何觀察方向放置在世界坐標(biāo)空間中的任何位置。圖2 是有關(guān)坐標(biāo)系之間的關(guān)系。

眼睛坐標(biāo)系是最適宜做背面刪除的空間。背面刪除操作是將背對(duì)觀察者的多邊形全部剔除，在場(chǎng)景中這些多邊形對(duì)于觀察者來說是不可見的。如果對(duì)一個(gè)凸物體做背面刪除，則可以完全解決其隱藏面問題。對(duì)于具有凹面的物體而言這一操作并不能解決隱藏面問題。背面刪除操作是通過計(jì)算多邊形所在平面的法向量與視線向量之間的夾角來決定該平面是否可見。如果這兩個(gè)向量的點(diǎn)積大于0，意味著其夾角小于90o 即該多邊形是可見的，否則為不可見。視線向量是從多邊形指向視點(diǎn)的向量。多邊形平面的法向量可通過其不共線的三個(gè)頂點(diǎn)計(jì)算而得。多邊形的法向量必須指向物體的外部，為保證這一點(diǎn)，多邊形的頂點(diǎn)必須以反時(shí)針方向（從多邊形外部看時(shí)）順序存儲(chǔ)。如圖3所示。

4.屏幕坐標(biāo)系（屏幕空間）

屏幕空間是比較難于靠直覺理解的一種空間概念。它是描述如何觀察場(chǎng)景的方法的過程，與透視幾何有關(guān)，也可以理解為怎樣定義場(chǎng)景中能夠到達(dá)眼睛（或相機(jī)）的光線的過程。將場(chǎng)景中的一個(gè)點(diǎn)投影到距離視點(diǎn)為D的觀察平面或屏幕要用到的基本變換是透視變換，屏幕或觀察平面的法向與觀察方向一致。從圖4可以看到，運(yùn)用相似三角形原理，點(diǎn)P在屏幕上的投影P’(Xs= Dxe/Ze, ys=Dye/Ze)。屏幕與觀察平面略有不同，屏幕是觀察平面上的一塊矩形區(qū)域，在經(jīng)過一個(gè)與設(shè)備有關(guān)的變換之后，可以從觀察平面坐標(biāo)求得屏幕坐標(biāo)。屏幕空間的定義使得其只對(duì)一個(gè)封閉空間中所包圍的場(chǎng)景進(jìn)行繪制處理，這個(gè)封閉的空間稱作視錐臺(tái)。它可以這樣來描述：設(shè)想在距離視點(diǎn)D處的觀察平面上有一尺寸為2h的正方形窗口，且該窗口關(guān)于觀察方向是對(duì)稱的，則平面

xe=±hze/D ye=±hze/D
ze=D ze=F

將構(gòu)成一個(gè)封閉的錐臺(tái)。其中xe、ye 、ze是指眼睛坐標(biāo)系中的坐標(biāo)，而平面ze=D和平面ze=F分別稱作近處和遠(yuǎn)處的裁剪平面，它們垂直于觀察方向，在此我們假設(shè)觀察平面與近處的裁剪平面重合。如圖4所示。對(duì)于透視投影而言，通過連接窗口角與投影中心就形成所謂的視錐體。

有了這個(gè)視錐體，就可以用它對(duì)已變換到眼睛坐標(biāo)系下的場(chǎng)景進(jìn)行選擇。這不外有三種情況，對(duì)于那些完全落在視椎臺(tái)之內(nèi)的物體，直接通過透視變換將其變換到屏幕坐標(biāo)系下；對(duì)于那些完全落在視椎臺(tái)之外的物體不作進(jìn)一步的處理而直接拋棄；對(duì)于那些與視椎臺(tái)的面相交的物體則應(yīng)作裁剪處理，裁取其位于錐臺(tái)內(nèi)的部分并用透視變換將它們變換到屏幕坐標(biāo)系下。在屏幕坐標(biāo)系下，Z坐標(biāo)將作為判斷物體面之間相互遮擋的唯一判據(jù)。
注意，場(chǎng)景中的每個(gè)物體的每個(gè)三角形都要經(jīng)過以上處理過程。

四、象素處理

經(jīng)過以上一系列的變換之后，一個(gè)多邊形已變換到屏幕坐標(biāo)系下。將一個(gè)屏幕多邊形在屏幕上繪制出來就是多邊形的象素處理過程，它包括光柵化、隱藏面消除、明暗處理。光柵化、隱藏面消除、明暗處理是整個(gè)3D圖形生成過程中最內(nèi)層的處理。他們是三個(gè)二維插值過程。光柵化是用屏幕空間三角形的頂點(diǎn)坐標(biāo)插值，以求得三角形的邊所截取的三角形內(nèi)掃描線段的端點(diǎn)坐標(biāo)，并進(jìn)而求得所截掃描線段上的象素坐標(biāo)。隱藏面消除則是通過對(duì)屏幕空間三角形頂點(diǎn)的深度值（Z坐標(biāo)）進(jìn)行插值，從而獲得三角形內(nèi)掃描線段上每個(gè)象素的深度值。明暗處理是用同樣的方法由頂點(diǎn)光強(qiáng)求得三角形內(nèi)掃描段上每個(gè)象素的光強(qiáng)。這三種處理的算法具有相同的數(shù)學(xué)表示形式，只需將坐標(biāo)、深度或光強(qiáng)代入該方程就可以得到相應(yīng)的結(jié)果?？傊瑘?chǎng)景的繪制過程可概括為：

對(duì)場(chǎng)景中的每個(gè)物體的每個(gè)多邊形做幾何變換將其變換到屏幕空間；
對(duì)多邊形內(nèi)的每一個(gè)掃描段求出其端點(diǎn)及其上每個(gè)象素的坐標(biāo)；
對(duì)掃描段上的每個(gè)象素做隱藏面消除處理及明暗處理。

1.光柵化

光柵化處理通過插值求得三角形內(nèi)掃描段的x坐標(biāo)的起點(diǎn)和終點(diǎn)。問題是何處是終點(diǎn)和起點(diǎn)？當(dāng)使用實(shí)數(shù)坐標(biāo)時(shí)在象素之內(nèi)的何處進(jìn)行采樣，屏幕坐標(biāo)是取整數(shù)還是保留小數(shù)精度？這些問題如果處理得不好，就會(huì)在多邊形之間產(chǎn)生孔洞，產(chǎn)生重疊的多邊形，這會(huì)在透明效果處理時(shí)產(chǎn)生嚴(yán)重問題。如果反走樣處理不精確，則會(huì)在帶有紋理的表面上產(chǎn)生紋理不連續(xù)現(xiàn)象。例如，如果對(duì)屏幕坐標(biāo)取整，則屏幕多邊形的頂點(diǎn)將延伸或縮回到離它最近的象素，這樣多邊形的大小將發(fā)生微小的變化，而且不能用密集采樣進(jìn)行反走樣處理，動(dòng)畫中的“顫抖”現(xiàn)象便是由此而引起的。在象素內(nèi)何處采樣并不重要，重要的是對(duì)象素采樣的處理必須一致。

2.隱藏面消除

全屏幕Z-Buffer（深度緩存器）算法已成為圖形學(xué)事實(shí)上的標(biāo)準(zhǔn)隱藏面消除算法，他雖然簡(jiǎn)單但存儲(chǔ)要求很高。Z-Buffer算法可看作是工作在三維屏幕空間。每一個(gè)象素有一個(gè)二維屏幕空間坐標(biāo)( xs , ys )和由眼睛空間頂點(diǎn)的深度值插值而得到的z深度值。深度緩存器開始時(shí)被初始化為遠(yuǎn)處裁剪平面的深度，對(duì)每一個(gè)象素比較其插值得到的深度值與已存儲(chǔ)在深度緩存中( xs , ys )處的值，如果該值小于存儲(chǔ)值，則新計(jì)算的象素更靠近觀察者。這時(shí)新計(jì)算的象素的明暗處理值將覆蓋幀緩存中的舊值，深度存儲(chǔ)器中的值也換成新計(jì)算的值。深度緩存器算法對(duì)場(chǎng)景數(shù)據(jù)庫(kù)組織及場(chǎng)景復(fù)雜性沒有限制。在處理復(fù)雜場(chǎng)景或物體時(shí)，應(yīng)保證足夠的深度精度。

3.明暗處理

首先計(jì)算多邊形頂點(diǎn)的明暗參數(shù)，然后在多邊形平面上進(jìn)行插值。這樣繪制出的物體不但具有很強(qiáng)的三維立體感，而且消除了用于近似曲面的多邊形之間的公用邊所形成的不連續(xù)特征。實(shí)現(xiàn)這一處理方式的算法有兩種，一種稱作Gouraud明暗處理，一種稱作Phong明暗處理（均以發(fā)明者的名字命名）。這也是基于多邊形的繪制日益受歡迎的一個(gè)重要原因。Gouraud明暗處理的速度快，但不能產(chǎn)生精確的高光效果，通常用在對(duì)速度要求高的場(chǎng)合，如飛行模擬、交互式CAD應(yīng)用等。Phong明暗處理可以生成高質(zhì)量的圖像，但將耗費(fèi)龐大的硬件資源。Gouraud明暗處理僅在多邊形的頂點(diǎn)使用局部反射光照模型計(jì)算光強(qiáng)，然后使用頂點(diǎn)處的光強(qiáng)通過插值求出多邊形內(nèi)各象素的光強(qiáng)值。而Phong明暗處理則對(duì)頂點(diǎn)的法向量進(jìn)行插值，并對(duì)多邊形內(nèi)的每一個(gè)象素用局部反射光照模型計(jì)算其光強(qiáng)。一般說來，多邊形頂點(diǎn)的光強(qiáng)是頂點(diǎn)的法向量相對(duì)于光源和視點(diǎn)的方向的函數(shù)，這就是所謂的局部反射光照模型。頂點(diǎn)的法向量用來近似原物體表面在該點(diǎn)處的法向量，通過平均公用該頂點(diǎn)的所有多邊形的法向量求得。

Gouraud明暗處理僅與局部光照模型中的漫反射分量一起使用，這是因?yàn)楫?dāng)高光點(diǎn)完全落在多邊形之內(nèi)時(shí)，其對(duì)多邊形頂點(diǎn)處沒有任何影響。該方法是目前3D圖形硬件都支持的唯一的明暗處理方法。

4.特殊效果
紋理映射、透明以及霧化（大氣效應(yīng)）等真實(shí)感效果都是在象素處理階段實(shí)現(xiàn)的。物體表面紋理的定義是在世界坐標(biāo)系中進(jìn)行的，通過預(yù)處理，每個(gè)帶有紋理的多邊形在其頂點(diǎn)數(shù)據(jù)中建立了與相應(yīng)紋理圖的映射關(guān)系。在繪制帶有紋理的多邊形時(shí)，其相應(yīng)的紋理圖也同時(shí)被加載到紋理存儲(chǔ)器中，在求出物體上象素坐標(biāo)的同時(shí)其相應(yīng)的紋理坐標(biāo)也被計(jì)算出來。用該紋理坐標(biāo)從紋理存儲(chǔ)器中讀出相應(yīng)紋理象素的值，將其與明暗處理的結(jié)果進(jìn)行混合就得到要顯示的象素值。霧化（大氣效應(yīng)）則是在計(jì)算出的象素值上乘上一個(gè)與深度有關(guān)的衰減因子。對(duì)落在同一屏幕位置的象素點(diǎn)的象素值按其所屬物體的透明系數(shù)進(jìn)行加權(quán)融合就可以產(chǎn)生透明效果。

五、結(jié)束語

3D圖形應(yīng)用對(duì)計(jì)算和存儲(chǔ)資源的巨大需求以及3D圖形生成算法與傳統(tǒng)計(jì)算機(jī)體系結(jié)構(gòu)的不相適應(yīng)產(chǎn)生了3D圖形硬件。PC機(jī)上的3D圖形硬件的出現(xiàn)只是最近幾年的事，它是技術(shù)進(jìn)步和市場(chǎng)推動(dòng)的結(jié)果。目前，3D圖形硬件既有高端的專用圖形工作站也有入門級(jí)的圖形加速卡，任何更好更快的圖形效果的獲得都需要付出巨大的硬件代價(jià)。