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

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

關鍵詞：實時交互式渲染;空間數(shù)據(jù)結構;碰撞檢測

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

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

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

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

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

1? ? ?空間數(shù)據(jù)結構加速的頂點與地形實時交互算法

提出一種頂點與地形實時交互算法，并利用空間數(shù)據(jù)結構加速。該算法要求在可移動的空間內，網格模型沒有孔洞或其他缺陷?？赏ㄟ^孔洞修補[8，9]對模型進行預處理，以達到此要求。算法將移動沿路徑依次分解到每個經過的多邊形上，下文以三角形網格模型為例。

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

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

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

1.1? ?單個模型內移動

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

如步驟2.3中所述的交點，每次計算時有且僅有兩個點。因為不考慮S與F法線平行的情況，所以兩個點分別令OO與S夾角大于或小于90°。依據(jù)S的趨勢，O需滿足：OO與S夾角小于90°。

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

1.2? ? 多個模型間移動與移動限制

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

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

步驟3.2：C=與O距離最短的交點。

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

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

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

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

2? ? ?實驗與性能分析

基于上文描述的方法，使用八叉樹進行場景

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

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

從數(shù)據(jù)顯示可知，模型個數(shù)對算法速度有較大影響，并且最短時間與最長時間差異較大，分析后可知，其主要原因為不同模型間的碰撞檢測時間消耗差異較大，并帶有一定隨機性。八叉樹最高層數(shù)對算法有較大影響，空間劃分越細，速度越快。因此可知，算法性能主要由空間數(shù)據(jù)結構決定，空間數(shù)據(jù)結構為算法的主要的性能瓶頸。

3? ? ?結論

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

參考文獻：

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

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

[3] 吳元洪，郭平，應新洋.空間數(shù)據(jù)結構分析[J]. 計算機應用研究，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] 謝倩茹，耿國華.三維模型孔洞修補方法的研究[J].計算機應用研究，2013，30（10）：3175-3177.

[9] 王運鋼，徐巖軍，林海榮. 基于雙向切片的點云孔洞修補方法研究[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

責任編輯? ? 張志釗