图形学教材课件第6章三维实体造型2章节.ppt

二） 苏 小 红 哈尔滨工业大学计算机科学与技术学院,三维实体造型,2,欧氏几何 使用方程描述有平滑的表面和规则形状的物体 分形几何 使用过程对具有不规则几何形态的物体（如自然景物）建模,分形几何,3,过程模型,不规则形体的建模方法 欧氏几何与分形几何 随机插值模型 迭代函数系统 基于文法的模型：L系统 粒子系统 复动力系统,4,1906年，瑞典数学家H.Von Koch在研究构造连续而不可微函数时，提出Koch曲线周长无穷，但面积为定值（0）,分形的由来（1/4）,,,,构造方法,5,构造方法,周长无穷，但面积为定值,分形的由来（2/4）,,,,,Von koch snowflake,D=log4/log3=1.2618,6,分形的由来（3/4）,60年代，现代分形理论的奠基人B.B.Mandelbrot将雪花与海岸线、山水、树木等自然景物联系起来,67年，英国《科学》杂志，《英国的海岸线有多长？统计自相似性与分数维数 》,什么是分形 ？,指具有多重自相似的对象 它可以是自然存在的，也可以是人造的7,分形的由来（4/4）,fractal概念的由来,75年，法文专著《分形对象:形、机遇与维数 77年，英译本《分形：形、 机遇与维数》 (Fractals: Form, Chance, and Dimension) 82年，增补本，改名为《大自然的分形几何学》,根据拉丁语fractus造的词 词根含义： 细片的、破碎的、分裂的、分数的,8,分形几何（1/8）,分形物体的细节变化用分形维数（分数维）来描述，它是物体粗糙性或细碎性的度量。

什么是分数维？,9,分形几何（2/8）,整数维数 拓扑维数 只能取整数 表示描述一个对象所需的独立变量的个数,10,分形几何（3/8）,分数维数 度量维数 是从测量的角度定义的 从测量的角度看，维数是可变的例如：看一个毛线团,从测量的角度重新理解维数概念,11,分形几何（4/8）,一根一维线段L，单位长度A，将其边长扩大到原来的3倍，看看能得到几个原始对象(单位长度为A的线段)3个： L→3L=3^1*L,平面上的一个正方形P，边长为A，将其边长扩大到原来的3倍，则得到9个正方形： P→9P=3^2*P,对于三维空间上的正方体V，边长为A，将其边长扩大到原来的3倍，则得到27个立方体： V→27V=3^3*V,得到的总个数可表达为： M=B^d 其中B指放大倍数，M是总个数，d相当于对象的维数 换一种写 法有： d=logM/logB 其中指数d相当于维数12,分形几何（5/8）,从放大的反面去理解 从“铺砌”的角度看,对给定对象， 用很小的单元块ε充填它，最后数一数所使用的小单元数目N,数学表达： d=lim(ε→0)logN(ε)/log(1/ε) = -lim(ε→0)logN(ε)/logε,13,分形几何（6/8）,以Koch曲线为例 细分线段数为N=4，细分单元长度为ε =1/3 Koch曲线的分数维为： d=ln4/ln3=1.2619,而按照欧氏几何方法 将一条线段4等分 则N=4， ε =1/4，d=1。

14,分形几何（7/8）,什么是分形 ？,Mandelbrot开始时 把那些Hausdorff维数不是整数的集合称为分形 但定义将某些显然为分形的集合排除在外 例如，Peano曲线的Hausdorff维数为2，是整数 定义修改为 强调具有自相似性的集合为分形,15,分形几何（8/8）,至今无统一定义，比较合理、普遍被人接受的定义 定义具有如下性质的集合F为分形 F具有精细的结构，有任意小比例的细节 F是如此地不规则，以至于它的整体与局部都不能用传统的几何语言来描述 F通常有某种自相似的性质，这种自相似性可以是近似的或者是统计意义下的 一般地，F的某种定义之下的分形维数大于它的拓扑维数 在大多数令人感兴趣的情形下，F通常能以非常简单的方法定义，由迭代过程产生 分形理论是非线性科学的生长点之一,16,随机插值模型（1/3）,1982年由 Alain Fournier Don Fussell Loren Carpenter 提出 能有效地模拟海岸线和山等自然景象 不是事先决定各种图素和尺度 而是用一个随机过程的采样路径作为构造模型的手段,17,随机插值模型（2/3）,构造二维海岸线的模型： 选择控制大致形状的若干初始点 在相邻两点构成的线段上取其中点 沿垂直连线方向随机偏移一个距离 将偏移后的点与该线段两端点分别连成两个新线段 如此继续可得到一条曲折的有无穷细节回归的海岸线,18,随机插值模型（3/3）,在三维情况下用类似过程构造山模型： 多边形（如三角形）细分 在三角形三边上随机各取一点 沿垂直方向随机偏移一段距离得到三个新点 连接成四个三角形 如此继续，可形成皱褶的山峰。

