有趣的深度圖：可見性問題的解法

01-24

0x00 前言

說起深度，朋友們一定都不陌生。為了解決渲染場景時哪部分可見，哪部分不可見的問題（即可見性問題，也被稱為隱藏面移除問題，hidden surface removal problem，從術語這個角度看，技術的發展有時也會帶動心態向積極的方向的變化），計算機圖形學中常使用畫家演算法或深度緩衝的方式。

這也是在處理可見性問題時的兩個大方向上的思路：Object space方式和Image space方式。在後文的描述中，各位應該能夠體驗到這兩種方式的異同。

下圖就是在Unity引擎中將深度緩衝的數據保存成的圖片。

而利用深度圖我們又可以實現很多有趣的視覺效果，例如一些很有科幻感的效果等等。

不過在說到這些有趣的效果之前，我們先來看看所謂的可見性問題和深度圖的由來吧。

0x01 人類的本能和畫家演算法

在計算機圖形學中，有一個很重要的問題需要解決，即可見性問題。因為我們要將一個3D模型投影到2D的平面上，這個過程中哪些多邊形是可見的，哪些是不可見的必須要正確的處理。

按照人類的天性，一個最簡單的解決方案就是先繪製最遠的場景，之後從遠及近，依次用近處的場景覆蓋遠處的場景。這就好比是一個畫家畫畫一樣。

（圖片來自維基百科）

而計算機圖形學中的畫家演算法的思想便是如此：

首先將待渲染的場景中的多邊形根據深度進行排序。
之後按照順序進行繪製。

這種方法通常會將不可見的部分覆蓋，這樣就可以解決可見性問題。

但是，世界上就怕但是二字，使用畫家演算法這種比較樸素的演算法的確能解決簡單的可見性問題，不過遇到一些特殊的情況就無能為力。例如下面這個小例子：

在這個例子中，三個多邊形A、B、C互相重疊，那麼到底如何對它們進行排序呢？此時我們無法確定哪個多邊形在上，哪個多邊形在下。在這種情況下，多邊形作為一個整體進行深度排序已經不靠譜了，因此必須用一些方法對這些多邊形進行切分、排序。

我們可以看到，這種方式是以場景中的對象或者說多邊形為單位進行操作的。因而常常被稱為Object space 方法或者稱為Object precision 方法，我個人更喜歡後者這個稱呼，因為這是一個關於操作精度的區別。這種方式主要是在對象或多邊形這個級別的，即對比多邊形的前後關係。除了畫家演算法之外，背面剔除也是Object Space的方法。它通過判斷面的法線和觀察者的角度來確定哪些面需要被剔除。

0x02 切分多邊形的Newell演算法

既然作為整體互相重疊導致難以排序，那麼是否可以對多邊形進行切分呢？Newell演算法早在1972年就已經被提出了，所以算不得是什麼新東西。但是它的一些思路還是很有趣的，倒也值得我們學習。

和畫家演算法一樣，Newell演算法同樣會按照深度對場景內的對象進行排序並對排序後的多邊形從遠及近的依次繪製，不過有時會將場景內的多邊形進行切割成多個多邊形，之後再重新排序。

簡單來說，首先我們可以將參與排序的結構定義為各個多邊形上頂點的最大Z值和最小Z值[Zmax，Zmin]。

我們會以多邊形上距離觀察者最遠的頂點的Z值對場景內的多邊形進行一個粗略的排序（因為此時只是依據每個多邊形距離觀察者最遠的那一個頂點的Z值進行排序），這樣我們就獲得了一個多邊形列表。

之後，取列表中的最後一個多邊形P（它的某個頂點是距離觀察者最遠的頂點）和P之前的一個多邊形Q，之後通過對比來確定P是否可以被寫入幀緩衝區。

這個對比簡單的說就是是否符合下面這個條件：

多邊形P的Zmin > 多邊形Q的Zmax

如果符合該條件，則P不會遮蓋Q的任何部分，此時可以將P寫入幀緩衝區。

即便答案是否，P和Q也有可能不發生遮蓋。例如它們在x、y上並無重疊。但是，Q還是有可能會被分割成若干個多邊形{Q1，Q2...}。此時有可能會針對下面的幾條測試結果，對最初的多邊形列表進行重新排序（也有可能生成新的多邊形，將新的多邊形也納入最初的列表中）並決定渲染的順序。

多邊形P和多邊形Q在X軸上是否可區分？
多邊形P和多邊形Q在Y軸上是否可區分？
多邊形P是否完全在多邊形Q的後方？
多邊形Q是否完全在多邊形P的前方？
判斷兩個多邊形的投影是否重疊？

如果這幾條測試全部都沒有通過，則需要對Q或P進行切割，例如將Q切割成Q1、Q2，則Q1和Q2將被插入多邊形列表代替Q。

但是，我們可以發現，這種對深度進行排序後再依次渲染的方式會使得列表中多邊形的每個點都被渲染，即便是不可見的點也會被渲染一遍。因此當場景內的多邊形過多時，畫家演算法或Newell演算法會過度的消耗計算機的資源。

0x03 有趣的Depth Buffer

正是由於畫家演算法存在的這些缺點，一些新的技術開始得到發展。而深度緩衝（depth buffer或z-buffer）就是這樣的一種技術。Depth Buffer技術可以看作是畫家演算法的一個發展，不過它並非對多邊形進行深度排序，而是根據逐個像素的信息解決深度衝突的問題，並且拋棄了對於深度渲染順序的依賴。

因而，Depth Buffer這種方式是一種典型的Image space 方法，或者被稱為Image precision方法，因為這種方式的精度是像素級的，它對比的是像素/片元級別的深度信息。

這樣，除了用來保存每個像素的顏色信息的顏色緩衝區之外，我們還需要一個緩衝區用來保存每個像素的深度信息，並且兩個緩衝區的大小顯然要一致。

該演算法的過程並不複雜：

首先，需要初始化緩衝區，顏色緩衝區往往被設置為背景色。而深度緩衝區則被設為最大深度值，例如經過投影之後，深度值往往在[0，1]之間，因此可以設置為1。
經過光柵化之後，計算每個多邊形上每個片元的Z值，並和對應位置上的深度緩衝區中的值作比較。
如果z <= Zbuffer[x][y]（即距離觀察者更近），則需要同時修改兩個緩衝區：將對應位置的顏色緩衝區的值修改為該片元的顏色，將對應位置的深度緩衝區的值修改為該片元的深度。即：Color[x][y] = color; Zbuffer[x][y] = z；

下面是一個小例子的圖示，當然由於沒有經過標準化，因此它的各個坐標和深度值沒有在[0-1]的範圍內，不過這不影響：