模型轉換符號距離場算法實現

樂璐

（四川大學計算機學院，成都610065）

0 引言

電子游戲行業一直致力于在游戲中實現越來越真實的圖形效果，但是當前的實時渲染器與用于電影的離線光線追蹤渲染器之間仍然存在著巨大差距。近年來人們一直在嘗試彌合這一差距，2018 年Wyman[1]在SIGGRAPH 2018 上介紹了實時光線追蹤API-DirectX Raytracing。同年，NVIDIA 發布了新一代首款支持實時光線追蹤技術的顯卡。但是上述實時光線追蹤技術并不能完全代替原有的光柵化技術。首先因為渲染最終的畫面需要求解渲染方程，而該方程不一定具有解析解，需要通過蒙特卡洛積分求近似解，蒙特卡洛積分法需要用到大量采樣數，使用光線追蹤計算大量的樣本數需要的代價十分昂貴，無法滿足追求實時渲染（每秒60 幀）的電子游戲的要求。其次由于光線追蹤顯卡尚未普及，更多的玩家依舊使用老一代不支持光線追蹤的顯卡。所以使用其他的下一代渲染方法成為游戲開發的重點，距離場技術就是其中一種可以逼近光線追蹤效果的渲染方法。

距離場并不是近幾年的概念，早在2007 年，Green[2]利用二維的距離場進行字體渲染，Inigo Quilez[3]利用距離場實現環境光遮蔽（Ambient Occlusion）、陰影（Shadow）等效果，并將之推廣開來。在SIGGRAPH 2015 會議上，Wright[4]提出了一種現代的距離場使用方法，顯示了距離場理論的可行性，并作為Unreal Engine 中對網格渲染的增強。

符號距離場（Signed Distance Field，SDF）本身是一種十分簡單的結構體，Jones[5]定義距離場為“場內任意一點我們知道其到場內任意對象上最接近點的距離”，因此距離場實質上也是表面的一種表示。在數學上，定義符號距離場為：

S 是對象表面上的點的集合，這些點構成對象的整個表面。函數sign 定義為：

廣義上講，符號距離場可以用函數F 表示，以便傳遞的任意點p 都將返回函數（1）表示的對象距離dist(p)。然后可以將此類函數返回的距離存儲為三維紋理，或者作為渲染目的而更常見的三維矩陣。三維紋理的每個網格元素表示從該網格元素到最近的對象表面的距離，因此值為0 的網格元素表示物體的表面，負距離表示該物體的內部，正距離表示物體的外部。從理論上講，可以使用不同的距離函數生成距離場，包括Chessbord 距離和Euclidean 距離，圖1 展示了二維的距離場表示。

圖1

在實際的符號距離場渲染中，Euclidean 距離是使用最廣泛的距離函數，并且該函數將用于本文所有進一步的實現。本文將游戲渲染中用到的模型作為輸入，計算得到該模型的SDF 數據文件，并通過Ray-Marching 的方式驗證生成的符號距離場的正確性。

1 算法概述

1.1 算法描述

生成符號距離場的方法通常有兩種，一種是利用定義明確的距離函數來為空間中的任意位置生成距離值，對于復雜的形狀可以通過布爾運算進行創建，這些距離函數會創建所謂的隱式表面。另一種方法就是由網格（顯式）表面轉換成距離值，利用三維紋理包含網格曲面存在的整個區域，并且每個網格單元保存該點離最近的網格表面的距離。本文會對上述兩種距離場生成方法進行介紹。

1.2 隱式表面轉換距離場

創建距離場最簡單的方法就是通過距離函數創建，許多基本的幾何形狀有不同的距離函數，并且由這些基本的幾何形狀可以組成更復雜的幾何圖形。距離函數具有不同的計算復雜度，但始終以點作為輸入，距離為其輸出。最簡單的隱式距離函數是球體函數，下述代碼片段可以得到球心在原點的球體：

float sdSphere( float3 p,float s)

{return length(p)-s;}

