樂(lè)璐

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

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

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

符號(hào)距離場(chǎng)（Signed Distance Field，SDF）本身是一種十分簡(jiǎn)單的結(jié)構(gòu)體，Jones[5]定義距離場(chǎng)為“場(chǎng)內(nèi)任意一點(diǎn)我們知道其到場(chǎng)內(nèi)任意對(duì)象上最接近點(diǎn)的距離”，因此距離場(chǎng)實(shí)質(zhì)上也是表面的一種表示。在數(shù)學(xué)上，定義符號(hào)距離場(chǎng)為：

S 是對(duì)象表面上的點(diǎn)的集合，這些點(diǎn)構(gòu)成對(duì)象的整個(gè)表面。函數(shù)sign 定義為：

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

圖1

在實(shí)際的符號(hào)距離場(chǎng)渲染中，Euclidean 距離是使用最廣泛的距離函數(shù)，并且該函數(shù)將用于本文所有進(jìn)一步的實(shí)現(xiàn)。本文將游戲渲染中用到的模型作為輸入，計(jì)算得到該模型的SDF 數(shù)據(jù)文件，并通過(guò)Ray-Marching 的方式驗(yàn)證生成的符號(hào)距離場(chǎng)的正確性。

1 算法概述

1.1 算法描述

生成符號(hào)距離場(chǎng)的方法通常有兩種，一種是利用定義明確的距離函數(shù)來(lái)為空間中的任意位置生成距離值，對(duì)于復(fù)雜的形狀可以通過(guò)布爾運(yùn)算進(jìn)行創(chuàng)建，這些距離函數(shù)會(huì)創(chuàng)建所謂的隱式表面。另一種方法就是由網(wǎng)格（顯式）表面轉(zhuǎn)換成距離值，利用三維紋理包含網(wǎng)格曲面存在的整個(gè)區(qū)域，并且每個(gè)網(wǎng)格單元保存該點(diǎn)離最近的網(wǎng)格表面的距離。本文會(huì)對(duì)上述兩種距離場(chǎng)生成方法進(jìn)行介紹。

1.2 隱式表面轉(zhuǎn)換距離場(chǎng)

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

float sdSphere( float3 p,float s)

{return length(p)-s;}

某一點(diǎn)據(jù)球體表面的距離就是該點(diǎn)據(jù)球心的距離減去球體半徑。

常使用布爾運(yùn)算例如并集、交集等方法將多個(gè)基本圖形的距離函數(shù)組成一個(gè)復(fù)雜的距離函數(shù)來(lái)表示復(fù)雜的圖形，布爾運(yùn)算具有保持Lipschitz 連續(xù)性的特性，因此能夠在距離場(chǎng)中依舊保持正確的梯度和距離。

float union( )

float distance1,float distance2

{return min(distance1,distacne2);}

關(guān)于各種形狀混合的代碼可以參考由Mercury 團(tuán)隊(duì)做的HG_SDF 距離場(chǎng)庫(kù)。

創(chuàng)建多個(gè)隱式圖元之后可以通過(guò)查詢(xún)每個(gè)離散網(wǎng)格元素的距離函數(shù)，并將這些值與布爾函數(shù)組合，使用最終結(jié)果的距離值填充三維紋理。由于大多數(shù)距離函數(shù)計(jì)算速度很快，因此可以在運(yùn)行時(shí)執(zhí)行距離的計(jì)算。由于無(wú)需保存網(wǎng)格數(shù)據(jù)，該方法被廣泛運(yùn)用在程序規(guī)模很小的圖形演示場(chǎng)景[6]中。

1.3 顯式表面轉(zhuǎn)換距離場(chǎng)

但是并非所有形狀都能通過(guò)隱式函數(shù)輕松生成，而且由于現(xiàn)代GPU 上高度優(yōu)化的渲染管線，幾乎所有開(kāi)發(fā)的游戲都使用三角網(wǎng)格來(lái)表示幾何圖形。對(duì)于游戲中有凹有凸的圖形，很難通過(guò)隱式函數(shù)對(duì)其進(jìn)行模擬。這時(shí)候就需要距離轉(zhuǎn)換算法實(shí)現(xiàn)網(wǎng)格幾何體到距離場(chǎng)表示的轉(zhuǎn)換。

最基本的距離變換算法是蠻力計(jì)算，對(duì)于每個(gè)網(wǎng)格單元計(jì)算該單元距離所有三角片元的距離，最短的距離存儲(chǔ)在距離場(chǎng)網(wǎng)格單元中。雖然蠻力算法計(jì)算代價(jià)十分昂貴，但是可以保證結(jié)果的正確性，并且該算法可以并行實(shí)現(xiàn)，非常適合GPU 計(jì)算。本文接下來(lái)會(huì)詳細(xì)介紹將現(xiàn)有的模型轉(zhuǎn)換成符號(hào)距離場(chǎng)的算法。

2 模型轉(zhuǎn)換符號(hào)距離場(chǎng)

