馬永斌 詹華蕊

摘? 要：三維虛擬場(chǎng)景中事物之間的交互可以滿足場(chǎng)景真實(shí)感并提高用戶的沉浸感，精確、快速地碰撞檢測(cè)對(duì)提高虛擬環(huán)境交互的真實(shí)性有著非常重要的作用，而虛擬交互下的碾壓場(chǎng)景的復(fù)雜性、實(shí)時(shí)性和精確性又對(duì)碰撞檢測(cè)提出了更高的要求。本文以草體被物體踩壓為例，對(duì)虛擬場(chǎng)景中事物間的交互過程進(jìn)行分析和研究。

關(guān)鍵詞：三維;虛擬場(chǎng)景;交互;碾壓碰撞算法

中圖分類號(hào)：TP391.9? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）09-0171-03

1? 交互過程中算法分析

本文以簡(jiǎn)單的小圓球來代替復(fù)雜物體模擬草體被碾壓后出現(xiàn)的動(dòng)態(tài)交互過程，具體過程中要解決三個(gè)問題，即球體在碾壓過程中每個(gè)階段需要變形的草體獲得、草體的碾壓計(jì)算和變形結(jié)束后草體的原貌恢復(fù)計(jì)算[1]。

在獲得球體碾壓作用下變形的草體時(shí)，本文利用包圍盒技術(shù)將球體用包圍盒表示。由于草被小球碾壓的過程是連續(xù)的、實(shí)時(shí)的，因此，草體的作用范圍的變化與小球滾動(dòng)的速度密切相關(guān)。為了使計(jì)算研究中出現(xiàn)的是連續(xù)的草體變形軌跡，將球體滾動(dòng)的當(dāng)前幀位置和球體的前一幀位置用一條連線來表示，作為球體的碾壓作用范圍中矩形的一條邊，而矩形中的另一條邊則由球體包圍盒中的邊長(zhǎng)決定。獲得了碾壓作用范圍的草體，則需要在渲染前確定好這些作用域。為了使CPU和GPU之間擁有高效的數(shù)據(jù)傳送速率，將大規(guī)模草地對(duì)應(yīng)的地形分為多個(gè)小網(wǎng)格進(jìn)行渲染，利用球體滾動(dòng)的當(dāng)前幀位置與球體的前一幀位置來做判斷，僅查詢這些幀位置所經(jīng)過的網(wǎng)格，然后確定這些網(wǎng)格中的草體是否需要變形。由于小球的滾動(dòng)方向是一個(gè)隨機(jī)草體變形的軌跡，為了方便計(jì)算，將任意方向的作用域和我們所要查詢確定的草體給定點(diǎn)同時(shí)進(jìn)行平移、旋轉(zhuǎn)至坐標(biāo)原點(diǎn)，獲得一個(gè)精確的需要變形的草體作用范圍。

接下來，對(duì)已經(jīng)確定變形的草體進(jìn)行碾壓計(jì)算。對(duì)于單棵草體來說，它的交互變形效果是草體根部的變形程度明顯大于其上部的變形程度，碾壓向量則由草體根部開始向上進(jìn)行計(jì)算。在建模中，對(duì)草體使用三個(gè)矩形來簡(jiǎn)單模擬，如圖1所示。節(jié)點(diǎn)1、2、3、4是用來調(diào)整草體的彎曲變形程度的，而球體的圓心到草體根部點(diǎn)的向量用來確定草體被碾壓的方向。由于球體底部正下方的草體是完全被擠壓且看不到，因此選擇球體剛離開時(shí)的草體狀態(tài)作為臨界點(diǎn)來進(jìn)行模擬。

如圖2所示，軌跡a表示草體的原始狀態(tài)，軌跡b表示草體的臨界狀態(tài)，h表示軌跡b中節(jié)點(diǎn)2離地面的高度。為了方便分析，設(shè)每一節(jié)草體的長(zhǎng)度為L(zhǎng)且不變，軌跡b中的節(jié)點(diǎn)2在x軸方向上的偏移量可以通過L和h的值求得，偏移方向則與碾壓軌跡方向一致，節(jié)點(diǎn)3和節(jié)點(diǎn)4用同樣的方法，并在節(jié)點(diǎn)2的基礎(chǔ)上，可以計(jì)算出它們的x軸方向的偏移量和偏移方向。本文還假設(shè)草體被碾壓前后的相鄰節(jié)段的草體骨架之間的夾角不變，用它們的補(bǔ)角表示為θ1=φ1，θ2=φ2。通過將軌跡b中節(jié)點(diǎn)2的切線方向在切點(diǎn)處順時(shí)針旋轉(zhuǎn)θ1度，在新的方向上加上預(yù)設(shè)的每節(jié)草體的固定長(zhǎng)度L，就可以得到變形后軌跡b中節(jié)點(diǎn)3的坐標(biāo)了，節(jié)點(diǎn)4的坐標(biāo)用同樣的方法可以計(jì)算得到。

