基于關鍵點存取的虛擬植物碰撞檢測方法的研究

鄭 萍，趙春江，2*，張繼成

（1.東北農業大學工程學院，哈爾濱 150030；2.國家農業信息化工程技術研究中心，北京 100097）

碰撞檢測是虛擬植物模擬中的一個重要問題。虛擬植物生長環境需要處理若干個靜止對象和活動對象，而且每個虛擬對象的模型都是由數以萬計的基本幾何元素組成的，這使得碰撞檢測處理的算法復雜度大大提高。虛擬植物需要準確地判斷兩個物體是否發生碰撞，并且要求具有很高的實時性。精確的碰撞檢測對于提高虛擬植物生長系統的擬真度、增強虛擬環境的沉浸感有著至關重要的作用。而且考慮到植物作為一個有機體，在虛擬植物生長過程中，具有碰撞規避機理，所以精確的進行碰撞檢測對增加生長系統模擬的真實性也具有重要意義。

1 碰撞檢測研究方法

現有的碰撞檢測算法大致可劃分為兩大類：空間分解法和層次包容盒法。這兩種方法的目的都是為了盡可能地減少需要相交測試的對象數目。

1.1 空間分解法

它是將整個虛擬空間劃分成相等體積的小單元格，只對占據同一單元格或相鄰單元格的幾何對象進行相交測試，該方法適用于稀疏環境中分布比較均勻的幾何對象間地碰撞檢測。比較典型的方法有八叉樹、BSP樹、均勻網格等。但是空間分解法隨著分化單元格的體積越小，數據處理量越大，影響了檢測速度和模擬系統的連續性，該方法以犧牲時間提高精度。

1.2 層次包容盒方法

層次包容體法的核心思想是利用體積略大而幾何特性簡單的包容體將復雜幾何對象包裹起來，在進行碰撞檢測時，首先進行包容體之間相交測試，只有包容體相交時，才對其所包裹的對象做進一步的相交計算。比較典型的包容體類型有軸對齊包容盒（AABB）、包容球、有向包容盒（OBB）、DOPs和凸包等。在構造碰撞體的包容體時，若引入樹狀層次結構，可快速剔除不發生碰撞的元素，減少大量不必要的相交測試，從而提高碰撞檢測效率。

它的關鍵在于包容盒類型的選擇，對用于碰撞檢測的包容盒有以下兩方面的約束：①簡單性：包容盒應該是簡單的幾何體，至少應該比被包容的幾何對象簡單。簡單性不僅表現為幾何形狀簡單易于計算，而且包括相交測試算法的快速簡單。②緊密性：包容盒應該盡可能地貼近被包容的幾何對象。緊密性直接關系到需要進行相交測試的包容盒的數目。該方法與空間分解法比較，縮短了檢測時間，提高了顯示速度。但是該方法屬于粗獷型碰撞檢測，對于不規則的物體（如植物等），缺失很多形態信息，導致很多互補形態結構被誤認為是碰撞，使模擬的效果降低。

在虛擬植物過程中，植株不斷生長，形態結構不斷變化，植株間的距離也會隨之改變。根據虛擬植物的這一特點，如果采用傳統的檢測方式，首先使用軸對齊包容盒（AABB）檢測遠距離植株之間的碰撞，并把八叉樹結構應用到碰撞檢測中，通過八叉樹空間剖分技術來縮短碰撞檢測的時間；在近植株的碰撞檢測中，則采用路徑跟蹤算法，經典算法有LC算法和GJK算法。

①軸對齊包容盒（AABB），雖然AABB存在著冗余量大等缺點，但當被包容的對象發生變形時，它能夠很方便地從子結點的包容盒合成父結點的包容盒，這一屬性正適合不斷變化的虛擬植物，而包容球和方向包容盒（OBB）則需要花費大量的時間重新計算。

一個給定對象的AABB被定義為包含該對象且各邊平行于坐標軸地最小地六面體。圖1給出了虛擬植物過程中一個簡化了的二維平面中的例子。給定對象的AABB的計算十分簡單，我們只需分別計算組成對象的基本幾何元素集合中各個元素的頂點坐標最大值和最小值即可。AABB間的相交測試也比較簡單，我們采用SAT（Separting-axes test）法，只需比較兩個AABB包容盒分別在三個坐標軸上投影的區間的重疊情況。定義AABB的六個最大最小值分別確定了它在三個坐標軸上的投影區間，因此AABB間的相交測試最多只需要六次比較運算。

