2008年6月1日 星期日

全景反鋸齒FSAA 簡介

FSAA 是 full scene anti-alias 的縮寫,有些人將其譯為全景反鋸齒,還算是合理。不過,倒底 FSAA 是什麼呢?為什麼要「全景」(full scene)?「半景」不行嗎?(其實相對於 FSAA 的是 edge AA,「邊緣反鋸齒」)反鋸齒(anti-alias)又是怎麼回事呢?


要弄清楚什麼是 FSAA,就得先從 AA(anti-alias)開始。要弄清楚 AA,只好說明一下取樣(sampling)這個麻煩的東西了。對於電腦繪圖有些瞭解的讀者,應該已經知道,目前的電腦繪圖使用的是 2D raster 的顯示方式。也就是說,畫面是由一大堆有不同顏色和不同亮度的小點,組成一個大的方陣。這些小點稱為像點,即 pixel,pixel 是 picture element 的縮寫。很明顯的,像點的數目愈多,圖形就會愈細緻。我們常說的解析度就是指這些像點的數目。例如,640×480 這個解析度,就表示畫面是由 307,200 個像點所組成的。
註:解析度在某些領域有不同的意義。在印刷的情形下,一般所謂的解析度,通常是以 DPI(dots per inch)為單位,即每英吋中含多少個點。像是某個印表機,若有 600 DPI 的解析度,就表示它每英吋可以包含 600 個點。所以,在一張 8.5"×11" 的紙上,就會有 5,100×6,600 = 33,660,000 個點。當然,紙愈大的話,點的數目就可以愈多,這是因為點的大小是固定的。在顯示幕的情形下,不管螢幕有多大,使用 640×480 這個解析度時,像點的數目都是 307,200 個,這和印刷的情形是不同的。當然,通常愈大的螢幕能容許愈高的像點數目。

當然,像點的數目是有限多的。不幸的是,這個世界並不是由有限的小點組成的。好吧!也許它是由有限的小點組成,但是這些小點的數目非常的多,所以以人類巨大的眼睛來看,就好像是完全連續的一樣。這樣一來,用有限的像點來表現畫面,就會出現問題。但是,只要像點的數目夠多,而且像點的大小夠小,小到人類的眼睛無法分辨的情形下,不就沒問題了嗎?當然會有問題,不然就不需要 FSAA 了。

問題在哪裡呢?問題在於取樣的方式。取樣是指把一個連續的訊號,轉換成不連續(離散)的訊號的動作。因為像點的數目是有限多的,所以它一定是不連續的,所以當然就需要這個取樣的動作了。下圖是一個取樣的例子:

**

上圖中,黑色的曲線是原始訊號,灰色是直線是取樣點,下圖則是取樣的結果。簡單的說,就是把曲線上面每個取樣點(就是那些灰色直線所在的地方)的數值取出來,這樣就是取樣的動作。一般來說,取樣點之間的距離是固定的。以電腦圖形的例子來看,每個像點就是取樣點。不過,電腦圖形是從一個二維的訊號中,取樣得到一個二維的陣列。所以,取樣看起來是會損失資訊的。另外,因為電腦是以數位的方式存放資料,所以還要把取樣的結果進行數位化。數位化可以看成是「轉成整數」的動作。例如,假設訊號的範圍是 0 ~ 1 之間,想要數位化成 8 位元的資料,就是先把它乘上 255(8 位元數字可以表示 0 ~ 255 的範圍),然後把結果以四捨五入或是直接捨去的方式轉成整數。這個動作當然也會損失資訊。不過,這部分和我們的主題無關。

取樣會牽扯到很多複雜的定理。例如,在做取樣之前,如果先經過一個 low pass filter,把高頻的部分濾掉,再設定適當的取樣頻率(通常是比是最高頻率的兩倍還大)。這樣處理過的訊號再去取樣,就可以完整還原到原來的訊號(指經過 low pass filter 後的訊號,而不是最原始的訊號)。當然,這篇文章並不是什麼教材,所以不會深入這些地方。不過,low pass filter 等一下會用到,所以先記著比較好。


[Part 2]

現在我們來看看,在電腦繪圖中,取樣的情形是什麼樣子。為了簡單起見,我們用兩個三角形來做例子。如下圖:

**

上圖中,灰色的線是像點的邊界,當然,實際上像點是不會有什麼邊界的,就算有也很細,不會這麼粗。這些邊界只是示意用的。每個像點中的小黑點就是取樣點。取樣的時候,就是取這些小黑點上面的顏色,做為整個像點的顏色。所以,取樣的結果如下圖:


**
我想大家應該都看到鋸齒現象了吧!這就是一般 3D 繪圖中所遇到的情形。為什麼會這樣呢?其實,這是因為我們在取樣之前,少了一個步驟:low pass filter。因此,原來訊號中的高頻部分並沒有去掉,所以才會出現鋸齒現象。對了,所謂的 low pass filter,就是指一個只能讓低頻成分通過的過濾器。詳細的細節就不在這裡說明了。現在只要記住一件事就夠了:box filter 是一種 low pass filter。也就是說,如果我們把一個像點的範圍內,所包含的訊號取其平均值的話,這樣就會是一個 low pass filter。經過這樣的動作,再來做取樣,會得到下圖:

