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

（1.東北農(nóng)業(yè)大學(xué)工程學(xué)院，哈爾濱 150030；2.國(guó)家農(nóng)業(yè)信息化工程技術(shù)研究中心，北京 100097）

碰撞檢測(cè)是虛擬植物模擬中的一個(gè)重要問(wèn)題。虛擬植物生長(zhǎng)環(huán)境需要處理若干個(gè)靜止對(duì)象和活動(dòng)對(duì)象，而且每個(gè)虛擬對(duì)象的模型都是由數(shù)以萬(wàn)計(jì)的基本幾何元素組成的，這使得碰撞檢測(cè)處理的算法復(fù)雜度大大提高。虛擬植物需要準(zhǔn)確地判斷兩個(gè)物體是否發(fā)生碰撞，并且要求具有很高的實(shí)時(shí)性。精確的碰撞檢測(cè)對(duì)于提高虛擬植物生長(zhǎng)系統(tǒng)的擬真度、增強(qiáng)虛擬環(huán)境的沉浸感有著至關(guān)重要的作用。而且考慮到植物作為一個(gè)有機(jī)體，在虛擬植物生長(zhǎng)過(guò)程中，具有碰撞規(guī)避機(jī)理，所以精確的進(jìn)行碰撞檢測(cè)對(duì)增加生長(zhǎng)系統(tǒng)模擬的真實(shí)性也具有重要意義。

1 碰撞檢測(cè)研究方法

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

1.1 空間分解法

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

1.2 層次包容盒方法

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

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

在虛擬植物過(guò)程中，植株不斷生長(zhǎng)，形態(tài)結(jié)構(gòu)不斷變化，植株間的距離也會(huì)隨之改變。根據(jù)虛擬植物的這一特點(diǎn)，如果采用傳統(tǒng)的檢測(cè)方式，首先使用軸對(duì)齊包容盒（AABB）檢測(cè)遠(yuǎn)距離植株之間的碰撞，并把八叉樹結(jié)構(gòu)應(yīng)用到碰撞檢測(cè)中，通過(guò)八叉樹空間剖分技術(shù)來(lái)縮短碰撞檢測(cè)的時(shí)間；在近植株的碰撞檢測(cè)中，則采用路徑跟蹤算法，經(jīng)典算法有LC算法和GJK算法。

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

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

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

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

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

2 關(guān)鍵點(diǎn)存儲(chǔ)技術(shù)

傳統(tǒng)的碰撞檢測(cè)方法具有各自的優(yōu)點(diǎn)和適用范圍，對(duì)檢測(cè)結(jié)果分析具有重要意義。但在虛擬植物生長(zhǎng)模擬過(guò)程中，應(yīng)該更多的結(jié)合植物的生長(zhǎng)發(fā)育規(guī)律進(jìn)行碰撞檢測(cè)，針對(duì)植物生長(zhǎng)發(fā)育特點(diǎn)提高檢測(cè)速度和精度，特別是對(duì)細(xì)小的植物分枝，往往忽略不計(jì)，造成了檢測(cè)速度的下降。根據(jù)上述問(wèn)題，利用關(guān)鍵點(diǎn)存儲(chǔ)方法進(jìn)行細(xì)小分枝的碰撞檢測(cè)，是對(duì)新的檢測(cè)方法的一種探索。

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

在基于生物量進(jìn)行植物形態(tài)模型建立之后，對(duì)于給定時(shí)刻植物模型將獲得一個(gè)靜態(tài)的植株。這樣問(wèn)題就得以簡(jiǎn)化，對(duì)于要進(jìn)行碰撞檢測(cè)的植株，只要對(duì)處于同一水平面上的生物點(diǎn)（關(guān)鍵點(diǎn)）進(jìn)行比較分析，即可判斷是否碰撞。下面針對(duì)碰撞檢測(cè)的這一方法進(jìn)行介紹。

2.1 關(guān)鍵點(diǎn)選取

將植物植株的高度設(shè)為H，在垂直方向上以步長(zhǎng)為L(zhǎng)對(duì)植株進(jìn)行區(qū)域劃分，進(jìn)行橫向切割，該植株將被分割成H/L+1個(gè)水平切面，對(duì)于植物就會(huì)在每個(gè)切面上形成植株的生物點(diǎn)，而這些生物點(diǎn)拼接起來(lái)就可以重現(xiàn)植株。在進(jìn)行碰撞檢測(cè)時(shí)，將同水平切面上的生物點(diǎn)進(jìn)行對(duì)比分析，即可判斷是否碰撞。這里碰撞檢測(cè)的精度取決于步長(zhǎng)L的設(shè)定，但是對(duì)于給定時(shí)刻的生長(zhǎng)模型，各生物點(diǎn)的數(shù)據(jù)相當(dāng)于靜態(tài)的離散點(diǎn)，與傳統(tǒng)檢測(cè)方法比較精度和速度都有很大的提高。在本節(jié)中，把植物生物點(diǎn)成為檢測(cè)的關(guān)鍵點(diǎn)。

