基于改進(jìn)包圍盒樹和GPU的水稻群體葉片間快速碰撞檢測

張興邦，胡 濱，湯 亮，伍艷蓮,，姜海燕※,

（1. 南京農(nóng)業(yè)大學(xué)信息科技學(xué)院，南京 210095；2. 南京農(nóng)業(yè)大學(xué)/國家信息農(nóng)業(yè)工程技術(shù)中心，南京 210095）

0 引 言

虛擬植物技術(shù)已經(jīng)在現(xiàn)代農(nóng)業(yè)生產(chǎn)決策、產(chǎn)量預(yù)測、作物育種、生長條件優(yōu)化等方面發(fā)揮著重要作用[1]。在虛擬植物群體的可視化繪制中，葉片之間經(jīng)常發(fā)生穿插生長的現(xiàn)象，降低了植物模擬的真實(shí)感，加之群體規(guī)模的增大，也出現(xiàn)了檢測效率較低的問題，因此及時快速檢測出群體葉片之間的碰撞行為，是進(jìn)一步模擬響應(yīng)行為的基礎(chǔ)。

國內(nèi)外學(xué)者對如何提高虛擬植物葉片間的碰撞檢測效率進(jìn)行了研究，主要集中在簡化碰撞檢測中檢測對象的數(shù)量或者計算量上，常采用的方法是空間分解法或?qū)哟伟鼑袠浞āＴ诳臻g分解法研究方面，鄭萍等皆通過將植物器官空間進(jìn)行分層再碰撞的方法[2-4]減少了碰撞檢測的計算量，提升了碰撞檢測的效率。雖然空間分解法可以簡化碰撞檢測的計算，但虛擬水稻群體葉片密集，找尋合適的分解規(guī)則比較困難，而層次包圍盒樹法正好適應(yīng)這種情況。秦栓等[5]針對玉米葉片的形態(tài)提出了一種基于AABB[6]-OBB[7-9]混合包圍盒的碰撞檢測方法，改進(jìn)了分離軸測試順序，加快了碰撞檢測速度。伍艷蓮等[10]提出了一種基于AABB-FDH[11]包圍盒的碰撞檢測方法，該方法結(jié)合了AABB包圍盒簡單、FDH包圍盒構(gòu)造緊密性較好的優(yōu)點(diǎn)，可快速排除 2張葉片相距較遠(yuǎn)而基本上不可能發(fā)生碰撞的場景。雖然已有研究都在不同場景下，通過簡化碰撞檢測的某一個過程提升了植物器官間的碰撞檢測效率，但仍然存在以下2方面的問題：1）現(xiàn)有研究多是通過包圍盒的組合來優(yōu)化相交檢測過程，對利用植株特定的形態(tài)特點(diǎn)簡化包圍盒的構(gòu)造過程研究有限；2）在大規(guī)模水稻群體的碰撞檢測處理中，僅對碰撞檢測算法本身進(jìn)行改進(jìn)已經(jīng)無法滿足大規(guī)模群體繪制實(shí)時性的要求。事實(shí)上在其他領(lǐng)域的復(fù)雜場景虛擬中，已有研究者使用多核 CPU技術(shù)[12]、CPU/GPU技術(shù)[13-16]等硬件加速手段提升碰撞檢測效率，如Tang等[17]針對可變形模型之間的碰撞設(shè)計了基于GPU的快速檢測方法，黃偉益[18]為了滿足虛擬手術(shù)實(shí)時性的要求，采用CUDA平臺設(shè)計了基于CPU和GPU協(xié)同處理的快速碰撞檢測算法。

本文以水稻葉片形態(tài)結(jié)構(gòu)模型為輸入，利用水稻葉片類拋物線的形態(tài)結(jié)構(gòu)特點(diǎn)，提出了新的OBB包圍盒方向軸的計算方式，降低了OBB包圍盒的構(gòu)建復(fù)雜度；設(shè)計了基于LCD[19]-OBB的混合層次包圍盒樹（mixed level tree, MLT）的水稻葉片碰撞檢測算法，采用隨機(jī)旋轉(zhuǎn)和縮放水稻單株的方法構(gòu)造了水稻群體模型，在此基礎(chǔ)上分析了大規(guī)模水稻群體葉片間碰撞檢測時的計算關(guān)系，利用CPU/GPU硬件加速技術(shù)，設(shè)計了大規(guī)模水稻群體葉片碰撞檢測并行化方案，利用CUDA編程實(shí)現(xiàn)并行加速。

