何康本

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

0 引言

隨著圖形處理器硬件的高速發(fā)展，使得繪制更高質(zhì)量的圖形效果變?yōu)榭赡?。然而，目前游戲中的實時繪制的繪制效果仍然和離線渲染的真實效果（Ground-Truth）間較大的差距。近些年來，硬件公司一直通過優(yōu)化硬件來彌補差距，2020 年NVIDIA 公司在2018 年發(fā)布的顯卡基礎(chǔ)上，進一步優(yōu)化硬件性能，發(fā)布最新光線追蹤優(yōu)化的顯卡。然而，光線追蹤過程中需要求解渲染方程，其中設(shè)計大量的積分計算，想要在游戲中實時實現(xiàn)基于物理的實時全局光照效果仍然需要時間。同時，支持光線追蹤顯卡價格昂貴，老一代顯卡并不支持硬件光線追蹤。因此，使用其他渲染方法便成為人們關(guān)注的焦點，利用符號距離場進行圖形繪制便是其中之一。

利用符號距離場進行場景繪制的應(yīng)用在近些年來大量增多。早在2013 年，Rougier[1]利用符號距離場實現(xiàn)高質(zhì)量的2D 文本繪制。在2015 年的Siggraph 大會上，Wright 等人[2]利用符號距離場實現(xiàn)環(huán)境光遮蔽（Ambient Occlusion）、軟陰影（Soft Shadow）等渲染效果。在2018 年GDC 上，Sebastian[3]介紹符號距離場在游戲《Claybook》中的應(yīng)用，其只利用符號距離場進行場景的繪制，同時在Wright[2]實現(xiàn)環(huán)境光遮蔽（Ambient Occlusion）、軟陰影（Soft Shadow）等效果的基礎(chǔ)上，進一步提升渲染效果。

符號距離場（Signed Distance Field）能夠表示空間中任意一點到最近物體表面的最短距離[4]。其能夠?qū)鼍暗木嚯x信息、物體表面信息進行有效表達。在數(shù)學(xué)中，其為三維空間映射到一維空間中函數(shù)，具體定義為

其中S 是構(gòu)成模型的點，這些點的組成整個物體對象。函數(shù)Sign 用以確定點是否在模型內(nèi)部，若在內(nèi)部則返回-1，反之為1。

符號距離場實則是符號距離函數(shù)的近似，即可完全使用符號距離函數(shù)代替符號距離場。然而，在游戲場景中，大多數(shù)物體構(gòu)造往往十分復(fù)雜，不具備解析的符號距離函數(shù)。故在游戲中，常常通過網(wǎng)格離散化物體，并通過計算網(wǎng)格中心的符號距離值來構(gòu)造符號距離場，同時將相應(yīng)的計算值存儲在體紋理中，從而方便在渲染時使用。然而上述預(yù)計算符號距離場，存在計算量極大，導(dǎo)致計算效率不高及耗時長的問題。

本文將三維模型作為輸入，通過OpenMP 庫并行加速三維模型符號距離場的生成，進行相關(guān)效率對比及通過球體追蹤的方式驗證符號距離場生成的正確性。

1 算法實現(xiàn)

1.1 算法描述

符號距離場有多種生成方式，其中最主要的兩種分別是符號距離函數(shù)及網(wǎng)格轉(zhuǎn)換算法。其中第一種方法適用于具有解析符號距離函數(shù)的三維圖形，如球、正方體等，同時，對于復(fù)雜模型，則可利用符號距離函數(shù)進行一系列布爾運算，得出相應(yīng)的符號距離函數(shù)。另一種方式是通過距離轉(zhuǎn)換算法，將三維網(wǎng)格模型轉(zhuǎn)化生成符號距離場，該方法可利用OpenMP 進行并行加速。下面，將對上述兩種算法概述。

1.2 符號距離函數(shù)表示符號距離場

符號距離函數(shù)在數(shù)學(xué)中用于表示點到表面的最近距離，是表示距離場最簡單的方式。大部分基本圖形都有著解析的符號距離函數(shù)，但不同的幾何圖形的符號距離函數(shù)也并不同。模型間的符號距離函數(shù)的計算復(fù)雜度也有著區(qū)別，但都以空間中點的位置坐標作為輸入，計算出相應(yīng)的符號距離值。以球為例，其符號距離函數(shù)如公式（3）所示：

