（运筹学与控制论专业论文）分形造型中的骨架截集技术.pdf

硕+ 学位论文 摘要 自1 9 7 5 年曼德勃罗( b e n o i tb m a n d e l b r o t ) 提出分形的概念后，分形几何学的研 究受到了广泛的重视，尤其是在自然景物的模拟方面，分形造型展示了其独特的 优势，成为当今研究者们的热点话题之一。 迭代函数系统( i f s ) 是分形造型的典型方法，其吸引子通常都是分形。给定 一个迭代函数系统，吸引子是唯一的，与迭代的初始集无关，并且需要经过无限 次迭代才能得到。然而在自然景物的模拟中，通常不需要迭代函数系统的吸引子， 只是考察迭代函数系统经过有限次迭代的结果。 在进行自然景物模拟时，特别是在构造树木的造型中，凝聚迭代函数系统是 一种可选的造型方法，因为它经过有限次的迭代产生的效果与迭代的初始集有关。 使用不同的初始集，可以得到不同的造型。 本文在研究了分形基本理论和分形造型发展现状的基础上，基于凝聚迭代函 数系统、曲线理论和细分方法，提出了一种骨架截集分形造型技术。该技术主要 包括两条主线：一是先由骨架和截集得到迭代函数系统的初始集的外轮廓，然后 对外轮廓进行曲化；二是先对骨架进行曲化，然后利用截集得到初始集的外轮廓。 外轮廓曲化主要采取两种策略：逼近策略和插值策略。 文中以树木的模拟为例，给出了在外轮廓曲化时使用不同的曲化方法所得到 的初始集，其中包括控制点样条、型值点样条和细分方法，并给出了利用这些初 始集迭代若干次的效果图。结果表明，利用该技术实现了树木表面的光滑处理， 使得到得模拟效果更加逼真。由于使用不同的表面曲化方法，可以得到不一样的 初始集，因此可以迭代生成丰富多姿的树木，实现了分形造型的多样化。 关键词：分形；骨架；截集；曲化 分犁造型中的骨架截集技术 i i ii i 。i i i i,iil i 曼皇量 a b s t r a c t a f t e rm a n d e l b r o tp u tf o r w a r dt h ec o n c e p to ff r a c t a l ，t h er e s e a r c ho nf r a c t a l g e o m e t r yh a da t t r a c t e de x t e n s i v ea t t e n t i o n s ，e s p e c i a l l ya t n a t u r es c e n e r ys i m u l a t i o n f r a c t a lm o d e l i n gd i s p l a y si t su n i q u ea d v a n t a g ea n db e c o m eo n eo ft h ep o p u l a rt o p i c s i t e r a t e df u n c t i o ns y s t e m ( i f s ) i st h et y p i c a lm e t h o do ff r a c t a lm o d e l i n g i t s a t t r a c t o ru s u a l l yi sf r a c t a l i fg i v e na ni f s ，t h a ti t sa t t r a c t o ri su n i q u e ，w h i c hi s i n d e p e n d e n tw i t ht h ei t e r a t i v ei n i t i a ls e t ，a n do b t a i n e db yi n f i n i t ei t e r a t i o n b u ta tt h e p r o c e s so fn a t u r a ls c e n e r ys i m u l a t i o n ，u s u a l l yd o n tn e e dt h ea t t r a c t o ro fi f s ，j u s tn e e d t h er e s u l to ft h ef i n i t ei t e r a t i o n w h e nw es i m u l a t et h en a t u r a ls c e n e r y , e s p e c i a l l yo nt r e e sm o d e l i n g ，c o n d e n s a t i o n i t e r a t e df u n c t i o ns y s t e mi sab e t t e rm e t h o d ，b e c a u s et h er e s u l tb yf i n i t ei t e r a t i o nh a s r e l a t i o nw i t hi n i t i a ls e t d i f f e r e n tm o d e l i n gw e r eo b t a i n e db yd i f f e r e n ti n i t i a ls e t t h i st h e s i sb a s e do nt h ec o n d e n s a t i o nr e r a t e df u n c t i o ns y s t e m ，c u r v et h e o r ya n d s u b d i v i s i o nm e t h o d ，p u tf o r w a r daf r a c t a lm o d e l i n gt e c h n o l o g yb ys k e l e t o na n dc u t - s e t t h i st e c h n o l o g yh a st w o m a i nm e t h o d s t h eo n ei so b t a i n i n gs h a p eo u t l i n eo ft h ei f s i n i t i a ls e tf i r s t l y , a n dt h e nb e n d i n gt h eo u t l i n e ；t h eo t h e ro n ei sb e n d i n gt h es k e l e t o n f i r s t l y , t h e ng e tt h eo u t l i n eo ft h ei n i t i a ls e tb yu s i n gc u t s e t t h e r ea r et w om a i n s t r a t e g i e si nt h ep r o c e s so fb e n d i n g ：a p p r o x i m a t i o na n di n t e r p o l a t i o n t h et h e s i st a k et h et r e ef o re x a m p l e ，p r e s e n t sd i f f e r e n ti n i t i a ls e tb yd i f f e r e n t b e n d i n g t h em e t h o dc o n c l u d e sc o n t r o l - p o i n ts p l i n e ，d a t a p o i n ts p l i n ea n ds u b d i v i s i o n t h ep a p e ra l s og i v e sm a n ye f f e c tp i c t u r e so nt h er e s u l tb yu s i n gt h i st e c h n o l o g y t h e r e s u l ts h o w , t h a tb yu s i n gt h i st e c h n o l o g y , w er e a l i z e dt h es m o o t hp r o c e s s i n go ft h e t r e e ss u r f a c e ，a n dm a k et h es i m u l a t i o ne f f e c tm o r ef i d e l i t y b e c a u s ed i f f e r e n ti n i t i a ls e t c a ng e tb yu s i n gd i f f e r e n tb e n dm e t h o d ，s ow ec a nm a k ev a r i o u sf o r m sb yi t e r a t i o na n d r e a l i z et h ed i v e r s i f i c a t i o no ft h ef r a c t a lm o d e l i n g k e yw o r d s ：f r a c t a l ；s k e l e t o n ；c u t s e t ；b e n d i n g 硕十学何论文 插图索引 图3 1 插值的曲线1 5 图3 2 逼近的曲线1 5 图3 3h e r m i t e 曲线1 7 图3 4 凸包性质2 0 图3 5 三次均匀的b 样条曲线2 2 图3 6 准均匀三次b 样条曲线2 3 图3 7 三次分段b 6 z i e r 曲线2 3 图3 8d e b o o r 算法的推导过程2 4 图3 9d e b o o r 算法的几何意义2 4 图3 1 0 顶点替换2 5 图3 1 1 插入一个节点t e i t 3 ，】2 5 图3 1 2c h a i k i n 细分方案2 6 图3 1 34 一点细分法2 6 图3 1 4 反射点p 一，的生成过程2 6 图4 1s i e r p i n s k i 三角形2 7 图4 2 不同凝聚集迭代相同次数得到相同的分形图2 8 图4 3 凝聚集的骨架与截集2 9 图4 4 外轮廓的求取3 1 图4 5 二次自然样条曲化效果3 2 图4 6 插入控制点的自然样条曲化效果图3 2 图4 7 中间控制点处的切线处理效果图3 3 图4 8 三次h e r m i t e 插值曲化效果图3 3 图4 9b 6 z i e r 曲线效果图3 4 图4 1 0 一种插值细分方法3 4 图4 1 1 三次细分效果图3 5 图4 1 2 骨架与截集3 5 图4 1 3 骨架曲化效果图3 5 图4 1 4 分叉现象3 6 图4 1 5 插入控制点后骨架曲化效果图3 6 图4 1 6 利用截集构造曲化骨架的外轮廓3 6 图4 1 7 曲化骨架的外轮廓3 7 图4 1 8 树木模拟效果图3 8 m 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：样 吼节月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服 务。 作者签名： 导师签名： 日期 日期 年乡月少日 年石月夕日 硕十学位论文 1 1 课题的研究背景 第1 章绪论 欧式几何的主要描述工具是直线，平滑的曲线，平面及边界整齐的平滑曲面。 在描述一些抽象图形或人造物体的形态时这些工具是非常有力的，然而对一些复 杂形态的自然景物就显得无能为力了，诸如变换飞渡的云、连绵起伏的群山、微 波粼粼的海浪等，原因是从欧氏几何的角度来看，它们是极端不规则的。 长久以来，自然界景物多姿多彩的几何形态吸引了众多学者的眼球。学者们 从不同的角度对一些结构复杂、形状不规则的景物做了研究并发现：自然界中许 多景物都蕴含着自相似的结构，即景物的每一部分的形态是整体形态的缩影。但 是都没有提出一种切实可行的解决方法。直到2 0 世纪7 0 年代，美籍法国数学家 m a n d d b r o t 提出分数维的概念，人们才有了一种用来描述那些不规则、欧氏几何无 法描述的复杂景象的通用方法，并创立了分形几何学。分形几何的提出，为研究 复杂形态提供了全新的角度，使人们从无序中重新发现了有序，许多学科像物理、 经济、气象等都将分形几何学作为解决难题的新工具。计算机图形学也从中受到 启发，并形成了以模拟自然界复杂景象、物体为目标的分形造型。 分形造型是利用分形图形的自相似性，采用各种模拟真实图形的模型，使整 个生成的景象呈现出细节的无穷递归性质的方法。所生成的景物中，可以有结构 性较强的树，也可以有结构性较弱的火、云、烟，甚至可生成有动态特性的火焰、 浪花等，但关键是要有一个合适的模型来描述上述景物。 多年来，人们研究出了不少的分形造型模型，诸如随机插值模型、粒子系统 模型、正规文法模型和迭代函数系统模型等，使分形在计算机造型技术方面的应用 越来越广泛，为人们对自然界中具有复杂形状、结构或功能的事物的定量刻画和 描述提供了新的方法，推动了造型技术的发展。 1 2 分形基本理论与课题研究意义 1 2 1 分形定义及特征 数学家m a n d e l b r o t 于1 9 7 5 年提出分形( f r a c t a l ) 一词，含义是断裂和碎片。同 年他的专著分形：形状、机遇和维数的问世，标志着分形理论的诞生。分形 几何是研究在标度变换下不变测度性质的一门学科，它能为非线性问题提供外在 几何表现或内在的几何表示。 在m a n d e l b r o t 最初的论述中，定义分形是其h a u s d o r f f 维数严格大与其拓扑维 分犁造础中的骨架截集技术 曼曼量量皇曼曼皇量舅i 一一； i 舅置皇曼皇曼曼曼曼皇蔓皇曼曼曼鼍曼曼量量舅 数的集合，但有些集合( 如p e a n o 曲线) 很明显是分形图形，却被这个定义排除在 外。后来英国数学家i cf a l c o n e r 在其所著分形几何的数学基础及应用中认为， 称集合f 是分形，是指它具有下面典型的性质： ( 1 ) f 具有精细的结构，即在任意小的尺度下，它总有复杂的细节； ( 2 ) f 是不规则的，它的整体与局部都不能用传统的几何语言来描述； ( 3 ) f 通常有自相似性，这种自相似可以是近似的或统计意义的； ( 4 ) 一般情况，f 的某种定义下的分形维数大于它的拓扑维数； ( 5 ) 在大多数情形下，f 以非常简单的方法确定，可由递归过程产生。 “分形”本身是名词，表示有自相似或自仿射性的结构。分形是介于无序与有 序、微观与宏观、简单性与复杂性、随机性与确定性之间的一种过渡状态。与数 学上的分形相比，自然界中实际存在的分形具有两个明显的特征： ( 1 ) 自然界中的分形仅在一定范围，一定层次中才表现出分形特征，这个具有 分形特征的范围叫“无标度区”。在无标度区外，自相似性不复存在，系统也就没 有分形规律了。此外，同一自然现象可能出现多个无标度区，在不同的无标度区 上可能出现不同的分形特征。 ( 2 ) 数学中的分形具有无限嵌套的层次结构，而自然界中的分形只有有限层次 的嵌套，且是具有自相似分布特征的随机现象，并不像数学上的分形那样单纯、 均匀和一致，必须从统计的角度考虑、分析和处理。 1 2 2 分形维数 分维( f r a c t a ld i m e n s i o n ) 又叫做分形维数，是分形理论中的核心概念与内容， 它是对非光滑、非规则、破碎的等等极其复杂的分形客体进行定量刻画的重要参 数，它表征了分形体的复杂程度和粗糙程度【。整数维数只代表几何对象占有或填 充空间能力连续变化过程中的质变的几个关节点，而分维代表不同关节点之间的 中介过渡态。新的维数理论采用条块分割与标度变换相统一的手段，寻找出众多 特征尺度之间的规律性联系，得出客体存在形式的维数。 由于各种千姿百态的空间形态，无不渗透着分数维的特征。所以为了描述复 杂的、其内部具有众多层次的事物，例如海岸线、蕨类植物的形状、混沌运动的 相空间轨道，必须采用分形维数。由于自然界的分形是种类繁多的，对不同的对象 需用不同的测量方法，因此，分维也具有多种形式的定义。下面介绍两种常用分维 数的定义。 1 2 2 1h a u s d o r f f 维数 定义1 1 考虑欧氏空间r “的子集u ，定义u 的直径妙l 为 i u i i is u p i x y i ：工，y u 2 硕 学位论文 即u 中任意两个点的最大距离。如果集合fcu 弘，且的最大直径为6 ，即 0 0 ，定义 日；( f ) 一i n f xu ；i p ： 弘) 是f 的一个6 一覆盖) 并约定空集i 彩i p ；0 。当6 递减时，上式的下确界是非递减的。记 h p 伊) 一! i m 钟俨) 则称日p ( f ) 为集合f 的p 维h a u s d o f f f 测度。 定理1 1 对于任意给定的集合f 和6 p 且 阢) 是f 的一个6 一覆盖，则 阢；善i 阢l ，l f ，舒卜9 善阿i p 从而有碰( f ) s 6 - p h ；( f ) ，令6 呻0 ，若o 耐。 令n 为正整数，对每个p ，q = 0 ，1 ，m ，计算轨道 ，“( z 胛) ) 时，一不能超过。 如果当n = n 时， ，“g 舶) ) 的轨道点集没有落入y ，则转向下一个( p ，q ) 值，否则 当刀- = n 时，存在第一个整数n 使，“q 阳) y ，则相应于z w 的像素点就要被点上一 个颜色，然后计算转向下一个( p ，留) 。这种画图算法称为逃逸时间法。 如果把逃逸时间算法运用到复动力系统 c ；厂 ，比如，：c 啼c 定义为 厂0 ) ；z 2 ，w 仍然为一个中心在原点，最小边长大于1 的矩形，y 定义中的r 选 得足够大。则我们将得到一个集合f 一仁e c ：l z i s l ) ，它由许多不同颜色的同心环 所组成，像这样的f 集称为伴随与多项式变换厂q ) = z 2 的填充j u l i a 集只1 2 1 。 1 2 3 2 粒子系统模型 粒子系统是w tr e e v e s 于1 9 8 3 年提出的一个随机模型。它是用大量的粒子 4 硕十学位论文 图元来描述景物。粒子可以随时间推移发生位置和形态变化。每个粒子的位置、 取向及动力学性质都是由一组预先定义的随机过程来说明的，是一种基于动态随 机生长原理算法的模型。每个粒子都有一组随机取值的属性，如初始位置、初速 度、颜色及大小。该模型是由粒子刻画的，因而还适合描述动态变化的火焰、烟、 和被风吹动的草，后来又用该模型来模拟草丛、森林等全景要求高的景象【3 】。 1 2 3 3l - 系统模型 该模型是1 9 8 4 年a l v y r a ys m i t h 为模拟植物而引入的。这是一种字符重写系 统或形式化语言方法，通过对植物对象生长过程的经验式概括和抽象，构造公理 与产生式集，生成字符发展序列，生成结构性强的植物的拓扑结构，再通过进一 步几何解释来形成逼真的画面。 目前较为常用的有： ( 1 ) 主要利用“乌龟行走式”解释算法模拟分形几何图形的确定性l - 系统。 ( 2 ) 克服了确定性l 一系统只能生成规则分形图形的局限，可构造随机的植物 拓扑结构的随机l _ 系统。 ( 3 ) 主要是用于表现植物生长过程中的外因发展特征的上下文相关l - 系统。 ( 4 ) 在形式化公理与产生式中引入了交流单元，用于传送、调整环境和植物 两方的相互信息，以实现植物与环境并发过程的模拟研究的开放式卜系统。 ( 5 ) 主要用来模拟植物的连续生长过程的时变l - 系统。 1 2 3 4 迭代函数系统模型 迭代函数系统理论是把自相似性或自仿射性、层次的多重性和不同层次的规 则的统一性归纳为仿射变换。认为几何对象的全貌与局部，在仿射变换的意义下， 具有自相似结构，只不过存在图形比例放大缩小，旋转和平移等。工作原理是先 选定几何对象的整体，再选定若干仿射变换，然后将整体形态变换到局部，并将 这一过程迭代的进行下去，这样就得到了满意的造型。但用于i f s 的仿射变换必 须为压缩仿射变换，以确保i f s 最终是收敛的。i f s 应用于计算机图形领域，可以 产生许多具有无穷细节、精致纹理的图形。尤其是在树木形态模拟方面，i f s 方法 可以表现出树木整体形态的不规则性以及整体与局部细节的自相似性，较之以规 则形状构图的传统方法更具优势( 关于这方面的内容将在第2 章作详细介绍) 。 1 2 4 课题研究意义 ( 1 ) 分形形态是自然界普遍存在的，研究分形是探索自然界复杂事物的客观 规律及其内在联系的需要，它为描述自然界中传统欧几里德几何学所不能描述的 一大类复杂无规则的几何对象提供了新的概念和方法。 ( 2 ) 分形造型以模拟复杂景物为目的，研究骨架截集技术在分形造型中的应 5 分犁造犁中的骨架截集技术 用，为分形造型提供了一种可行的方法，促进了分形造型的发展。 ( 3 ) 凝聚i f s 是分形造型的一种基本模型，结合骨架截集技术进行自然景物 的模拟，为自然景物的真实感模拟技术的发展添砖加瓦。 ( 4 ) 利用曲线曲面理论和细分方法，对骨架和外轮廓边进行曲化，并将其应 用的分形造型中，这在一定程度上推广了曲线曲面和细分方法的应用。 1 3 课题研究的内容 ( 1 ) 研究分形以及迭代函数系统的基本理论。 ( 2 ) 研究曲线理论和细分方法，包括样条曲线、b 6 z i e r 曲线、b 样条曲线、三 次h e r m i t e 曲线等几种逼近和插值细分方法。 ( 3 ) 研究基于骨架截集的外轮廓计算、外轮廓的曲化、骨架的曲化和曲化骨 架的外轮廓构造。 ( 4 ) 研究凝聚i f s 的性质，将骨架截集技术与凝聚i f s 结合起来，实现分形造 型的多样化。 1 4 课题国内外研究现状 迭代函数系统是分形造型的典型模型，利用分形几何学的自相似性，为不规 则的复杂景物的图形生成提供了可行的方法。近年来，国内外学者从各个方面对 迭代函数系统了大量的研究，如i f s 吸引子图的生成算法【4 9 】、i f s 分形图的交互 式控制方法【1 叭4 1 。 在自然景物的模拟研究方面，程学珍等人对基于分形的自然景物描述方法进 行了比较【1 5 】，研究了基于分形的3 种造型模型：递归模型、i 广系统模型和i f s 模 型，并得到了满意的实验效果，还说明了i f s 模型适用于具有较多细节结构的景 物模拟，i ，系统模型适用于生成具有较强拓扑结构的景物，而递归模型适用于具 有严格自相似的景物模拟。 章立亮在凝聚i f s 的基础上，提出了一种含可控阵列因子的类凝聚i f s l l 6 1 ，实 现了用计算机仿真模拟具有全景效果的景物。郝小琴将景物模拟推广到三维，研 究了森林景物的三维迭代函数系统的建模技术f 1 7 1 ，给出了基于树木的分枝模式与 叶序模式的三维i f s 建模法以及相应的图形绘制算法。郑洪源将分形应用到植物 的三维特征化造型中【1 8 j ，论述了对传统分形造型方法的改进，阐述了针对自然界 中不同植物种类的特征进行个性化造型的理论基础、数据结构、算法及步骤。王 琰等人将植物的分支模式分成单轴分枝和合轴分枝，研究了随机三叉树的分形模 拟【”之o l ，郝卫亮等人用圆台来生成树枝，并通过参数控制生成不同的树木形态【2 1 1 。 上述的景物模拟研究中，植物的枝条都是笔直的，显然不符合自然规律。模 6 硕十学何论文 拟植物枝条的自然弯曲，是虚拟场景中的难点。目前主要有两种方法：设定枝条 各片段弯曲角度方法和参数曲线拟合方法。p r u s i n k i e w i c z 和w e b e r 分别给出了不 同的算法来绘制弯曲的枝条，前者是分别给出所有枝条的弯曲系数，即组成各枝 条片段的初始方向矢量及整个枝条的趋向性矢量，然后通过计算这两个矢量的乘 积得到每个片段的最终方向矢量，这样就得到了弯曲的枝条f 2 2 1 ；后者是对植物的 每个枝条设定两个偏转角度，枝条的前半部和后半部分分别以不同的偏转角度向 下和向上偏转，模拟出s 型枝条形状瞄】。虽然上述两种方法都可以绘制出形象逼 真的枝条，但计算量很大，影响绘制速度。曾兰玲等人提出了一种改进方法，用 于三维梨树的建模1 2 4 1 。该方法采用参数曲线拟合技术绘制末端弯曲枝条，然后用 分段技术改善树干的弯曲程度，段与段之间可以加入随机弯曲系数，形成自然形 态树干。对主干和侧枝采用不同数目的分段和不同大小的弯曲系数，更好的表现 了树干的自然形态，真实感增强。韩云萍等人将分形与计算机图形学相结合，研 究了基于自由曲面与迭代函数系统的景物模拟【2 5 1 ，采用b 样条曲线构造果实的外 型轮廓，利用自由曲面( b 样条曲面) 绘制山坡，最后模拟出了种植果树的山坡， 效果自然逼真。 将分形技术和骨架截集相结合进行自然景物的模拟，目前在国内外研究较少。 周文利讨论了基于b 样条曲线的植物模型建立方法【冽，将植物的几何模型分为骨 架和枝节两部分，前者是根据植物枝节的生长和死亡的模拟算法来实现的，后者 利用枝节与枝节的自相似性，由细枝和叶片构成。 赵春江等人研究了骨架模型在玉米根系可视化中的应用1 2 7 】，采用交互式骨架 模型确定了玉米根系的拓扑结构，利用带参数的随机l 系统产生一级侧根，并结 合其它技术实现了玉米根系的三维交互式设计。文中所述方法提高了植物根系模 拟的真实感，对植物可视化建模具有一定的影响。 曲线是计算机图形学的基本元素之一，可以提供比直线更平滑、更连续的图 元。曲线的表示方法最著名、最实用的是b 6 z i e r 技术幽j ，但也有不足的地方：一 是它并没有通过所有的控制点( 端点除外) ；二是曲线的自由度会随着控制点数的 增加而增大。 1 9 7 2 年，g o r d o n 等人拓展了b 6 z i e r 曲线，用b 样条函数代替b e m s t e i n 函数， 从而构造了等距离节点的b 样条曲线，改进了b 6 z i e r 特征多边形与b e r n s t e i n 多项 式次数有关，且是整体逼近的弱点。国内外研究b 样条的相关课题的有很多，如 b 样条曲线的节点插入算法1 2 9 - 3 0 1 、b 样条曲线的升阶问题【3 1 。3 剐、b 样条曲线形状分 析与控制f 3 9 屯】和b 样条曲线的应用【4 3 删等等。 在b 样条曲线的生成方面，已有很多文献进行了讨论【4 5 却j 。常用的有逐级线 性插值的d e b o o r 算法和基于b 样条基函数细分的算法。王增波等人把b 样条曲 线分成了4 种类型【删，并对它们的特点和实现方法进行了阐述，还给出了完整的 7 分型造帮中的骨架截集技术 生成各种b 样条曲线的代码。李郝林根据遗传算法，讨论了测量数据的b 样条曲 线逼近算法i 钙1 ，并采用了端点插值的三次非均匀b 样条算法逼近测量数据点来保 证曲线的光顺性和曲线在端点处的控制性。褚标等人提出了一种基于增量方法的 均匀b 样条曲线快速生成算、法【4 9 1 ，该算法在计算出曲线段上首端点后，曲线段上 其余各点的计算只用到加法运算，效率较高。王三福等人讨论了平面数据点集的 整体b 样条曲线的逼近【矧，给出了逼近算法和逼近精度的判别。林意等人讨论了 过控制点的二次和三次b 样条曲线f 5 m 引，这种曲线可通过调整控制顶点进行形状 修改并始终通过控制点，在保证精度的同时，不必作反求计算，修改曲线形状的 速度很快。 细分是构造曲线曲面的一种相对较新的方法，它的魅力之处就在于它可以作 为非连续表面和连续表面之间的桥梁。通常细分方法分为两种：逼近法和插值法。 c h a i k i n 提出了一种割角细分法1 5 引，这种细分法采取的是逼近法，即每执行一 次细分，就扔弃了原来的顶点，并将新顶点连接起来作为下一次细分的原顶点。 虽然这种方法能快速简单地生成平滑曲线，也能生成二次b 样条曲线，但是不能 直接得到过控制点的曲线。 通常细分是一个不断加细修正的过程，通过双重细分方法会得到一系列的控 制多边形来逼近细分曲线。j o y 的在线几何建模【5 4 j 换了另一种角度来看待控制多边 形上点的产生，它把这些点分顶点和边点两类，并直接计算这些点。该方法非常 有用，因为这能够直接计算极限曲线上的点而不经过加细修正的过程。 利用插值策略进行细分，会首先保存前一个细分阶段的所有点，然后在原先 的多边形上进行插值得到增加新的点。最早的插值细分法由d y n 等人提出的四点 b i n a r y 插值细分方法【5 5 1 ，该方法用四个最近的点来生成一个新点。当细分参数在一 定范围内取值时，细分曲线可达到c 1 连续。在此基础上，许多改进的b i n a r y 插值 细分法被提出，以拓展四点b i n a r y 插值细分法的曲线造型能力【5 6 - 5 a 。一些新的插 值细分法也陆续被提出1 5 9 柳j 。 1 5 论文的组织结构 第一章论述了课题的研究背景、分形基本理论与课题研究意义、课题的国内 外研究现状和研究内容。 第二章论述了迭代函数系统的基本思想和理论以及各类i f s ，其中包括凝聚 i f s 、带参数i f s 和再归迭代函数系统( r i f s ) 。 第三章论述了曲线的基本理论和细分方法。 第四章论述了骨架截集造型技术，主要包括外轮廓的求取、外轮廓的曲化、 骨架的曲化、曲化骨架的外轮廓构造和基于凝聚i f s 的骨架截集造型方法。 最后为课题的总结与展望。 8 硕十学位论文 2 1i f s 的基本思想 第2 章迭代函数系统 分形图形具有自相似性或自仿射性，即局部是整体的一个小复制品，只是在 大小、位置和方向上有所不同而已。如果将这种复杂归纳为仿射变换，那么产生 一个小复制品就相当于对图形作一次压缩仿射变换。于是，对于那些具有自相似 结构的实体，如果能够找到描述这些复制过程的仿射变换，就可以把握该实体的 总体信息，i f s 正是基于这个思想。从理论上讲，任何图形都可以用一组压缩仿射 变换来描述或生成。i f s 认定集合对象的全貌和局部在仿射变换的意义下具有自相 似机构，因此可以通过定义集合对象的整体和选定若干仿射变换，将整体形态变 换到局部，并可反复迭代该过程直至得到满意的造型。当然，并不是任何仿射变 换都可以用于迭代函数系统，只有压缩仿射变换才可以应用，否则就不能保证迭 代过程的保形性和收敛性。 2 2i f s 的基本理论 定义2 1 若变换w ：r 2 一r 2 具有形式为 形 ； 2 ：三】 ； + ；】 其中a , b ，c ，d ，e ，f 为实数，则称w 为一个( 二维) 仿射变换。 当x e r 2 时，上式常写成“) = a x + f ，其中 彳= ：三】，t = 【；】 通常有四种常用的仿射变化具有明显的几何意义，记 4 2 _ _ 矧，4 ；瞄= 】 则4 为缩放变换，4 为伸长变换，4 i 为剪切变换，4 为旋转变换。 定义2 2 度量空间( x ，d ) 上的变换厂：x - x 称作压缩或压缩映射，如果存在一个 常数0ss 0 ，选定一个 i f s ： x ；嵋， ，其压缩因子为0 ss 1 ，以至于 h ( l ，u 睨犯) ) ss 一- 1 则 1 0 硕七学位论文 h ( l ，彳) s 1 一s 其中h ( a ) 是h a u s d o r f f 度量，a 是i f s 的吸引子，等价地 1 j l 犯，彳) s 仁，u 睨犯) ) ，对任意的l h ( x ) 1 一j 月- 1 拼贴定理可描述成定理2 4 的形式。 定理2 4 设( x ，d ) 为度量空间，厂：x 呻x 是具有压缩因子0 ss 吣= 1 ，2 ，n ) 雨 而每个概率以对应一个变换睨，所以一个i f s p 就是 x ；睨，以，na1 ，2 ，) 。 通常，以由下式给定 口；盟；丝! 二垒盟 三4 三m 一酬 分犁造犁中的骨架截集技术 曼量量鼍曼舅曼鼍曼笪蔓量量曼曼量曼皇量曼量量曼曼曼曼皇皇曼曼i 曼曼曼曼曼曼曼曼曼曼! 皇曼曼舅曼曼曼曼鼍詈曼曼曼曼曼曼舅曼曼蔓曼曼曼量量量曼皇曼曼曼曼皇曼曼量量 若对某个h l 一0 ，s e j p 可取小数0 0 0 1 。 具体实验时，可任选一个点，然后根据概率产生一个随机整数k ( 1sk 墨) ， 令墨一磁x o ) 且在鼍点处画上一个颜色，然后又根据概率产生另一个随机整数 j ( 1j s ) ，令吃= “) ，也在该点画上颜色，如此反复的迭代便可得到i f s 的吸引子彳。 2 5 带凝聚集的i f s 定义2 6 设伍，d ) 为度量空间，c e h ( x ) 。定义变换 w o ：日僻) 呻h ( x ) 为w o ) ；c ，对任意的b e l l ( x ) 则称为凝聚变换，称c 为相应于凝聚变换的凝聚集。 由于 h ( w o 俾) ，睨( d ) ) ；h ( c ，c ) n0 ，对任意的b ，d e h ( x ) 因此凝聚变换是压缩因子s = 0 的压缩变换，它的唯一的不变集c 称为凝聚集。 定义2 7 设 x ；嘶，) 为具有压缩因子0 墨s 1 的i f s ，w o ：呻h 是凝 聚变换，则 x ；，暇，) 称为带凝聚的i f s ，其压缩因子为s 。 定理2 5 设 x ；形，n 一0 ，1 ，2 ， 是具有压缩因子s 的迭代函数系统，则变换 w ：h ( x ) _ h ( x ) 定义如 w ( e ) ；u 形p ) ，对任意的b e h ( x ) n - o 是完备空间( 日( x ) ，j l 似) ) 上具有压缩因子s 的压缩映射，即 忍( 形似) ，伊) ) ss h 研，b ) ，对任意的a ，b e l l ( x ) 它的唯一不动点p ( e h ( x ) 满足 p 一矽( 尸) 一u w , ( e ) a e - l 。i m 。w “p ) ，对任意的b 日( x ) 定义2 8 设( x ，d ) 为一度量空间，如果有4c4c4c ，则称集序列 似c 日( x ) 矗。是递增的；如果a3 43 43 ，则称集序列“c 日( x ) 鼍。是 递减的。这种包含不必是严格的。一个递减集序列“c 日( x ) 臻。是c a u c h y 序列， 反之，只有当x 是紧集时，递增序列 4c 日( x ) 矗。才是c a u c h y 序列。 设 x ；，嵋，峨) 是带凝聚集c 的迭代函数系统，x 是一紧集，记 nn 一u 睨p ) ，对任意的b e h ( x ) ，w u 呒p ) 有 q = w ( c ) 矗。 由定理2 5 可知，若 c ) 是空间h ( x ) 中的c a u c h y 序列，且收敛到迭代函数 系统的吸引子。则显然得 e = c u w ( c ) u w 2 ( c ) u u w “( c ) 是一个紧集的递增序列，其极限集a 满足形似) - a 。 硕十学位论文 2 6 带参量的i f s 到此为止，我们可以利用i f s 去产生静态的分形集了，但动态的i f s 分形吸引 子怎么绘制呢? 带参量的i f s 有助于该问题的解决。所谓带参量，即是在映射中 再加进一个参数p ，使之成为形( p ，) 。 引理2 3 设( p ，d 。) 是度量空间，( x ，d ) 是完备度量空间，w ：p x x 是x 上的 一组压缩因子为s 的压缩映射，即对每个p e p ，w 0 ，) 是x 上的压缩映射。如果 对于每个xe x ，w 是p 上的连续函数，则的不动点碲：p _ x 是连续函数。 引理2 4 设( p ，d 。) 是度量空间，伍，d ) 是完备度量空间，形：p x 呻x ， 刀l2 ，是x 上的一组依赖于参数p 的连续变换，即对每个固定的p e p ， 形( p ，x ) 是p 上的连续函数。定义 w ：日( x ) 呻h ( x ) ，w 但) = 叱p ) u p ) u u p ) 对任意的b e h ( x ) ，则对于每个bs h ( x ) ，w 是日伍) 上的对于p 的连续函数。 定理2 6 设( x ，d ) 是度量空问， x ；眠) ，彬， 是个带凝聚集的i f s ，压缩 因子s ，m a x s ：咒；0 ，1 ，如果每个睨都连续依赖于参数 ， 是紧度量, p e p p 空间，则吸引子4 ( p ) 日( x ) 就按h a u s d o r f f 度量h ( d ) 连续地依赖于p p 。 2 7 再归迭代函数系统 设憾，d 1 ) 为紧度量空间，i e 仉2 ， ， ，h i ) 为相应的以h a u s d o f f f 距离 及k i 上的紧子集组成的紧度量空间。 定义映射 ：日，呻皿，对任意的( f ，j ) e i 此处j 表示具有如下性质的目录对：即对每一个f 托2 ，) ，总有一个 仉2 ，】与之对应，也就是若( f ，j f ) ，则存在对于任一个i ，有 j ( f ) = uio ，j ) e i 一妒成立。同时映射满足 瑰( ) ，( c ) ) s 曲。j l ，俾，c ) 对任意的o ，j ) ，对任意的曰，c h ，成立( j 一1 2 ，n ) ，其中0 1 ，即 映射n 】：f ，是压缩的。 定义2 9 设x 是一个完备的度量空间，m 是一连通的h a u s d o r f f 空间，且 e c l - o ( c 1 - o 悸，x ) c 1 o ( x ，x ) ，m ) ，i