基于分形生成圖的樹木幾何建模方法

逯燕玲, 解文彬

(1.北京聯(lián)合大學(xué)應(yīng)用文理學(xué)院 北京100191; 2.北京市石景山區(qū)教育委員會會計核算中心網(wǎng)絡(luò)部 北京100043)

基于分形生成圖的樹木幾何建模方法

逯燕玲1, 解文彬2

(1.北京聯(lián)合大學(xué)應(yīng)用文理學(xué)院 北京100191; 2.北京市石景山區(qū)教育委員會會計核算中心網(wǎng)絡(luò)部 北京100043)

利用樹木的形態(tài)結(jié)構(gòu)特征,采取分形迭代系統(tǒng)構(gòu)建樹木的整體結(jié)構(gòu)形態(tài).用分形元和生成圖技術(shù)對樹木三維形態(tài)數(shù)據(jù)進行抽象分析和記錄,并用參數(shù)化曲線模擬樹木枝條的自然彎曲狀態(tài)以及在彎曲過程中枝條半徑的變化,以實現(xiàn)樹木形態(tài)結(jié)構(gòu)的三維可視化.

樹木幾何建模;迭代函數(shù)系統(tǒng);分形元;生成圖;參數(shù)化曲線

0 引言

虛擬樹木就是應(yīng)用計算機以可視化方式模擬樹木在三維空間中的形態(tài)結(jié)構(gòu)變化規(guī)律及生長發(fā)育過程,已成為數(shù)字林業(yè)信息可視化研究熱點[1-3].與傳統(tǒng)的生產(chǎn)模擬相比,它具有定量、直觀、精細、可以縮短研究周期等特點.但樹木可視化模擬一直是個難點問題,這主要是由于:①樹木的幾何結(jié)構(gòu)非常復(fù)雜,這給樹木三維數(shù)據(jù)的獲取、幾何建模及真實感繪制都帶來了很大困難;②樹木不僅具有復(fù)雜的幾何結(jié)構(gòu),而且具有豐富的可視化細節(jié),例如樹皮表面的凹凸不平、樹葉的半透明、復(fù)雜的陰影效果等,這使得真實表現(xiàn)樹木并非易事.

樹木的形態(tài)結(jié)構(gòu)在其生長過程中起著重要作用,它直觀反映了樹木生產(chǎn)發(fā)育狀況,是進行科學(xué)決策的重要因子[4],而在樹木幾何建模的過程中,其形態(tài)結(jié)構(gòu)也是真實地模擬樹木枝條的自然彎曲狀態(tài)的一個重要因素.在傳統(tǒng)的建模方法中,樹枝的形狀用圓臺或圓柱表示,繪制出的樹的枝干直上直下,效果很生硬,而真實樹木的主干和主要枝條都是彎曲的,其彎曲程度各異.本文通過觀測分析樹木的幾何結(jié)構(gòu)特征,構(gòu)造出描述樹木三維形態(tài)的幾何模型,以openGL三維圖形為可視化平臺,采用M icrosoft Visual C++計算機編程語言,用分形迭代系統(tǒng)構(gòu)建樹木的整體結(jié)構(gòu),用分形元和生成圖技術(shù)對樹木三維形態(tài)數(shù)據(jù)進行抽象分析和記錄,并通過Bezier這種基于控制點的自由曲線描述枝條的自然彎曲狀態(tài),從而實現(xiàn)了樹木形態(tài)結(jié)構(gòu)的三維可視化.

1 樹木的形態(tài)結(jié)構(gòu)模型

樹木的形態(tài)結(jié)構(gòu)遵循自相似規(guī)律,即局部與整體相似.樹木的結(jié)構(gòu)模型一般包括3個方面的信息[5]:描述植物由幾個成分或單元構(gòu)成的單元信息,描述各單元形狀和空間位置的幾何結(jié)構(gòu)信息和描述各單元在物理上的連接方式的拓撲結(jié)構(gòu)信息.幾何結(jié)構(gòu)模型是指對植物整體或部分器官組成結(jié)構(gòu)的三維信息描述.拓撲結(jié)構(gòu)模型是植物建模中的最基本模型,主要用于描述植物離散結(jié)構(gòu)單元之間的連接關(guān)系,并可以通過抽象的數(shù)學(xué)語言反映出植物的生長階段.