某一點據球體表面的距離就是該點據球心的距離減去球體半徑。

常使用布爾運算例如并集、交集等方法將多個基本圖形的距離函數組成一個復雜的距離函數來表示復雜的圖形，布爾運算具有保持Lipschitz 連續性的特性，因此能夠在距離場中依舊保持正確的梯度和距離。

float union( )

float distance1,float distance2

{return min(distance1,distacne2);}

關于各種形狀混合的代碼可以參考由Mercury 團隊做的HG_SDF 距離場庫。

創建多個隱式圖元之后可以通過查詢每個離散網格元素的距離函數，并將這些值與布爾函數組合，使用最終結果的距離值填充三維紋理。由于大多數距離函數計算速度很快，因此可以在運行時執行距離的計算。由于無需保存網格數據，該方法被廣泛運用在程序規模很小的圖形演示場景[6]中。

1.3 顯式表面轉換距離場

但是并非所有形狀都能通過隱式函數輕松生成，而且由于現代GPU 上高度優化的渲染管線，幾乎所有開發的游戲都使用三角網格來表示幾何圖形。對于游戲中有凹有凸的圖形，很難通過隱式函數對其進行模擬。這時候就需要距離轉換算法實現網格幾何體到距離場表示的轉換。

最基本的距離變換算法是蠻力計算，對于每個網格單元計算該單元距離所有三角片元的距離，最短的距離存儲在距離場網格單元中。雖然蠻力算法計算代價十分昂貴，但是可以保證結果的正確性，并且該算法可以并行實現，非常適合GPU 計算。本文接下來會詳細介紹將現有的模型轉換成符號距離場的算法。

2 模型轉換符號距離場

蠻力算法是常用的距離變換算法中最簡單的方法，首先必須選擇距離場網格的范圍和每個網格元素之間的距離。選擇具有相等尺寸（例如64×64×64）的三維數據集會導致很多空的單元格。通過分析要轉換的網格并根據網格的范圍縮放尺寸來壓縮距離場網格的大小，可以減少總體內存占用。計算完網格大小以后，可以用以下算法計算每個網格的距離值：

Foreach GridCell in DistanceFieldGrid：

Foreach Triangle in Mesh：

Find distance from Triangle to GridCell，save the closest one.

該算法非常簡單并且可以很容易通過CPU 并行處理。但是蠻力算法中計算每個網格到三角面片的最近距離時除了如圖2 所示需要考慮該點與三角形頂點、邊、面的最近距離，還需要知道該網格元素的符號。

圖2 點與三角形距離的三種情況與面最近（1），與邊最近（2），與頂點最近（3）

2.1 點到三角形的距離

蠻力算法最重要的步驟是點到三角形面片距離的計算。最接近的點落在三角形的三個特征元素之一上：點、邊和面。蠻力算法必須確定網格單元最接近哪個三角形特征，然后計算距離。計算點與三角形距離的方法有2 種，一種三維方法，一種二維方法。本文主要采用三維方法計算點到三角形面片的距離。

（1）三維方法

首先，將網格單元點投影到由三角形創建的平面上，然后將所得的投影點轉換為重心坐標，以確定其是否位于三角形面內。如圖2 所示，如果位于三角形面上即區域1 的位置，則該點到三角形的最短距離就是網格點和三角形上的投影點之間的矢量的長度；如果位于三角形面外區域2 的位置，則該點到三角形的最短距離就是網格點到三角形邊的距離；如果位于三角形面外區域3 的位置，則該點到三角形的最短距離就是網格點到三角形頂點的距離。找到最接近的特征后，計算出網格單元點到該特征的距離，由此得到的最短距離才是該網格元素距離三角面片的正確最短距離。

（2）二維方法

