三维实体造型

三维实体造型2欧氏几何使用方程描述有平滑的表面和规则形状的物体分形几何使用过程对具有不规则几何形态的物体（如自然景物）建模分形几何3过程模型不规则形体的建模方法欧氏几何与分形几何随机插值模型迭代函数系统基于文法的模型：L系统粒子系统复动力系统41906年，瑞典数学家H.VonKoch在研究构造连续而不可微函数时，提出Koch曲线。

周长无穷，但面积为定值（0）分形的由来（1/4）构造方法5构造方法周长无穷，但面积为定值分形的由来（2/4）VonkochsnowflakeD=log4/log3=1.2618……6分形的由来（3/4）60年代，现代分形理论的奠基人B.B.Mandelbrot将雪花与海岸线、山水、树木等自然景物联系起来67年，英国《科学》杂志，《英国的海岸线有多长？统计自相似性与分数维数

》什么是分形？指具有多重自相似的对象它可以是自然存在的，也可以是人造的。7分形的由来（4/4）fractal概念的由来75年，法文专著《分形对象:形、机遇与维数77年，英译本《分形：形、机遇与维数》(Fractals:Form,Chance,andDimension)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/3Koch曲线的分数维为：

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年由AlainFournierDonFussellLorenCarpenter提出能有效地模拟海岸线和山等自然景象不是事先决定各种图素和尺度而是用一个随机过程的采样路径作为构造模型的手段

17随机插值模型（2/3）构造二维海岸线的模型：选择控制大致形状的若干初始点在相邻两点构成的线段上取其中点沿垂直连线方向随机偏移一个距离将偏移后的点与该线段两端点分别连成两个新线段如此继续可得到一条曲折的有无穷细节回归的海岸线18随机插值模型（3/3）在三维情况下用类似过程构造山模型：多边形（如三角形）细分在三角形三边上随机各取一点沿垂直方向随机偏移一段距离得到三个新点连接成四个三角形如此继续，可形成皱褶的山峰。19迭代函数系统（1/10）IteratedFunctionSystem（简称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,fIFS方法之所以能产生逐渐逼近吸引子的图像是以拼贴定理为依据的怎样确定概率向量？掷骰子操作26迭代函数系统（8/10）D=log3/log2=1.585Sierpinski三角形fabc

defp

10.5000.52510.3320.5000.51500.3330.5000.550500.3327迭代函数系统（9/10）Barnsley蕨的参数表fabc

defp

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

：包含于V×V*，是产生规则的有穷集。32L系统（4/10）设计D0L系统的步骤：定义字符表V给出公理，即初始图ω定义产生式P

33L系统（5/10）13世纪数学家Fibonacci（1170-1250）兔子的理想化繁衍问题

baby(b),adult(a)V：{a,b}W:bP:a->abb->abaababaabaababaababaabaababaabaababaababaabaababaababa34L系统（6/10）vonKoch雪花曲线V：{F,+,-}w：FP：F->F-F++F-Fδ=60º几何解释F：向前画一条线+：右转60º-：左转60º

n=0n=1n=2n=3生成元初始图35L系统（7/10）四方内生树四方内生树V：{F,+,-}w：F+F+F+FP：F->FF+F++F+F

δ=90º

生成元初始图36L系统（8/10）植物w：FP：F->F[+F]F[-F]F[:将当前乌龟爬行的状态压入堆栈，信息包括所在位置和方向等]:从堆栈中弹出一个状态作为乌龟的当前状态，但不画线37L系统（9/10）设计L系统的过程是根据自相似结构形成信息压缩的一个过程利用设计好的L系统进行绘制的过程是信息压缩的逆过程，或者说是信息复原的过程。38L系统（10/10）L系统能有效给出植物的拓扑结构但绘制真实感的二、三维植物形态还必须结合几何造型技术39粒子系统（1/5）ParticleSystem

W.T.Reeves1983年提出描述对象不规则、结构随时间而变化的FuzzyObject

尤其擅长模拟不规则物体的随机动态特性如跳动的火焰、烟雾、下雨、行云、远处随风摇曳的树林和草丛等

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为拟圆(b)c=0.5-0.5i，f有吸引不动点，J为拟圆(c)c=1.0-0.05i，f有周期为2的吸引轨道(d)c=0.2-0.75i，f有周期为3的吸引轨道(e)c=-0.25-0.52i，f有周期为4的吸引轨道(f)c=0.5-0.55i，f有周期5的吸引轨道(g)c=-0.66i，f没有吸引轨道，且J为全部连通(h)c=-i，f为无圈曲线改变常数c的取值，可以得到各式各样的J集

49复平面上的迭代（6/11）二维复平面上二次映射广义的M集和J集任意多项式映射三角函数指数函数对数函数50复平面上的迭代（7/11）高维M集与J集通过“四元数”(quaternions)推广到高维空间中在四维空间中研究迭代x→x^2+c下的超Julia集选一个截面，将超