19,迭代函数系统（1/10）,Iterated Function System（简称 IFS） 美国佐治亚理工学院 Demko,Barnsley教授首创 在SIGGRAPH’85国际会议上， IFS专题报告,20,迭代函数系统（2/10）,确定性算法与随机性算法相结合的方法生成植物杆茎或叶片,21,迭代函数系统（3/10）,设最终要生成的植物形态图为M ，它要满足下述集合方程： M=R_1∪R_2∪…∪R_N 含义： 随机地从R_i(i=1,…，N)中挑选一个迭代规则迭代 一次 然后再随机地在R_i(i=1,…，N)中选一个规则迭代一次 不断重复此过程 最后生成的极限图形M就是欲求的植物形态图22,迭代函数系统（4/10）,每个迭代规则R_i都是一个仿射变换正交变换保持几何图形的度量性质不变,仿射变换一般会改变几何图形的度量性质 但不改变共线、平行、相交、共线点的顺序、中心对称、二次曲线的次数等,23,迭代函数系统（5/10）,上的收缩仿射变换 记为,迭代函数系统 若干个收缩仿射变换的组合,,,24,迭代函数系统（6/10）,IFS方法生成分形图像的步骤 ：,,,一个二维的IFS的组成 收缩仿射变换的集合 概率的集合,,,,确定仿射变换 确定概率向量 通过迭代过程产生点集序列来绘制分形图形,,25,迭代函数系统（7/10）,收缩影射不动点原理 每个迭代函数系统都定义了一个唯一的分形图形，称为该迭代函数系统的吸引子,怎样确定仿射变换？ 确定a,b,c,d,e,f,IFS方法之所以能产生逐渐逼近吸引子的图像 是以拼贴定理为依据的,怎样确定概率向量？ 掷骰子操作,26,迭代函数系统（8/10）,D=log3/log2=1.585,Sierpinski三角形,27,迭代函数系统（9/10）,Barnsley蕨的参数表,28,迭代函数系统（10/10）,增减规则R_i，可以改变最终植物M的形态。

即使不改变迭代规则，采用同样的程序 ，只改变参数也可以生成完全不同的植物形态应用 自然景物模拟 分形图像压缩,29,L系统（1/10）,由美国生物学家林德梅叶(Lindenmayer)创立， 1984年由Smith等人将L系统引入图形学 1990年，普鲁辛凯维奇(P.Prusinkiewicz)与林氏出版《植物的算法美》(The Algorithmic Beauty of Plants),一种形式语言 字符串重写系统 通过符号串的解释，转化为造型工具 基本思想： 从一个初始串(叫做公理)开始 将变换规则多次作用于其上 最后产生一个较长的命令串,30,L系统（2/10）,L系统分类 0L系统 与上下文无关 1L系统 仅考虑单边的文法关系，即左相关或右相关 在植物的生态模拟中 左相关文法用于模拟植物从根向叶、茎的传播过程 右相关文法用于模拟从叶到茎、根的传播过程 2L系统 同时考虑左边和右边文法关系,31,L系统（3/10）,D0L系统 确定的上下文无关的L系统 定义为一个三元组〈V,ω,P〉 V：字符表(alphabet) V*：V上的所有单词(words) ω： ω ∈V*是一个非空的单词，称公理(axiom) P ：包含于V×V*，是产生规则的有穷集。

