基于八叉樹三維農作物葉片的體建模算法

林金花， 劉曉東， 李萬龍， 王 璐

（1．長春工業大學軟件職業技術學院，吉林長春 130012；2．西安交通大學電子與信息工程學院，陜西西安 710049）

0 引 言

我們一直尋求在三維虛擬環境中繪制出棉花葉片、玉米葉片、水稻植株乃至各種農作物形態比較好的方法，從以往經驗來說，利用計算機圖形學技術把農作物葉片的模型建造起來不是很困難的事情，但是，結合作物生長模型，將作物葉片的內部實體屬性（環境因子、三維紋理、顏色密度）描述成計算機可以控制的模型則比較困難。所以，在實現過程中必須采用一些簡化思想。

首先，采用八叉樹方法［1］實現三維作物葉片模型的體建模，該模型可以精確表示三維葉片內部所有點的幾何位置，這種點集拓撲體模型將葉片實體內部的屬性和結構看作三維實體占據的空間位置函數，由于體幾何模型構造方法簡單，容易離散化，所需計算及存儲均很少，使得三維作物葉片的形態建模得以精確控制。然后結合知識引擎組件對象驅動作物器官組件對象生長變化，使生長模型中的屬性描述與虛擬作物器官（葉片）組件分離，在生長模型腳本里定義作物生長的各種參數，知識引擎就根據這些參數來控制作物的具體生長。最后在進行虛擬試驗時，通過體模型控制作物生長所需元素的變化，實現農作物葉片的真實感建模。

采用體幾何模型來對作物葉片進行建模，由于體模型構造方法簡單，可以表示具有凹凸表面、橫截面變化連接以及旋轉體等，但是，對于作物葉片這種形態較不規則的實體，為了使得葉片體模型更加真實地擬合生長過程中的葉片變化形態，引入八叉樹剖分方法，將體模型剖分成一個個體元組成的集合，生成一個樹形結構，采用線性八叉樹鏈表存儲，通過知識引擎組件輸入葉片的屬性參數，驅動作物葉片的形態建模。

體建模與八叉樹技術的結合，實現了三維農作物葉片的生長形態建模，使得模型真實并且控制精確，基本滿足了虛擬作物可視化平臺實時性交互的要求。

1 基于八叉樹的葉片模型體元化

所謂多面體的體元化是把面圖形學中由邊界法表示的多面體轉換成體圖形學中的由若干個體元［2］（即附帶實體屬性空間分布數據的一個體單位）組成的一個多面體。采用八叉樹方法將用邊界法表示的葉片幾何模型轉換成三維體元模型，八叉樹的體元化即為面數據轉換成體數據的過程，這里采用十字鏈表結構以及八叉樹線性編碼來實現。

1.1 體元數據結構

為了使八叉樹剖分中的立方體與邊界面更加精確地逼近相交，首先將多面體的每個面都進行三角剖分，組成一張三角面片表，這是一張由三元組構成的二維鏈表，用來存放多面體每個面的三角面片屬性。然后根據三角面片屬性表生成一個由若干個體元組成的集合，也就是將具有樹形結構的三角面片鏈表（八叉樹）轉換為一種體元數據結構，采用十字鏈表結構來表示這種體元數據結構，每一個鏈表結點表示一個體元。最后采用線性八叉樹編碼［3］對體元鏈表進行編碼，即對每個結點進行統一的八進制編碼，可以節省內存空間，提高體繪制的索引速度，由此生成體建模所需的體元坐標。具體剖分過程如圖1所示。

圖1 八叉樹剖分流程圖

初始控制點決定了所生成模型的大致形狀，應該簡單并且特征突出。若控制點選取過多，就不能很好地體現整體變形簡單的優勢；若控制點選取過少，就很可能不能模擬出物體的特征，缺乏真實感。所以，要建立恰當的初始控制點集［4］，必須要對待建模物體進行很好的分析，用盡可能少的點集模擬出物體的大致形狀和主要特征。根據文中算法中的控制點必須是原始模型上的點，同時，對初始模型細分后要保存其控制點不變的特征，選用改進的Butterfly細分規則對原始模型進行細分，再應用文中算法進行變形。根據性能測試中原始模型在不同變形效果時作物模型的細致程度和繪制速度，取得合適的變形參數，使得最終模型的真實感和生成速度有較好的折衷。這里采用十字鏈表結構實現這種鏈表間的嵌套，體元數據結構如圖2所示。

