OpenGL中一種高效的線段反走樣技術
令人討厭的“走樣”
我在日常工作中通過傳統的OpenGL繪制函數繪制線段時，發現繪制出的線段邊緣充滿了“鋸齒”，而這種“鋸齒”在線段運動和旋轉時往往會更加明 顯（圖 1）。這種我們不希望看到的“鋸齒”被成為“走樣”，而消除這種“鋸齒”的過程就是我們所說的“反走樣”。雖然OpenGL提供了諸如設置 GL_LINE_SMOOTH 屬性、多重采樣等線段反走樣的方法，但效果和質量受到很多方面的限制，而且不同的硬件廠商使用不同的反走樣算法，所以使得反走樣的結果在不同的GPU上有 著不同的效果。因此我們需要一種更為高效和通用的線段反走樣技術。
圖1 采用傳統OpenGL繪制方法繪制的線段
為什么會“走樣”？
在介紹如何對線段反走樣之前，我們必須了解為什么我們繪制的線段會產生“走樣”。
我們都知道，在數學的定義中一條線段是由兩個端點確定的，而線段是沒有寬度和面積的。但在計算機圖形領域中，為了讓人的肉眼能夠看到，必須給線段 一定的寬 度，所以我們的線段通常是由兩個端點和一個寬度參數確定的，而我們計算機中圖形的寬度通常都是以像素為單位的，因此我們的線段寬度有可能是1像素也有可能 是n像素。
如果需要在白色的背景下繪制一條寬度為1像素的黑色線段，從信號處理的觀點上來看，我們可以把這條線段看做一個值為1的信號，而線段外部的區域信 號值為0，如果不加任何處理，線段的邊界就是這樣一個不連續的階梯函數（圖2）。 因為幀緩存和顯示器所能容納的像素點是有限的，所以我們需要對這個信號進行采樣。
圖2 線段信號采樣示意圖
我們可以看到：離散采樣（圖2 中用藍色虛線表示）的間隔無論多么的小都無法精確的表達它的不連續性，因此我們無論怎么提高分辨率，都無法徹底消除走樣。而根據耐奎斯特的信號采樣定理：要重構一個不走樣的信號，采樣率至少是信號最高頻率的兩倍。
即：C = B * log2 N ( bps )
因此，從理論上來說要繪制一條沒有走樣的線段，我們必須擁有足夠大的信號頻率，也就是我們需要無限放大我們的屏幕分辨率才能徹底消除走樣。
圖3 通過提高分辨率減輕走樣現象
從圖3我們可以看出，雖然我們提高了分辨率，但是走樣依然存在。因此，一味地提高分辨率是無法徹底解決掉線段走樣問題的，而且在時間、空間以及金錢有限的情況下是不允許我們這么做的。
解決之道
計算機圖形學領域中廣泛采用的一種方法是：限制信號的帶寬。也就是說既然無法提高分辨率，我們可以將信號中無法還原的高頻部分去掉以達到“反走 樣”的目的。這樣線段就不再有明顯尖銳的邊界了，相反，線段的邊界處將變得模糊，這種將邊界模糊的過程我們稱之為“過濾”。我們可以讓信號通過一個低通過 濾器，來過濾掉信號中的高頻部分，以達到過濾的效果，這樣的過濾器有很多，可以是簡單的線性過濾器也可以是稍微復雜一點的盒狀過濾器或高斯過濾器。本文將 以高斯過濾器為例，為大家介紹整個過濾的過程。
圖4 低通高斯過濾器對2D信號的過濾效果
圖4演示了高斯過濾器對一個2D信號進行過濾操作的整個過程，首先圖4(a)表示未處理的線段信號，其中x和y軸表示線段所處平面坐標系，z軸表 示圖像信號的強度，可以認為是RGBA顏色中的alpha值。其中左半部分z=1表示位于線段內部，右半部份z=0表示位于線段外部，這里z=0和z=1 邊界處是不連續的。圖4(b）所表示的是一個高斯地同過濾器，將它與圖4(a)中的某一段信號做卷積后就得到了圖4(c)中的效果。卷積在這里等效于求出 過濾器與信號相交部分的體積，圖4(d)就是將所有信號與過濾器卷積后得到的最終過濾效果。
圖5 經過半徑為2的高斯過濾后的線段信號示意圖
從圖5可以看到：經過過濾后的線段邊界將不再是一段不連續的階梯函數，而是一段連續的平滑曲線。
預處理
至此，我們似乎已經解決了困擾我們的反走樣問題，但是我們需要注意到的是：在程序運行時我們的GPU會逐像素地進行復雜的卷積計算，這種大規模的 計算對我們來說無疑是一筆很大的開銷，會直接影響我們程序運行的效率。因此，我們需要將這部分的計算放在渲染之前進行，我們稱之為預處理。
如圖6所示，在預處理過程中，我們將半徑為R的過濾器和寬度為W的線段進行卷積，所得到的強度值根據過濾器的位置變化而變化。當過濾器剛好位于直 線上（圖6a）時，我們得到的強度值最大，因為此時過濾器與直線重疊部分最多，（在圖4所示坐標系中）重疊部分的體積也就越大。相反的，當過濾器位于距離 直線w/2+R的位置（圖6b）時，卷積所得強度值最小，因為此時過濾器與直線沒有重疊。而在過濾器從距離為0移動到w/2+R處的過程中，強度值在慢慢 變小。
圖6 過濾器位置影響卷積值
有了這個關系，我們就可以根據到直線的距離提前為像素計算出對應的強度值而建立一個距離與強度值對應的查找表，在渲染時只需要根據像素與線段的距 離從查找表中取出強度值即可，而無需進行即時的計算，大大提高了我們渲染的速度。而同一平行線上的所有像素強度值是一樣的，這樣理論上來說我們就只需要算 W/2個像素的強度值就可以繪制出整條直線了，計算量也大大減少。
然而，我們并不希望計算量會隨線段寬度變化，我們希望我們的渲染過程的效率是穩定的，因此，我們需要一張固定寬度的查找表。通過實踐發現，一張 32個強度值的查找表已經足夠應付任意寬度的直線了（圖7），如果覺得這樣不夠精細，你還可以使用64個強度值的查找表，因為對于GPU來說，處理一個 32或64元素的1D紋理實在是小菜一碟。
圖7 32個強度值的查找表
如圖8中的代碼片段所示，生成這樣一個紋理只需按照設定的強度值數量利用過濾器計算出相應數量的強度值就可以了。唯一需要注意的是這個紋理是關于直線中心對稱的，以及紋理參數中縮放過濾參數要設置為GL_NEAREST。
圖8 生成一張64個強度值查找表的過程
運行時
預處理只需要在CPU中運行一次，而當我們將過濾后的紋理完成后，我們的預處理工作就算告一段落，接下來就可以進行渲染了。渲染時，我們需要進行 兩種計算，一種是在CPU中的線段相關參數的計算，另一種計算GPU的著色器中進行的，主要是利用CPU提供的參數在頂點著色器和片段著色器中計算出真正 的位置和顏色。
首先我們需要得到一條具有寬度的“線段”，既然線段是沒有寬度的，那我們就利用矩形來生成這樣一條有寬度的“線段”，所生成矩形的寬度就是線段的寬度，而我們需要計算的也就是矩形的4個頂點的坐標。
圖9 將線段端點沿兩側法向量平移w/2距離后得到矩形4個頂點
計算矩形頂點的坐標看起來也不是一件很困難的事情，只需要將線段的兩個頂點向兩側分別平移w/2距離就可以得到（圖9），而線段的平移方向正好是xy平面上垂直于該線段的法向量方向，因此我們只需要計算這個法向量即可。
圖10 頂點著色器
有了法向量后，頂點著色器中只需將頂點和法向量相乘，再乘上w/2就可以得到平移后的頂點位置，最后再與線段的模型視圖投影矩陣相乘，計算出最終的頂點位置（圖10）。
圖11 片段著色器
片段著色器只需對紋理進行一次采樣得到強度值再與線段顏色進行一次疊加就行了,這樣就能得到一條任意顏色的線段。
最終效果
經過這樣的一系列處理，我們就能得到一條邊緣不再尖銳的“反走樣”線段。同時，我們放大后觀察可以發現：線段邊緣因為過濾的效果而變得模糊了（圖5）。
圖12 過濾后線段邊緣變得模糊
并且對它進行拉伸或者旋轉都不會產生新的走樣（圖13）。
圖13(a) 經過反走樣處理的線段拉伸效果圖
圖13(b) 反走樣后線段旋轉效果圖
通過圖13的對比我們可以清楚地看出，經過預過濾反走樣處理的線段相比普通線段和硬件反走樣處理的線段鋸齒感明顯要弱了許多。這種處理方式所需的 存儲空間代價僅僅是額外的兩個頂點和一個寬度64的一維紋理，而運行時處理上也只是增加了一次法向量的計算，可以稱得上是簡單高效。
圖13(c) 各種反走樣線段效果： 從左至右依次為 普通線段 默認硬件反走樣 盒狀過濾器 高斯過濾器
這種方法的優勢可總結為:
1.支持任意對稱的過濾器，除了我們使用的高斯過濾器外還支持盒狀或立方等過濾器。
2.可忽略過濾器算法復雜度對運行效率的影響，因為過濾計算是在渲染之前預先完成的。3.無論渲染任何線段，運行時開銷固定不變。
最后，希望這個方法能夠對大家處理2D線段抗鋸齒問題能夠有所幫助。