基于OpenMP 加速的符號(hào)距離場(chǎng)構(gòu)建算法實(shí)現(xiàn)

何康本

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

0 引言

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

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

符號(hào)距離場(chǎng)（Signed Distance Field）能夠表示空間中任意一點(diǎn)到最近物體表面的最短距離[4]。其能夠?qū)?chǎng)景的距離信息、物體表面信息進(jìn)行有效表達(dá)。在數(shù)學(xué)中，其為三維空間映射到一維空間中函數(shù)，具體定義為

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

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

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

1 算法實(shí)現(xiàn)

1.1 算法描述

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

1.2 符號(hào)距離函數(shù)表示符號(hào)距離場(chǎng)

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

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

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

圖1 簡(jiǎn)單圖形布爾運(yùn)算

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

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

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

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

2 并行加速模型轉(zhuǎn)符號(hào)距離場(chǎng)

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

2.1 空間中點(diǎn)到三角形最近距離計(jì)算

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

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

2.2 距離值符號(hào)確定

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

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

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

圖2 點(diǎn)P 處于頂點(diǎn)V ，兩個(gè)三角形1、2共享點(diǎn)P

2.3 OpenMP并行加速

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

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

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

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

本節(jié)將會(huì)對(duì)利用OpenMP 并行加速構(gòu)建符號(hào)距離場(chǎng)進(jìn)行效率測(cè)試。同時(shí)，在模型生成符號(hào)距離場(chǎng)后，利用球體追蹤的方式可視化符號(hào)距離場(chǎng)，以驗(yàn)證符號(hào)距離場(chǎng)構(gòu)建的準(zhǔn)確性。實(shí)驗(yàn)的主要軟硬件環(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ā)庫(kù)：C++、STL、OpenGL

表1 為本算法計(jì)算不同分辨率的符號(hào)距離場(chǎng)的程序運(yùn)行時(shí)間。

表1

圖4 展示利用龍模型生成的符號(hào)距離場(chǎng)，通過球體追蹤的方式進(jìn)行模型繪制。

4 結(jié)語(yǔ)

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

圖4 龍模型和其符號(hào)距離場(chǎng)，符號(hào)距離場(chǎng)分辨率為64×64×64

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