本文根據(jù)樹木的形態(tài)結(jié)構(gòu)特征,抽象出如圖1所示的樹的基本形態(tài)結(jié)構(gòu)模型,樹木的三維形態(tài)主要由主干、分枝和樹葉決定.樹木形態(tài)結(jié)構(gòu)的主要構(gòu)件是枝條,其在樹干上分枝的角度、長度和級數(shù)等是決定分枝空間格局以及樹冠形態(tài)的關(guān)鍵因素.根據(jù)其層次的不同又將枝劃分為一級枝、二級枝和三級枝.

2 樹木的整體結(jié)構(gòu)建模

樹木形態(tài)結(jié)構(gòu)的自相似性使得分形技術(shù)可以成功應(yīng)用于樹木的計算機建模過程中.所謂分形[6],在數(shù)學(xué)上是指具有無限的細節(jié)、自相似等性質(zhì)的一類圖形.迭代函數(shù)系統(tǒng)(IFS)[7]屬于一種分形構(gòu)形系統(tǒng),它借助于計算機強大的迭代計算能力,將自相似性、層次的多重性和不同層次的規(guī)則統(tǒng)一性應(yīng)用于計算機圖形領(lǐng)域,可以產(chǎn)生許多具有無窮細節(jié)的、精致紋理的圖形.尤其是在樹木形態(tài)模擬方面,IFS方法可以表現(xiàn)出樹木整體形態(tài)的不規(guī)則性以及整體與局部細節(jié)的自相似性,較之以規(guī)則形態(tài)構(gòu)圖的傳統(tǒng)方法更具優(yōu)勢.IFS算法有2種[8]:①確定性迭代算法,指用以迭代的規(guī)則是確定性的,由一組仿射變換構(gòu)成.確定性迭代算法總能夠產(chǎn)生清晰完整的圖形,可以對細節(jié)精確控制,缺點是浪費存儲空間.②隨機性迭代算法,不需要占用很大的存儲空間,易于實現(xiàn),但需要規(guī)定一個迭代的最大次數(shù).本文采用IFS的隨機迭代法來構(gòu)建樹木模型.

樹木的每一級側(cè)枝螺旋狀依次著生在上一級枝干的結(jié)點處,在幾何造型上與上一級枝干相似,可以用遞歸算法構(gòu)造樹木模型.在遞歸過程中不斷修改其屬性值,每次新生枝條產(chǎn)出之前,引入隨機因子,用于控制新生枝條是否分枝及分枝的角度和長度,使得樹枝的傾斜度和長度產(chǎn)生隨機變動.參數(shù)dep th用于控制遞歸的深度,圖2為dep th取不同值時由隨機迭代算法生成的樹模型,其樹枝的形狀在此用圓柱表示.

3 彎曲枝條建模

觀察圖2,用圓臺表示樹干的方法使整個樹體形態(tài)較自然樹體形態(tài)“筆直”,不能體現(xiàn)自然樹干的隨機彎曲.模擬植物枝條的自然彎曲狀態(tài)是直觀形象地再現(xiàn)植物形體的重要內(nèi)容.彎曲樹枝光滑連續(xù),采用Bezier曲線來繪制是一種很好的解決方法,它具有良好的受控特點,只需要改動幾個控制點就能重新得到一個曲線,能很方便地找到模擬樹枝彎曲的近似曲線.

3.1 Bezier曲線的數(shù)學(xué)表述

Bezier曲線是一種外形可以構(gòu)成控制多邊形的曲線,給定空間n+1個點p0,p1,…,pn,稱下列參數(shù)曲線為n次的Bezier曲線:

其中,Cin是二項式系數(shù)級n!/[i!(n-i)!],Bi,n(t)稱為伯恩斯坦基底函數(shù),滿足

折線P0P1,P1P2,…,PnP0構(gòu)成該曲線C(t)的控制多邊形,P0,P1,…,Pn各點為C(t)的控制頂點.本文采用二次Bezier曲線來描述擬合枝條曲線,當(dāng)n=2時,

因此,二次Bezier曲線對應(yīng)一條有3個控制點P0,P1,P2,起點在P0,終點在P2處的拋物線.

3.2 計算二次Bezier曲線的控制點

要擬合出枝條曲線,關(guān)鍵是確定控制點P0,P1,P2的坐標(biāo),為控制點P0取定一個坐標(biāo)值,為了計算方便,定為(0,0,0),P2點的坐標(biāo)設(shè)為(x2,y2,0),樹木的主干與z軸平行,控制點P0到P2的直線距離以及側(cè)枝與主干間的夾角可通過測量得到,分別用參數(shù)L和α表示,可通過式(5)求出控制點P2的坐標(biāo),