**

把上面的兩個例子都縮小到實際的大小,會得到下圖:

**

兩者之間的差異應該是相當明顯吧!

有些讀者可能會對 low pass filter 有疑問。為什麼用了 low pass filter 消除高頻成分就會有比較好的效果呢?實際的理論相當複雜,所以不在這裡多說。不過,如果以人眼實際上的觀察方式來看,倒是很合理的。因為,人眼內部的感光細胞,是會收集它的感光範圍中的所有能量,再送到腦部。所以,可以看成感光細胞其實就已經包含了一個 box filter。因此,在進行取樣之前,先做 box filter 是很合理的做法。

有一點要特別注意:如果顯示系統的解析度非常的高,遠遠超出人眼可以分辨的範圍,那麼 anti-aliasing 的效果就會慢慢消失。以一般習慣上的閱讀距離來說,人眼很難分辨超過 300 DPI 以上的彩色點。也就是說,對一個對角線為 15" 的顯示器來說,如果解析度高達 3,600×2,700 的話,那就沒有做 anti-alias 的必要了,反正人的眼睛也沒辦法看到這麼細的像點。不過,貼圖的 filtering 是不同的事,無論解析度有多高,都需要適當的貼圖 filtering 才不會出現不正常的情形。


[Part 3]

現在來看看 3D 繪圖晶片要怎麼處理這個問題。目前的 3D 晶片,幾乎都是用 by primitive 的方式畫出整個畫面的。所謂的 by primitive,就是指一次畫一個 primitive,把每一個 primitives 都畫好之後,整個場景就畫好了。Primitive 是指三角面和由許多三角面組成的簡單東西。這種方法和 ray tracing 或是 scanline renderer 是不一樣的。這兩者都是分別對畫面上的每個像點,去決定它應該會是什麼顏色。

另外,現在的 3D 繪圖晶片通常是利用 Z buffer 來去除隱藏面(即被其它三角面蓋住的部分),而不對三角面做任何排序動作。這當然是有原因的,因為如果對三角面做排序,再以「由後面往前面畫」的方式來去除隱藏面的話,有時就需要把某些三角面切開,還有一些很麻煩的東西,這樣的工作並不適合由記憶體很少的 3D 繪圖晶片來做。當然,讓 CPU 來做這個工作,速度也不會很快。無論如何,Z buffer(或是其它類似的方法)還是目前最有效率的方法之一。

現在來看看 3D 晶片要怎麼做到 anti-alias。一個最簡單的想法是,讓 3D 晶片在畫三角面的時候,就自動產生適當的「佔有率」數字,即這個三角面在某個特定的像點上,所佔有的面積的比例,而該像點的顏色則會乘上這個比例。這樣一來,就可以畫出平滑的三角面了。當然,對於三角面來說,三角面的內部像點所佔的面積比例當然都是 100%,只有在邊緣的地方才會有小於 100% 的佔有率。所以,這個方法也稱為 edge anti-alias。

不過,這個方法有一些問題。例如,當兩個三角面有重疊的時候,「佔有率」的計算就會出問題,因為 3D 晶片只知道將被蓋住的三角面,其佔有率的數字;但是,它卻沒辦法知道被蓋住的三角面,倒底是佔有哪些部分。最嚴重的問題,則是出現在三角面有交叉的時候。這時,因為交叉的地方是由 Z buffer 算出來的,所以根本沒辦法算出正確的「佔有率」數字。所以,除非三角面都沒有交叉,而且重疊的情形都還在合理範圍,不然的話,這個方法是不能用的。如果三角面都已經排序且切割過,那就可以使用這個方法。但是,就如同前面所說的,目前不太可能即時做這些動作。

如果需要畫的東西不是三角面,而只是線框的話,那麼 edge anti-alias 就很適用了。因為,線框很少會有交叉的現象(兩條線就算是交叉,也沒人會注意到吧!),而且,兩條線重疊的情形也不多。所以,edge anti-alias 非常適用在線框繪圖。某些應用像是 CAD/CAM 等等,特別常用到線框繪圖,所以他們會喜歡用 edge anti-alias。不過,對於模擬、視覺化、或是 3D 遊戲來說,線框繪圖很少用到,所以 edge anti-alias 就不太適用。

另外有一點要注意的是,edge anti-alias 只處理三角面的邊緣部分。當然高頻成分也是在邊緣最為明顯。但是,如果三角面有貼圖的話,還是可能會出現高頻成分。不過,一般來說,貼圖的 anti-alias 通常可以很容易用雙線性內插(bilinear interpolation)和 mipmap 來解決。這部分比較複雜,以後再特別討論。

說了這麼多,終於要說到 FSAA 了。為什麼叫 full scene 呢?它就是指對整個畫面做 anti-alias,而不是像 edge anti-alias 只是對某個 primitive(如三角面或是線)做 anti-alias。那麼,要怎樣對整個畫面來做 anti-alias?

