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

?

　　一、引言

　　3D芯片的處理對象是多邊形表示的物體。用多邊形表示物體有兩個(gè)優(yōu)點(diǎn)：首先是直接(盡管繁瑣)，多邊形表示的物體其表面的分段線性特征除輪廓外可以通過明暗處理(shading)技術(shù)消除;其次是僅存儲多邊形頂點(diǎn)的幾何信息，多邊形內(nèi)部每個(gè)象素的明暗顏色計(jì)算所需的信息由這些頂點(diǎn)信息插值而來，這正是易于用圖形硬件支持的快速明暗處理技術(shù)。支持多邊形繪制的圖形硬件同樣也可以繪制由雙三次曲面片表示的物體，通過對這種物體的表面進(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)，由物體組成的場景的組織結(jié)構(gòu)，物體從場景到屏幕空間要經(jīng)過的一系列變換，以及產(chǎn)生最終屏幕圖象要經(jīng)過的一系列光柵化處理。這些方面都涉及到特定的處理算法,相應(yīng)的算法又有許多不同的變種。下面僅就3D芯片涉及的圖形處理過程及相關(guān)算法做一簡單分析介紹，這些是理解3D圖形處理及圖形硬件的基礎(chǔ)。

　　二、3D物體的表示法

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

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

　　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í)多邊形的表示是基于多邊形的邊而不是多邊形本身?；谶叺姆椒ㄒ馕吨L制過程的組織要采用基于掃描線的算法，基于掃描線的算法將同時(shí)處理與當(dāng)前掃描線相交的所有多邊形。這時(shí)存儲器中能存儲的可被同時(shí)處理的多邊形的最大數(shù)目將成為可繪制的場景復(fù)雜度的上限。使用全屏Z-buffer并將掃描線算法局限在物體所包含的多邊形上就可以解決這一問題。