圖1 軸對齊包容盒（AABB）Fig.1 Axis alignment bounding box

②空間八叉樹剖分技術是一個空間非均勻網格剖分技術，該技術是將含有整個對象的空間立方體按三個方向中剖面分割成八個子立方體網格，組織成一棵八叉樹。若某一子立方體網格中所含對象面片數大于給定閾值，則為該子立方體做進一步的剖分。上述剖分過程直至八叉樹的每個葉子結點所含面片數均小于給定的閾值為止。這個技術也是利用了空間連貫性。

構造八叉樹包容盒：首先，為植株建立包容盒，輸入葉片（以三角形頂點的形式）的數據，遍歷所有三角形的每個頂點，找出葉片中沿三個坐標軸的最大、最小值，按照最大、最小值分別對植株對象建立各條邊分別平行于坐標軸方向的AABB包容盒；接著，以植株對象的AABB包容盒為例，采用自頂向下的方法構造，①確定分裂軸，分裂點：通常選擇三個坐標軸分裂平面的法向軸，分裂點取AABB包容盒各條棱的中點，這樣經過一次分割就可以把AABB包容盒以分八。②包容盒中元素（三角形）分屬確定：一個基本的幾何元素（三角形）或屬于八個子包容盒的某個，或與子包容盒的某些相交。若相交，則計算該三角形的重心，通過判斷重心位置屬于哪個子包容盒來確定此三角形屬于哪部分，若重心也恰在分裂面上，則把它分配給元素較少的那一部分，若幾部分所包含的三角形一樣多，則指定此三角形屬于任一子包容盒。③遞歸構造包容盒八叉樹及終止條件：分別對對于每個子包容盒中三角形運用步驟①建立AABB包容盒，并遞歸調用步驟②直至每個包容盒中只含有一個三角形（葉片）為止。

2 關鍵點存儲技術

傳統的碰撞檢測方法具有各自的優點和適用范圍，對檢測結果分析具有重要意義。但在虛擬植物生長模擬過程中，應該更多的結合植物的生長發育規律進行碰撞檢測，針對植物生長發育特點提高檢測速度和精度，特別是對細小的植物分枝，往往忽略不計，造成了檢測速度的下降。根據上述問題，利用關鍵點存儲方法進行細小分枝的碰撞檢測，是對新的檢測方法的一種探索。

首先對植物生長特點進行分析，形態復雜的植株或多植株相鄰生長在一起，會有大量的細小枝葉穿插生長，此時如用空間分解法就需要對空間劃分非常小的格子，否則還沒有進行檢測兩個格子就已經相互碰撞了，但是隨著格子體積的減小，計算量也同樣增加了，影響檢測速度，如用包容盒法將植物包裹起來，就違反了植物生長特點，影響模擬效果。兩種檢測方法在植物碰撞檢測中都具有缺點，所以有必要提出針對植物生長系統的碰撞檢測方法。

在基于生物量進行植物形態模型建立之后，對于給定時刻植物模型將獲得一個靜態的植株。這樣問題就得以簡化，對于要進行碰撞檢測的植株，只要對處于同一水平面上的生物點（關鍵點）進行比較分析，即可判斷是否碰撞。下面針對碰撞檢測的這一方法進行介紹。

2.1 關鍵點選取

將植物植株的高度設為H，在垂直方向上以步長為L對植株進行區域劃分，進行橫向切割，該植株將被分割成H/L+1個水平切面，對于植物就會在每個切面上形成植株的生物點，而這些生物點拼接起來就可以重現植株。在進行碰撞檢測時，將同水平切面上的生物點進行對比分析，即可判斷是否碰撞。這里碰撞檢測的精度取決于步長L的設定，但是對于給定時刻的生長模型，各生物點的數據相當于靜態的離散點，與傳統檢測方法比較精度和速度都有很大的提高。在本節中，把植物生物點成為檢測的關鍵點。

2.2 關鍵點存儲

對于已經經過水平分割處理的植株，僅需比較同層關鍵點是否重疊即可，使植物碰撞的三維檢測降低為二維檢測。將每層的關鍵點按照一定規律掃描存儲在計算機中進行管理，本節采用鄰接表的形式對關鍵點進行存儲，為了便于分析，現將其數據結構定義見圖2。

圖2 植株在計算機內的存儲結構Fig.2 Storage structure of plant simulation in computer

該存儲結構算法：