一個簡單的方法,就是使用在每個像點中,取幾個 sub-sample 點,然後把這些 sub-sample 的顏色取平均值,做為這個像點的顏色。這樣的方法就稱為 super-sampling。很明顯的,這種做法完全不需要什麼特別的設計,不用切三角面,不用排序,直接就可以得到 anti-alias 的效果。所以這是一種 FSAA 的方法。

最簡單的 super-sampling 方法是 ordered grid super-sampling,簡稱 OGSS。所謂的 OGSS,就是把直接把解析度提高,再用 box filter 把它縮小。例如,假設要對 640×480 的解析度,做 4 個 sample 的 FSAA,那就把解析度提高為 1280×960,畫出整個畫面,然後再用 box filter 把它縮小到 640×480。為什麼稱為 OGSS 是因為它的 sub-sample 點等於是排成方形,如下圖所示:


***

上圖中,左邊是原來的解析度方式,大的灰色圓點是原來的取樣點。放大解析度為四倍之後(每邊各兩倍),會變成右邊的情形。這時,在新的解析度下,新的取樣點是紅色小點。對每個原來的像點來說,它會取內部的四個紅色小點的平均值,做為它的取樣值。所以,這些紅色小點就是它的 sub-sample 點。可以看出,它的 sub-sample 點正是排成方形,所以才會叫做 OGSS。


[Part 4]

OGSS 有什麼缺點嗎?要看出它的缺點,得先看下面這張圖:


***

上圖中的這些三角面,顯示出邊線的角度和 aliasing 程度的關聯。從最左邊的三角形來看,可以看出完全垂直線、完全水平線和 45°的斜線,都不太會顯示出 aliasing。但是,接近垂直或接近水平的線,會顯示出最明顯的 aliasing。不幸的是,因為 OGSS 的 sub-sample 點是垂直和水平的排列,所以在處理接近垂直或水平的線時,通常只有兩個 sub-sample 會發生作用。如下圖所示:

**

在上圖中,當深藍色的三角形經過這些 sub-sample 點時,可以看出這三種方法,會得到明顯不同的結果。在兩個 OGSS 的例子中,每個像點都剛好有一半的 sub-sample 點包含在三角形裡面,所以它們的表現是完全相同的。當然,如果三角面再延長一些,4 samples 的 OGSS 的表現就會比 2 samples OGSS 要好一點。但是,這已經可以顯示出 OGSS 的表現,在接近垂直或接近水平的線,是不太好的。事實上,在線愈接近 45° 時,OGSS 的表現就會愈好。但是,前面也提過,45° 的線其 alias 的現象並不會很嚴重。再者,如果線真的是 45°,那 OGSS 的結果還是不會好,因為每個邊緣的像點,都會剛好有三個 sub-sample 點在三角面裡面(或外面),而正確的值應該是兩個。

如果把 sub-sample 點稍微轉動一下,情形就會改觀了。如果不希望在接近 45° 的時候會有較好的結果,那只要把 sub-sample 點轉動一些角度,就會讓接近垂直或水平的線對每個像點的 sub-sample 點「看起來」像是 45° 了。在上面的圖中就可以看到明顯的結果。因為 sub-sample 被轉動某個角度,所以這個方法稱為 rotate grid super-sampling,簡稱 RGSS。

很明顯的,RGSS 是不能用「提高解析度」這個方法來達成的。那要怎麼做到 RGSS 呢?基本上,方法並不難。只要在畫三角面的時候,把每個三角面稍微移動位置,這樣就和移動像點的取樣點,是同樣的效果。所以,要做到像上圖的 RGSS,只要把整個場景畫四次,每次都稍微移動每個三角面,到適當的取樣點位置(移動的範圍會小於一個像點的大小)。最後,再把這四張圖合起來,對每個像點取平均值,就可以得到結果了。傳統上,這可以利用 accumulation buffer 來達到。不過,accumulation buffer 需要很大的頻寬(每次從 frame buffer 複製到 accumulation buffer 需要兩次讀取和一次寫入),而且 accumulation buffer 通常需要比一般 frame buffer 更高的精確度才行,所以又需要更多頻寬。再加上 4 samples 的 FSAA 已經需要把整個場景畫出四次了,所以速度一定會很慢。

另一個方法是利用多個 frame buffer,這也是 3dfx 的 T-Buffer 的原理。這個方法是讓顯示晶片保有四個不同的 frame buffer,並把四個 sub-sample 的圖分別畫到這四個 frame buffer 中。而顯示晶片的 RAMDAC(把 frame buffer 輸出到螢幕上的裝置)則自動把這四個 frame buffer 的內容做平均。這樣一來,就不需要高精確度的 accumulation buffer,而且也沒有明顯的額外頻寬需求。因此,對於 sample 的數目很少的情形下,這的確是個取代 accumulation buffer 的好方法。

現在 DirectX 8 中的 DirectGraphics 也加入了 multi-sample buffer 的支援,基本上就和 3dfx 的 T-Buffer 是完全相同的。所以,將來的 3D 顯示晶片都很可能會支援這樣的功能。

沒有留言: