Carved Marker

Z buffer 和 W buffer 簡介 [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 場景時,要畫出正確的結果,就一定要處理這個問題。

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

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

Painter's algorithm

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

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

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 1] [Part 2]

8/10/2001, Ping-Che Chen


Sorry, Traditional Chinese only. This page is encoded in UTF-8.

Copyright© 2000, 2001 Ping-Che Chen