基于分枝類型和空間點(diǎn)的三維樹木建模方法

(1. 武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430063； 2. 黃淮學(xué)院 計(jì)算機(jī)科學(xué)技術(shù)系，河南 駐馬店 463000)

摘 要：生成圖形相似性太強(qiáng)和不易局部控制是目前主流植物建模方法存在的共同不足之處，基于指定樹木的分枝類型和空間的隨機(jī)分布點(diǎn)，提出了一種新的樹木建模方法，克服了目前樹木建模方法的上述缺陷；同時(shí)，該方法還能簡便地進(jìn)一步控制樹木枝條的稀疏密集和光順程度。實(shí)驗(yàn)結(jié)果表明，該方法生成的圖形逼真、自然，為樹木建模提供了一種新的思路。

關(guān)鍵詞：分枝類型； 空間點(diǎn)； 樹木； 三維建模

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)04-1591-02

Trees’3D modeling based on branching type and space points

WANG Chun-hua1，2， YANG Ke-jian1， HAN Dong2

(1.School of Computer Science Technology， Wuhan University of Technology， Wuhan 430063， China; 2.Dept. of Computer Science， Huanghuai University， Zhumadian Henan 463000， China)

Abstract:L-systems， IFS and fractal method are the prevailing modeling methods for trees， but two common shortages exist in them. One is that the generated graphs are of strong self-similarity and unable to represent the differences of different trees. The other is that local tiny change of parameter will cause tremendous change of globe shape， so it is froward to model trees. Based on the branching type and stochastic space points， proposed a novel modeling method for trees. This method not only overcame the above shortcoming but also could easily control the branches’ smooth level and density. Experiments show that the result graphs are true to nature and the modeling method can be applied to computer animation.

Key words：branching type; space points; trees; 3D modeling

對(duì)樹木形狀的三維建模一直是計(jì)算機(jī)圖形學(xué)領(lǐng)域的一個(gè)研究熱點(diǎn)，大量學(xué)者對(duì)此進(jìn)行了深入研究[1]。樹木可視化建模的思想起源于Honda[2]在1971年提出遞歸分枝結(jié)構(gòu)建模的思想， 他提出利用少量的樹木幾何屬性（如分枝的角度、節(jié)間的長度比例等）進(jìn)行樹木模擬。目前樹木建模的主流方法，如以文法為基礎(chǔ)的L系統(tǒng)[3，4]、IFS（函數(shù)迭代系統(tǒng)）[5]、分形方法[6]，都是基于Honda提出的將樹木看成遞歸分枝結(jié)構(gòu)的思想，生成的樹木具有很強(qiáng)的相似性和規(guī)則性。除此之外，L系統(tǒng)是根據(jù)產(chǎn)生式規(guī)則來生成圖形的，對(duì)一種樹的產(chǎn)生式規(guī)則很難應(yīng)用到另一種樹上；而IFS和分形方法中，局部參數(shù)的細(xì)微改變將引起整個(gè)結(jié)構(gòu)的巨大變化，不易控制[7]。

1 相關(guān)工作

為了減小生成圖形的相似性和使建模方法易于局部控制，目前基于遞歸結(jié)構(gòu)建模樹木的方法做了一些努力，主要工作可歸納為在遞歸過程中添加隨機(jī)變量控制。文獻(xiàn)[3]中提到將L系統(tǒng)調(diào)用特定規(guī)則，修改成按一定概率隨機(jī)調(diào)用指定規(guī)則集中的某一規(guī)則（即隨機(jī)L系統(tǒng)），從而減小生成圖形的規(guī)則性；文獻(xiàn)[8]提出了指定樹木主軸和通過用戶的操作控制遞歸深度，從而通過局部控制來控制L系統(tǒng)生成樹木的外觀；文獻(xiàn)[9]在IFS系統(tǒng)的基礎(chǔ)上，提出了基于正余弦的IFS碼系統(tǒng)，可以獲得大量造型新穎的吸引子圖像，從一定程度上克服IFS描述方法的生硬性和一律性；文獻(xiàn)[6，10]則在分形方法的每次遞歸中，通過添加隨機(jī)變量改變分枝的角度和節(jié)間的長度，從而減輕生成圖形的同性特征。但是，由于這些建模方法都是基于以自相似形為基礎(chǔ)的遞歸結(jié)構(gòu)，不管怎么改進(jìn)，生成的樹木仍然都具有形態(tài)差異性小、千篇一律的現(xiàn)象。

