3D圖形芯片的算法原理是什么樣的？

一、引言

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

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

二、3D物體的表示法

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

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

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

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

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

繪制多邊形物體的傳統方法是將多邊形作為獨立的繪制實(shí)體，這樣多邊形之間的共享邊就要被處理兩次。為避免這種情況，可采用基于邊的繪制方法，這時(shí)多邊形的表示是基于多邊形的邊而不是多邊形本身?；谶叺姆椒ㄒ馕吨?zhù)繪制過(guò)程的組織要采用基于掃描線(xiàn)的算法，基于掃描線(xiàn)的算法將同時(shí)處理與當前掃描線(xiàn)相交的所有多邊形。這時(shí)存儲器中能存儲的可被同時(shí)處理的多邊形的最大數目將成為可繪制的場(chǎng)景復雜度的上限。使用全屏Z-buffer并將掃描線(xiàn)算法局限在物體所包含的多邊形上就可以解決這一問(wèn)題。

三、坐標系統

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

1.局部坐標系(局部空間)

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

2.世界坐標系(世界空間)

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

3.眼睛坐標系、相機坐標系或觀(guān)察坐標系(眼睛空間)

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

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