Z buffer 和 W buffer 簡介

待我称王封你为后i 2022-09-29 14:55 93阅读 0赞

目录：  
　　 [Part 1][]  
　　 [Part 2][]  
  
文档内容：  
**\[Part 1\]**  
  
幾乎所有目前的 3D 顯示晶片都有 Z buffer 或 W buffer。不過，還是常常可以看到有人對 Z buffer 和 W buffer 有一些基本的問題，像是 Z buffer 的用途、Z buffer 和 W buffer 的差別、或是一些精確度上的問題等等。這篇文章的目的就是要簡單介紹一下 Z buffer 和 W buffer。

Z buffer 和 W buffer 是做什麼用的呢？它們的主要目的，就是**去除隱藏面**，也就是 Hidden surface elimination（或是**找出可見面**，Visible surface detemination，這是同樣意思）。在 3D 繪圖中，只要有兩個以上的三角面，就可能會出現某個三角面會遮住另一個三角面的情形。這是很明顯的現象，因為近的東西總是會遮住遠的（假設這些三角面都是不透明的）。所以，在繪製 3D 場景時，要畫出正確的結果，就一定要處理這個問題。

不過，這個問題是相當困難的，因為它牽扯到三角面之間的關係，而不只是某個三角面本身而已。所以，在做去除隱藏面的動作時，是需要考慮場景中所有的三角面的。這讓問題變得相當的複雜。而且，三角面往往並不是整個被遮住，而常常是只有一部分被遮住。所以，這讓問題變得更複雜。

要做到去除隱藏面的最簡單方法，就是「畫家演[算法][Link 1]」（Painter's algorithm）。這個方法的原理非常簡單，也就是先畫遠的東西，再畫近的東西。這樣一來，近的東西自然就會蓋住遠的東西了。因為油畫的畫家通常會用這樣的方法，所以這個方法被稱為「畫家演算法」。下圖是一個例子：

