Part 1]

在這篇文章中，我們會從數位訊號處理的理論角度來看 3D 電腦繪圖中的 antialiasing 問題。當然，這並不是教科書（我也沒能力寫教科書 :P），所以我會儘可能避開數學式，而只是從觀念的角度來說明這個問題。

首先，我們從數位訊號的基礎來看。因為我們現在所用的電腦，幾乎都是數位電腦，所以它們當然也只能處理數位的資料。所謂的數位資料，其實就是一堆數字，或更正確的說，一堆整數。因為數位電腦只能處理 0 和 1，所以它們所能處理的東西，可以說都是有限的整數。當然，我們可以用一些整數來表示有理數（用分數來表示），所以數位電腦也可以用來處理一些小數。

不過，有很多東西不是用有理數就可以表示的。不過，這還不是最大的問題。最大的問題是，很多訊號都是連續的。這裡所謂的連續，並不是微積分裡面的那種連續，而只是說訊號就像一個實數函數一樣，在任何參數上都有值。這告訴我們，即使是隨便一小段訊號，都需要用無限多個數字才能表示。很明顯的，數位電腦是不能存放無限多個數字的。下圖是一個例子：

在上圖中，垂直方向是訊號的強度，在影像中就是 intensity。而水平方向則是訊號的位置，我們稱為 spatial domain。如果是聲音訊號的話，那它就不是位置，而是時間了，也就是 time domain。不過，因為我們這裡只討論影像，所以基本上水平方向就是 spatial domain。

不過，因為這樣的訊號是連續的，所以，就像前面所說的，需要無限多個數字才能存放這個訊號。但是電腦不能存放無限多個數字，所以，只好取其中的一些數字。比如說，如果上圖中垂直方向的虛線，就是 pixel 的邊界，那我們可以只取訊號中，在 pixel 正中間的值。這樣我們只需要存放八個數字。這就是所謂的取樣（sampling）。以上例來說，取樣得到的八個數字分別是 0.548、0.468、0.760、0.296、0.400、0.348、0.460、和 0.507。這些取樣得到的數字，就形成了數位訊號。

這些數位訊號在經過處理後（所謂的處理，也許只是存放在某個地方，像是光碟片裡面），最後還是需要讓人看到結果。因為人是沒辦法光從一堆數字就看得出來那是什麼東西，所以，一定要設法把這些數位訊號，再轉換成連續的、人可以接受訊號（像是顯示在螢幕上，或是對聲音訊號來說，用喇叭發出聲音）。這個過程就稱為重建（reconstruction）。比如說，上面的數位訊號，利用 sample and hold 的方式重建的話（也就是說，在整個 pixel 的範圍中，都輸出該 pixel 的取樣值），會變成如下圖：

不用說，這是一個蠻差的重建方式，因為它重建出來的訊號，和原來的訊號實在是相差太多了。不過，其實這也是沒辦法的事，因為對一個連續的訊號（原來需要無限多個數字才能表示），只用八個數字來表示，本來就會丟失很多資訊。不過，我們當然還是希望能夠儘可能達到最好的效果。這就是理論發揮作用的時候了。

[Part 2]

究竟在取樣的時候，發生了什麼事呢？這就得從 frequency domain 的角度來看了。所謂的 frequency domain，就是指訊號所擁有的各種頻率的成份。也就是說，我們可以用一大堆不同頻率的正弦波，合成我們所要的訊號。或是說，我們要找出我們所要的訊號，是由哪些不同頻率、不同強度、和不同相位的正弦波所組成的。這可以利用 Fourier transform 把一個訊號從 spatial domain 或 time domain 轉換成 frequency domain，或利用 inverse Fourier transform 把它從 frequency domain 轉回來。

下圖是一個訊號和它的 Fourier transform：

要注意的是，一個訊號的 Fourier transform，對任一個頻率實際上有兩個成份，一個是訊號的強度（magnitude），另一個是相位（phase）。在上圖中只顯示出強度，而沒有顯示出相位。另外，在頻率為 0 的地方，稱為 DC，等於是整個訊號在 spatial domain（或 time domain）的總合，所以特別大。在後面的圖中，有時會把 DC 值切掉，以讓其它頻率的值更容易看出來。

假設現在要對一個訊號在每個 pixel 的中間進行取樣，也就是保留訊號在 pixel 中間的值，而把其它地方的值變成 0。這其實可以利用乘上另一個訊號的方式來做，也就是乘上一個「在每個 pixel 中間為 1、其它地方為 0」的訊號。如下圖所示：

原始訊號	Comb filter	取樣後的訊號

上圖是一個原始訊號，在乘上 comb filter 後，得到取樣後的訊號。Comb filter 的名字來自於它的形狀，因為它在每個 pixel 中間的值為 1，其它地方的值為 0，看起來長得像梳子，所以叫 comb filter。

究竟取樣的時候，發生什麼事呢？這要從 frequency domain 來看才會清楚。下圖是同樣的訊號，在 frequency domain 的形狀：

原始訊號	Comb filter	取樣後的訊號

