王春華,韓 棟

(黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

0 引 言

三維樹木模型是虛擬場(chǎng)景中具有普遍性和代表性的自然景觀模型[1-3]，可廣泛應(yīng)用于計(jì)算機(jī)游戲、虛擬生態(tài)景觀、數(shù)字農(nóng)業(yè)、虛擬城市等。因樹木種類繁多且?guī)缀谓Y(jié)構(gòu)差異性大，三維樹木建模研究一直是計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)視覺(jué)和虛擬現(xiàn)實(shí)等領(lǐng)域具有挑戰(zhàn)性的研究課題[4-6]。

自組織結(jié)構(gòu)建模和遞歸結(jié)構(gòu)建模是樹木真實(shí)感建模的2大主流思想，早期研究可分別追溯于Ulam于1962年發(fā)表的學(xué)術(shù)論文[7]和Honda于1971年提出的參數(shù)化建模方法[8]。Honda將樹木視為一種參數(shù)的遞歸結(jié)構(gòu)，參數(shù)主要由分枝角度、單元模塊尺寸等構(gòu)成，后來(lái)的樹木建模分形方法[9-10]、L-system方法[11]皆在此基礎(chǔ)上產(chǎn)生。遞歸結(jié)構(gòu)的算法，由于基于一個(gè)基本的遞歸結(jié)構(gòu)不斷地迭代，因此局部參數(shù)的細(xì)微變化將引起整個(gè)模擬結(jié)果的巨大變化，且整個(gè)建模過(guò)程不易控制。Ulam將樹木視為自組織的結(jié)構(gòu)，分枝模型源于個(gè)體單元對(duì)資源的競(jìng)爭(zhēng)，文獻(xiàn)[12-15]在此基礎(chǔ)上進(jìn)行了更深入的研究，都強(qiáng)調(diào)樹木結(jié)構(gòu)模型對(duì)周圍環(huán)境的自適應(yīng)性。據(jù)Sachs和Novoplansky[16]觀察，較之遞歸結(jié)構(gòu)，Ulam自組織結(jié)構(gòu)的思想能更好地捕獲樹木生長(zhǎng)的本質(zhì)。

本文基于自組織結(jié)構(gòu)的思想，提出一種樹木基本生長(zhǎng)單位——芽基于光源競(jìng)爭(zhēng)的建模方法，詳細(xì)描述了模擬算法各個(gè)環(huán)節(jié)的計(jì)算過(guò)程，通過(guò)實(shí)驗(yàn)驗(yàn)證了算法在模擬樹木頂端優(yōu)勢(shì)的各種情況、向地性現(xiàn)象和向光性現(xiàn)象等方面的有效性，生成結(jié)果真實(shí)感強(qiáng)。

1 相關(guān)術(shù)語(yǔ)

為了便于理解和建模，本文將樹木視為一種分層次組織的模塊化結(jié)構(gòu)，從芽的生長(zhǎng)命運(yùn)和頂端優(yōu)勢(shì)2方面介紹樹木生長(zhǎng)的植物學(xué)原理。

1.1 芽的生長(zhǎng)命運(yùn)

樹木由芽生長(zhǎng)發(fā)育而成。根據(jù)芽的位置，芽可分為頂芽和側(cè)芽2種，側(cè)芽位于葉和枝軸之間，頂芽位于樹枝或樹干末端，如圖1所示。葉與樹枝或樹干的交叉點(diǎn)稱為節(jié)點(diǎn)，同一枝上相鄰2個(gè)節(jié)點(diǎn)之間稱為節(jié)間。受生長(zhǎng)環(huán)境影響，芽有4種不同的生長(zhǎng)命運(yùn)：生長(zhǎng)為幼枝、生長(zhǎng)為花、處于休眠狀態(tài)(在以后的某個(gè)生長(zhǎng)期再生長(zhǎng))和脫落死亡。

圖1 樹木生長(zhǎng)構(gòu)成圖

1.2 頂端優(yōu)勢(shì)

