Home > 圖像編程 > Freetype2向量文字渲染

Freetype2向量文字渲染

上回使用Freetype2的光柵化(Rasterization)功能把文字渲染到 Texture上,再把 Texture 渲染到螢幕上。除了這個方法外,前文也提及可以把字型以向量方式渲染。在朋友的慫恿下,加上未有這方面的經驗,便花了兩三天去實作這個功能。雖然這個功能在遊戲中完全不重要,但實作這個的難度比預期高,也沒找到類似的參考,而且需要用許多計算幾何(Computational Geometry) 的演算法,對我來說,好像是一個學習和練習的功課。我嘗試把實作的過程記錄下來,和大家交流。

光柵化和向量文字的效果比較

上半圖是把每個字型光柵化至 32×32, 8-bit alpha 的 Texture,再渲染出來。

下半圖是把每個字型轉為三角形網格 (Triangle Mesh),每段 Bézier 曲線固定用5點插值,用 4x MSAA 渲染。

可以看到,向量化的文字能有較圓滑的邊線,而且可以加入如 Extrusion 等三維模型的效果。但如果沒有 MSAA,太小的向量化文字會很難看。所以兩者是相輔相承的。另外,在 Mil 中,生成的向量文字是普通的 Geometry,所以可以直接用在 Entity 上;而光柵化的 API 需要在渲染的過程呼叫,並不能在目前的 Entity 系統中使用。

向量化文字有時會應用在遊戲中,例如賽車遊戲 GRID 的選單。不過我想大部份引擎都不會即時生成這些網格,而是美工在三維模型軟件(如 3D Stduio Max)先做好的。這個沒有甚麼用途的功能,就讓我介紹一下它的實作過程吧。

實作過程

在開始實作之前,我首先把之前實現的文字光柵化代碼重構一遍。主要是把一些通用的功能(例如特殊字符處理、Kerning等)用Extract Method方式抽離出來。

之後,我主要的實作步驟如下 (加上個人觀感的難度分):

  1. 從Freetype2 API 取得字型線框 (簡單)
  2. Bézier曲線插值 (簡單)
  3. 把外輪廓和內輪廓分開 (簡單)
  4. 找出鑰匙孔(keyhole),結合外框和內框,生成簡單多邊形(難)
  5. 使用Ear Clipping 演算法去三角形化(Triangulation) (難)
  6. 製作Extrusion網格 (簡單)

1. 從 Freetype2 API 取得字型線框

光柵化和取得線框(Outline)都是使用 Freetype2 的 FT_Load_Glyph 函數,只是光柵化可加入 FT_LOAD_RENDER 旗標,而取得框線不需要。

載入字符(Glyph)後,可以直接從 FT_GlyphSlot 裡取得 FT_Outline 物件,內裡有該字符的線框。線框是由一組輪廓 (Contour)組成。輪廓是一串直線和Bézier曲線所組成的一個環 (Loop)。如果只有直線的話,那輪廓其實就是一個多邊型而已。

上圖是直接把輪廓以直接繪畫出來。感覺不錯,這比做光柵化還要簡單呢!因為不需要做Texture,又不需要設UV,就可以渲染出來了。

2. Bézier曲線插值

當我再讀 Freetype2 文檔去理解 Bézier 曲線的參數是怎樣表達在FT_Outline裡的時候,發現原來還有一組Freetype2 API 專門為繪畫 Outline 而設的,我指的就是 FT_Outline_Decompose 函數。
這函數有點像SAX介面,給它一組回調函數(Callback Functions),當它遇到Outline裡的新起點、直線、Bézier曲線,就會呼叫回調函數,讓你處理。

在Freetype2中有兩種Bézier曲線,分別是二次 (Quadratic 或 Conic) 和三次 (Cubic) Bézier曲線。Truetype字型只用二次Bézier曲線。

二次Bézier曲線是由兩個端點 (End Points)、一個控制點 (Control Point) 定義的 Parametric Function。只要把 0 至 1 的參數放進該 function,就能取得曲線上的位置。

以下是我實作的二次 Bézier 曲線回調函數,現時 hardcode 了把曲線切為五段直線。

static int ConicTo(const FT_Vector* control, const FT_Vector* to, void* user) {
    static const int level = 5;
    static bool bezierInit = false;
    static float bezier[level + 1][3];
    if (!bezierInit) {
        for (int i = 1; i <= level; i++) {
            float t = (float)i / (float)level;
            bezier[i][0] = (1 - t) * (1 - t);
            bezier[i][1] = 2 * (1 - t) * t;
            bezier[i][2] = t * t;
        }
        bezierInit = true;
    }
    
    // Convert control and to into Vector2
    // ...
    // start is the last position
    
    for (int i = 1; i <= level; i++) {
        Vector2 p = start * bezier[i][0] + controlv * bezier[i][1] + tov * bezier[i][2];
        // Add p to our data structure	
    }
}

那麼,字就變圓了。

3. 把外輪廓和內輪廓分開

Freetype2 中沒有直接告訴你那些輪廓是外框、那些是內框(字型中的孔,例如 O 字中間的小圓)。要把相關的輪廓變成一個簡單多邊形(沒有孔的多邊形),首先要分辦那些是外輪廓,那些是內輪廓。

Freetype2 把外輪廓設定為順時針的排序,內輪廓為逆時針的排序。我在網上找到對凹多邊型的方向檢測演算法,就是計算它的面積,面積為負數的為順時針,正數為逆時針。

