3D圖形編程指南(back culling)

隱麵消除(back culling)

　　目 錄
　　7.1 背麵剔除算法
　　7.2 從後到前排序
　　7.3 順序列表和八叉樹
　　7.4 入口
　　7.5 二叉空間分割樹
　　7.6 Beam樹
　　7.7 掃描線算法
　　7.8 Z-Buffer算法

---

　　引言
　　到目前為止，我們完全忽略了一些問題：很明顯，它們是由於屏幕上的一些圖元被另一些圖元擋住所造成的。例如，當我們要描繪一個由多邊形麵組成的三維物體時，那麽它的一部分必然要被擋住。我們要在屏幕上顯示的必須是可見的東西。打個比方，對於一個立方體，無論從哪個方向進行透視處理，我們最多隻能看到其中的三個麵。這樣，我們就要想出一種方法來決定哪些麵是我們所能看到的。
　　如果我們使用從屏幕到世界的視處理方法，那麽很自然的就能保證隻有圖元上正確的部分才顯示在屏幕上。在這種視處理中，可見性在屏幕的每一個像素上進行判斷。我們從人眼發出一條射線，穿過一個給定的像素，那麽首先與這條射線相交的表麵在這一個像素上就是可見的。從這個表麵反射的光線能夠進入我們的眼睛。
　　在這一章中，我們將討論用於隱麵消除的一些方法。由於最普通的圖元就是多邊形，所以我們將要討論的許多技術都是隻針對多邊形模型的。我們也將重點討論用於多邊形地形、體素模型的一些技術，最後將討論一種適用於任何圖元的一般性的算法。
　　盡管隱麵消除對於光線投射方法是本身就具備的，但是它的計算量是很大的。這樣，我們還將使用一些用於從世界到屏幕視處理方法的隱麵消除算法，它們將與光線投射算法結合使用，從而減少計算量。

7.1、背麵剔除(back culling)算法
　　許多三維物體，它們所占據的空間都被一些連續的表麵所包圍。當我們觀察這些物體時，隻能看到這些包圍表
麵中正麵部分，而對背麵就無法看到了。背麵剔除算法就是將這些我們看不到的背麵多邊形去除掉(見圖7.1)

圖7.1 包圍表麵的可見與不可見部分

　　在前麵的章節中，我們已經遇到過凸多邊形的概念。這一概念也可以引申到多麵體上。如果位於表麵上的任意兩個點的連線都沒有超出邊界的話，那麽這個多麵體就是一個凸多麵體。凹多麵體沒有這樣的特性。(見圖7.2)

圖7.2 凸多麵體與凹多麵體

　　如果我們對一個多邊形模型執行背麵剔除，並且這個模型是一個凸多麵體，那麽經過這樣的處理之後，我們就已經消除了所有的隱藏表麵。由於這些模型的形狀，所有隱藏的多邊形就是組成背麵的多邊形。但是，在消除凹多麵體的隱藏麵時，這一通用的技術就會出現一些問題。有可能某些對象的正麵被其他多邊形中同樣是正麵的麵遮擋(見圖7.3)。這時，位於背麵的多邊形仍然是不可見的，明確地消除它們將對此有幫助， 即便不能解決這一問題，那麽至少減小了其複雜性。

圖7.3 向前的多邊形被遮擋的情況

　　同樣的推理也應用於光線投射算法。盡管我們完成隱麵消除要歸功於這種算法的自然本性，但背麵剔除算法可以減少場景的複雜度，使我們不用再同那些複雜的隱藏麵一起進行考慮，這樣就加快了視處理的過程。
　　讓我們來設計一種技術，來決定一個多邊形是位於物體表麵的正麵還是背麵。我們已經看到了法向量在描述一個多邊形的朝向時所起到的作用。這樣，當一個多邊形的法向量與觀察方向之間的夾角大於90°時，就表示這個多邊形位於物體的背麵。
　　我們已經討論過矢量積和標量積，它們對於解決上麵的問題很有幫助。首先，我們計算位於一個給定多邊形平麵上的某兩個向量的矢量積，得到這個多邊形的法向量。這兩個向量可以通過多邊形頂點的差分來得到。接下來，計算觀察方向與法向量之間標量積的符號，由此決定它們之間是否形成了大於90°的角。如果真的大於90°，這個多邊形就要被剔除掉，也就不用再考慮進行視處理過程了。
　　我們要注意，根據定義，兩個向量的矢量積的結果也是一個向量，它與兩個做向量乘法的向量組成的平麵正交。這也就是說，根據多邊形平麵上形成這兩個向量的方式的不同，我們可以得到兩種可能的法向量，它們的方向正好相反。(見圖7.4)

圖7.4 頂點順序與方向量方向的關係

　　如圖7.4所示，如果我們在連續頂點和建立兩個向量，那麽法向量的方向將會依賴於這兩個向量的順序。我們可以很方便的將多邊形表麵的正麵與頂點的反時針順序聯係起來(見圖7.4 (a))，這也正是定義表麵法向量的基礎。
　　我們已經見到了兩種不同的視處理過程，並且還有兩種不同的投影變換。使用這些技術，我們可以在渲染管道中的某一特定階段完成背麵剔除算法。
　　對於平行投影方式，投影線都具有相同的方向，並且與觀察方向一致。就在投影階段之前，觀察方向向量指向Z方向，可以用(0,0,1)來進行描述。這樣當然也就減少了標量積的計算量，其結果就等於法向量的z分量。這樣，我們就隻需要計算法向量的z分量值就可以了。
　　對於透視投影，投影線相交在觀察者的眼中，它們的方向是不同的。我們可以在世界或觀察空間中的任一點上構造一個指向觀察者眼睛的向量，並使它指向該點方向，這樣就得到了這一點的觀察方向。(見圖7.5)

圖7.5 尋找背麵多邊形