植物學(xué)上，樹木外觀主要受頂端優(yōu)勢(shì)的影響，不同的頂端優(yōu)勢(shì)將產(chǎn)生不同的樹冠。頂芽?jī)?yōu)先生長(zhǎng)而使側(cè)芽受到抑制的現(xiàn)象，稱為頂端優(yōu)勢(shì)，其可分為3種情況：1)頂端可以完全或幾乎完全抑制側(cè)芽生長(zhǎng)，樹木主干明顯；2)一個(gè)枝條的生長(zhǎng)可以比其他枝條占優(yōu)勢(shì)，該枝條生長(zhǎng)茂密；3)頂端可以影響分枝和葉的方位。優(yōu)勢(shì)的程度與遺傳性、環(huán)境因素、生理過(guò)程及植物年齡等有關(guān)。究其本質(zhì)，頂端優(yōu)勢(shì)是由樹林內(nèi)部營(yíng)養(yǎng)成份傳輸和外部光照等因素決定的，本文主要通過(guò)外部光源競(jìng)爭(zhēng)思想來(lái)模擬樹木的建模。

2 TMLC算法的提出

本文通過(guò)迭代模擬樹木芽在每個(gè)生長(zhǎng)周期內(nèi)與光源競(jìng)爭(zhēng)來(lái)實(shí)現(xiàn)樹木建模，該建模算法簡(jiǎn)稱為TMLC(Tree Modeling based on Light Competition)。在TMLC算法中，芽的每個(gè)生長(zhǎng)周期都需要完成3個(gè)主要環(huán)節(jié)的計(jì)算：計(jì)算芽的生長(zhǎng)環(huán)境、分配芽的生長(zhǎng)資源和模擬幼枝生長(zhǎng)，如圖2所示。

2.1 芽生長(zhǎng)環(huán)境計(jì)算

圖2 TMLC算法主要流程框圖

為了便于描述，定義Na={n|n是芽a的錐形半影區(qū)中的體素網(wǎng)格}，即體素網(wǎng)格ni∈Na；定義C(Na)表示Na中陰影值最小的體素網(wǎng)格。

1)初始化。將生長(zhǎng)空間劃分為體素網(wǎng)格，如圖3所示。初始化每個(gè)網(wǎng)格(x,y,z)的陰影值s=0。

2)產(chǎn)生陰影區(qū)。芽A所在體素網(wǎng)格(X,Y,Z)產(chǎn)生一個(gè)位于它下方、光照受其影響的錐形半影區(qū)NA，NA中元素n的空間索引值(x,y,z)=(X±p,Y-q,Z±p)，其中q=0,1,…，qmax，p=0,1,…，q。

3)計(jì)算陰影增量。受芽A遮擋的影響，Na中元素n的陰影增量Δs=ab-q，其中a是比例系數(shù)，a>0；b是體素的光密度值，b>1。

4)計(jì)算光量值。體素(x,y,z)所接收到的光量Q=max (C-s+a,0)，C為體素在沒(méi)有任何遮擋時(shí)的光量值。

圖3 芽生長(zhǎng)空間體素網(wǎng)格圖

2.2 芽生長(zhǎng)資源分配

1)統(tǒng)計(jì)每個(gè)枝上芽的數(shù)量以及各芽所接收的光量Q值；

3)生成每個(gè)枝的優(yōu)先級(jí)鏈表，按光量值遞減排序各芽；

4)若有頂端優(yōu)勢(shì)，則不論枝上末端芽所接收的光量Q值大小，均將其移至優(yōu)先級(jí)鏈表的頭部；

5)根據(jù)優(yōu)先級(jí)鏈表，分配各枝和枝上各芽的內(nèi)生資源，分配表達(dá)式如下：

(1)

圖4 資源分配權(quán)重系數(shù)函數(shù)圖

6)判斷芽的生長(zhǎng)：芽在下一生長(zhǎng)周期內(nèi)將生長(zhǎng)出的節(jié)間數(shù)為n=?vi」，節(jié)間長(zhǎng)度為1=vi/n，其中，vi表示芽分配到的內(nèi)生資源值，若n=0，則表示該芽停止生長(zhǎng)；n≥1表示該芽將長(zhǎng)出至少一個(gè)節(jié)間。

2.3 幼枝生長(zhǎng)模擬