以上截圖只顯示外輪廓。

4. 找出鑰匙孔,結合外輪廓和內輪廓,生成簡單多邊形

距離三角形化還有一步,就是把每個外輪廓和它的(多個)內輪廓給合,生成簡單多邊形。

每個內輪廓是屬於那個外輪廓,也是一個問題。對於不相交(Intersect)的輪廓,可以推斷,如果一個內輪廓在一個外輪廓裡,那麼那內輪廓的任意一點也在那外輪廓裡。所以我把內輪廓的第一點和每個外輪廓做一個「點在多邊形」(point in polyon)測試,去找出這個關係。由於是凹多邊型,所以用了這網頁所說的第一個方法,檢查該點發出的任意一光線和多邊形相交的次數,點在多變形入面時是奇數,外面是偶數。

之後,從 Real-time Rendering 一書中得之,透過加入鑰匙孔 (key hole、或稱為 bridge),可以把有孔的多邊形變成無孔的。現實生活的例子是把一個有孔的紙,從邊上剪到孔裡,那麼紙就算是沒「孔」的了。下圖顯示 key hole。

鑰匙孔是由內輪廓的一點和外輪廓的一點定義的線段,且該線段不和輪廓相交。

我在網上找不到相關的資料。我覺得,最簡單的方法是找出所有可能線段,逐一檢查它們是否和輪廓相交,但這樣的時間效率是 O(n^3)。我最後只計算最短的線段,而不計算相交,就把它當成鑰匙孔,這也要O(n^2)。但當一個外輪廓內有多個內輪廓,問題就更複雜了。現時我的實作加入了一些檢測,但它應該不能處理所有情況。這方面我應該要再研究多一點。

上圖顯示了鑰匙孔﹐簡單的一條線段得來不容易。

5. 使用 Ear Clipping 演算法去三角形化

最後,採用堪稱最簡單的三角形化的演算法──Ear Clipping,但我的實作出來還是覺得太複雜,應該要好好重構。

要解釋 Ear Clipping,首先要定義 Ear。讓一個 n 邊多邊形由 v[0], ..., v[n-1] 頂點組成,Ear 是指三角形 v[i], v[(i+1) mod n], v[(i+2) mod n]中,線段 v[i] ~ v[(i+2) mod n] 在多邊形內,而且不和其他多變形邊線相交。

如下圖所示,三角形 是一個 ear,因為線段 v0, v2 在多邊形內,而且不與其它邊相交。 就不是 ear,因為線段 v1, v3 在多邊形外(換句話說,v2 的內角大於 180 度)。而三角形 就不是 ear,因為線段 v2, v4 和邊線相交。

把一個 Ear 「切掉」成為三角形網格的一部分,餘下的便是一個 n-1 邊的多邊形。一直切下去,就會把多邊形變成三角形網格。

Ear Clipping 有 Two-Ears 定理支持的,該定理說,所有三邊以上的多邊形必定有兩個 Ears,所以所有簡單多邊形都必定能用 Ear Clipping 分解成三角形網格。

上圖就是三角形化後的結果。看到錯中複雜的切割,雖然還有待改善三角形化的質素,已經很滿足了。

6. 製作 Extrusion 網格

向量文字的好處是它真的是三維世界的一部份,可以加入不同效果,例如 Extrusion、Chamfer 等等。

Extrusion 比較困難的地方,是那條帶的法向量(normal)。因為字型上的每條直線要生成四個獨立的點(因為頂點法向量和相鄰的不同),而曲線的線段要和相鄰的面共用兩個點。我現時只是在產生線段時,簡單的加入一些資料,決定是獨立或共享點。寫到這裡,就想到,最好的方法還是在生成輪廓時計算二維的法向量,Bézier曲線應該可以直接計算法向量的。

大功告成,但有待改善。

後記

今次的實作感覺像在學校裡做習題一樣。很久沒有寫這麼「演算法」的代碼,許多時候只是在解決一些軟件設計、或是某個技術的使用問題。

另一點感受是,雖完剛從頭到尾看了一遍第三版的《Real-Time Rendering》,看完即時忘掉了大部份內容。不練習過、應用過的東西還不是自己學到的知識。

Comments:3

半路 09-01-24 (六) 14:31

這成果的確相當出色哪。

讓我想起之前測試使用過的 Scaleform Gfx,可以做到不失真的字型渲染,也就是利用類似這樣的方式實作出來的。

Milo 09-01-24 (六) 14:54

回半路:

應用了 Scaleform Gfx 的遊戲已經越來越多。

我對向量字型的 polygon triangulation 現在是比較慢,暫時不適合每幀去生成網格。

在 Real-time Rendering 還看到有一個方法做向量字型/曲線的方法,就是用 Pixel Shader 計算一個 Pixel 是否在一條直線線段和 Bézier曲線線段之間,也可以用 multi-sampling 來做 anti-aliasing。該方法好像很適合用來生成 Texture。有機會也想試試實作。

exe 09-01-25 (日) 15:29

很酷啊
good job!
thanks for sharing! :D

Comment Form
Remember personal info

Trackbacks:0

Trackback URL for this entry
http://miloyip.seezone.net/wp-trackback.php?p=82
Listed below are links to weblogs that reference
Freetype2向量文字渲染 from Milo的遊戲開發

Home > 圖像編程 > Freetype2向量文字渲染

Search
Feeds
Meta

Return to page top