（计算机软件与理论专业论文）叶脉建模方法与绘制技术研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 重废 邮电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 合文簟 签字日期： 工7 年5 月2 2 日 学位论文版权使用授权书 本学位论文作者完全了解重废邮电太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权一重庆邮电太堂 可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：谷之哲导师签名：与多& 陟 签字日期：c 7 年5 月2 2 日 签字日期：歹1 年厂月砂纱日 重庆邮电大学硕士论文摘要 摘要 随着计算机软硬件技术的不断提高，虚拟植物是当今计算机图形学领 域的热点研究内容，它在理论研究以及实际应用两方面都具有重要意义。 叶脉的建模方法和绘制技术一直是图形学中一个富有挑战性的问题，它对 于在计算机中真实表现自然物体和场景起着不可或缺的作用。随着研究与 应用的深入，叶脉模型构建的合理程度和模拟的真实感仿真程度越来越成 为研究者关注的重点。本文对此领域进行了较深入的研究与探讨，提出了 一个评判叶脉建模方法是否合理的“叶脉生长规则，改进了两种叶脉建 模方法，这些方法与技术为自然场景中植物的真实感绘制提供了更多选 择，具有很强的实用价值。本文在此方面的主要工作与贡献如下： 对现有叶脉建模方法和绘制技术进行了较深入的对比研究，在总 结各自优缺点的基础上，提出了一个客观评判建模方法优劣的叶脉生长规 则。 在r o d k a d w 的叶脉建模方法基础上，提出一种采用v o r o n o i 图来 绘制三级网状细脉的改进方法，生成的叶脉模型在形状上更加接近于真实 叶脉。 通过将l s y s t e m s 文法引入到r u n i o n s 的叶脉建模方法当中，提出 了一种改进后的建模方法，解决了原方法当中由于主侧脉生长比较慢，最 终主侧脉夹角比较小的缺点。作为整体算法中的一步，在用随机采样方法 放置均匀分布的营养点时，采用了一种新的d a r t t h f o w i n g 算法，将时间复 杂度从d ( 2 ) 改进为d ( l o g ) ，有效地提高了整体算法的绘制速度。结果 证明，改进后的方法能以更快的速度生成更加逼真效果的叶脉模型。 目前，人类对于植物叶脉的建模方法与绘制技术的研究还处于发展阶 段，现有的各种方法还存在着不少缺点。这就为后续工作留下了很大的研 究空间。 关键词：叶脉模型，l s y s t e m s ，营养点权值，d a r t t h r o w i n g a b s t r ac t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n i q u e s ， m o d e l i n g a n d v i s u a l i z a t i o n0 fp l a n t ss c e n e si sah o tt o p i ci nt h er e s e a r c ha r e a0 fc o m p u t e r g r a p h i c s ，s 追n i f i c a n t i nb o t ha c a d e m i cr e s e a r c ha n dp r a c t i c a la p p l i c a 。i o n m o d e l i n ga n dv i s u a l i z a t i o no fl e a fv e n a t i o np a t t e r n s i sv e r yi m p o r t a n tf o r e x h i b i t i n gt h en a t u r a lo b j e c t sr e a l i s t i c a l l y ，w h i l e i ti s s t i l lac h a l l e n g i n g p r o b l e mt i l ln o w f o c u s i n g0 nt h i st o p i c ，s e v e r a lr e s e a r c hr e s u l t sa f ea c h i e v e d i nt h et h e s i s a l o n gw i t ht h cp f o g r e s s i nt h es t u d y0 fl e a fp a t t e r n s ， 0 n m o d e l i n ga n dv i s u a l i z a t i o n ， t h et o p i ch a sb e e nr e c e i v i n gm o r ea n dm o r e a t t e n t i o nf r o mr e s e a r c h e r s i nt h et h e s i s ，w ep u tf o f w a f da “l e a fv e i ng r o w t h r u l e ，a n dan u m b e r0 ft e c h n i q u e s i n m o d e l i n ga n dv i s u a l i z a t i o n t h e s e t e c h n i q u e sw o u l de n h a n c et h ef e a s i b i l i t y0 f r e a l i s t i cp l a n tr e n d e r i n g ，a n dh a v e i m p o r t a n tp r a c t i c a lv a l u e s t h em a i nc o n t r i b u t i o n s0 f0 u rw o r k i n c l u d et h e f o l l o w i n ga s p e c t s ： ( db a s e do nr e s e a r c ht ot h ec u r r e n tm o d e l i n gm e t h o d so fl e a fv e n a t i o n s ， w ep r o p o s ea no b je c t i v e “l e a fv e i ng r o w t hr u l e t oj u d g e t h eq u a l i t yo f e x i s t i n gm e t h o d s 0 n ei m p r o v e dm e t h o d i s p r e s e n t e df o rm o d e l i n go f l e a fv e n a t i o n p a t t e r n s ，v o r o n o id i a g r a mi su s e dt os i m u l a t et h et h i r d - l e v e lv e i n so ft h e l e a f b l a d e a n o t h e ri m p r o v e dm e t h o di sp r e s e n t e df o rm o d e l i n go fl e a fv e n a t i o n p a t t e r n s ，l s y s t e m si s i n t r o d u c e di n t ot h er u n i o n s m o d e l i n gm e t h o dt os o l v e t h es 1 0 wg r o w t ho fm a i na n dl a t e r a lv e i n s a n d ，an e wd a r t - t h r o w i n ga 1 9 0 r i t h m i su s e dt op l a c ea u x i ns o u r c e si ne a c hs i m u l a t i o nl o o p ， w h i c he f f c c t i v e l y i m p r o v et h ed r a w i n gs p e e d o ft h ew h o l ea l g o r i t h m t h er e s u l t sv e f i f yt h a tt h e i m p r o v e dm e t h o dc a ng e tm o r er e a l i s t i cv e n a t i o np a t t e r nb y q u i c k e rs p e e d a tp r e s e n t ，t h er e s e a r c ho nm o d e l i n ga n dv i s u a l i z a t i o no fl e a fv e n a t i o n s a r es t i l li nad e v e l o p i n gp r o c e s s ，a n dt h e r ea r el o t so fr e m a i n d e rc o n t e n t s t o s t u d v k e yw o r d s ：l s y s t e m s ，v e n a t i o np a t t e r n ，n u t r i t i o nw e i g h t ，d a r t t h r o w i n g i i 重庆邮电大学硕士论文目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 论文研究背景一1 1 2 植物建模与绘制技术研究现状2 1 3 叶脉建模与绘制技术研究现状5 1 4 论文的主要研究工作8 1 5 论文组织结构9 第二章相关理论和算法基础1 0 2 1 分形l s v s t e m s 原理介绍1 0 2 2v o r o n o i 图基本原理1 3 2 3 叶脉建模方法1 3 2 3 1 基于分形的建模方法1 4 2 3 2 基于粒子系统的建模方法1 4 2 4 随机采样算法1 9 2 5 小结2 1 第三章叶脉生长规则2 2 3 1 引言2 2 3 2 各种叶脉建模方法的对比分析2 2 3 2 1 分形方法与粒子系统方法对比2 2 3 2 2 两种粒子系统方法对比2 4 3 3 叶脉生长规则2 5 3 4 小结2 5 第四章基于分形的改进叶脉建模方法2 6 4 1 引言2 6 4 2 改进方法的理论依据2 6 4 3 实验步骤2 8 4 4 实验结果及分析2 8 4 4 1 实验环境2 8 4 4 2 真实叶脉主侧脉统计表2 8 4 4 3 所用状态参数表和l s y s t e m s 文法规则式2 9 4 4 4 用d a r t t h r o w i n g 算法生成v o r o n o i 基点集所用阈值3 0 i i l 重庆邮电大学硕士论文目录 4 4 5 结果叶脉图3 0 4 5 小结3 1 第五章基于粒子系统的改进叶脉建模方法3 2 5 1 引言3 2 5 2 改进方法的可行性分析3 2 5 2 1 理论依据3 2 5 2 2 可行性证明3 3 5 3 改进后的建模方法一3 4 5 4 实验步骤3 5 5 4 1 初始条件3 5 5 4 2 循环绘制过程一3 5 5 4 3 叶脉宽度计算一3 6 5 4 4 对放置营养点算法的改进。3 7 5 5 实验结果及分析3 7 5 5 1 实验环境与算法复杂度分析3 8 5 5 2 真实树叶主侧脉统计表3 8 5 5 3 状态参数表和l s v s t e m s 文法规则式4 0 5 5 4 在主侧脉路径上放置营养点4 1 5 5 5 改进后程序所用参数4 1 5 5 6 结果叶脉图及对比分析4 1 5 6 本章小结4 5 第六章总结及未来工作一4 6 6 1 总结4 6 6 2 未来的工作4 7 致 射4 8 攻读硕士学位期间发表及录用的论文4 9 参考文献5 0 i v 重庆邮电大学硕十论文第一章绪论 第一章绪论 作为自然场景的重要构成部分，植物对象的建模和绘制一直都是图形 学的研究热点。这一研究方向的难度源于植物对象的多样性以及绘制过程 的高度复杂性。叶脉的建模与绘制的研究源于真实感植物场景绘制中对于 被绘制物体表面纹理表达模型的需求，反映了人们对模拟真实世界的不懈 追求，它在动画电影、数字游戏、虚拟现实等方面都有着重要应用价值， 并在高度真实感绘制、虚拟现实、科学计算可视化等领域具有重要理论价 值和广阔的应用前景。 1 1 论文研究背景 在计算机图形学中，对于自然场景中植物的建模方法和绘制技术的研 究一直是虚拟现实技术发展过程中的一个重点和热点问题，其目标是对植 物进行造型、材质表达以及真实感绘制，在最近十几年一直是极富挑战性 的工作。 植物往往由很多具有不同外形特征的器官组成，如茎、叶子、花、果 实等。对自然界中存在的真实植物的建模与绘制，与大部分人造形体的最 大区别在于：人造物体往往按照人们的审美和应用需求，在模拟过程中， 其几何形状可以任意控制，并易于被描述；而对于自然界的植物而言，其 几何形状和表面纹理的形成，则由其生长的自然规律所掌控，并不以人的 意志所掌控，这就使此项工作的难度大大增加。如本章中的图1 1 所示， 在自然场景中，植物的建模与绘制几乎是最能影响场景真实感和表现力的 重要组成部分。 因此，自然界中的真实植物，通常拥有比较特殊的几何形态和表面纹 理结构，利用传统的几何方法很难表达。叶脉作为植物树叶的组成部分之 一，其几何形状和表面纹理结构多种多样，这也组成了树叶外观的重要特 征。但是，由于目前生物学领域对叶脉形成过程在认识上的局限性，以及 现有计算几何理论和计算机图形学技术的限制，在真实感绘制领域中，大 部分绘制出来的植物场景很难对树叶表面的脉络结构进行很深入的表达。 这些情况不仅与自然界的真实情况不符，也大大限制了植物仿真技术的进 一步发展。因此，本文对作为自然场景中最主要组成部分之一的植物树叶 重庆邮电火学硕士论文第一章绪论 叶脉的几何结构的脉络特征进行了分析，对其建模方法和绘制技术做了较 深入的研究和改进，使树叶的绘制结果更加贴近自然真实，具有更强的真 实感。通过这些研究，本文的成果可帮助在虚拟现实应用中构建更加逼真 的自然植物场景，也可以让叶脉过程的模拟与绘制在游戏、影视等领域得 到进一步应用。同时，这些建模方法和可视化绘制过程也可以为树叶叶脉 的生物学研究提供基础性帮助。 图1 1 包含树叶的真实自然场景 1 2 植物建模与绘制技术研究现状 植物模拟是一种运用计算机图形学的理论与方法对植物形态结构和 生长过程进行仿真的技术。对植物的建模方法和绘制技术的研究已经有了 很长的历史，它跨越了生物学、数学和计算机图形学等领域【1 1 。早期的模 拟对象主要包括树木、森林、花卉等。自上世纪6 0 年代以来，人们在植 物建模与绘制方面的研究已经有了长足的发展，自然场景中植物的模拟和 绘制得到了广泛的应用。 最初的植物模拟是一种简单的形态模拟，只追求视觉上的真实感和美 感，后来人们开始关注到植物内部特性对形态的影响，直到把植物生长和 发育的外部环境和内在机理作为植物形态结构模拟的参数以后，人们才真 正认识到植物模拟的内容和意义。植物的形态结构与植物生长发育的环境 和生理机制密切相关，植物形态结构的计算机模拟有着广泛地应用前景。 例如在人工生命领域，生物学家希望借助可视化技术更方便地研究植物的 2 重庆邮电大学硕士论文第一章绪论 生长规律，在园林设计、艺术造型等领域的许多设计工作也有赖于有效的 植物结构形态表达方法。 目前关于植物建模方面的研究工作主要包括：l i n d e n m a y e r ( 1 9 6 8 ) 1 2 j 提 出了l s y s t e m s ，并与p r u s i n k i e w i c z ( 1 9 9 0 ) 将其用于树木等植物的建模； a o n o 和k u n i i ( 1 9 8 4 ) 【3 】引入枝间的相互吸引、抑制作用及其夹角的统计变 化机制，对子干在母干上的分布作了详细的估算：d er e f f e e ( 1 9 8 5 ) 1 4 j 等提 出严格的植物学模型；o p p e n h e i m e f ( 1 9 8 6 ) 【5 】运用分形技术对树木进行建 模；r e e v e s ( 1 9 8 5 ) 1 6 】提出基于粒子系统的方法仿真模拟森林；h o l t o n ( 1 9 9 4 ) 【7 】 提出基于s p l i n e 骨架的造型；w e b e r 等( 1 9 9 5 ) 【8 】从整体几何结构出发提出的 参数化建模方法对树木模型进行控制，并对森林的绘制进行了探讨； p r u s i n k i e w i c z 和l i n d e n m a y e r ( 1 9 9 0 ) 【9 】提出了重写( r e w r i t i n g ) 规则系统； l i n t e r m a n n 和d e u s s e n ( 1 9 9 9 ) 【1 0 】提出基于图结构的建模；f r e d e r i c 和 p r u s i n k i e w i c z ( 2 0 0 3 ) 【1 1 】提出了交互设计法；l e f c b v r e 和n e y r e t ( 2 0 0 2 ) 【1 2 1 、 f e d e r l 和p r u s i n k i e w i c z ( 2 0 0 4 ) 【1 3 】提出了基于物理的植物纹理模拟。以上方 法都取得了良好效果，植物建模的理论也随之日益成熟起来。目前在植物 模拟方法上主要有以下两种： 分形方法 分形是一种利用植物形态结构的分形性质( 结构自相似性) 产生植物图 形的方法。其中主要包括l s y s t e m s ，i f s ( 迭代函数系统) 法和d l a ( 扩散有 限凝聚) 模型等【1 4 j 。 1 ) l s y s t e m s 美国生物学家a r i s t i d “n d e n m a y e r 在研究植物形态的进化与构造时， 于1 9 6 8 年提出一种形式化语言，用来描述植物的结构和生长，称为 l - s y s t e m s 。1 9 8 4 年，a r s m i t h 首次将其引入到计算机图形学领域。 图1 2p r u s i n k i e w z 用l - s y s t e m 生成的花卉 3 重庆邮电人学硕士论文第一章绪论 2 ) i f s 迭代函数系统( i t e r a t e d f 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 ) 和 m f b a f n s l e y ( 1 9 8 5 ) 提出并发展的一种研究分形集的数学方法，后由 s t e p h e nd e m k o 等人将其公式化，并引入到计算机图形学领域。i f s 由一组 能满足一定条件的映射函数雌( 例如仿射变换) 及一组变换发生的概率异定 义：啦一 ( q ，号) ，f 一1 2 ，玎 其中q 控制着图形的结构和形状，只控制着每个 变换被调用的概率。利用i f s 生成植物图象的过程是对初始植物图象按照 已知概率选择函数而实施的一种迭代变换。 图1 3p r u s i n k i e w z 用i f s 生成的分形树 3 ) d l a 模型 d l a 模型，即扩散有限凝聚模型( d i f u s i o nl i m i t e da g g r e g a t i o n ) 模型， 是美国科学家t h o m a sa w i t t e n 和l e u 舳r dm s a n d e r 于1 9 8 1 年提出的。d l a 模型的基本方法是：在一个平面网格上选定一个静止的微粒作为种子，然后 在距种子较远的格点上产生一个微粒，并令微粒沿各方向做无规则的运 动。如果该微粒在行走过程中与生长着的凝聚体相接触，便永远附着在其 上；如果微粒走到边界上，就被边界吸收而消失。如此重复上述步骤，就 会以种子为中心形成一个不断增长的凝聚集团。利用d l a 和其修改的模 型可以对部分植物的形态结构进行计算机模拟，例如植物根系的生长过程 模拟和海藻类植物的形态结构模拟等。 粒子系统方法 粒子系统方法是由r e e v e s 在1 9 8 3 年提出，最早用于模拟火焰、烟雾 等，后逐渐被用于生成真实感的自然景物。其基本思想是采用许多形状简 单的微小粒子作为基本元素来表示自然界不规则的模糊景物，粒子的创 建、消失和运动轨迹由所造型的物体的特性控制，从而形成景物的动态变 4 重庆邮电大学硕士论文第一章绪论 化。由粒子系统表示的物体，要么是给定时刻粒子的位置，如火和焰火， 要么是粒子的一部分运动轨迹，如草和树。根据这种思想，可以用圆台状 粒子组成植物的枝条，用小球状或小立方体粒子组成叶，只要建立了这些 粒子组合或排列的模型，就可以实现植物形态结构的模拟，粒子在生命周 期中的变化就会反映出植物生长发育最终枯萎的过程。粒子系统的主要优 点是由于其几何图元是点，易于被变换和实现反走样。其主要缺点是景物 的表达涉及大量的基本图元，因此设计是一个反复试验和修改的过程。 图1 4r e e v e s 用粒子系统方法生成的森林场景 1 3 叶脉建模与绘制技术研究现状 对植物器官的建模与绘制已经有了很长的历史，它跨越了生物学、形 态遗传学和计算机图形学【1 引。早期的模型包括t u r k 【1 6 】的动物毛皮模型， d e s b e n o i t 等【1 7 l 的描述苔藓的d i f f u s i o n 1 i m i t e d 聚焦模型；l e f e b v r e 与 n e y r e t l l 8 j 以及f e d e r l 与p r u s i n k i e w i c z 【1 9 】的描述树皮纹理的物理模型。叶脉 被认为最能体现植物的自然美，地球上现存的植物树叶表现出高度多样和 详尽复杂的脉络结构。在涉及植物的场景绘制当中，叶脉几乎是必不可少 的组成部分。但是相比而言，叶脉模型和它们的生长过程很难理解【2 0 1 ，叶 片表面的脉络结构具有高度的复杂性，用传统的方法来模拟其形态比较困 难，这就使叶脉的建模与绘制成为特别有挑战性的问题。由于真实叶脉的 纹理非常复杂，所以当前用以比较判断叶脉模型是否接近真实的客观标准 非常有限【2 1 1 。 相关背景与术语 5 重庆邮电大学硕士论文第一章绪论 d e n g l e r 和k a n g ( 2 0 0 1 ) 1 2 1j 提出，叶脉模型与叶片形状密切相关，因此 在对叶脉进行建模时，必须考虑到叶片轮廓。j u d d ( 1 9 9 9 ) 等1 2 2 l 提出了用来 描述叶片形状的相关术语，如图1 5 所示。一个典型的树叶包含叶片、叶 柄和叶干。单叶只包含一个单独的叶，复叶的叶片可以分割成为几个单独 的小叶片。本文不考虑复叶，认为它们的脉络可以在每个小叶的层次上进 行建模。 整状齿状多裂状 掌状羽状 单叶 复叶 图1 5 描述叶片形状的相关术语 叶脉的生长也与叶片的生长密切相关。叶片生长可以用生长张量 r e r g ( r e l a t i v ee l e m e n t a r yr a t eo fg r o w t h ) 【2 3 】来刻画，它规定了在不同方向上 的无穷小表面区域的扩大。生长张量定义为无穷小的s ，在生长物体的点p 处，沿向量方向随时间变化的增长率，用公式表示为：尺e r g 工( p ) 一吉等。 如果它集中在边缘则生长是在边上的，如果它遍及整个表面，则它是散射 的【2 4 1 。如果漫射增长在所有方向上相等，则称为等方向性，否则称为各向 异性的。更进一步，如果生长张量在表面的各个点上是相同的，则称为是 一致，否则是不一致的。一致的各向同性生长称为等偏角的【2 5 1 。这些变化 如图1 6 所示。本文只考虑空白生长。 r 气 一 一 、 fr 、 ? r 、 、 ， fj | l l罗 k 舌 蕊 于a 厂 li 、 匿 i ；虽 拶 图1 6 叶片空白生长过程 ( a ) 样本叶，( b ) 空白生长，( c ) 一致等方向生长，( d ) 一致各 向异性生长，( e ) 非一致各向异性生长 6 重庆邮电大学硕士论文第一章绪论 h i c k e v 【2 6 j 提出了描述叶脉模型的术语，j u d d f 2 2 】将这些术语又简化了， 如图1 7 所示。一个基本的概念是叶脉顺序。一般，第一级叶脉是起源于 叶根部的最宽脉络，好的脉络具有逐步增高的次序。叶脉模型与植物的分 类群和叶片的形状相关。单叶子植物( 一般是草) 通常有近似平行的初等脉 络，这与高度拉长的叶片形状和叶底的宽度一致。有单叶片的双叶子植物 通常有羽状脉络，以一个起源于底部并延伸到叶子尖端的单独的基本脉络 为特征。有趾状叶片的双叶子植物一般具有掌状脉络。主脉支撑着次脉的 次序，这可以使分支深入到更高序的叶脉上。次脉和它的衍生者可以自由 结束，这可以产生一个开放式的类似树结构的叶脉模型，它们也可能相连， 形成环路特性的封闭模型。第三级和更高序的叶脉通常连接着第二级叶 脉，形成一个阶梯状或网状的叶脉模型。 图1 7 描述叶脉模型的相关术语 叶脉的生长机制与建模方法 最被广泛接受的脉络模型格式是运河网假说【2 7 l 。根据这个假说，脉络 生长是由在叶片里传播并造成脉络分化的信号所控制。至少这个信号的一 部分是植物荷尔蒙生长营养激素1 2 8 ，2 9 1 。植物生长营养激素产生于叶片并流 到现在的脉络中，这些脉络将它传输到叶的底部。在这个流动中，生长营 养激素被渠成窄径，在方式上类似于水在松软的地形上雕成河床。这些路 径逐渐分化为新的叶脉络。实验证据表明，生长激素应该是离散的。 g o t t l i e b ( 1 9 9 3 ) 1 3 0 】提出了直接插入新叶脉的方法。此方法的实现局限于 一些简单的假设，很难实现模拟真实的树叶。c o u d e r 等( 2 0 0 2 ) 【”l 提出了基 于生物力学的方法，利用可伸展物质的断裂传播来模拟叶脉生长，但此方 法缺少生物学支持。r o d k a e w 等( 2 0 0 2 ) 【3 2j 提出了基于粒子系统的方法。这 个方法与当前对叶脉形成的生物认识并不相关，想结合生物学知识来改进 7 重庆邮电人学硕士论文第一章绪论 效果是比较困难的。r o d k a e w ( 2 0 0 4 ) 【3 3j 又提出利用l s y s t e m s 建立叶脉模型 的方法，它以先后顺序产生主侧脉及更高序叶脉，不同序叶脉生长的先后 顺序性比较好，但不同步，最终造成不同序叶脉之间的耦合性不够好。 r u n i o n s 等( 2 0 0 5 ) 【3 4 】在s i g g r a p h 会议上提出了基于生物假说的建模方法，这 是一个反馈过程。叶片上随机均匀分布大量营养点，它们指示着叶脉的生 长方向，叶片的生长增加了现存叶脉之间的距离，新的营养点又可插入到 相应的空区中。通过将新的营养点连结到最近的老脉上就可以得到新的叶 脉。 1 4 论文的主要研究工作 论文的主要工作是对现有叶脉建模方法和绘制技术进行了深入的对 比和研究，认真总结了各自的优缺点，然后在此基础上提出了一个客观评 判建模方法优劣的“叶脉生长规则。接着，分别以r o d k a e w 的基于 l s v s t e m s 的建模方法和r u n i o n s 的基于粒子系统的建模方法为基础，对它 们进行了改进，分别得到了两种改进后的叶脉建模方法。最后，利用v i s u a l c + + 和o p e n g l 图形库对真实叶脉的生长过程进行了可视化模拟绘制并对 结果做了对比分析。具体包括以下三个方面： 对现有叶脉建模方法和绘制技术进行了深入的对比和研究，在总 结各自的优缺点的基础上，提出了一个客观评判建模方法优劣的“叶脉生 长规则 。 在r o d k a d w 的叶脉建模方法基础上，提出一种采用v o r o n o i 图来 绘制三级网状细脉的改进方法。实验结果证明，利用改进后的方法生成的 叶脉模型在形状上更加接近于真实叶脉的结构特征。 通过将l s v s t e m s 文法引入到r u n i o n s 的叶脉建模方法当中，提出 了一种改进后的建模方法，解决了原方法当中主侧脉生长比较慢的缺点； 作为整体算法中的一步，在用随机采样方法放置均匀分布的营养点时，采 用了一种新的d a r t t h r o w i n g 算法替代原r u n i o n s 方法中的b e s t c a n d i d a t e 算法，将时间复杂度从d ( 2 ) 改进为d ( l o g ) ，有效地提高了整体算法的 绘制速度。实验结果表明，改进后的方法能够以更快的速度生成具有更加 逼真效果的叶脉模型。 8 重庆邮电大学硕士论文第一章绪论 1 5 论文组织结构 本论文分为六章，各章的内容安排如下： 第一章：绪论。本章主要介绍了论文的研究背景、植物建模与绘制技 术的研究现状、叶脉建模与绘制技术现状，以及本文的主要研究工作和组 织结构。 第二章：相关理论和算法基础。本章主要介绍了与本文相关的一些理 论和算法基础，包括分形l s y s t e m s 的基本原理、v r o r o n o i 图的基本原理， 以及常用的一些叶脉建模方法。 第三章：对现有叶脉建模方法和绘制技术进行了深入的对比和研究， 认真总结了各自的优缺点，在此基础上提出了一个客观评判建模方法优劣 的“叶脉生长规则，这也是本论文的核心理论创新之一。 第四章：在r o d k a d w 的叶脉建模方法基础上，提出一种采用v o r o n o i 图来绘制三级网状细脉的改进方法，并仿真实现了这一方法。最后分析比 较了改进后的结果，并得出了结论。 第五章：通过把l s y s t e m s 文法引入到r u n i o n s 的叶脉建模方法当中， 提出了一种改进后的叶脉建模方法，解决了原方法当中主侧脉生长比较慢 的缺点。而且在随机放置均匀分布的营养点时，采用了一种新的 d a r t t h r o w i n g 算法替代原r u n i o n s 方法中的b e s t c a n d i d a t e 算法，将时间复 杂度从d ( 2 ) 改进为d ( l o g ) ，有效地提高了整个算法的绘制速度。最后 对该方法进行了仿真实现，分析对比了实验结果，并得到了结论。 第六章：结论及未来的工作。本章总结了本文所做的工作，给出了总 体结论，并指出下一步的研究内容。 9 重庆邮电大学硕十论文第二章相关理论和算法基础 第二章相关理论和算法基础 近年来，随着计算机软硬件技术的迅猛发展，真实感自然场景的绘制 成为计算机图形学领域中的研究热点。在真实感自然场景绘制当中，包含 真实感植物场景的绘制是一个研究热点。与真实感植物场景绘制密切相关 的是植物的建模与绘制，其中，叶脉的建模与绘制又是其中一个非常重要 的方面。 本章的结构如下：第一节，对分形l s y s t e m s 理论进行了详细介绍； 第二节，对v b r o n o i 图做了介绍：第三节，对几种重要的叶脉建模方法进 行了详细介绍；第四节介绍了在叶脉建模过程中涉及到的随机点的采样算 法；本章的最后部分对以上作了分析和总结。 2 1 分形l - s y s t e m s 原理介绍 1 9 9 0 年，p r u s i n k i e w i c z 出版了他的著作植物的算法美【引，详细地 介绍了如何将l i n d e n m a y e r 所提出的l s y s t e m s 用于树木及其它植物的建 模。 l s y s t e m s 的核心概念是重写( r e w r i t i n g ) 。重写是使用一系列重写规则 或生成式，通过连续地替代简单原始物体的某部分来达到定义复杂物体的 目的。l s v s t e m s 与以往重写机制的本质区别是应用规则的方法不同，以前 的重写机制都是顺序地应用规则，而l s y s t e m s 是并行的，且同时替换字 符串中的相关字符。它使用形式语言的方法来描述植物的生长过程。 l s v s t e m s 作图的基本原理是“字符串改写”。首先用字符串表示复杂的 自相似物体，然后根据一组改写规则或产生式依次替换一个简单初始物体 的每一个部分形成最终的整体字符串。在具体生成分形图形的过程中，要同 时结合使用“改写规则”和“龟形图法”两种方法。“改写规则”是形式化的描 述，首先从初始字符串集合( 称为公理) 中任选出一个字符串，并在产生式 集合中选择一个适当的产生式，即改写规则，以初始字符串为前导代入产生 式进行字符串改写，得到一个新的字符串后继，并以此新字符串为前导重新 代入产生式生成下一个后继字符串，以此迭代改写多次，直到产生最后的字 符串，由这个字符串生成对应的图形就是l s y s t e m s 产生的分形图。最后再 对此字符序列进行几何解释( 如表2 1 ) ，就能生成非常复杂的分形图形。目 1 0 重庆邮电大学硕士论文第二章相关理论和算法基础 前常用的l s y s t e m s 主要可以分为以下几种。 表2 1 二维l s y s t e m 的绘图符号及其几何解释 f 在当前方向上前进一步，并且画线 + 逆时针旋转给定角度 顺时针旋转给定角度 【 将当前的位置信息( 点的坐标及前进角度) 压入堆栈 】 将最近“】”时刻的信息出栈 确定性l - s y s t e m s 最简单的l - s y s t e m s 是确定的且上下文无关的，被称为d o l - s y s t e m s 。 令矿表示字符集，y 表示矿上所有字符串的集合，y + 是y 上所有非空字符 串的集合。一个字符串o l s y s t e m 是一个有序的三元组g 一 。其中 是一个非空字符串集合，称作公理，pc y y 。是规则式的有限集合，规 则产生式( 口，工) p 写作口_ 石，字母口和单词x 分别称作规则产生式的前驱 和后继。规定对任何字母口矿，至少存在一个字符串集合z y ，使得口_ x 。 若对给定的前驱口y 无明确解释的产生式，则规定口_ 口是个特殊的产生 式，且属于p 。若对每个口y ，当且仅当恰有一个z y ，使得口一x ，那么 就说此o l s y s t e m 是一个确定的，记为d o l s y s t e m s 系统。依据 d o l s v s t e m s 系统的原理，按照一定的重写规则，并加以参数控制，即可 模拟植物的各种形态及其生长过程。以下是一个d o l s y s t e m s 的例子： ：s 墨：s - 州睨 最：彳_ 脚 b ：b 呻玎 最终生成的字符串序列为黝脚。 随机l s y s t e m s 使用d o l s y s t e m s 所得到的植物造型都是确定的，为了能在整体上保 留一种植物的主要特性而又使其细节具有不同的随机效果，可以使用随机 l s y s t e m s 。一个随机l s y s t e m 是一个有序的四元组q 。 ，其中 y 、p 的定义与2 1 3 相同。函数石：p 呻( 0 ，1 】，被称为是概率分布，它 指明了某个规则式将以多大的概率来进行替换。这里要求对任一字母 口y ，所有以口为前驱的生长规则式的概率之和必为1 。以下是一个随机 l s v s t e m 的例子： 丘，：f 重庆邮电人学硕士论文第二章相关理论和算法基础 异：f 一，【+ f 】f 【一f 】f 最：f 呻f 【+ f 】， 只：f _ f 卜f 】， 上下文相关l s y s t e m s 以上两种l s y s t e m s 的规则式是上下文无关的，在应用时不用考虑它 的前驱是什么。但是，规则式的应用可以依赖于它的前驱。在绘制植物时， 若植物的生长依赖于某些先决条件时，这种依赖于前驱的规则式对于描绘 植物不同器官间的相互作用非常重要，它们被称为上下文相关l s y s t e m s 。 目前有很多种上下文相关l s y s t e m s 的扩展形式。2 l s y s t e m s 使用规则式 口f 口，_ x ，其中口是直接前驱，当且仅当口的前驱是口f ，后继是口，时， 可以生成x 。以下是一个上下文相关2 l s v s t e m 的例子： ：s 只：s _ a 鲋 最：彳 r - 【+ 用珂】 只：彳 f _ f 只：口_ 【一尉f 】 只：z 呻f 参数l s y s t e m s 尽管带有“龟形图法”解释的l s y s t e m s 可以产生从抽象分形图到具有 分支结构的各种各样植物，但它的建模功能十分有限。最重要的原因就是 所有画线的增减必须是最小单元线段长度或角度的整数倍，这就造成很多 非整数长度的线段无法表示。为了解决这些问题，p r u s i n k i e w i c z 和h a 船n 给出了参数l s v s t e m s 的定义。 参数l s y s t e m s 操作于带参数的单词上，这些单词由与参数相关的字 符串模块组成。字母属于字母表y ，参数属于实数集合尺。一个包含彳y 和参数口。，口：，口。r 的字符串模块可以表示为彳( 口。，口：，口。) 。每个模块都 属于集合m ；y r ，其中r 是所有有限参数序列的集合。 单词中所出现的具有真实值的实际参数，对应于l s y s t e m s 产生式中 所定义的形式参数。令是表示形式参数的集合，c ( ) 和e ( ) 分别是由中 字母所表示的逻辑表达式和算术表达式。这两种类型的表达式分别由形式 参数和数值常量构成。同时还使用了算术运算符+ 、一、宰、；指数符号 ： 关系符号 、= ；逻辑运算符! 、& 、i 和圆括号等。c ( ) 和( ) 表示用 中的参数正确构造的逻辑和算法表达式集合。 1 2 重庆邮电火学硕士论文第二章相关理论和算法基础 一个参数l s y s t e m 可以定义为一个有序的四元组gt ，其 中其中y 是字母表，是的所有形式参数的集合，尺) + 被称为公理， 是一个非空参数单词，p c 缈) c 仨) e ( ) ) 是规则式的有限集。以 下是一个参数l s y s t e