1 水稻群體葉片間碰撞檢測算法

圖 1為本文研究流程，首先根據(jù)水稻葉片拋物線的形態(tài)特點(diǎn)，結(jié)合水稻形態(tài)結(jié)構(gòu)模型為水稻單株葉片構(gòu)建改進(jìn)后的 MLT，在此基礎(chǔ)上，通過更新操作分別構(gòu)建水稻不同葉位、單株、群體葉片的 MLT，然后在對水稻兩株不同葉位葉片對進(jìn)行碰撞檢測的基礎(chǔ)上，按照一定的碰撞檢測規(guī)則，完成水稻群體葉片間的碰撞檢測。

1.1 水稻群體繪制

水稻群體是多植株的集合，但不是簡單的水稻個體的復(fù)制，具體體現(xiàn)在不同的水稻個體，其葉片的長度、寬度不同，莖鞘夾角不同，分蘗數(shù)量不同，植株大小不同等。本研究在進(jìn)行水稻群體的繪制時通過加入差異化因子，隨機(jī)縮放旋轉(zhuǎn)水稻單株等操作實(shí)現(xiàn)水稻之間的差異性。

圖1 基于MLT碰撞檢測算法的水稻群體葉片間碰撞檢測流程Fig.1 Detection process of inter-blade collision of rice population based on MLT(mixed level tree)collision detection algorithm

水稻群體在繪制時，需要確定每一株的坐標(biāo)位置，設(shè)水稻群體行數(shù)為 RNum，列數(shù)為 CNum，行間距為RowDis，列間距為 ColumnDis，則第 i行 j列水稻的坐標(biāo)為

在對水稻葉片進(jìn)行繪制時，加入差異化因子θ，對水稻葉片的莖鞘夾角和方位角進(jìn)行差異化處理，設(shè)水稻葉片的原莖鞘夾角為α，方位角為β，處理后分別為γ和δ

對水稻單株整體進(jìn)行隨機(jī)旋轉(zhuǎn)和縮放操作，進(jìn)一步增加水稻群體之間的差異性。

1.2 水稻群體葉片的MLT構(gòu)建

水稻葉片間碰撞檢測的基礎(chǔ)是構(gòu)造MLT，本文MLT構(gòu)建主要包括兩部分：LCD包圍盒[15]的構(gòu)造和OBB包圍盒的構(gòu)造。由1.1水稻群體差異性的生成規(guī)則可知，水稻群體葉片MLT可在單株葉片MLT的基礎(chǔ)上通過旋轉(zhuǎn)和縮放得到，因此，其構(gòu)建的關(guān)鍵在于單葉片MLT的構(gòu)建。

1.2.1 LCD包圍盒構(gòu)造

LCD包圍盒，是一個包含幾何對象且垂直方向平行于坐標(biāo)軸的最小六面體，LCD包圍盒用3個值來表示：葉片的控制點(diǎn)集合元素在初始構(gòu)造時在 3個坐標(biāo)軸上投影的最大值（Max）和最小值（Min），以及葉片組裝到水稻單株上時所使用的矩陣（Matrix）。Matrix用于在器官組裝成水稻個體后使用分離軸理論（separation axis theory，SAT）進(jìn)行包圍盒的相交檢測。因此本文使用的LCD包圍盒相較于傳統(tǒng)AABB包圍盒提升了其自身的緊密性，減少了旋轉(zhuǎn)更新的代價。

1.2.2 OBB包圍盒方向軸確定

OBB包圍盒定義為包含幾何對象且相對于坐標(biāo)軸任意方向的最小長方體[6]。OBB包圍盒構(gòu)建的關(guān)鍵在于方向軸的確定，傳統(tǒng)的OBB包圍盒構(gòu)造時通過計算對象數(shù)據(jù)的均值和協(xié)方差矩陣方式來確定OBB包圍盒的方向軸[6]。