可以看到，經過取樣後的訊號，在 frequency domain 變成一個不停重覆的東西。不過，它在 -1 和 1 之間的形狀，和原來的形狀並不相同。這是因為原始訊號在 -1 和 1 之外還有東西（像是 1 和 2 之間的突起，這是來自原始訊號右邊的那三個尖角，它們的頻率太高了），這些東西「干擾」到原來在 -1 和 1 之間的東西。這個現象使得原來訊號中的高頻成份（像是 1 和 2 之間的突起），在取樣後，可能會被當成是比較低頻的成份。這些多出來的低頻成份，就是失真（aliasing）。

要避免高頻成份在取樣後會被當成低頻成份，最簡單的方式，就是在取樣前，用 low pass filter 把所有的高頻成份都去掉，如下圖所示：

經過 low pass filter 的訊號	取樣後的訊號

上圖中，先把高頻成份去掉之後，在取樣時，就不會干擾到低頻部份，也就不會產生失真了。不過，要去掉多高頻的成份呢？從 comb filter 的表現可以看到，當取樣頻率是 N 的時候，所有頻率大於 N/2 的成份，都會造成失真。所以，要把頻率大於 N/2 的成份都去除。反過來說，如果已經知道所需要最高的頻率是 N，那就要把取樣頻率設在 N 的兩倍以上。

不過，去除了高頻成份之後，訊號會變成什麼樣子呢？下圖是上面的訊號和其經過 low pass filter 後的比較：

可以看到它和原來的訊號相差蠻多的，不過這是在這個取樣頻率下（16 個取樣點）所能做到最好的結果了。


[Part 3]

在前面已經說明了為什麼在對一個訊號進行取樣之前，要先把高頻成份去除。在去除高頻成份後，取樣時就不會發生失真的現象了。不過，在取樣後的數位訊號，只是一堆數字，所以還需要一個重建的動作，才能變回原來的類比訊號。

理論上，重建原來的類比訊號的動作並不太困難。因為，對取樣後的訊號進行 Fourier transform 後，會得到一堆重覆的東西。如下圖所示：

經過 low pass filter 的訊號	取樣後的訊號

所以，只要把取樣後的訊號，在 frequency domain 中，再經過一個 low pass filter（和取樣之前用的那個一樣），再進行一次 inverse Fourier transform，就可以得到原來的（經過 low pass filter 的）訊號了。

但是，Fourier transform 和 inverse Fourier transform 都是很花時間的工作。也就是說，在實際上是不可能真的用 Fourier transform 的。不過，low pass filter 其實是在 frequency domain 做乘法的運算，而它可以轉換成在 spatial domain（或 time domain）的 convolution 運算。

一般用到的 low pass filter，其實就是把一段範圍內的訊號保留，而範圍外的訊號則變成零。所以，可以把它想成是乘上一個特別的訊號，這個訊號在指定的範圍內是 1，其它的地方則是 0。因此，把任何一個訊號乘上這個訊號，就會保留指定的範圍的訊號，而把其它地方變成 零了。所以，只要把這個訊號轉換到 spatial domain 中，就可以很容易用 convolution 的方式來進行運算。

不幸的是，這樣的訊號轉換到 spatial domain 後，會變成一個稱為 sinc filter 的東西。Sinc filter 是一個延伸範圍達到無限遠的 filter。當然，隨著距離變遠，它也會衰減，但是這會使它的 filter 範圍變得很大。下圖是一個理想的 low pass filter 在 frequency domain 和 spatial domain 的長像：

Frequency domain	Spatial domain

使用 sinc filter 來做 convolution 不但很花時間，它還有負值的部份，也會造成一些麻煩。所以，一個比較常用的 low pass filter 是 box filter。利用 box filter 來做 convolution，就等於是把一個 pixel 範圍內所有的值全部加起來，做為一個 pixel 的值。如下所示：

Unit box filter	Frequency response

從 box filter 的 frequency response 可以看到 box filter 的缺點：box filter 把一些低頻成份衰減了，但是又留下了一些高頻成份。而且，box filter 會留下一大堆更高頻的地方（像是 2 ~ 3 之間的地方）。因此，box filter 會造成一些模糊的現象，但是還是可能會產生不少失真的情形。不過，因為 box filter 非常簡單，計算上也比較容易，所以仍是最常用的 low pass filter。

另外一個常用的 low pass filter 是 Gaussian filter。Gaussian filter 的一個非常重要的特性，是它在 frequency domain 的形狀會和原來一樣，也是一個 Gaussian。不過，它的寬度會有一些改變。以下是一個 Gaussian filter 和其在 frequency domain 的形狀：

Unit Gaussian filter	Frequency response

