范曾，張建偉

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

幾十年來，復(fù)雜植物的幾何建模一直是計(jì)算機(jī)圖形學(xué)面臨的一個(gè)挑戰(zhàn)。其中，真實(shí)、實(shí)時(shí)的樹木建模與渲染是一個(gè)相當(dāng)困難的部分。因?yàn)闃淠臼菓敉鈭?chǎng)景的主要組成部分，并且具有復(fù)雜的拓?fù)浣Y(jié)構(gòu)和幾何形狀，需要大量的圖元才能形成令人信服的視覺效果。樹冠內(nèi)樹枝和樹葉的重疊交錯(cuò)，以及樹木在結(jié)構(gòu)上的自相似性，使樹木模型的生成變得復(fù)雜。

為了避免這些困難，此類三維模型的生成通?；诔绦蚍椒ǎ鏛indenmayer 系統(tǒng)[1]，該系統(tǒng)通過形式語言的描述來創(chuàng)建模型，見圖1。程序樹模型在計(jì)算機(jī)圖形學(xué)中很受歡迎，因?yàn)樗鼈兡軌驈囊唤M輸入?yún)?shù)生成各種輸出樹，并模擬植物與環(huán)境的交互，以便在虛擬場(chǎng)景中真實(shí)地放置樹木。

不幸的是，要模擬特定的樹或給定的樹種，通常必須手動(dòng)地調(diào)整許多參數(shù)。這使得建模的工作人員以及藝術(shù)家們背負(fù)著很大的創(chuàng)作負(fù)擔(dān)。并且，大規(guī)模植物的幾何復(fù)雜性仍然超過了當(dāng)前計(jì)算機(jī)硬件的渲染能力。為了解決這個(gè)問題，研究者們已經(jīng)開發(fā)了幾種策略：①簡(jiǎn)化網(wǎng)格以減少多邊形的數(shù)量；②用更基本的幾何體（如點(diǎn)、線、圓柱體）替換復(fù)雜多邊形；③用紋理或billboard 替換3D 幾何體。這些方法都有效地提高了繪制大范圍森林的效率。在飛行模擬機(jī)中，我們的樹木模型是按照植物學(xué)規(guī)則構(gòu)建的，它反映了植物的生長(zhǎng)過程及其空間占有率。其中，樹木的樹枝由非常簡(jiǎn)單的圓柱體表示，足以用于沉浸式的視景視圖中。

圖1 Lindenmayer系統(tǒng)

1 相關(guān)工作

經(jīng)典的樹建模是基于規(guī)則或使用建模過程的。雖然Prusinkiewicz 和Lindenmayer 的L 系統(tǒng)[1]中的形式規(guī)則適用于初始狀態(tài)，但大多數(shù)過程方法使用參數(shù)化算法，如Oppenheimer[2]、de Reffye[3]、Holton[4]、Weber 和Penn[5]。這些算法也對(duì)規(guī)則進(jìn)行編碼，但用的是更具體的概念。Lintermann 和Deussen[6]的xfrog 系統(tǒng)試圖將這兩種方法結(jié)合起來。

在經(jīng)典的L 系統(tǒng)中，規(guī)則基礎(chǔ)必須由用戶編寫。由于規(guī)則作用于局部，所以值的細(xì)微差異可能會(huì)導(dǎo)致整體形狀的變化。這樣的方式使得建模非常麻煩。從那時(shí)起，人們提出了L-系統(tǒng)的各種擴(kuò)展，例如Prusinkiewicz 和Lindenmayer[7]的 參 數(shù) 化、Mech 和Prusinkiewicz[8]的開放式，和Prusinkiewicz 等人[9]的微分L 系統(tǒng)。這些擴(kuò)展可以創(chuàng)建各種效果，但也會(huì)產(chǎn)生附加參數(shù)。Prusinkiewicz 等人[10]為L(zhǎng) 系統(tǒng)提供了一個(gè)建模接口，以增強(qiáng)建模的簡(jiǎn)便性，但仍有大量參數(shù)需要用戶定義。