其中，點(x，z)表示生長最低點，(xn，zn)表示生長最高點，步長為L，i表示第i個水平切面，n表示同一切面上的第n個關鍵點。

3 方法檢驗

將植株的關鍵點以這種鄰接表的形式進行存儲，然后采用深度優先遍歷法進行查找，即在同一水平面上的生物點進行比較查找，即具有相同y軸坐標的關鍵點進行比較查找，這樣將降低檢測數量。然后將對x軸坐標進行比較，如果具有相同的x坐標值，將進一步比較，否則放棄。

通過這種方式比較將急劇減少關鍵點的比較數量，提高了碰撞檢測速度。具體的檢測算法如下：

該方法中設植物高度為H，垂直方向分割步長為L，則植物分層從0至H/L層。則碰撞檢測需檢測H/L+1各平面，即H/L+1次。對于每一個平面內關鍵點數假設為vetexCount。根據上述算法需要進行碰撞檢測次數為：（H/L+1）*vetexCount。當L取值接近1/N時，vetexCount取值接近N時，該算法擁有的最壞時間復雜度為O（N2）；當L與vetexCount取值都接近常數時，該算法的最好時間復雜度為O（1）；其余取值時間復雜度為O（N）。

目前的碰撞檢測方法中，多為虛擬現實中場景的檢測，很少有特為植物碰撞檢測進行的算法設計。本節在虛擬植物模型建立的基礎上，提出了關鍵點存取思想進行檢測，在一般的碰撞檢測要求下，其算法優勢明顯。

根據上述方法，可以快速有效地進行碰撞檢測，在此之后，碰撞處理按照后生成器官讓位于先生成器官的原則，即某器官在生成過程中，經過檢測發現與已生成的器官有坐標重疊現象，則對該器官進行適當的位置修改，再進行檢測，直到沒有發生碰撞現象為止，才進行該器官顯示（見圖3）。

圖3 模擬效果Fig.3 Simulation effect

4 結論

本文利用了關鍵點存取思想的檢測方法是在給定生長模型基礎上，針對植株生長提出的。將植株進行切片分層，碰撞檢測簡化成各離散關鍵點的檢測，然后分別對坐標分量進行比較分析，進行碰撞監測，能夠降低檢測方法的復雜度并提高檢測精度。

[1] 蘇中濱,戰守義,鄭萍,等.作物高光效株型數字化設計方法研究[J].農業工程學報,2008,24(1)：203-207.

[2] 蘇中濱，鄭萍,孫紅敏,等.大豆形態生長系統的組件化設計方法[J].微型電腦應用,2008,24(2)：53-55.

[3] 蘇中濱,張繼成,鄭萍.作物高光效株型數字化設計的方法研究[J].計算機科學與應用,2008,25(5)：269-270.

[4] 章德賓,胡斌,張金隆.多線程技術與分布式并發離散事件仿真[J].計算機仿真,2007(1):97-100.

[5] 熊邦毛,熊葉明,張再萍.用多線程技術解決單線程沖突問題[J].計算機與數字工程,2007(1):115-119.

[6] 張樂平,孔玉,雷長海,等.基于多線程技術的實時檢測[J].醫療衛生裝備,2005(6):1-2.

[7] 翟巍,遲忠先,方芳.大規模三維場景可視化的數據組織方法研究[J].計算機工程,2003,29(20):26-27.

[8] 唐珉,胡占義.參數空間分解法[J].計算機學報,2001,9(22):911-917.

[9] 黃娟,顧寄南.裝配仿真中碰撞干涉檢查研究的綜述[J].科學通報,2002,2(23):17-21.

[10] 陳尚飛.基于分離軸理論的有向包圍盒重疊測試算法 [J].廣西科學院學報,2005,3(21):196-198.

[11] 牛立新,劉旭敏,王功明.基于空間八叉剖分的面聚類網格簡化算法[J].計算機工程，2007,20(33):228-238.

[12] 周之平,張少博,吳介一,等.基于非線性規劃理論的凸多面體最小平移距離算法[J].中國圖象圖形學報,2006,10(11):1487-1492.

[13] 孫紅敏,鄭萍,張繼成.大豆葉片生長特征的動態模擬研究[J].東北農業大學學報,2007,38(4):446-448.

[14] 李曉明,趙春江,鄭萍.基于Agent的植物生長系統結構[J].東北農業大學學報,2010,41(8)：127-130.

[15] 孫紅敏,李曉明.大豆葉片形態模擬模型建立方法的研究[J].農機化研究,2007(11)：48-50.