《形体在计算机内的表示.ppt课件》由会员分享，可在线阅读，更多相关《形体在计算机内的表示.ppt课件（96页珍藏版）》请在金锄头文库上搜索。
1、3.5形体在计算机内的表示几何外型形体表示边境表示模型3.5.1 引言计算机中表示形体，通常用线框、外表和实体三种模型。几何外型历史：早期的线框表示 实体外型与曲面外型70 独立开展 到 相互溶合 NURBS 边境表示正那么形体对于任一形体，假设它是3维欧氏空间中非空、有界的封锁子集，且其边境是二维流形即该形体是连通的，我们称该形体为正那么形体，否那么称为非正那么形体。一些非正那么形体的实例集合运算并、交、差是构造形体的根本方法。正那么形体经过集合运算后，能够会产生悬边、悬面等低于三维的形体。Requicha在引入正那么形体概念的同时，还定义了正那么集合运算的概念。正那么集合运算保证集合运算的
2、结果仍是一个正那么形体，即丢弃悬边、悬面等。集合运算举列 为了可以处置非正那么形体，产生了非正那么外型技术。九十年代以来，基于约束的参数化、变量化外型和支持线框、曲面、实体一致表示的非正那么形体外型技术已成为几何外型技术的主流。3.5.2 形体表示模型 在实体模型的表示中，根本上可以分为分解表示、构造表示和边境表示三大类。1、分解表示将形体按某种规那么分解为小的更易于描画的部分，每一小部分又可分为更小的部分，这种分解过程直至每一小部分都可以直接描画为止。(a)将形体空间细分为小的立方体单元。这种表示方法的优点是简单，容易实现形体的交、并、差计算，但是占用的存储量太大，物体的边境面没有显式的解析
3、表达式，不便于运算。(b)八叉树法表示形体.首先对形体定义一个外接立方体，再把它分解成八个子立方体，并对立方体依次编号为0，1，2，7。假设子立方体单元曾经一致，即为满该立方体充溢形体或为空没有形体在其中，那么该子立方体可停顿分解；否那么，需求对该立方体作进一步分解，再一分为八个子立方体。在八叉树中，非叶结点的每个结点都有八个分支。 优点主要是：1形体表示的数据构造简单。 2简化了形体的集合运算。只需同时遍历参与集合运算的两形体相应的八叉树，无需进展复杂的求交运算。 3简化了隐藏线或面的消除，由于在八叉树表示中，形体上各元素已按空间位置排成了一定的顺序。 4分析算法适宜于并行处置。 八叉树表示
4、的缺陷：占用的存储多，只能近似表示形体，以及不易获取形体的边境信息等。 2构造表示。通常有扫描表示、构造实体几何表示和特征表示三种。(a)扫描表示。基于一个基体普通是一个封锁的平面轮廓沿某一途径运动而产生形体。扫描是生成三维形体的有效方法用扫描变换产生的形体能够出现维数不一致的问题。扫描方法不能直接获取形体的边境信息，表示形体的覆盖域非常有限。 (b)构造实体几何表示(CSG).经过对体素定义运算而得到新的形体的一种表示方法。体素可以是立方体、圆柱、圆锥等，也可以是半空间，其运算为变换或正那么集合运算并、交、差。CSG表示可以看成是一棵有序的二叉树。其终端节点或是体素、或是形体变换参数。非终端
5、结点或是正那么的集合运算，或是变换平移和/或旋转操作，这种运算或变换只对其紧接着的子结点子形体起作用。 CSG树是无二义性的，但不是独一的.CSG表示的优点： 数据构造比较简单，数据量比较小，内部数据的管理比较容易； CSG表示可方便地转换成边境Brep表示； CSG方法表示的形体的外形，比较容易修正。CSG表示的缺陷： 对形体的表示受体素的种类和对体素操作的种类的限制，也就是说，CSG方法表示形体的覆盖域有较大的局限性。 对形体的部分操作不易实现，例如，不能对根本体素的交线倒圆角；由于形体的边境几何元素点、边、面是隐含地表示在CSG中，故显示与绘制CSG表示的形体需求较长的时间。 (c)特征
6、表示从运用层来定义形体，因此可以较好的表达设计者的意图。从功能上可分为外形、精度、资料和技术特征。特征是面向运用、面向用户的。特征模型的表示依然要经过传统的几何外型系统来实现。不同的运用领域，具有不同的运用特征。在几何外型系统中，根据特征的参数我们并不能直接得到特征的几何元素信息，而在对特征及在特征之间进展操作时需求这些信息。特征方法表示形体的覆盖域受限于特征的种类。 构造表示的特点：构造表示通常具有不便于直接获取形体几何元素的信息、覆盖域有限等缺陷，但是，便于用户输入形体，在CAD/CAM系统中，通常作为辅助表示方法。3边境表示BR表示或BRep表示按照体面环边点的层次，详细记录了构成形体的
7、一切几何元素的几何信息及其相互衔接的拓扑关系。边境表示的一个重要特点是在该表示法中，描画形体的信息包括几何信息Geometry和拓扑信息Topology两个方面。拓扑信息描画形体上的顶点、边、面的衔接关系，拓扑信息构成物体边境表示的“骨架。形体的几何信息犹如附着在“骨架上的肌肉。 Brep表示的优点是：表示形体的点、边、面等几何元素是显式表示的，使得绘制Brep表示的形体的速度较快，而且比较容易确定几何元素间的衔接关系；容易支持对物体的各种部分操作，比如进展倒角。便于在数据构造上附加各种非几何信息，如精度、外表粗糙度等。Brep表示的缺陷是：数据构造复杂，需求大量的存储空间，维护内部数据构造的
8、程序比较复杂；Brep表示不一定对应一个有效形体，通常运用欧拉操作来保证Brep表示形体的有效性、正那么性等。Brep表示覆盖域大，原那么上能表示一切的形体，而且易于支持形体的特征表示等，Brep表示已成为当前CAD/CAM系统的主要表示方法。CSG 与边境表示成为两大主流方法 80 ACM Solid modeling 欧洲CSG会议 边境表示 一统天下 欧洲CSG会议 亚州GMP 3.5.3 形体的边境表示模型3.5.3.1 3.5.3.1 边境表示的根本实体边境表示的根本实体边境模型表达形体的根本拓扑实体包括：边境模型表达形体的根本拓扑实体包括：1. 1. 顶点顶点2. 2. 边。边有方
9、向，它由起始顶点和终止顶边。边有方向，它由起始顶点和终止顶点来界定。边的外形点来界定。边的外形CurveCurve由边的几由边的几何信息来表示，可以是直线或曲线，曲何信息来表示，可以是直线或曲线，曲线边可用一系列控制点或型值点来描画，线边可用一系列控制点或型值点来描画，也可用显式、隐式或参数方程来描画。也可用显式、隐式或参数方程来描画。3. 环。环Loop是有序、有向边Edge组成的封锁边境。环有方向、内外之分，外环边通常按逆时针方向排序，内环边通常按顺时针方向排序。4.面。面Face由一个外环和假设干个内环可以没有内环来表示，内环完全在外环之内。假设一个面的外法矢向外，称为正向面；反之，称为
10、反向面。面的外形可以是平面或曲面。平面可用平面方程来描画，曲面可用控制多边形或型值点来描画，也可用曲面方程隐式、显式或参数方式来描画。对于参数曲面，通常在其二维参数域上定义环，这样就可由一些二维的有向边来表示环，集合运算中对面的分割也可在二维参数域上进展。5.体。体Body是面的并集。3.5.3.2 边境表示的数据构造翼边数据构造：在1972年，由美国斯坦福大学Baumgart作为多面体的表示方式提出。它用指针记录了每一边的两个邻面即左外环和右外环、两个顶点、两侧各自相邻的两个邻边即左上边、左下边、右上边和右下边，用这一数据构造表示多面体模型是完备的，但它不能表示带有准确曲面边境的实体。 辐射
11、边：为了表示非正那么形体，1986年，Weiler提出了辐射边Radial Edge数据构造。辐射边构造的形体模型由几何信息和拓扑信息两部分组成。几何信息有面face、环loop、边edge和点vertex拓扑信息有模型model、区域region、外壳shell、面援用face use、环援用loop use、边援用edge use和点援用vertex use。点是三维空间的一个位置边可以是直线边或曲线边，边的端点可以重合。环是由首尾相接的一些边组成，而且最后一条边的终点与第一条边的起点重合；环也可以是一个孤立点。外壳是一些点、边、环、面的集合；外壳是一些点、边、环、面的集合。区域由一组外壳
12、组成。模型由区域组成。 清华大学开发的几何外型系统GEMS5.0中，采用的数据构造如图体组特征表示单体(零件)面组面线框环环边边顶点曲 面曲 线点实体几何数据实体拓扑数据参数域曲线欧拉操作 选读集合运算 选读3.5.3.3 欧拉操作对于恣意的简单多面体，其面(f)、边(e)、顶点(v)的数目满足 欧拉公式 v - e + f = 2对于恣意的正那么形体，引入形体的其它几个参数：形体一切面上的内孔总数(r)、穿透形体的孔洞数(h)和形体非连通部分总数(s)，那么形体满足公式： v - e + f = 2(s-h) + r 修正正程中保证各几何元素的数目坚持这个关系式不变，这一套操作就是欧拉操作。
13、最为常用的几种欧拉操作有：(1)mvsf(v,f)，生成含有一个点的面，并且构成一个新的体。(2)kvsf，删除一个体，该体仅含有一个点的面。(3)mev(v1,v2,e)，生成一个新的点v2，衔接该点到已有的点v1，构成一条新的边。(4)kev(e,v)，删除一条边e和该边的一个端点v。(5)mef(v1,v2,f1,f2,e)，衔接面f1上的两个点v1、v2，生成一条新的边e，并产生一个新的面。(6)kef(e)，删除一条边e和该边的一个邻面f。(7)kemr(e)，删除一条边e，生成该边某一邻面上的一新的内环。(8)mekr(v1,v2,e)，衔接两个点v1、v2，生成一条新的边e，并删
14、除掉v1和v2所在面上的一个内环。(9)kfmrh(f1,f2)，删除与面f1相接触的一个面f2，生成面f1上的一个内环，并构成体上的一个通孔。(10)mfkrh(f1,f2)，删除面f1上的一个内环，生成一个新的面f2，由此也删除了体上的一个通孔。为了方便对形体的修正，还定义了两个辅助的操作：公共端点。(11)semv(e1,v,e2)，将边e1分割成两段，生成一个新的点v和一条新的边e2。(12)jekv(e1,e2)，合并两条相邻的边e1、e2，删除它们的公共端点。以上十种欧拉操作和两个辅助操作，每两个一组，构成了六组互为可逆的操作。可以证明：欧拉操作是有效的，即用欧拉操作对形体操作的结
15、果在物理上是可实现的；欧拉操作是完备的，即任何形体都可用有限步骤的欧拉操作构造出来。3.5.3.4 集合运算正那么集与正那么集合运算算子规定正那么形体是三维欧氏空间中的正那么集合，因此可以将正那么几何形体描画如下： 设G是三维欧氏空间中的一个有界区域，且GbGiG，其中bG是G的n1维边境，iG是G的内部。G的补空间cG称为G的外部，此时正那么形体G需满足：1bG将iG和cG分为两个互不连通的子空间；2bG中的恣意一点可以使iG和bG连通；3bG中任一点存在切平面，其法矢指向cG子空间4bG是二维流形。设是集合运算算子交、并或差，R3中恣意两个正那么形体A、B作集合运算：R=AB 运算结果R仍
16、是R3中的正那么形体，那么称为正那么集合算子。 正那么并、正那么交、正那么差分别记为*，*、-*。分类Tilove对分类问题的定义为：设S为待分类元素组成的集合，G为一正那么集合，那么S相对于G的成员分类函数为： C(S,G)=S in G，S out G，S on G其中，S in G=SiG，S out G=ScG，S on G=SbG，集合运算算法包括以下几部分：(1)求交：参与运算的一个形体的各拓扑元素求交，求交的顺序采用低维元素向高维元素进展。用求交结果产生的新元素维数低于参与求交的元素对求交元素进展划分，构成一些子元素。(2)成环：由求交得到的交线将原形体的面进展分割，构成一些新的
17、面环。再加上原形体的悬边、悬点经求交后得到的各子拓扑元素，构成一拓扑元素生成集。(3)分类：对构成的拓扑元素生成集中的每一拓扑元素，取其上的一个代表点，根据点/体分类的原那么，决议该点相对于另一形体的位置关系，同时思索该点代表的拓扑元素的类型即其维数，来决议该拓扑元素相对于另一形体的分类关系。(4)取舍：根据拓扑元素的类型及其相对另一形体的分类关系，按照集合运算的运算符要求，决议拓扑元素是保管还是舍去；保管的拓扑元素构成一个保管集。(5)合并：对保管集中同类型可合并的拓扑元素进展合并，包括面环的合并和边的合并。(6)拼接：以拓扑元素的共享边境作为其衔接标志，按照从高维到低维的顺序，搜集分类后保
18、管的拓扑元素，构成结果形体的边境表示数据构造。3.6归类求交几何外型中，通常利用集合运算并、交、差运算实现复杂形体的构造。集合运算需求大量的求交运算。如何提高求交的适用性、稳定性、速度、精度等，对几何外型系统至关重要。历史上的观念变化:简单体素的准确求交， NURBS一致求交 - 归类求交3.6.1 求交分类简介多面体模型这种模型的求交计算主要是线段和平面的求交，求交问题的处理相对简单。多面体模型的缺陷是明显的。它只能近似表示形体，同时，复杂形体外表的离散会带来宏大的数据量。CSG模型在这种模型中，形体经过根本体素的组合来实现。二次曲面的求交是这些外型系统中必不可少的。当前的几何外型系统，大多
19、采用准确的边境表示模型。在这种表示法中，形体的边境元素和某类几何元素相对应，它们可以是直线、圆圆弧、二次曲线、Bezier曲线、B样条曲线等，也可以是平面、球面、二次曲面、Bezier曲面、B样条曲面等，求交情况非常复杂。二次曲面与各种自在曲面并存的混合表示模型的采用，导致了归类求交思想的产生。“无处不在的求交：GEMS实例！实体建模步骤分析：草图拉伸、填“体、面、环、点构造打孔，直径为20cm: 圆柱与立方体的一切面求交线，成环、重填“面子环点构造打第二个孔，直径为18cm: 圆柱与立方体的一切面、及第一个圆柱面求交线，成环、重填“面子环点构造3.6.2 归类求交战略几何外型系统中，用到的几
20、何元素：(25种)点：3D点。线：3D直线段、二次曲线(包括圆弧和整圆、椭圆弧和椭圆、抛物线段、双曲线段)、 Bezier曲线 (有理和非有理)、B样条曲线、NURBS曲线。面：平面、二次曲面(包括球面、圆柱面、圆锥/台面、双曲面、抛物面、椭球面和椭圆柱面)、Bezier曲面 (有理和非有理)、B样条曲面、NURBS曲面。将几何元素进展归类，利用同一类元素之间的共性来研讨求交算法。同时对每一类元素，在详细求交算法中要思索它们的特性，以提高算法的效率，发扬混合表示方法的优势。求交方法可分为：点点、点线、点面、线线、线面六种。清华大学的GEMS5.0系统采用点、直线、平面、二次曲线等简单的几何元素
21、之间的求交直线、平面、二次曲线等简单的几何元素与二次曲面之间的求交三维点与二次曲线/曲面之间的求交三维点与自在曲线、曲面之间的求交二次曲面与二次曲面之间的求交直线自在曲线/自在曲面的求交平面自在曲线/自在曲面的求交自在曲线自在曲线的求交自在曲线自在曲面的求交二次曲线自在曲线的求交 二次曲线自在曲面的求交自在曲面自在曲面的求交二次曲面自在曲线的求交二次曲面自在曲面的求交3.6.3 根本的求交算法曲线曲面求交的根本方法主要有:代数方法几何方法离散方法跟踪方法1代数方法利用代数运算，特别是求解代数方程的方法求出曲面的交线。根据参与求交的两曲面的表示方式的不同，可以把求交分为三种情况。隐式表示和参数表
22、示的曲面求交，经过把参数方程代入隐式方程的方法，可以将交线表示为g(u,v)=0的方式。此时得到的交线方程是平面代数曲线方程，可根据平面代数曲线实际的方法求解交线。两个曲面都是参数表示的情形，只需求将其中之一隐式化，然后用前面的方法求解。而参数多项式或有理多项式曲面的隐式化经过消元来实现。两个曲面都是隐式曲面。一种方法是将其中一个曲面参数化，然后用第一种情况来求解。但是，普通情况下这种参数化很困难，对于某些情况可以采用另外的方法计算参数化的曲面。代数法的弱点是对误差很敏感这是由于代数法经常需求判别某些量能否大于零、等于零或小于零，而在计算机中的浮点数近似表示的误差经常会使这种判别出现错误。代数
23、法实例：园与椭圆求交，化为求解4次方程，有公式解。园与圆环求交，化为求解8次方程，迭代求解。8次方程到达求解，不稳定。2几何方法利用几何的方法，对参与求交的曲面的外形大小、相互位置以及方向等进展计算和判别，识别出交线的外形和类型，从而可准确求出交线。几何求交顺应性不是很广，普通仅用于平面以及二次曲面等简单曲面的求交对于一些交线退化或相切的情形，交线往往是点、直线或圆锥曲线，用几何方法求交可以更加迅速和可靠。几何法实例：平面与圆柱求交1. 平面、圆柱参数的合法性检查2. 平面变换到圆柱的部分坐标系 3. 几何求交： 假设平面与圆柱平行，不交或交于两条直线 假设平面与圆柱垂直，不交或交于一个圆 否
24、那么，交于椭圆或椭圆弧 先求出平面与无限长圆柱交得的椭圆 (在圆柱的部分坐标系下) 根据椭圆在长轴上的两点与圆柱的 关系，确定交于点、椭圆、椭圆弧等3离散方法离散方法求交是利用分割的方法，将曲面不断离散成较小的曲面片，直到每一子曲面片均可用比较简单的面片，然后用这些简单面片求交得一系列交线段，衔接这些交线段即得到准确交线的近似结果。离散求交普通包括下面的过程：用包围盒作分别性检查排除无交区域；根据平坦性检查判别能否终止离散过程；衔接求出的交线段作为求交结果。由于Bezier曲面，B样条曲面具有离散性质，使得它们最适宜于离散法求交。缺陷：离散法求出的交线逼近精度不高。假设要求的精度较高，需求添加
25、离散层数。这将大大添加了数据储存量和计算量。处于不同离散层数的相邻子曲面片，由它们产生的交线段能够会出现裂痕。高度估计问题 H4跟踪方法经过先求出初始交点，然后从知的初始交点出发，相继跟踪计算出下一交点，从而求出整条交线的方法。跟踪法的本质是构造交线满足的微分方程组，先求出满足方程组的某个某个初值解，经过数值求解微分方程组的方法来计算整个交线。跟踪方法在计算相继交点的时候，利用了曲面的部分微分性质，普通采用数值迭代的方法求解，使得计算效率较高。跟踪法求交中思索的主要问题包括：如何求出初始交点并保证每一交线分支都有初始交点被求出；如何计算奇特情况下的跟踪方向以及合理选取跟踪的前提高长；如何处置相
26、切的情况。跟踪法实例：MAF方法曲线曲线求交近似交点，切线求交，投影MAF与Newton法的比较Newton法MAF与Newton法的比较MAF法 假设 为初始交点， 为两切线的交点；由于在曲线 在 的切线上，有 于是 由此得到新交点 ，如此反复迭代。3.7 实体外型系统简介在早期开发的实体外型系统中，值得提及的是剑桥大学的BUILD-1系统。该研讨小组的一部分人组建了Shape Data公司，并开发出实体外型系统Romulus，Romulus孕育了最著名的两个实体外型系统开发环境：Parasolid和ACIS。3.7.1 Parasolid系统：Solidworks3.7.2 ACIS系统:
27、Autodesk,Solidedge 3.7.1.1 Parasolid的主要功能Parasolid有较强的外型功能，但是只能支持正那么实体外型。主要功能包括：1Parasolid采用自在曲面和解析曲面的混合表示，共提供了10种规范的曲面类型和7种规范的曲线类型，并且是完选集成的。2Parasolid可用简单的方法生成复杂的实体，实体之间可有多种方式的操作。3.用户可用本人了解的工程特征进展设计4.可以提供非拓扑和非几何数据，称为属性 属性包括系统定义的属性和用户定义的属性两种，且依靠于模型实体Entities。5.支持部分操作。包括：改动面几何、变换面几何、使面成锥形、摆动面、扫描面及删除面
28、。提供了多半径、变半径的过渡功能。3.7.1.2 Parasolid的模型构造模型实体包括三种： 拓扑、几何和相关数据1拓扑实体1体Body：Parasolid模型通常包括一个或多个体Bodies2壳Shell：壳是实体Solid和空气之间封锁的边境3面Face、边Edge和顶点Vetex4翼Fin：翼Fins表示一条边的一侧每一条边有一个左翼和一个右翼5环Loop：由一个面上封锁的翼组成。7装配件Assembly和实例Instance：一个装配件是一个对其它装配件或体的指针的集合。每一个指针被称为一个实例。8世界World：世界是一个独特的实体Entity，它包含模型中的一切的体Bodies
29、和装配件Assemblies。2几何实体Entities点。主要依靠于顶点，它们也依靠于体和装配件作为构造几何。曲线。主要依靠于面，但也依靠于体和装配件作为构造几何。曲面。主要依靠于模型的边或翼，但也依靠于体和装配件作为构造几何。变换。变换表示几何操作：平移、修剪等，主要依靠于实例。3相关的数据实体1特征feature：是实体的集合，依靠于体和装配件。2表List：提供了构造化数据的方法，它们普通独立运用，也可依靠于体和装配件。表有三种：整数表Integer、实数表Real和标志表Tag。3属性Attribute：是用于附着信息到实体的数据构造。3.7.1.3 Parasolid的界面Para
30、solid有两个界面。一个在外型器顶部，称为中心界面KI，经过KI，用户可以外型、操作对象和控制外型器。另一个在外型器下部，它包括三个部分：Frustrum、GOGraphics Output和FGForeign Geometry。Frustrum：Frustrum是用户写的函数集，当数据被存储、提取，或进展内存分配时，它们被中心调用。图形输出GO：图形输出GO函数也是被用户写的。从这些函数输出的通是要求中心Kernel绘图的指令。外部几何FG：Parasolid经过FG模块界面访问用户定义的曲线、曲面，使得用户可以运用Parasolid外型出的曲线、曲面及规范的Parasolid曲线、曲面类
31、型。3.7.2 ACIS系统ACIS是由美国Spatial Technology于1990年初次推出。ACIS的重要特点是支持线框、曲面、实体一致表示的非正那么形体外型技术，可以处置非流形形体。ACIS产品采用了组件技术，其中心是几何外型器Geometric Modeler，还包括一些可与中心集成的组件，称为外壳Husk。3.7.2.1 ACIS的构造中心只提供一些根本的几何外型功能，其它高级功能在外壳中提供。外壳可以是Spatial Technology公司提供的，如高级渲染Advanced Rendering外壳、三维工具箱3D Toolkit外壳等，也可以是用户开发的。3.7.2.2 A
32、CIS的模型表示ACIS模型表示由各种属性Attributes、几何Geometries和拓扑Topologies成。几何是指模型的物理描画，如点、曲线、曲面、直线、椭圆等；拓扑是指各种几何实体在空间的关联，如体、壳、面、环、边和顶点等；属性依靠于模型实体。ACIS是用C+开发的，C+类的层次如下图。3.7.2.3 ACIS的几何总线ACIS中心提供了一个几何总线，以衔接其它的外壳与运用程序3.7.2.3 ACIS的界面1API函数APIApplication Procedural Interface函数是一个函数集，运用程序经过调用这些函数可以操作模型。2属性ACIS属性Attributes机制向开发者提供了详细的运用程序数据到ACIS几何或拓扑实体ENTITY的方法。属性与模型数据一同存储或恢复。3类类Classes界面是定义ACIS几何和拓扑模型及其它ACIS特征的C+类的集合，开发者可以直接利用这些类和方法，为特定的用途导出新的类和方法。4. 宏预处置器宏Macros用于简化通常的编码义务。 谢谢！
