• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2021-05-13 07:16:34何康本
      現(xiàn)代計(jì)算機(jī) 2021年8期
      關(guān)鍵詞:中心點(diǎn)繪制符號(hào)

      何康本

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

      0 引言

      隨著圖形處理器硬件的高速發(fā)展,使得繪制更高質(zhì)量的圖形效果變?yōu)榭赡堋H欢?,目前游戲中的?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)。

      猜你喜歡
      中心點(diǎn)繪制符號(hào)
      Art on coffee cups
      學(xué)符號(hào),比多少
      幼兒園(2021年6期)2021-07-28 07:42:14
      Scratch 3.9更新了什么?
      “+”“-”符號(hào)的由來
      如何設(shè)置造型中心點(diǎn)?
      電腦報(bào)(2019年4期)2019-09-10 07:22:44
      放學(xué)后
      童話世界(2018年17期)2018-07-30 01:52:02
      變符號(hào)
      漢字藝術(shù)結(jié)構(gòu)解析(二)中心點(diǎn)處筆畫應(yīng)緊奏
      尋找視覺中心點(diǎn)
      大眾攝影(2015年9期)2015-09-06 17:05:41
      圖的有效符號(hào)邊控制數(shù)
      中牟县| 乌什县| 四平市| 驻马店市| 克东县| 宁蒗| 麻阳| 诸暨市| 泗洪县| 龙海市| 工布江达县| 石狮市| 宜城市| 视频| 岚皋县| 临泉县| 双峰县| 东乌珠穆沁旗| 尉犁县| 互助| 嵊州市| 隆回县| 宁明县| 克拉玛依市| 白城市| 通州市| 井陉县| 五河县| 富顺县| 沙河市| 定西市| 印江| 永嘉县| 清原| 綦江县| 固始县| 社旗县| 辛集市| 和硕县| 广西| 龙陵县|