（管理科学与工程专业论文）树的三维建模研究.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得( 注：如没有其他需要特别声明的，本栏可 空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：像 茬导师橼验州 j 签字日期：2 0 0 4 年年月2 , 2 - - 日签字日期：20 0 4 年拿月“日 摘要 近十年自然景物模拟是计算机图形学研究的热点，其基本目标是利用计算机 系统尽可能真实地再现大自然巧夺天工的造型，如地貌、海岸、树木、草丛、云 彩等大自然中的不规则物体。其中对于树和其他植物的三维建模问题的研究更是 热点中的热点，近几年在国内外期刊出现大量相关论文，提出了许多可以借鉴的 简单、有效方法。本文首先对一些经典的解决方法进行综述，主要包括林氏系统 和迭代函数系统，以及基于此类算法的优化、推广和补充方案。 l 系统和i f s 都是单纯利用分形结构实现树的造型。这类方法的优点是使用 参数较少，数学形式比较优美，缺点是生成的造型过于呆板，缺乏生动性，且不 易控制，即从初始参数无法估计或想象出最终产生的造型，最终造型对初始参数 的变化也过于敏感。 本文首次提出了一种利用动力学系统建立的基于分形的树的三维建模方法。 树形态具有典型的分形特征和随机性，其形成受内在基因和外在环境因素影响。 文本通过一个包含质量、力、速度和能量的分形分布等因素相互作用的动力系统， 运用一组非常直观的参数集合描述了树的三维造型，并给出了生成姿态各异的树 的三维建模算法。 享李母学印科的；维建攀方荤，旱科形零的自巷分形结构与槔于 l 树车长昀动 力幂筝绎令的产物，与摹他攥犁布荤胡毕，皋市挚母刨章a 文本提出的算法通过a u t o c a d 的v b a 实现，实际效果表明本模型不仅可行 而且效果很好。 本模型最大的优点是可以通过力( 内力和外力) 的作用，非常直观地控制树 形态的分形结构。我们知道自然界中的树形态是在基本形态一致的基础上千变万 化的，构造树形态的模型既要保证树的基本形态，又要能够在基本形态上变化。 树的基本形态是通过分形机制保证的，而在变化方面，传统方式是采用随机过程。 通过仔细观察千姿百态的树形态，我们可以发现，虽然局部的变化没有什么规律， 基本上是完全随机的，但整体上的变化是有一定趋势的。通过单纯的随机过程实 现类似造型的控制是很困难的，而引入力进行控制便可以迎刃而解。在本模型中 引入了内力和外力，内力用于控制树的局部形态，而外力用于控制树的整体形态。 本模型的缺点是特征参数和控制参数个数都比较多；另外算法具有较大的时 间和空间复杂性，有待进一步优化。 关键词：分形三维建模计算机图形学 中图法分类号：t p 3 9 1 4 1 8 t i t l e ：t h er e s e a r c ho f3 dm o d e l i n gm e t h o do f t r e e a b s t r a c t n a t u r a ls c e n e r ye m u l a t i o ni sas u b d i s c i p l i n eo fc o m p u t e rg r a p h i c sw h i c hh a s a t t r a c t e dm a n ys c i e n t i s t st or e s e a r c hi nr e c e n ty e a r s t h eg o a lo fn a t u r a ls c e n e r y e m u l a t i o ni s t or e a p p e a ra p p e a r a n c eo fi r r e g u l a ro b j e c t si n1 1 a t u l - e ，s u c h a s t o p o g r a p h i c a lf e a t u r e s ，h a s s o c k ，t r e e ，c o a s t , c l o u da n ds oo n a m o n gt h e s et o p i c s ，t h e r e s e a r c ho f3 dm o d e l i n gm e t h o do ft r e ea n do t h e rp l a n t si st h em o s tp o p u l a r t h e r e a r em a n yp a p e r sa b o u tt h es u b j e c ti np u b l i s h ，t h e s ep a p e r sp u tf o r w a r dl o t so fg o o d i d e a st os o l v et h ep r o b l e m t h i sa r t i c l e w ew i l ls u m m a r i z eg e n e r a lo u t l i n eo ft w o c l a s s i c a lm e t h o d s ，l s y s t e ma n di f s ，a n ds o m ev a r i a n tm a n n e r sd e r i v e df r o mt h e c l a s s i c a lm e t h o d s b o t hl - s y s t e ma n d i f sa r ep u r e l yb a s e do nf r a c t a l t h em e r i to ft h e s em e t h o d s i st h a tt h e yh a v ef e w e rp a r a m e t e r sa n dh a v eab e a u t i f u lm a t h e m a t i c a ls t y l e t h e d e m e r i to f t h e s em e t h o d si st h a tt h es h a p e sg e n e r a t e da r en o ts om u c hv i v i d ，i ti sh a r d t oc o n c e i v et h er e s u l tt h r o u g ht h ep a r a m e t e r s ，a n dt h er e s u l ti st o os e n s i t i v er e l i a b l eo n t h ep a r a m e t e r s t h es h a p e so ft r e eh a v et y p i c a lf e a t u r eo ff r a c t a la n dr a n d o m n e s s ，w h i c hw e r e i n f l u e n c e db yt h e i rg e n e sa n dc i r c u m s t a n c e s t h i sa r t i c l ep u tf o r w a r dad y n a m i c f o r c es y s t e m ( d f s ) ，w h i c hi n c l u d em a s s ，f o r c e ，v e l o c i t ya n df r a c t a ld i s t r i b u t i n go f a m o u n to fe n e r g y d f su s eag r o u po fp a r a m e t e r st od e s c r i b ev a r i o u s3 dm o d e l so f t r e e t h i sp a p e rh a sa l s op r o v i d e dt h ea l g o r i t h mo f d f s 3 dm o d e l i n gm e t h o da n da l g o r i t h mo ft r e ep u tf o r w a r db yt h i sa r t i c l ec o m b i n e t h en a t u r es t r u c t u r eo ff r a c t a lw i t had y n a m i cf o r c es y s t e m t h i si sd i f f e r e n tf r o m o t h e rm e t h o da n di sas p e c i a lc r e a t i v ei d e a t h ea l g o r i t h mp r e s e n t e db yt h i sa r t i c l eh a sb e e nd e v e l o p e db yv b ab u i l t i n a u t o c a d t h er e s u l ts h o w st h a tt h i sm e t h o di sn o to n l ya d e q u a t e ，b u ta l s ov e r y e f f e c t i v e t h em o s ta d v a n t a g eo ft h i sm e t h o di st h a ti ti se a s i l yt oc o n t r o lf r a c t a ls t r u c t u r e o ft r e es h a p et h r o u g ht h ef o r c e i n c l u d ei n l 2 e rf o r c ea n do u t e rf o r c e w ecans e et h a t t r e es h a p e si nn a t u r ea r ev a r i o u s b u tb a s i cs h a p ei ss i m i l a r t h em o d e l i n gm e t h o do f t r e es h a p es h o u l dr e m a i n 血eb a s i cs h a p e a n da l s os h o u l dh a v ev a r i a b i l i t vb a s e do n b a s i cs h a p e t h ef r a c t a lm e c h a n i s mc a l lu n d e r t a k et h eb a s i cs h a p e t r a d i t i o n a l m e t h o da c h i e v ev a r i a b i l i t yt h r o u g hr a n d o mp r o c e s s i f w el o o ki n t ov a r i a b l es h a p e so f 订e ec a r e f u l l y , w ec a ne a s i l yf m dt h ef a c t t h a ta l t h o u g hl o c a lv a r i a b i l i t yi sc o m p l e t e l y r a n d o m t h ei n t e g r a t i o nc o m m o n l yh a sat e n d e n c y s oi t i sd i f f i c u l tt op u r e l yu s e 9 r a n d o mp r o c e s si nm o d e l i n g3 dt r e e t h es o l u t i o ni sa d o p t i o nt h en o t i o no ff o r c e ， w h i c hc a ne a s i l ys o l v et h ep r o b l e m o u rm e t h o di n t r o d u c e st h en o t i o no fi n n e rf o r c e a n do u t e rf o r c e ，i n n e rf o r c ec o n t r o lt h eb a s i cs h a p e ，a n do u t e rf o r c ec o n t r o lt h ew h o l e t e n d e n c y t h ed e f e c to fo u rm e t h o di st h a ti th a sm a n yf e a t u r ep a r a m e t e r sa n dc o n t r o l p a r a m e t e r s ，a n dt h et i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t ys h o u l d b eo p t i m i z e d k e y w o r d s ：f r a c t a l ，3 dm o d e l i n g ，c o m p u t e rg r a p h i c s 1 0 1 现状 自然景物模拟的基本目标是利用计算杌图形学手段尽可能真实再现大自然 巧夺天工的造型，如雪花、冰凌、地貌、海岸、树木、草丛、云彩等大自然中的 静态事物。由于这类事物的外观具有无限丰富的细节，通常将这类事物称为分形 物体，分形物体无法直接利用传统的e u c l i d 几何进行精确描述，而分形几何是 描述分形物体的有效工具。 自然界中的树( 也包括大部分植物) 的形态具有局部与整体近似相似的性质， 因此树是一种非常典型的分形物体。目前大多数流行的有关树的三维建模方法都 是基于分形方法，本文提出的方法也是基于分形过程的。 1 1 分形概述 7 0 年代中期由芒德勃罗( b b m a n d e l b r o t ) 创立的分形几何学，是探索复杂 性的有效工具，它的出现对各门自然科学产生了深远影响。 几何学是用来描述物体空间结构的- 1 7 数学分枝，传统的几何学可以对光 滑、规则形体进行精确描述，是以此为基础的严密和完整的理论体系。而普遍存 在的一系列自然界中的物体并不是光滑、规则的，它们通常是错综复杂的，如海 岸线、树枝、山脉、星系分布、云朵、聚合物、天气模式、大脑皮层褶皱、肺部 支气管分支以及血液微循环管道等等。这些事物利用传统几何学工具几乎无法描 述，甚至无法近似描述。 1 9 世纪的数学家也凭借想象创造出了一些不光滑、不正则的形体或空间形 式，如c a n t o r 集( 从拓扑学角度看，它是紧致的、完全不连通的完备集，而且 具有连续统的基数，但测度为o ) 、w e i e r s t r a s s 函数( r e ( x ) = 口c o s ( 2 2 6 舡) ， i 。i 当o a l l2 0 ) ( p r o g n l 是生成元长度，w 是生成元半径 长度小于2 0 ，结束递归调用 ( c o a n d ”c y l i n d e r ”( o00 ) w1 ) ；画圆柱体，长度1 ，半径w ( s e t qw l w0 6 ) )；按一定比例减少半径 ( s e t qr0 6 )；设定长度减少的比例 ( c o a n d ”u c s ”n ”z a ”( 1 i s t001 ) ( 1 i s t00 ( + li ) ) ) ；坐标变换 ( s s s ( 术lr ) w 1 )i 递归调用 ( c o a n d ”u c s ”p ”)；恢复坐标变换 ( c o a n d ”u c s ”n ”z a ”( 1 i s t00i ) ( 1 i s tl1 ( + 11 ) ) ) ( s s s ( 1r ) w 1 ) ( c o m m a n d ”u c s ”p ”) ( c o m m a n d ”u c s ”n ”z a ”( 1 i s t001 ) ( 1 i s t ii ( + li ) ) ) ( s s s ( 1r ) w 1 ) ( c o a n d ”u c s ”p ”) ( c o a n d ”u c s n ”z a ”( 1 i s t001 ) ( 1 i s t i 一1 ( + l1 ) ) ) ( s s s ( $ lr ) w 1 ) ( c o a n d ”u c s ”p ”) ( c o a n d ”h c s ”n ”z a ”( 1 i s t001 ) ( 1 i s t1 - i ( 十l1 ) ) ) ( s s s ( lr ) w 1 ) ( c o a n d ”u c s ”p ”) ) ) ) 由于a u t d c a d 内嵌的v b a 除了提供了更加丰富的内置函数之外，还支持结构 化程序设计，支持基于对象的编程，它的数据处理能力也比a u t o l i s p 强。本文 提出的树的三维建模算法采用v b a ，源代码参见附录2 。 基于能量分形的数学模型 2 1 能量分形概述 l 系统和i f s 都是单纯利用分形结构实现树的三维建模。这类方法的优点是 使用参数较少，数学形式比较优美，缺点是生成的造型过于呆板，缺乏生动性， 早不易莩制，印丛司始爹攀乖荤佶计孽罄雾出晕警产牛的雌犁，晕绛建犁科印蝓 参数的变化过于敏感。 树的三维建模系统的理想模式应当具有以下特点； 比较精确地描述一般树形态的特征参数大约需要几十个左右，这些参数之间 不是相互独立的，它们通常具有一定的依赖关系。一旦数学模型确定后。选 择一个合适的参数集是首要任务。 描述方法使用的参数集的个数应当越少越好，便于用户使用。 各参数之间应当尽可能独立，即相互依赖性越小越好。 每个参数应当能够直接反映树形态的某种特征，使用户可以通过所选参数值 大致推断出最终生成的树形态。 最终结果对参数的变化应当具有连续性，这样便于用户通过参数的变化控制 最终生成的树形态。 对最终生成的树形态应当具有整体和局部的控制能力。 生成系统应当具有一定的随机性。 应当具有快速生成模式，便于用户预览结果。 基于能量分形模型的基本思想是建立一个树的动力学模型，认为树的生长收 到内力和外力的综合作用，初始状态的“种子”具有一定的生命能量，即具有一 定的质量和初速度，这里质量对应树干的横截面积，横截面积的运动轨迹形成树 干。由于存在内力和外力的综合作用，树生长过程会消耗生命能量，当生命能量 消耗到定程度( 一个特定的比例因子) ，树枝开始分枝，分枝的过程是将质量 分裂为若干块，就像一股流水分成若干股流水一样，所有分枝的横截面积的总和 等于分枝前树枝的横截面积，分枝后各子枝将按不同的速度继续生长，并继续分 枝，直到生命能量用尽或满足终止条件。 上述思想是将一棵树的三维造型建立在一个动态生长的基础上，生长过程不 仅是一个分形的过程，同时也是一个不断受内力和外力作用的过程，内力和外力 产生影响的大小取决于分枝的质量大小。所以整个过程我们就有可能通过一组控 制参数对树的三维造型进行有效的控制。 下面将要讨论上述动力系统需要引入哪些参数，以及引入这些参数的必要性 和这些参数所起的控制作用。整个模型从以下几个方面引入了不同的参数： 有关树枝的粗细 有关树枝的生长速度 树枝发生分枝的条件 进行分枝过程的具体细节 各树枝的生长方向 力( 内力和外力) 的控制作用 枝与叶之间的空间关系 终止生长的条件 2 2 动力系统模型 本节讨论用于描述一棵树生长过程的基于分形的动力系统模型。首先声明， 本模型不是模拟实际树生长的仿真模型，而是用于树的三维建模的生成过程的模 型。 如图6 所示，一棵树的生长是从树芽开始，当生长到一定程度后便开始分枝， 形成新的树芽，树芽按照同样的生长规律继续生长，直到满足分形结束条件，最 后生长的分枝是带树叶的分枝，形成树冠。树的整个生长过程受内因和外因的控 制作用。 树的生长从树芽开始，树芽具有一定的生命能量，即具有质量和初速度。 其中质量表示树干的横截面积，即质量越大树干越粗；速度表示树干的 生长能力。另外树芽应当有特定的位置，开始的树芽表示树根的空间坐 标，后来生成的树芽表示子枝在主枝上的位置。 树芽所具有的横截面积的运动轨迹形成树干。 树枝的生长受内因和外因作用的控制。 1 内因： 包括两组力和加速度。其中力的控制作用与质量( 即横截面积) 有 关，加速度的控制作用与质量无关。 1 ) 一组力和加速度用于抑制树枝的生长，使树枝的生长以消耗生命 能量为代价。这组力和加速度的方向始终与树的生长方向相反。 2 ) 另一组力和加速度用于控制树枝的弯曲程度和方向，这组力和加 速度的方向始终与树的生长方向垂直，因此该组力和加速度树枝 的生命能量不产生影响。 2 外因： 外因包括一组力和加速度，方向随意设定，用于控制整棵树的生长 趋势。 树枝生长到一定程度，当满足分枝条件时，开始分枝。按照树的一组特 征参数的描述进行分枝，形成新的树芽。这些特征参数包括；树枝的质 量、初始位置和初速度、分枝条件、分枝数、主枝和子枝的质量比、主 枝和子枝之间的角度、分形终止条件、叶子大小和密度等。这些特征参 数都是描述一棵树所必须的。 新的树芽按照同样的生长规律继续生长，形成分形过程。 当满足分形结束条件时，停止分枝。最后生长的分枝上应当长上书叶， 形成树冠。 图6 ：树牛长的动力系统模犁 图7 ：树的生长模型 图7 说明了一棵树的生长过程。 在上述模型中，树的建模过程是一个动态过程，首先从一个二维的实心圆开 始，在控制作用下不断生长直到达到满足分枝条件，如图7 ( a ) 所示。 实际的树枝生长过程是连续的，而计算机的处理过程是离散的。本模型通过 一个步长数参数( s t e p ) 可以控制离散化的程度，s t e p 越大，逼近程度越高， 当然绘制时间也越长。从图7 ( a ) 中可以看到连续的树枝被分割成了若干段。 树枝的生长过程受各种控制因素的影响，因此生长方向会有一个趋势上的变 化。从图7 ( b ) 可以观察到分枝是以主枝为中轴散开的：从图7 ( c ) 可以 观察到整棵树生长不是各方向对称的，而是向一个方向倾斜。 当满足分枝条件后，便开始分枝，生成新的树芽并继续生长。分枝的个数， 子枝与主枝之间的角度，子枝的质量等必要的数据可以通过树的相应的特征 参数求得。树芽的位置和初速度则由分形过程自动获得，并受到相同的控制 作用的影响。 当满足分形结束条件时，最后生长的分枝上面应当生长树叶。本模型将树叶 与子枝做相同处理，只是树叶不会再进一步分枝。树叶有对生、环生等形式， 有针叶、阔叶等形状，本模型在这些方面没有细分，仅采用了一种常见形式， 见图7 ( d ) 。 2 3 模型中的参数及作用 首先树枝应当有一个横截面积m ，如果用圆柱体简单表示树枝，圆柱体的半 径直接可以通过横截面积导出。当然我们也可以选择圆柱体的半径作为参数，因 为进一步的分枝是分割横截面积，而半径的平方与横截面积成正比，所以计算量 相应会增加，权衡后还是选择横截面积作为参数比较合适。 树枝的生长需要速度，速度是矢量，具有大小和方向。最初树干的生长有一 个初速度s t a r tv ，以后树干及各分枝的速度将根据内力和外力的影响不断改变， 其能量也随之改变。按照牛顿第一定律，如果没有力的作用，物体的动能不发生 变化，速度也不改变，这样树枝将无限生长下去。因此需要一个抑制生长的内力， 该内力的方向永远与生长速度方向相反，保证生长过程必须以消耗生命能量为代 价。由于力作用于物体对速度的影响与物体的质量有关，这样如果使用内力作为 参数，将对不同粗细的树枝产生不同的加速度，并且树枝越粗，加速度越小，导 致越粗的树枝会生长的越长，这一现象不符合对大多数树的观察结果。所以选择 只对速度产生影响，与质量大小无关的加速度面作为控制参数。 树枝生长到一定长度以后便开始分枝，分枝以后各子枝仍然会按既定的规律 继续生长，这一分形过程将通过递归算法实现。分枝的位置需要设置一个参数进 行控制，由于树枝的生长是具有一定质量和初速度的在力的作用下的运动过程， 在生长过程中动能逐渐递减，所以可以选择将初始动能递减到一个特定的比例 b ，作为开始进行分枝的条件。 分枝过程是将当前主枝的质量分配给各个子枝，各子枝初速度的大小就是当 前分枝时树枝的生长速度，各子枝的初速度具有不同的方向，在新的质量和初速 度情况下各子枝继续生长。完成这一过程需要确定以下事情：分出几个子枝? 是否有与主枝方向一致的子枝? ，除与主枝方向一致的子枝之外，其他子枝的 初速度是什么? 各子枝如何分配主枝的质量? 引入参数k 作为所有与主枝方向不一致的子枝的个数。引入参数 m s r a t i o ( m s r a t i o 0 ) ，表示与主枝方向一致的子枝的横截面积和所有与 主枝方向不一致的子枝的横截面积总和之比。当msr a t i o = 0 时，不存在与主 枝方向一致的子枝；当m j r a t i o 0 时，存在与主枝方向一致的子枝。 msr a t i o 参数同时也给出了质量分配方案，将主枝质量的 m 占r a t i o l + mjr a t i o分配 给与主枝方向一致的子枝，将主枝质量的- l _ 分配给与主枝方向不一 l 十msr a t i o 致的子枝，所有与主枝方向不一致的子枝共有k 个，每个与主枝方向不一致的子 枝得到主枝质量的百i 南。 确定与主枝方向不一致的子枝的初速度，需要引入控制参数口，表示予枝与 主枝之间的夹角。由于无法仅通过一个参数确定三维空间的方向矢量，这里引入 主子平面的概念：主子平面是由主枝方向和子枝方向两条相交的直线确定的空间 平面。建立第f ( o f 0 ，可以使树枝向主枝方向弯曲；当 inner一，可以使树枝向主枝相反方向弯曲。该值的绝对值越大，表示曲率_a 0 越大。i n n e r j a = 0 ，表示该控制参数不起作用。 u n i f o r m _ i n n e r _ f o r c em - 与i n