控制點P1的坐標(biāo)設(shè)為(x1,y1,0),將P0,P1,P2的坐標(biāo)代入二次Bezier曲線的公式,則曲線上任一點的坐標(biāo)可由式(6)表示為

其中,i=1,2,…,N,N表示將枝條曲線平均分段后的段數(shù),t=i×dt,dt為相應(yīng)的步長.

根據(jù)式(6),當(dāng)t從0到1變化時,將已求出的x2,y2的值代入,可得到枝條曲線上N個點T0,T1,…, TN的用x1,y1表示的坐標(biāo),再由兩點間的距離公式,可由式(7)求出枝條曲線上任意相鄰兩點間的距離為

因此枝條曲線的長度PS可近似表示為

式(8)是由參數(shù)x1,y1表示的式子,枝條曲線的長度PS可從實際測量中得到,所以可根據(jù)此式求出控制點P1的坐標(biāo).由控制點P0,P1,P2的坐標(biāo),可以擬合出枝條曲線.在IFS中使用已擬合出的枝條曲線,建立起樹木的結(jié)構(gòu)骨架,如圖3所示,樹木的枝條有了一定的彎曲效果.

3.3 基于分形元和生成圖技術(shù)的數(shù)據(jù)抽象

將圖3中的樹木結(jié)構(gòu)骨架圖轉(zhuǎn)換為樹的分形元和生成圖,如圖4所示.

其中,除終止結(jié)點(A4)外,其余各結(jié)點之上都含有分支.例如圖4(a)中:A0結(jié)點對應(yīng)A0-A4分支,A1結(jié)點對應(yīng)A1-B分支,A2結(jié)點對應(yīng)A2-C分支,A3結(jié)點對應(yīng)A3-D分支.可以用結(jié)點A1代表其所對應(yīng)的分支A1-B,并對其賦予該分支所具有的特征參數(shù)長度L和夾角tanα值,作為分支A1-B的權(quán)值.同理,結(jié)點A2代表其所對應(yīng)的分支A2-C,并對其賦予該分支所具有的特征參數(shù)長度L和夾角tanα值,作為分支A2-C的權(quán)值;結(jié)點A3代表其所對應(yīng)的分支A3-D,并對其賦予該分支所具有的特征參數(shù)長度L和夾角tanα值,作為分支A3-D的權(quán)值.由此,可以得到一個樹形拓撲結(jié)構(gòu)圖G=,A0= ,其中,L=,k=tanα=x2/y2.同理,可以將圖3(b)處理為圖4(b)進行數(shù)據(jù)抽象,其中, A1與A′B 0,A2與A′C0,A3與A′D 0結(jié)點為同結(jié)點,并由此獲得其相關(guān)參數(shù).

3.4 描述枝干的廣義圓柱體

樹木的枝條不僅具有彎曲狀態(tài),而且在彎曲的過程中,枝條的半徑不斷變化,本文采用橫截面直徑變化的廣義圓柱體來描述樹木的枝條.廣義圓柱體是以三維空間曲線為軸的立體,軸上任意一個點都定義一個封閉的截面.

對于已經(jīng)擬合出的枝條曲線,t從0到1變化得到曲線上的N個點,對任意點Ti(i=1,2,…,N),過該點的切線可以表示為

以插值多項式近似代替函數(shù),以插值多項式在結(jié)點上的導(dǎo)數(shù)值近似代替函數(shù)在結(jié)點上的導(dǎo)數(shù)值,利用該方法產(chǎn)生的微分與用公式求出的微分幾乎一致.在實現(xiàn)過程中,將已經(jīng)擬合出的枝條曲線均勻分段,用變量DuanShu表示所分段數(shù).通過求出的切向量及指定的半徑Ri,可以計算出封閉截面圓上均勻分布的輪廓點的坐標(biāo),用變量DianShu表示每一截面圓上輪廓點的個數(shù).為了更真實地表現(xiàn)枝條由底端到末梢由粗變細的狀態(tài),可以使半徑Ri逐漸變小,繪制過其他N-1點的截面圓上分布均勻的輪廓點的坐標(biāo),將計算出的坐標(biāo)值存入三維數(shù)組Cylinder[DuanShu][DianShu][3]中,再依次將相鄰的4個點用四邊形連接,圖5為曲線分段數(shù)及輪廓點個數(shù)分別取不同值時所繪制出的廣義圓柱體.