本文提出一種新的樹木建模方法，避免目前建模方法的不足，通過指定植物學(xué)上的樹木分枝類型（單軸分枝、合軸分枝和假二叉分枝）生成相應(yīng)的樹木圖形，生成的樹木自然、逼真。

2 算法MTSP的提出

本文提出的樹木建模方法是將一定空間中的隨機(jī)分布點(diǎn)按一定策略連接實(shí)現(xiàn)的，具體的算法根據(jù)英文的首字母命名為MTSP (modeling trees with space point)。

為了說明該算法的思想，先作如下三個(gè)定義：

定義1 d(a，b)表示空間a點(diǎn)到空間點(diǎn)b的歐氏距離，d(a，b)=(a.x-b.x)2+(a.y-b.y)2+(a.z-b.z)2。

定義2 S(V，t)表示以空間點(diǎn)t為起點(diǎn)，以空間點(diǎn)集合V中各元素為終點(diǎn)的向量和，即S(V，t)=∑vi∈V(vi-t)。其中：(vi-t)表示空間點(diǎn)t到空間點(diǎn)vi的向量；∑表示對(duì)向量求和。

定義3 將隨機(jī)生成的空間點(diǎn)分為兩種類型：一種用于標(biāo)志生成樹的各節(jié)點(diǎn)，稱為樹節(jié)點(diǎn)，兩個(gè)樹節(jié)點(diǎn)間的連線稱為節(jié)間（internodes），連續(xù)的節(jié)間形成樹干或樹枝；另一種稱為吸引點(diǎn)，滿足一定條件的吸引點(diǎn)集合決定新樹節(jié)點(diǎn)的位置和方向。

MTSP算法的具體內(nèi)容如下：

a）定義影響距離di 、刪除距離dk和樹節(jié)點(diǎn)間的連接距離D并賦初值，di用于限定影響樹節(jié)點(diǎn)的吸引點(diǎn)集合，dk用于指定需要?jiǎng)h除的吸引點(diǎn)的集合。

b）在一定范圍的空間包圍盒（如立方體、圓柱體等）內(nèi)，產(chǎn)生均勻分布（或高斯分布等其他分布）的若干吸引點(diǎn)和至少一個(gè)樹節(jié)點(diǎn)，吸引點(diǎn)的集合表示為V，樹節(jié)點(diǎn)的集合表示為T。

c）尋找樹節(jié)點(diǎn)集合T中以每個(gè)樹節(jié)點(diǎn)t為球心，di為半徑的球體內(nèi)吸引點(diǎn)集合Vt，Vt中元素滿足如下條件：s∈Vt，VtV，t′∈T，t∈T且t′≠t，d(s，t)≤d(s，t′)。

d）對(duì)每個(gè)樹節(jié)點(diǎn)t的吸引點(diǎn)集合Vt，求S(Vt，t)，并規(guī)范化S(Vt，t)得到向量N(Vt，t)，即N(Vt，t)=S(Vt，t)/‖S(Vt，t)‖。其中：‖S(Vt，t)‖為向量S(Vt，t)的長度。

e）創(chuàng)建新的樹節(jié)點(diǎn)tn并且連接t和tn，tn到t的距離d(tn，t)=N(Vt，t)×D，方向?yàn)橄蛄縉(Vt，t)的方向。

f）對(duì)于每個(gè)新建的樹節(jié)點(diǎn)tn，刪除吸引點(diǎn)集合Vd，Vd滿足如下條件：s∈Vd，VdV，d(s，tn)≤dk。

