几何变换集合运算构建客观存在或想象中的形体模型是课件

1、几何造型就是通过点、线、面和立体等几何元素的定义、几何变换、集合运算构建客观存在或想象中的形体模型，是确定形体形状和其它几何特征方法的总称。 第三章 几何造型2022/8/91提出问题如何在计算机中建立恰当（完整、精确、快速）的几何造型的模型表示不同图形对象？如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快？2022/8/92本章内容提要 计算机内基本几何元素和形体的定义 形体的表示模型和数据结构 三维形体常用的几何造型方法 几何造型的实例 2022/8/93第一节 形体的计算机表示、表示形体的坐标系2022/8/94 一般采用右手三维笛卡儿坐标系 一般与

2、用户定义形体和图素的坐标系一致 用于定义用户整图或最高层图形结构 用户坐标系分为以下五种:直角坐标系也称为（笛卡儿坐标系），仿射坐标系，圆柱坐标系，球坐标系，极坐标系。1.用户坐标系（WCS：World Coordinate System，也称世界坐标系）2022/8/95 右手三维直角坐标系，用来定义基本形体或图素 每一个形体和图素都有各自的坐标原点和长度单位 3.观察坐标系(VCS：Viewing Coordinate System) 可看作是局部坐标系（Local Coordinates） 左手三维直角坐标系，用来产生形体、图形的视图 用于指定裁剪空间 把三维形体的用户坐标变换成规格化的

3、设备坐标 2.造型坐标系(MCS：Modeling Coordinate System)2022/8/965.设备坐标系（DCS：Device Coordinate System） 使图形处理过程做到与设备无关 设备坐标规定为0X1，0Y1 左手三维直角坐标系，用来定义视图区 可提高应用程序的可移值性 设备坐标系是与图形设备相关联的坐标系 采用左手三维直角坐标系 通常也是定义象素(Pixel)或位图(bitmap)的坐标系 4.规格化的设备坐标系（NDCS：Normalized Device Coordinate System）2022/8/97各类坐标系之间的关系 2022/8/98点是0维

4、几何元素，分端点、交点、切点和孤立点等。在自由曲线面的描述中常用三种类型的点：控制点、型值点、插值点 边是1维几何元素，是两个邻面（正则形体）或多个邻面（非正则形体）的交界。直线边、曲线边二、基本几何元素2022/8/99环是有序、有向边（真线段或曲线段）组成的面的封闭边界。环中的边不能相交，相邻两条边共享一个端点确定面的最大外边界的环称之为外环确定面中内孔或凸台边界的环称之为内环在面上沿一个环前进，其左侧总是面内，右侧总是面外。2022/8/910是2维几何元素，是形体上一个有限、非零的区域，由一个外环和若干个内环界定其范围。 一个面可以无内环，但必须有一个且只有一个外环 面有方向性面常用的

5、面包括平面、二次面、双三次参数曲面等。 2022/8/911体 素是3维几何元素，由封闭表面围成空间，也是欧氏空间R3中非空、有界的封闭子集，其边界是有限面的并集。体素有三种定义形式 单元实体，参数定义，代数半空间定义 壳（shell），也称外壳，是一些点、边、环、面的集合。 2022/8/912形体的层次结构2022/8/913三、形体的分类与定义按所构造的对象来划分，可分为规则形体和不规则形体。 规则形体是指可以用欧氏几何进行描述的三维物体，如点、直线、曲线、平面、曲面或三维立体等及它们的规则组合。规则形体的造型是本章描述的重点。1.形体的分类2022/8/914不规则形体是指不能用欧氏几