程序性方法通常僅限于產(chǎn)生數(shù)量有限的形狀。它們還可以限制用戶可調(diào)參數(shù)的數(shù)量。然而，隨著模型復(fù)雜性的增加，這個(gè)數(shù)量也會(huì)增加。雖然Oppenheimer[2]只使用了一些基本參數(shù)，但后來的方法，如Weber 和Penn[5]提出的方法有幾十個(gè)參數(shù)。

在xfrog 系統(tǒng)中，使用一個(gè)簡(jiǎn)單的規(guī)則系統(tǒng)來組合過程元素，這樣可以更快地進(jìn)行建模。但是，參數(shù)的數(shù)量仍然很大。Ijiri 等人[11]使用基于植物學(xué)規(guī)則的交互式編輯器來創(chuàng)建植物模型。雖然這些編輯允許高效地制作花和葉序，但在制作復(fù)雜樹木方面并不出彩。Okabe 等人[12]提出了一種基于草圖創(chuàng)建樹木的接口。在這種方法中，用戶可以繪制樹骨架的輪廓及其形狀。然而，許多參數(shù)必須調(diào)整以達(dá)到特定的物種。

基于粒子的方法[13]在與自然生長(zhǎng)相反的方向構(gòu)造樹骨架。最初，粒子是在樹冠（球形或圓錐形）的樹葉位置生成的。模擬流動(dòng)的方法是，以小步重復(fù)移動(dòng)粒子到其最近的鄰居和根，當(dāng)粒子非常接近時(shí)合并粒子。獲得的粒子軌跡形成樹骨架，隨后用于擠出可渲染幾何體。為了將粒子引導(dǎo)到地面，Rodkaew 等人使用靜態(tài)目標(biāo)點(diǎn)和最近鄰吸引力，這會(huì)在粒子軌跡中產(chǎn)生急轉(zhuǎn)彎，并嚴(yán)重限制建模的通用性。

粒子流算法對(duì)于從運(yùn)動(dòng)捕捉到的樹枝尖端[14]或激光掃描[15]重建樹也很有用。Xu 和Mold[16]提出了一種自頂向下的方法來構(gòu)造不規(guī)則樹模型。一個(gè)加權(quán)圖是由一組隨機(jī)生成的點(diǎn)在一個(gè)用戶繪制的樹shell 的旋轉(zhuǎn)中構(gòu)造的，其中一個(gè)點(diǎn)被指定為根節(jié)點(diǎn)，而其他節(jié)點(diǎn)的隨機(jī)選擇則指定端點(diǎn)。找到從各個(gè)端點(diǎn)到根節(jié)點(diǎn)的最短路徑，并用于構(gòu)造樹骨架。此過程將重復(fù)多次，其端點(diǎn)來自上一次迭代服務(wù)的端點(diǎn)在下一次迭代中。這種方法比粒子流算法需要更多的內(nèi)存，因?yàn)樵诿看蔚卸紩?huì)構(gòu)造出一個(gè)具有多個(gè)節(jié)點(diǎn)甚至更多邊的新圖。在他們使用引導(dǎo)向量的方法[17]的后期擴(kuò)展中，作者使用了單個(gè)圖，但是高空間復(fù)雜度仍然是該方法的主要限制。

Reche Martinez 等人[18]描述了一種非常精確但復(fù)雜的基于圖像的建模方法。在這種方法中，使用一組注冊(cè)的照片來確定給定樹的體積形狀。體積被分成單元塊，對(duì)于每個(gè)單元塊，用一組紋理計(jì)算出有效的視覺表示。完整的紋理集代表了樹。然而，這種方式需要數(shù)十兆字節(jié)的紋理空間。另外，在不同的光照條件下也不容易顯示樹，因?yàn)楣庹找呀?jīng)包含在紋理中。