采用協(xié)方差矩陣確定 OBB包圍盒方向軸的計算量大、耗時較多[4]。本文利用水稻葉片曲線類拋物線的形態(tài)特點(diǎn)，提出了新的OBB包圍盒方向軸的計算方法。水稻葉片在坐標(biāo)軸原點(diǎn)進(jìn)行構(gòu)建，然后通過旋轉(zhuǎn)平移等操作組裝到水稻植株上，水稻葉片的中脈曲線是空間中一條近似光滑的曲線（圖 2），構(gòu)建時葉片的主脈曲線在 xoy平面內(nèi)，在葉片不發(fā)生折斷的情況下，可認(rèn)為葉片中脈曲線一階可導(dǎo)、二階連續(xù)[20-21]。設(shè) a為葉片中脈曲線的起點(diǎn)，b為葉片中脈曲線的終點(diǎn)，由于葉片中脈曲線連續(xù)且凸，所以葉片中脈曲線上的所有點(diǎn)都在a與b的連線的一側(cè)，因此a與b連線所在的方向?yàn)榘鼑撊~片的有向包圍盒的一個方向軸，若(xa, ya, za)為a點(diǎn)坐標(biāo)，(zb)為b點(diǎn)坐標(biāo)，則該方向軸由式（3）計算得到，式中為ab連線所在的方向向量。在葉片不發(fā)生卷曲、扭曲等形變時，葉片邊緣控制點(diǎn)的x、y坐標(biāo)與同一排主脈控制點(diǎn)的x、y坐標(biāo)相同，z坐標(biāo)不同，因此z軸為包圍該葉片的有向包圍盒的其中一條方向軸。至此，有向包圍盒的兩條方向軸已經(jīng)確定，第三條方向軸可以根據(jù)這兩條方向軸來進(jìn)行確定。

計算出OBB包圍盒的方向軸之后，利用葉片控制點(diǎn)數(shù)據(jù)在3個方向軸上投影的最大最小值，即可構(gòu)造OBB包圍盒。

圖2 水稻葉片OBB包圍盒方向軸確定示意圖Fig.2 Schematic diagram of OBB bounding box for rice leaves to determine the direction of the axis

1.2.3 單葉片MLT的構(gòu)造

本文MLT在樹的葉子節(jié)點(diǎn)構(gòu)造OBB包圍盒，其余節(jié)點(diǎn)構(gòu)造LCD包圍盒并采用自頂向下的方法遞歸建立層次包圍盒樹。首先根據(jù)葉片的控制頂點(diǎn)對整張葉片構(gòu)建LCD包圍盒，并將其作為MLT的根節(jié)點(diǎn)，以盡快排除不相交的情況；然后用曲面分割算法將葉片從中間一分為二，對分割后的2部分葉片繼續(xù)構(gòu)造LCD包圍盒和相應(yīng)的節(jié)點(diǎn)，將這些新節(jié)點(diǎn)作為根節(jié)點(diǎn)的左、右子節(jié)點(diǎn)；依次按照第二步方法分割每個子節(jié)點(diǎn)對應(yīng)的葉片曲面，遞歸地建立MLT，遞歸次數(shù)自定義。

1.3 水稻群體葉片間碰撞檢測

1.3.1 碰撞檢測規(guī)則

水稻群體生長過程的可視化模擬中，雖然水稻植株形態(tài)會發(fā)生變化，但是植株所在空間坐標(biāo)位置不變，結(jié)合現(xiàn)實(shí)世界中的稻田中水稻的種植規(guī)律，本文采用如下碰撞檢測規(guī)則。

水稻群體植株按照行列種植，行相鄰或者列相鄰的植株之間有可能發(fā)生葉片間的碰撞，而不相鄰的植株之間發(fā)生碰撞的概率較低。由此本文采用每株水稻的葉片與周圍鄰近水稻的所有葉片進(jìn)行碰撞檢測, 當(dāng)檢測到最多與周圍 8株植株上的所有葉片都沒有發(fā)生碰撞時才判定該葉片沒有發(fā)生碰撞。兩株植株之間的碰撞檢測需先計算兩個植株上最長葉片在地面上的投影之和是否大于兩株之間的行距（或列距），若大于則進(jìn)行碰撞檢測，否則認(rèn)為不會發(fā)生碰撞。

1.3.2 基于MLT的群體葉片碰撞檢測

碰撞檢測的核心就是遍歷 2個待測對象的層次包圍盒樹[22]，本文采用同步下降的方式進(jìn)行檢測，對 2個葉片自身的包圍盒層次樹進(jìn)行遍歷，檢測同一層次的包圍盒是否發(fā)生碰撞，若某一層次的包圍盒之間都沒有發(fā)生碰撞，則判定這 2張葉片沒有發(fā)生碰撞，否則繼續(xù)檢測下一層，直到檢測到葉子節(jié)點(diǎn)。對于作物系統(tǒng)可視化仿真，一般只需近似模擬碰撞情況，并不要求碰撞檢測達(dá)到100%精確[9]，因此在樹的深度選擇適當(dāng)?shù)那闆r下，如果葉子節(jié)點(diǎn)的OBB包圍盒之間沒有發(fā)生碰撞就判定2張葉片之間沒有發(fā)生碰撞，否則判定為發(fā)生碰撞。