幼枝生長(zhǎng)模擬包括芽死亡脫落、幼枝生長(zhǎng)方向優(yōu)化和幼枝半徑計(jì)算3部分。

1)芽死亡脫落判斷。芽的死亡脫落是樹木生長(zhǎng)過(guò)程中的自然現(xiàn)象，也是基于規(guī)則樹木建模類方法的重要組成部分。本文借鑒Měch提出的植物與環(huán)境交互的可視化模型[18]，將芽接收到的光量值Q與可能生長(zhǎng)出的節(jié)間數(shù)n比較，若比值小于自定義的閾值ε，則視為芽將死亡脫落，反之則生長(zhǎng)為幼枝。即：

(2)

其中，i=1,2,…，N。

(3)

其中，α，β和γ為權(quán)重系數(shù)，α+β+γ=1，改變3個(gè)系數(shù)的比例大小，將會(huì)引起樹木外觀的可預(yù)測(cè)性變化。

圖5 母節(jié)間和子節(jié)間半徑關(guān)系圖

3 實(shí)驗(yàn)分析

依托2.2 GHz主頻的雙核CPU，4 G內(nèi)存以及NVIDIA GEFORCE 610M顯卡，在Windows7 64位操作系統(tǒng)下，開發(fā)環(huán)境為Visual Studio2010，本文采用C++語(yǔ)言對(duì)TMLC算法進(jìn)行了實(shí)現(xiàn)，分以下幾種情況進(jìn)行實(shí)驗(yàn)分析：

1)體素網(wǎng)格的光密度值模擬。根據(jù)TMLC算法分析，光密度值b越大，體素(x,y,z)所接收到的光量Q=max (C-s+a,0)=max(C+a(1-b-q),0)值越大。圖6是在其他參數(shù)相同情況下的實(shí)驗(yàn)結(jié)果，光密度值遞增，樹木越茂密；光密度值遞減，樹枝越稀疏，模擬結(jié)果與自然現(xiàn)象吻合。

圖6 光密度值模擬結(jié)果圖

2)頂端優(yōu)勢(shì)模擬分析。根據(jù)資源分配模型可知，比例系數(shù)k越大，分配到樹枝上各芽的資源就越多，樹枝就越茂密，相應(yīng)地，主干就越不明顯。圖7是在其他參數(shù)相同情況下的實(shí)驗(yàn)結(jié)果，比例系數(shù)k遞增，樹枝越茂密；比例系數(shù)k遞減，主干越明顯，驗(yàn)證了算法TMLC的正確性。

圖7 頂端優(yōu)勢(shì)模擬結(jié)果圖

3)芽脫落模擬分析。根據(jù)芽死亡脫落判斷模型可知，當(dāng)設(shè)置芽脫落閾值ε越大，芽越容易死亡脫落；閾值ε越小，芽越容易生長(zhǎng)出來(lái)。圖8是在其他參數(shù)相同情況下的實(shí)驗(yàn)結(jié)果，閾值ε遞增，樹枝越稀疏；閾值ε遞減，樹枝越茂密，驗(yàn)證了算法TMLC的正確性。

圖8 芽死亡脫落模擬結(jié)果圖

圖9 向性模擬結(jié)果圖

圖10 芽生長(zhǎng)方向權(quán)重系數(shù)變化模擬結(jié)果圖

4)幼枝方向權(quán)重系數(shù)模擬分析。根據(jù)幼枝生長(zhǎng)方向優(yōu)化模型公式(3)可知，芽的生長(zhǎng)方向由3個(gè)方向及其權(quán)重來(lái)決定。圖9是在其他參數(shù)相同情況下，向性方向變化的模擬結(jié)果，從圖9可以看出樹木的生長(zhǎng)方向與向性方向基本一致，與自然現(xiàn)象吻合。圖10是向性方向向上時(shí)，α，β和γ權(quán)重系數(shù)改變時(shí)的實(shí)驗(yàn)結(jié)果，從圖可以看出，當(dāng)權(quán)重系數(shù)調(diào)整時(shí)，將生成形狀各異的樹木。

4 結(jié)束語(yǔ)