和理想的 low pass filter 相比，Gaussian filter 還是留下了一些高頻部份（因為在 -0.5 ~ 0.5 以外的範圍還是有非 0 的值），而且在低頻部份的衰減也比 box filter 更為嚴重。但是，它沒有負值的情形，而且在 -1 ~ +1 範圍之外幾乎沒有留下任何東西。所以，它在消除高頻失真上面，會比 box filter 要好很多。但是，它的結果看起來會比 box filter 更為模糊一些。而且，和 box filter 相比，它比較寬。Box filter 對每個 pixel 只需要處理一個 pixel 寬度的資料，但是 Gaussian filter 則需要處理約三個 pixel 寬度的資料。所以，整體來說，Gaussian filter 所需的運算量，比 box filter 要高出很多。另外，因為 Gaussian filter 在每個取樣點需要不同的權重（box filter 則是每個取樣點都使用同樣的權重），所以，Gaussian filter 幾乎無法適用在隨機取樣的情形，因為如果取樣點的位置會不停變化，就需要每次重新計算其權重。這對於需要即時運算的應用，其計算太過複雜，幾乎是不可能的。


[Part 4]

前面提到，不論是取樣時，或是在重建訊號時，都需要一個 low pass filter。在 3D 繪圖的時候，一般是利用超取樣（supersampling），也就是在同一個 pixel 中，取多個取樣點，再以一個數位的 low pass filter（box filter 或是 Gaussian filter）處理後，得到每個 pixel 的「經過 low pass filter 的取樣結果」。當然，超取樣的取樣點數目會影響 low pass filter 的效果。這是因為數位 low pass filter 長得並不可愛。例如，下圖是一個兩個取樣點的 box filter 的長像：

2 samples digital box filter	Frequency response

可以看出來，兩個 samples 的數位 box filter 根本無法有效消除高頻成份。要注意的是，因為影像是一個二維的空間，所以如果每軸需要兩個 samples，則共需要四個 samples。目前大部份 3D 顯示晶片所支援的 4X OGSS FSAA 就是這樣。

如果採用 Gaussian filter 則會稍微好一些。下面是一個經過調整的數位 Gaussian filter：

3 samples digital Gaussian filter	Frequency response

它的表現比兩個 samples 的 box filter 要好一些，但並不明顯。因為它實際的取樣數並沒有增加（三個取樣點中，有兩個是和鄰近的 pixel 重覆的）。所以，它基本上還是兩倍的超取樣，只是 post filter 不同。它比 box filter 可以消除更多的高頻成份，但是也同時犧牲了一些低頻。所以，它的結果看起來會比較模糊，但是高頻失真的情形會比較少。

如果增加取樣點的數目，則這兩種 low pass filter 的表現都會變好。以下是在每個 pixel 使用四個取樣點的情形：

4 samples digital box filter	Frequency response
5 samples digital Gaussian filter	Frequency response

在這裡的 Gaussian filter 雖然使用五個取樣點，但是每個 pixel 範圍內還是只有四個取樣點，所以在超取樣上面和 box filter 是相同的。從這兩種 filter 的 frequency response 可以看出，Gaussian filter 的表現還是比 box filter 要好一些，而且它不像 box filter 會產生討厭的負值。然而，每邊四個取樣點，對目前的 3D 顯示晶片來說，工作量還是太大了。

最後我們要稍微討論一下訊號重建的問題。前面說過，在重建訊號時，只要先對數位訊號使用 low pass filter，就可以得到原始的訊號（當然，是指經過 low pass filter 的原始訊號）。然而，重建訊號的工作通常是由顯示單元（也就是螢幕）在進行的，所以，一般應用程式對它是沒什麼控制的。

一般的顯示晶片在輸出訊號時，會先經過一個 sample-and-hold 的過程，簡單的說，就是使用一個 box filter。Sample-and-hold 會產生具有大量鋸齒狀的結果（參考下圖）。不過，為了讓顯示卡可以符合 FCC 規範，通常在顯示卡上會有一個 low pass 電路。這個電路理論上會把顯示晶片上 RAMDAC 所能處理的最高頻率以上的高頻成份去除。不過，一般來說都不會這麼理想就是了。

這個經過 low pass 的訊號，在送到螢幕顯示時，如果是傳統 CRT 螢幕的話，它會把訊號直接放大，送到電子槍後，在螢光幕上產生光點。但是，因為螢光劑的塗布、和電子槍光點的大小等問題，實際上 CRT 上的光點，並不會剛好只是個小點，而會是一個和周圍的光點有些重疊的圓形。而且，這個圓形的亮度反應，大致上和 Gaussian filter 形狀類似。所以，基本上，數位訊號在重建時，並不是理想的重建，而比較接近以 Gaussian filter 做為 low pass filter 的重建。不過，一般來說，它的效果也算是夠好了。

如果使用的是 LCD 或是 plasma display 等顯示幕的話，情形就會更糟。因為 LCD 和 plasma display 的 pixel 都是一個一個分開的，不像 CRT 是連續塗布的螢光劑，配上一個 mask。所以，它在顯示時，整個 pixel 內的顏色都是一樣的，而且 pixel 通常是方形。因此，它幾乎等於是用一個理想的 box filter 當作 low pass filter 的重建。這會產生和上面的圖形完全相同的結果。所以，LCD 或是 plasma display 在配合 FSAA 時，效果會比 CRT 螢幕要差一些。