2 基于CPU/GPU的水稻群體葉片碰撞檢測并行化

2.1 并行程序設(shè)計

并行程序設(shè)計常采用PCAM方法，是并行任務(wù)劃分（Partitioning）、任務(wù)通信（Communication）、任務(wù)組合（Agglomeration）和處理器映射（Mapping）共4個階段的簡稱[23]。任務(wù)劃分將整個計算問題分解成一些小計算任務(wù)，目的是挖掘問題的可并行性。

2.2 水稻群體葉片碰撞檢測算法的計算特性分析

本文在對水稻葉片構(gòu)造MLT時，通過改變上層LCD包圍盒以及底層OBB包圍盒的旋轉(zhuǎn)角度和放縮比例達(dá)到更新目的，而在繪制水稻群體時通過旋轉(zhuǎn)和放縮來增加群體間的差異性，因此在對水稻群體葉片構(gòu)造MLT時只需要構(gòu)造一株植株上所有葉片的 MLT，其余植株可以在此基礎(chǔ)上改變其旋轉(zhuǎn)角度和放縮比例來實(shí)現(xiàn) MLT的構(gòu)造，因此水稻群體葉片構(gòu)造MLT的耗時與群體規(guī)模相關(guān)性不大。

水稻群體葉片間進(jìn)行碰撞檢測，CPU的串行程序如圖 3所示。其中①為群體植株之間的循環(huán)；②為單株葉片之間的循環(huán)，③為周圍植株葉片之間的循環(huán)；其中 h為當(dāng)前要檢測植株周圍的總?cè)~片數(shù)，計算方法為周圍植株數(shù)（最多 8株）與每株的分蘗數(shù)以及每個分蘗上的葉片總數(shù)的乘積，h隨著GDD（growth degree days）發(fā)生改變，④為當(dāng)前待檢測的葉片對的包圍盒樹層次之間的循環(huán)。葉片之間進(jìn)行碰撞檢測時輸入數(shù)據(jù)是葉片的包圍盒樹數(shù)據(jù)，不同葉片的包圍盒樹數(shù)據(jù)是不相關(guān)的，因此不同葉片之間進(jìn)行碰撞檢測操作獨(dú)立，滿足 Bernstein[24]條件，可以并行。

圖3 水稻群體葉片碰撞檢測算法偽代碼Fig.3 Pseudo code of leaf collision detection algorithm for rice population

2.3 基于CUDA的水稻群體葉片碰撞檢測算法實(shí)現(xiàn)

2.3.1 算法的并行方案設(shè)計

CUDA是由NVIDIA公司推出，將GPU作為并行數(shù)據(jù)計算設(shè)備的軟硬件體系架構(gòu)[25]。CUDA軟件體系將GPU的處理器陣列抽象為由線程（Thread）、線程塊（Block）和線程網(wǎng)格（Grid）組成的線程結(jié)構(gòu)。

根據(jù)2.2分析，結(jié)合CUDA程序設(shè)計原則，本文對水稻群體葉片相交檢測過程進(jìn)行并行設(shè)計。以一對葉片間的相交檢測計算過程為基礎(chǔ)單元，劃分水稻群體葉片間的碰撞檢測并行任務(wù),并分配到GPU設(shè)備端執(zhí)行。包圍盒樹構(gòu)造耗時較少且可并行性差,分配到CPU端執(zhí)行（如圖4）。CUDA的線程映射如下：

由于水稻群體中不同葉片間的相交檢測彼此獨(dú)立，因此將每張葉片的相交檢測過程映射到獨(dú)立的 Block中處理。Block中的線程負(fù)責(zé)處理該葉片與周圍植株葉片之間的相交檢測計算。在GPU顯存管理方面，由于水稻葉片包圍盒樹數(shù)據(jù)各個線程都要使用，所以將水稻群體葉片的包圍盒樹數(shù)據(jù)放在Global Memory中存儲；計算完成后各個Block中的計算結(jié)果要集中在一起作為最后的總的相交檢測結(jié)果，所以該部分放在Global Memory中存儲，而Block代表的葉片的包圍盒數(shù)據(jù)在該 Block中的所有線程都要使用，所以存儲在Shared Memory中存儲。