　　然而，一旦模型經過透視變換從觀察空間映射到屏幕空間之後，用來執行背麵剔除的觀察方向恒定，使我們隻需要對法向量的z分量來進行簡單的計算就可以了。
　　背麵剔除可以在渲染管道的開始階段執行，也可以在世界空間甚至對象空間中來進行。我們越早剔除掉背麵多邊形，那麽要執行的多餘的操作就會也少。我們還要考慮對頂點進行的3-D變換，這樣，如果我們可以剔除掉不屬於任何前表麵的頂點的話，在對象空間執行背麵剔除運算將會很有好處。我們可以對每一個頂點設置一個布爾變量，當包含某個頂點的多邊形位於前表麵時，就將該頂點的布爾變量值設為“true”。檢查完所有多邊形之後，我們就可以將任何情況下都沒有被設置為“true”的頂點剔除掉。這樣就可以避免對被剔除的頂點執行3-D變換，從而減少了計算量。如果我們不選擇執行上述操作，那我們同樣可以在世界空間中來進行背麵剔除運算。在世界空間中執行剔除運算，可以避免對一些多邊形進行計算量很大的裁剪計算。但是剔除運算本身的計算量將比在光柵化之前執行大一些。
　　除了在運行時計算多邊形表麵的法向量之外，我們還可以在程序的渲染循環之前預先計算好這些向量，並將它們與每一個多邊形表麵聯係起來。為了在世界空間中得到法向量，我們可以應用變換將頂點變換到世界空間中。應該注意到，為了達到對一個向量的變化目的，我們隻能應用變換的線性部分（也就是旋轉和非歸一化縮放變換）。平移變換沒有必要使用，因為它對向量沒有影響。將一個法向量從一個空間變換到另一個空間中的計算量往往要比直接在目標空間中建立該法向量還要大。但是，由於光線處理過程也要使用到單位法向量，這樣我們就可以將兩種運算目的合並起來。然而，在一個空間中建立一個單位法向量的計算量又要比從另一個空間中變換過來的計算量大的多。因此，我們還是要對法向量進行變換。
　　同樣的推理最可能應用在從屏幕到世界的視處理情形中，正如我們注意到的，我們可以對這種方式進行一些修改，避免計算光線和背麵多邊形的交叉點。由於在這種視處理方法中，我們沒有明確地把坐標變換到視空間中，它留下的隻是用於可能的剔除應用的世界和對象空間。將在下一章中，我們可能會使用遞歸射線來追蹤環境反射。由於這種光線的方向很難被提前預見，因此它們可能正好與觀察者不可見的多邊形相交。作為結果，在對象空間中剔除沒有太多的意義。

7.2、從後到前排序
　　如我們在前一節看到的，背麵剔除對多邊形模型中的隱麵消除來說是不夠的。一般情況下，在使用從世界到屏幕方法時，要找到所有被遮擋起來的多邊形部分是比較困難的。要解決這一問題，我們可以對每一個多邊形相對於所有其它的多邊形進行反複的裁剪，並檢查得到的麵片的深度信息。如果麵片沿著觀察方向比裁剪多邊形更遠的話，那麽它就一定被遮擋住了，就要被剔除掉。在這一處理過程結束時，我們會得到一係列新的多邊形，它們都是可見的。
　　毫無疑問，這種方法的計算量將會很大，並不一定實用。我們還有一種方法，它充分利用了圖形硬件的幀緩存結構。不管場景中的多邊形擋沒擋住其它的多邊形，我們隻要按照從後向前順序光柵化圖元，就可以正確的顯示所有的圖元。離觀察者最近的一個多邊形最後進行光柵化處理。這種方法就是我們常說的畫家算法。
　　我們必須注意，當多邊形光柵化處理的計算量太大時，例如我們使用比較複雜的紋理映射和光線，再使用從後到前順序就不太好了，因為許多多邊形會被遮擋住，白白浪費了大量的工作。這時，使用我們前麵所說的一些方法可能會比較適合。
　　為了得到從後向前的順序，沿著觀察方向按照多邊形的深度信息對它們進行排序是一種比較好的方法。如果使用了透視變換，我們在視空間中就不能使用排序方法了，因為觀察方法相對於不同的多邊形會發生變化。觀察方向隻在光柵化處理階段前才是一個常量，這時就可以使用排序方法了。
　　為了沿著觀察方向進行排序，必須找到一個多邊形比較的判據。最簡單的方法就是比較一個多邊形上所有頂點中最大z坐標（離觀察者最遠）。也可以比較多邊形頂點z坐標的平均值。
　　還有其它許多的排序算法。最直截了當的方法複雜度為。也就是說為了產生一個排序列表，這些算法中使用的大量的基本運算都與成比例。這種算法的一個例子就是氣泡排序法（bubble-sort）。在這種算法中，我們在列表中將一個物體與它前麵的物體進行比較，如果不滿足排序判據，就將它們的位置進行交換。如果我們從列表中的第一個物體開始對每一個物體進行比較，那麽對於單個物體來說，它就會逐漸被交換到正確的位置，就像一個氣泡被逐漸推到水麵一樣。我們將一個物體移動到正確的位置隻需要進行n-1比較。(見圖7.6)

圖7.6 氣泡排序法

　　具有平方複雜度的算法的計算量仍然是很大的。還有一類排序算法，它們的複雜度為。這類算法都使用了各種不同的細分和克服策略。例如快速排序算法（quicksort），它將一個列表分為兩部分，並預先選出一個重心值，這樣，列表一部分中的所有對象都比重心小，而另一部分中的所有對象都大於或等於重心。如果我們遞歸地進行快速排序，那麽最終就會得到排序的原始列表。這種算法的複雜度大約是。(見圖7.7)

圖7.7 快速排序算法

　　的複雜程度已經很有效了，但我們還有一類排序算法，它們利用了這樣的一個事實，那就是我們的排序總有一定的範圍，這樣它的複雜度就更小。例如，我們經常用32位來存儲一個整型數，這也是我們能夠表示一個整型數的界限。基數排序算法（Radix sort）就是這類算法中的一種，它的複雜度大約隻有，但是它往往要求比較大的空間，有時又對基本操作或存儲單元又不同的要求。這樣，我們還是經常使用複雜度為的一些算法。
　　基數排序（Radix sort）算法基於這麽一個事實，即對來自一定範圍的數進行排序比較容易。例如，如果允許的排序索引表（sorting key）的範圍為[0,3]，那麽我們就可以按照下麵的步驟來放置標有這些索引表數值的對象。計算標有每個索引表數值的元素的總的序號。這些序號定義了一些偏移量，根據偏移量每一組的元素必須放置在最終的列表中。比如說，標有1的對象必須跟在標有0的對象後麵，並由此放置在最終的列表中。我們再一次遍曆原始列表， 這次根據已知的偏移量將對象放置在最終的列表中。這一算法就是計數排序算法（counting sort），當排序索引的範圍較小時，它是比較適合的。基數排序算法需要一個有限的但不必非常小的範圍，並且它通過多次引用一個與計數算法類似的過程來進行工作， 每一次排序都按照不同的位來安排索引表數值。(見圖7.8，左圖用低2位進行遍曆排序，右圖則再用高2位排序)