另一類不同的樹木合成方法是資源競(jìng)爭(zhēng)（如光、空氣、水等）視為樹木生長(zhǎng)的驅(qū)動(dòng)機(jī)制。其中提出基于局部生長(zhǎng)條件的模型結(jié)構(gòu)自組織生長(zhǎng)是Pa?ubicki 等人[19]的關(guān)鍵貢獻(xiàn)。

2 算法概述

本文的樹木建?；赑a?ubicki 等人的自組織建模方式，將樹描述為一個(gè)分層組織的模塊化結(jié)構(gòu)。一片或多片葉子附著在莖上的那一點(diǎn)叫做節(jié)。莖在兩個(gè)節(jié)之間的部分是節(jié)間。在每片葉的腋部形成一個(gè)側(cè)芽，即支撐葉的莖和葉柄之間的有角空間。一個(gè)節(jié)間與附生的葉和芽形成一個(gè)變位異構(gòu)體。

一個(gè)芽可能有四種不同的命運(yùn)：產(chǎn)生一個(gè)新的變位異構(gòu)體，產(chǎn)生一朵花，保持休眠（保持將來生長(zhǎng)的可能性）或死亡。變位異構(gòu)體可以連續(xù)或有周期地產(chǎn)生。溫帶氣候樹木的生長(zhǎng)是有周期性的，受季節(jié)循環(huán)的調(diào)節(jié)。在一次生長(zhǎng)（溫帶氣候樹木的春天）中產(chǎn)生的一系列變位異構(gòu)體形成一個(gè)嫩芽。芽軸由位于芽端的頂芽產(chǎn)生。主干由幼苗的頂芽發(fā)育而來，軸序?yàn)?。軸序?yàn)閚 的側(cè)芽生長(zhǎng)之后將會(huì)成為它產(chǎn)生的軸序+1 的頂芽。

生長(zhǎng)方式分為兩類：

（1）連年持續(xù)產(chǎn)生的嫩枝呈線性排列，形成單枝分枝結(jié)構(gòu)。

（2）樹木發(fā)育的主要推力轉(zhuǎn)移到側(cè)枝，頂芽產(chǎn)生一朵花或死亡。這樣將會(huì)導(dǎo)致共軸分枝。新的分枝可以在同一季節(jié)產(chǎn)生（即與支撐它們的莖形成的同一季節(jié)）。

3 建模方式

通過模擬樹木的生長(zhǎng)過程，創(chuàng)建一個(gè)樹形結(jié)構(gòu)。

3.1 環(huán)境輸入計(jì)算

本文將樹木生長(zhǎng)所需要的環(huán)境資源（如陽光、水分、空氣等）用隨機(jī)生成的3D 資源點(diǎn)表示。在程序運(yùn)行之處，用C++的隨機(jī)函數(shù)生成指定數(shù)量的3D 資源點(diǎn)。隨后，將資源點(diǎn)構(gòu)建為KD-Tree。我們假設(shè)每個(gè)芽被一個(gè)半徑為r 的球形占據(jù)區(qū)所包圍，并且每個(gè)芽有一個(gè)感知角度為θ、距離為R 的圓錐形感知體。在每一次生長(zhǎng)迭代的過程中，根據(jù)構(gòu)建的KD-Tree，從3D資源點(diǎn)集中刪除任何芽的占用區(qū)域內(nèi)的點(diǎn)，然后芽再去爭(zhēng)奪剩余的資源點(diǎn)。用這種方式計(jì)算每個(gè)芽周圍空間的可用性，同時(shí)依據(jù)空間定殖的方法計(jì)算芽的最佳生長(zhǎng)方向。其中，若芽周圍空間的可用性為0，則芽不生長(zhǎng)；若芽周圍空間的可用性為1，則芽可按照計(jì)算得出的最佳生長(zhǎng)方向生長(zhǎng)。

