第一讲三维几何造型精选文档.ppt

《第一讲三维几何造型精选文档.ppt》由会员分享，可在线阅读，更多相关《第一讲三维几何造型精选文档.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一讲三维几何造型1本讲稿第一页，共八十四页第6讲 几何造型6.1 概述概述6.2 基础知识6.3 常用的形体表示模型6.4 三维形体的多边形表示6.5 过程模型6.6 常见实体造型系统简介2本讲稿第二页，共八十四页6.1 概述n客观世界中的物体都是三维的，真实地描述和显示客观世界中的三维物体是计算机图形学研究的重要内容。n一个物体的计算机描述叫做模型，它能被计算机所懂得，并在一定的条件下（变换和投影）被转换成相应的图形在屏幕显示或在绘图机上输出；n图形是模型的一个具体可见像，是人们所看到的模型的表征。不能把两者混为一谈。n在三维空间，描述的是几何形体和几何曲面，只有在平面上，它才是人们通常所

2、称的图形。3本讲稿第三页，共八十四页6.1 概述n计算机几何造型就是用计算机系统来表示、控制、分析和输出三维形体(描述物体的几何信息和拓扑信息)。所以几何造型是计算机图形学中一个十分重要的研究领域。n几何造型系统的主要功能：n形体输入，即把形体从用户格式转换成计算机内部格式；n形体数据的存储和管理；n形体控制，如对形体进行平移、缩放、旋转等几何变换；n形体修改，如应用集合运算、欧拉运算、有理B样条等操作实现对形体局部或整体修改；n形体分析，如形体的容差分析，物质特性分析等；n形体显示输出，如消隐、光照、颜色的控制等；n询问形体的属性及其有关参数。4本讲稿第四页，共八十四页6.1 概述n表示形体

3、的两种模型:n数据模型：规则形体的建模方法；n用欧式几何描述。n过程模型：不规则形体的建模方法；n用分形几何描述。形体表示形体表示数据模型数据模型过程模型过程模型线框模型线框模型表面模型表面模型实体模型实体模型5本讲稿第五页，共八十四页6.1 概述n数据模型n完全以数据描述。通常是欧式几何所能描述的规则物体。n例如：以顶点表示的立方体、以球心和半径表示的球。n按发展时间：线框模型、表面模型、实体模型；n以数据文件的形式存在。(静态)n本章主要介绍实体模型。6本讲稿第六页，共八十四页6.1 概述n过程模型n以一个过程和相应的控制参数描述。通常描述不规则的自然景物。(基于分形几何)n例如：用一些控

4、制参数和一个生成规则描述的植物。n以一个数据文件和一段代码的形式存在；（动态）n包括：随机插值模型、迭代函数系统、L系统、粒子系统、动力系统等。7本讲稿第七页，共八十四页第6讲 几何造型6.1 概述6.2 基础知识基础知识6.3 常用的形体表示模型6.4 过程模型6.5 三维形体的多边形表示6.6 常见实体造型系统简介8本讲稿第八页，共八十四页6.2 基础知识1.形 体2.形体表示方法3.正则集合运算4.欧拉运算9本讲稿第九页，共八十四页1.形 体n在计算机中，形体一般定义为六层拓扑结构，首先介绍在三维空间中基本术语的定义。形体(object)外壳(shell)面(face)环(loop)边(

5、edge)顶点(vertex)曲线或直线方程 点的 几何坐标10本讲稿第十页，共八十四页1.形 体n体由封闭表面围成的有效空间称为体；一个体Q是R3空间中非空、有界的封闭子集。其边界（记为Q）是有限个面的并集，而外壳是形体的最大边界。一个单位立方体可定义为：(x,y,z)R3|0 x1,0y1,0z1其中一个表面可表示为：(1,y,z)R3|0y1,0z1n必须注意：并没有规定形体必须是一个连续的封闭集合，目的是用这样的定义来扩大几何造型的域，使得形体可以由不连续的体素，或是仅有某些相交的形体组成。xzy11本讲稿第十一页，共八十四页1.形 体n面R3中非空、连续、共面且封闭的子集称为面F，其

