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