6、何进行描述的物体，如山、树、草、云、火、波浪等自然界的复杂物体。 不规则形体大多采用过程式模拟，即用一个简单模型和少量易于调节的参数来表示一大类形体，不断改变参数，递归调用这一模型就能产生数量很大的形体，这一技术也称为数据放大技术 。基于分维数理论的随机插值模型、基于文法的模型、粒子系统模型。不规则形体造型方法主要有：2022/8/9152. 形体的边界所有实际形体都可看作是由封闭表面围成的空间，其边界是有限面的并集，而壳是形体的最大边界。对于任何区域都可以用完全在区域之中（i）和在其边界上（b）的全部点来定义，表示区域的点集可以表示成ib。 2022/8/9163. 形体的定义 对于形体表面

7、上任意一点，如果围绕该点的形体邻域在二维空间中可以构成一个单连通域，且它与封闭圆之间存在着连续的一一对应关系，那么我们称形体表面具有的这种性质为二维流形，把表面具有二维流形性质的形体称为正则形体。 (a) 二维流形 (b) 二维流形 (c) 非二维流形 (d) 非二维流形2022/8/9174. 形体的表示模型 在计算机中，形体常用线框模型、表面模型、实体模型来表示。 线框模型应用最早，也是最简单的一种形体表示方法； 采用三维空间的线段表达三维形体的棱边。 优点：采用线框模型描述形体所需信息最少，数据运算简单，所占的存贮空间也比较小；对硬件的要求也不高，容易掌握，处理时间较短。2022/8/9

8、18 四棱柱、四棱锥和圆柱的线框模型 局限性：信息表达不完整、不易表达曲面体。 2022/8/919 表面模型是在线框模型的基础上，增加有关面、边信息以及表面特征、棱边连接方向等内容逐步形成的。 早期的Coons、Ferguson、Bezier等方法 80年代后期，非均匀有理B样条（NURBS）方法用于曲线曲面的描述 表面模型采用有向棱边围成的部分来定义形体表面，由面的集合来定义形体。 优点：具有很好的显示特性能够以消隐、小平面着色、平滑明暗、颜色和纹理等方式显示形体。 2022/8/920四棱柱和圆柱的表面模型 (a) 模型消隐后的效果 (b) 模型着色后的效果局限性：不能切开形体而展示其内

9、部结构；物体的实心部分在边界的哪一侧是不明确的，使设计者对物体缺乏整体的概念等等。 2022/8/921 实体模型 在表面模型的基础上定义了表面的哪侧存在形体，一般采用三种方法来定义： (1)在定义表面时，给出形体存在侧的一点P;(2)直接用表面的外法矢来指明形体存在的一侧;(3)采用有向棱边隐含地表示表面的外法矢方向，有向棱边按右手法则取向，沿闭合的棱边所得的方向与表面的外法矢方向一致;2022/8/922 (a)给出一点 (b)采用表面外法矢 (c)采用有向棱边 (d)形体拓扑检验图无法准确地描述和控制形体的外部形状；只能产生正则形体；不能描述具有工程语义的实际形体如具有实际工程意义的加工

10、孔、槽等；不能为其后续系统（CAM/CAPP等）提供非几何信息如材料、公差等。实体模型的局限性2022/8/923实用的几何造型系统中，常常综合使用线框模型，表面模型和实体模型，以相互取长补短。 表示模型优点局限性应用范围线框模型结构简单、易于理解、运行速度快无观察参数的变化；不可能产生有实际意义的形体；图形会有二义性；画二维线框图（工程图）、三维线框图表面模型完整定义形体表面，为其他场合提供表面数据不能表示形体艺术图形；形体表面的显示；数控加工实体模型定义了实际形体只能产生正则形体；抽象形体的层次较低物性计算；有限元分析；用集合运算构造形体 三种模型的比较2022/8/924第二节 数据结构

11、、几何信息与拓扑信息图形对象及构成它的点、线、面的位置、相互间关系和几何尺寸等都是图形信息；表示图形对象的线型、颜色、亮度以及供模拟、分析用的质量、比重、体积等数据，是有关对象的非图形信息。2022/8/925图形信息又包括：几何信息：形体在欧氏空间中的位置和大小拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。1. 点、线、面的几何信息 (1)几何分量的数学表示2022/8/926(2)几何分量之间的相互关系2022/8/927几何信息的二义性2. 点、线、面的拓朴信息平面立体的几何分量之间一共有九种拓扑关系:2022/8/9282022/8/929刚体运动：不改变图形上任意两点

