第8章几何造型

几何造型,2020年6月9日11时52分,1,概述,几何造型:利用点、线、面、体等几何元素，经过平移、旋转、比例等几何变换和交、叉、并等集合运算，产生实际或想象的物体模型；应用：飞机外形设计，机械零件的计算机辅助设计与制造，刀具、机器人运动的模拟等等。三维几何造型的两个主要分支：曲面造型：研究在计算机内如何描述一张曲面,如何对它的形状进行交互式的显示与控制；实体造型：研究如何在计算机内定义、表示一个三维物体。,曲线和曲面,2020年6月9日星期二,2,造型技术的发展6070年代初：早期的实体造型技术，共同的特点是不支持精确的曲面表示，用多面体表示形体70年代：雕塑曲面技术的发展，出现了Coons曲面、Bezier曲线和曲面、B样条曲线和曲面等设计方法，在汽车、航空和造船等行业得到了广泛的应用。80年代末：出现了NURBS曲线曲面设计方法，已有的曲线曲面表示方法，如Bezier方法、B样条方法等，可以用NURBS方法统一表示，且能精确表示二次曲线曲面。由于NURBS的强大的表示能力，能够精确表示形体的几何造型系统，纷纷采用了NURBS方法，国际标准化组织也已将NURBS作为定义工业产品形状的唯一数学方法。,曲线和曲面,2020年6月9日星期二,3,正则形体早期的几何造型系统只支持正则的形体造型对于任一形体，如果它是3维欧氏空间R3中非空、有界的封闭子集，且其表面任意一点的足够小的邻域在拓扑上应该是一个等价的封闭圆，我们称该形体为正则形体，否则称为非正则形体。,曲线和曲面,2020年6月9日星期二,4,非正则实体,基于正则形体表示的实体造型形体只能表示正则的三维“体”，低于三维的形体是不能存在的。这样，线框模型中的“线”，表面模型中的“面”，都是实体造型系统中所不能表示的。实际应用中，有时候人们希望在系统中也能处理象形体中心轴、剖切平面这样低于三维的形体，这就要求造型系统的数据结构能统一表示线框、表面、实体模型。,曲线和曲面,2020年6月9日星期二,5,形体的集合运算（并、交、差）是构造形体的基本方法正则造型和非正则造型（非正则造型是主流）,曲线和曲面,2020年6月9日星期二,6,坐标系,造型坐标系（局部坐标系）用户坐标系直角坐标系（左手系，右手系）仿射坐标系圆柱坐标系球坐标系极坐标系观察坐标系规格化的设备坐标系设备坐标系,曲线和曲面,2020年6月9日星期二,7,球坐标系,直角坐标系,几何元素,点（Vertex）控制点，型值点，插值点点通过它在空间中的位置来表示。一维空间的点用一元组（t）表示；二维空间中的的点用二元组（x,y）表示；三维空间中的点用三元组（x,y,z）表示。n维空间中的点在齐次坐标下用（n+1）元组（x1，x2，xn，w）表示。点是几何造型中的最基本的元素，许多其它形体都可以用有序的点集表示。在正则形体定义中，不允许孤立的点存在。,曲线和曲面,2020年6月9日星期二,8,边（Edge）面的边界或者几个面（包括平面和曲面）的交正则形体：一条边只能是两个面的交集非正则形体：既可以是多个面的交集，也可以是一张孤立的平面或曲面的边界边可以是直线或曲线，它的形状由边的几何信息来表示边有方向，它由起点和终点来界定在正则形体定义中，不允许孤立的边存在,曲线和曲面,2020年6月9日星期二,9,环（Loop）由一系列首尾相连的有向边组成的封闭边界环中的边不能相交，并且相邻的两条边共享一个端点环有方向、内外之分。外环边通常按逆时针方向排序，内环边通常按顺时针方向排序，这样，使得环的“内部”始终位于环的左侧环主要用于定义面，包括带一个或多个孔的面,曲线和曲面,2020年6月9日星期二,10,面（Face）由一个外环和n（n0）个内环来表示内环完全在外环之内每个环既不能自相交，也不能与其它环相交根据环的定义，在面上沿环的方向前进，左侧总在面内，右侧总在面外面有方向性，一般用其外法矢方向作为该面的正向面的形状由它的几何信息来表示，可以是平面或曲面在正则形体定义中，也不允许孤立的面存在。,曲线和曲面,2020年6月9日星期二,11,体（Body）是用面的并集来表示的用于定义体的面形成一个封闭的边界在正则几何造型系统中，要求体必须是正则的。体素（voxel）来源：从实际形体中选择、参数轮廓线扫描产生、代数半空间定义,曲线和曲面,2020年6月9日星期二,12,表示形体的两种模型,曲线和曲面,2020年6月9日星期二,13,表示形体的数据模型,线框模型用顶点和棱边来表示形体,曲线和曲面,2020年6月9日星期二,14,V8,长方体的线框模型,线框模型缺点数据结构包含的信息有限，无法实现图形的自动消隐；同一数据结构可能对应多个物体，产生二义性；无法表达连续的几何信息，不能明确的定义点和几何物体之间的关系；在生成复杂物体的图形时，采用线框式的数据结构要求输入大量的初等数据，这不仅加重了用户的负担，而且很难保证数据的有效性和统一性。,曲线和曲面,2020年6月9日星期二,15,表面模型用有向棱边围成的部分来定义物体表面，由面的集合来定义物体。表面模型是在线框模型的基础上，增加了有关生成三维物体各表面的数据信息，这些信息包括定义表面的环、表面特征、棱边连接方向等内容；可以满足面和面的求交、线面消隐、明暗色彩图、数控加工等应用问题的需要；缺点：没有说明形体究竟在面的哪一侧。,曲线和曲面,2020年6月9日星期二,16,实体模型明确定义了表面的哪一侧存在实体；在表面模型的基础上可用三种方法来定义：（a）在定义表面的同时，给出实体存在侧的一点P；（b）直接用表面的外法矢来指明实体存在的一侧；（c）是用有向棱边的方向表示表面的外法矢方向，右手法则确定外法矢量，图（d）所示。,曲线和曲面,2020年6月9日星期二,17,实体表示模型,常用的形体表示方式,前面三种表示模型是一种广义的概念，不反映实体在计算机内部，或对最终用户而言所用的具体表示方式。针对不同的表示方式，几何造型系统采用的数据结构也有所不同，常用的有：构造实体几何表示：以一组简单的物体通过正则集合运算来构造新的物体，这些简单的物体称为基本体素，可以是立方体、长方体、圆柱体、圆锥体等。边界表示：通过描述构成实体边界的点、边、面而达到表示实体的目的，实体与其边界一一对应。空间分割表示：将基本体素通过“粘合”构造新的物体。单元分解表示、八叉树表示等属于这种表示方法，特征表示法也可看作这种表示方法的特例。,曲线和曲面,2020年6月9日星期二,18,构造实体几何表示,构造实体几何（ConstructionSolidGeometry）表示，或称CSG树表示是一种应用广泛的物体表示与构造方法，它的基本思想是将一些简单的基本体素通过正则集合运算来构造、表示新的物体。,曲线和曲面,2020年6月9日星期二,19,物体的CSG树表示,曲线和曲面,2020年6月9日星期二,20,常用体素,曲线和曲面,2020年6月9日星期二,21,CSG树,CSG树表示的优点：数据结构简单，数据量小，内部数据管理容易；每个CSG树都能表达有效的形体，无二义性；可方便的转换成BRep表示，从而支持更广泛的应用；容易编辑。CSG树表示的缺点：产生、修改形体的操作种类有限，集合运算对形体的局部操作不易实现；绘制困难。,曲线和曲面,2020年6月9日星期二,22,边界表示法,边界表示法(BoundaryRepresentation，BRep):边界就是物体内部点与外部点的分界面。,曲线和曲面,2020年6月9日星期二,23,边界表示法,边界表示法与传统的工程绘图有密切的联系。输入两个点，即可以通过两个给定点连接一条线。若干条首尾相接的线段(即棱边，在计算机图形学中它们被定义成物体的相邻表面的交线)可形成一个闭合环，一个或多个环给出一个面的边界。最后，若干个表面闭合后围成一个“体”。边界表示法的一个很重要的特点是在该表示法中，描述物体的信息包括几何信息与拓扑信息两个方面。,曲线和曲面,2020年6月9日星期二,24,拓扑信息物体的拓扑信息是指物体上所有的顶点、棱边、表面间是怎样连接的。几何信息物体的几何信息指的是顶点、边、面的位置、大小、形状等几何数据。,曲线和曲面,2020年6月9日星期二,25,拓扑信息与几何信息分开表示有下述优点：,便于具体查询物体中各元素，获取它们的相关信息。容易支持对物体的各种局部操作。对于具有相同拓扑结构而只是大小、尺寸不同的一类物体可以用统一的数据结构加以表示。便于在数据结构上附加各种非几何信息。,曲线和曲面,2020年6月9日星期二,26,Brep表示的优点：表示形体的点、边、面等几何元素是显式表示的，使得绘制形体的速度较快，而且比较容易确定几何元素间的连接关系；容易支持对物体的各种局部操作；便于在数据结构上附加各种非几何信息，如精度、表面粗糙度等。Brep表示的缺点：数据结构复杂，需要大量的存储空间，维护内部数据结构的程序比较复杂；不一定对应一个有效形体，通常运用欧拉操作来保证Brep表示形体的有效性、正则性等。,曲线和曲面,2020年6月9日星期二,27,欧拉运算,欧拉运算是三维物体边界表示数据结构的生成操作，它的每一种运算所构建的拓扑元素和拓扑关系均要求满足欧拉公式：以保证所建边界表示的有效性。式中v、e、f分别表示物体上的顶点、棱边和表面的数目，而r、s、h分别表示物体表面的内环数，不相连接的物体个数以及物体的通孔数目。,曲线和曲面,2020年6月9日星期二,28,简单多面体欧拉公式：v-e+f=2,满足欧拉公式的欧拉运算多种多样，下表列出了五个具有鲜明几何意义的基本欧拉操作,曲线和曲面,2020年6月9日星期二,29,BRep的半边数据结构：在构成多面体的三要素(顶点、边、面)中，半边数据结构以边为核心。为了方便表达拓扑关系，它将一条边表示成拓扑意义上方向相反的两条“半边”，所以称为半边数据结构。半边数据结构在拓扑上分为五个层次，即体-面-环-半边-顶点。,曲线和曲面,2020年6月9日星期二,30,曲线和曲面,2020年6月9日星期二,31,半边数据结构的层次结构,右环,半边数据结构,基于空间分割的八叉树表示,一种层次数据结构表达方法：首先在空间中定义一个能够包含所表示物体的立方体，立方体的三条棱边分别与x,y,z轴平行，边长为2n；,曲线和曲面,2020年6月9日星期二,32,若立方体内空间完全由所表示的物体占据，则物体可用这个立方体予以表示，否则将立方体等分为八个小块，每块仍为一个小立方体，其边长为原立方体边长的1/2，并依次编号为0,1,2,7；,若某一小立方体的体内空间全部被所表示物体占据，则将此立方体标识为“FULL”;若它与所表示物体无交，则该立方体被标志为“EMPTY”;否则将它标识为“PARTIAL”，并继续分割下去；依此方式，物体在计算机内可表示为一棵八叉树。凡是标识为“FULL”或“EMPTY”的立方体均为终端节点，而标识为“PARTIAL”的立方体为非终端节点；当分割生成的每一小立方体的边长为单位长时，分割即告终止。此时，应将每一标识为“PARTIAL”的小立方体重新标识为“FULL”或“EMPTY”。,曲线和曲面,2020年6月9日星期二,33,二维形体的四叉树表示,曲线和曲面,2020年6月9日星期二,34,三维物体的八叉树表示,曲线和曲面,2020年6月9日星期二,35,八叉树表示的优点：容易实现物体之间的正则集合运算。由于物体的八叉树表示就是由它内部含有的大大小小的立方体（称体元）组成，因此对物体执行并、交、叉运算时，只需同时遍历参加集合运算的两物体相应的八叉树，就可以获得拼合的八叉树，而无需进行复杂的求交运算；容易实现隐藏线和隐藏面的消除。消除隐藏线和隐藏面的关键是对物体（及其不同部分）按其距视点的远近排序，而在八叉树表示中，各结点之间的序的关系是简单且固定的，使得计算比较容易；,曲线和曲面,2020年6月9日星期二,36,易计算物体的整体性质，如体积、质量等。在计算物体的体积或质量时，只需从物体的八叉树的根节点开始，逐层计算所表示物体的最大和最小体积（质量）。当标识为“PARTIAL”的体元以“FULL”计时得最大体积（质量），若不计入时得最小体积（质量）。由于树的每一层都是在一定精度下对所表示物体的一种近似，因此若所得的最大最小体积（质量）之差小于给定的允差，计算即结束。,曲线和曲面,2020年6月9日星期二,37,八叉树表示的缺点：不能精确地表示一个物体，并且对八叉树表示的物体做任意的几何变换也比较困难；它占用的存储空间很多，这是因为每一体元都是立方体，且体元各表面分别与三个坐标平面平行。只有当所表示的物体具有相似的形状和位置时，才会获得简洁的八叉树表示。在每一个八叉树结点中，除去一个描述该结点性质（FULL或EMPTY等）的域外，还存储它指向父结点及八个子结点地址的指针，从而使物体的八叉树表示在空间花费上十分昂贵。实际上，八叉树表示是以存储空间换取了算法的效率。,曲线和曲面,2020年6月9日星期二,38,构造形体的Sweep运算,一个在空间移动的几何集合，可扫描出一个实体。它是以沿着某种轨迹移动点、曲线或曲面为基础的，这一过程所产生的轨迹定义为一维、二维或三维物体。Sweep运算要求定义要移动的物体和移动的轨迹，物体可以是曲线、曲面或实体，轨迹则是可分析的、可定义的轨迹。Sweep