一種空間數(shù)據(jù)結(jié)構(gòu)加速的頂點(diǎn)與地形實(shí)時(shí)交互算法

鄒劉磊 徐安琦 張震 朱洪錦 范洪輝

摘要：針對動態(tài)場景的實(shí)時(shí)交互式渲染中，離散碰撞檢測算法導(dǎo)致的“穿模”現(xiàn)象，提出一種新的頂點(diǎn)與地形實(shí)時(shí)交互算法，并利用空間數(shù)據(jù)結(jié)構(gòu)進(jìn)行加速。算法利用頂點(diǎn)與模型表面多邊形的空間位置關(guān)系，首先計(jì)算頂點(diǎn)在當(dāng)前模型移動后的位置，然后計(jì)算本次移動與其他模型的相交情況，將移動沿路徑依次分解到每個(gè)經(jīng)過的面上，以此計(jì)算移動軌跡與終點(diǎn)位置。算法可通過層次包圍盒、八叉樹、KD樹等各類現(xiàn)有的空間數(shù)據(jù)結(jié)構(gòu)進(jìn)行加速。使用八叉樹，設(shè)計(jì)并實(shí)現(xiàn)了簡易的場景漫游與尋路，以此為實(shí)驗(yàn)環(huán)境進(jìn)行性能分析。實(shí)驗(yàn)數(shù)據(jù)證明，該方法能夠滿足實(shí)時(shí)性的要求，并且具有較高精度。

關(guān)鍵詞：實(shí)時(shí)交互式渲染;空間數(shù)據(jù)結(jié)構(gòu);碰撞檢測

計(jì)算機(jī)圖形學(xué)領(lǐng)域中，創(chuàng)建有效的視覺交流是研究的核心。其中，在實(shí)時(shí)渲染的三維場景中，涉及大量人機(jī)交互，交互時(shí)給予用戶以類似現(xiàn)實(shí)世界的視覺感受，是必不可少的。

實(shí)時(shí)渲染系統(tǒng)中，針對物體間交互的常用方法主要依賴動態(tài)碰撞檢測算法[1，2]。動態(tài)碰撞檢測主要可分為兩類，一類是連續(xù)碰撞檢測，另一類是離散碰撞檢測。離散碰撞檢測考慮經(jīng)過一段時(shí)間間隔后，物體間的碰撞檢測問題，因此，在復(fù)雜場景中存在穿模現(xiàn)象。連續(xù)碰撞檢測算法則能很好的計(jì)算運(yùn)動中的碰撞問題，但其速度較慢。因?qū)崟r(shí)性的要求，目前實(shí)時(shí)渲染中使用的技術(shù)主要為離散碰撞檢測。離散碰撞檢測中大部分算法都依賴于空間數(shù)據(jù)結(jié)構(gòu)加速。

空間數(shù)據(jù)結(jié)構(gòu)[3]是將幾何體組織在多維空間中的一系列數(shù)據(jù)結(jié)構(gòu)。空間數(shù)據(jù)結(jié)構(gòu)的組織通常是層次結(jié)構(gòu)的，用層次結(jié)構(gòu)的實(shí)現(xiàn)方式，使得幾何體訪問速度得到提升。空間數(shù)據(jù)結(jié)構(gòu)可以用于很多實(shí)時(shí)渲染相關(guān)操作的加速查詢中，如相交測試、碰撞檢測、裁減算法、場景管理、光線追蹤等。

常見的用于動態(tài)三維場景的空間數(shù)據(jù)結(jié)構(gòu)有：BSP樹及其變體[4]、八叉樹[5]、層次包圍盒[6，7]等。其中，層次包圍盒對物體本身所在空的進(jìn)行劃分，將物體分層放入幾何特性更為簡單的包圍盒，用包圍盒來進(jìn)行初步的碰撞檢測。BSP樹、八叉樹是基于空間分割思想[5]的空間數(shù)據(jù)結(jié)構(gòu)，從整個(gè)空間的角度進(jìn)行細(xì)分。

為了解決存在多個(gè)復(fù)雜模型的三維場景中，以某一個(gè)模型表面一點(diǎn)為起點(diǎn)沿某一模糊方向移動一定距離后，如何確定終點(diǎn)位置、如何確定移動軌跡的問題，本文提出一種空間數(shù)據(jù)結(jié)構(gòu)加速的頂點(diǎn)與地形實(shí)時(shí)交互算法。該算法有效的解決了離散碰撞檢測中的穿模問題，并能滿足實(shí)時(shí)性要求。算法核心思想為：根據(jù)三維模型表面多邊形與起點(diǎn)的空間位置關(guān)系，將移動分解到每個(gè)多邊形上，以此計(jì)算移動軌跡與終點(diǎn)位置。算法在查找相鄰三角形、不同物體間轉(zhuǎn)移時(shí)，可利用空間數(shù)據(jù)結(jié)構(gòu)，進(jìn)行進(jìn)一步的加速。