其中(x,y,z)表示空間中任意一點位置，(xr,yr,zr)表示球體中心點坐標，r表示球半徑。

對于復(fù)雜模型而言，其并不具備直接解析的符號距離函數(shù)，可通過簡單模型的符號距離函數(shù)通過布爾運算組合而成，圖1 可視化該過程。通過組合運算，并不影響符號距離值計算的正確性。

圖1 簡單圖形布爾運算

由于符號距離函數(shù)計算復(fù)雜度低，可直接在GPU中進行相應(yīng)計算，能夠滿足運行時實時計算的需求。同時，其不包含三角網(wǎng)格數(shù)據(jù)，幾乎不占用內(nèi)存空間，在小型繪制場景中，常常利用符號距離函數(shù)進行模型的相應(yīng)繪制[5]。

1.3 網(wǎng)格轉(zhuǎn)換符號距離場

在游戲場景中，存在許多十分復(fù)雜的模型，其并不具備解析的符號距離函數(shù)。同時，由于圖形處理器定制化的繪制管線，在游戲行業(yè)中，往往使用三角網(wǎng)格對物體進行建模表示。對于上述這些物體，無法通過符號距離函數(shù)表示符號距離場。為此，可通過距離變換算法將網(wǎng)格模型轉(zhuǎn)化為相應(yīng)的符號距離場。

在過去的幾十年中，提出了各種各樣的網(wǎng)格距離變換算法。蠻力法（Brute Force Algorithm）作為其中之一，有著計算準確性高、數(shù)值穩(wěn)定性強等特點。蠻力法通過遍歷所有的網(wǎng)格中心點，計算該點到構(gòu)造模型所有三角形的距離，取最小值作為輸出結(jié)果。該算法容易實現(xiàn)并行，為此，可通過OpenMP 并行庫對其進行并行加速。下面，本文將對利用OpenMP 并行庫加速模型烘焙出符號距離場算法進行詳細描述。

2 并行加速模型轉(zhuǎn)符號距離場

不同模型有著不同的三角面片數(shù)量，伴隨著不同的復(fù)雜程度。對于復(fù)雜的模型，則需要利用更為精細的網(wǎng)格對其進行表示，即需要構(gòu)造更高分辨率的符號距離場。在確定相應(yīng)分辨率后，可計算出相應(yīng)的網(wǎng)格中心點。在蠻力法中，根據(jù)網(wǎng)格中心點在模型空間的坐標位置，遍歷所有三角網(wǎng)格，計算該點距三角網(wǎng)格的最近距離，作為最終的距離值。同時，根據(jù)三角形的頂點順序確定相應(yīng)符號，最終得出符號距離值。

2.1 空間中點到三角形最近距離計算

蠻力法生成符號距離場過程中的計算空間中點到三角形的最近距離是極為關(guān)鍵的一步，其計算正確才能保證符號距離場構(gòu)建準確。

Jones 等人[6]提出一種快速有效的點到三角形最近距離的計算方法。首先，確定網(wǎng)格分辨率，計算出相應(yīng)的網(wǎng)格中心點坐標p。其次，將網(wǎng)格中心點p投影到三角形所處的平面中，并計算出相應(yīng)的投影點坐標p'。然后，通過重心法判斷p'是否處于三角形中，若處于三角形中，則距離值為網(wǎng)格中心點和投影坐標點的矢量距離。反之，則需進行進一步計算，即計算三角形三條邊中距離p'最近的點q的坐標位置，最終距離值為點p和點q之間的歐氏距離。該方法在保證距離計算的正確性，能夠確保數(shù)值的穩(wěn)定性，同時易于并行加速。

2.2 距離值符號確定

蠻力法確定距離值后，便需進行對該距離值符號得確定，進一步表達相應(yīng)網(wǎng)格中心點相對于物體信息，即該點處于物體內(nèi)部還是外部。符號得確定是保證符號距離場構(gòu)建正確的關(guān)鍵之一。

符號距離值得符號可通過公式（4）進行確定。其具體思想為，在給定空間中任意一點坐標位置p 的條件下，通過2.1 小節(jié)中計算的最近點q，確定矢量(p-q)。同時，計算出q點所在三角形的法向量。計算矢量(p-q)和法向量n的夾角，若夾角大于90 度，則確定符號為-1，等于90 度，為0，小于90 度則為1。為方便計算，可通過公式（4）中點乘的正負值進行相應(yīng)確定。在計算出符號后，通過符號和距離值得乘積確定符號距離值。