圖2 體元數據結構

文中算法采用三角面片表示葉片模型的整個剖分過程，一方面為了實現整個三維環境下的可視化繪制，另一方面便于實現與作物其它器官部件的接口連接繪制。

具體的體元數據結構如下：

typedef struct VoType｛

VType vbox；／／體元類型

Vertex vo；／／體元坐標

char＊code；／／八叉樹線性編碼

int l；／／體元分辨率l＝2i，i為剖分次數

RGB color；／／體元顏色及對比度

struct VoType＊next；／／指向下一個體元

struct VoType＊child；／／指向子體元鏈表

Tlist＊Trintermesh；／／相交三角面片指針鏈表［5］

｝VoType；

1.2 八叉樹體元化算法

具體的八叉樹剖分算法如下：void Alloctree：：make＿tree（TList＊interTrmesh，TList＊primitive，octreeType＊tree，int depth）

｛

int i，j；

switch（classify（interTrmesh，primitive，tree））

／／判斷當前八叉樹結點，是否與其父結點相交的三角面片相交，從而得出其是No1，No2，No3結點。

在八叉樹剖分算法中，最關鍵的是判斷出哪些立方體與邊界面相交，為了使利用立方體逼近的邊界面更為光滑，立方體應越小越好，但是這樣會使空間與時間復雜度增加，因此，在邊界面上的八叉樹剖分中采用提高分辨率的方法，同時保存原有體元結點，進而實現十字鏈表形式的八叉樹結構［6］。

2 葉片生長模型的構建

生長模型就是將作物及其環境因子作為一個整體，應用系統分析的原理和方法，對作物的生育、生長的生理過程及其環境因子關系的實驗數據加以整合概括和量化分析，建立相應的數學模型。將抽象出來的具有實際意義的公式、參數、變量等用XML語言包裝起來，形成生長模型腳本［7］，知識引擎就可以根據這個腳本來控制作物的生長。

2.1 知識引擎組件結構

采用知識引擎組件對虛擬作物進行生長驅動，在生長模型腳本里定義作物生長的各種參數，知識引擎就根據這些參數來控制作物的具體生長。知識引擎組件結構如圖3所示。

圖3 知識引擎結構圖

2.2 生長模型的建立

生長模型的XML腳本文件描述了環境、作物先天因素等數據與作物生長形態變化（時間與幾何）之間的關系，知識引擎組件對XML腳本［8］進行分析，從中提取出一系列具有時序性的數值運算和邏輯運算，使系統中可驅動作物器官組件對象的屬性發生改變。從技術角度來講，就是通過農學知識把影響作物生長的各種因素經過一系列演算，生成作物各個階段的生長量，然后把這個生長量作為作物器官對象的控制器官形變的屬性值，驅動器官的生長。

在知識引擎組件與可驅動組件（生長模型）之間建立驅動關系的結構示意圖，如圖4所示。

圖4 知識引擎與葉片組件之間建立子屬性關系

知識引擎組件以索引屬性的形式將一個驅動組件對象放于集合列表中，從而保持了對可驅動組件一對多的關聯關系［9］。

3 三維葉片模型的動態體繪制

采用八叉樹結構表示模型的內部屬性變化，用知識引擎驅動這種變化［10］，建立作物的動態模型。由于采用八叉樹將多面體剖分為體元，模型實體的空間信息已經保存在混合數據結構中，并能夠方便進行查找索引，因此，采用體元組成繪制算法。

具體算法如下（以棉花葉片為例）：

1）建立模型的生長曲線，對多面體模型進行面繪制。棉花葉片形態上最大的特點是邊緣呈皺褶狀。我們讓葉片兩邊的控制點隨著皺褶的變化呈現高低交錯的情況。葉片中間是主脈，可用葉片的空中伸展曲線來模擬它［11］。

2）用知識引擎技術驅動作物葉片的動態建模，選擇相關性體元進行體繪制的象素，可以在繪制過程中組合原先幀緩存中的屬性信息。

