三维几何模型在计算机内的表示.docx

三维几何模型在计算机表达
CAD/CAM关键技术是几何造型技术一项研究在计算机中怎样表达物体模型形状技术。
在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)〞系统，开目信息技术XX企业开发开目三维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．正那么集合运算
能产生正那么几何体〔有正那么点集构成形体〕集合运算称为正那么集合运算。正那么集合运算与老式集合运算区别重要是在对产生成果边界面处理上，其部点处理是一致。正那么运算重要是考虑怎样消除或不产生悬点悬边和悬面。如如下图：

上图，左边为老式交运算成果，右边为正那么交运算成果。在老式集合运算符后加“*〞号表达正那么运算符。
实现正那么集合运算有两种措施：间接法和直接法。间接法是先按一般集合运算求出成果，后用某些规那么判断，以消除不符合正那么几何定义局部〔即悬边、悬面等〕，从而得到正那么几何体。直接法是定义正那么集合算子体现式，用以直接得出符合正那么几何体定义成果。
正那么几何运算定义如下：
A* B = r ( A B ) ;
式中表达老式集合并、交、差算子；
*表达对应正那么并、交、差算子；
r是集合正那么化算子。
实体造型是以立方体圆柱体、球体、锥体、环状体等多种主线体素为单位元素，通过集合运算(拼合或布尔运算)，生成所需要几何形体。这些形体具有完整几何信息，是真实而唯一三维物体。因此，实体造型包括两局部容：即体素定义和描述，以与体素之间布尔运算(并、交、差)。布尔运算是构造复杂实体有效工具。目前常用实体表达措施重要有：构造实体几何法(CSG)、边界表达法(BRep)和扫描法。
物体CSG树表达
物体体素构造表达法〔Constructive Solid Geometry, CSG〕是用两个物体间并、交、差正那么集合运算操作生成一种新物体措施。
CSG表达法：先定义某些形状比拟简单常用体素，如方块、圆柱、圆锥、球、棱柱等。然后用集合运算并、交、差把体素修改成复杂形状形体。初期CSG模型仅使用代数方程与半空间概念，体素只支持多面体与二次曲面体，而不支持外表具有自由曲面实体。整个模型是棵树构造，最终形体外表交线与有效区域没有显式给出，不能直接用于NC加工与有限元分析等后继处理。
集合运算构造实体过程可用二叉树构造表达，称该二叉树为CSG树。树叶节点表达体素或带有几何变换参数体素，非叶节点表达施加于其子节点正那么集合算子，或称布尔算子。树根节点表达集合运算最终止果，也即但愿得到实体。
边界表达法
边界表达法〔Brep-Boundary Representation〕通过描述物体边界来表达一种物体。所谓边界是指物体部点与外部点分界面，定义了物体边界，该物体也就被唯一地定义了。如如下图：
边界表达法一种重要特点是：描述物体信息包括几何信息与拓扑信息两个方面。几何信息是指物体在欧氏空间中位置、形状和大小；而拓扑信息是指拓扑元素〔顶点、边和外表〕数量与其互相间连接关系。拓扑信息构成物体“骨架〞，而几何信息那么犹如附着在这一“骨架〞上“肌肉〞。
几何信息有面〔face〕、环〔loop〕、边〔edge〕和点〔vertex〕，拓扑信息有模型〔model〕、 区域〔region〕、外壳〔shell〕、面引用〔face use〕、环引用〔loop use〕、边引用〔edge use〕和点引用〔vertex use〕。如如下图是用辐射边数据构造表达一种形体模型，注意其中实体、面、线是用统一数据构造表达。

顶点
顶点〔Vertex〕位置用〔几何〕点〔Point〕来表达。点是几何造型中最主线元素，自由曲线、曲面或其他形体均可用有序点集表达。用计算机存储、管理、输出形体实质就是对点集与其连接关系处理。
在正那么形体定义中，不容许孤立点存在。
边
边〔Edge〕是两个邻面(对正那么形体而言)、或多种邻面(对非正那么形体而言)交集，边有方向，它由起始顶点和终止顶点来界定。边形状〔Curve〕由边几何信息来表达，可以是直线或曲线，曲线边可用一系列控制点或型值点来描述，也可用显式、隐式或参数方程来描述。形体中与一条空间曲线相联络，以与包含其两个端点和引用它
所有环边等信息拓扑元素称为边。
环
环〔Loop〕是有序、有向边〔Edge〕构成封闭边界。环中边不能相交，相邻两条边共享一种端点。环有方向、外之分，外环边一般按逆时针方向排序，环边一般按顺时针方向排序。
面
面〔Face〕由一种外环和假设干个环〔可以没有环〕来表达，环完全在外环之。根据环定义，在面上沿环方向前进，左侧总在面，右侧总在面外。面有方向性，一般用其外法矢方向作为该面正向。假设一种面外法矢向外，称为正向面；反之，称为反向面。面形状〔Surface〕由面几何信息来表达，可以是平面或曲面，平面可用平面方程来描述，曲面可用控制多边形或型值点来描述，也可用曲面方程〔隐式、显式或参数形式〕来描述。对于参数曲面，一般在其二维参数域上定义环，这样就可由某些二维有向边来表达环，集合运算中对面分割也可在二维参数域上进展。
体
体〔Body〕是面并集。在正那么几何造型系统中，规定体是正那么，非正那么形体造型技术将线框、外表和实体模型统一起来，可以存取维数不一致几何元素，并可对维数不一致几何元素进展求交分类，从而扩大了几何造型形体覆盖域。 几何形体是由封闭外表围成空间，是欧氏空间中非空、有界封闭子集，其边界是有限个面并集。
外壳
外壳是某些点、边、环、面集合,其所含面集有也许围成封闭三维区域，从而构成一种实体；外壳还可以表达任意一曲面或假设干个曲面构成面组；外壳还可以是一条边或一种孤立点。外壳中环和边有时被称为“线框环〞和“线框边〞，这是由于它们可以用于表达形体线框图。
区域
由一组外壳构成，而模型由区域构成。
正那么形体
对于任一形体，假如它是三维欧氏空间R3中非空、有界封闭子集，且其边界是二维流形(即该形体是连通)，那么称该形体为正那么形体，否那么称为非正那么形体。
在这种表达法中，由于物体点、边和外表以独立对象形式存在，因此可以以便地对物体进展多种局部修改。
多面体顶点、边和外表之间拓扑关系可用9种不一样形式予以描述：
1．顶点相邻性，表达 v->{v}
2．顶点—边相邻性，表达v->{e}
3．顶点—面相邻性，表达v->{f}
4．边—顶点，     e->{v}
5．边—边           e->{e}
6．边—面            e->{f}
7．面—顶点        f->{v}
8．面—边            f->{e}
9．面—面            f->{f}
边界表达数据构造
两种经典边界表达法数据构造重要包括：翼边构造，双向边表(DCEL―Doubly Connected Edge List) ，半边构造，四边构造，辐射边(Radial-Edge)构造等等。其中半边构造非常适合表达正那么形体。
翼边构造
在顶点、边、外表等构成物体三要素中，翼边构造以边为中心来组织数据。如如下图：