3.2 芽命運(yùn)計(jì)算

在這個(gè)階段，通過上一節(jié)中計(jì)算得到的芽周圍空間的可用性決定芽的命運(yùn)。由于目前尚不清楚自然界的根尖控制是通過資源競(jìng)爭(zhēng)、激素控制還是二者都有，這里采用Pa?ubicki 等人實(shí)現(xiàn)的擴(kuò)展模型進(jìn)行資源分配。

該模型通過控制生長(zhǎng)誘導(dǎo)資源向芽的分配來調(diào)節(jié)分枝，通過考慮分支點(diǎn)處（即芽）接收到的資源點(diǎn)數(shù)量分配縱向流動(dòng)的資源。該算法氛圍兩個(gè)步驟：①到達(dá)芽的資源是流動(dòng)的，累積值存儲(chǔ)在節(jié)間。②累積值決定了該過程要分配的資源量：Resbase=αCbase，其中α是比例系數(shù)。到達(dá)分支點(diǎn)的資源按照公式（1）分布在連續(xù)的主軸Cm和橫向分枝Cl之間。

其中，ε∈[0,1]控制資源是否偏向主軸（ε＞0.5），還是偏向側(cè)枝（ε＜0.5）。到達(dá)一個(gè)芽的資源量Res 的整數(shù)部分決定了這個(gè)芽產(chǎn)生的變位異構(gòu)體的數(shù)量：n=。

3.3 增加新芽

默認(rèn)情況下，新幼芽是按芽所指的方向生長(zhǎng)的。頂芽的方向與它的支撐節(jié)間的方向一致。側(cè)芽的方向由葉序和芽與親本節(jié)間的分枝角度決定。形成一個(gè)新芽的連續(xù)變位體的方向受到兩個(gè)因素的影響：由環(huán)境決定的最佳生長(zhǎng)方向和重力因素。因此，變位異構(gòu)體的實(shí)際生長(zhǎng)方向計(jì)算為上述三種方向的加權(quán)和。

隨后，通過計(jì)算得出該芽在一次迭代生長(zhǎng)之后的半徑與長(zhǎng)度，按照相應(yīng)比例對(duì)替代樹枝的圓柱體進(jìn)行放縮，可得到新生長(zhǎng)出來的樹枝。

4 程序效果

該程序運(yùn)行的界面效果如圖2、3 所示。點(diǎn)擊“Add Attr Pt Cloud”按鈕生成隨機(jī)的3D 資源點(diǎn)，繪制在窗口上，見圖2。

圖2 隨機(jī)資源點(diǎn)圖示

隨后設(shè)置不同參數(shù)（如樹枝半徑、迭代生長(zhǎng)次數(shù)等），點(diǎn)擊“Iterate Tree”按鈕，每次點(diǎn)擊樹木會(huì)生長(zhǎng)一次，如圖3。

圖3 動(dòng)態(tài)生成樹

5 結(jié)語

經(jīng)過幾十年的發(fā)展，森林的建模算法已經(jīng)有了巨大的進(jìn)步。本文通過研究最近30 年內(nèi)樹木的建模方式，對(duì)各種方式進(jìn)行分析，結(jié)合飛行模擬視景的實(shí)際情況，基于自組織思想的建模方法，并利用OpenGL、Dear Imgui、glfw 以及glad 庫編程實(shí)現(xiàn)了單顆樹木建模的動(dòng)態(tài)演示。該應(yīng)用程序具備一定的可擴(kuò)展性。然而，由于飛行模擬機(jī)這類大規(guī)模的視景需要在短時(shí)間內(nèi)生成成千上萬棵樹，一個(gè)可行的優(yōu)化改進(jìn)方向是利用OpenGL 的Compute Shader 進(jìn)行并行化處理。針對(duì)繪制效率的問題，還需要繼續(xù)改進(jìn)研究。