本文從樹木生長(zhǎng)對(duì)光源競(jìng)爭(zhēng)的角度，提出了自組織的建模算法，實(shí)驗(yàn)?zāi)M結(jié)果表明，TMLC算法能有效地進(jìn)行樹木建模，并且通過(guò)參數(shù)的調(diào)制可以生成可預(yù)測(cè)性的樹木外觀，操作簡(jiǎn)單，對(duì)模擬結(jié)果逼真、自然。在此基礎(chǔ)上，樹木在有障礙物生長(zhǎng)環(huán)境下的建模，如多棵樹木共同競(jìng)爭(zhēng)、有石頭或人為障礙物的環(huán)境，是下一步的研究方向。

[1] 譚云蘭,賈金原,張晨,等. 3D樹木建模技術(shù)研究進(jìn)展[J]. 中國(guó)圖象圖形學(xué)報(bào)， 2013,18(11):1520-1526.

[2] 蔣艷娜,肖伯祥,郭新宇,等. 植物建模與動(dòng)畫合成研究[J]. 系統(tǒng)仿真學(xué)報(bào), 2015,27(4):881-892.

[3] Xie Ke, Yan Feilong, Sharf A, et al. Tree modeling with real tree-parts examples[J]. IEEE Transactions on Visualization & Computer Graphics, 2016,22(12):2608-2618.

[4] 于舜,張鐵. 雨場(chǎng)下的樹木建模方法分析[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014,35(7):913-916.

[5] Tan Ping, Zeng Gang, Wang Jingdong, et al. Image-based tree modeling[J]. ACM Transactions on Graphics, 2007,26(3): Article No. 87.

[6] Neubert B, Franken T, Deussen O. Approximate image-based tree-modeling using particle flows[J]. ACM Transactions on Graphics, 2007,26(3): Article No. 88.

[7] Ulam S. On some mathematical properties connected with patterns of growth of figures[C]// Proceedings of Symposia on Applied Mathematics. 1962,14:15-24.

[8] Honda H. Description of the form of trees by the parameters of the tree-like body: Effects of the branching angle and the branch length on the shape of the tree-like body[J]. Journal of Theoretical Biology, 1971,31(2):331-338.

[9] 張德嘉,梁爽,張晨,等. 基于增強(qiáng)PyrLK光流法的三維樹木骨架重建方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2015,27(7):1247-1254.

[10] 趙春江,陸聲鏈,郭新宇,等. 數(shù)字植物研究進(jìn)展：植物形態(tài)結(jié)構(gòu)三維數(shù)字化[J]. 中國(guó)農(nóng)業(yè)科學(xué), 2015,48(17):3415-3428.

[11] 王春華,楊克儉. 基于L-系統(tǒng)和Perlin噪聲函數(shù)的風(fēng)吹樹動(dòng)模擬[J]. 計(jì)算機(jī)工程, 2009,35(12):191-193.

[12] Runions A, Lane B,Prusinkiewicz P. Modeling trees with a space colonization algorithm[C]// Proceedings of the Eurographics Workshop on Natural Phenomena. 2007:63-70.

[13] Palubicki W, Horel K, Longay S, et al. Self-organizing tree models for image synthesis[J]. ACM Transactions on Graphics, 2016,28(3):1-10.

[14] Wang Yutong, Xue Xiaowei, Jin Xiaogang, et al. Creative virtual tree modeling through hierarchical topology-preserving blending[J]. IEEE Transactions on Visualization and Computer Graphics, 2017,23(12):2521-2534.

[15] Tang Liyu, Chen Chongcheng, Huang Hongyu, et al. An integrated system for 3D tree modeling and growth simulation[J]. Environmental Earth Sciences, 2015,74(10):1-14.

[16] Sachs T, Novoplansky A. Tree from: Architectural models do not suffice[J]. Israel Journal of Plant Sciences, 1995,43(3):203-212.

[17] Bornhofen S, Lattaud C. Competition and evolution in virtual plant communities: A new modeling approach[J].Natural Computing, 2009,8(2):349-385.

[18] Měch R, Prusinkiewicz P. Visual models of plants interacting with their environment[C]// Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. 1996:397-410.