圖7.8 基數排序

　　從圖7.8的例子可以看到，這種算法的複雜度也為，但是，它需要多次的穿越列表，這樣它的執行效率就會降低。通常，快速排序算法在列表較小時執行的比較好。基數排序算法隻有在列表較長，要表示的值的範圍較窄時，它的優點才會顯現出來。
　　我們使用上述算法的目的就為了將多邊形按照從後向前的順序放置。但是，所討論的算法的性能依賴於要被排序的列表的混亂程度。許多級的算法在整個列表都被進行排序時工作得較好，這時，隻需要很少的操作就可以完成工作。當列表比較混亂時，快速排序算法工作的較好。隻有在列表比較大、數值範圍比較窄時，基數排序算法才比較適用。在三維圖形程序中，我們經常希望慢慢的旋轉多邊形物體。這時，多邊形的順序在幀與幀之間變化不大，我們使用通常看起來效率不太高的算法就可以達到很好的性能了。另一方麵，如果要確保通常情況下的比較平均的性能，那麽快速排序算法比較適合。
　　還應該強調，我們進行排序算法是基於這樣的一個假設的，就是我們已經具有一些排序判據來將多邊形按照從後向前的順序放置。不幸的是，並不完全是這樣。有時按照最大z坐標來進行比較並不正確。(見圖7.9)

圖7.9 最大z坐標判據實效的情況

　　在圖7.9中，基於最大z坐標判據，多邊形A應該首先被繪製，但是實際上它擋住了多邊形B的一部分。類似的情況也會發生在使用平均z坐標判據的情況。
　　在某些情況下，我們可以容忍上述的問題。當我們保證場景中的多邊形的大小都相同時，基於最大或平均z坐標的排序算法是可以接受的。例如，當我們將某種解析形狀如球、或雙三次麵片鑲嵌成多邊形時，上述這種情況就會發生。這時，簡單的排序通常是比較有效的。有時，我們不能保證多邊形的大小完全相等，我們可以嚐試使用更複雜的排序判據。如果我們可以找到一個點，它屬於兩個多邊形的屏幕投影的交集，我們就可以進一步計算這一點的深度，並用結果作為判據來進行比較。為了定位這樣一個點，我們不得不找到一個多邊形的每個邊與其他多邊形的每個邊的交集，還要檢查一個多邊形的屏幕投影被包含在其他多邊形的屏幕投影中的情況。這樣的一種方法可能在每個多邊形的邊較少時比較有效。當這一情況不能保證時，我們將不得不進行一定的條件放寬，並使用一些更經典的方法。例如，如果我們假設多邊形是凸多邊形，我們可以首先找到它們的公共切線，也就是一條將多邊形的頂點都留在一側的線（見圖7.10），接下來，將會得到帆狀或沙漏多邊形來找到一個交點或顯示不存在這種現象。(見圖7.11)
　　為了找到公共切線，我們可以首先檢查兩個多邊形的邊延長線，例如可以從具有最小y坐標的頂點開始。既然在一個凸多邊形中，一條邊的延長線將所有的頂點都置於同一側，這條線就可以稱為一條切線。我們可以檢查兩個多邊形的這些切線的關係。例如，在圖7.10中的邊d，它位於邊a延長線的右側。我們處理下麵的邊，得到同樣的情況：屬於第二個多邊形的邊e位於b的右側。但是，當我們考慮相鄰的邊時，情況發生了變化，第一個多邊形中的邊c位於第二個多邊形中的邊f的右側。由於有切線相互交叉，換句話說當我們從一個多邊形中的方向b變化到方向c，並且從另一個多邊形中的方向e到方向f時，它們的關係會發生變化，因此，存在一條公共的切線，使得兩個多邊形的所有頂點都位於它的同一側，這條切線就是圖中點A和D的連線。(見圖7.10)

圖7.10 找到兩個多邊形之間的橋梁

　　必須注意，切線從不相交的情況是並不是不可能的。如果我們遇到一個多邊形包含在另一個多邊形內的情況，那麽前者的所有點都可以被用來進行深度比較。
　　一條公共切線就象一座橋一樣將兩個多邊形聯係在一起。它同樣定義了一個類似帆的形狀，它由兩個交叉的凸多邊形鏈組成，每一個都來自於一個多邊形 。(見圖7.11)

圖7.11 尋找交點

　　為了找到兩個鏈的交點， 我們可以反複減小問題的大小直到找到交點為止。我們來看一下上圖中的三角形ABI和IJA。很明顯，每一個都是一個ear，也就是一個不包含在任何其他凸多邊形的內部的三角形。為了驗證這一點，可以檢查B是否在AJ上，同樣，也要檢查J是否在IB上。確定了ABI是一個凸狀體之後，我們可以將它去除掉，並繼續進行最初的子問題 — 一個BI位於頂部的帆。最後，CK成為帆當前的頂，在這一點處，D不在CL上，L也不在DK上。這就意味著，我們已經找到了CD和KL的交點，並且可以進一步使用第五章中的技術來找到兩個多邊形在交點處的z坐標。
　　應該注意，這兩個多邊形可能不會相交，這時，代替帆狀多邊形，我們將得到一個沙漏多邊形。調整暗示的方法來找到合適發生這種情況並不困難。
　　這種方法的另一個加速的辦法，就是使用約束體，並且在多邊形的關係很明顯時避免大量的計算。例如，如果一個多邊形最小的z值比另一個多邊形最大的z值還要大，那麽，我們就可以確定它們的順序了。(見圖7.12)