圖4 基于CUDA的水稻群體葉片間碰撞檢測算法映射方案示意圖Fig.4 Mapping schemes of inter - blade collision detection algorithm for rice population based on CUDA

2.3.2 基于MLT碰撞檢測算法的并行實(shí)現(xiàn)

水稻群體葉片MLT數(shù)據(jù)在CPU端計算得到，相交檢測計算任務(wù)與線程的映射關(guān)系如2.3.1所述，算法實(shí)現(xiàn)偽代碼如圖5所示。

1）CUDA內(nèi)核函數(shù)配置

在啟動Kernel函數(shù)之前需要對Grid和Block進(jìn)行配置，如圖4所示，本研究以Grid的x，y，z三個維度分別代表水稻的植株號、分蘗號以及葉位號。本研究中水稻分蘗最多7個，單蘗上同時存在的葉片不超過15片，因此配置Grid為dim3 numBlocks(N,8,16)，N的大小為不小于當(dāng)前水稻群體總植株數(shù)的2的最小倍數(shù)。

2）CUDA內(nèi)核函數(shù)數(shù)據(jù)共享

在核函數(shù)中獲取當(dāng)前線程所對應(yīng)的葉片MLT數(shù)據(jù)，并進(jìn)行相交檢測。獲取葉片MLT數(shù)據(jù)時需要先計算一維數(shù)組的索引值，當(dāng)前線程的 blockIdx.x代表植株號，blockIdx.y代表分蘗號，blockIdx.z代表葉位號，則索引值計算公式如下所示：

式中index為一維數(shù)組的索引號，T代表單株分蘗數(shù)，L代表單蘗葉片數(shù)，threadIdx.x、threadIdx.y、threadIdx.z分別代表與該葉片進(jìn)行碰撞檢測的植株、分蘗及葉位。

圖5 水稻群體葉片并行碰撞檢測算法偽代碼Fig.5 Pseudo code of leaf parallel collision detection algorithm for rice population

3 試驗(yàn)及結(jié)果分析

3.1 試驗(yàn)環(huán)境與輸入數(shù)據(jù)

試驗(yàn)在AMAX高性能計算機(jī)(512 G內(nèi)存以及Intel?Xeon?CPU E5-2670 v3 @ 2.30 GHz)平臺上進(jìn)行，該機(jī)配備1塊Tesla K40c卡[26]。

水稻群體生長可視化模型的輸入數(shù)據(jù)來自國家信息農(nóng)業(yè)工程技術(shù)中心的形態(tài)結(jié)構(gòu)模型[27-30]，本研究開發(fā)的虛擬仿真試驗(yàn)系統(tǒng)可以模擬秈稻和粳稻 2類水稻品種在高氮、中氮、低氮 3種氮素水平下逐日生長的形態(tài)結(jié)構(gòu)數(shù)據(jù)。該系統(tǒng)采用C#語言開發(fā)，并行計算部分采用CUDA C++語言實(shí)現(xiàn)。

本文試驗(yàn)使用秈稻YD6號水稻品種進(jìn)行試驗(yàn)，其規(guī)模與組成圖形的基本圖元的對應(yīng)關(guān)系如表 1所示，計算公式如下

式中BP為基本圖元數(shù)，G為群體規(guī)模大小，T為單株分蘗數(shù)，L為單蘗葉片數(shù)。

表1 水稻群體規(guī)模與三角面片基本圖元對應(yīng)關(guān)系Table 1 Correspondence between rice population size and triangular patches basic element

3.2 試驗(yàn)方法

為了比較本文提出的MLT方法與傳統(tǒng)的AABB方法和 OBB方法的優(yōu)劣，從單葉片和群體兩個層次設(shè)計了試驗(yàn)。

1）仿真生成具有19 744個三角面片的葉片模型R1，將葉片模型R1復(fù)制后向X軸方向平移，然后繞Y軸旋轉(zhuǎn)180°形成葉片模型R2，使此時的R1與R2相交，對這兩個模型之間進(jìn)行碰撞檢測，經(jīng)前期預(yù)實(shí)驗(yàn)MLT選擇深度為4，以驗(yàn)證比較單葉片模型發(fā)生碰撞時不同算法的檢測耗時。2）在秈稻YD6號水稻品種生長的苗期、分蘗期、拔節(jié)期、灌漿期以及成熟期對水稻單株葉片進(jìn)行包圍盒樹構(gòu)造，獲取包圍盒樹構(gòu)造耗時。3）在水稻生長的第130 d（每個分蘗上有 10片葉）對水稻群體葉片進(jìn)行相交檢測，獲取水稻群體在高氮（分蘗數(shù)為7）和正常氮素水平（分蘗數(shù)為 5）下葉片間的相交檢測耗時。4）分別獲取秈稻YD6號水稻品種生長到第130 d時使用CUDA加速和不使用CUDA加速的葉片間碰撞檢測耗時，來驗(yàn)證并行加速的有效性。

