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

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

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

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

文章編號：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

對樹木形狀的三維建模一直是計算機(jī)圖形學(xué)領(lǐng)域的一個研究熱點，大量學(xué)者對此進(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ī)則來生成圖形的，對一種樹的產(chǎn)生式規(guī)則很難應(yīng)用到另一種樹上；而IFS和分形方法中，局部參數(shù)的細(xì)微改變將引起整個結(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ī)分布點按一定策略連接實現(xiàn)的，具體的算法根據(jù)英文的首字母命名為MTSP (modeling trees with space point)。

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

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

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

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

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

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

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

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

d）對每個樹節(jié)點t的吸引點集合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é)點tn并且連接t和tn，tn到t的距離d(tn，t)=N(Vt，t)×D，方向為向量N(Vt，t)的方向。

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

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

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

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

3.1 方法概述

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

3.2 方法實例

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

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

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

4 實驗結(jié)果分析

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

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

由于MTSP算法不是基于特定的產(chǎn)生式規(guī)則或初始表達(dá)式進(jìn)行遞歸迭代，而是每個節(jié)間的生成位置由初始隨機(jī)分布的空間點來決定，故克服了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)行外力作用下樹木的動態(tài)模擬。

參考文獻(xiàn)：

［1］

潘云鶴，毛衛(wèi)強(qiáng).基于交互變形的樹木三維建模研究[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，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é)報，2007， 19(21): 4957-4959.

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