為了使草體在碾壓后有一個(gè)平滑過渡的變形，可以采用一種基于草體骨架線的隱式曲面的計(jì)算公式來計(jì)算草體的碾壓向量[2]：

（1）

如圖3所示，在平滑過渡原理中，v0和v1分別表示球體當(dāng)前幀位置和球體前一幀位置，P代表當(dāng)前需要變形的草體位置，H點(diǎn)是草體位置在v0、v1上的投影。由公式可知，我們可以調(diào)節(jié)草體的變形彎曲程度，即改變圖中點(diǎn)H的位置，而圖中的θ0和θ1則反映了草體位置分別距離球體當(dāng)前幀與球體前一幀的位置方向。

為了恢復(fù)草體為交互變形前的原貌，本文采用Catmull-Rom樣條對(duì)草體頂點(diǎn)的碾壓向量進(jìn)行插值運(yùn)算，在GPU中實(shí)現(xiàn)碾壓向量的更新計(jì)算，最后完成草體頂點(diǎn)的更新，將其平滑度恢復(fù)到原貌。如圖4所示，將草體處于變形狀態(tài)的時(shí)間先保存下來，當(dāng)前草體的狀態(tài)就是圖中的臨界狀態(tài)，節(jié)點(diǎn)2、3、4分別創(chuàng)建樣條插值，虛線部分代表插值的過渡狀態(tài)，其中插值間隔越短說明草體恢復(fù)越快。然后在GPU中實(shí)現(xiàn)草體的碾壓向量的更新計(jì)算，分擔(dān)CPU的工作量，提高運(yùn)行速率。根據(jù)草體當(dāng)前狀態(tài)的時(shí)間和變形狀態(tài)的時(shí)間記錄，在頂點(diǎn)著色器中調(diào)用Catmull-Rom插值函數(shù)，計(jì)算出草體新的碾壓向量，將它在正切空間中作用于草體的頂點(diǎn)位置，完成草體頂點(diǎn)的更新，進(jìn)而恢復(fù)草體原貌。

2? 碰撞檢測(cè)計(jì)算

本文采用基于骨架線的快速碰撞檢測(cè)算法[3，4]，使得檢測(cè)草體間的碰撞轉(zhuǎn)變成單株草體骨架線與另一株草體模型的相交檢測(cè)。首先獲得草體的碰撞作用域，然后對(duì)作用域內(nèi)的草體進(jìn)行碰撞檢測(cè)計(jì)算，確定草體的位置，避免出現(xiàn)穿透現(xiàn)象。

由于草體被小球碾壓時(shí)，被擠壓的草體只與它周圍有限范圍內(nèi)的草體發(fā)生碰撞，為了確定草體的碰撞作用域，可以將當(dāng)前草體的位置作為圓心，以草體的長(zhǎng)度作為半徑畫圓作為碰撞檢測(cè)范圍。其中，碰撞檢測(cè)范圍的大小可以通過改變圓的半徑值來進(jìn)行調(diào)節(jié)。如圖5所示，當(dāng)前草體的骨架線用Ι1Ι2Ι3Ι4表示，另一株草體用多邊形Η1Η2Η3Η4Η5Η6Η7Η8表示，其中，用Ι1'Ι2'Ι3'Ι4'表示草體沒有發(fā)生碰撞時(shí)被碾壓后應(yīng)到達(dá)的位置。若線段ΙnΙn'與另一株草體的矩形任一邊相交，則說明草體間發(fā)生了碰撞。由圖5可知，以Ι1為圓心的弧段Ι4Ι4'與Η1Η2Η3Η4Η5Η6Η7Η8相交于點(diǎn)P，那么P點(diǎn)處則為Ι4'碰撞后應(yīng)該達(dá)到的位置，其余點(diǎn)碰撞后的位置可由等比例位移依次得到。

若Ι4'P之間的距離為d，那么Ιn'點(diǎn)的位移則可表示為：

（2）

其中，L和Ln分別表示單株草中草體的總長(zhǎng)和第n節(jié)草的長(zhǎng)，進(jìn)而計(jì)算出發(fā)生碰撞后草體應(yīng)該達(dá)到的位置I1"I2"I3"P，最終確定出草體的位置，避免場(chǎng)景中各物體間進(jìn)行交互時(shí)出現(xiàn)穿透的失真現(xiàn)象。