圖7.12 多邊形比較的擴展

　　當z值出現重疊時，我們再使用計算量較大的比較方法。除了計算量較大之外，上述的比較多邊形進行排序的方法還有它內在的問題。我們不能真正找到一個能夠建立很好的順序的判據。本質上，一個建立得很好的順序就需要在任何的一係列的元素中都有最小的一個。(見圖7.13)

圖7.13 多邊形比較的困難所在

　　在圖7.13中，多邊形A、B和C應該按照先A再B然後C的順序排列，這是由於B擋住了A的一部分，而C又擋住了B的一部分。但是，如果在排序處理過程中，我們要對A和C進行比較，那我們就不能這麽說了。這些多邊形具有相同的最大和平均z坐標值，它們在屏幕上的投影也並不相交。我們將嚐試著認為它們“相等”，並且對我們來說，應該按照什麽順序進行渲染並不重要。但這並不是真的：多邊形B確實在A和C之間， 並且它們的順序也是很重要的。這種情況在有多重交疊存在是將更加嚴重(見圖7.14)。這些多邊形中沒有一個明確的最小者。

圖7.14 多邊形的多重交疊

　　在這個例子中，A<C並且C<B，但同時又有B<A。
　　我們可以看到，當一個多邊形穿刺過其他多邊形時，排序方法就不能進行處理了，還有其他一些情況，例如多
重交疊等。但是，這種方法在一定的限製內還是有用的。

7.3、順序列表和八叉樹
　　我們在前一節已經看到，一般多邊形模型的隱麵消除代價極其昂貴。然而，在大多數情形中，我們要處理的對象有一些特殊的屬性，利用這些屬性可以減輕隱麵消除工作量。舉例來說，在以高度場（Height-field）進行表度的地形處理的情形中，我們可以很容易地獲得多邊形從前到後的順序。這是由於這種表度方法具有的矩形自然本性，據此，地形可以被分割為正方形的單元格。
　　讓我們考慮一種情況，觀察者在一些單元邊界內位於虛擬地形表麵上或表麵的上方。我們能夠把整個的地形分割為四個規則的子地形，如圖7.15所示。

圖 7.15 高度場遍曆（Height-field traversal）

　　由於這種表達方法的規律性，這四個子地形在觀察者屏幕上的投影幾乎沒有交叉。少數由於透視變換可能出現的交叉點可通過按從小到大渲染子地形很容易地得到修複。
　　在每個分割域內，我們通過從最遠的多邊形開始能夠得到多邊形從後到前的順序，一行一行或一列一列地朝向觀察者所在的單元進行處理。包含觀察者所在的單元的多邊形最後進行光柵處理。舉例來說，在圖7.15中的地形單元光柵處理順序如下：

　　首先： 1,2,3,4;
　　其次： 5,6,7,8,9,10;
　　再次： 11,12,13,14,15,16;
　　然後： 17,18,19,20,21,22,23,24,25;

　　這種遍曆有效地保證了在任意投影中的可見性。然而，每個單元，正如我們在前一章所看到的，可能由兩個三角形組成。光柵處理的順序將依據看向場景的角度而不同。（參見圖7.16）

圖7.16 在高度場單元中的三角形順序

　　從圖7.16中，很清楚，當觀察方向在範圍45°～225°的時候，多邊形B在A之後被渲染，否則，當觀察方向不同的時候，我們以相反的順序渲染多邊形：A在B之後。在正好是45°或者225°的時候， 渲染的順序無所謂，因為多邊形的投影在屏幕上沒有交叉。
　　極為類似的規律特性也用於尋找體素從後到前的順序，這使用八叉樹存儲，或者也用於空間占用的矩形表達方式，這兩點在前一章中我們都已經看過了。在這兩種情形中，我們能夠使用同討論過的高度場非常類似的方法，擴展為處理三維而不是兩維。
　　八叉樹是遞歸結構，在每個細分的層次上有著同樣規則的屬性。因此，在每個層次上可以應用同樣的遍曆順序，以獲得整個結構元素從後到前的順序。
　　四叉樹是八叉樹在一個平麵上的特例。為了簡化的緣故，讓我們考慮一下如圖7.17遍曆一個四叉樹。取決於觀察的方位，共有四種不同的遍曆順序，每種用於方位的特定範圍。（參見圖7.17）

圖7.17 四叉樹遍曆的四種順序

　　如圖7.17所示，為了遍曆任意子樹，我們使用相同的順序，輪到它的時候，可能會導致在很低的細分層次上遍曆，但即便如此，我們仍然在高層次上對其使用同樣的順序。
　　非常類似的策略可以用在八叉樹的情形中。通過把上麵的方法擴展到三維，我們將有8個不同的遍曆順序，每個應用於方位角度的特定範圍。

7.4、入口(Portals)
　　如何處理可見性的另一個例子是，在一種特別的情形下，模型在室內場景中演示。考慮到域的集合 — 房間，通過入口（門、窗等）連接。在這種簡化的例子中，房間是凸多麵體，這通過背麵剔除就可以正確地繪製出可見物體。
　　在圖7.18中，觀察者位於房間A。顯然，組成房間A的多邊形是可見的。為了正確地繪製入口在屏幕上的投影，房間入口導向的地方必須被繪製；為了正確地繪製其他房間可見部分，組成該處的多邊形和入口同樣也要被繪製。

圖7.18 室內空間布局

　　恰到好處地描述上麵這種策略的語言使人想起遞歸。讓我們考慮一下觀察者所處的房間的相鄰房間。我們能夠構建一個圖表，其中的節點代表房間，線條代表入口。（參見圖7.19）

圖7.19 室內域圖表

　　首先繪製房間中入口導向的多邊形，然後繪製當前房間中確保可見性正確的所有多邊形。這個轉化到圖表（房間）的遞歸上，首先對連接到當前節點的節點應用遞歸，然後對當前節點本身應用可見性處理算法。
　　必須注意到，在任意圖表遞歸中，對這種算法來說，應該小心地注意不要發生可能的循環。如果算法應用到某個節點上，則不應在對該節點重複應用第二次。在圖7.19這個特別的例子中，工作過程如下：我們從頂點A開始，接下來是頂點B，在經過頂點C到達頂點D。在這個過程中，我們不會跑到別的地方去，因為B已經被用過了。既然再沒地方可去，同D聯係在一起的房間被繪製；我們再返回C，從這裏第一次到達E，繪製其多邊形，返回並繪製C房間的所有多邊形。在該點上，我們返回B，繪製它並最終返回並繪製A房間。