1? ? ?空間數(shù)據(jù)結(jié)構(gòu)加速的頂點(diǎn)與地形實(shí)時(shí)交互算法

提出一種頂點(diǎn)與地形實(shí)時(shí)交互算法，并利用空間數(shù)據(jù)結(jié)構(gòu)加速。該算法要求在可移動的空間內(nèi)，網(wǎng)格模型沒有孔洞或其他缺陷。可通過孔洞修補(bǔ)[8，9]對模型進(jìn)行預(yù)處理，以達(dá)到此要求。算法將移動沿路徑依次分解到每個(gè)經(jīng)過的多邊形上，下文以三角形網(wǎng)格模型為例。

上述步驟中，初始的S不可與F所在平面垂直，具體原因?yàn)镾與F所在平面垂直時(shí)，并非為沿物體表面移動，而表示一種離開表面的移動趨勢。

如上所述，其中步驟2、步驟3中的計(jì)算，可利用空間分割、層次包圍盒等空間數(shù)據(jù)結(jié)構(gòu)進(jìn)行加速。實(shí)驗(yàn)證明，算法利用空間數(shù)據(jù)結(jié)構(gòu)后，能十分有效的減少時(shí)間開銷。

算法可用于懸浮于物體表面的頂點(diǎn)移動，此時(shí)需要存儲頂點(diǎn)與所屬三角形的初始間隔距離，并在各步驟中考慮此距離。算法可拓展至三角形圖元以外的模型數(shù)據(jù)存儲方式，此時(shí)，僅需將移動分解至單個(gè)面上。算法可用于計(jì)算移動路徑，只需在循環(huán)中每次記錄位置即可。

1.1? ?單個(gè)模型內(nèi)移動

步驟2.1中，所在三角形F，分為三種情況。其一，O與三角形頂點(diǎn)重合時(shí)，則F為所有共有此頂點(diǎn)的三角形。其二，O位于三角形邊上時(shí)，則F為共有此邊的所有三角形。其三，O位于某三角形內(nèi)時(shí)，則F為該三角形。

如步驟2.3中所述的交點(diǎn)，每次計(jì)算時(shí)有且僅有兩個(gè)點(diǎn)。因?yàn)椴豢紤]S與F法線平行的情況，所以兩個(gè)點(diǎn)分別令OO與S夾角大于或小于90°。依據(jù)S的趨勢，O需滿足：OO與S夾角小于90°。

上述算法中，步驟2.3中計(jì)算交點(diǎn)時(shí)，若O與F中三角形頂點(diǎn)重合時(shí)，可能出現(xiàn)F中的某一個(gè)三角形的邊位于平面P內(nèi)。此時(shí)，O的位置須根據(jù)移動限制進(jìn)行計(jì)算，亦可延后至步驟3計(jì)算。如算法用于控制游戲角色時(shí)，模擬重力系統(tǒng)，此時(shí)O的選擇為高度較低的點(diǎn)。

1.2? ? 多個(gè)模型間移動與移動限制

步驟3中碰撞檢測時(shí)，若存在數(shù)個(gè)可在其表面移動的物體，物體間移動的計(jì)算方式，其流程如圖3所示，其文字描述具體步驟如下。

步驟3.1：如果場景中存在其他允許在其表面移動的模型，且OO（不含O點(diǎn)）與這些模型存在交點(diǎn)（若O、O均屬于此時(shí)相交三角形所在平面或與三角形邊有重合，則碰撞檢測時(shí)不考慮此三角形）;則執(zhí)行步驟3.2;否則步驟結(jié)束。

步驟3.2：C=與O距離最短的交點(diǎn)。

步驟3.3：找出C在相交的模型上所在的所有三角形，計(jì)算P與這些三角形邊的交點(diǎn)。

步驟3.4：如果交點(diǎn)中存在滿足K的法線與交點(diǎn)屬于的三角形所在的面的夾角小于90°的點(diǎn);則S=normalize（線段OC與交點(diǎn)屬于的三角形所在的面夾角最小者-O）;M=交點(diǎn)所在模型;O=C。

步驟3.3中所述的所有三角形與步驟2.1中情況類似，兩者需要遍歷M上的所有三角形，遍歷的過程可通過空間數(shù)據(jù)結(jié)構(gòu)加速。步驟3.1中的碰撞檢測，也可以使用空間數(shù)據(jù)結(jié)構(gòu)加速。

上述步驟3中所述的移動限制，需根據(jù)不同系統(tǒng)中的要求進(jìn)行相應(yīng)變化，可以為：與其他不可在其表面移動的物體產(chǎn)生碰撞、高度限制、邊界限制、移動時(shí)仰角限制等，該步驟有可能需要算法提前結(jié)束。比如：場景中移動存在邊界限制情況下，OO與邊界相交時(shí)，如果O點(diǎn)不與OO、邊界的交點(diǎn)重合，則將交點(diǎn)值賦給O，否則算法提前結(jié)束。