32,L系统（4/10）,设计D0L系统的步骤： 定义字符表V 给出公理，即初始图ω 定义产生式P,33,L系统（5/10）,13世纪数学家Fibonacci（1170-1250） 兔子的理想化繁衍问题 baby(b), adult(a) V：{a,b} W: b P: a-ab b-a b a ab aba abaab abaababa abaababaabaab abaababaabaababaababa,34,L系统（6/10）,von Koch 雪花曲线 V：{F,+,-} w：F P：F-F-F++F-F δ= 60º 几何解释 F：向前画一条线 +：右转60º -：左转60º,生成元,初始图,,35,L系统（7/10）,四方内生树,四方内生树 V：{F,+,-} w：F+F+F+F P：F-FF+F++F+F δ= 90º,生成元,,初始图,36,L系统（8/10）,植物 w：F P：F-F[+F]F[-F]F [:将当前乌龟爬行的状态压入堆栈，信息包括所在位置和方向等 ]:从堆栈中弹出一个状态作为乌龟的当前状态，但不画线,37,L系统（9/10）,设计L系统的过程 是根据自相似结构形成信息压缩的一个过程 利用设计好的L系统进行绘制的过程 是信息压缩的逆过程，或者说是信息复原的过程。

38,L系统（10/10）,L系统能有效给出植物的拓扑结构 但绘制真实感的二、三维植物形态还必须结合几何造型技术,39,粒子系统（1/5）,Particle System W.T.Reeves 1983年提出,描述对象 不规则、结构随时间而变化的Fuzzy Object 尤其擅长模拟不规则物体的随机动态特性 如跳动的火焰、烟雾、下雨、行云、远处随风摇曳的树林和草丛等,40,粒子系统（2/5）,基本思想 造型和动画是一个有机的整体 单个随时间变化的粒子(Particle)作为景物造型的基本元素 由粒子刻划的模型 每个粒子有一个生命周期 包括出生、成长、死亡等几个阶段 粒子在不同的阶段具有不同的形态 粒子的运动由一定的规则控制,41,粒子系统（3/5）,本质是随机模型 采用随机过程的方法来实现粒子在“出生”、“生长”、“死亡”三个阶段的不确定性 在生长过程中，粒子的属性被随机地改变,42,粒子系统（4/5）,1985年，Reeves和Blau 进一步发展了粒子系统 并维妙维肖的模拟了小草随风摇曳的景象 模拟动态模糊自然景物 电视电影的特技制作,最初引入是为了模拟火焰 跳动的火焰被看作是一个喷出许多粒子的火山。

每个粒子都有一组随机取值的属性,43,粒子系统（5/5）,模拟动态自然景物的过程 生成新的粒子，分别赋予不同的属性以及生命周期 将新粒子加到系统中 删去系统中老的已经死亡的粒子 根据粒子的属性，按适当的运动模型或规则，对余下的存活粒子的运动进行控制 （Transformation） 绘制当前系统中存活的所有粒子,44,复平面上的迭代（1/11）,80年代初， Mandebrot在迭代z→z^2+c时，发现了著名的Mandebrot集， 简称M集,复数迭代,45,复平面上的迭代（2/11）,绘制M集 以横轴x记录实部 以纵轴y记录虚部 迭代从(x,y)=(0,0)开始迭代 不同迭代次数和模值的点涂上不同的颜色,M集合实际上是常数c=(p,q)构成的图象,46,复平面上的迭代（3/11）,M集特征： 一个主要的心形图与一系列圆盘形的“芽苞”突起连在一起 每个芽苞又被更细小的芽苞所环绕 还有精细的“发丝状”分枝从芽苞向外长出,47,复平面上的迭代（4/11）,M集记录的是整个区域上的c值情况 Julia集是取一固定的c值后，观察复平面上每一点(x,y)在迭代中的表现，并把结果记录下来,M集包含了关于Julia集构造的大量信息,,,48,复平面上的迭代（5/11）,(a) c=0.1-0.1i， f有吸引不动点，J为拟圆,(。