圖7.20 帶有入口的內部場景

　　這種方案可得到成倍的改良。顯然，圖表可能極大，而實際上遍曆到某個深度就停止比較有意義，舉例來說，當遍曆到遠離當前所在房間三到四個房間的時候就停止。比這些房間還要深的房間用不著被看到。
　　除了我們所在的房間外，也有可能通過入口看到所有的房間，入口在屏幕上投影之外的不可能被看到。因此，當繪製我們通過門看到的房間的時候，我們實際上沿著入口屏幕投影裁剪多邊形，極大地減輕了過負荷的問題。然而，既然入口的投影是任意導向的多邊形，這類裁剪可能是非常昂貴的。我們通過沿著矩形約束裁剪來解決這個問題，矩形約束是入口屏幕投影的擴展。盡管仍然要出現某些透支現象，沿著矩形裁剪要比沿著任意多邊形裁剪快得多。特別在紋理映射多邊形伴隨著複雜的光線模式的情形下，從此改進中我們將節省相當大的開銷。應該注意到，如果我們沿著入口邊界應用裁剪，必須改變房間遍曆算法，這樣在通過不同的入口到達同一個房間的時候，我們能夠多次繪製它。
　　進一步，我們將要看到某個通用的方法，在我們用到後麵提到的beam樹的時候，利用它來減輕開銷。

7.5、二叉空間分割（BSP）樹
　　BSP （Binary Space Partition）表示二叉空間分割。使用這種方法可以使我們在運行時使用一個預先計算好的樹來得到多邊形從後向前的列表，它的複雜度為。它是由Fuch和Kedem在1980年首先提出的。它的基本思想是基於這樣一個事實，任何平麵都可以將空間分割成兩個半空間。所有位於這個平麵的一側的點定義了一個半空間，位於另一側的點定義了另一個半空間。此外，如果我們在任何半空間中有一個平麵，它會進一步將此半空間分割為更小的兩個子空間。我們可以使用多邊形列表將這一過程一直進行下去，將子空間分割得越來越小，直到構造成一個二叉樹。在這個樹中，一個進行分割的多邊形被存儲在樹的節點，所有位於子空間中的多邊形都在相應的子樹上。當然，這一規則使用於樹中每一個節點。
　　我們來看一下圖7.21種的多邊形。為了簡單起見，我們選擇一個這樣一個平麵投影，在它上麵，所有多邊形都能映射為直線段。讓我們由多邊形B開始構造一個BSP樹。(見圖7.21)

圖7.21 一個二叉空間分割

　　多邊形B所在的平麵將空間分割為兩個部分，使得多邊形D和E位於同一個半空間中，多邊形C在另一個半空間中。在這個例子中， 多邊形A穿越了兩個半空間，這樣，它就不能十分明確的被分配到任何一個半空間中。但是，如果我們將這個多邊形從它與分割平麵相交的地方分為兩個部分一個命名為，另一個命名為，這樣，就和D、E在同一個半空間中，和C在同一個半空間中。下圖表述了這一過程。

圖7.22 建立BSP樹的一個階段

　　我們現在已經將問題分成了兩個子問題。我們可以在子樹中再次使用上述算法。例如，我們在左邊子樹中選擇E作為分割多邊形，在右邊子樹中選擇作為分割多邊形。這樣，我們將建立下麵的結構樹。(見圖7.23)

圖7.23 建立BSP樹

　　必須注意，任何給定的BSP樹都不是唯一的。我們可以對同樣的多邊形找到多個有效的二叉分割。依靠我們選擇來進行分割的多邊形的順序，可以得到不同的樹。例如，在圖7.24中，我們可以看到另一個樹，它也建立在前麵我們討論的多邊形上。

圖7.24 另一種結構

　　盡管所有適合這種算法的正確的樹都可以用來得到多邊形從後向前的順序，但是總有一些要比其他一些更加有效。我們首先檢查樹遍曆算法，然後檢查確認特殊樹結構的原因。
　　我們考慮一個包含了一係列多邊形的場景， 場景帶有一個預先計算好的BSP樹和一個位於場景中某個位置的觀察者。(見圖7.25)

圖7.25 用BSP樹來得到從後向前的順序

　　我們檢查觀察者的位置和位於樹頂部的多邊形之間的關係。很明顯，當這個多邊形將空間分割為兩個部分時，觀察者必須位於其中的一個半空間中。當然，位於同一半空間中的多邊形要比另一半空間中的多邊形離觀察者更近。基於這樣的事實，如果我們首先將較遠處半空間中的多邊形放置在最終的列表中，然後放置根多邊形，再放置與觀察者在同一半空間中的多邊形，這樣就很容易得到多邊形從後向前的順序了。我們對每一個子樹都重複同樣的過程，在每一個級別中選擇相應的順序，最終，就會得到正確的多邊型的順序。
　　這一算法的一個優點就是無論觀察者位於場景中的什麽位置，無論觀察者的朝向如何，它都可以很好的進行工作。例如，在圖7.25 (a)中產生的列表就與(b)中產生的不同。但是他們對於各自的情況都是正確的。這樣，如果我們預先為一個多邊形模型計算一個BSP樹，那麽在運行時，我們隻需要根據觀察者的位置調用這個樹，執行樹遍曆過程，就可以產生用於隱麵消除的畫家算法所需的從後向前的多邊形順序。
　　在這個算法中，在樹的每一個節點處所作的判定，都依賴於觀察者位於該節點多邊形所產生的哪一個半空間中。在第五章中，分析平麵方程式時我們已經遇到過要使用這種計算的情況。利用我們所討論過的事實，我們可以看到，如果將觀察者位置的坐標代入給定多邊形的平麵方程式中，結果數值的符號如果是正號，就表示觀察者位於該多邊形的法向量所指向的半空間中，負號表示位於另一個半空間中， 0值表示他位於這個多邊形所在的平麵上。最後一種情況，對於遍曆整個BSP樹的意圖來說，意味著半空間在屏幕上的投影不相交， 並且我們可以在這一階段的遍曆過程中選擇任何子樹的順序。
　　相同的計算也要在預先計算一個BSP樹時使用到。我們需要決定不同的多邊形應該被放置在哪個子樹中。從可實現性的觀點出發，預先計算一個BSP樹的過程可以被描述成下麵的形式：對多邊形集合，我們選擇一個多邊形。進一步計算該多邊形的平麵方程式。對剩餘的多邊形，我們用所說的方程式檢查它們的所有頂點。如果所有頂點都是負值，那麽多邊形就放置在一個子樹中；如果都是正值，那麽多邊形就放置在另一個子樹中；如果結果有正有負，那麽多邊形就被分為兩部分，分別放置在兩個子樹中。一旦我們將所有多邊形分配到了正確的半空間中，我們就可以對子樹進一步調用同樣的方法來進行處理，直到當前的子表隻包含一個多邊形為止。
　　一個多邊形被任何平麵所分割的問題可以當作一個裁剪問題來處理。解決這一問題的算法隻與我們在裁剪問題時所討論的算法又很小的差別。唯一明顯的差別就是在二進製搜索邊緣裁剪過程中，我們將使用分割多邊形的平麵方程式來找到邊的中點的位置。