2.2 關(guān)鍵點(diǎn)存儲(chǔ)

對(duì)于已經(jīng)經(jīng)過(guò)水平分割處理的植株，僅需比較同層關(guān)鍵點(diǎn)是否重疊即可，使植物碰撞的三維檢測(cè)降低為二維檢測(cè)。將每層的關(guān)鍵點(diǎn)按照一定規(guī)律掃描存儲(chǔ)在計(jì)算機(jī)中進(jìn)行管理，本節(jié)采用鄰接表的形式對(duì)關(guān)鍵點(diǎn)進(jìn)行存儲(chǔ)，為了便于分析，現(xiàn)將其數(shù)據(jù)結(jié)構(gòu)定義見(jiàn)圖2。

圖2 植株在計(jì)算機(jī)內(nèi)的存儲(chǔ)結(jié)構(gòu)Fig.2 Storage structure of plant simulation in computer

該存儲(chǔ)結(jié)構(gòu)算法：

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

3 方法檢驗(yàn)

將植株的關(guān)鍵點(diǎn)以這種鄰接表的形式進(jìn)行存儲(chǔ)，然后采用深度優(yōu)先遍歷法進(jìn)行查找，即在同一水平面上的生物點(diǎn)進(jìn)行比較查找，即具有相同y軸坐標(biāo)的關(guān)鍵點(diǎn)進(jìn)行比較查找，這樣將降低檢測(cè)數(shù)量。然后將對(duì)x軸坐標(biāo)進(jìn)行比較，如果具有相同的x坐標(biāo)值，將進(jìn)一步比較，否則放棄。

通過(guò)這種方式比較將急劇減少關(guān)鍵點(diǎn)的比較數(shù)量，提高了碰撞檢測(cè)速度。具體的檢測(cè)算法如下：

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

目前的碰撞檢測(cè)方法中，多為虛擬現(xiàn)實(shí)中場(chǎng)景的檢測(cè)，很少有特為植物碰撞檢測(cè)進(jìn)行的算法設(shè)計(jì)。本節(jié)在虛擬植物模型建立的基礎(chǔ)上，提出了關(guān)鍵點(diǎn)存取思想進(jìn)行檢測(cè)，在一般的碰撞檢測(cè)要求下，其算法優(yōu)勢(shì)明顯。

根據(jù)上述方法，可以快速有效地進(jìn)行碰撞檢測(cè)，在此之后，碰撞處理按照后生成器官讓位于先生成器官的原則，即某器官在生成過(guò)程中，經(jīng)過(guò)檢測(cè)發(fā)現(xiàn)與已生成的器官有坐標(biāo)重疊現(xiàn)象，則對(duì)該器官進(jìn)行適當(dāng)?shù)奈恢眯薷?，再進(jìn)行檢測(cè)，直到?jīng)]有發(fā)生碰撞現(xiàn)象為止，才進(jìn)行該器官顯示（見(jiàn)圖3）。

圖3 模擬效果Fig.3 Simulation effect

4 結(jié)論

本文利用了關(guān)鍵點(diǎn)存取思想的檢測(cè)方法是在給定生長(zhǎng)模型基礎(chǔ)上，針對(duì)植株生長(zhǎng)提出的。將植株進(jìn)行切片分層，碰撞檢測(cè)簡(jiǎn)化成各離散關(guān)鍵點(diǎn)的檢測(cè)，然后分別對(duì)坐標(biāo)分量進(jìn)行比較分析，進(jìn)行碰撞監(jiān)測(cè)，能夠降低檢測(cè)方法的復(fù)雜度并提高檢測(cè)精度。

[1] 蘇中濱,戰(zhàn)守義,鄭萍,等.作物高光效株型數(shù)字化設(shè)計(jì)方法研究[J].農(nóng)業(yè)工程學(xué)報(bào),2008,24(1)：203-207.

[2] 蘇中濱，鄭萍,孫紅敏,等.大豆形態(tài)生長(zhǎng)系統(tǒng)的組件化設(shè)計(jì)方法[J].微型電腦應(yīng)用,2008,24(2)：53-55.

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

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

[5] 熊邦毛,熊葉明,張?jiān)倨?用多線程技術(shù)解決單線程沖突問(wèn)題[J].計(jì)算機(jī)與數(shù)字工程,2007(1):115-119.

[6] 張樂(lè)平,孔玉,雷長(zhǎng)海,等.基于多線程技術(shù)的實(shí)時(shí)檢測(cè)[J].醫(yī)療衛(wèi)生裝備,2005(6):1-2.

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

[8] 唐珉,胡占義.參數(shù)空間分解法[J].計(jì)算機(jī)學(xué)報(bào),2001,9(22):911-917.

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

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

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

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

[13] 孫紅敏,鄭萍,張繼成.大豆葉片生長(zhǎng)特征的動(dòng)態(tài)模擬研究[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),2007,38(4):446-448.

[14] 李曉明,趙春江,鄭萍.基于Agent的植物生長(zhǎng)系統(tǒng)結(jié)構(gòu)[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),2010,41(8)：127-130.

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