3.3 結(jié)果與分析

表 2顯示了不同碰撞檢測方法在單葉片碰撞檢測時各步驟的耗時，數(shù)據(jù)分析可知：1）在包圍盒樹構(gòu)造時本文方法耗時為5～8 ms，其余的方法皆在100 ms以上，本文方法節(jié)省了90%以上的時間；2）在相交檢測發(fā)生碰撞時，本文方法耗時為600～1 000μs，其余方法皆在2 300μs以上。

表2 不同包圍盒樹對單葉片構(gòu)造檢測的性能Table 2 Performance of different bounding box trees for single leaf structure detection

圖 6為水稻群體葉片包圍盒樹構(gòu)造耗時比較，各個時期OBB方法包圍盒樹構(gòu)造耗時均在40 ms以上，AABB方法和MLT方法耗時均在10 ms以下。

圖6 水稻單株全生育期包圍盒樹構(gòu)造耗時比較Fig.6 Time - consuming comparison of bounding box tree structure in rice whole plant growth period

圖 7為不同氮素水平下使用不同碰撞算法檢測水稻群體葉片相交耗時比較：在不同氮素水平下基于MLT的方法相交檢測耗時為 AABB方法耗時的 50%，為 OBB方法耗時的30%。

圖7 第130天不同碰撞檢測算法耗時比較Fig.7 Time-consuming comparison of collision detection algorithms in 130th days

圖8為基于CPU/GPU的碰撞檢測算法效率，程序在CPU上運(yùn)行時，相交檢測耗時隨著群體規(guī)模的增加而增長，當(dāng)水稻群體規(guī)模達(dá)到10 000株時，耗時超過40 s，在經(jīng)過GPU并行加速后，水稻群體葉片間的碰撞檢測耗時維持在 2 s以內(nèi)，相比在 CPU運(yùn)行耗時減少了 98%左右。

圖8 第130天基于CUDA的相交檢測算法測試結(jié)果Fig.8 Testing results of intersection detection algorithm based on CUDA in 130th days

3.4 分析與討論

由3.3的試驗(yàn)結(jié)果可知，本文方法在水稻群體葉片間碰撞檢測時表現(xiàn)比AABB方法和OBB方法要好，這是因?yàn)楸疚姆椒ㄉ蠈邮褂肔CD包圍盒快速排除不可能發(fā)生碰撞的葉片對，減少了計算量，且底層使用OBB包圍盒保證檢測精度，且采用新的方向軸計算方式降低了OBB包圍盒的構(gòu)建復(fù)雜度，減少了計算耗時。基于CPU/GPU的并行加速在水稻群體規(guī)模較大時能較好的提升碰撞檢測的效率，計算耗時不會隨著群體的規(guī)模的增加成倍數(shù)增長。

本文提出的新的OBB包圍盒方向軸的計算方式雖然降低了OBB包圍盒構(gòu)建的復(fù)雜度，但沒有考慮水稻葉片發(fā)生折斷、扭曲和卷曲等復(fù)雜場景。當(dāng)發(fā)生上述情況時，可以在現(xiàn)有計算框架下調(diào)整包圍盒構(gòu)建方式。

4 結(jié) 論

為了解決水稻群體模擬過程中葉片間碰撞檢測效率低的問題，本文從算法改進(jìn)和硬件加速兩方面進(jìn)行研究，并進(jìn)行了相關(guān)試驗(yàn)驗(yàn)證。

1）根據(jù)水稻葉片類拋物線的形態(tài)特點(diǎn)，提出了新的OBB包圍盒方向軸的計算方式，它可以代替?zhèn)鹘y(tǒng)的使用協(xié)方差矩陣和均值的計算方式，降低包圍盒構(gòu)建的復(fù)雜度，在此基礎(chǔ)上構(gòu)建MLT（mixed level tree）。試驗(yàn)結(jié)果表明，本文方法比傳統(tǒng)的AABB、OBB方法碰撞檢測耗時減少50%以上，提高了碰撞檢測的效率。