g）重復(fù)c）~f）直到吸引點(diǎn)集合為空或達(dá)到指定循環(huán)次數(shù)。

3 指定分枝類型的樹木生成

在植物學(xué)上，樹木芽的性質(zhì)活動(dòng)情況不同，所產(chǎn)生的枝的組成和外部形態(tài)也不同，因而分枝的方式各異，主要有單軸分枝、合軸分枝和假二叉分枝等。本文根據(jù)分枝的類型，由提出的MTSP算法來生成相應(yīng)的三維樹木圖形。

3.1 方法概述

結(jié)合MTSP算法，首先在產(chǎn)生空間隨機(jī)點(diǎn)的包圍盒內(nèi)指定分枝類型的主干節(jié)點(diǎn)，并對(duì)節(jié)點(diǎn)進(jìn)行連接產(chǎn)生主干，將能體現(xiàn)分枝類型的點(diǎn)作為初始的樹節(jié)點(diǎn)。圖1中實(shí)心的球是樹節(jié)點(diǎn)；空心球是輔助產(chǎn)生能體現(xiàn)分枝類型的節(jié)點(diǎn)。利用MTSP在包圍盒內(nèi)產(chǎn)生隨機(jī)空間點(diǎn)作為吸引點(diǎn)，并執(zhí)行算法的每一步，將生成指定分枝類型的樹木。

3.2 方法實(shí)例

下面給出一個(gè)簡化的實(shí)例，說明本文提出的生成樹木方法的具體操作過程，如圖2所示。

a）在包圍盒內(nèi)指定樹木分枝類型（這里為二分叉型），產(chǎn)生主干和樹節(jié)點(diǎn)（實(shí)心小球），如圖2（a）所示，正方體內(nèi)有一個(gè)二分叉主干和兩個(gè)初始的樹節(jié)點(diǎn)；b）產(chǎn)生均勻分布的空間點(diǎn)作為吸引點(diǎn)（空心球），尋找以樹節(jié)點(diǎn)為球心，半徑為di的球體內(nèi)的吸引點(diǎn)，且這些吸引點(diǎn)到其他樹節(jié)點(diǎn)距離都比到該樹節(jié)點(diǎn)距離要大，并連接樹節(jié)點(diǎn)和吸引點(diǎn)形成多個(gè)向量，如圖2(b)所示；c）將各向量求和并規(guī)范化，樹節(jié)點(diǎn)到吸引點(diǎn)的向量用帶箭頭的線表示，虛線箭頭線表示各向量和，如圖2(c)所示；d）創(chuàng)建新的樹節(jié)點(diǎn)，并連接當(dāng)前樹節(jié)點(diǎn)和新樹節(jié)點(diǎn)，如圖2(d)所示，樹節(jié)點(diǎn)的位置和方向根據(jù)MTSP算法的步驟e)計(jì)算；e）尋找以新產(chǎn)生的樹節(jié)點(diǎn)為球心，dk為半徑球體內(nèi)的吸引點(diǎn)并刪除，如圖2(e)和(f)所示；f）對(duì)另一個(gè)初始的樹節(jié)點(diǎn)執(zhí)行c）~e）的操作；g）利用已經(jīng)產(chǎn)生的吸引點(diǎn)，依次對(duì)每個(gè)新產(chǎn)生的樹節(jié)點(diǎn)再執(zhí)行圖2(b)~(f)的操作，直到吸引點(diǎn)數(shù)為0或達(dá)到指定的迭代次數(shù)，最終將生成樹的圖形。

圖3中兩個(gè)圖都是主干為二分叉型，均勻分布的吸引點(diǎn)數(shù)為100，D=0.4，di=25×D，dk＝20×D時(shí)生成的樹。因?yàn)槲c(diǎn)是隨機(jī)生成的，所以在參數(shù)一定的條件下，也可以生成形態(tài)各異的樹木圖形。

4 實(shí)驗(yàn)結(jié)果分析