圖7.26 使用BSP樹渲染的一個場景，左邊是不同的多邊形

　　對於垂直邊的裁剪情況，我們使用二分搜索技術，根據邊的中點的位置拋除掉邊的一部分。既然這樣，我們可以使用類似的方法來進行處理，區別隻是改變一下判據。我們可以將同樣的方法用於多邊形的裁剪。
　　應該強調的是，由於一個BSP樹的結構是預先確定的，因此我們不必擔心建立樹時算法的效率問題。
　　一旦創建了樹，要得到多邊形從後向前的順序，就要采取下麵的步驟：我們取位於樹頂的一個多邊形。計算這個多邊形的平邊方程式。將觀察者當前的位置坐標代入方程式中，觀察結果的正負號。接著對子樹運用相同的方法
進行處理。
　　我們回憶一下平麵方程式的形式：


　　式中，P表示平麵中的點，時平麵的法向量。它還可以表示成下麵的形式：


　　後一種形式是通過對原始形式進行標量相乘得到的，使得、、、。當我們在視空間中遍曆整個樹時，觀察者的位置為(0,0,0)，我們提到的代換結果等於平麵方程式中的係數D。這樣，BSP樹遍曆可以很方便的在透視變換之前來進行。
　　表7.1顯示了一個樹遍曆的結構。

表7.1 遍曆一個BSP樹

　　我們考查了樹的創建和遍曆之後，仍然有一些問題需要解決。當我們構建一個樹時，我們可以選擇剩餘多邊形中的任何一個來分割空間。選擇不同的多邊形會導致不同的樹的結構。因此，我們就應該考慮選擇哪個多邊形有助於算法的效率。
　　有些多邊形會導致剩餘多邊形更多的分割(見圖7.21、7.23和7.24)。每一個多邊形在通過渲染管道時都有一定的係統消耗，因此多邊形越少，性能就越好。我們可以利用判據來選擇有較少分割的多邊形。
　　使用判據來平衡BSP樹，並不需要每一級中的子樹中的多邊形的數量都相同， 因為它不會影響運行時間。樹的遍曆總是假設至少每次都取一個多邊形，因此平衡不會影響性能——我們仍然不得不每次取每一個多邊形。另一方麵，一個平衡的樹可以以較少的迭代調用來執行遍曆。我們可以將平衡作為第二判據來使用。
　　總之，使用BSP樹來進行從後向前排序的最大優點就是算法運行的複雜性較低 。這種方法也解決了多邊形的多重交疊和多邊形穿越問題。但是，通過使用一個預計算結構，我們已經失去了一定的靈活性。如果多邊形的排列在運行時發生了改變， BSP樹就必須發生相應的改變。由於計算量非常巨大，我們不能這樣做，因此，這種算法對於場景在運行時發生改變的情況就不能使用了。
　　應該注意，隻有當多邊形經曆不同的變換設置時樹才會受到影響。如果所有的多邊形都使用同樣的變換，那麽分割仍然是正確的，樹也將不會受到影響。這樣，場景中的一個動態物體，它在世界中移動或者是旋轉，仍然可以使用同樣的BSP樹。如果物體中的一部分相對於其他物體發生了移動，那我們就要使用其它的算法了。

7.6、Beam樹
　　盡管使用前一節提及的BSP樹能夠有效地創建可用於畫家隱麵消除算法的多邊形從後到前的順序，但它仍然有某些缺點。當我們要繪製紋理或明暗處理多邊形的時候，存在著畫家算法的基本問題 — 透支，其開銷很大，不能夠忽視。早先也注意到，在沿著所有其它的多邊形執行裁剪的時候，看起來也是個低效率的解決方案，實際上，分析並拋棄遮住的部分可能對繼續下去更有吸引力，因為它避免了透支。非常有趣的是，BSP樹可能同樣對後者有極大的幫助。我們即將討論的Beam樹方法，可以同BSP樹一同用於這兩個方麵：對多邊形的排序和追蹤屏幕上哪個區域被繪製。
　　在前一節中，我們已經討論了使我們能夠使用BSP樹獲得多邊形從後到前的順序的算法。也可以用同樣的方式獲得從前到後的順序，隻需逆轉BSP遍曆算法中的調用順序。因此，更靠近觀察者的半空間將首先被遍曆，然後是根多邊形和較遠的半空間遍曆，產生需要的從前到後的順序。
　　獲得的順序中，第一個多邊形最靠近觀察者。既然沒什麽東西能遮擋它，這個多邊形完整地在屏幕上可見，由此被光柵處理。所有其它的多邊形可能完全或部分被第一個遮擋。如果我們沿著第一個多邊形的邊界裁剪剩餘多邊形在屏幕上的投影，並拋除被遮擋的部分，我們實際上把原始問題的大小減小了一個。在列表開頭的新多邊形也是能被完整地看到的（因為它已經被沿著原來第一個多邊形裁剪過了），而且，剩下的多邊形如前麵一樣可能完全或部分被順序列表中新的第一個多邊形遮擋。
　　必須承認，我們必須做大量的裁剪，這相當大地惡化了這種算法。為了更有效地管理裁剪，引入了平麵BSP樹，用來追蹤屏幕上哪個區域剩了下來可用於繪製。不象在前麵考慮的樹， 在這個BSP樹中附加的葉節點將描述最終的凸多邊形區域，其結果形成了細分區域，且沒有相關聯的多邊形。該區域被標記為占用或空。由於2D屏幕邊界裁剪的基本目的基本是一樣的 — 尋找可被光柵處理的圖元部分，這兩個處理過程實際上是統一的。因此我們從描述屏幕區域為空（可繪製）的BSP樹開始，相對應的，在屏幕外的空間被標記為占用。圖7.27演示了初始化的BSP樹和導致的分割部分。