2）分析水稻群體葉片碰撞檢測計算關(guān)系的依賴性，設(shè)計了CPU/GPU加速方案，并在Tesla 40加速卡上開發(fā)實(shí)現(xiàn)，進(jìn)一步提升了水稻群體葉片碰撞檢測的效率。試驗(yàn)結(jié)果表明，利用CPU/GPU并行加速相較于在CPU上的運(yùn)行時間節(jié)省了98%。

[1] 唐衛(wèi)東，李金忠，劉昌鑫，等. 虛擬植物模型及其構(gòu)建方法研究綜述[J]. 計算機(jī)應(yīng)用研究，2012，29(9)：3206－3211.Tang Weidong, Li Jinzhong, Liu Changxin, et al. A survey of virtual plant model and its construction[J]. Computer Application Research, 2012, 29(9): 3206－3211. (in Chinese with English abstract)

[2] 鄭萍，趙春江，張繼成. 基于關(guān)鍵點(diǎn)存取的虛擬植物碰撞檢測方法的研究[J]. 東北農(nóng)業(yè)大學(xué)學(xué)報，2011，42(8)：78－82.Zheng Ping, Zhao Chunjiang, Zhang Jicheng. Research on virtual plant collision detection method based on key point access[J]. Journal of Northeast Agricultural University, 2011,42(8): 78－82. (in Chinese with English abstract)

[3] 李長鋒，郭新宇，趙春江，等. 基于空間散列法的虛擬植物碰撞檢測算法[J]. 計算機(jī)應(yīng)用與軟件，2009，26(4)：242－245.Li Changfeng, Guo Xinyu, Zhao Chunjiang, et al. Virtual collision detection algorithm based on spatial hashing[J].Computer Applications and Software, 2009, 26(4): 242－245.(in Chinese with English abstract)

[4] Xiao B, Guo X, Wang C, et al. Collision detection based on biomimetic pattern recognition for virtual plant[J]. Icic Express Letters, 2015, 9(5): 1413－1418.

[5] 秦銓，趙春江，肖伯祥，等. 基于 AABB-OBB盒的玉米葉片碰撞檢測[J]. 農(nóng)機(jī)化研究，2012，34(1)：177－180.Qin Quan, Zhao Chunjiang, Xiao Boxiang, et al. Maize blade collision detection based on AABB - OBB Box[J]. Research on Agricultural Mechanization, 2012, 34(1): 177－180. (in Chinese with English abstract)

[6] Van Den Bergen G. Efficient collision detection of complex deformable models using AABB trees[J]. Journal of Graphics Tools, 1998, 2(4): 1－13.

[7] Gottschalk S, Lin M C, Manocha D. OBBTree: A hierarchical structure for rapid interference detection[C]//Conference on Computer Graphics and Interactive Techniques. ACM, 1996: 171－180.

[8] Stüvel S A, Magnenat Thalmann N, Thalmann D, et al.Hierarchical structure for collision checking between virtual characters [J]. Computer Animation and Virtual Worlds,2014,25(25): 333－342.

[9] Lifang Bai, Chaowen Chang, Yutong Wang, et al. OBB Intersect Test Algorithm Based on Effective Constraint[M].Proceedings of Science, 18-19 December 2015. Guangzhou,China.

[10] 伍艷蓮，湯亮，曹衛(wèi)星，等. 作物可視化中的碰撞檢測及響應(yīng)研究[J]. 計算機(jī)科學(xué)，2011，38(10)：263－266.Wu Yanlian, Tang Liang, Cao Weixing, et al. Research on collision detection and response in crop visualization[J].Computer Science, 2011, 38(10): 263－266. (in Chinese with English abstract)

[11] Klosowski J T, Held M, Mitchell J S B, et al. Efficient collision detection using bounding volume hierarchies of k-DOPs[J]. IEEE Transactions on Visualization & Computer Graphics, 1998, 4(1): 21－36.

[12] Kim D, Heo J, Huh J, et al. Hybrid parallel continuous collision detection using CPUs and GPUs[J]. Computer Graphics Forum, 2009, 28(7): 1791－1800.

[13] Gre? A, Guthe M, Klein R. GPU-based collision detection for deformable parameterized surfaces[J]. Computer Graphics Forum, 2006, 25(3): 497－506.

[14] Du P, Liu E S, Suzumura T. Parallel continuous collision detection for high-performance GPU cluster[C]// ACM SIGGRAPH Symposium on Interactive 3d Graphics and Games. ACM, 2017: 4.