然而，由于構(gòu)造模型的三角網(wǎng)格往往共享相同的邊，通過公式（4）進行符號計算，可能存在符號計算不正確的情況。如圖2 所示，通過2.1 小節(jié)找到最近的三角形，則會存在兩個三角形都滿足的情況。然而，兩個三角形根據(jù)公式（4）所計算出的符號卻截然相反。為此，可以通過平均混合兩個三角形的法線得出最終用于確定符號得法線值n' 。通過n' 和(p-q)代入公式（4）中計算出最終的符號距離值。

圖2 點P 處于頂點V ，兩個三角形1、2共享點P

2.3 OpenMP并行加速

在過去的一些年中，實現(xiàn)并行計算的方法多種多樣。CPU 上的并行計算一般基于OpenMP 或MPI，分別適用于共享內(nèi)存多處理器系統(tǒng)和分布式內(nèi)存并行系統(tǒng)。MPI 適用于粗粒度并行計算，特別是集群系統(tǒng)；OpenMP 適合細粒度并行計算，通常用于對稱多處理器平臺（SMP），它充分利用了CPU 中的多個處理核心[7]。由于在符號距離場中需要遍歷網(wǎng)格中心點及物體所有的三角面片，在C++環(huán)境中利用模型生成符號距離場的工作通常在SMP 上進行，因此基于OpenMP 的并行計算對加速符號距離場的生成更為實用。

OpenMP 由一組描述并行性的編譯器指令和一個支持的子程序庫組成[8]。OpenMP 基于多線程的方法，采用標準的fork-join 并行化模型，如圖3 所示。串行域中的主線程（連續(xù)執(zhí)行一系列指令）在遇到并行域時分叉出指定數(shù)量的從線程(Tid0,Tid1,Tid2,…)，這使得系統(tǒng)在這些線程之間劃分一個任務(wù)，然后這些線程并行獨立地運行。在并行化代碼完成后，這些線程重新連接到主線程中，主線程繼續(xù)連續(xù)執(zhí)行指令。OpenMP可以直接嵌入到源代碼中，從而為串并行轉(zhuǎn)換提供了一個簡單的快捷方式?；贠penMP 的并行計算模型具有低延遲、高帶寬的特點。為此，利用OpenMP 可并行加速符號距離場的生成，能夠大大減少生成耗時。

圖3 Fork-join多線程處理模式

3 實驗結(jié)果

本節(jié)將會對利用OpenMP 并行加速構(gòu)建符號距離場進行效率測試。同時，在模型生成符號距離場后，利用球體追蹤的方式可視化符號距離場，以驗證符號距離場構(gòu)建的準確性。實驗的主要軟硬件環(huán)境配置如下所示。

硬件環(huán)境：

CPU：Intel Core i3-6100 CPU@3.70GHz

內(nèi)存：20.0GB

顯卡：NVIDIA GeForce GTX 1060 3GB

軟件環(huán)境：

操作系統(tǒng)：Windows 10

編譯器：Visual Studio 2019

開發(fā)庫：C++、STL、OpenGL

表1 為本算法計算不同分辨率的符號距離場的程序運行時間。

表1

圖4 展示利用龍模型生成的符號距離場，通過球體追蹤的方式進行模型繪制。

4 結(jié)語

本文給出了一種基于OpenMP 并行加速生成符號距離場的算法。通過輸入構(gòu)造模型的網(wǎng)格文件，計算出相應(yīng)的符號距離場，并且對其加速效率進行測試，及利用球體追蹤方式對其可視化，驗證距離場構(gòu)建的準確性。

圖4 龍模型和其符號距離場，符號距離場分辨率為64×64×64

通過本文的方法可以快速生成符號距離場，但是符號距離場的構(gòu)建時間仍然和模型的三角網(wǎng)格數(shù)量，以及烘焙的分辨率存在正相關(guān)的聯(lián)系。在模型數(shù)量過多，分辨率過高的情況下，生成距離場所需的時間仍然很多。為此，在接下來工作中，可通過GPU 加速的方式進行進一步加速生成符號距離場。