圖7.27 用於空屏幕的Beam樹

　　當一個多邊形必須被繪製的時候，它向下過濾BSP樹。在某些節點可能被分割， 這樣該部分可以在正確的子樹內被明確地檢查。當某一塊到達樹葉，且該葉被標記為占用，我們就知道了這個多邊形實際上被遮擋可以被拋除。另一方麵，當多邊形某塊到達標記為空的葉時，該塊被光柵處理，由於多邊形所在的區域現在被占用了，必須更新BSP樹來反映這一點。
　　考慮圖7.28中的例子。在這個例子中， 要繪製包含E、G、H邊的多邊形。首先沿著追蹤當前屏幕上可見區域的BSP樹根檢驗。在BSP樹根，A邊分割了指定的多邊形。A左側的較小部分要沿著左側子樹檢驗，剩餘部分沿著右側子樹檢驗。在前者的情形下，該小塊到達被占用的節點，因此被拋棄。對後者來說，多邊形沿著B邊檢驗，被上邊分割的要被拋棄。低處的部分進一步到描述屏幕矩形的節點進行檢驗（參見圖7.27，標記為F的節點）。在該點上，我們能夠安全地光柵處理多邊形剩餘的部分，並更新樹，使用多邊形邊進行進一步的分割，同時標記多邊形區域為占用，剩下的標記為空。顯然，當多邊形小塊到達葉節點的時候，該塊整個在葉描述的區域內。因此，任何必要的樹的替換方案都位於子樹的這個區域，並以該葉作為根節點。(參見圖 7.28)

圖7.28 在多邊形被繪製之後的Beam樹

　　在屏幕平麵創建的BSP樹追蹤沒有被遮擋的視線（beam of view），這也是它的名稱的由來。總的來說，在這種算法中，我們從前到後地拾取多邊形，一次隻拾取一個，並在BSP樹中向下進行過濾，同時關聯著屏幕。當多邊形的一部分或多個部分被光柵處理的時候，樹就被更新，以追蹤剩餘的自由空間，這樣，每個連續的多邊性能一致的被檢驗。這樣，透支問題被極大地避免了，盡管如此，這種算法的裁剪數量較大以及實現起來要更複雜。
　　我們在下一章中討論到陰影產生的時候，還要遇到一個使用BSP樹的例子。顯然，這個和其他的分割方案在解決計算機圖形處理的許多問題的時候具有極大的重要性。

7.7、掃描線算法
　　在第六章中我們已經討論過多邊形模型的另一種表度方式，其中的多邊形以邊的形式來描述而不是用頂點的形式。這類表度方式能避免多餘的裁剪且對隱麵消除來說也相當地實用，在這一節中，我們對這種方法作一下分析。掃描線隱麵消除的思路是把可見性確定從多邊形層次轉變到單個的多邊形像素線（參見圖7.29）。這種算法可以被認為是通用多邊形光柵處理的擴展，這種方法我們曾與凹多邊形一起討論過。我們應該看到，這兩種算法的許多思想是一致的。

圖7.29 在每條掃描線上確定隱藏麵

　　在這種算法中，場景中的所有多邊形同時被光柵處理，可見性判定在平麵內執行，該平麵與當前屏幕上的掃描線正交，我們將要在屏幕上判定交叉的多邊形的關係。圖7.30演示了一個例子，三個多邊形被使用這種算法進行光柵處理。能夠看出，多邊形中與掃描線相交的邊的順序的信息對這個算法來說是最至關緊要的。我們能夠在每條掃描線上使用與對凹多邊形光柵處理應用該算法時相同的方法得到這樣的邊順序。有了這個順序後，可見性的判定可以通過相當直截了當的方式完成，假定我們也有多邊形平麵方程。讓我們分析一下在圖7.30中的掃描線1。

圖7.30 不同掃描線上的活動邊

　　在圖7.30中的掃描線1隻與多邊形ABC相交，因此，我們在這些邊中光柵化該多邊形。掃描線2交叉了兩個多邊形， 但交叉邊的順序是這樣的：在遇到多邊形DEF之前我們結束了多邊形ABC的光柵處理。此情形對掃描線3來說不是這樣的。我們開始渲染多邊形ABC，在結束之前，遇到了屬於多邊形EDF的邊DE。在此階段，我們必須在該點上比較這兩個多邊形的深度以判定可見性。如果在此位置對兩個多邊形求平麵方程的值，就可以完成判定。在這個特別的情形下，多邊形DEF的深度較小，因此我們先渲染它。當我們進一步遇到AC邊的時候，我們可以忽略它，因為多邊形DEF的光柵處理還沒有結束，且AC邊屬於早就被判定為較遠的多邊形。
　　在某種意義上，每條邊在端點間定義了一個範圍，在其中的被光柵處理。如果在某些點上多邊形被遮擋，我們仍然必須稍後對其進行光柵處理。這種情形就是掃描線4所演示的（參見圖7.30）。因此，在交叉DF邊之後，我們必須分析多邊形ABC和IJK的深度，在此情形中，光柵處理多邊形ABC。當我們越過AC邊的時候，我們仍然在一個多邊形的範圍內，對此多邊形仍然要進行處理。
　　正如我們看到的，這種分割算法相當容易被實現。我們也取決於這麽一個事實，即在每條掃描線上，我們都有多邊形的排序。如我們所討論的，這種順序可以通過以最小垂直頂點坐標預排序所有的多邊形來獲得，在兩條邊相同的情形中，使用第二個評判標準，比較具有最大垂直坐標的端點的水平坐標。有了這個順序後，我們能夠以增量方式為每條掃描線更新當前邊。一旦我們找到了當前邊，也必須根據當前水平坐標排列。
　　必須強調的是這種算法的優點在於它能夠忽略被遮擋的掃描線的光柵處理。正如我們看到的，如果在場景中使用了複雜的紋理映射或照明的時候，這變得極其重要。這種算法也正確地處理了多邊形相互重疊的情形，但是在形式不變的時候，它不能處理多邊形穿越的情形。使用這種算法也暗示了對已存在的多邊形管道的修改，因為全部多邊形同時被光柵處理有時候並不合算。