[15] Yong B, Shen J, Sun H, et al. Parallel GPU-based collision detection of irregular vessel wall for massive particles[J].Cluster Computing, 2017: 1－13.

[16] Rubio-Largo S M, Lind P G, Maza D, et al. Granular gas of ellipsoids: Analytical collision detection implemented on GPUs[J]. Computational Particle Mechanics, 2015, 2(2): 1－12.

[17] Tang M, Manocha D, Lin J, et al. Collision-streams: Fast GPU-based collision detection for deformable models[C]//Symposium on Interactive 3d Graphics & Games. DBLP,2011: 63－70.

[18] 黃偉益. 虛擬手術(shù)中碰撞檢測并行化算法的研究[J]. 電子技術(shù)與軟件工程，2015(4)：190－192.Huang Weiyi. Research on collision detection parallelization algorithm in virtual surgery[J]. Electronic Technology and Software Engineering, 2015(4): 190－192. (in Chinese with English abstract)

[19] 宋偉國. 小麥生長可視化關(guān)鍵技術(shù)研究[D]. 南京：南京農(nóng)業(yè)大學(xué)，2013.Song Weiguo. Study on Key Technologies of Wheat Growth Visualization[D]. Nanjing: Nanjing Agricultural University,2013. (in Chinese with English abstract)

[20] 石春林，朱艷，曹衛(wèi)星. 水稻葉曲線特征的機(jī)理模型[J]. 作物學(xué)報，2006，32(5)：656－660.Shi Chunlin, Zhu Yan, Cao Weixing. Mechanism model of rice leaf curve[J]. Journal of Crop Sciences, 2006, 32(5): 656－660. (in Chinese with English abstract)

[21] 孫愛珍，楊紅云，何火嬌，等. 水稻葉片三維可視化建模[J]. 安徽農(nóng)業(yè)科學(xué)，2008，36(4)：1320－1321.Sun Aizhen, Yang Hongyun, He Huojiao, et al. Three -dimensional visual modeling of rice leaves[J]. Anhui Agricultural Sciences, 2008, 36(4): 1320－1321. (in Chinese with English abstract)

[22] 孫勁光，吳素紅，周積林，等. 基于形狀分類的包圍盒碰撞檢測優(yōu)化算法[J]. 計算機(jī)應(yīng)用與軟件，2016(2)：242－245.Sun Jinguang, Wu Suhong, Zhou Jilin, et al. Optimal algorithm of bounding box collision detection based on shape classification[J]. Computer Applications and Software, 2016(2): 242－245. (in Chinese with English abstract)

[23] Nvidia CUDA Compute Unified Device Architecture Programming Guide[M]. NVIDIA, 2013

[24] Bernstein A J. Analysis of programs for parallel processing[J].IEEE Transactions on Electronic Computers, 1966,EC-15(5):757-763.

[25] 陳國良. 并行計算：結(jié)構(gòu)、算法、編程[M]. 北京：高等教育出版社，2003：4－175.

[26] Liu Y, Aluru S. LightScan: Faster scan primitive on CUDA compatible manycore processors[EB/OL]. [2017:06-06].http://www.researchgate.net/pulitation/301898340.

[27] Zhang Yonghui, Tang Liang, Liu Xiaojun, et al. Modeling morphological dynamics and color characteristics of rice panicle[J]. European Journal of Agronomy, 2014, 52(1): 279－290.

[28] Zhang Y H, Tang L, Liu X J, et al. Modeling dynamics of leaf color based on RGB value in rice[J]. Journal of Integrative Agriculture, 2014, 13(4): 749－759.

[29] 張永會，湯亮，劉小軍，等. 不同品種和氮素條件下水稻莖鞘夾角動態(tài)模擬[J]. 中國農(nóng)業(yè)科學(xué)，2012，45(21)：4361－4368.Zhang Yonghui, Tang Liang, Liu Xiaojun, et al. Dynamic simulation of stem and sheath in rice under different varieties and nitrogen conditions[J]. Chinese Journal of Agricultural Sciences, 2012, 45(21): 4361－4368. (in Chinese with English abstract)

[30] 張永會，湯亮，劉小軍，等. 基于高斯函數(shù)的水稻葉曲線動態(tài)模擬[J]. 中國農(nóng)業(yè)科學(xué)，2013，46(1)：215－224.Zhang Yonghui, Tang Liang, Liu Xiaojun, et al. Dynamic simulation of rice leaf curve based on gaussian function[J].Chinese Journal of Agricultural Sciences, 2013, 46(1): 215－224. (in Chinese with English abstract)