3? 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文方法的有效性，相應(yīng)的交互實(shí)驗(yàn)在PC機(jī)上進(jìn)行了多次。該實(shí)驗(yàn)中的草地場(chǎng)景擁有草體三角形數(shù)目約為50萬，分辨率為1024×768。

在場(chǎng)景交互過程中，草體碾壓效果的實(shí)現(xiàn)可以分為以下三個(gè)步驟：

（1）獲取球體滾動(dòng)時(shí)的作用范圍。

（2）對(duì)前面作用范圍內(nèi)的草體進(jìn)行碾壓計(jì)算。

（3）使被碾壓的草體恢復(fù)原狀。

實(shí)驗(yàn)結(jié)果如圖6中所示，圖6（a）和圖6（b）是草體沒有采取碰撞檢測(cè)計(jì)算的效果，而圖6（c）和圖6（d）是草體采取了碰撞檢測(cè)計(jì)算的效果。從兩圖的對(duì)比中可以看出，在沒有考慮碰撞檢測(cè)時(shí)，在小球碾壓草體的交互過程中會(huì)出現(xiàn)部分草體穿透小球的現(xiàn)象;而考慮并采取了碰撞檢測(cè)的效果圖中，草體不再穿透球體，場(chǎng)景的真實(shí)感具有明顯增強(qiáng)。

（a）草體沒有采取碰撞檢測(cè)計(jì)算的效果（單點(diǎn)碰撞）

（b）草體沒有采取碰撞檢測(cè)計(jì)算的效果（多點(diǎn)碰撞）

（c）草體采取了碰撞檢測(cè)計(jì)算的效果（單點(diǎn)碰撞）

（d）草體采取了碰撞檢測(cè)計(jì)算的效果（多點(diǎn)碰撞）

4? 結(jié)? 論

本文主要對(duì)三維場(chǎng)景中交互過程中的算法進(jìn)行了分析與研究，以小球碾壓草體為例，實(shí)現(xiàn)了真實(shí)感較好的交互動(dòng)態(tài)變形過程，并同時(shí)考慮了交互過程中的碰撞檢測(cè)。在交互過程中，首先利用球體包圍盒獲得需要變形的草體，然后以一個(gè)臨界狀態(tài)表示單株草體的變形狀態(tài)，通過草體骨架線的隱式曲面計(jì)算公式計(jì)算出草體的碾壓向量，最后采用Catmull-Rom樣條插值方法將草體恢復(fù)至原貌。

參考文獻(xiàn)：

[1] 韓光輝，徐鵬飛，周明全.實(shí)時(shí)碰撞檢測(cè)中的穿透問題研究與解決 [J].北京師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，47（4）：370-373.

[2] 何援軍.計(jì)算機(jī)圖形學(xué) [M].北京：機(jī)械工業(yè)出版社，2009.

[3] 蔡鵬，趙偉，任大鵬.行人仿真系統(tǒng)中的碰撞檢測(cè)與避讓 [A].中國(guó)建筑科學(xué)研究院、金融街控股股份有限公司 [C].第十五屆全國(guó)工程設(shè)計(jì)計(jì)算機(jī)應(yīng)用學(xué)術(shù)會(huì)議，中國(guó)黑龍江哈爾濱：中國(guó)土木工程學(xué)會(huì)、中國(guó)建筑學(xué)會(huì)、中國(guó)工程圖學(xué)學(xué)會(huì)，2010：297-301.

[4] Decaudin P，Neyret F. Rendering Forest Scenes in Real-Time [C]// Fifteenth Eurographics Conference on Rendering Techniques. Eurographics Association，2004：56-63.

[5] 王長(zhǎng)波.基于物理模型的自然景物真實(shí)感繪制 [D].杭州：浙江大學(xué)，2006.

[6] Wan HG，F(xiàn)an ZW，Gao SM，et al. Streaming Real Time Collision Detection Using Programmable Graphics Hardware [J]. Journal of Software，2004，15（10）：1505-1514.

作者簡(jiǎn)介：馬永斌（1982.10-），男，漢族，河南商丘人，講師，本科，研究方向：計(jì)算機(jī)應(yīng)用及物聯(lián)網(wǎng)技術(shù);詹華蕊（1986. 03-），女，漢族，河南商丘人，講師，研究生，研究方向：計(jì)算機(jī)應(yīng)用及網(wǎng)絡(luò)技術(shù)。