基于分形生成图的树木几何建模方法
2010-09-07逯燕玲解文彬
逯燕玲, 解文彬
(1.北京联合大学应用文理学院 北京100191; 2.北京市石景山区教育委员会会计核算中心网络部 北京100043)
基于分形生成图的树木几何建模方法
逯燕玲1, 解文彬2
(1.北京联合大学应用文理学院 北京100191; 2.北京市石景山区教育委员会会计核算中心网络部 北京100043)
利用树木的形态结构特征,采取分形迭代系统构建树木的整体结构形态.用分形元和生成图技术对树木三维形态数据进行抽象分析和记录,并用参数化曲线模拟树木枝条的自然弯曲状态以及在弯曲过程中枝条半径的变化,以实现树木形态结构的三维可视化.
树木几何建模;迭代函数系统;分形元;生成图;参数化曲线
0 引言
虚拟树木就是应用计算机以可视化方式模拟树木在三维空间中的形态结构变化规律及生长发育过程,已成为数字林业信息可视化研究热点[1-3].与传统的生产模拟相比,它具有定量、直观、精细、可以缩短研究周期等特点.但树木可视化模拟一直是个难点问题,这主要是由于:①树木的几何结构非常复杂,这给树木三维数据的获取、几何建模及真实感绘制都带来了很大困难;②树木不仅具有复杂的几何结构,而且具有丰富的可视化细节,例如树皮表面的凹凸不平、树叶的半透明、复杂的阴影效果等,这使得真实表现树木并非易事.
树木的形态结构在其生长过程中起着重要作用,它直观反映了树木生产发育状况,是进行科学决策的重要因子[4],而在树木几何建模的过程中,其形态结构也是真实地模拟树木枝条的自然弯曲状态的一个重要因素.在传统的建模方法中,树枝的形状用圆台或圆柱表示,绘制出的树的枝干直上直下,效果很生硬,而真实树木的主干和主要枝条都是弯曲的,其弯曲程度各异.本文通过观测分析树木的几何结构特征,构造出描述树木三维形态的几何模型,以openGL三维图形为可视化平台,采用M icrosoft Visual C++计算机编程语言,用分形迭代系统构建树木的整体结构,用分形元和生成图技术对树木三维形态数据进行抽象分析和记录,并通过Bezier这种基于控制点的自由曲线描述枝条的自然弯曲状态,从而实现了树木形态结构的三维可视化.
1 树木的形态结构模型
树木的形态结构遵循自相似规律,即局部与整体相似.树木的结构模型一般包括3个方面的信息[5]:描述植物由几个成分或单元构成的单元信息,描述各单元形状和空间位置的几何结构信息和描述各单元在物理上的连接方式的拓扑结构信息.几何结构模型是指对植物整体或部分器官组成结构的三维信息描述.拓扑结构模型是植物建模中的最基本模型,主要用于描述植物离散结构单元之间的连接关系,并可以通过抽象的数学语言反映出植物的生长阶段.
本文根据树木的形态结构特征,抽象出如图1所示的树的基本形态结构模型,树木的三维形态主要由主干、分枝和树叶决定.树木形态结构的主要构件是枝条,其在树干上分枝的角度、长度和级数等是决定分枝空间格局以及树冠形态的关键因素.根据其层次的不同又将枝划分为一级枝、二级枝和三级枝.
2 树木的整体结构建模
树木形态结构的自相似性使得分形技术可以成功应用于树木的计算机建模过程中.所谓分形[6],在数学上是指具有无限的细节、自相似等性质的一类图形.迭代函数系统(IFS)[7]属于一种分形构形系统,它借助于计算机强大的迭代计算能力,将自相似性、层次的多重性和不同层次的规则统一性应用于计算机图形领域,可以产生许多具有无穷细节的、精致纹理的图形.尤其是在树木形态模拟方面,IFS方法可以表现出树木整体形态的不规则性以及整体与局部细节的自相似性,较之以规则形态构图的传统方法更具优势.IFS算法有2种[8]:①确定性迭代算法,指用以迭代的规则是确定性的,由一组仿射变换构成.确定性迭代算法总能够产生清晰完整的图形,可以对细节精确控制,缺点是浪费存储空间.②随机性迭代算法,不需要占用很大的存储空间,易于实现,但需要规定一个迭代的最大次数.本文采用IFS的随机迭代法来构建树木模型.
树木的每一级侧枝螺旋状依次着生在上一级枝干的结点处,在几何造型上与上一级枝干相似,可以用递归算法构造树木模型.在递归过程中不断修改其属性值,每次新生枝条产出之前,引入随机因子,用于控制新生枝条是否分枝及分枝的角度和长度,使得树枝的倾斜度和长度产生随机变动.参数dep th用于控制递归的深度,图2为dep th取不同值时由随机迭代算法生成的树模型,其树枝的形状在此用圆柱表示.
3 弯曲枝条建模
观察图2,用圆台表示树干的方法使整个树体形态较自然树体形态“笔直”,不能体现自然树干的随机弯曲.模拟植物枝条的自然弯曲状态是直观形象地再现植物形体的重要内容.弯曲树枝光滑连续,采用Bezier曲线来绘制是一种很好的解决方法,它具有良好的受控特点,只需要改动几个控制点就能重新得到一个曲线,能很方便地找到模拟树枝弯曲的近似曲线.
3.1 Bezier曲线的数学表述
Bezier曲线是一种外形可以构成控制多边形的曲线,给定空间n+1个点p0,p1,…,pn,称下列参数曲线为n次的Bezier曲线:
其中,Cin是二项式系数级n!/[i!(n-i)!],Bi,n(t)称为伯恩斯坦基底函数,满足
折线P0P1,P1P2,…,PnP0构成该曲线C(t)的控制多边形,P0,P1,…,Pn各点为C(t)的控制顶点.本文采用二次Bezier曲线来描述拟合枝条曲线,当n=2时,
因此,二次Bezier曲线对应一条有3个控制点P0,P1,P2,起点在P0,终点在P2处的抛物线.
3.2 计算二次Bezier曲线的控制点
要拟合出枝条曲线,关键是确定控制点P0,P1,P2的坐标,为控制点P0取定一个坐标值,为了计算方便,定为(0,0,0),P2点的坐标设为(x2,y2,0),树木的主干与z轴平行,控制点P0到P2的直线距离以及侧枝与主干间的夹角可通过测量得到,分别用参数L和α表示,可通过式(5)求出控制点P2的坐标,
控制点P1的坐标设为(x1,y1,0),将P0,P1,P2的坐标代入二次Bezier曲线的公式,则曲线上任一点的坐标可由式(6)表示为
其中,i=1,2,…,N,N表示将枝条曲线平均分段后的段数,t=i×dt,dt为相应的步长.
根据式(6),当t从0到1变化时,将已求出的x2,y2的值代入,可得到枝条曲线上N个点T0,T1,…, TN的用x1,y1表示的坐标,再由两点间的距离公式,可由式(7)求出枝条曲线上任意相邻两点间的距离为
因此枝条曲线的长度PS可近似表示为
式(8)是由参数x1,y1表示的式子,枝条曲线的长度PS可从实际测量中得到,所以可根据此式求出控制点P1的坐标.由控制点P0,P1,P2的坐标,可以拟合出枝条曲线.在IFS中使用已拟合出的枝条曲线,建立起树木的结构骨架,如图3所示,树木的枝条有了一定的弯曲效果.
3.3 基于分形元和生成图技术的数据抽象
将图3中的树木结构骨架图转换为树的分形元和生成图,如图4所示.
其中,除终止结点(A4)外,其余各结点之上都含有分支.例如图4(a)中:A0结点对应A0-A4分支,A1结点对应A1-B分支,A2结点对应A2-C分支,A3结点对应A3-D分支.可以用结点A1代表其所对应的分支A1-B,并对其赋予该分支所具有的特征参数长度L和夹角tanα值,作为分支A1-B的权值.同理,结点A2代表其所对应的分支A2-C,并对其赋予该分支所具有的特征参数长度L和夹角tanα值,作为分支A2-C的权值;结点A3代表其所对应的分支A3-D,并对其赋予该分支所具有的特征参数长度L和夹角tanα值,作为分支A3-D的权值.由此,可以得到一个树形拓扑结构图G=
3.4 描述枝干的广义圆柱体
树木的枝条不仅具有弯曲状态,而且在弯曲的过程中,枝条的半径不断变化,本文采用横截面直径变化的广义圆柱体来描述树木的枝条.广义圆柱体是以三维空间曲线为轴的立体,轴上任意一个点都定义一个封闭的截面.
对于已经拟合出的枝条曲线,t从0到1变化得到曲线上的N个点,对任意点Ti(i=1,2,…,N),过该点的切线可以表示为
以插值多项式近似代替函数,以插值多项式在结点上的导数值近似代替函数在结点上的导数值,利用该方法产生的微分与用公式求出的微分几乎一致.在实现过程中,将已经拟合出的枝条曲线均匀分段,用变量DuanShu表示所分段数.通过求出的切向量及指定的半径Ri,可以计算出封闭截面圆上均匀分布的轮廓点的坐标,用变量DianShu表示每一截面圆上轮廓点的个数.为了更真实地表现枝条由底端到末梢由粗变细的状态,可以使半径Ri逐渐变小,绘制过其他N-1点的截面圆上分布均匀的轮廓点的坐标,将计算出的坐标值存入三维数组Cylinder[DuanShu][DianShu][3]中,再依次将相邻的4个点用四边形连接,图5为曲线分段数及轮廓点个数分别取不同值时所绘制出的广义圆柱体.
在程序中,将Bezier曲线分为120段,即取DuanShu为120,每一截面圆上取60个轮廓点,即DianShu为60,枝条的弯曲状态自然,计算机的运算速度比较理想.
将已经建好的树木枝干运用到分形迭代系统中,可以建立树干弯曲状态自然的树木形态模型,如图6所示.
4 结论
观察图7可以发现,用圆柱来绘制的树的枝干直上直下,效果很生硬,不能体现自然树干的随机弯曲.基于控制点变化的Bezier曲线能较好地模拟枝条自然弯曲和光滑连续的状态,构形真实、灵活,而且用较少的具有农学意义的参数就可描述枝条曲线形态,易与树木的形态结构模型相结合.
树木的自然形态结构虽然复杂多变,但都具有统计意义上的自相似性,其每一部分都相似于整体.本文基于图论理论,根据树木形态学原理和计算机图形学技术,抽象出树木的形态结构模型;采用分形技术建立树木的整体结构,通过引入随机因素和控制迭代概率来自由改变树木的形态;并使用Bezier曲线控制枝条的弯曲状态,建立了呈现自然弯曲状态的树干,树形态其效果逼真,基本上与自然状态下的树一致.
图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] 雷相东,常敏,陆元昌,等.长白落叶松单木生长可视化系统设计与实现[J].计算机工程与应用,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].北京:清华大学出版社,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].中南林业调查规划,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-),女,副教授,硕士研究生,主要从事离散数学、系统工程及计算机网络技术研究,E-mail:yanling@ygi.edu.cn.
