基于骨架截集的交互式三维分形树造型技术.pdf

兰州理工大学 硕士学位论文 基于骨架截集的交互式三维分形树造型技术 姓名：赵鸿飞 申请学位级别：硕士 专业：应用数学 指导教师：刘树群 20100520 硕士学位论文 摘要 分形作为一门新兴的交叉学科，受到非线性学术界的广泛重视。分形为探讨自然 界复杂事物的客观规律及其内在联系提供了新的概念和方法。在自然景观的模拟特别 是植物的模拟中，分形技术展现了其独特的优势，成为当前研究的热点之一。 利用分形进行植物模拟实际上是利用植物自身结构的分形特征生成植物图形。目 前主要的模拟的方法有：迭代函数系统i f s 、l - 系统、受限扩散凝聚d l a 模型和粒 子系统等。本文基于迭代函数系统i f s ，结合骨架截集造型方法，讨论了交互式三维 分形树的造型技术。 本文首先介绍了带凝集i f s 、带参量i f s 、不压缩i f s 、再归i f s 等几种扩充的 i f s 数学模型、基于点和直线的i f s 分形树造型技术，为进一步利用i f s 数学模型模 拟植物奠定理论基础。 其次介绍了计算机图形学三维造型中的骨架截集造型方法，主要包括骨架截集造 型方法的定义、基本原理和具体函数的使用，为在三维分型树造型中利用骨架截集造 型方法替代圆台造型方法提供基础。 最后分析了基于圆台造型的三维分形树木i f s 递归算法的优缺点，然后采用基于 骨架截集的多种树枝造型，对原有的递归算法加以改进，使i f s 数学模型能够和骨架 截集造型方法相结合，进而提出了基于骨架截集造型技术的三维分形树木i f s 递归算 法，并对这两个算法的三维分形树生成效果进行比较。在编程实现部分，主要介绍了 二维仿射变换的计算、三维变换的获得、二维树枝造型的生成、二维树枝造型数据向 三维树枝造型的数据转换和三维分形树的递归生成。 本文在基于圆台造型的三维分形树木i f s 递归算法的基础上，提出了基于骨架截 集造型技术的交互式三维分形树木i f s 递归算法。从简单的和非真实感的二维手绘图 形快速生成复杂的和具有真实感的三维树木模型，得到的三维分形树连接自然，形态 逼真。该方法克服了基于圆台造型的三维分形树木i f s 递归算法树枝造型种类单一、 固定、造型数据与仿射变换数据相同和造型效果僵硬等缺点，使得树枝造型种类多样 化、随机化、造型数据与仿射变换数据相关、造型效果更加自然。为三维分形树造型 技术的研究提供了新的途径，在自然景物模拟、动画制作、虚拟现实等方面都有重要 的应用价值。 关键词：分形；迭代函数系统( i f s ) ；树木模拟；植物模拟；骨架；手绘图形 基于骨架截集的交互式三维分形树造型技术 a b s t r a c t f r a c t a la san e wi n t e r d i s c i p l i n a r yf i e l d ，r e c e i v e dw i d er a n g eo fa c a d e m i ca t t e n t i o n f r o mn o n - l i n e a rf i e l d f r a c t a lp r o v i d e sn e wc o n c e p ta n dm e t h o df o re x p l o r i n gt h e c o m p l e x i t yo ft h ef r a c t a ln a t u r ea n di t si n h e r e n to b j e c t i v el a w i nt h ef i e l do fn a t u r a l l a n d s c a ps i m u l a t i o ne s p e c i a l l yt h ep l a n ts i m u l a t i o n ，f r a c t a lh a s d e m o n s t r a t e di t s u n i q u ea d v a n t a g e sa n db e c o m eo n eo ft h eh o tt i m e s a c t u a l l ys i m u l a t i n gp l a n tb yf r a c t a li sg e n e r a t i n gf r a c t a lg r a p h i c sb ym a k i n gu s eo f f r a c t a ls t r u c t u r ei t s e l f a tp r e s e n t ，t h em a i nm e t h o d so fs i m u l a t i n gp l a n ti n c l u d e s i t e r a t e df u n c t i o ns y s t e m ，l - s y s t e m ，d i f f u s i o nl i m i t e da g g r e g a t i o nm o d e la n d p a r t i c l es y s t e m b a s i c i n gt h ei f sa n dc o m b i n i n gt h es k e l e t o n s e tm o d e l i n g ，t h i sp a p e r d i s c u s s i n gt h ei n t e r a c t i v et h r e e - d i m e n s i o n a lf r a c t a lt r e em o d e l i n gt e c h o n o l o g y t h i sp a p e rf i r s ti n t r o d u c e ss e v e r a le x p a n s i o ni f ss u c ha sw i t ha g g r e g a t i o ni f s ， i f sw i t hp a r a m e t e r , n oc o m p r e s si f sa n dr e c u r r e n ti f sa n di f sf r a c t a lt r e em o d e l i n g t e c h o n o l o g yb a s e dp o i n ta n dl i n e i tp r o v i d e sb a s i s e sf o rs i m u l a t i n gp l a n tb yi f s t h e ns k e l e t o n - s e tm o d e l i n gi nc o m p u t e rg r a p h i c s3 dm o d e l i n gi si n t r o d u c e d w h i c hm a i n l yi n c l u d e st h ed e f i n i t i o n ，b a s i cp r i n c i p l e sa n dc o n c r e t ef u n c t i o n i t p r o v i d e sb a s i s e sf o ri n s t e a do fr o u n d t a b l em o d e l i n gw i t hs k e l e t o n - s e tm o d e l i n gi n3 d f r a c t a lt r e em o d e l i n g a tl a s t ，t h ea d v a n t a g e sa n dd i s a d v a n t a g e so fi f sr e c u r r e n ta l g o r i t h mb a s e d r o u n d t a b l em o d e l i n ga r ea n a l y s i s e d w ei m p r o v e di t b yu s i n gk i n d so f b r a n c h m o d e l i n gb a s e ds k e l e t o n s e ti no r d e rt oc o m b i n ei f sw i t hs k e l e t o n - s e tm o d e l i n g a n d t h e ni f sr e c u r r e n ta l g o r i t h mo f3 df r a c t a lt r e eb a s e ds k e l e t o n s e tm o d e l i n gi s a d v a n c e da n dt h e3 df r a c t a lt r e ee f f e c t sg e n e r a t e dw i t ht h o s et w oa l g o r i t h m sa r e c o m p a r e d i np r o g r a m m i n gr e a l i z ep a r t ，t h em a i nc o n t e n t sc o n t a i nt h ec o m p u t a t i o no f 2 da f f i n et r a n s f o r m a t i o n ，t h eg e t t i n gw a yo f3 dt r a n s f o r m a t i o n ，t h eg e n e r a t i n go f2 d b r a n c hm o d e l i n g ，t h ec o n v e r s i o nf r o m2 db r a n c hm o d e l i n gd a t a st o3 db r a n c h m o d e l i n gd a t a sa n dt h er e c u r r e n tg e n e r a t i n go f3 df r a c t a lt r e e t h i sp a p e rp u tf o r w a r d si n t e r a c t i v ei f sr e c u r r e n ta l g o r i t h mo f3 df r a c t a lt r e e b a s e ds k e l e t o n - s e tm o d e l i n gb a s i n go ft h er o u n d t a b l em o d e l i n g t h e3 df r a c t a lt r e e w i t hn a t u r a lc o n n e c t i o na n dv e r i s i m i l i t u d ef o r m ，w h i c hi sa b t a i n e db a s i n g3 dt r e e m o d e l i n gw i t hc o m p l e x i t ya n ds e n s eo fr e a l i t yg e n e r a t i n gf r o ms i m p l e2 dh a n d - d r a w n g r a p h i c sw i t hf e e l i n go fu n r e a l i t y t h ei f sr e c u r r e n ta l g o r i t h mo f3 df r a c t a lt r e eb a s e d s k e l e t o n s e tm o d e l i n go v e r c o m e ss o m ed i s a d v a n t a g e sb a s e dr o u n d t a b l em o d e l i n gs u c h n 硕士学位论文 a ss i n g l ea n df i x e dt y p e ，m o d e l i n gd a t aw i t ht h es a m et oa f f i n et r a n s f o r m a t i o n ，t h e e f f e c to fs t i f f n e s se t c a n di tp r o v i d e sn e wm e t h o df o r3 df r a c t a lt r e em o d e l i n g r e s e a r c ha n dh a ss i g n i f i c a n ta p p l i c a t i o nv a l u ei nt h ef i e l do fn a t u r a ls c e n es i m u l a t i n g ， a n i m a t i o n ，v i r t u a lr e a l i t ye t c k e yw o r d s ：f r a c t a l ；i t e r a t e df u n c t i o ns y s t e m ( i f s ) ；t r e es i m u l a t i o n ；p l a n ts i m u l a t i o n ； s k e l e t o n ；h a n d p a i n t e dg r a p h i c s i n 基于骨架截集的交互式二维分形树造型技术 图表索引目录 图2 1 缩放变换彳。9 图2 2 伸长变换4 示意图9 图2 3 剪切变换4 。示意图一9 图2 4 旋转变换4 示意图9 图2 5 谢尔宾斯基三角形迭代一次结果1 1 图2 6 谢尔宾斯基三角形迭代第二次结果1 2 图2 7 谢尔宾斯基三角形迭代第六次结果1 2 图2 8 一般i f s 初始元无关示意图1 4 图2 9 羊齿叶与分形树示意图1 5 图2 1 0 带凝聚集i f s 分形树示意图1 7 图2 1 1 带凝聚集i f s 一排分形树示意图1 8 图2 1 2 带参量的i f s 分形树示意图1 9 图2 1 3 不压缩i f s 分形树示意图2 0 图2 1 4 再归i f s 分形树示意图2 1 图2 1 5 树枝骨架示意图2 2 图2 1 6 树枝骨架示意图。2 3 图2 1 7 三维骨架图2 3 图2 1 8 骨架截集造型三维效果图2 4 图3 1 三维分型树2 7 图3 2 基于圆台造型三维分形树示意图3 0 图3 3 改用多种树枝造型的三维分形树3 1 图3 4 对彬变化后的三维分形树3 1 图3 5i f s 递归算法二维效果比较图3 3 图3 7 基于骨架截集的i f s 递归算法三维效果图3 3 图3 6 基于圆台的i f s 递归算法三维效果图3 3 图4 1 程序开发示意图3 4 图4 2 系统界面示意图3 5 图4 3 二维仿射变换与树枝造型数据3 5 图4 4 二维骨架图3 6 图4 5 三维骨架图3 7 图4 6 截集示意图3 7 l v 硕十学位论文 图4 7 三维树枝线框图3 9 图4 8 二维仿射变换数据3 9 图4 9 变换后的二维仿射与树枝造型数据4 0 图4 1 0 基于直线造型的二维仿射与树枝造型数据4 0 图4 1 1 基于圆台造型的三维仿射变换示意图4 2 图4 1 2 基于圆台的仿射变换与骨架截集造型结合示意图4 3 v 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：去? v 砂 日期：2 f 年 石月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 作者签名：务增弘 导师签名： 日期：知o 年 日期：烈砒辉 月日 参旯1 日 硕十学位论文 1 1 课题研究背景 第1 章绪论 欧氏几何的主要描述工具是直线、平滑的曲线、平面及边界整齐的平滑曲面，这 些工具在描述一些平面多面体、二次曲面体、自由曲面体等抽象图形或人造物体的形 态时是非常有力的。然而，对于一些复杂的自然景象形态就显得无能为力了，如山、 树、草、火、云、浪等，这是由于从欧氏几何来看，他们是极端无规则的。 2 0 世纪7 0 年代，美籍法国数学家b e n o i tb m a n d e l b r o t 提出了“f r a c t a l ( 分形1 “ 一词，其原义是“不规则的、分数维的、支离破碎的物体”。由m a n d e l b r o t 撰写 的( ( f r a c t a l ：f o r m ，c h a n c ea n dd i m e n s i o n ) ) 书的出版，标志着分形理论的诞生。 1 9 8 2 年，m a n d e l b r o t 的专著( ( t h ef r a c t a lg e o m e t r yo f n a t u r e ) ) 二版的问世，在全 世界迅速形成了“分形热”。分形适合用来描述那些不规则而欧氏几何又无法描述 的几何现象和物体。 由于分形几何的自相似性，分形为描述不规则形体提供了全新的角度，使人们从 无序中重新发现了有序。计算机图形学也从中受到启发，并形成了以模拟自然界复杂 景象和物体为目标的分形造型技术。 分形造型是基于分形几何学的自相似性，采用各种模拟真实图形的模型，使整个 生成的景象呈现出细节的无穷回归性质的技术。所生成的景物中，可以有结构性较强 的树，也可以是结构性较弱的火、云、烟，甚至可生成有动态特性的火焰、浪等。生 成图形的关键是要有一个合适的模型来描述上述景象。人们已经研究了不少模型，对 于这些模型应尽量满足下列要求i “ 】：能逼真的“再现”自然景象；模型不依赖于观 察距离：模型说明应尽量简单，模型应具有数据放大能力：模型应便于交互地修改； 图形生成的效率要高：模型适用范围应尽可能地宽。 对树木等非规则自然景物的计算机生成技术的研究，自2 0 世纪8 0 年代开始，逐 渐成为计算机图形学领域的热点之一。树木的形态复杂，随机性强，给计算机实时模 拟带来了巨大困难，但分形理论大大缓解了这个问题，根据所选择的分形造型的数学 模型，可以将生成树木分形图形的方法分为三大类：l 系统模型方法、迭代函数系统 i f s 模型方法、粒子系统模型方法。国内关于树木三维可视化研究中已经完全涵盖了 这三种产生分形图形的方法，并应用计算机程序实现了基于这些建模方法的可视化树 木【& 1 3 1 。 随着对逼真程度和审美要求的不断提高，如何用尽可能通俗易懂的方式，在实时 交互的界面上，用户只需通过简单操作，修改少量参数，同时进行颜色调整和纹理映 基于骨架截集的交互式二维分形树造型技术 射，便可生成各种美丽的三维分形树，已成为当前一个被众多学者所关注的课题。 1 2 课题研究现状 目前，三维分形树造型的常用数学模型有：粒子系统模型、l 系统模型、迭代函 数系统模型。 ( 1 ) 粒子系统模型 w t r e e v e s 于1 9 8 3 年提出的粒子系统模型是一种很有影响的模拟不规则物 体的方法f 川。粒子系统的随机性使模拟不规则模糊物体变得十分简便。粒子系统虽然 在处理大量单独粒子的运动( 变化) 上很有用处，但是一涉及到需要考虑粒子间相互作 用的场合，因为这时的计算量呈粒子数量的指数级增长，它就显得有些力不从心了。 比如在模拟有相互引力作用下的大量星体的运动，大量粒子的相互碰撞等。 树木的形态结构可以用不同粒子的排列组合来模拟，粒子在生命周期中的变化反 映了树木生长发育甚至死亡的过程。当然，由于粒子系统本身的特点，它更适合于森 林景观生长系统的可视化模拟的整体研究，而单木可视化系统也同时是森林景观的关 键组成部分，讨论粒子系统在单木可视化中的应用同样有重要意义。 王小铭等人以树木的静态造型为背景，提出了一种基于骨架定制和粒子系统模型 的树木模拟方法【1 5 】。文中讨论了基于粒子系统方法的树木形态结构描述和生成：枝干 骨架及其存储结构、枝干和树叶的生成，基于粒子系统方法的树木枝干生长模型：新 枝干生长模型、枝干增长生长模型和枝干比例调节模型，并给出了上述模型的模拟结 果。雷蕾等人借助于粒子系统思想提出了一种基于能量模型的叶片纹理构造算测1 6 1 ， 该方法避免了传统的纹理贴图方法复杂的纹理坐标计算带来的复杂性和对贴图高要 求的局限性，充分发挥了粒子系统在模拟自然界中的复杂且有规律的事物的优势，模 拟出的叶片具有较高的真实性。 ( 2 ) l 系统模型 a r t i s t i dl i n d e n m a y e r 于1 9 6 9 年提出了一种研究植物形态与生长的描述方法，称 之为l - 系统( l - s y s t e m ) 1 7 1 。l - 系统的基本思想是用正规文法生成结构性强的植物的拓 扑结构，再通过进一步几何解释来形成逼真的画面。1 9 8 4 年，a r s m i t h 将l 系 统应用于计算机图形学中，为模拟植物而引入基于文法的模型。此后，用l - s y s t e m 研究树木三维可视化模拟成为所有研究中最集中、应用最广泛的方法，当前国内研究 的树木可视化软件系统大都基于1 , s y s t e m 理论，结合g i s 技术、v r 技术、3 d 技术 等不断扩展研究领域。 1 9 9 0 年郑卓嘉等人率先用l - s y s t e m 理论给出树木结构特征的文法描述1 18 | ，成功 产生出树木的三维逼真图形。文中运用并行产生式系统，给出了一类景物结构特征的 文法描述，详细地讨论了链语言的分枝骨架表示以及产生式规则与形态模式的关系， 2 硕士学位论文 并提出了有效的属性算法。该研究是目前国内最早在树木可视化范畴对l - s y s t e m 的 深入研究，为后来的l - s y s t e m 在林业可视化中的应用打下了基础。随后北京林业大 学的郝小琴等人也在此算法的基础上，结合林业生产实际，提出了与林业结合的d o l 算法，取得良好的可视化效果【l 引。 2 0 0 1 年徐杨等人基于l 系统对树木的三维结构形态建模进行了讨论，综合考虑 了树木的分生规律、趋光性和屈地性，以较小的数据量对树木形态进行模拟，效果良 好。然而如果能够进一步完善树木葱结构复杂的树木提取替换规则，或对树木生长规 律和外部环境影响因素作进一步研究，可以过得更加复杂逼真的模拟效果。 为了克服将l 系统用于编程指导时繁琐的缺点，张树兵等人在对用l 系统代码 生成的各阶段图形的形状进行分析的基础上，给出了一种改进方法1 2 。该方法首先把 系统代码转换成简单递归表达式，然后根据该表达式编写具有递归结构的程序，从而 避免了传统方法中庞大的链表结构和复杂的遍历过程，而且使植物建模和实现更加简 洁和高效。 为提高三维分形植物生成的交互性，张帆等人讨论了在v r m l 环境中三维分形 植物的生成【2 2 1 。文中指出了植物形态结构分形模拟的难点，提出了基于v r m l 的简 化l 广系统算法，并利用该算法生成了若干种具有交互性的三维分形植物的实例。魏 琼等人以d o l 为基本算法，运用v c 和o p e n g l 对树木形态的三维模拟，得到了形 象逼真的立体树木形态模型【矧，并利用该模型计算了叶面积指数和光斑密度，为实际 生产提供了重要参考数据，是l 系统在树木生成理论与计算机结合的较好尝试。 赵欣等人为了在3 dg i s 领域中寻找到关于树木实体表达的有效途径，对i f s 和 i 广系统两种三维树木实体建模方法进行了比较，最终确定了l 广系统是3 dg i s 中构建 树木实体的最佳方法，并从面向对象角度出发，给出了基于i 广系统的树木实体对象 类，便于使树木实体作为3 dg i s 中的对象之一融合到系统中瞄】。李小青等人则在3 d s m a x 脚本语言的基础上，实现了三维树木的创建，为实现森林虚拟环境的创建奠定 了基础【2 5 1 。树木的整体创建采用了三维l 系统，利用3 dm a x 中的对象创建工具 一m e s h 创建对象，并实现了场景动画。 ( 3 ) 迭代函数系统模型 迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，简记为i f s ) 的产生最早可以追溯到 1 9 8 1 年h u t c h i n s o n 对自相似集的研究【2 6 。1 9 8 5 年m f b a r n s l e y 和s d e m p o 将其公式 化，并应用到图像压缩和处理方面1 2 7 1 。1 9 8 9 年b a r n s l e y 等提出了“再归迭代函数 系统( r e c u r r e n ti f s ) “ 方法【2 8 1 。该方法在自相似性生成方面更加灵活多变，植物 局部自相似性之间可以有更多不同。 1 9 9 1 年p r u s i n k i e w i c z 与h a m m e l 等提出了“语言约束式迭代函数系统 ( 1 a n g u a g e r e s t r i c t e di f s ) “ 方法，该方法通过加入不同变换顺序的约束条件，能 够比较通用地概括各类不同的i f s 方法。 3 基 = 4 骨架截集的交互式三维分形树造型技术 近年来，国内外学者在基于i f s 系统的分形图形生成领域都进行了大量的研究 工作，产生了带概率i f s 、带凝聚i f s 、带参数i f s 等等，并取得了一定的进展。 在分形图形交互式生成技术方面，美国伊利诺斯州立大学计算机系p a u l s h e r m a n 和j o h nc h a r t 给出了一个分形图形生成算法【2 9 1 ，使用户可以直接操作一 个由周期迭代函数系统( r i f s ) 生成的分形对象，这种方法可以让用户指定吸引 子上的特定点，然后拖拽其他点到用户需要的位置，进而改变吸引子的形状。王 镝等人讨论了一种参数控制方法 3 引，通过改变参数控$ 1 j i f s 吸引子的形状，最终 生成不同的计算机图像，该方法首先给出两个原始三角形，通过对两者位置和形 状的改变得n i f s 码，并通过不断引入新的三角形并改变其位置和形状来影响i f s 吸引子的外观。 有些学者提出了寻找新的i f s 建模技术或者根据已知的i f s 码通过加入某些 参量再进行调整来生成新的分形图形的方法【3 1 3 3 1 ，s a r a h 研究了分形的快速精确 的生成算法【3 4 l ；t a oj u 研究了仿射变换i f s 和递归龟图几何生成分形图算法【3 5 1 ； 仲兰芬、李庆忠等研究了基于i f s 的三维树木模拟方法【3 6 】：方建安、张旭还研究 了i f s 模拟植物图像的颜色生成算法【3 7 】；曾锋等基于迭代函数系统进行了彩色植 物模拟研究【3 8 1 ；李庆忠、h s u a nt c h a n g 等分别提出了l 系统与i f s 相融合的方 法和分形图形的合成方法【3 9 4 0 】；b u r c h 等提出了利用极值分解方法分解工i f s 仿 射变换的线性部分矩阵，实现二维i f s 线性分形变形【4 1 】；t o m e km a r t y n 提出了吸 引子变形的正确性标准及新的i f s 分形变形算法【4 2 】，为分形动画的实现奠定了基 础。刘树群实现i f s 吸引子图像仿射变换的分形码变换通式，并讨论了几种常见 的吸引子变换，其为分形图像变换和分形图形设计提供了一种简捷、高效和灵活 的处理方式【4 引。 由于树木具有自相似的特点，在树木可视化系统中有大量应用i f s 算法的研究的 成功实例。 郭维红等人提出利用i f s 方法构建树木数学模型并在实现单木可视化系统，该 研究采用随机二叉递归模型方法能较真实地实现树、竹类自然植物的计算机仿真。李 庆忠等人基于i f s 方法，提出用有限个压缩放射变换子图对树木各部分进行贴图的方 法，并讨论了对该树木模型进行着色的方法和树影运算的方法，实现树木不同姿态的 模拟1 4 5 】。仲兰芬等人给出了生成单轴分枝和合轴分枝两类树木的递归算法，经过计算 机实验得出了单轴分枝和合轴分枝两类树木的i f s 码，并进行了正确性证明和真实感 n i l s 。刘树群等人研究并讨论了再归迭代函数系统的相关理论，并在此基础上提出 了采用再归迭代函数系统的完全转移式、部分转移式、交替式生成分形图形的一种新 方法；并将此方法应用于分形植物的计算机模拟，实验结果表明该模拟使分形树图形 更加逼真、自然1 1 3 】。 现有的迭代函数系统i f s 维分形树生成技术，从分形图形的基本造型元素来分 类，可分为： 4 硕士学位论文 ( 1 ) 基于点的二维分形树制作技术； ( 2 ) 基于直线的二维分形树制作技术； ( 3 ) 基于圆台的三维分形树制作技术。 树木在其形态的发生与发展过程中是不断地在已经存在的组织上复制一个与 其相类似的部分，这使得树木的生长呈现出了一定的分形特征，可使用二维i f s 植物建模加以模拟，但二维i f s 植物建模的应用受到一定限制，这主要是因为， 首先二维i f s 码不易获得，它是利用交互图形技术对景物图像不断“试凑”而获取 的，对使用的硬件、软件以及操作人员的经验要求都很高。其次，二维i f s 码只 是景物图像的模型，而不是景物自身的形体模型，反映的只是从某个确定的视点 所看到的景物的某个观察面。并且，若景物自身的形态发生了变化或者变换了观 察视点，就需要有相应的景物图像并由此得到另一组新的i f s 码，这在实践上是 很困难的。 采用三维i f s 植物建模，建立起植物本身的三维形体模型，可以解决以上问 题，使得树枝连接准确，并可使用纹理、光照等计算机图形学方法增强三维形体 的真实感。 但基于圆台的三维分形树可视化研究中也存在如下的一些问题： ( 1 ) 这些三维分形树可视化研究中的交互手段都是寻找i f s 码或者调整i f s 码来实 现分形吸引子的生成或形状调整，不能实现实时交互的分形树图形生成，这些迭代函 数系统( i f s ) 的模型【8 d 1 】需要提供大量的仿射变换的具体参数，大都采用i f s 码输入， 很难在i f s 码与三维树木之间产生直观的对照【1 2 h 3 1 ，不便于树木造型的调整，对于 使用者来说，不仅要熟悉树木的各种形态特征，而且要熟悉i f s 迭代函数系统，限制 了这类系统的使用。 ( 2 ) 这些三维分形树可视化研究中三维造型技术主要是采用圆台( 柱) 造型，给 树干的弯曲的实现，树干的多样化自由造型的实现，造成了很大的困难。 1 3 课题研究内容 通过对基于圆台的迭代函数系统递归算法的改造，使其能和三维骨架截集造型技 术相结合，最终在v c 环境下用m f c 方式在o p e n g l 下，实现基于手绘的三维分形 树就是本课题研究的主要内容。 1 4 课题研究意义 本课题提出的基于骨架截集的交互式迭代函数系统i f s 三维分形树造型方法是 一种基于分形的多边形几何面三维树木构造方法，生成方法简单，通过对迭代函数系 统i f s 递归算法的改进，为实时交互的实现和骨架截集造型技术在分形中的应用创造 5 基于骨架截集的交互式三维分形树造型技术 了条件，实现了迭代函数系统数学模型与骨架截集造型方法的结合。既可以绘制出树 木自然形态的分形特征，又可以利用纹理、光照等多种已有的多边形几何面构图技术 对树体渲染，生成具有高度真实感的三维分形树木。 本文的成果为三维分形树造型技术的研究提供了新的途径，在自然景物模拟、动 画制作、虚拟现实等方面都有重要的应用价值。 1 5 论文的组织结构 第一章论述了课题的研究背景，国内外分形树研究现状、研究内容和研究意。 第二章首先论述了分形理论中吸引子初始元无关的一般迭代函数系统的定义，重 要定理等基本理论以及基于点的分形树造型技术等，然后论述了分形理论中几种吸引 子初始元相关的扩充迭代函数系统的基本理论以及基于直线的分形树造型技术等，其 次论述了骨架截集造型方法理论，包括骨架截集集造型方法简介和骨架截集造型函数 说明等。 第三章论述了基于骨架截集的交互式1 f s 三维分形树的的算法原理，主要是对基 于圆台的三维分形树递归算法的分析，改进前后的效果对比等。 第四章论述了基于骨架截集的交互式i f s 三维分形树的编程实现的具体步骤，包 括二维数据的获得、三维数据向三维数据的转化、程序的界面设计和骨架截集造型方 法的实现等。 6 硕士学位论文 第2 章预备知识 分形几何( f r a c t a l ) 这一概念首先是由法国数学家b m a n d e l b r o t 提出的，他1 9 7 5 年的专著分形：形状，机遇与维数的问世标志着分形理论的诞生。 1 9 8 2 年m a n d e l b r o t 给出分形的一个尝试性的定量刻画： 定义2 1 如果一个集合在欧氏空间中的h a u s d o r f f 维数以严格大于其拓扑 维数珥，则称该集合为分形集，简称分形。 此定义强调维数，其中的h a u s d o r f f 维数一般不是整数。该定义不合理，因 为它把一些明显应为分形的集合排除了。1 9 8 6 年，m a n d e l b r o t 又提出了一个实用 的定义： 定义2 2 组成部分以某种方式与整体相似的形体叫分形。 上述定义都不够精确和全面。英国数学家k f a l c o n e r 认为分形的定义应不寻 求分形的确切定义，而是寻求分形的特征。一般地，称集f 是分形，即认为它具 有如下性质： ( 1 ) f 具有精细的结构，即在任意小的尺度下，总是有复杂的细节； ( 2 ) f 是不规则的，以至于它的整体和局部都不能用传统的几何语言来描述； ( 3 ) f 通常具有某种自相似性，可能是近似的或统计的； ( 4 ) f 在某种意义下的分形维数通常都大于拓扑维数； ( 5 ) 在多数情况下，f 可以以非常简单的方式定义，或许以递归过程产生。 分形是介于无序与有序、微观与宏观、简单性与复杂性、随机性与确定性之 间的一种过渡状态。分形既可以是几何图形，也可以是由“功能“ 或“信息”等 构成的数理模型。通过分形定义可知，规则分形具有以下特点： ( 1 ) 图形是“支离破碎、不规则的“ ，从数学角度看，它处处是奇点，如处处 不连续或处处不可微； ( 2 ) 分形具有标度不变性，即改变尺度或标度时，图形是相同或相似的； ( 3 ) 分形的h a u s d o r f f 维数一般是分数，且大于拓扑维数。 上述特点在不规则分形中也是存在的，但不规则分形中的自相似性是统计意 义上的，即总体来看局部和整体是相似的。 与数学上的分形相比，自然乔中实际存在的分形具有两个明显的特点： ( 1 ) 自然界中的分形仅在一定范围和层次中才表现出分形特征，这个具有分形 特征的范围叫“无标度区“ 。在无标度区外，自相似性不复存在，系统也就没有分 形规律。此外，同一自然现象可能出现多个无标度区，在不同的无标度区上可能 出现不同的分形特征。 7 基于骨架截集的交互式三维分形树造型技术 ( 2 ) 数学中的分形具有无限嵌套的层次结构，而自然界中的分形只有有限层次 的嵌套，且是具有自相似分布特征的随机现象，并不像数学上的分形那样单纯、 均匀，必须从统计的角度考虑、分析和处理。 2 1i f s 与基于点的分形树造型技术 迭代函数系统( i f s ) 属于一种分形构形系统，是分形几何学的重要分支，是普 遍用到的一种生成分形吸引子的算法。它根据不动点原理采用多个仿射变换生成 吸引子的。用到的仿射变换主要有：缩放变换、旋转变换、平移变换等。它借助 计算机强大的迭代计算能力，将分形理论的自相似性、层次的多重性和不同层次 的规则的统一性，应用于计算机图形领域，可以产生许多具有无穷细节、精致纹 理的图形。尤其是在树木形态模拟方面，i f s 方法可以表现出树木整体形态的不 规则性及整体与局部细节的自相似性，较之以规则形状构图的传统方法更具优势。 2 1 1 迭代函数系统( i f s ) 的定义与基本定理 迭代函数系统，又称双曲迭代函数系统( h y p e r b o l i ci t e r a t e df u n c t i o ns y s t e m ) 的基本思想为在仿射变换的意义下几何对象的整体与局部具有自相似结构，正是这种 自相似性，使得有可能用迭代法生成图像从一个点或一个简单的几何图形出发，按一 定的规则反复迭代，一生二，二生三，三生万物，直到生成一幅复杂图像，最终得到 的目标点集与初始点集无关，而只取决于迭代的规则，即一组仿射变换的系数，这一 图像生成系统称为双曲迭代函数系统。 双曲迭代函数系统模型最早是由h u t c h i n s o n 于1 9 8 1 年提出的。此处双曲的概念 就是指变换为收缩的，一般地用收缩仿射变换来表示这些变换。迭代函数系统以仿射 变换为框架，根据几何对象的整体与局部具有自相似结构，经过迭代而产生的。 几何对象的整体被定义以后，选定若干仿射变换，将整体形态变换到局部，并且 这一过程可以迭代地进行下去。直到得到满意的造型。其理论依据及应用效果是基于 著名的压缩映射不变集定理和拼贴定理。 仿射变换是对图形所做的绕原点旋转、比例放大及平移等操作。这是一种最广泛 的线性变换。仿射变换可以使图形产生一个复本，分形图形的每个部分都可看作是在 不同仿射变换下的复制品。这种分解与尺度无关，即原图经仿射变换后仍然可以对局 部图形进行类似的分解。 定义2 3 变换w ：r 2 一r 2 具有形式为 ( ；) 。( 兰三) ( ；) + ( ；) ， 其中a , b ，c ，d ，e ，厂为实数，则称w 为一个( 二维) 仿射变换。 当x e r 2 ，上式常写成为 8 硕士学位论文 其中彳2 ( ：) ，r 。( ；) 。 矽o ) - a ( x ) + t ， 有四种平面仿射变换有明显的几何意义，记 4 。( 舌；) ，4 。( 三? ) ，4 。( 三砂2 瞄= ) ， 4 为缩放变换，4 为伸长变换，4 为剪切变换，4 为旋转变换。其示意图为： j 。 j 。 j 。 j 。 jl 图2 1 缩放变换4 j 。 图2 2 伸长变换4 示意图 jl i l | 一 图2 3 剪切变换4 示意图 ji 0 ，选 定一个i f s x ；w , ，刀一1 ，2 ， ，其压缩因子为os s 0 ，其中鼽；1 。取石x 并且依照递归方式独立的，可取 x 。【1 ( x 。1 ) ，2 ( z 。1 ) ，( x 。一1 ) 】- 以= 1 2 ， 其中事件z 。= 缈f ( 石撑一。) 的概率是易。构造一个序列以，万一q 】，j ，则序列 图采用随机i f s 系统，正如随机生成算法所描述的一样引入一随机变量历。p l 代 见。牡。乒型盟。 善孙或一酬 若对某个1 4 i o ，则以可取一个很小的正数。例如取a ；o 0 ( 0 ) 0 1 ，之后调整 其他概率，以确保耋a 一1 。式中42 ( 三艺) ，z = 1 ，2 ，。 其他概率，以确保a 一1 。式中4 2 i l ，f = 1 2 ，。 基于骨架截集的交互式三维分形树造犁技术 2 1 4 基于点的i f s 分形树造型技术 双曲迭代函数系统的吸引子是初始元无关的，那么采用点来生成吸引子的算 法在计算机上非常容易实现，虽早的分形树生成技术就是采用的这种方法。 国磊 盈遗厶 图28 一般i f s 初始元无美示意图 基于一般1 f s 的树木模拟i f s 描述树木形态的方法是根据拼贴原理，对已有 的某一树木图像尽可能精确地用有限个该图像的压缩仿射变换子图去覆盖它，并 允许部分重叠。 由此得到一个压缩仿射变换集：怛2 ：q ，0 ) 2 ，q ，其中任一变换为： 叶：阶刚 每个压缩映射由a , b ，e , d ，e ，f 这六个参数确定。因此，通过在原图整体及每个拼 贴子图上分别取点( z ，y ) 和( x ：y ( 其中f - i , 2 ，n 为小拷贝的总个数)