3）重新定義一個統一的分辨率進行再剖分，實現體元形狀相同、大小不一的體元模型。

4 實驗結果

以棉花和玉米葉片為例來驗證文中算法。在顯示的時候把葉鞘與葉片設置為屬于同一個體元集合，因此葉片在u方向（局部坐標）的控制點個數和葉鞘必須相等，最終葉片的控制點設定為兩邊各1組和中間緊密的5組，共7組。傳統算法是將模型剖分成均勻大小的體元，文中算法把模型剖分成不同大小的體元集合，以棉花葉片為例，不同算法的棉花葉片體建模效果如圖5所示。

圖5 不同算法的棉花葉片體建模效果

傳統算法的空間開銷為2 221個體元，效果見圖5（a）。文中算法空間開銷為5 272個體元，效果見圖5（b），顯示效果真實感較好，如果采用傳統算法要達到相同效果，則體元數要達14 760個。可見文中算法可以在較小的空間開銷下，達到較好的顯示效果。

玉米葉片的建模效果［12］如圖6所示。

圖6 文中算法繪制的玉米葉片模型

5 結 語

三維實體的體建模技術是體圖形學的重要組成部分，傳統的體建模方法僅適用于均勻大小的體元模型［13］，而對于農作物葉片模型，其葉片紋理、旋轉角度以及顏色分布等內部屬性受環境因子的影響，使得葉片模型應具有不規則性。為了解決這一問題，文中引入八叉樹剖分技術將葉片模型剖分成不均勻的體元模型，生成一個十字鏈表結構，用八叉樹體元實現葉片模型的不規則顯示，通過知識引擎組件驅動作物葉片的形態建模。實驗表明，文中算法對作物葉片整體建模效果較好，適用于虛擬作物實驗系統的開發與應用。

［1］ Stachniak S，Stuerzlinger W．An algorithm for automated fractal terrain deformation［J］．Computer Graphics and Artificial Intelligence，2005，5：64－76．

［2］ Kruer J，Kipfer P，Ondratieva P，et al．A particle system for interactive visual－ization of 3Dflows［J］．IEEE Transactions on Visual－ization and Computer Graphics，2005，11（6）：744－756．

［3］ Su Z X，Li B J，Liu X P，et al．Rapid evaluation ofregular quad－mesh interpolatory subdivision surfaces based on parametric decomposition［J］．Journal of Software，2007，8：18－25．

［4］ Kruer J，Kipfer P，Ondratieva P，et al．A particle system for interactive visual－ization of 3Dflows［J］．IEEE Transactions on Visual－ization and Computer Graphics，2005，11（6）：744－756．

［5］ Hu S M，Zhang H，Tai C L，et al．Direct manipulation of FFD：Efficient explicit solutions and decomposible multiple point constraints［J］．The Visual Computers，2010，17（6）：370－379．

［6］ Huijing Zhao，Ryosuke Shibasaki．Reconstructing a textured CAD model of an urban environment using vehicle－borne laser range scanners and line cameras［J］．Machine Vision and Applications，2003，14（1）：222－225．

［7］ 胡小紅，周旺，黃臨平，等．三維散亂點的八叉樹建模及程序實現［J］．東華理工學院學報，2007，5（6）：41－43．

［8］ 洪雄，張建勛，曾慶森．基于似三棱柱構模的三維地質體的剖切［J］．計算機工程與技術，2008，15（5）：273－275．

［9］ 連紀恩，張鳳軍，付永剛，等．虛擬環境下基于語義的三維交互技術［J］．軟件學報，2006（7）：1535－1543．

［10］ 王亮．虛擬環境中基于語義的三維交互技術研究及應用［D］：［碩士學位論文］．合肥：中國科技大學，2008．

［11］ 曹彤，劉臻．用于建立三維GIS的八叉樹編碼壓縮算法［J］．中國圖象圖形學報，2002，7（A1）：50－54．

［12］ 呂廣憲，潘懋，王占剛，等．面向體數據的虛擬八叉樹模型研究［J］．計算機應用，2006，26（12）：1535－1543．

［13］ 林金花，李萬龍，王璐，等．一種基于B－樣條曲面控制的自由變形方法［J］．長春工業大學學報：自然科學版，2011，32（6）：574－580．