在程序中,將Bezier曲線分為120段,即取DuanShu為120,每一截面圓上取60個輪廓點,即DianShu為60,枝條的彎曲狀態(tài)自然,計算機的運算速度比較理想.

將已經(jīng)建好的樹木枝干運用到分形迭代系統(tǒng)中,可以建立樹干彎曲狀態(tài)自然的樹木形態(tài)模型,如圖6所示.

4 結(jié)論

觀察圖7可以發(fā)現(xiàn),用圓柱來繪制的樹的枝干直上直下,效果很生硬,不能體現(xiàn)自然樹干的隨機彎曲.基于控制點變化的Bezier曲線能較好地模擬枝條自然彎曲和光滑連續(xù)的狀態(tài),構(gòu)形真實、靈活,而且用較少的具有農(nóng)學(xué)意義的參數(shù)就可描述枝條曲線形態(tài),易與樹木的形態(tài)結(jié)構(gòu)模型相結(jié)合.

樹木的自然形態(tài)結(jié)構(gòu)雖然復(fù)雜多變,但都具有統(tǒng)計意義上的自相似性,其每一部分都相似于整體.本文基于圖論理論,根據(jù)樹木形態(tài)學(xué)原理和計算機圖形學(xué)技術(shù),抽象出樹木的形態(tài)結(jié)構(gòu)模型;采用分形技術(shù)建立樹木的整體結(jié)構(gòu),通過引入隨機因素和控制迭代概率來自由改變樹木的形態(tài);并使用Bezier曲線控制枝條的彎曲狀態(tài),建立了呈現(xiàn)自然彎曲狀態(tài)的樹干,樹形態(tài)其效果逼真,基本上與自然狀態(tài)下的樹一致.

圖7 不同方法生成的樹模型對比Fig.7 The comparison of treemodels using different methods

[1] Room P,Hanan J,Prusinkiew ics P.Virtual plants:new perspectives fo r ecologists,pathologists and agricultural scientists[J].Trends in Plant Science,1996,1(1):33-38.

[2] Wilson PA,Chakrabrty S.The virtual p lant:a new tool for the study and management of p lant diseases[J].Crop Protection,1998,17(3):231-239.

[3] de Reffye P,Edilin C,Franqon J,et al.Plants models faithful to botanical structure and development[J].Computer Graphic,1998,22(4):151-158.

[4] 雷相東,常敏,陸元昌,等.長白落葉松單木生長可視化系統(tǒng)設(shè)計與實現(xiàn)[J].計算機工程與應(yīng)用,2006,42(17):180-183.

[5] Godein C,Caraglio Y.A multiscale model of p lant topological structures[J].J theor Biol,1998,191:1-46.

[6] 張濟忠.分形[M].北京:清華大學(xué)出版社,1995.

[7] Dodds P.Advanced distributed learning,sharable content object referencemodel version 1.2[EB/OL].[2002-03-25]. http://www.adlnet.o rg.

[8] 謝紹鋒,肖化順.虛擬森林資源信息三維可視化中樹模型的生成方法[J].中南林業(yè)調(diào)查規(guī)劃,2007,26(1):43-47.

Trees Geometry Modeling Method Based on the Fractal Graph Generating

LU Yan-ling1, XIEWen-bin2
(1.College of A rts and Sciences,Beijing Union University,Beijing 100191,China; 2.N etw ork Department of Accounting Center,Education Comm ittee of Beijing Shijingshan D istrict,Beijing 100043,China)

The overall structure of tree shapew ith IFS is constructed and the natural bending state and changes in radius of tree branchesw ith parametric curve are simulated based on morphological characteristic of trees.The three-dimensional mo rphological data of trees is abstractly analyzed and recorded by using f ractal unit and tree image in IFS.The natural bending state of tree branches and three-dimensionalmo rphological structure of tree are realized on the computer.

geometric modeling fo r tree;iteration function system(IFS);fractal unit;tree image in IFS;parametric curve

O 157.6

A

1671-6841(2010)03-0041-05

2010-02-01

逯燕玲(1963-),女,副教授,碩士研究生,主要從事離散數(shù)學(xué)、系統(tǒng)工程及計算機網(wǎng)絡(luò)技術(shù)研究,E-mail:yanling@ygi.edu.cn.