dota2一直在安装:三维几何模型在计算机内的表示
来源:百度文库 编辑:偶看新闻 时间:2024/04/28 05:31:13
造型技术的发展
CAD/CAM的核心技术是几何造型技术[5–9]── 一项研究在计算机中如何表示物体模型形状的技术。在CAD/CAM技术四十多年的发展历程中,经历了四次重大的变革。60年代初期的CAD系统只能处理简单的线框模型,提供二维的绘图环境,用途比较单一。进入70年代,根据汽车造型中的设计需求,法国人提出了贝塞尔算法,随之产生了三维曲面造型系统CATIA。它的出现,标志着CAD技术从单纯模仿工程图纸的三视图模式中解放出来,首次实现以计算机完整描述产品零件的主要信息。这是CAD发展历史中的第一次重大飞跃。1979年,SDRC公司发布了世界上第一个完全基于实体造型技术的大型CAD/CAE软件──IDEAS。由于实体造型技术能够精确表达零件的全部属性,在理论上有助于统一CAD、CAE、CAM的模型表达,给设计带来了惊人的方便性。可以说,实体造型技术的普及应用标志着CAD发展史上的第二次技术革命。但是,在当时的硬件条件下,实体造型的计算及显示速度太慢,限制了它在整个行业的推广。90年代初期,参数化技术逐渐成熟,标志着CAD技术的第三次革命。参数化技术的成功应用,使得它在1990年前后几乎成为CAD业界的标准。随后,SDRC攻克了欠约束情况下全参数的方程组求解问题,形成了一套独特的变量化造型理论。SDRC将变量化技术成功的应用到CAD系统中,标志着CAD技术的第四次革命。随着CAD技术和几何造型技术的发展, 近年来, 市场上出现了一大批优秀的几何造型软件及工具。例如,PTC公司的产品Pro/E、SDRC的产品I-DEAS Master Series、UGS公司的产品Unigraphics、IBM公司的产品CATIA/CADAM、Autodesk公司的产品MDT、Spatial Tech公司的ACIS、EDS公司的Parasolid等。在国内,清华大学、北京航空航天大学、华中理工大学、浙江大学、上海交通大学、西北工业大学,以及其他一些单位也发表了一些关于特征造型技术研究的论著,并开发了一些特征造型系统,例如:清华大学开发的TiGems造型系统,北京航空航天大学研制出的微机版“金银花(LONICERA)”系统,武汉开目信息技术有限责任公司开发的开目三维CAD软件等等。 造型系统简介Parasolid和ACIS是两个最有代表性的几何造型系统的开发平台。在早期开发的实体造型系统中,英国的剑桥大学研制出了BUILD-1和BUILD-2系统,但都没有公开使用。80年代初期,研究小组的一部分人组建了Shape Data公司,并开发了实体造型系统Romulus。1986年,Shape Data并入EDS Unigraphics之后,推出了功能强大的几何造型核心Parasolid。同时,Shape Data一部分保留人员研制了新的造型核心,就是后来由Spatial Technology公司推出的几何造型系统核心ACIS。Parasolid和ACIS并不是面向最终用户的应用系统,而是“几何引擎”,作为应用系统的核心。用户可用它们作为平台,开发自己的应用系统。当今许多流行的商用CAD/CAM软件,如Unigraphics、Solidedge、Solidwork、MDT等,都是在Parasolid或ACIS的基础上开发出来的。 Parasolid有较强的造型功能,但是只能支持正则实体造型。它提供的主要功能有:集合运算、特征的创建和编辑、局部操作、数据交换文件接口等。Parasolid采用精确的边界表示,包括拓扑、几何和关联三种数据类型。ACIS具有和Parasolid相似的形体结构,但在系统结构上采用了核心和外壳相结合的方式。ACIS支持线框、表面和实体的统一表示,支持非正则形体的造型。在上述几何实体造型系统中,通常都会提供一些基本的形体输入方法,以及拉伸,旋转,蒙皮,扫描等直接构造形体的方法,通过集合运算对形体进行拼合。虽然对这些造型方法的研究取得了一系列新进展,但是集合运算仍基本局限在对两个体进行正则运算(交,并,差)上,而且结果形体的信息都已经包含在两个参加运算的原始形体之中,不能引入新的信息。实际应用中,有些机械零件具有特定的形状特征,不能通过集合运算来直接完成,或者直接实现时操作步骤非常复杂。但是,它们的生成方法和集合运算非常相似,可以看作是集合运算的扩展。拔模和抽壳都属于这一类型的造型方法。三维形体的表示
三维造型技术是建立恰当的模型来表示自然界中形态丰富的三维物体的技术,根据造型对象将造型技术分成3类。
第一类是曲面造型,主要研究计算机内如何描述一张曲面,及曲面的显示与控制。曲面造型又分成规则曲面和不规则曲面两种。不规则曲面造型方法主要有贝塞尔曲线曲面、B样条曲线曲面和孔斯曲面等。(二维曲线:Nurbs(通过拟合点)、三次B样条(通过控制点)、贝塞尔(控制点和拟合点重合)和波浪线(B样条)))
第二类是立体造型方法,主要研究在计算机内如何定义、表示一个三维物体,主要有体素构造法、边界表示法和八叉数法等等。曲面造型和立体造型合称几何模型造型。该技术主要应用在机械行业辅助设计制造领域(CAD)。
第三类是自然景物模拟,主要研究在计算机内如何模拟自然景物,如云、流水、树等。该造型技术主要应用在游戏和艺术造型等领域。
如下主要说说几何模型的表示。
在计算机中,表示几何形体的方法通常有三种:线框模型、表面模型和实体模型
一、线框模型
该模型采用三维形体的全部顶点及边的集合来描述三维形体,即用顶点表和边表
两个表的数据结构来表示三维模型。每条边由两个顶点表示。
主要优点是结构简单,处理容易。描述二维目标十分理想。但对三维物体,存在如下缺点:
1)没有面的信息,它不能表示表面含有曲面的物体。
2)不能明确定义点与物体之间的关系。
3)点和边信息容易出现二义性。
二、表面模型
在线框模型的基础上,增加了物体中的面的信息,用面的集合来表示物体,每个面由多条有向边构成,用环来定义面的边界,即是用顶点表、边表和面表来描述模型。 表面模型又分为平面模型和曲面模型。前者以多边形网格为基础。后者以参数曲面块为基础。
表面模型存在的不足就是它只能表示物体的表面边界,而不能表达出真实实体的属性,很难确认一个表面模型表示的三维图形是一个实体还是一个空壳。这个不足,在实体模型中得到了解决。
三、实体模型
实体模型是最高级的模型,它能完整表示物体的所有形体信息,可以无歧义地确定一个点是在物体外部还是内部或表面上。
实体模型使用有向边的右手法则来确定所在面的外法线方向。即用右手沿边的顺序方向握住,大拇指所指向为该面的外法线方向。法线方向指向体外。
体外
实体模型存在着不同的数据结构,在这些结构中存在一个共同点,即数据结构不仅记录了物体全部的几何信息,而且还记录了所有的点、线、面、体的拓扑信息(即空间位置关系)。实体模型的构造通常使用体素(即原始的基本实体),经集合论中的交、并、差运算构成复杂形体。
1. 实体的定义
实体就是有效的物体,即客观世界中确实存在的物体,要在计算机内表示、构造一个实体,就必须给出实体的确切定义(即用最小的数据结构唯一地确定实体的形状和位置。)如下图带有悬挂面的立方体就不是实体,在客观世界中不可能存在这样的物体。
作为实体应满足如下条件:
1.刚性。一个实体必须具有一定的形状(流体不属于实体)
2.维数一致性。一个实体的各个部分必须是三维的,不能存在悬挂的、孤立的边界。
3.有限性。一个实体必须占有有限的空间。
4.边界确定性。根据实体的边界,可确定实体的内部或外部。
5.封闭性。经过集合运算后,仍然是有效的实体。
实体的表面必须具备如下性质:
1. 连通性。表面任意两点都可用表面上的一条路径连接起来。
2. 边界性。
3. 非自相交性。一个实体表面不可自相交。
4. 可定向性。一个实体的表面两则可明确定义出实体的内侧和外侧。
5. 封闭性。一个表面的封闭性由多边形网格各元素的拓扑关系确定的。即每条边连接且仅连接两个面,每条边有且仅有两个端点。
从点集拓扑角度给出实体的定义。将三维实体看作是空间中点的集合,它由内点与边界点共同组成。
内点是指点集中的这样一些点:它们具有完全包含于该点集的充分小的领域。点集中除内点外的所有的点就是边界点。
所以三维物体A可表示为:
A = {bA,iA}
bA为物体A的边界点集;iA为物体A的内部点集。
定义点集的正则运算r如下:
rA = ciA
i为取A的内点运算;
c为取闭包运算;
A为一个点集。
iA为A的全体内点组成的集合,称为A的内部,它是一个开集(“开集”可以理解为没有边界值去判断点是否为内点)。
ciA为A的内部的闭包,是iA与其边界点的并集。(据此可以理解“闭包”的含义),它本身是一个闭集,(“闭集”可以理解为可以通过明确的边界值来判断点是否在集合中)。
正则运算即为:先对物体取内点再取闭包的运算。rA称为物体A的正则点集。如图:
带有悬边的二维点集A
内点集合 iA
(没有粗边界)
正则点集ciA
(有粗边界)
以上图中,图1有悬边所以点集不是有效实体,图2没有边界,不是满足“封闭性”所以也不是实体。图3为正则点集,封闭性,也满足实体的其他条件,所以为实体。
正则点集有时也不一定是实体。如下图:
左图为正则点集,但它不是有效的物体。由此,就会涉及到另外一个概念“二维流体”。
二维流体是指对于实体表面上的任何一点,都可以找到一个围绕着它的任意小的领域,该领域在拓扑(即是空间位置)上与平面上的一个圆盘是等价的(也就是在表面上存在着一个领域围绕着某个点)。这意味着,在领域的点集和圆盘之间存在着连续的一对一的对应关系。如上右图,立体表面上任一点都存在与圆盘同构的领域。而左图,两个立方体共享边被四个面共享,其上的点不存在这样的唯一的领域(在上图中,共享边的点,存在围绕它的领域有两个)。
有了上述概念后,实体可以这样描述为:
对于一个占据有限空间的正则点集,如果其表面是二维流形,则该正则点集为实体(有效物体)。
2. 正则集合运算
.已知一个体,查找它的所有面、所有边或所有顶点;
.已知一个面或一个边,查找它所属于的体;
.已知一个面,顺序查找围成它所有边;
.已知一个边,查找交于该边的所有面,或着查找该边的邻边,或者查找该边的两个端点;
.已知一个顶点,查找交于该顶点的所有边或所有面.以上这些基本操作的效率直接影响着整个实体造型系统的效率。一个B-rep数据结构应当方便、迅速地实现几何元素的这些查询或增删操作.为了查询或操作方便,必须建立各几何元素间的拓扑关系,且引入其它辅助元素,例如在许多B-rep数据结构中具有环结点,用来表示面的内、外封闭边界.在B-rep的数据结构设计时,除了需要考虑时间的因素外,还要考虑空间的因素,即模型所占计算机内存的大小,但往往这两方面是互相矛盾的.要想各个几何元素之间查询迅速,必然要在它们之间建立广泛的联系,这样必然增加存储空间的占用量.反过来也是如此,而半边数据结构就很好的权衡了空间和时间的问题。在构成多面体的三要素(点、边、面)中,半边数据结构仍以边为核心,但为了方便表达拓扑关系,它将一条边表示成拓扑意义上方向相反的两条“半边”,所以称为半边数据结构,其结构入图: 半边数据结构共包含六个结点:体、面、环、边、半边和顶点.半边是一连接两个顶点并具有一固定方向的线段.一系列首尾相连的半边形成一个环.半边的关系是一个边包含两个相反方向的半边,由这两个半边可以查询交于这个边的两个面。半边的含义如上图所示.半边数据结构的优点是几何元素之间的互相查询非常方便,不足之处是由于结点多占用空间较大。半边数据结构的六个结点在C语言中被表达成“结构”.结点之间通过结构指针互相联系.这些结点描述如下: 顶点结点:顶点结点是半边数据结构中最底层的结点,实体的几何位置和尺寸最终都由顶点结点来定义.所以,顶点结点必须包含顶点的空间三维坐标值
半边结点:半边结点包含指向前趋半边和后继半边的两个指针.这两个指针形成了一个环内半边的双向链表.半边结点还包含半边所属于的环的指针,以及半边起始顶点的指针.
. 边结点:边结点包含左右两个半边的指针,通过这两个指针可以查找该边的两个端点以及交于该边的两个面.指向前趋边和后继边的两个指针实现一个实体内边的双向链表.
环结点:因为一个环包含一系列的首尾相接的半边,故环结点是一个指向这些半边其中之一的指针,通过该指针可以查找构成该环的所有半边.环结点还包含指向前趋和后继环的两个指针,用以实现一个面内环的双向链表.另外,环结点还包含指向环所在面的指针.
面结点:因为面是由若干个环围成的内部连通的平面多边形,所以,面结点包含一个环的首指针,用来查找围成它的所有环.因为外环只有一个,为了区分内环和外环,面结点中包含指向它的外环的指针.面的前趋指针和后继指针形成一个实体内面的双向链表.面结点中还包含指向它所属于的体的指针,用来查询面所属于的实体.面所在平面的方程也是定义完整实体的重要内容,所以,面结点中包含一个四个浮点数的数组,表示其平面方程.
体结点:在半边数据结构中,体结点是各种引用的根结点.从体结点出发,可以搜索任何其它的结点.所以,体结点,包含面、边和顶点的首指针.体结点之间也是通过前趋指针和后继指针形成的双向链表来连接。从图中可以看出,许多几何元素可以有不同的搜索路径,例如查找实体上的顶点可以有两个路径:一是体→面→环→半边→顶点;二是体→顶点.第二个路径比第一个路径要简捷得多,用来进行实体的平移等整体操作;第一个路径一般用作局部查找。