2? ? ?實(shí)驗(yàn)與性能分析

基于上文描述的方法，使用八叉樹進(jìn)行場景

管理，筆者設(shè)計(jì)并實(shí)現(xiàn)了簡易的場景漫游與尋路。以此，對八叉樹層數(shù)為4、模型相同（400個(gè)頂點(diǎn)、722個(gè)三角形）、模型數(shù)量不同時(shí)的計(jì)算速度進(jìn)行了測試。十組測試數(shù)據(jù)處理后如表1所示。

同時(shí)，對單個(gè)模型下（400個(gè)頂點(diǎn)、722個(gè)三角形），八叉樹最高層數(shù)對計(jì)算速度的影響進(jìn)行了測試，數(shù)據(jù)如表2所示。

從數(shù)據(jù)顯示可知，模型個(gè)數(shù)對算法速度有較大影響，并且最短時(shí)間與最長時(shí)間差異較大，分析后可知，其主要原因?yàn)椴煌Ｐ烷g的碰撞檢測時(shí)間消耗差異較大，并帶有一定隨機(jī)性。八叉樹最高層數(shù)對算法有較大影響，空間劃分越細(xì)，速度越快。因此可知，算法性能主要由空間數(shù)據(jù)結(jié)構(gòu)決定，空間數(shù)據(jù)結(jié)構(gòu)為算法的主要的性能瓶頸。

3? ? ?結(jié)論

針對交互式實(shí)時(shí)渲染中，頂點(diǎn)與復(fù)雜三維場景交互時(shí)，常規(guī)的離散碰撞檢測易發(fā)生穿模現(xiàn)象，提出一種空間數(shù)據(jù)結(jié)構(gòu)加速的頂點(diǎn)與地形實(shí)時(shí)交互算法。算法首先計(jì)算頂點(diǎn)在當(dāng)前模型移動后的位置，然后計(jì)算本次移動與其他模型的相交情況，有效解決了動態(tài)場景中的穿模問題，并能夠滿足實(shí)時(shí)渲染的性能要求。實(shí)驗(yàn)證明，算法性能主要依賴空間數(shù)據(jù)結(jié)構(gòu)加速后，數(shù)據(jù)的查詢速度。

參考文獻(xiàn)：

[1] 馮立穎.碰撞檢測技術(shù)研究綜述[J].計(jì)算機(jī)時(shí)代，2014（8）：7-10.

[2] 劉復(fù)昌，王雙建，潘志庚，等.并行化碰撞檢測算法綜述[J]. 系統(tǒng)仿真學(xué)報(bào)， 2017（11）：2601-2607.

[3] 吳元洪，郭平，應(yīng)新洋.空間數(shù)據(jù)結(jié)構(gòu)分析[J]. 計(jì)算機(jī)應(yīng)用研究，2004（3）：39-41.

[4] AR S，CHAZELLE B，TAL A.Self-customized BSP trees for collision detection[J]. Computational Geometry，2000，15（1-3）：91-102.

[5] MEI K J，LEE R S.Collision detection for virtual machine tools and virtual robot arms using the Shared Triangles Extended Octrees method[J].International Journal of Computer Integrated Manufacturing，2016，29（4）：355-373.

[6] SCHWESINGER U，SIEGWART R，F(xiàn)URGALE P T.Fast collision detection through bounding volume hierarchies in workspace-time space for sampling-based motion planners[C].ICRA，2015：63-68.

[7] WANG X，TANG M，MANOCHA D， et al.Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring[C].Computer Graphics Forum，2018，37（2）： 227-237.

[8] 謝倩茹，耿國華.三維模型孔洞修補(bǔ)方法的研究[J].計(jì)算機(jī)應(yīng)用研究，2013，30（10）：3175-3177.

[9] 王運(yùn)鋼，徐巖軍，林海榮. 基于雙向切片的點(diǎn)云孔洞修補(bǔ)方法研究[J]. 測繪與空間地理信息，2015， 38（10）： 218-220.

Abstract： For real-time interactive rendering of dynamic scenes， the phenomenon of mutual penetration or superposition of objects caused by discrete collision detection algorithms， this paper proposes a new real-time interaction algorithm between vertex and terrain， and accelerates with spatial data structure. The algorithm uses the spatial positional relationship between the vertex and the surface polygon of the model. Firstly， the position of the vertex after the current model is moved is calculated. Then， the intersection of the current movement and other models is calculated， and the movement is sequentially decomposed along the path to each passing surface to This calculates the movement path and the end position. The algorithm can be accelerated by various existing spatial data structures such as bounding volume hierarchies， octrees， and KD trees. In this paper， we use octree to design and implement simple scene roaming and pathfinding to analyze the performance of the experimental environment. The experimental data proves that the method can meet the requirements of real-time and has?high precision.

Key words： real-time interactive rendering; spatial data structure; collision detection

責(zé)任編輯? ? 張志釗