Jones[7]提出將三角形旋轉到yz 平面，將點p0到三角形的距離問題由三維轉換成二維來解決。該方法需要預計算得到將三角形旋轉到yz 平面的旋轉矩陣。因為已經將三角形旋轉到了yz 平面，點p0(x0,y0,z0)在yz 平面上的投影坐標即為(0,y0,z0)。然后和三維方法一樣的檢查點與三角形的最接近特征，計算得到最短距離值。因為該算法需要大量旋轉，導致距離場中存在許多不準確性，所以本文采用三維計算距離的方法而未采用二維的計算方法。

2.2 符號計算

在計算最短距離之后，需要確定網格的符號，符號表示該網格單元與給定曲面的位置關系，如下函數所示：

由于僅針對閉合曲面定義了內外部，因此會在未閉合的幾何體上返回錯誤的結果。還有一種更簡單的定義方式[8]：

其中S 是由一組有向的三角形構成的曲面，n 為任意點q ∈S 的面法線，q 為S 距離點p 最近的點。對于任意集合S 都存在點p 使得sign( p )= sign。因此只要曲面存在方向無需閉合也可以得到符號。

然而在三角形的最接近特征是邊緣或點的情況下，如果最近的頂點由網格中的至少三個三角形共享或最近的邊緣由兩個三角形共享時，有時會產生不正確的結果。如圖3 所示，如果算法試圖找到最接近的三角形，則兩個三角形都符合。兩者都能用于符號計算，但是得到的符號相反。可以使用偽法線n'代替三角形的實際法線來解決這種情況。法線n'只是共享最接近特征的所有三角形的法線之和。

上述改進方法雖然能夠減輕問題，但是在某些情況下仍然不足。當網格的一個面細分為更多更細的三角形，同時仍共享相同的頂點時，就會出現問題。部分三角形雖然面積很小，但數量多，影響三角形法線總和的方向，如圖4 所示。角度加權偽法線可以解決這個問題。除了法線的總和，每個法線還必須通過一個值加權，該值等于連接到最接近頂點的兩個邊的夾角。對于較小的三角形，具有較小的權重；對于較大的三角形，具有較大的權重。盡管這種符號計算方法在理論上完全正確，但是由于浮點數的不精確，在實際實現中仍存在一些問題。由于浮點數的精度有限，所以相鄰的小三角形可能會導致得到的距離略有不同，這將阻止它們的偽法線合并，得到錯誤的結果。

本文采用Houston 等人[9]提出的基于可見性方法，先集成表面法線信息，然后利用單射線投射奇偶計數的方法來確定網格單元位于表面，內部還是外部。

計算得到最近距離值和符號以后我們就擁有了完整的符號距離場，可以根據符號距離場將原模型重新表示，也可以利用符號距離場計算軟陰影等效果。

圖3 點P最靠近頂點V，該頂點由兩個三角形1，2共享

圖4 第二個三角形細分成3個三角形2，3，4

3 實驗結果

本節將會展示將一個模型轉換成SDF 以后，利用Raytracing 的方式查看SDF，驗證生成的距離場的正確性。實驗設備為：

CPU：AMD Ryzen 3 1200 Quad- Core Processor 3.10GHz

RAM：4.0 GB

System：Windows 10

GPU：NVIDIA GeForce GTX 1050

圖5 展示了將鴨子模型和雕塑模型轉換成SDF后，利用Raymarching 展示SDF。

圖5

表1 展示了生成不同分辨率的SDF 本算法所需要的時間。

表1 不同模型生成距離場需要的時間

4 結語

本文給出了一種蠻力求解計算符號距離場的算法，通過輸入模型文件可以生成符號距離場，并且對生成的距離場利用光線行進的方式進行展示，驗證了生成的距離場的正確性，得到了后續可以用于實時渲染效果的距離場。

雖然我們的方法可以得到正確的距離場，但是生成距離場的時間和模型的大小相關，當模型三角面片數目很多時所需的時間代價十分昂貴。盡管可以通過降低分辨率的方式加快距離場的生成，但是會丟失模型細節。在后續的研究中會利用空間加速結構例如KD-Tree 等優化算法，也可以根據上文中提到的利用GPU 并行計算快的特性，加速計算距離場。