12、间的距离，也不改变图形的几何性质的运动。拓扑运动：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。拓扑等价、拓扑性质2022/8/930二、线框模型的数据结构将形体的几何信息和拓扑信息记录在边表及顶点表中。 四棱柱的线框模型 四棱柱线框模型中边与顶点的关系2022/8/931边表顶点表边号边端点号顶点号XYZe1v1v2v1x1y1z1e2v2v3v2x2y2z2e3v3v4v3x3y3z3e4v4v5v4x4y4z4e5v5v6v5x5y5z5e6v6v7v6x6y6z6e7v7v8v7x7y7z7e8v8v1v8x8y8

13、z8e9v1v5e10v2v6e11v3v7e12v4v82022/8/932三、表面模型的数据结构 将形体以三张表的形式表示，即面表、边表、顶点表，并以单链指示它们之间的关系。 通常把这种结构称为以面为中心的顶点棱边面（V-E-F）树形结构，或单链三表结构。 (a) 三棱锥的表面模型 (b) 三棱锥表面模型中点、边、面的关系2022/8/933 特点：是结构关系清楚，节省存储空间，检索比较容易。 缺点：它不宜于频繁地进行交互地修改。 2022/8/934四、实体模型的数据结构1. 翼边结构 在顶点、棱边、表面等组成物体的三要素中，翼边结构以边为中心来组织数据。 2022/8/935 翼边结构

14、中边的数据结构V1lLeLcc，eLcw，eRcc，eRcwV2lR(a) 棱边指针结构(b) 顶点指针(c) 环指针(d) 面环表2022/8/936 翼边结构的存储方式2022/8/937 翼边结构存在的问题：需要较多的存储单元，对机器的存储容量有一定的要求；在边的构造与使用方面还比较复杂。 为此对其进行了改进，提出了半边数据结构。半边结构已成为边界表示的主流数据结构。 半边数据结构与翼边数据结构的主要区别在于该结构将一条物理边拆成两条边表示，使其中每条边只与一个邻接面相关 。2022/8/9382. 半边结构 由于半边数据结构中的边只表示相应物理边的一半信息，故称为半边。半边数据结构在拓

15、扑上也分为五个层次，即体-面-环-半边-顶点。 半边结构2022/8/939 半边数据结构的层次结构2022/8/9404.以顶点为中心的数据结构。 3.以面为中心的数据结构面顶点坐标F1(X1Y1Z1，X2Y2Z2，X3Y3Z3，X4Y4Z4)F2(X1Y1Z1，X2Y2Z2，X6Y6Z6，X5Y5Z5).顶点/坐标表面/顶点序列表顶点坐标面顶点序列V1X1Y1Z1F1V1V2V3V4V2X2Y2Z2F2V1V2V6V52022/8/941第三节 常用的几何造型方法线框模型、表面模型和实体模型是一种广义的概念，并不反映形体在计算机内部、或对用户而言所用的具体表示方式。从用户角度看，形体表示以

16、特征表示和构造的实体几何表示（CSG）较为方便；从计算机对形体的存储管理和操作运算角度看，以边界表示（BRep）最为实用。为了适合某些特定的应用要求，形体还有一些辅助表示方式，如单元分解表示和扫描表示。总体而言，比较传统和常用的造型方法有以下几种：2022/8/942 传统和常用的造型方法有以下几种： 扫描表示法（Sweep Representation）构造实体几何法（Constructive Solid Geometry）边界表示法（Boundary Representation Scheme）基本体素表示法（Pure Primitive Instancing）空间位置枚举法（Spatia

