图形学第7章 实体造型技术

*第7章三维实体造型技术提出问题如何在计算机中建立恰当的模型表示不同图形对象如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快*造型技术:把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术.有两类图形对象：规则对象：几何造型、几何模型不规则对象*线框模型是用顶点和棱边来表示三维物体的模型。为了确切地表示清楚物体的形状和位置，必须给出顶点集的位置和它们之间的连边规则。线框模型的优点：结构简单，用顶点和棱边来表示物体，具有模型简单、实现方便、运算量小、显示迅速等优点。对于平面多面体（表面由平面多边形构成的三维体）而言，用线框模型是很自然的。7.1线框模型线框模型存在着几个缺陷(1)用三维线框模型表示三维形体常常具有二义性**(2)由于不存在面的信息，三维线框模型容易构造出无效形体*不能正确表示曲面信息。无法进行图形的线面消隐。 加重用户的输入负担难以保证数据的统一性和有效性。*实体模型（实体造型技术）可以将实体模型的表示大致分为三类：表面模型（Boundaryrepresentation,B-reps）构造实体几何表示空间分割（Space-partitioning）表示*优点：模型的数据结构简单，数据存储量小；缺点：不能自动消隐，几何描述能力差；不能进行诸如体积、面积、重量、惯性矩等几何特性的计算；一、线框造型——物体的骨架*二、曲面造型——物体的皮肤*◆Bézier方法◆B样条方法◆非均匀有理B样条（NURBS）*飞机气道模型——三角网络上的复合Bézier曲面*基于四边形的C-C细分曲面*三．实体造型——“有血有肉”的物体模型7.2表面模型7.2.1三维物体的边界表示*边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。而每个面又由它所在的曲面的定义加上其边界来表示，面的边界是边的并集，而边又是由点来表示的。*BoundaryRepresentation，也称BR表示或BRep表示最成熟、无二义性物体的边界与物体一一对应实体的边界是表面的并集表面的边界是边的并集*图7-3四面体的点、边、面之间的关系几何信息（Geometry）与拓扑信息（Topology）拓扑信息：描述形体上的顶点、边、面的连接关系，拓扑信息形成物体边界表示的“骨架”。几何信息：犹如附着在"骨架"上的肌肉。例如形体的某个表面位于某一个曲面上，定义这一曲面方程的数据就是几何信息。此外，边的形状、顶点在三维空间中的位置（点的坐标）等都是几何信息，一般说来，几何信息描述形体的大小、尺寸、位置、形状等。*拓扑信息与几何信息分开表示具有许多优点1.如便于具体查询物体中各元素，获取它们的相关信息；2.容易支持对物体的各种局部操作；3.对于具有相同拓扑结构而只是大小、尺寸不同的一类物体可以用统一的数据结构加以表示；4.便于在数据结构上附加各种非几何信息。*体体有扩大的含义，可以是一根或多根线，可以是不封闭的壳，称作板，也可以是若干个离散的体，合成一个处理。线可以是作图的辅助线，中心线或扫成曲面的母线，也可以退化成一个辅助点；也可以是未蒙皮的线框模型。壳正常情况下壳是一个完整物体的封闭边界。一个连通的物体有一个外壳和若干个可能的内壳，后者构成体内的边界。壳也可能是无边界的无限面或有部分边界的半无限面。板是壳的中性层表面，没有厚度，正反面都有效。子壳壳或子壳的一个分割，系统通常用它来提高壳与壳相关性判断的效率。面空间一张几何面的有界部分、它的边界由一个或多个环组成。球是封闭的面，但没有环。环环是面边界的连通部分。从名称看，环应该封闭，实际上可以不封闭。共边用来存放一条边与相邻边以及与环的关系。在正常的实体中一条边严格为两个邻面所共有，这时共边成对出现，各与一个面环相关联。边一条空间曲线的有界部分。顶点面的角点。线边的有序连接。实体模型的表示——ACIS*ACIS数据结构表示的四面体模型*边界表示拓扑图翼边结构拓扑信息采用翼边结构表示，这种存储平面物体数据模型的方法，主要供物体的集合运算调度使用。如图7-4所示。翼边结构的定义方法当从物体外部观察该物体的一条棱边时，该有向边有左右两个相邻的有界平面，以及两个邻面中与该有向边相邻的四条有向边（图7-4中的左上边、左下边、右上边、右下边）等，这两个相邻面与四条有向边好象有向边PS-PE的双翼，因而取名为翼边结构。优点:(1)翼边结构对于在明暗处理时，实现跨越一边的两多边形之间的平滑光顺特别有利。(2)便于在几何表中附加信息，如每条边的斜率等。翼边结构的数据存储方式分五个层次来存储:物体的壳表、面表、环表、边表及顶点表。Brep表示的缺点是：数据结构复杂，需要大量的存储空间，维护内部数据结构的程序比较复杂；Brep表示不一定对应一个有效形体，通常运用欧拉操作来保证Brep表示形体的有效性、正则性等。优点：Brep表示覆盖域大，原则上能表示所有的形体，而且易于支持形体的特征表示等，Brep表示已成为当前CAD/CAM系统的主要表示方法。7.2.2扫描表示扫描运算的基本思想：沿着某种轨迹移动点、曲线或曲面，所产生的轨迹定义为一维、二维或三维物体；扫描运算要求定义:要移动的物体和移动的轨迹；物体可以是曲线、曲面或实体；轨迹则是可分析的、可定义的轨迹；扫描运算分为三种：平移式、旋转式和广义扫描。如图7-7表示了扫描面、平移扫描体和旋转扫描体的形成原理。(a)基线平移形成的扫描面(b)基线旋转形成的旋转扫描面(c)基面平移形成具有一定厚度的扫描体(d)基面旋转形成的旋转扫描体(1)平移扫描若一个二维区域（图形）沿着轨迹作直线移动而形成空间区域（三维图形），这种方法称平移扫描。常用的立方体和圆柱体等基本体素即可用此法生成，如图7-8所示。*(2)旋转扫描若将一平面区域沿某一轴线旋转某一角度（00到3600的角度），即为旋转扫描。旋转扫描的特点是生成轴对称的物体，如图7-9所示。*（3）广义扫描若将一平面区域沿任意的空间轨迹线移动，生成一个三维物体，即为广义扫描。如图7-10所示为用不等截面的圆盘沿任意的轨迹移动构成的三维物体。图7-10表示了一个广义扫描的实例。**7.3实体模型的表示实体造型体素的定义和描述体素之间的拼合体素构造法边界表示法7.3.1正则形体及正则运算正则形体集（R-Set）是几何造型的理论基础。定义:对于任一形体，具有3维欧氏空间R3中非空、有界的封闭子集，且其边界是二维流形（即该形体是连通的），我们称该形体为正则形体，否则称为非正则形体。二维流形（2-manifold）是指这样一些面，其上任一点都存在一个充分小的邻域，该邻域与平面的圆盘是同构的，即在该邻域与圆盘之间存在连续的一一映射。*集合运算（并、交、差）是构造形体的基本方法。正则形体经过集合运算后，可能会产生悬边、悬面等低于三维的形体。正则集合运算：正则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面等。*正则集*图7-11非正则体*集合论的求交运算正则集合的求交运算图7-12集合与正则集合的求交运算*7.3.2构造实体几何表示(CSG)1.几何表示（CSG，ConstructiveSolidGeometry）是由两个实体间的并、交或差操作生成新的实体。*2、几何运算的基础是对参与运算的元素进行分类。*3.体素分类是求两组元素的组合。*表1.2对于拼合体的分类*5、当集合运算的结果有二义性时，利用邻域进行测试。*从上图中可以看出，基本体素通过集合运算，可以生成新的物体，不断地通过的集合运算可以生成复杂的三维物体。如下图所示。**几何定义语句：PART=I+II-III-IV*任何复杂的形体都可以通过简单形体（体素）的组合来表示。CSG树是一棵有序的二叉树。其终端节点或是体素、或是形体变换参数。非终端结点或是正则的集合运算，或是变换（平移和/或旋转）操作，这种运算或变换只对其紧接着的子结点（子形体）起作用。CSG树是无二义性的，但不是唯一的。CSG法的基本思想*CSG树的数据结构CSG树可定义为：::=1.CSG树是无二义性的，但不是唯一的。2.除操作码外，其余均以指针形势存贮。3.操作码为0，表示基本体素结点。左、右子树为NULL.4.非终端结点，操作码为集合运算符。基本体素结点为NULL。5.坐标变换:进行变化前，所作坐标变换的信息*6、对CSG表示采用分治（Divide-and-Conquer）算法。所谓分治，就是对于实际中遇到的问题，倘若它比较复杂，不能直接求解，就将这个问题分割成若干小问题分别求解；然后再将求得的小问题的解合成整个问题的解。递归模式*ProcedureClassLine3D(L,S)ifSisaprimitiveThenClassLine3DwrtPrim(L,S)elseCombineLine3D(ClassLine3D(L,Left_S),ClassLine3D(L,Right_S),Op_S)*采用CSG表示三维物体的优点是：1）可以构造出多种不同的符合需要的实体；2）数据结构比较简单，数据量比较小，内部数据的管理比较容易；3）CSG表示可方便地转换成边界（Brep）表示；4）CSG方法表示的形体的形状，比较容易修改。CSG表示的缺点1）对形体的表示受体素的种类和对体素操作的种类的限制，即CSG方法表示形体的覆盖域有较大的局限性；2）对形体的局部操作不易实现，例如，不能对基本体素的交线倒圆角；3）由于形体的边界几何元素（点、边、面）是隐含地表示在CSG中，故显示与绘制CSG表示的形体需要较长的时间。*7.3.3光线投射算法构造实体几何法存在的主要问题是:求交困难,不能直观地表示形体的边界。解决方法:采用光线投射（Ray-casting）算法。该算法思想:从显示屏（投影平面）的每一个像素位置发射一根光线（射线），求出射线与距离投影平面最近的可见表面的交点和交点处的表面法矢量，然后根据光照模型计算出表面可见点的色彩和亮度，生成实体的光栅图形。**算法关键如何确定光线与距离投影平面最近的可见面的交点，通过集合成员分类。*具体算法是：1)将射线与CSG树中的所有基本体素求交，求出所有的交点。2)将所有交点相对于CSG树表示的物体进行分类，确定位于物体边界上的那部分交点。3)对所有位于物体边界上的交点计算它们在射线上的参数值并进行排序，确定距离最近的交点。得到其所在基本体素表面的法矢量。算法特点光线投射算法用一维集合运算代替了CSG实体的边界生成算法所需的三维集合运算，简单可靠。但光线投射算法是近似的，精度取决于显示屏幕的分辨率。另外，光线投射算法还可用来求CSG实体的物理性质，如体积和质量等。*7.4空间划分表示法空间划分:物体被分割表示为互不相交的“粘合”在一起的基本体素。基本体素的大小、位置、类型可以多种多样，但它们的形状比较简单。空间划分表示法对形体分解到何种程度依赖于实体需要怎样的基本实体，以便于准备完成感兴趣的运算。常用的空间划分表示方法：空间位置枚举表示和八叉树表示。**1空间位置枚举表示空间位置枚举:将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对象。形体可以用唯一且可以明确表示单元是否为空的方法进行表示二维情况，常用二维数组存放。三维情况下，常用三维数组p[i][j][k]来存放。空间位置枚举的应用空间位置枚举：通常应用于生物医学领域，用来表示体数据，这些数据来自计算机X射线、轴向分层造影（CAT）扫描等途径。空间位置枚举的特点：是一种穷举表示法，它可以用来表示任何实体。采用这种表示法很容易实现实体的集合运算以及体积计算等。*空间位置枚举的缺点(1)没有明确给出实体的边界信息，不适于图形显示，(2)要存储全部有关的信息需要大量的存储空间.(3)若还要考虑其他因素，如图形质量、数据之间的关联等，则还要求更多的存储空间。(4)还有空间位置枚举表示没有“部分”充满的概念。因此，许多实体只能近似表示。(5)在三维空间中，当体素分辨率为n时，表示一个形体就需要占用高达n3个单元。*7.4.2八叉树表示八叉树（octrees）又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体。八叉可以克服空间位置枚举占用的存储量太大的问题。对于三维实体采用八叉树进行表示，对于二维实体则采用四叉树进行表示树**四叉树F:FULL（完全被图形覆盖）E:EMPTY（完全没有被覆盖）B:Boundary（部分被覆盖）自适应八叉树划分（1）在空间中定义一个能够包含所表示物体的立方体。立方体的三条棱边分别与x,y,z轴平行，边长为2n。（2）若立方体内空间完全由所表示的物体占据，则物体可用这个立方体予以表示，否则，将立方体等分为八个小块，每块仍为一个小立方体，其边长为原立方体边长的1/2。*（3）将这八个小立方体依次编号为1,2,3,…8。如果子立方体单元已经一致，即为满（该立方体充满形体）或为空（没有形体在其中），则该子立方体可停止分解；（4）否则，需要对该立方体作进一步分解，再一分为八个子立方体。在八叉树中，非叶结点的每个结点都有八个分支。**八叉树***实体运算：一旦对一实体建立起八叉树表示，可将各种操作应用到该实体。比如对一个八叉树进行平移、旋转和缩放等几何变换，可以产生一个新的八叉树。对同一空间区域不同实体的两个八叉树表示，可进行并、交、差等集合运算，产生一个新的八叉树。八叉树算法的优点（1）数据结构简单划一，易于实现实体之间的集合运算，易于计算实体的几何特性。（2）由于具有层次结构，易于实现消隐。（3）这种方法不是一种精确的表示法，其近似程度完全取决于分割精度，与几何形体的复杂程度无关。*3.多边形网格定义：是三维计算机图形学中表示多面体形状的顶点与多边形的集合，它也叫作非结构网格。组成：网格通常由三角形、四边形或者其它的简单凸多边形组成，这样可以简化渲染过程。但是，网格也可以包括带有空洞的普通多边形组成的物体。*非结构网格内部表示：采用一组顶点的简单列表，它们带有表示那些顶点组成多边形的信息列表；另外可能带有表示空洞的附加信息。顶点列表+边界列表（一对索引信息）+连接边界的多边形列表三角形的处理要比普通多边形的处理更加简单，尤其是在计算几何中更是这样。对于优化的算法，可能需要快速访问边线或者相邻表面这样的拓扑信息，这样就需要如翼边表示这样更加复杂的结构。*********7.5产品数据交换标准*常用的面向产品数据模型及其文件格式的标准有DXF、IGES和STEP。*1、DXFDXF文件的总体结构由7个段和文件结尾组成，按顺序分别是：标题段、类段、表段、块段、实体段、对象段、预览段、文件结尾。DXF文件的最小组成单元是组（Group），一个DXF文件由若干组构成，每个组在文件中占两行，第一行称为组码（Groupcode），第二行称为组值（Groupvalue）。组码说明了组值的数据类型，组值是数据的具体值，这两行组合起来才是一个完整的数据。外部应用程序通过组码得到组值的数据类型，从而可以方便地读取组值。*2、IGES1.基本图形交换 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 （InitialGraphicsExchangeSpecification，IGES）1980年由美国国家标准局主持开发，1982年成为ANSI标准。2.IGES虽然不是ISO标准，且在1992年以后其版本不再发展，但作为事实上的工业标准，现有大多数CAD商用软件仍支持IGES图形文件格式。利用IGES文件，用户可以从中提取所需数据进行用户应用程序的开发。*IGES的文件格式分为ASCII格式与二进制格式。固定行长的格式中，每行为80个字符，由若干行组成一个文件。文件分成五段到六段，即开始段，全局参数段，目录段，参数数据段、结束段。*标志段：标志段可选，对于固定行长的ASCII文件可省。第一行的第73列如是B，则是二进制文件，如是C，则是压缩的ASCII文件。开始段：开始段提供人们阅读文件的序言。行数不限，但至少应占一行，每行的第73列有字母S。第74至80列为序号。*全局参数段：全局参数段所有记录的第73列均有字母G。74~80列为序号。本段含前置处理与后置处理的有关信息。例如参数分界符，记录分界符，发送系统标识符，文件名，前置处理文本，各种数据的表示方式，接受系统标识符等等以及作者、机构、版本等。*目录段：目录段为文件提供一个索引。每行的第73列为字母D，第74至80列为序号。文件的每个实体都在目录中占有一个条目。条目占两行。每89个字符组成一个域，共20个域。参考数数据段：参考数数据段列出实体的参数数据。每行的第73列有字母P。数据按自由格式排列，每行止于第64列。65列为空白。66列至72列有关于本实体在条目目录段中的第一行的序号，第74至80列仍为本段落持序号。*结束段：结束段标志文件的结束。它占一行，第73列为T。该行分为10个域。每域的首字符为段的代码，其后为本段的最末一行序号。1，2，3，4域为S，G，D，P。5~9域保留，第10域为结束段。结束段域中填T0000001。结束段所在行必须是文件的最后一行。*IGES是一种中性文件，其作用是在不同的CAD/CAM系统之间交换数据。将某种CAD系统的输出转换成IGES文件时需用前置处理程序处理；将IGES文件传送至另一种CAD系统也需要经后置程序处理。*不同系统间通过IGES交换数据*尽管IGES在工业界得到了广泛和成功的应用，但它在实践中存在着比较严重的问题，即不同系统之间采用IGES文件进行数据交换时图形发生失真现象。首先，IGES中定义的实体主要是几何图形方面的信息，而不是产品定义的全面信息。其次，IGES的另一个缺点是数据传输不可靠，一些语法结构有二义性，这可能导致数据交换的失败。此外，IGES文件所占的存储空间太大，虽然后来提出了压缩的ASCII码格式，但多数IGES处理器都不支持。*产品模型数据转换标准（StandardfortheExchangeofProductModelData，STEP），于1988年公布为ISO标准。STEP标准是一个关于产品信息表达与交换的国际标准，它提供了一种不依赖于具体软硬件系统的中性机制，目的是要建立一个包括产品整个生命周期的、完整的、语义一致的产品数据模型，从而满足产品生命周期内各个阶段对产品信息的不同需求，并保证对产品信息理解的一致性。2、STEP*STEP标准包括以下5方面的内容：标准的描述方法、资源模型的定义、应用 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 、实现形式以及一致性测试。*特点：1.STEP标准是一种思想、一门技术和一种方法学，它对产品信息建模、信息集成与交换带来了深远的影响。2.STEP标准满足了产品开发部门在实施协同设计、并行设计、虚拟产品集成开发等环境下的需求。3.其建立了统一的产品信息模型并进行数据交换，提供了一种数据共享的机制。5.STEP标准也为CAX和DBMS应用系统的开发，提供了接口标准化和概念模型标准化的支持。