struct Edge{
Vertex P1,P2;
Loop *LeftLoop,*RightLoop;
struct Edge *ercw,*ercc,*elcc,*elcw;
}
上图菱边e作为有向线段，其数据构造中包具有两个指针，分别指向e两个端点：起点P1和终点P2。此外，e中还设置有两个环指针，分别指向菱边e所邻接两外表上环Loop左和Loop右。这样就确定了菱边e与相邻外表之间拓扑关系。为了能从边e出发找到它所在任一闭合面环上其他菱边，在e中又增长了四个边指针ercw、ercc、elcc、elcw，ercc表达e在右面环中沿逆时针方向所连接下一条菱边，elcw表达e在左面环中沿顺时针方向所连接下一条边，余类推。
由于翼边构造边构造和使用比拟复杂，后来在此构造根底上改良，提出了半边数据构造。半边构造已成为边界表达主流数据构造。
半边数据构造
实体B-rep表达模型是一非常复杂模型，规定可以体现出多面体各几何元素之间完整几何和拓扑关系，并且容许对这种几何和拓扑关系进展修改.在B-rep表达中，体、面、边和顶点是最主线几何元素，在实体拼合、显示、分析计算或人机交互过程中，对主线几何元素如下操作是必不可少：
l 增长或删除体、面、边或顶点；
l 一种体，查找它所有面、所有边或所有顶点；
l 一种面或一种边，查找它所属于体；
l 一种面，次序查找围成它所有边；
l 一种边，查找交于该边所有面，或着查找该边邻边，或者查找该边两个端点；
l 一种顶点，查找交于该顶点所有边或所有面。
以上这些主线操作效率直接影响着整个实体造型系统效率。一种B-rep数据构造应当以便、迅速地实现几何元素这些查询或增删操作．为了查询或操作以便，必须建立各几何元素间拓扑关系，且引入其他辅助元素，例如在许多B-rep数据构造中具有环结点，用来表达面、外封闭边界．在B-rep数据构造设计时，除了需要考虑时间原因外，还要考虑空间原因，即模型所占计算机存大小，但往往这两方面是互相矛盾．要想各个几何元素之间查询迅速，必然要在它们之间建立广泛联络，这样必然增长存储空间占用量。反过来也是如此，而半边数据构造就很好权衡了空间和时间问题。
在构成多面体三要素〔点、边、面〕中，半边数据构造仍以边为关键，但为了以便体现拓扑关系，它将一条边表达到拓扑意义上方向相反两条“半边〞，因此称为半边数据构造，其构造入图：

半边数据构造六个结点在C语言中被体现成“构造〞.结点之间通过构造指针互相联络.这些结点描述如下：
顶点结点：顶点结点是半边数据构造中最底层结点，实体几何位置和尺寸最终都由顶点结点来定义.因此，顶点结点必须包含顶点空间三维坐标值半边结点：半边结点包含指向前趋半边和后继半边两个指针.这两个指针形成了一种环半边双向链表.半边结点还包含半边所属于环指针，以与半边起始顶点指针。
边结点：边结点包含左右两个半边指针，通过这两个指针可以查找该边两个端点以与交于该边两个面.指向前趋边和后继边两个指针实现一种实体边双向链表。
环结点：由于一种环包含一系列首尾相接半边，故环结点是一种指向这些半边其中之一指针，通过该指针可以查找构成该环所有半边.环结点还包含指向前趋和后继环两个指针，用以实现一种面环双向链表.此外，环结点还包含指向环所在面指针。
。
体结点：在半边数据构造中，体结点是多种引用根结点.从体结点出发，可以搜索任何其他结点.因此，体结点，包含面、边和顶点首指针.体结点之间也是通过前趋指针和后继指针形成双向链表来连接。

从图中可以看出，许多几何元素可以有不一样搜索途径，例如查找实体上顶点可以有两个途径：一是体→面→环→半边→顶点；二是体→顶点．第二个途径比第一种途径要简捷得多，用来进展实体平移等整体操作；第一种途径一般用作局部查找。

12 / 12