《维几何造型》PPT课件.ppt

1 第 6讲 三维几何造型 三维物体的表示 /建模 2 第 6讲 几何造型 6.1 概述 6.2 基础知识 6.3 常用的形体表示模型 6.4 三维形体的多边形表示 6.5 过程模型 6.6 常见实体造型系统简介 3 6.1 概述 客观世界中的物体都是三维的 ， 真实地描述和显示 客观世界中的三维物体是计算机图形学研究的重要 内容 。 一个物体的计算机描述叫做 模型 ， 它能被计算机所 懂得 ， 并在一定的条件下 （ 变换和投影 ） 被转换成 相应的图形在屏幕显示或在绘图机上输出； 图形 是模型的一个具体可见像 ， 是人 们所看到的模型的表征 。 不能把两者 混为一谈 。 在三维空间 ， 描述的是几何形体和几 何曲面 ， 只有在平面上 ， 它才是人们 通常所称的图形 。 4 6.1 概述 计算机几何造型 就是用计算机系统来表示、控制、分析和输出 三维形体 (描述物体的几何信息和拓扑信息 )。所以几何造型是 计算机图形学中一个十分重要的研究领域。 几何造型系统的主要功能： 形体输入，即把形体从用户格式转换成计算机内部格式； 形体数据的存储和管理； 形体控制，如对形体进行平移、缩放、旋转等几何变换； 形体修改，如应用集合运算、欧拉运算、有理 B样条等操作 实现对形体局部或整体修改； 形体分析，如形体的容差分析，物质特性分析等； 形体显示输出，如消隐、光照、颜色的控制等； 询问形体的属性及其有关参数。 5 6.1 概述 表示形体的两种模型 : 数据模型：规则形体 的建模方法； 用欧式几何描述。 过程模型：不规则形 体的建模方法； 用分形几何描述。 形体表示 数据模型 过程模型 线框模型 表面模型 实体模型 6 6.1 概述 数据模型 完全以数据描述。通常是欧式几何所能描述的规则物体。 例如：以顶点表示的立方体、以球心和半径表示的球。 按发展时间：线框模型、表面模型、实体模型； 以数据文件的形式存在。 (静态 ) 本章主要介绍实体模型。 7 6.1 概述 过程模型 以一个过程和相应的控制参数描述。通常描述不规则的 自然景物。 (基于分形几何 ) 例如：用一些控制参数和一个生成规则描述的植物。 以一个数据文件和一段代码的形式存在；（动态） 包括：随机插值模型、迭代函数系统、 L系统、粒子系 统、动力系统等。 8 第 6讲 几何造型 6.1 概述 6.2 基础知识 6.3 常用的形体表示模型 6.4 过程模型 6.5 三维形体的多边形表示 6.6 常见实体造型系统简介 9 6.2 基础知识 1. 形 体 2. 形体表示方法 3. 正则集合运算 4. 欧拉运算 10 1. 形 体 在计算机中，形 体一般定义为六 层拓扑结构，首 先介绍在三维空 间中基本术语的 定义。 形体 (object) 外壳 (shell) 面 (face) 环 (loop) 边 (edge) 顶点 (vertex) 曲线或直线 方程 点的 几何坐标 11 1. 形 体 体 由封闭表面围成的有效空间称为体；一个体 Q是 R3空间中 非空、有界的封闭子集 。其边界（记为 Q）是有限个面 的并集，而外壳是形体的最大边界。一个单位立方体可定 义为： (x,y,z) R3|0 x1,0y1,0z1 其中一个表面可表示为： (1,y,z) R3|0y1,0z1 必须注意 ：并没有规定形体必须是一个 连续 的封闭集合， 目的是用这样的定义来扩大几何造型的域，使得形体可以 由不连续的体素，或是仅有某些相交的形体组成。 x z y 12 1. 形 体 面 R3中非空、连续、共面且封闭的子集称为面 F， 其边界 (记为 F)是有限条线段的并集， Pt表示含有 F 的唯一平面。 面是形体表面的一部分，且具有方向性 . F Pt 13 1. 形 体 环 由 有序、有向边 组成的面的封 闭边界称为环。 环中任意边都不能自交； 相邻两条边共享一个端点； 环又分为内环和外环。内环是在 已知面中的内孔，其边按逆时针 方向。外环是已知面的最大外边 界的环，其边按顺时针方向，按 这种方式定义，在面上沿着边的 方向前进，面的内部始终在走向 的右侧。 14 1. 形 体 边 形体内两个相邻面的交界称为边。一条边有且仅有两个相 邻面。两个端点确定一条边，这两个端点分别称为该边的 起点和终点。 假设 Q是一个形体， E(Q)是形体边的集合，则在 Q中 E(Q) 为满足下列条件的所有线段的集合： 边 e的两个端点属于顶点 V(Q)； 边 e中没有一个内部点属于顶点 V(Q) 边 e上每个点，都有两个不同的面，即存在两个面 fi， fJ Q，使得边 e fi fj； 形体 Q的边框线 WF(Q)是由有序对 (V(Q),E(Q)所组成。 v1 v2 e f 1 f2 15 1. 形 体 顶点 边的端点称为顶点，顶点不能出现在边的内部， 也不能孤立地位于物体内、物体外或面内，顶点 又是 F中两条不共线的线段的交点。 假设 Q是一个形体， V(Q)是所有顶点 P的集合， Pf 是含面 f的唯一平面，则存在 3个面 f1,f2,f3 Q， 一点 P V(Q)，使得 |P|=f1 f2 f3=Pf1 Pf2 Pf3。 v1 v2 e f 1 f2 16 1. 形 体 几何信息 用来表示形体的几何性质和度量关系称为几 何信息。 拓扑信息 用来表示形体之间的连接关系称为拓扑信息。 17 6.2 基础知识 1. 形 体 2. 形体表示方法 3. 正则集合运算 4. 欧拉运算 18 2. 形体表示方法 形体常用的 3种表示方法： 线框模型、表面模型和实体模型 : 线框模型 早期模型。用 顶点 和 棱边 来描述物体。 一般地，画出了形体的棱线 (边 )与轮廓线就能唯一地表 示出来。如上图，八个顶点可以定义一个长方体，但还 不足以识别它，如果定义了棱线，则无论如何放置长方 体都能唯一地表示了。 e12 v4 v8 e2 e4 e6 e8 e2 e 7 e11 e10 e9 e3 e1 v2 v3 v1 v7 v5 v 6 19 V1 V2 V3 V4 V5 V6 V7 V8 E8 E10 E1 E2 E3 E4 E5 E6 E7 E9 E11 E12 a b c X Z Y 下图和表说明了线框模型在计算机内存储的数据结构原理。 组成长方体的顶点和边 顶点表 V1 V2 V3 V4 V5 V6 V7 V8 x坐标 a a a a 0 0 0 0 y坐标 0 b b 0 0 b b 0 z坐标 0 0 c c 0 0 c c 长方体的顶点表 20 边号 E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 起点号 V1 V2 V3 V4 V5 V6 V7 V8 V1 V2 V3 V4 终点号 V2 V3 V4 V1 V6 V7 V8 V5 V5 V6 V7 V8 长方体的边表 V1 V2 V3 V4 V5 V6 V7 V8 E8 E10 E1 E2 E3 E4 E5 E6 E7 E9 E11 E12 a b c X Z Y 组成长方体的顶点和边 21 2. 形体表示方法 线框模型 对于多面体由于其轮廓线和棱线通常是一致的，所以多面体 的线模型更便于识别，且简单。 对于圆柱体或球体之类的形体，只画出棱线而不画出轮廓线 是不能完整地表示出这个形体的。下图是圆柱体的多种表示 方法： e12 v4 v8 e2 e4 e6 e8 e5 e7 e11 e10 e9 e3 e1 v2 v3 v1 v7 v5 v6 22 2. 形体表示方法 线框模型的优缺点 : 简单，处理速度快， 所占的存贮空间较少； 对于非平面多面体，如圆柱、球等形体，其轮廓线随观察 方向的改变而改变，无法用一组固定的轮廓线来表示它们。 线框模型与形体之间不存在一一对应关系：它仅仅通过给 定的轮廓线约束所表示形体的边界面，而在轮廓线之间的 地方，形体的表面可以任意变化。 没有包含全部的信息，定义的形体存在多义性； 不能计算面积、体积等物理量； 不适于真实感显示（不能处理物体的侧影轮廓线，也不能 生成剖切图、消隐图、明暗色彩图等） 。 其应用范围很有 限。 23 线框图的二义性 24 2. 形体表示方法 表面模型 将形体表示成一组表面的集合。 如果把线框模型中的棱线及轮廓线 包围的部分定义为面，所形成的模 型便是表面模型。其数据结构是在 线模型的基础上附加一些指针，有 序地连接棱线。下图中表面编号表 示第几个表面，表面特征是平面还 是曲面。 4 顶点个数 1 起始指针 0 表面特征 5 表面编号 0 1 4 0 4 3 0 3 2 0 2 1 连接指针 属 性 顶点 号 1 4 2 3 2 3 4 1 25 2. 形体表示方法 比线框模型立体感强； 形体与其表面一一对应， 表达了物体的表面形状， 消除了多 义性； 能够计算面积； 适合于真实感显示； 存在的问题 不能有效的用来表示实体； 表面模型中的所有面未必形成一个封闭的边界； 各个面的侧向没有明确定义，即不知道实体位于面的哪 一侧。 在面模型上打孔， 内部为“空洞” 26 2. 形体表示方法 实体模型 形体为封闭表面围成的有效空间； 可以简单理解为 “ 实心 ” 。 在表面模型的基础上增加： 一个封闭的边界； 实体在表面某一侧的定义方法。 能够计算体积、面积、重量、动 量、转矩等物理量； 可以赋予材料特性；模拟物理的 运动，受力变形等。 27 2. 形体表示方法 实体模型 以下是实体在表面某一侧的 4种定义方法： 方法 1：除了定义一个表面外，还已知实体 存在于表面一侧的一点 P； 方法 2：以箭头指向实体存在一侧的方法； 方法 3：定义表面边界线为有向边界，并设 右螺旋前进的方向为实体存在的一侧； 方法 4：将形体分割成几个区域， 由于每一条边界线两侧的箭头方 向相反，则表明表面一侧存在实体。 P 28 6.2 基础知识 1. 形 体 2. 形体表示方法 3. 欧拉运算 29 6.2 基础知识 1. 形 体 2. 形体表示方法 3. 欧拉运算 30 4. 欧拉运算 欧拉公式： V-E+F=2 （ V为顶点数， E为棱线数， F为面数） 凡是满足欧拉公式的形体均称为欧拉形体。 欧拉公式是必要条件。 V=4,E=6,F=4 v2 v1 v3 v4 v 4 v1 v5 v8 v6 v3 v2 v7 V=8,E=12,F=6 V=10,E=15,F=7 31 4. 欧拉运算 扩展的欧拉公式： V- E+F - H=2(B-P) 其中， H为面上的孔穴数， P为贯穿多面体的孔穴数， B为 形体非连通部分总数。 V=16,E=24,F=11, H=1,B=1,P=0 V=10,E=15,F=7, H=2,B=1,P=1 (圆柱孔上取两点） V=12,E=18,F=8, H=2,B=1,P=1 (圆柱孔上取四点） 32 第 6讲 几何造型 6.1 概述 6.2 基础知识 6.3 常用的形体表示模型 6.4 三维形体的多边形表示 6.5 过程模型 6.6 常见实体造型系统简介 33 6.3 常用的形体表示模型 1. 模型的考虑 2. 扫描变换 (Sweep)表示模型 3. 构造实体几何 (CSG)表示模型 4. 边界表示 (B-Rep)模型 5. 空间分割模型 34 1. 模型的考虑 必须考虑以下一些问题： 根据形体边界给定的信息，是否能自动的获取形 体的几何特征？ 如何确定对形体操作数据的有效性？ 形体的表示模型是否唯一？ 不同的表示模型是否可以转换？ 是否最佳表示模型？ 35 1. 模型的考虑 在实体模型的表示中，基本上可以分为 分解表示、 构造表示和边界表示 三大类。 目前常用的形体表示模型有： 扫描变换表示模型 (Sweep) 构造实体几何表示模型 (CSG: Constructive Solid Geometry) 边界表示模型 (B-rep： Boundary Representations) 空间分割模型 对于几何造型系统来说，按照不同的目的可以采用 不同的最佳表示模型。后面将介绍四种模型。 36 6.3 常用的形体表示模型 1. 模型的考虑 2. 扫描变换 (Sweep)表示模型 3. 构造实体几何 (CSG)表示模型 4. 边界表示 (B-Rep)模型 5. 空间分割模型 37 2. Sweep表示模型 扫描变换表示模型 的基本思 想非常简单： “物体” + “运动的轨迹”。 扫描变换表示模型是基于一 个 基体 (一般是一个封闭的 平面轮廓 或一个形体 ) 沿指 定路径运动而扫掠生成的新 形体。也称“推移表示”。 如：图形 A沿 Z轴做扫描变换 出来的三维形体。 z y x A 平移扫描法 38 2. Sweep表示模型 常用的扫描方式有： 平移扫描法：基体 沿直线进行扫描；（拉伸体） 旋转扫描法：基体 绕某一轴线旋转一定角度；（旋转体） 广义扫描法：扫描路径是曲线，扫描过程中基体还可以 发生变化 ； 旋 转 扫 描 法 广 义 扫 描 法 39 2. Sweep表示模型 图形 A绕 B轴作旋转扫描的形体：因此，三维形体 S可以表 示为由一个二维图形 A和一根轴 B组成，即三维形体的表示 可简化为二维图形的表示。 B A z y x A 平 移 扫 描 法 旋 转 扫 描 法 40 2. Sweep表示模型 三维形体也能在空间通过扫 描变换生成新的形体。 如左图，一个圆柱体按指定 方向在长方体上运动生成新 的形体，这个过程犹如长方 体与运动者的圆柱体不断的 作差运算操作。 U 扫描线方向 有时经过扫描变换所生成的形体可能会出现维数不一致问题。 41 2. Sweep表示模型 优点： 表示简单、直观， 是生成三维形体的有效方法。 适合 做图形输入手段； 可用来生成一些体素。 配合仿射变换可生成复杂的形体； 缺点： 用扫描变换产生的形体可能出现维数不一致的问题 (非 正则物体无效物体 )； 扫描方法不能直接获取形体的边界信息； 表示形体的覆盖域 (类型 )非常有限； 作几何变换困难； 42 2. Sweep表示模型 43 6.3 常用的形体表示模型 1. 模型的考虑 2. 扫描变换 (Sweep)表示模型 3. 构造实体几何 (CSG)表示模型 4. 边界表示 (B-Rep)模型 5. 空间分割模型 44 3. CSG表示模型 构造实体几何表示模型对 于复杂的形体都可以通过 正则集合运算或几何变换 操作用简单形体（体素） 组合来表示。 并 交 球柱 差 体素： 球和柱 柱球 45 3. CSG表示模型 由于体素表示的有效性 决定了构造实体几何表 示的有效性，所以在几 何造型中必须细致定义 各种体素。 在几何造型系统中常用 的体素如图，每个体素 都用简单参数变量表示， 这里的参数包含体素的 大小、形状、位置和方 向。 H H H H H H H R R R R R r R d W W W W W L L L L L 46 3. CSG表示模型 体素的构造： 参数定义的简单形体，如球体，柱体，立方体等； 扫描变换生成的形体； 体素的表示也可以用曲面或平面半空间的交运算 来表示。 47 3. CSG表示模型 一般地，用构造实体几何表示模型构造形体的方法无二义 性，但不是唯一的，通常采用最简单的构造方法。 (a)中的形体可以用 (b)或 (c)定义 (b) A-*B (a) (c) AU*B 48 3. CSG表示模型 构造实体几何表示模型的构造方法可以看作一棵有序的二叉树， 称为 CSG树。其中叶节点可以是体素，也可以是形体运动的变 换参数，非叶节点可以是正则集合运算操作，也可以是形体的 几何变换（平移、旋转或缩放）操作，所有操作只对其子树 （子形体）起作用。 对一棵 CSG树按深度优先遍历，依次执行指定的操作，结果便 得到所表示的形体。 CSG树的形式定义为： := | | 49 3. CSG表示模型 例如：体素 1、 2和 平移变换 x作为 3 个叶节点， 1- 2和 2(x)的操作结果 作为两个中间节点 (非叶节点 )，最终 的形体 (1- 2)-2(x)作为根 节点。 50 3. CSG表示模型 构造实体几何表示模型的几何造型系统一般由两部分组成： 一部分是描述通过集合运算和几何变换操作连接体素所生 成子形体的 CSG树的数据结构； 另一部分是描述相应体素的大小、形状、位置和方向等几 何参数。 通过以上给定的构造实体几何表示模型可以计算出其形体的 边界表示。其计算过程如下： 对单个形体，计算其表面在何处被截断，哪些边或顶点被 产生或删除？ 对两个相交形体，计算由于其相交而产生的新边： 计算两相交形体的相交线段； 按几何元素分类，确定相交线段的哪一部分真正属于新 形体的边（有效边）。 51 3. CSG表示模型 CSG表示的优点： 数据结构比较简单，数据量比较小，内部数据的管理比较 容易； CSG表示可方便地转换成边界（ B-Rep）表示； CSG方法表示的形体的形状，比较容易修改。 CSG表示的缺点： 是一种体表示方法，显示 /绘制时需进行转换； 对形体的表示受体素的种类和对体素操作的种类的限制， 也就是说， CSG方法表示形体的覆盖域有较大的局限性。 对形体的局部操作不易实现。例如：弯曲表面，对交线倒 圆角； 所以在使用 CSG表示模型的系统中需要结合其他表示模型或 算法来解决有关问题。 52 6.3 常用的形体表示模型 1. 模型的考虑 2. 扫描变换 (Sweep)表示模型 3. 构造实体几何 (CSG)表示模型 4. 边界表示 (B-Rep)模型 5. 空间分割模型 53 4. 边界表示 (B-Rep)模型 CSG表示与 B-Rep表示曾为两大主流方法。 80， ACM Solid modeling、欧洲 CSG会议 当前 B-Rep表示一统天下。 在一个几何造型系统中，往往是多种方法 并存，互相补充。 54 4. 边界表示模型 边界表示模型是一种采用几何和拓扑 信息来描述的表示模型。一个形体一 般可以通过其边界拆成一些有界的 “ 面 ” 或 “ 小片 ” 的子集来表示，而 每一个面又可以通过其边界的边和顶 点来表示。若面的表示无二义性，则 其边界表示模型也无二义性，但通常 不一定只有唯一的表示。 四棱椎边界表示的例子如右，由 4个面 组成，且这种表示可以看作是含有体、 面、边、顶点为节点的有向图 四棱椎边界表示也可以基于边界的三 角形分解，即把形体的边界拆成一些 互不重叠的三角形。 v1 v2 v3 v4 v5 v2 v3 v4 v5 e1 e2 e3 f 1 v1 四棱柱 面节点 边节点 顶点坐标 f1 f2 f3 . e1 e2 e3 e4 . v1 v2 v3 . (x1,y1,z1) 组合 结构 坐标 信息 . 55 4. 边界表示 (B-Rep)模型 边界模型的基本拓扑实体包括： 1. 顶点 2. 边 边有方向，它由起始顶点和终止顶点来界定。边的形状 （ Curve）由边的几何信息来表示，可以是直线或曲线，曲 线边可用一系列控制点或型值点来描述，也可用显式、隐式 或参数方程来描述。 3. 环 环（ Loop）是有序、有向边（ Edge）组成的封闭边界。环有 方向，有内、外环之分。 56 4. 边界表示模型 边界模型表达形体的基本拓扑实体包括 (参考 8.2.1)： 4. 面 面（ Face）由一个外环和若干个内环（可以没有内环）来表 示，内环完全在外环之内。 面具有方向。面的形状可以是平面或曲面。平面可用平面方 程来描述，曲面可用控制多边形或型值点来描述，也可用曲 面方程（隐式、显式或参数形式）来描述。对于参数曲面， 通常在其二维参数域上定义环，这样就可由一些二维的有向 边来表示环，集合运算中对面的分割也可在二维参数域上进 行。 5. 体 体（ Body）是面的并集。 57 4. 边界表示 (B-Rep)模型 用边界模型表示形体的方法有多种： 如把面组成 CSG表示模型中的体素，再组合体素生成更复 杂形体； 或直接将表面的组合及其相交来生成复杂形体； 利用欧拉运算； B-Rep模型的数据结构中比较著名的有： 翼边数据结构； 1972年，由美国斯坦福大学 Baumgart作 为多面体的表示模式提出。用这一数据结构表示多面体 模型是完备的，但它不能表示带有精确曲面边界的实体。 辐射边数据结构； 1986年， Weiler提出了辐射边（ Radial Edge）数据结构。可表示非正则形体，及曲线边、曲面 等。 数据结构根据造型系统的需求设计。 58 4. 边界表示 (B-Rep)模型 优点： 表示能力强； 精确表示物体； 几何变换容易； 适于显示处理； 缺点： 表示复杂； 有效性难以保证； (采用多边形近似时 ) 集合运算复杂； 59 空间分割表示模型 物体的八叉树表示是一种层次数据结构，是对二维空间中四叉 树编码方法的扩展。四叉树将二维区域分成四等分而得，八叉树是 将三维区域分成八等分而得。 首先在空间中定义一个能够包含所表示物体的立方体。立方体 的三条棱边分别与 x,y,z轴平行，边长为 2n。若立方体内空间完全由 所表示的物体所占据，则物体可用这个立方体予以表示，否则将立 方体在 x,y,z轴三个方向都分成二等分，整个立方体共等分为八个小 块，每块仍为一个小立方体，其边长为原来立方体边长的 1/2。将 这八个小立方体依序编号为 0， 1， 2， ， 7，如图所示。 八叉树的结点编码 60 若某一小立方体的体内空间全部被所表示的物体占据， 则将此立方体标识为 “ Full”；若它与所表示物体无交，则 该立方体被标识为 “ Empty”；否则将它标识为 “ Partial”， 并继续分割下去。依此方式，物体在计算机内可表示为一 棵八叉树。 注意，凡是标识为 “ Full”或 “ Empty”的立方体均为 终端结点，而标识为 “ Partial”的立方体为非终端结点。 最后，当分割生成的每一小立方体的边长为单位长时，分 割即告终止。此时可将每一小立方体标识为 “ Full”。 61 物体之间的集合运算在八叉树表示中具有十分简单的 形式。由定义可知，两物体的并就是这两个物体一共占有 的空间，而物体之间的交即它们共同占据的空间。由于物 体的八叉树表示就是由它内部含有的大大小小的立方体 （称为体元）组成，因此对物体执行并、交、差运算时， 只需同时遍历参加集合运算的两物体相应的八叉树，就可 以获得拼合体的八叉树，而无需进行复杂的求交运算。 62 6.3 常用的形体表示模型 1. 模型的考虑 2. 构造实体几何 (CSG)表示模型 3. 扫描变换 (Sweep)表示模型 4. 边界表示 (B-Rep)模型 63 第 6讲 几何造型 6.1 概述 6.2 基础知识 6.3 常用的形体表示模型 6.4 三维形体的多边形表示 6.5 过程模型 6.6 常见实体造型系统简介 64 6.4 三维形体的多边形表示 造型的应用？ CAD/CAM中，需要精确的表示。实体模型。 游戏、动画等显示或绘制环境中，只需要可 接受的视觉效果。往往采用多边形网格来近 似表示物体。 多边形表示的精度由多边形网格的数量决定。 65 6.4 三维形体的多边形表示 多边形网格实际上就是物体表面 (faces)的近似多 边形的集合。 为什么要采用多边形网格来表示形体？ 结构简单，可表示任意形体。虽然不精确，但 足以满足视觉的需要。 在光照处理、纹理映射等算法中易于处理多边 形 (计算属性简单，如法向量等 )，便于硬件实 现。 66 第 6讲 几何造型 6.1 概述 6.2 基础知识 6.3 常用的形体表示模型 6.4 三维形体的多边形表示 6.5 过程模型 6.6 常见实体造型系统简介 67 6.5 过程模型 1. 分形几何 2. 随机插值模型 3. 迭代函数系统 4. 基于文法的模型： L系统 5. 粒子系统 6. 动力系统 68 1. 分形几何 真实的世界却并不规则。 闪电不是直线，海岸线不是弧线，云团不是球体，山峦也 不是锥体。自然界的许多对象是如此不规则和支离破碎， 以致欧氏几何学不能真实有效地再现大自然。 为了再现真实世界，必须选择新的工具，分形几何 学应运而生。 分形几何是以非规则物体为研究对象的几何学。由于闪电、 海岸线、云团、山峦、海浪、野草、森林、火光等非规则 物体在自然界里比比皆是，因此分形几何学又被称为描述 大自然的几何学。 69 1. 分形几何 分形（ Fractal）这个词，是由美籍法国数学家曼德尔布罗特 （ Benoit B.Mandelbrot）自己创造出来的，此词来源于拉丁 文 fractus，意为不规则、支离破碎。 1967年曼德尔布罗特在美国 科学 杂志上发表了划时代 的论文 英国海岸线有多长？统计自相似与分数维 ，成为 其分形思想萌芽的重要标志。 1973年，在法兰西学院讲学期间，曼德尔布罗特提出了分 形几何学的整体思想，并认为分数维是个可用于研究许多物 理现象的有力工具。 1982年曼德尔布罗特出版了 大自然的分形几何学 ，引 起了学术界的广泛重视，曼德尔布罗特也因此一举成名。 1985年获得 Barnard奖章（物理学，每五年一次） 70 1. 分形几何 67年， Mandelbrot提出“英国 的海岸线有多长？” 正确的答案令人吃惊：是不确 定的，其长度依赖于测量单位 的长度。 71 1. 分形几何 分形物体的基本特征： 1.自相似性 指局部与整体相似的 性质 。一座座山峰和整体 山脉，河流中一个个支流 和整体河川，茂密的树木 上的一条条树杈和整体树 木等，均具有自相似性。 如图所示的是蕨类植物叶 子上的细叶和整体叶子的 相似性。 72 分形物体的基本特征： 2.无标度性 标度是计量单位的刻度。 比如长度的标度是米；重量 的标度是公斤；面积的标度 是平方米等。对欧氏几何学 内的不同形体，可以选择不 同的标度去度量。例如，直 线是多长，面积是多大，体 积是多少。自然界中很多的 物体具有特征长度，如人有 高度、山有海拔等等。 1. 分形几何 73 1. 分形几何 分形的定义。一般认为，满足下列条件的图形称为 分形集： 分形集具有任意尺度下的比例细节，或者说具有 无穷的精细结构； 分形集是不规则的，以致于不能用传统的几何语 言来描述。 分形集通常具有某种自相似性，或许是近似的或 许是统计意义下的自相似。 分形集在某种方式下定义的“分数维”一般大于 它的拓扑维数。 分形集的定义常常是非常简单的，或许是递归的。 74 2. 随机插值模型 1982年由 Alain Fournier， Don Fussell和 Loren Carpenter提出：能有效地模拟海 岸线和山等自然景象 ， 不是事先决定各 种图素和尺度 ， 而是用一个随机过程的 采样路径作为构造模型的手段 。 构造二维海岸线的模型可以选择控制大 致形状的若干初始点。再在相邻两点构 成的线段上取其中点。并沿垂直连线方 向随机偏移一个距离，再将偏移后的点 与该线段两端点分别连成两个新线段。 这样下去可得到一条曲折的有无穷细节 回归的海岸线，其曲折程度由随机偏移 量控制，它也决定了分数维的大小。 75 2. 随机插值模型 在三维情况下可通过类似过程构 造山的模型，一般通过多边形 （简单的如三角形）细分的方法。 可以在一个三角形的三边上， 随机各取一点，沿垂直方向随 机偏移一段距离得到新的三个 点，再连接成四个三角形，如 此继续，即可形成皱褶的山峰。 山的褶皱程度由分数维控制。 76 3. 迭代函数系统 Iterated Function System（简称 IFS） 在 SIGGRAPH85国际会议上， Demko， Barnsley等人作过 IFS的专题报告。 应用 自然景物的模拟 图像压缩 77 3. 迭代函数系统 谢尔宾斯基垫片 生成规则：取一等边三角形， 连接各边中点将原三角形分 成四个小三角形，然后舍弃 位于中间的一个小三角形， 将剩下的其余三个小三角形 按同样方法继续分割，并舍 弃位于中间的那个三角形， 如图所示。如此不断地分割 与舍弃，就能得到中间有大 量孔隙的 Sierpinski垫片。 Sierpinski carpet Sierpinski gasket 78 4. 基于文法的模型： L系统 由美国生物学家 Lindenmayer创立，后来由 Smith等人将 L系统引入图形学。 1990年，” The Algorithmic Beauty of Plant” 是一种形式语言，通过符号串的解释，转化 为造型工具 基本思想： 用文法表示植物的拓扑结构； 通过图形学方法生成逼真的画面。 79 4. 基于文法的模型： L系统 一个例子： 13世纪数学家 Fibonacci，（ 1170-1250）， 兔子的理想化繁衍 字符串 a， b，改写规则 a ab; b a baby： b； adult： a b a ab aba abaab abaababa abaababaabaab abaababaabaababaababa 80 4. 基于文法的模型： L系统 例子： von Koch 雪花曲线 w： F F F-F+F-F 几何解释 F：向前画一条线 +：右转 -： 左转 81 4. 基于文法的模型： L系统 例子：植物 w： F F F+FF-FF :将当前植物生长的状 态压入堆栈，信息包括 所在位置和方向等。 :从堆栈中弹出一个状 态作为植物的当前状态， 但不画线。 82 5. 粒子系统 (Particle System) W.T.Reeves 1983年提出随机模型 ， 它用大量的粒子图元 (Particle)来描述景物 。 最初引入是为了模拟火焰 ， 火焰被看作是一个喷出许多粒子 的火山 。 每个粒子都有一组随机取值的属性 ， 如起始位置 、 初速度 、 颜色及大小 。 方法 一个粒子系统由一些随时间变化 的粒子构成了； 每个粒子有一个生命周期，包括 出生、成长、灭亡等几个阶段， 演化过程有一定的规则控制； 粒子在不同的阶段具有不同的形 态； 粒子的运动由一定的规则控制。 83 5. 粒子系统 (Particle System) 描述对象 ： 结构随时间而变化的物体 。 跳动的火焰 飘浮不定的云彩、烟、雾 远处的草地、森林 每个粒子的位置 、 取向及动力学性质都是由一组预 先定义好的随机过程来说明的 。 模拟草丛 、 森林等全景要求高的景象 。 该模型是由粒子刻划的 ， 因而适合描述动态的火焰 、 烟和被风吹动的草等 。 84 第 6讲 几何造型 结束！