7.8、Z-Buffer算法
　　迄今為止的大多數算法都有一個很大的限製，它們處理的對象都模擬為多邊形集。有時候這不是問題。我們光柵處理的內容可能表示為其它各種各樣的圖元形式。即便是在多邊形模型的情形中，當多邊形數量增加的時候，大多數隱麵消除方法的性能出現了不成比例的退化。
　　在本節我們要考慮的算法適合以任何一種方法光柵化任何一種圖元，並且在本質上其工作時間是線性的，這就是說，複雜性與場景中的圖元數量成比例。
　　Z-buffer算法的思路是，它把尋找哪些是可見的，哪些是被遮擋的處理過程從圖元層次或掃描線層次上進一步轉變到了單個的像素層次上。換句話說，每次我們要判定某些圖元的一個像素在圖元光柵處理前是否應該被繪製時， 我們把該像素的顏色同z（深度）坐標存儲在一起。如果某個屬於另一個甚至是同一個圖元的像素必須被繪製在同一個位置上，必須比較z值，且如果新像素實際上更靠近觀察者，則它將替代前麵被繪製上的像素。如果新像素被判定距離更遠，我們在該位置上保留原先的像素。圖7.31演示了兩個被光柵化的圖元位置，使用Z-buffer算法用於隱麵消除。

圖7.31 使用Z-buffer隱麵消除的光柵處理

　　從圖7.31中，我們能夠看出，每個屏幕像素，除了一些圖像位圖的存儲單元之外，還必須分配空間存儲z值。所有z值的數組被存在“Z-buffer”中。
　　在幀渲染的開始，我們必須在Z-buffer中以選定的精度用最遠的z值初始化所有的位置。作為結果，在任意位置獲得的第一個像素將有必要通過算法邏輯的比較允許其被繪製。
　　在多邊形情形中，z坐標的判定可以通過線性插值來完成。我們使用與光柵化明暗強度相同的算法來判定，該方法在光柵處理中內插明暗以及在線性紋理映射中內插紋理坐標。因此，我們將在保留每個像素上的z直到光柵處理階段，沿著邊內插它然後沿著掃描線在邊上使用該值。
　　必須注意到，如果我們應用了透視投影變換，在可用空間中的z坐標不是線性地變化的。比較有吸引力的是使用來代替深度標準，在這樣的空間中是線性變化的。

圖7.32 使用Z-buffer算法處理對象的交叉

　　在Z-buffer算法的眾多優點中，可能它的簡單性是最大的一個優點。由於這種簡單性，它成為了最可能通過硬件實現的算法。它的通用性和本質上的線性運行時間使它對最高級的應用充滿了吸引力。Z-buffer算法的問題可能來自這麽一個事實，即我們隻有極為有限的位數來表度屏幕上像素的z坐標。在某些場合下，我們對z值可能的舍入或截尾引起了對像素的人為幹擾，位數的減少可能引起可見性的錯誤判定。當然，對實現來說，我們必須在光柵處理例程內循環中加入一定數量的代碼。這也導致了某些性能上的惡化，使這種算法對有中等數量圖元的應用沒什麽吸引力。我們必須也要注意到，Z-buffer數組也是相當大的，雖然隨著時間的推移，內存的限製越來越小，但對某些應用來說，用初始值填充Z-buffer可能導致相當可觀的花費。這個算法也很容易受到透支問題的困擾，因為被遮擋的圖元仍然必須被光柵處理。

　　小結
　　總的說來，當我們將圖元從世界投影到屏幕上而獲得虛擬世界的圖像的時候，隱藏麵帶來的問題就會出現在從世界到屏幕的視處理過程中。一些圖元可能會遮擋住屏幕投影中的其他圖元，這樣我們就需要一些方法來將隱藏麵去除掉。對於我們已經討論過的幾種消除隱藏麵的方法，許多都隻能應用於使用多邊形表示的模型。一種比較普通的方法就是按照從後向前的順序對多邊形進行光柵化處理，使得靠近觀察者的多邊形能夠覆蓋掉遠離的觀察者的多邊形。我們有很多方法來將多邊形按照從後向前的順序進行排列。具體的算法包括排序、空間分割等。但是，這種方法在執行光柵化處理的時候係統開銷會很大，因為它要光柵化所有的多邊形，包括被遮擋住的。這時，我們就要考慮采取其它一些看起來效率低下的方法，例如使用Beam樹對多邊形進行反複的裁剪，以避免對不必要的多邊形進行光柵化。
　　Z-buffer方法對圖元的形狀沒有任何的要求，並且它也是最簡單的隱麵消除算法，還經常通過硬件來執行。這種算法同樣要我們對無用的多邊形進行處理。掃描線隱麵消除算法使我們避免了這種情況，但是它隻適用於多邊形模型，同時還要求對多邊形管道進行相當大的改變。
　　隱麵消除算法的運行時間是很難進行比較的，因為它們都有一個基本的不同複雜性的步驟。這樣，具有線性運行時間的算法執行起來可能比具有指數性運行時間的算法執行起來更糟糕。前一種形式的優點通常隻在多邊形的數量非常巨大的時候才能顯現出來。隻有基於一些特殊的情況和對條件進行適當的放寬，才能夠確定選擇哪一種策略。