17、l Occupancy Enumeration）单元分解法（Cell Decomposition）2022/8/943新的表示方法：八叉树表示法特征造型表示法曲面离散化近似表示法元球造型法2022/8/944 该表示法的覆盖率形体范围的大小造型能力的强弱 蕴含信息的完整性数据结构是否唯一能否为后续工作提供信息选择方法时需考虑以下两点：2022/8/9451. 边界表示法（ BR表示或BRep表示）边界: 形体内部点与外部点的分界面将形体的边界分成有限个“面”（faces）或“片”（patches） (a) (b)2022/8/9462022/8/9472022/8/9482022/8/949利

18、用正则集的概念来定义上述的三维有效物体：点的领域：如果P是点集S的一个元素，那么点P的以R（R0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。边界点2022/8/950定义点集的正则运算r运算为：正则运算即为先对物体取内点再取闭包的运算。rA称为A的正则集。 2022/8/9512022/8/952二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。 2022/8/953实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实

19、体。 该定义条件可检测2022/8/9544.1.6 正则集合运算有效实体的封闭性 把能够产生正则形体的集合运算称为正则集合运算2022/8/9552022/8/956有两种方法实现正则运算间接方式：点的领域，即集合S在点P附近的局部几何性质：当且仅当P的领域为满时，P在S之内；当且仅当P的领域为空时，P在S之外；当且仅当P的领域既不满也不空时，P在S的边界上。2022/8/9572022/8/958直接方式：在三维空间中，给定一个正则形体S，空间点集被分为三个子集：S的内部点集S的边界点集S之外的点集2022/8/959分类函数： 若给定一个正则形体S及一个有界面G，则G相对于S的分类函数可

20、为： C(S,G)=G in S, G out S, G on S 其中， 2022/8/960用-G表示有界面G的反向面。即，如果有界面G在P点的法向为NP(G)，则有界面-G在P点的法向就是-NP(G)。于是：G on S=G shared (bS), G shared (-bS)其中， 2022/8/961则G相对于S的分类函数C(S,G)可为：C(S,G)=G in S, G out S, G shared (bS), G shared (-bS)正则集合算子 定义三个正则集合算子关于边界面的表达式：2022/8/9622022/8/9634.1.7 平面多面体与欧拉公式平面多面体是表

21、面由平面多边形构成的三维物体。简单多面体指与球拓扑等价的那些多面体。欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下关系：V-E+F=2。2022/8/9642022/8/965令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G）2022/8/966线框模型线框模型存在着几个缺陷：二义性4.2 三维形体的表示2022/8/967容易构造出无效形体2022/8/968不能正确表示曲面信息。2022/8/969无法进行图形的线面消隐。加重用户的输入负担难以保证数据的统一性和有效性。2022/8/970

22、实体模型（实体造型技术）可以将实体模型的表示大致分为三类：边界表示（Boundary representation, B-reps）构造实体几何表示空间分割（Space-partitioning）表示2022/8/9714.2.1 多边形表面模型边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。2022/8/9721. 多边形表几何表属性表 例如：顶点表、边表和多边形表。为图4-17所示的四面体建立的三张表如下：2022/8/973顶点表边表面表Ax1,y1,z1ABA,BABCAB,BC,ACBx2,y2,z2BCB,CAB

23、DAB,BD,ADCx3,y3,z3CAC,ABCDBC,CD,BDDx4,y4,z4ADA,DACDAC,CD,ADBCB,CCDC,D2022/8/974表示其拓扑信息例如，翼边结构表示（Winged Edges Structure）2022/8/9752. 平面方程可以利用平面方程：求得平面的法向量鉴别空间上的点与物体平面的位置关系。判别点在面的内部或外部2022/8/9763. 多边形网格三维形体的曲面边界通常用多边形网格（polygon mesh）的拼接来模拟。三角形带、四边形网格2022/8/9774.2.2 扫描表示（sweep representation）扫描表示法（swee