![Painter's algorithm][Painter_s algorithm]

上圖中，紅色的圓形最遠，所以最先畫。然後是黃色的三角形，最後是灰色的方形。照遠近的順序來畫，就可以達到去除隱藏面的效果。所以，只要把 3D 場景中的三角面，以對觀察者的距離遠近排序，再從遠的三角面開始畫，應該就可以畫出正確的結果了。

不過，實際上並沒有這麼理想。在 3D 場景中，一個三角面可能有些地方遠，有些地方近，因為三角面有三個頂點，而這三個頂點和觀察者的距離，通常都是不同的。所以，要以哪個頂點來排序呢？或是以三角面的中心來排序？事實上，不管以什麼為依據來排序，都可能會有問題。下圖是一個「畫家演算法」無法解決的情形：

![Painter's algorithm failed][Painter_s algorithm failed]

上圖中，三個三角面互相遮住對方，所以不管用什麼順序去畫，都無法得到正確的結果。另外，這個方法也無法處理三角面有交叉的情形。

當然，如果相當確定場景中不會出現這麼奇怪的情形，那「畫家演算法」一般還是可以用的。不過，它還有一個很大的問題，就是效率不佳。首先，畫家演算法需要對場景中，在視角範圍內所有的三角面做一個排序的動作。最好的排序演算法也需要 O(*n log n*) 的時間。也就是說，（大致上來說）如果三角面的數目從一千個變一萬個，排序需要的時間會變成約 13.3 倍。而且，因為這需要對場景中所有的三角面來做，因此也不適合用特別的硬體來做加速。另外，這個方法還有一個很大的問題，就是它會花很多時間去畫一些根本就會被遮住的部分，因為每個三角面的每個 pixel 都需要畫出來。這也會讓效率變差。

如果場景是靜態（不動）的，只有觀察者會變動的話，那是有方法可以加快排序的速度。一個很常用的方法是 **binary space paritioning**（BSP）。這個方法需要事先對場景建立一個樹狀結構。建立這個結構後，不管觀察者的位置、角度是如何，都可以很快找出正確的繪製順序。而且，BSP 會視需要切開三角面，以處理像上圖那樣，三個三角面互相遮住對方的情形。

不過，BSP 結構在建立時，要花很多時間，所以不太可能即時運算。因此，通常只能用在場景中的靜態部分，而會動的部分還是需要另外排序。而且，BSP 常會需要切開三角面，也會讓三角面的數目增加。另外，BSP 仍然無法解決需要畫出那些被遮住的 pixel 的問題。

另一種去除隱藏面的方法，是直接以 pixel 為單位，而不是以三角面為單位，來考慮這個問題。其中最簡單的方法是由 Catmull 在 1974 年時提出來的，也就是 *Z buffer*（或稱 *depth buffer*）。這個方法非常簡單，又容易由特別設計的硬體來執行，所以在記憶體容量不再是問題後，就變得非常受歡迎。

Z buffer 的原理非常簡單。在繪製 3D 場景時，除了存放繪製結果的 frame buffer 外，另外再使用一個額外的空間，也就是 Z buffer。Z buffer 記錄 frame buffer 上，每個 pixel 和觀察者的距離，也就是 Z 值。在開始繪製場景前，先把 Z buffer 中所有的值先設定成無限遠。然後，在繪製三角面時，對三角面的每個 pixel 計算該 pixel 的 Z 值，並和 Z buffer 中存放的 Z 值相比較。如果 Z buffer 中的 Z 值較大，就表示目前要畫的 pixel 是比較近的，所以應該要畫上去，並同時更新 Z buffer 中的 Z 值。如果 Z buffer 中的 Z 值較小，那就表示目前要畫的 pixel 是比較遠的，會被目前 frame buffer 中的 pixel 遮住，所以就不需要畫，也不用更新 Z 值。這樣一來，就可以用任意的順序去畫這些三角面，即可得到正確的繪製結果。下圖是一個例子：

![An example of Z buffer][]

上圖中，紅色的三角面雖然先畫出來，但是因為使用了 Z buffer，所以後畫的黃色方塊還是只會遮住適當的部分，而不會連較近的部分都遮住。這就顯示出 Z buffer 的效果。

實際上 Z buffer 中能存放的數字當然會有一定的限度，所以通常會把 Z 值縮小到 0 ~ 1 的範圍。因此，在繪製 3D 場景時，就會需要把可能出現的 Z 值限制在某個範圍內。通常是用兩個和投影平面平行的平面，把所有超出這兩個平面範圍的三角面都切掉。這兩個平面通常分別稱為 Z near 和 Z far，分別表示較近的平面和較遠的平面。而在 Z near 平面的 Z 值為 0，在 Z far 的 Z 值為 1。

在效率上 Z buffer 並不一定會比「畫家演算法」要快。但是，它比較簡單。而且，它的效率和三角面的數目並沒有太大的關係，而是和繪製的 pixel 數目有關。所以，而且可以很容易設計出特定的 3D 硬體來做這個動作，而不需要由 CPU 來做。而 Z buffer 所需要的額外記憶體，在今天已經顯得不是很重要。所以現在幾乎所有的 3D 顯示晶片都是使用 Z buffer。

不過，Z buffer 並非全無問題。一個很大的問題是在於精確度上。如果有兩個三角面很靠近，而其中一個完全在另一個之前，那應該只能看到一個三角面才對。但是，如果 Z buffer 的精確度不夠，那這兩個三角面每個 pixel 的 Z 值可能會很接近。再加上計算出來的 Z 值一定會有誤差，所以，很可能會造成應該被遮住的三角面，卻有一些 pixel 沒有被遮住。這種情形稱為 *Z fighting*。下圖中，球在地面上的影子就是一個例子：

![An example of Z fighting][]

要避免這類問題，就要避免在場景中出現太過靠近，且接近平行的三角面。一般的場景不太會出現這個情形。不過，Z buffer 的精確度問題並不只是這樣而已。在下一部分會對這個問題有更詳細的說明。  
  
  
**\[Part 2\]**  
  
前面把 Z buffer 的原理做了一個大概的說明，聽起來 Z buffer 似乎是個很理想的技術。但是，實際上 Z buffer 有一個很大的問題，就是精確度的問題。

在前一頁後面所提到的，兩個非常接近的平面所出現的 Z fighting 情形，其實是相當少見，而且很容易避免的。當然，遇而還是會看到有一些遊戲會出現這種情形。不過，Z buffer 最嚴重的問題是在離觀察者較遠的部分。如果 Z buffer 的精確度不夠，而場景又很遠的的話，那遠處的東西就會出現一些非常奇怪的現象。下圖是一個例子：

<table style="color:rgb(54,46,43); font-family:Arial; font-size:14px"> 
 <tbody> 
  <tr> 
   <td><span style="font-size:12px"><img height="240" alt="Z aliasing" src="http://dev.gameres.com/Program/Visual/3D/zwbuf_z_aliasing.jpg" width="320" style="border:none; max-width:100%"></span></td> 
   <td><span style="font-size:12px"><img height="240" alt="No Z aliasing" src="http://dev.gameres.com/Program/Visual/3D/zwbuf_z_normal.jpg" width="320" style="border:none; max-width:100%"></span></td> 
  </tr> 
  <tr> 
   <td><span style="font-size:12px">Z aliasing</span></td> 
   <td><span style="font-size:12px">無 Z aliasing</span></td> 
  </tr> 
 </tbody> 
</table>

當然，上面的例子是比較極端的情形。實際上一般情形下並不會有這麼誇張的 Z aliasing 現象。不過，我相信大家多少都在一些場景較大的遊戲中，看過類似的情形。

為什麼會有這樣的現象呢？這就要從 Z buffer 的結構談起了。如果前一頁所說的，一般的顯示晶片，是把 Z 值限制在 0 ~ 1 的範圍，再用一個定點數去表示它。例如，一個 16 位元的 Z buffer，可能會用 0 ~ 65535（一個 16 位元數字可表示的範圍）來表示這個 0 ~ 1 之間的 Z 值。

如果 Z buffer 的分布在 eye space 中是線性的，也就是它的每個數字之間的間隔都相等的話，那這樣的精確度應該是蠻高的才對。因為，假設觀察者可以看到一公里遠的東西，那每個間隔就是約 1.5 公分。如果用更高精確度的數字來表示的話（像是 24 位元數字），那精確度還會更高。然而，Z buffer 在 eye space 中並不是線性的。它是在 projection space 中為線性。

如果你覺得這些聽起來像是外星話的話，現在就要來「翻譯」這些外星話。首先，先來看一張示意圖：

![Hyperbolic Z][]

上圖是一個眼睛在透視投影的情形下，觀看場景中的一個紅色平面的情形。靠近眼睛的平面（上面有黃色點的）是代表投影平面，也就是 3D 繪圖中的螢幕。黃色的點紅色平面投影到螢幕上的 pixel，他們當然是等間距的。但是，注意看這些「等間距」的 pixel，他們所對映的 Z 值（也就是 Z 軸上的那些灰色的點），並不是等間距的。實際上，離眼睛愈遠的 pixel，其 Z 軸上的間距就愈大。

這其實透視投影的一個明顯的性質。因為在透視投影的情形下，愈遠的東西看起來愈小，所以，在螢幕上同樣的間距，在比較遠的地方，就會變得比較大。因此，雖然三角面是平面，但是它在每個 pixel 上的 Z 值卻不是線性的變化。因此，就無法用線性內插來計算三角形內部的 pixel 的 Z 值。但是，要正確計算出每個 pixel 上的 Z 值，會需要一個除法的動作，而除法是很討厭、很花時間的動作。

早期的顯示晶片無法花費一個除法器在 Z buffer 上面。所以，一個方法是在 Z buffer 中，不要存放 eye space 的 Z 值，而改成存放 projection space 的 Z 值。這樣一來，Z 值在 projection space 就會變成是線性的，就可以簡單地用線性內插來計算三角形內部的 pixel 的 Z 值了。這也是目前幾乎所有顯示晶片的 Z buffer 的設計。

不過，在 projection space 中的 Z 值，就像上面的圖所顯示的一樣，有一個很重要的特性：它所對映的 eye space 的 Z 值間隔，在愈遠的地方就愈大。所以，Z buffer 的精確度，如果以 eye space 來看的話（這樣看才有意義），就會變成不平均的分布。離觀察者愈近的地方，其精確度會比遠的地方更高。而這個精確度的變化，會取決於 Z near 平面和 Z far 平面的位置。Z near 平面離觀察者愈近，且 Z far 平面離觀察者愈遠，則精確度的變化就會愈大，也就是遠的地方的精確度會愈差。

在這一頁最前面的兩張圖中，其 Z far 平面的位置是一樣的，但是左圖的 Z near 平面的位置，比右圖的 Z near 平面的位置近了一千倍。所以，在左圖中就出現了嚴重的 Z aliasing 現象，但是右圖就沒有出現這種現象。

所以，要儘可能避免 Z aliasing 現象，就要儘可能把 Z near 平面拉遠，而把 Z far 平面拉近。但是，實際上很多情形下，是無法允許這樣的設計的。比如說，在一個場景中，玩家可能會看到 50 公分遠的桌子上的東西，而同時看到窗外在一公里外的一座大基地。因此，Z near 平面不能設得比 50 公分要遠，但是 Z far 平面又得到一公里遠。以 16 位元 Z buffer 來看，那最遠處的間隔（也就是一公里遠的地方）會達到 30 公尺，也就是如果兩個 pixel 的間距小於 30 公尺的話，Z buffer 將無法分辨出正確的順序！而它在 Z near 處（也就是 50 公分的地方）的精確度則高達 0.0000076 公尺。這顯示出精確度分布是如此的不平均和不適當。如果改用 24 位元 Z buffer 的話，那情形會有相當程度的改善，在一公里遠處的精確度會提高到約 12 公分。這也是為什麼 24 位元 Z buffer 很少會顯示出 Z aliasing 的情形。

不過，即使是 24 位元 Z buffer 也不見得是完全理想。以上面的例子來說，如果 Z near 平面移到 10 公分處，在遠處的精確度就會從 12 公分降低為 60 公分。有些人可能會覺得，在一公里遠的地方，又有誰能分辨 60 公分，或是 12 公分呢？但是，問題在於，當兩個大的平面的距離小於 60 公分時，因為 Z buffer 無法分辨出正確的順序，就可能會在這一框是某個平面被畫出來，而在下一框卻變成是另一個平面被畫出來。如果這兩個平面的顏色差別很大，就會產生閃爍的現象，任何人都會很容易就注意到的。

有些顯示晶片採取一些方法來解決這個問題。一個簡單的想法是在 Z buffer 中使用浮點數，而不使用定點數。經過適當的設計，浮點數可以在某個特定的數字附近，提供更大的精確度範圍（一般情形是在 0 附近）。而一般的 Z buffer 在 Z far 附近會需要更高的精確度，所以可以把 Z buffer 在 Z far 平面以 0 表示，而 Z near 平面以 1 表示。這樣就可以得到更高的精確度。不過，浮點數在計算上比較麻煩。特別是 Z buffer 的運算中，常需要做加法和比較的運算，這都會比定點數的運算要麻煩很多。

另外一個方法是用非線性的 Z buffer。例如，可以把 Z buffer 切成很多個小區間，而每一個小區間中都是一般的線性 Z buffer。但是，可以在遠方分配更多的小區間，讓它的精確度可以提高。這也是一種解決精確度問題的方式。

其實，要解決 Z buffer 精確度問題，最簡單的方法就是在 eye space 中做線性內插。但是，前面已經說過，在 eye space 中的線性，在 projection space 並不一定是線性，所以它會需要額外的除法器。不過，有一個方法可以避免使用除法器，而只需要「倒數器」，「倒數器」比完整的除法器要簡單一些。這個方法就是先以較高的精確度，在 projection space 中，對 Z 做線性內插。對每個內插得到的結果，再用倒數器算出其倒數，也就是所謂的 W 值。這個 W 值的精確度可以較低，因為它在 eye space 中的分布是平均的。最後，再把這個 W 值和 "W buffer" 裡面的值做比較，就可以得到正確的順序。這個方法，相信有些人已經猜到了，就是**W buffering**。

當然，另外還有一些別的方法可以實作出 W buffer。不過，不管是用什麼方法實作 W buffer，其最重要的性質就是在 eye space 中為線性分布。因此，16 位元的 W buffer 在遠處的精確度是非常理想的。以前面的例子來說，即使是 24 位元 Z buffer，在一公里遠處的精確度也只能到 12 公分。但是 16 位元 W buffer 則是每個地方的精確度都是 1.5 公分。因此，在這個例子中，16 位元 W buffer 在遠處的表現，甚至比 24 位元 Z buffer 更好。

而且，W buffer 還有一個好處，就是其 W near 平面（相對於 Z buffer 中的 Z near 平面）的位置是不重要的。也就是說，W buffer 可以同時兼顧眼前的桌子，和數公里外的巨大基地。而用 Z buffer 的話，如果想要能正確顯示出數公里外的巨大基地，那可能就得犧牲眼前的桌子了。

不過，因為 W buffer 的精確度是平均分布，它在 Z near 處的精確度就明顯不如 Z buffer 了。雖然說 Z buffer 在 Z near 處的精確度是過於高了（像是 0.0000076 公尺），但是，W buffer 卻可能會過於低。比如說，1.5 公分的精確度對於遠處的物體是絕對足夠的，但是對於靠近觀察者的物體，則是明顯的不足。比如說，桌上可能有一本厚度小於 1.5 公分的書。這時，1.5 公分的精確度是完全不夠的。

這樣聽起來，好像 W buffer 也無法解決問題嘛！其實並不是這樣的。如果有 24 位元的 W buffer，同時可以看到十公里外的東西（這應該算是非常的遠了），那它的精確度還是有約 0.6 公厘左右。這樣的精確度一般來說是相當足夠的了。而且 W buffer 也很容易使用，不需要對程式有什麼重大的修改。

目前 W buffer 最大的問題就是支援度不夠。有些顯示晶片根本就不支援 W buffer，而有些則只支援 16 位元的 W buffer。不過，目前很多顯示晶片都已經開始支援 W buffer，所以將來應該會有更多遊戲使用吧！

[Part 1]: http://dev.gameres.com/Program/Visual/3D/ZWBuf.htm#Part%201
[Part 2]: http://dev.gameres.com/Program/Visual/3D/ZWBuf.htm#Part%202
[Link 1]: http://lib.csdn.net/base/datastructure
[Painter_s algorithm]: /images/20220708/ecba9ef78a8143718e2b0471f5dfd2b5.png
[Painter_s algorithm failed]: /images/20220708/49387bda4ce042178bf8c4226dca43a3.png
[An example of Z buffer]: /images/20220708/69aa481184c54aa6a8f9a73a0a2ebb1b.png
[An example of Z fighting]: /images/20220708/2294ca444dc5460bb3e3559e1e6fcf93.png
[Hyperbolic Z]: /images/20220708/ee04b852998047c986aa5e4007e0b8b6.png