蠻力算法是常用的距離變換算法中最簡(jiǎn)單的方法，首先必須選擇距離場(chǎng)網(wǎng)格的范圍和每個(gè)網(wǎng)格元素之間的距離。選擇具有相等尺寸（例如64×64×64）的三維數(shù)據(jù)集會(huì)導(dǎo)致很多空的單元格。通過(guò)分析要轉(zhuǎn)換的網(wǎng)格并根據(jù)網(wǎng)格的范圍縮放尺寸來(lái)壓縮距離場(chǎng)網(wǎng)格的大小，可以減少總體內(nèi)存占用。計(jì)算完網(wǎng)格大小以后，可以用以下算法計(jì)算每個(gè)網(wǎng)格的距離值：

Foreach GridCell in DistanceFieldGrid：

Foreach Triangle in Mesh：

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

該算法非常簡(jiǎn)單并且可以很容易通過(guò)CPU 并行處理。但是蠻力算法中計(jì)算每個(gè)網(wǎng)格到三角面片的最近距離時(shí)除了如圖2 所示需要考慮該點(diǎn)與三角形頂點(diǎn)、邊、面的最近距離，還需要知道該網(wǎng)格元素的符號(hào)。

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

2.1 點(diǎn)到三角形的距離

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

（1）三維方法

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

（2）二維方法

Jones[7]提出將三角形旋轉(zhuǎn)到y(tǒng)z 平面，將點(diǎn)p0到三角形的距離問(wèn)題由三維轉(zhuǎn)換成二維來(lái)解決。該方法需要預(yù)計(jì)算得到將三角形旋轉(zhuǎn)到y(tǒng)z 平面的旋轉(zhuǎn)矩陣。因?yàn)橐呀?jīng)將三角形旋轉(zhuǎn)到了yz 平面，點(diǎn)p0(x0,y0,z0)在yz 平面上的投影坐標(biāo)即為(0,y0,z0)。然后和三維方法一樣的檢查點(diǎn)與三角形的最接近特征，計(jì)算得到最短距離值。因?yàn)樵撍惴ㄐ枰罅啃D(zhuǎn)，導(dǎo)致距離場(chǎng)中存在許多不準(zhǔn)確性，所以本文采用三維計(jì)算距離的方法而未采用二維的計(jì)算方法。

2.2 符號(hào)計(jì)算

在計(jì)算最短距離之后，需要確定網(wǎng)格的符號(hào)，符號(hào)表示該網(wǎng)格單元與給定曲面的位置關(guān)系，如下函數(shù)所示：

由于僅針對(duì)閉合曲面定義了內(nèi)外部，因此會(huì)在未閉合的幾何體上返回錯(cuò)誤的結(jié)果。還有一種更簡(jiǎn)單的定義方式[8]：

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

然而在三角形的最接近特征是邊緣或點(diǎn)的情況下，如果最近的頂點(diǎn)由網(wǎng)格中的至少三個(gè)三角形共享或最近的邊緣由兩個(gè)三角形共享時(shí)，有時(shí)會(huì)產(chǎn)生不正確的結(jié)果。如圖3 所示，如果算法試圖找到最接近的三角形，則兩個(gè)三角形都符合。兩者都能用于符號(hào)計(jì)算，但是得到的符號(hào)相反?？梢允褂脗畏ň€n'代替三角形的實(shí)際法線來(lái)解決這種情況。法線n'只是共享最接近特征的所有三角形的法線之和。

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

本文采用Houston 等人[9]提出的基于可見(jiàn)性方法，先集成表面法線信息，然后利用單射線投射奇偶計(jì)數(shù)的方法來(lái)確定網(wǎng)格單元位于表面，內(nèi)部還是外部。

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

圖3 點(diǎn)P最靠近頂點(diǎn)V，該頂點(diǎn)由兩個(gè)三角形1，2共享

圖4 第二個(gè)三角形細(xì)分成3個(gè)三角形2，3，4

3 實(shí)驗(yàn)結(jié)果

本節(jié)將會(huì)展示將一個(gè)模型轉(zhuǎn)換成SDF 以后，利用Raytracing 的方式查看SDF，驗(yàn)證生成的距離場(chǎng)的正確性。實(shí)驗(yàn)設(shè)備為：

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

RAM：4.0 GB

System：Windows 10

GPU：NVIDIA GeForce GTX 1050

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

圖5

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

表1 不同模型生成距離場(chǎng)需要的時(shí)間

4 結(jié)語(yǔ)

本文給出了一種蠻力求解計(jì)算符號(hào)距離場(chǎng)的算法，通過(guò)輸入模型文件可以生成符號(hào)距離場(chǎng)，并且對(duì)生成的距離場(chǎng)利用光線行進(jìn)的方式進(jìn)行展示，驗(yàn)證了生成的距離場(chǎng)的正確性，得到了后續(xù)可以用于實(shí)時(shí)渲染效果的距離場(chǎng)。

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