24、p representation）可以利用简单的运动规则生成有效实体。包含两个要素：一是作扫描运动的基本图形；二是扫描运动的方式。 2022/8/978扫描运动的方式有：旋转扫描非圆形路径扫描广义扫描法2022/8/9794.2.3 构造实体几何法构造实体几何法（CSG，Constructive Solid Geometry）由两个实体间的并、交或差操作生成新的实体。2022/8/980在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述：树的叶子树的非终端结点二叉树根结点2022/8/981构造实体几何法的优点：可以构造出多种不同的符合需要的实体。问题：求交困难CSG

25、树不能显式地表示形体的边界解决：光线投射（Ray-casting）算法2022/8/982光线投射（Ray-casting）算法核心思想：2022/8/983具体算法是：1)将射线与CSG树中的所有基本体素求交，求出所有的交点。2)将所有交点相对于CSG树表示的物体进行分类，确定位于物体边界上的那部分交点。3)对所有位于物体边界上的交点计算它们在射线上的参数值并进行排序，确定距离最近的交点。得到其所在基本体素表面的法矢量。2022/8/9844.2.4 空间位置枚举表示空间位置枚举表示法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对象。二维情况

26、，常用二维数组存放。三维情况下，常用三维数组pijk来存放。2022/8/9854.2.5 八叉树八叉树（octrees）又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体。2022/8/986四叉树2022/8/987八叉树2022/8/9884.2.6 BSP树二叉空间分割（binary space partitioning，BSP）方法每次将一实体用任一位置和任一方向的平面分为二部分。2022/8/9894.3 非规则对象的表示基于分数维理论的随机模型基于文法的模型粒子系统模型2022/8/9904.3.1 分形几何(fractal geometry)分形几何物

27、体具有一个基本特征：无限的自相似性。无限的自相似性是指物体的整体和局部之间细节的无限重现。分形物体的描述又包含：分形维数，又称分数维数生成过程：初始生成元（initiator）、生成元（genenator）2022/8/9914.3.2 形状语法形状语法（shape grammars）：给定一组产生式规则，形状设计者可以在从给定初始物体到最终物体结构的每一次变换中应用不同的规则。2022/8/9924.3.3 微粒系统用于模拟自然景物或模拟其它非规则形状物体展示“流体”性质的一个方法是微粒系统（particle systems）。这一方法尤其擅长描述随时间变化的物体。微粒运动的模拟方式：随机过

28、程模拟、运动路径模拟、力学模拟2022/8/9934.3.4 基于物理的建模基于物理的建模方法：描述了物体在内外力相互作用下的行为。通常用一组网格结点来逼近物体。网格结点间取为柔性连接，再考虑贯穿物体网格的力传递。基于力学方程的动画描述比基于运动学方程的描述产生的运动更真实。实例2022/8/9944.3.5 数据场的可视化科技计算可视化（scientific visualization）指的是运用计算机图形学和图象处理技术，将科学计算过程中及计算结果的数据转换为图形及图象在屏幕上显示出来并进行交互处理的理论、方法和技术。有三种不同类型的数据需要实现可视化：2022/8/995标量：若对每一个

29、直角坐标系oxyz有一个量，它在坐标变换时满足下式，即保持其值不变，则此量定义了一个标量。 2022/8/996矢量：对于每一个直角坐标系ox1x2x3来说有三个量x1,x2,x3，它们可根据下式变换到另一个坐标系ox1x2x3，则此时三个量定义了一个矢量。2022/8/997二阶张量：如果对每一个直角坐标系ox1x2x3，有9个量Xij(i=1,2,3;j=1,2,3)，它可以按照以张量形式表示的下述公式转换为另一个直角坐标系中的9个量Xij(i=1,2,3;j=1,2,3)，则这9个量定义了一个二阶张量。 2022/8/998显然，二阶张量可以表示为一个33矩阵： 2022/8/999二阶张量的定义可以推广到n阶张量。当n=0时，张量的分量