在Microsoft Visual Studio 2005平臺(tái)上，利用C++語言對(duì)提出的算法進(jìn)行實(shí)驗(yàn)，對(duì)圖1中所示的單軸分枝和合軸分枝也進(jìn)行了實(shí)驗(yàn)驗(yàn)證，生成的結(jié)果如圖4所示。本文提出的建模方法不僅可以生成單株樹木，還可以同時(shí)生成多株樹木，只需指定每株樹木的初始樹節(jié)點(diǎn)即可。圖4（e）即是同時(shí)生成兩株單軸分枝型樹木的圖形。

樹節(jié)點(diǎn)間的連接距離D是樹枝節(jié)間的長度，所以通過控制D的大小能控制樹枝的光順粗糙程度；通過控制影響距離di、刪除距離dk或吸引點(diǎn)的數(shù)量num，可以控制樹枝的稀疏茂密。限于篇幅，本文沒有給出具體的實(shí)驗(yàn)結(jié)果圖。

由于MTSP算法不是基于特定的產(chǎn)生式規(guī)則或初始表達(dá)式進(jìn)行遞歸迭代，而是每個(gè)節(jié)間的生成位置由初始隨機(jī)分布的空間點(diǎn)來決定，故克服了L系統(tǒng)、IFS和分形方法共同的不足之處——相似性太強(qiáng)、異性特征太弱。從以上的各生成圖形中還可以看出，該算法能生成單軸分枝樹、合軸分枝樹和假二叉分枝樹，而且形態(tài)各異。

5 結(jié)束語

本文提出的MTSP算法在指定樹木分枝類型基礎(chǔ)上，很簡便地生成相應(yīng)類型的樹木圖形。在相同的參數(shù)條件下，可生成形態(tài)各異的樹木外觀，很好地解決了基于自相似性進(jìn)行樹木建模的L系統(tǒng)、IFS和分形方法生成圖形規(guī)則性強(qiáng)、千篇一律的不足。該算法還克服了L系統(tǒng)、IFS和分形方法各參數(shù)的細(xì)微變化引起最終生成圖形巨大變化的缺陷。下一步的研究將基于此算法進(jìn)行外力作用下樹木的動(dòng)態(tài)模擬。

參考文獻(xiàn)：

［1］

潘云鶴，毛衛(wèi)強(qiáng).基于交互變形的樹木三維建模研究[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2001，13(11):1037-1041.

[2]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: 331-338.

[3]PRUSINKIEWICZ P， LINDENMAYER A. The algorithmic beauty of plants[M]. New York: Springer-Verlag， 1990.

[4]PRUSINKIEWICZ P， KARWOWSKI R， LANE B. The L+C plant modeling language[M]// VOS J. Functional-structural plant mode-ling in crop production.New York: Springer， 2007.

[5]DEKMO S， HODGES L， NAYLOR B. Construction of fractal objects with iterated function systems [J].Computer Graphics， 1985，19(3): 271-278.

[6]OPPENHEIMER P. Real-time design and animation of fractal plants and trees [J].Computer Graphics， 1986，22(4): 55-64.

[7]RODKAEW Y，CHONGSTITVATANA P，SIRIPANT S，et al.Particle systems for plant modeling[C]// Proc of PMA’03.Beijing:Tsinghua University Press and Springer， 2003: 210-217.

[8]TAKASHI I， SHIGERU O， TAKEO I. The sketch L-system: global control of tree modeling using free-form strokes[C]//Proc of the 6th International Symposium on Smart Graphics. 2006: 138-146.

[9]程學(xué)珍，曹茂永，徐小平.基于分形的自然景物描述方法研究[J].系統(tǒng)仿真學(xué)報(bào)，2007， 19(21): 4957-4959.

[10]趙慧蘭.基于分形幾何學(xué)的植物圖像計(jì)算機(jī)模擬[J]. 浙江師范大學(xué)學(xué)報(bào):自然科學(xué)版，2007， 30(3): 299-302.