6、边界(记为F)是有限条线段的并集，Pt表示含有F的唯一平面。n面是形体表面的一部分，且具有方向性.FPt12本讲稿第十二页，共八十四页1.形 体n环由有序、有向边组成的面的封闭边界称为环。n环中任意边都不能自交；n相邻两条边共享一个端点；n环又分为内环和外环。内环是在已知面中的内孔，其边按逆时针方向。外环是已知面的最大外边界的环，其边按顺时针方向，按这种方式定义，在面上沿着边的方向前进，面的内部始终在走向的右侧。13本讲稿第十三页，共八十四页1.形 体n边形体内两个相邻面的交界称为边。一条边有且仅有两个相邻面。两个端点确定一条边，这两个端点分别称为该边的起点和终点。n假设Q是一个形体，E(Q)

7、是形体边的集合，则在Q中E(Q)为满足下列条件的所有线段的集合：n边e的两个端点属于顶点V(Q)；n边e中没有一个内部点属于顶点V(Q)n边e上每个点，都有两个不同的面，即存在两个面fi，fJ Q，使得边efifj；n形体Q的边框线WF(Q)是由有序对(V(Q),E(Q)所组成。v1v2ef1f214本讲稿第十四页，共八十四页1.形 体n顶点边的端点称为顶点，顶点不能出现在边的内部，也不能孤立地位于物体内、物体外或面内，顶点又是F中两条不共线的线段的交点。n假设Q是一个形体，V(Q)是所有顶点P的集合，Pf是含面f的唯一平面，则存在3个面f1,f2,f3 Q，一点PV(Q)，使得|P|=f1f

8、2f3=Pf1Pf2Pf3。v1v2ef1f215本讲稿第十五页，共八十四页1.形 体n几何信息用来表示形体的几何性质和度量关系称为几何信息。n拓扑信息用来表示形体之间的连接关系称为拓扑信息。16本讲稿第十六页，共八十四页6.2 基础知识1.形 体2.形体表示方法3.正则集合运算4.欧拉运算17本讲稿第十七页，共八十四页2.形体表示方法n形体常用的3种表示方法：线框模型、表面模型和实体模型:n线框模型n n早期模型。用早期模型。用顶点顶点顶点顶点和和棱边棱边棱边棱边来描述物体。来描述物体。n一般地，画出了形体的棱线(边)与轮廓线就能唯一地表示出来。如上图，八个顶点可以定义一个长方体，但还不足以

9、识别它，如果定义了棱线，则无论如何放置长方体都能唯一地表示了。e12v4v8e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v618本讲稿第十八页，共八十四页V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZY下图和表说明了线框模型在计算机内存储的数据结构原理。下图和表说明了线框模型在计算机内存储的数据结构原理。组成长方体的顶点和边组成长方体的顶点和边 顶点表顶点表V1V2V3V4V5V6V7V8x坐标坐标aaaa0000y坐标坐标0bb00bb0z坐标坐标00cc00cc长方体的顶点表长方体的顶点表 19本讲稿第十九页，共八十

10、四页边号边号E1E2E3E4E5E6E7E8E9E10E11E12起点号起点号V1V2V3V4V5V6V7V8V1V2V3V4终点号终点号V2V3V4V1V6V7V8V5V5V6V7V8长方体的边表长方体的边表 V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZY组成长方体的顶点和边组成长方体的顶点和边 20本讲稿第二十页，共八十四页2.形体表示方法n线框模型对于多面体由于其轮廓线和棱线通常是一致的，所以多面体的线模型更便于识别，且简单。对于圆柱体或球体之类的形体，只画出棱线而不画出轮廓线是不能完整地表示出这个形体的。下图是圆柱体的多种表示方法：e

11、12v4v8e2e4e6e8e5e7e11e10e9e3e1v2v3v1v7v5v621本讲稿第二十一页，共八十四页2.形体表示方法n线框模型的优缺点:n简单，处理速度快，所占的存贮空间较少；所占的存贮空间较少；n对于非平面多面体，如圆柱、球等形体，其轮廓线随观察方向的改变而改变，无法用一组固定的轮廓线来表示它们。线框模型与形体之间不存在一一对应关系：它仅仅通过给定的轮廓线约束所表示形体的边界面，而在轮廓线之间的地方，形体的表面可以任意变化。n n没有包含全部的信息，定义的形体存在多义性；没有包含全部的信息，定义的形体存在多义性；n n不能计算面积、体积等物理量；不能计算面积、体积等物理量；n

12、 n不适于真实感显示（不能处理物体的侧影轮廓线，也不能生成剖不适于真实感显示（不能处理物体的侧影轮廓线，也不能生成剖切图、消隐图、明暗色彩图等）切图、消隐图、明暗色彩图等）。其应用范围很有限。其应用范围很有限。22本讲稿第二十二页，共八十四页线框图的二义性23本讲稿第二十三页，共八十四页2.形体表示方法n表面模型n将形体表示成一组表面的集合。n如果把线框模型中的棱线及轮廓线包围的部分定义为面，所形成的模型便是表面模型。其数据结构是在线模型的基础上附加一些指针，有序地连接棱线。下图中表面编号表示第几个表面，表面特征是平面还是曲面。4顶点个数1起始指针0表面特征5表面编号014043032021连

13、接指针属性顶点号1423234124本讲稿第二十四页，共八十四页2.形体表示方法n比线框模型立体感强；n形体与其表面一一对应，表达了物体的表面形状，消除了多义性；n能够计算面积；n适合于真实感显示；存在的问题n不能有效的用来表示实体；n表面模型中的所有面未必形成一个封闭的边界；n各个面的侧向没有明确定义，即不知道实体位于面的哪一侧。在面模型上打孔，内部为“空洞”25本讲稿第二十五页，共八十四页2.形体表示方法n实体模型形体为封闭表面围成的有效空间；可以简单理解为“实心”。在表面模型的基础上增加：n一个封闭的边界；n实体在表面某一侧的定义方法。n能够计算体积、面积、重量、动量、转矩等物理量；n可

14、以赋予材料特性；模拟物理的运动，受力变形等。26本讲稿第二十六页，共八十四页2.形体表示方法n实体模型以下是实体在表面某一侧的4种定义方法：n方法1：除了定义一个表面外，还已知实体存在于表面一侧的一点P；n方法2：以箭头指向实体存在一侧的方法；n方法3：定义表面边界线为有向边界，并设右螺旋前进的方向为实体存在的一侧；n方法4：将形体分割成几个区域，由于每一条边界线两侧的箭头方向相反，则表明表面一侧存在实体。P27本讲稿第二十七页，共八十四页6.2 基础知识1.形 体2.形体表示方法3.欧拉运算28本讲稿第二十八页，共八十四页6.2 基础知识1.形 体2.形体表示方法3.欧拉运算29本讲稿第二十

15、九页，共八十四页4.欧拉运算n欧拉公式：V-E+F=2（V为顶点数，E为棱线数，F为面数）n凡是满足欧拉公式的形体均称为欧拉形体。n欧拉公式是必要条件。V=4,E=6,F=4v2v1v3v4v4v1v5v8v6v3v2v7V=8,E=12,F=6V=10,E=15,F=730本讲稿第三十页，共八十四页4.欧拉运算n扩展的欧拉公式：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,

16、P=1 (圆柱孔上取四点）31本讲稿第三十一页，共八十四页第6讲 几何造型6.1 概述6.2 基础知识6.3 常用的形体表示模型常用的形体表示模型6.4 三维形体的多边形表示6.5 过程模型6.6 常见实体造型系统简介32本讲稿第三十二页，共八十四页6.3 常用的形体表示模型1.模型的考虑模型的考虑2.扫描变换(Sweep)表示模型3.构造实体几何(CSG)表示模型4.边界表示(B-Rep)模型5.空间分割模型33本讲稿第三十三页，共八十四页1.模型的考虑n必须考虑以下一些问题：n根据形体边界给定的信息，是否能自动的获取形体的几何特征？n如何确定对形体操作数据的有效性？n形体的表示模型是否唯一

17、？n不同的表示模型是否可以转换？n是否最佳表示模型？34本讲稿第三十四页，共八十四页1.模型的考虑n在实体模型的表示中，基本上可以分为分解表示、构造表示和边界表示三大类。n目前常用的形体表示模型有：n扫描变换表示模型(Sweep)n构造实体几何表示模型(CSG:Constructive Solid Geometry)n边界表示模型(B-rep：Boundary Representations)n空间分割模型n对于几何造型系统来说，按照不同的目的可以采用不同的最佳表示模型。后面将介绍四种模型。35本讲稿第三十五页，共八十四页6.3 常用的形体表示模型1.模型的考虑2.扫描变换扫描变换(Sweep

18、)表示模型表示模型3.构造实体几何(CSG)表示模型4.边界表示(B-Rep)模型5.空间分割模型36本讲稿第三十六页，共八十四页2.Sweep表示模型n扫描变换表示模型的基本思想非常简单：“物体”+“运动的轨迹”。n扫描变换表示模型是基于一个基体(一般是一个封闭的平面轮廓或一个形体)沿指定路径运动而扫掠生成的新形体。也称“推移表示”。n如：图形A沿Z轴做扫描变换出来的三维形体。zyxA平移扫描法37本讲稿第三十七页，共八十四页2.Sweep表示模型n常用的扫描方式有：n n平移扫描法：基体平移扫描法：基体沿直线进行扫描；（拉伸体）n n旋转扫描法：基体旋转扫描法：基体绕某一轴线旋转一定角度；

19、（旋转体）n n广义扫描法：扫描路径是曲线，扫描过程中基体还可以发生广义扫描法：扫描路径是曲线，扫描过程中基体还可以发生变化变化；旋转扫描法广义扫描法38本讲稿第三十八页，共八十四页2.Sweep表示模型n图形A绕B轴作旋转扫描的形体：因此，三维形体S可以表示为由一个二维图形A和一根轴B组成，即三维形体的表示可简化为二维图形的表示。BAzyxA平移扫描法旋转扫描法39本讲稿第三十九页，共八十四页2.Sweep表示模型n三维形体也能在空间通过扫描变换生成新的形体。如左图，一个圆柱体按指定方向在长方体上运动生成新的形体，这个过程犹如长方体与运动者的圆柱体不断的作差运算操作。U U扫描线方向有时经过

20、扫描变换所生成的形体可能会出现维数不一致问题。40本讲稿第四十页，共八十四页2.Sweep表示模型n优点：n表示简单、直观，是生成三维形体的有效方法。适合做图形输入手段；n可用来生成一些体素。n配合仿射变换可生成复杂的形体；n缺点：n用扫描变换产生的形体可能出现维数不一致的问题(非正则物体无效物体)；n扫描方法不能直接获取形体的边界信息；n表示形体的覆盖域(类型)非常有限；n作几何变换困难；41本讲稿第四十一页，共八十四页2.Sweep表示模型42本讲稿第四十二页，共八十四页6.3 常用的形体表示模型1.模型的考虑2.扫描变换(Sweep)表示模型3.构造实体几何构造实体几何(CSG)表示模型

21、表示模型4.边界表示(B-Rep)模型5.空间分割模型43本讲稿第四十三页，共八十四页3.CSG表示模型n构造实体几何表示模型对于复杂的形体都可以通过正则集合运算或几何变换操作用简单形体（体素）组合来表示。并交球柱差体素：球和柱柱球44本讲稿第四十四页，共八十四页3.CSG表示模型n由于体素表示的有效性决定了构造实体几何表示的有效性，所以在几何造型中必须细致定义各种体素。n在几何造型系统中常用的体素如图，每个体素都用简单参数变量表示，这里的参数包含体素的大小、形状、位置和方向。HHHHHHHRRRRRrRdWWWWWLLLLL45本讲稿第四十五页，共八十四页3.CSG表示模型n体素的构造：n参

22、数定义的简单形体，如球体，柱体，立方体等；n扫描变换生成的形体；n体素的表示也可以用曲面或平面半空间的交运算来表示。46本讲稿第四十六页，共八十四页3.CSG表示模型n一般地，用构造实体几何表示模型构造形体的方法无二义性，但不是唯一的，通常采用最简单的构造方法。(a)中的形体可以用(b)或(c)定义(b)A-*B(a)(c)AU*B47本讲稿第四十七页，共八十四页3.CSG表示模型n构造实体几何表示模型的构造方法可以看作一棵有序的二叉树，称为CSG树。其中叶节点可以是体素，也可以是形体运动的变换参数，非叶节点可以是正则集合运算操作，也可以是形体的几何变换（平移、旋转或缩放）操作，所有操作只对其

23、子树（子形体）起作用。n对一棵CSG树按深度优先遍历，依次执行指定的操作，结果便得到所表示的形体。nCSG树的形式定义为：:=|48本讲稿第四十八页，共八十四页3.CSG表示模型n例如：体素1、2和平移变换x作为3个叶节点，1-2和2(x)的操作结果 作为两个中间节点(非叶节点)，最终的形体(1-2)-2(x)作为根节点。49本讲稿第四十九页，共八十四页3.CSG表示模型n构造实体几何表示模型的几何造型系统一般由两部分组成：n一部分是描述通过集合运算和几何变换操作连接体素所生成子形体的CSG树的数据结构；n另一部分是描述相应体素的大小、形状、位置和方向等几何参数。n通过以上给定的构造实体几何表

24、示模型可以计算出其形体的边界表示。其计算过程如下：n对单个形体，计算其表面在何处被截断，哪些边或顶点被产生或删除？n对两个相交形体，计算由于其相交而产生的新边：n计算两相交形体的相交线段；n按几何元素分类，确定相交线段的哪一部分真正属于新形体的边（有效边）。50本讲稿第五十页，共八十四页3.CSG表示模型nCSG表示的优点：n数据结构比较简单，数据量比较小，内部数据的管理比较容易；nCSG表示可方便地转换成边界（B-Rep）表示；nCSG方法表示的形体的形状，比较容易修改。nCSG表示的缺点：n是一种体表示方法，显示/绘制时需进行转换；n对形体的表示受体素的种类和对体素操作的种类的限制，也就是

25、说，CSG方法表示形体的覆盖域有较大的局限性。n对形体的局部操作不易实现。例如：弯曲表面，对交线倒圆角；n所以在使用CSG表示模型的系统中需要结合其他表示模型或算法来解决有关问题。51本讲稿第五十一页，共八十四页6.3 常用的形体表示模型1.模型的考虑2.扫描变换(Sweep)表示模型3.构造实体几何(CSG)表示模型4.边界表示边界表示(B-Rep)模型模型5.空间分割模型52本讲稿第五十二页，共八十四页4.边界表示(B-Rep)模型nCSG表示与B-Rep表示曾为两大主流方法。80，ACM Solid modeling、欧洲CSG会议n当前B-Rep表示一统天下。n在一个几何造型系统中，往

26、往是多种方法并存，互相补充。53本讲稿第五十三页，共八十四页4.边界表示模型n边界表示模型是一种采用几何和拓扑信息来描述的表示模型。一个形体一般可以通过其边界拆成一些有界的“面”或“小片”的子集来表示，而每一个面又可以通过其边界的边和顶点来表示。若面的表示无二义性，则其边界表示模型也无二义性，但通常不一定只有唯一的表示。n四棱椎边界表示的例子如右，由4个面组成，且这种表示可以看作是含有体、面、边、顶点为节点的有向图n四棱椎边界表示也可以基于边界的三角形分解，即把形体的边界拆成一些互不重叠的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱面节点边节点顶点坐标f1f2f3.e

27、1e2e3e4.v1v2v3.(x1,y1,z1)组合结构坐标信息.54本讲稿第五十四页，共八十四页4.边界表示(B-Rep)模型n边界模型的基本拓扑实体包括：1.顶点2.边边有方向，它由起始顶点和终止顶点来界定。边的形状（Curve）由边的几何信息来表示，可以是直线或曲线，曲线边可用一系列控制点或型值点来描述，也可用显式、隐式或参数方程来描述。3.环环（Loop）是有序、有向边（Edge）组成的封闭边界。环有方向，有内、外环之分。55本讲稿第五十五页，共八十四页4.边界表示模型n边界模型表达形体的基本拓扑实体包括(参考8.2.1)：4.面面（Face）由一个外环和若干个内环（可以没有内环）来

28、表示，内环完全在外环之内。面具有方向。面的形状可以是平面或曲面。平面可用平面方程来描述，曲面可用控制多边形或型值点来描述，也可用曲面方程（隐式、显式或参数形式）来描述。对于参数曲面，通常在其二维参数域上定义环，这样就可由一些二维的有向边来表示环，集合运算中对面的分割也可在二维参数域上进行。5.体体（Body）是面的并集。56本讲稿第五十六页，共八十四页4.边界表示(B-Rep)模型n用边界模型表示形体的方法有多种：n如把面组成CSG表示模型中的体素，再组合体素生成更复杂形体；n或直接将表面的组合及其相交来生成复杂形体；n利用欧拉运算；nB-Rep模型的数据结构中比较著名的有：n翼边数据结构；1

29、972年，由美国斯坦福大学Baumgart作为多面体的表示模式提出。用这一数据结构表示多面体模型是完备的，但它不能表示带有精确曲面边界的实体。n辐射边数据结构；1986年，Weiler提出了辐射边（Radial Edge）数据结构。可表示非正则形体，及曲线边、曲面等。n数据结构根据造型系统的需求设计。57本讲稿第五十七页，共八十四页4.边界表示(B-Rep)模型n优点：n表示能力强；n精确表示物体；n几何变换容易；n适于显示处理；n缺点：n表示复杂；n有效性难以保证；(采用多边形近似时)n集合运算复杂；58本讲稿第五十八页，共八十四页q空间分割表示模型空间分割表示模型 物体的八叉树表示是一种层

30、次数据结构，是对二维空间中四叉树编码方法的物体的八叉树表示是一种层次数据结构，是对二维空间中四叉树编码方法的扩展。四叉树将二维区域分成四等分而得，八叉树是将三维区域分成八等分而得。扩展。四叉树将二维区域分成四等分而得，八叉树是将三维区域分成八等分而得。首先在空间中定义一个能够包含所表示物体的立方体。立方体的三条棱边分首先在空间中定义一个能够包含所表示物体的立方体。立方体的三条棱边分别与别与x,y,z轴平行，边长为轴平行，边长为2n。若立方体内空间完全由所表示的物体所占据，则物。若立方体内空间完全由所表示的物体所占据，则物体可用这个立方体予以表示，否则将立方体在体可用这个立方体予以表示，否则将立

31、方体在x,y,z轴三个方向都分成二等分，整轴三个方向都分成二等分，整个立方体共等分为八个小块，每块仍为一个小立方体，其边长为原来立方体边长个立方体共等分为八个小块，每块仍为一个小立方体，其边长为原来立方体边长的的1/2。将这八个小立方体依序编号为。将这八个小立方体依序编号为0，1，2，7，如图所示。，如图所示。八叉树的结点编码八叉树的结点编码 59本讲稿第五十九页，共八十四页 若某一小立方体的体内空间全部被所表示的物体占据，若某一小立方体的体内空间全部被所表示的物体占据，则将此立方体标识为则将此立方体标识为“Full”；若它与所表示物体无交，则该立；若它与所表示物体无交，则该立方体被标识为方体

32、被标识为“Empty”；否则将它标识为；否则将它标识为“Partial”，并继续分，并继续分割下去。依此方式，物体在计算机内可表示为一棵八叉树。割下去。依此方式，物体在计算机内可表示为一棵八叉树。注意，凡是标识为注意，凡是标识为“Full”或或“Empty”的立方体均为终端结的立方体均为终端结点，而标识为点，而标识为“Partial”的立方体为非终端结点。最后，当分的立方体为非终端结点。最后，当分割生成的每一小立方体的边长为单位长时，分割即告终止。此割生成的每一小立方体的边长为单位长时，分割即告终止。此时可将每一小立方体标识为时可将每一小立方体标识为“Full”。60本讲稿第六十页，共八十四页

33、 物体之间的集合运算在八叉树表示中具有十分简单的形式。物体之间的集合运算在八叉树表示中具有十分简单的形式。由定义可知，两物体的并就是这两个物体一共占有的空间，而由定义可知，两物体的并就是这两个物体一共占有的空间，而物体之间的交即它们共同占据的空间。由于物体的八叉树表示物体之间的交即它们共同占据的空间。由于物体的八叉树表示就是由它内部含有的大大小小的立方体（称为体元）组成，因就是由它内部含有的大大小小的立方体（称为体元）组成，因此对物体执行并、交、差运算时，只需同时遍历参加集合运算此对物体执行并、交、差运算时，只需同时遍历参加集合运算的两物体相应的八叉树，就可以获得拼合体的八叉树，而无需的两物体

34、相应的八叉树，就可以获得拼合体的八叉树，而无需进行复杂的求交运算。进行复杂的求交运算。61本讲稿第六十一页，共八十四页6.3 常用的形体表示模型1.模型的考虑2.构造实体几何(CSG)表示模型3.扫描变换(Sweep)表示模型4.边界表示(B-Rep)模型62本讲稿第六十二页，共八十四页第6讲 几何造型6.1 概述6.2 基础知识6.3 常用的形体表示模型6.4 三维形体的多边形表示三维形体的多边形表示6.5 过程模型6.6 常见实体造型系统简介63本讲稿第六十三页，共八十四页6.4 三维形体的多边形表示n造型的应用？nCAD/CAM中，需要精确的表示。实体模型。n游戏、动画等显示或绘制环境中

35、，只需要可接受的视觉效果。往往采用多边形网格来近似表示物体。n多边形表示的精度由多边形网格的数量决定。64本讲稿第六十四页，共八十四页6.4 三维形体的多边形表示n多边形网格实际上就是物体表面(faces)的近似多边形的集合。n为什么要采用多边形网格来表示形体？n结构简单，可表示任意形体。虽然不精确，但足以满足视觉的需要。n在光照处理、纹理映射等算法中易于处理多边形(计算属性简单，如法向量等)，便于硬件实现。65本讲稿第六十五页，共八十四页第6讲 几何造型6.1 概述6.2 基础知识6.3 常用的形体表示模型6.4 三维形体的多边形表示6.5 过程模型过程模型6.6 常见实体造型系统简介66本

36、讲稿第六十六页，共八十四页6.5 过程模型1.分形几何分形几何2.随机插值模型3.迭代函数系统4.基于文法的模型：L系统5.粒子系统6.动力系统67本讲稿第六十七页，共八十四页1.分形几何n真实的世界却并不规则。n闪电不是直线，海岸线不是弧线，云团不是球体，山峦也不是锥体。自然界的许多对象是如此不规则和支离破碎，以致欧氏几何学不能真实有效地再现大自然。n为了再现真实世界，必须选择新的工具，分形几何学应运而生。n分形几何是以非规则物体为研究对象的几何学。由于闪电、海岸线、云团、山峦、海浪、野草、森林、火光等非规则物体在自然界里比比皆是，因此分形几何学又被称为描述大自然的几何学。68本讲稿第六十八

37、页，共八十四页1.分形几何n分形（Fractal）这个词，是由美籍法国数学家曼德尔布罗特（Benoit B.Mandelbrot）自己创造出来的，此词来源于拉丁文fractus，意为不规则、支离破碎。n1967年曼德尔布罗特在美国科学杂志上发表了划时代的论文英国海岸线有多长？统计自相似与分数维，成为其分形思想萌芽的重要标志。n1973年，在法兰西学院讲学期间，曼德尔布罗特提出了分形几何学的整体思想，并认为分数维是个可用于研究许多物理现象的有力工具。n1982年曼德尔布罗特出版了大自然的分形几何学，引起了学术界的广泛重视，曼德尔布罗特也因此一举成名。n1985年获得Barnard奖章（物理学，每

38、五年一次）69本讲稿第六十九页，共八十四页1.分形几何n67年，Mandelbrot提出“英国的海岸线有多长？”n正确的答案令人吃惊：是不确定的，其长度依赖于测量单位的长度。70本讲稿第七十页，共八十四页1.分形几何n分形物体的基本特征：1.自相似性指局部与整体相似的性质。一座座山峰和整体山脉，河流中一个个支流和整体河川，茂密的树木上的一条条树杈和整体树木等，均具有自相似性。如图所示的是蕨类植物叶子上的细叶和整体叶子的相似性。71本讲稿第七十一页，共八十四页n分形物体的基本特征：2.无标度性 标度是计量单位的刻度。比如长度的标度是米；重量的标度是公斤；面积的标度是平方米等。对欧氏几何学内的不同

39、形体，可以选择不同的标度去度量。例如，直线是多长，面积是多大，体积是多少。自然界中很多的物体具有特征长度，如人有高度、山有海拔等等。1.分形几何72本讲稿第七十二页，共八十四页1.分形几何n分形的定义。一般认为，满足下列条件的图形称为分形集：n分形集具有任意尺度下的比例细节，或者说具有无穷的精细结构；n分形集是不规则的，以致于不能用传统的几何语言来描述。n分形集通常具有某种自相似性，或许是近似的或许是统计意义下的自相似。n分形集在某种方式下定义的“分数维”一般大于它的拓扑维数。n分形集的定义常常是非常简单的，或许是递归的。73本讲稿第七十三页，共八十四页2.随机插值模型n1982年由Alain

40、 Fournier，Don Fussell和Loren Carpenter提出：能有效地模拟海岸线和山等自然景象，不是事先决定各种图素和尺度，而是用一个随机过程的采样路径作为构造模型的手段。n构造二维海岸线的模型可以选择控制大致形状的若干初始点。再在相邻两点构成的线段上取其中点。并沿垂直连线方向随机偏移一个距离，再将偏移后的点与该线段两端点分别连成两个新线段。n这样下去可得到一条曲折的有无穷细节回归的海岸线，其曲折程度由随机偏移量控制，它也决定了分数维的大小。74本讲稿第七十四页，共八十四页2.随机插值模型n在三维情况下可通过类似过程构造山的模型，一般通过多边形（简单的如三角形）细分的方法。n

41、可以在一个三角形的三边上，随机各取一点，沿垂直方向随机偏移一段距离得到新的三个点，再连接成四个三角形，如此继续，即可形成皱褶的山峰。山的褶皱程度由分数维控制。75本讲稿第七十五页，共八十四页3.迭代函数系统nIterated Function System（简称 IFS）n在SIGGRAPH85国际会议上，Demko，Barnsley等人作过IFS的专题报告。n应用n自然景物的模拟n图像压缩76本讲稿第七十六页，共八十四页3.迭代函数系统n谢尔宾斯基垫片生成规则：取一等边三角形，连接各边中点将原三角形分成四个小三角形，然后舍弃位于中间的一个小三角形，将剩下的其余三个小三角形按同样方法继续分割，

42、并舍弃位于中间的那个三角形，如图所示。如此不断地分割与舍弃，就能得到中间有大量孔隙的Sierpinski垫片。Sierpinski carpetSierpinski gasket77本讲稿第七十七页，共八十四页4.基于文法的模型：L系统n由美国生物学家Lindenmayer创立，后来由Smith等人将L系统引入图形学。n1990年，”The Algorithmic Beauty of Plant”n是一种形式语言，通过符号串的解释，转化为造型工具n基本思想：n用文法表示植物的拓扑结构；n通过图形学方法生成逼真的画面。78本讲稿第七十八页，共八十四页4.基于文法的模型：L系统n一个例子：13世纪

43、数学家Fibonacci，（1170-1250），n兔子的理想化繁衍字符串a，b，改写规则aab;banbaby：b；adult：abaababaabaababaababaabaababaabaababaababaabaababaababa79本讲稿第七十九页，共八十四页4.基于文法的模型：L系统n例子：von Koch 雪花曲线nw：FnFF-F+F-Fn几何解释nF：向前画一条线n+：右转n-：左转80本讲稿第八十页，共八十四页4.基于文法的模型：L系统n例子：植物w：F F F+FF-FF:将当前植物生长的状态压入堆栈，信息包括所在位置和方向等。:从堆栈中弹出一个状态作为植物的当前状态，

44、但不画线。81本讲稿第八十一页，共八十四页5.粒子系统(Particle System)nW.T.Reeves 1983年提出随机模型，它用大量的粒子图元(Particle)来描述景物。n最初引入是为了模拟火焰，火焰被看作是一个喷出许多粒子的火山。每个粒子都有一组随机取值的属性，如起始位置、初速度、颜色及大小。n方法n一个粒子系统由一些随时间变化的粒子构成了；n每个粒子有一个生命周期，包括出生、成长、灭亡等几个阶段，演化过程有一定的规则控制；n粒子在不同的阶段具有不同的形态；n粒子的运动由一定的规则控制。82本讲稿第八十二页，共八十四页5.粒子系统(Particle System)n描述对象：结构随时间而变化的物体。n跳动的火焰n飘浮不定的云彩、烟、雾n远处的草地、森林n每个粒子的位置、取向及动力学性质都是由一组预先定义好的随机过程来说明的。n模拟草丛、森林等全景要求高的景象。n该模型是由粒子刻划的，因而适合描述动态的火焰、烟和被风吹动的草等。83本讲稿第八十三页，共八十四页第6讲 几何造型结束！84本讲稿第八十四页，共八十四页