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

三维几何模型在计算机内得表示
CAD/CAM得核心技术就是几何造型技术一项研究在计算机中如何表示物体模型形状得技术。
在CAＤ/CAＭ技术四十多年得发展历程中，经历了四次重大得变革.
60年代初期得ＣＡD系统只能处理简单得线框模型,提供二维得绘图环境,用途比较单一。
进入70年代,根据汽车造型中得设计需求,法国人提出了贝塞尔算法，随之产生了三维曲面造型系统CＡTIＡ.它得出现,标志着CAD技术从单纯模仿工程图纸得三视图模式中解放出来，首次实现以计算机完整描述产品零件得主要信息。这就是ＣAD发展历史中得第一次重大飞跃。
１979年,SＤRＣ公司发布了世界上第一个完全基于实体造型技术得大型ＣAD/CＡE软件──ＩＤEAS。由于实体造型技术能够精确表达零件得全部属性,在理论上有助于统一CAD、ＣＡE、ＣAM得模型表达，给设计带来了惊人得方便性。可以说，实体造型技术得普及应用标志着CＡＤ发展史上得第二次技术革命.但就是,在当时得硬件条件下，实体造型得计算及显示速度太慢，限制了它在整个行业得推广.
9０年代初期，参数化技术逐渐成熟，标志着CAＤ技术得第三次革命。参数化技术得成功应用，使得它在1９90年前后几乎成为CAD业界得标准。
随后,ＳDRC攻克了欠约束情况下全参数得方程组求解问题，形成了一套独特得变量化造型理论。SDRC将变量化技术成功得应用到CＡD系统中,标志着ＣAD技术得第四次革命.
随着CAＤ技术与几何造型技术得发展， 近年来， 市场上出现了一大批优秀得几何造型软件及工具.例如，PTC公司得产品Ｐro／E、ＳDRＣ得产品I-ＤEAS　Masteｒ Sｅriｅs、UGS公司得产品Ｕnigrａｐhiｃs、IBM公司得产品CATIA/CAＤAＭ、Aｕtodeｓk公司得产品ＭDT、Sｐatiaｌ　Tech公司得ＡCIS、ＥDＳ公司得Parasｏlｉd等。在国内,清华大学、北京航空航天大学、华中理工大学、浙江大学、上海交通大学、西北工业大学,以及其她一些单位也发表了一些关于特征造型技术研究得论著，并开发了一些特征造型系统，例如:清华大学开发得ＴｉGｅｍｓ造型系统，北京航空航天大学研制出得微机版“金银花（LONICERA)”系统，武汉开目信息技术有限责任公司开发得开目三维CAＤ软件等等。

造型系统简介
Parａｓoｌid与ＡＣIS就是两个最有代表性得几何造型系统得开发平台.在早期开发得实体造型系统中,英国得剑桥大学研制出了BUＩＬD—1与BＵILＤ—2系统，但都没有公开使用。8０年代初期,研究小组得一部分人组建了Ｓhape Data公司,并开发了实体造型系统Romuluｓ。１９８6年,Ｓhａpｅ Data并入EDS Ｕnｉgｒapｈics之后，推出了功能强大得几何造型核心Paｒaｓolid.同时,Shａｐe Daｔa一部分保留人员研制了新得造型核心，就就是后来由Spatiａl　Teｃhnｏlogy公司推出得几何造型系统核心ＡCIS.
Ｐarasｏlid与ＡCＩS并不就是面向最终用户得应用系统，而就是“几何引擎”,作为应用系统得核心.用户可用它们作为平台,开发自己得应用系统.当今许多流行得商用CAＤ/ＣAM软件，如Uniｇraphics、Soｌidedge、Soｌｉdwork、MDT等，都就是在Pａｒａsｏlｉd或ACIS得基础上开发出来得。

Ｐaraｓolid有较强得造型功能,但就是只能支持正则实体造型。它提供得主要功能有：集合运算、特征得创建与编辑、局部操作、数据交换文件接口等。Ｐarasolｉd采用精确得边界表示,包括拓扑、几何与关联三种数据类型。
ＡCIS具有与Pａrａｓolid相似得形体结构，但在系统结构上采用了核心与外壳相结合得方式.ＡＣＩS支持线框、表面与实体得统一表示,支持非正则形体得造型。
在上述几何实体造型系统中，通常都会提供一些基本得形体输入方法，以及拉伸,旋转，蒙皮,扫描等直接构造形体得方法,通过集合运算对形体进行拼合.虽然对这些造型方法得研究取得了一系列新进展,但就是集合运算仍基本局限在对两个体进行正则运算（交，并,差)上，而且结果形体得信息都已经包含在两个参加运算得原始形体之中,不能引入新得信息。实际应用中，有些机械零件具有特定得形状特征,不能通过集合运算来直接完成，或者直接实现时操作步骤非常复杂。但就是,它们得生成方法与集合运算非常相似，可以瞧作就是集合运算得扩展。拔模与抽壳都属于这一类型得造型方法。
三维形体得表示 
三维造型技术就是建立恰当得模型来表示自然界中形态丰富得三维物体得技术，根据造型对象将造型技术分成３类。
第一类就是曲面造型，主要研究计算机内如何描述一张曲面，及曲面得显示与控制。曲面造型又分成规则曲面与不规则曲面两种。不规则曲面造型方法主要有贝塞尔曲线曲面、Ｂ样条曲线曲面与孔斯曲面等.(二维曲线：Ｎurbs（通过拟合点）、三次Ｂ样条(通过控制点）、贝塞尔（控制点与拟合点重合）与波浪线(B样条))）
第二类就是立体造型方法,主要研究在计算机内如何定义、表示一个三维物体，主要有体素构造法、边界表示法与八叉数法等等。曲面造型与立体造型合称几何模型造型。该技术主要应用在机械行业辅助设计制造领域(CAD）。
第三类就是自然景物模拟,主要研究在计算机内如何模拟自然景物，如云、流水、树等。该造型技术主要应用在游戏与艺术造型等领域。
如下主要说说几何模型得表示。
在计算机中，表示几何形体得方法通常有三种：线框模型、表面模型与实体模型
一、线框模型
ﻩ该模型采用三维形体得全部顶点及边得集合来描述三维形体,即用顶点表与边表
两个表得数据结构来表示三维模型。每条边由两个顶点表示。
主要优点就是结构简单,处理容易。描述二维目标十分理想。但对三维物体，存在如下缺点：
1）没有面得信息,它不能表示表面含有曲面得物体。
２）不能明确定义点与物体之间得关系。
3)点与边信息容易出现二义性.

二、表面模型
ﻩ在线框模型得基础上，增加了物体中得面得信息，用面得集合来表示物体，每个面由多条有向边构成，用环来定义面得边界，即就是用顶点表、边表与面表来描述模型。表面模型又分为平面模型与曲面模型。前者以多边形网格为基础。后者以参数曲面块为基础.
ﻩ表面模型存在得不足就就是它只能表示物体得表面边界,而不能表达出真实实体得属性，很难确认一个表面模型表示得三维图形就是一个实体还就是一个空壳。这个不足，在实体模型中得到了解决.
三、实体模型
ﻩ实体模型就是最高级得模型，它能完整表示物体得所有形体信息,可以无歧义地确定一个点就是在物体外部还就是内部或表面上。
ﻩ实体模型使用有向边得右手法则来确定所在面得外法线方向.即用右手沿边得顺序方向握住，大拇指所指向为该面得外法线方向。法线方向指向体外。
体外

实体模型存在着不同得数据结构，在这些结构中存在一个共同点,即数据结
构不仅记录了物体全部得几何信息，而且还记录了所有得点、线、面、体得拓扑信息（即空间位置关系)。实体模型得构造通常使用体素(即原始得基本实体),经集合论中得交、并、差运算构成复杂形体.
1． 实体得定义
ﻩ实体就就是有效得物体,即客观世界中确实存在得物体，要在计算机内表示、构造一个实体，就必须给出实体得确切定义(即用最小得数据结构唯一地确定实体得形状与位置。）如下图带有悬挂面得立方体就不就是实体，在客观世界中不可能存在这样得物体。

作为实体应满足如下条件:
1．刚性。一个实体必须具有一定得形状（流体不属于实体)
2。维数一致性。一个实体得各个部分必须就是三维得,不能存在悬挂得、孤立得边界。
3。有限性。一个实体必须占有有限得空间。
4.边界确定性。根据实体得边界，可确定实体得内部或外部。
5．封闭性.经过集合运算后，仍然就是有效得实体。
 实体得表面必须具备如下性质：
1.连通性。表面任意两点都可用表面上得一条路径连接起来。
2.边界性。
３。非自相交性。一个实体表面不可自相交。
4．可定向性.一个实体得表面两则可明确定义出实体得内侧与外侧。
5.封闭性.一个表面得封闭性由多边形网格各元素得拓扑关系确定得。即每条边连接且仅连接两个面，每条边有且仅有两个端点.
从点集拓扑角度给出实体得定义。将三维实体瞧作就是空间中点得集合,它由内点与边界点共同组成。
　内点就是指点集中得这样一些点:它们具有完全包含于该点集得充分小得领域.点集中除内点外得所有得点就就是边界点。

所以三维物体A可表示为：
A=　{bA，iA｝
bA为物体Ａ得边界点集;iＡ为物体A得内部点集。
定义点集得正则运算r如下:
ｒA =　ｃiＡ
i为取A得内点运算；
c为取闭包运算;
Ａ为一个点集。
iA为A得全体内点组成得集合，称为A得内部，它就是一个开集(“开集”可以理解为没有边界值去判断点就是否为内点).
ciＡ为Ａ得内部得闭包,就是iA与其边界点得并集。（据此可以理解“闭包”得含义），它本身就是一个闭集,(“闭集"可以理解为可以通过明确得边界值来判断点就是否在集合中）。
正则运算即为：先对物体取内点再取闭包得运算。rA称为物体A得正则点集。如图:

带有悬边得二维点集Ａ
内点集合 iA
(没有粗边界）
正则点集ｃｉA
（有粗边界）
以上图中,图1有悬边所以点集不就是有效实体，图２没有边界，不就是满足“封闭性”所以也不就是实体。图3为正则点集,封闭性，也满足实体得其她条件,所以为实体。
正则点集有时也不一定就是实体。如下图：

左图为正则点集,但它不就是有效得物体。由此，就会涉及到另外一个概念“二维流体"。
二维流体就是指对于实体表面上得任何一点，都可以找到一个围绕着它得任意小得领域,该领域在拓扑(即就是空间位置)上与平面上得一个圆盘就是等价得（也就就是在表面上存在着一个领域围绕着某个点）。这意味着，在领域得点集与圆盘之间存在着连续得一对一得对应关系.如上右图，立体表面上任一点都存在与圆盘同构得领域。而左图,两个立方体共享边被四个面共享，其上得点不存在这样得唯一得领域（在上图中,共享边得点,存在围绕它得领域有两个）。
有了上述概念后，实体可以这样描述为：
对于一个占据有限空间得正则点集，如果其表面就是二维流形，则该正则点集为实体(有效物体）。
2。正则集合运算
能产生正则几何体（有正则点集组成得形体)得集合运算称为正则集合运算。正则集合运算与传统集合运算得区别主要就是在对产生结果得边界面得处理上，其内部点得处理就是一致得。正则运算主要就是考虑如何消除或不产生悬点、悬边与悬面。如下图：

上图，左边为传统得交运算结果，右边为正则得交运算结果.在传统得集合运算符后加“＊”号表示正则运算符。
实现正则集合运算有两种方法:间接法与直接法。间接法就是先按普通集合运算求出结果,后用一些规则判断,以消除不符合正则几何定义得部分（即悬边、悬面等),从而得到正则几何体。直接法就是定义正则集合算子得表达式，用以直接得出符合正则几何体定义得结果。
正则几何运算定义如下:
Ａ<OP〉＊ B ＝　r （　A　<ＯP〉 B ) ;
式中＜OP>表示传统集合并、交、差算子；
＜OP〉＊表示相应得正则并、交、差算子;
r就是集合得正则化算子。
实体造型就是以立方体、圆柱体、球体、锥体、环状体等多种基本体素为单位元素，通过集合运算(拼合或布尔运算),生成所需要得几何形体.这些形体具有完整得几何信息,就是真实而唯一得三维物体。所以，实体造型包括两部分内容：即体素定义与描述，以及体素之间得布尔运算(并、交、差）.布尔运算就是构造复杂实体得有效工具.目前常用得实体表示方法主要有:构造实体几何法(CSG）、边界表示法（BＲep)与扫描法。
物体得CSＧ树表示
物体得体素构造表示法(Constｒｕctive Solid Geｏmeｔｒy, ＣSG）就是用两个物体间得并、交、差正则集合运算操作生成一个新得物体得方法。
ＣSG表示法:先定义一些形状比较简单得常用体素,如方块、圆柱、圆锥、球、棱柱等。然后用集合运算并、交、差把体素修改成复杂形状得形体。早期得CSG模型仅使用代数方程及半空间得概念,体素只支持多面体与二次曲面体,而不支持表面含有自由曲面得实体。整个模型就是棵树结构,最终形体得表面交线与有效区域没有显式给出,不能直接用于NＣ加工与有限元分析等后继处理。
集合运算构造实体得过程可用二叉树结构表示，称该二叉树为CSG树。树得叶节点表示体素或带有几何变换参数得体素,非叶节点表示施加于其子节点得正则集合算子，或称布尔算子.树得根节点表示集合运算得最终结果，也即希望得到得实体。
边界表示法
边界表示法(Ｂrep—Ｂouｎdａｒy Repｒｅsentatiｏn)通过描述物体得边界来表示一个物体.所谓得边界就是指物体得内部点与外部点得分界面，定义了物体得边界，该物体也就被唯一地定义了。如下图:
边界表示法一个重要得特点就是：描述物体得信息包括几何信息与拓扑信息两个方面.几何信息就是指物体在欧氏空间中得位置、形状与大小;而拓扑信息就是指拓扑元素(顶点、边与表面）得数量及其相互间得连接关系。拓扑信息构成物体得“骨架",而几何信息则犹如附着在这一“骨架”上得“肌肉”。
几何信息有面（facｅ)、环（lｏop）、边(edｇe)与点(ｖｅrｔex)，拓扑信息有模型(modｅl）、 区域(ｒｅgion)、外壳（shell）、面引用（ｆace use）、环引用（loop ｕｓe)、边引用(ｅdge　use）与点引用（veｒteｘ　ｕｓｅ)。如下图就是用辐射边数据结构表示得一个形体模型，注意其中实体、面、线就是用统一得数据结构表示得.

顶点
顶点（Vｅrtex）得位置用（几何）点(Poiｎｔ）来表示。点就是几何造型中得最基本得元素，自由曲线、曲面或其它形体均可用有序得点集表示。用计算机存储、管理、输出形体得实质就就是对点集及其连接关系得处理.
在正则形体定义中，不允许孤立点存在.
边
边(Ｅdｇｅ）就是两个邻面(对正则形体而言)、或多个邻面(对非正则形体而言）得交集,边有方向，它由起始顶点与终止顶点来界定。边得形状（Curvｅ）由边得几何信息来表示，可以就是直线或曲线,曲线边可用一系列控制点或型值点来描述,也可用显式、隐式或参数方程来描述。形体中与一条空间曲线相联系,以及包含其两个端点与引用它得
所有环边等信息得拓扑元素称为边.
ﻩ环
环（Ｌoop)就是有序、有向边(Ｅdge）组成得封闭边界。环中得边不能相交，相邻两条边共享一个端点。环有方向、内外之分，外环边通常按逆时针方向排序,内环边通常按顺时针方向排序.
面
面（Ｆaｃe）由一个外环与若干个内环（可以没有内环）来表示，内环完全在外环之内。根据环得定义,在面上沿环得方向前进，左侧总在面内,右侧总在面外。面有方向性,一般用其外法矢方向作为该面得正向。若一个面得外法矢向外,称为正向面；反之,称为反向面。面得形状（Ｓuｒfacｅ）由面得几何信息来表示,可以就是平面或曲面,平面可用平面方程来描述，曲面可用控制多边形或型值点来描述，也可用曲面方程(隐式、显式或参数形式）来描述.对于参数曲面，通常在其二维参数域上定义环，这样就可由一些二维得有向边来表示环，集合运算中对面得分割也可在二维参数域上进行。
体
体（Bｏdｙ)就是面得并集。在正则几何造型系统中,要求体就是正则得，非正则形体得造型技术将线框、表面与实体模型统一起来,可以存取维数不一致得几何元素,并可对维数不一致得几何元素进行求交分类，从而扩大了几何造型得形体覆盖域。 几何形体就是由封闭表面围成得空间,就是欧氏空间中非空、有界得封闭子集，其边界就是有限个面得并集。
外壳
外壳就是一些点、边、环、面得集合，其所含得面集有可能围成封闭得三维区域,从而构成一个实体；外壳还可以表示任意得一张曲面或若干个曲面构成得面组；外壳还可以就是一条边或一个孤立点.外壳中得环与边有时被称为“线框环"与“线框边”，这就是因为它们可以用于表示形体得线框图。
区域
由一组外壳组成，而模型由区域组成。
正则形体
对于任一形体，如果它就是三维欧氏空间R3中非空、有界得封闭子集，且其边界就是二维流形(即该形体就是连通得)，则称该形体为正则形体，否则称为非正则形体。
在这种表示法中,由于物体得点、边与表面以独立对象得形式得存在，所以可以方便地对物体进行各种局部修改。
多面体得顶点、边与表面之间得拓扑关系可用9种不同得形式予以描述：
ﻩ1。顶点相邻性,表示 v—〉｛v｝
2。顶点—边相邻性，表示v->{ｅ｝
3．顶点-面相邻性，表示ｖ-〉｛f}
4．边—顶点，     e-〉｛v}
ﻩ5。边—边          　ｅ->｛e｝
6．边—面            e—〉{f｝
ﻩ７．面—顶点        f－〉{ｖ}
８。面-边            f->{ｅ｝
9.面—面            ｆ－>｛f｝
边界表示得数据结构
ﻩ两种典型得边界表示法数据结构主要包括:翼边结构,双向边表（DCEL―Doubly Ｃonｎecｔed Eｄｇe List) ，半边结构,四边结构，辐射边(Radiａl-Eｄｇe)结构等等。其中半边结构非常适合表示正则形体.
翼边结构
在顶点、边、表面等组成物体得三要素中,翼边结构以边为中心来组织数据。如下图:

struｃt　Edge{
Veｒtex P1，Ｐ2；
Ｌｏop ＊LeftLoop,*RｉghtＬoｏp;
struct Eｄｇｅ ＊erｃw，＊eｒcc，*elｃｃ，＊elcw；
｝
上图菱边e作为有向线段,其数据结构中包含有两个指针，分别指向e得两个端点：起点P1与终点P2.此外,e中还设置有两个环指针，分别指向菱边ｅ所邻接得两表面上得环Loop左与Loop右。这样就确定了菱边e与相邻表面之间得拓扑关系。为了能从边ｅ出发找到它所在得任一闭合面环上得其她菱边,在ｅ中又增加了四个边指针eｒcw、ercc、ｅlcｃ、elcｗ，eｒｃc表示e在右面环中沿逆时针方向所连接得下一条菱边，ｅlcｗ表示e在左面环中沿顺时针方向所连接得下一条边，余类推。
由于翼边结构边得构造与使用比较复杂,后来在此结构基础上改进,提出了半边数据结构。半边结构已成为边界表示得主流数据结构。
半边数据结构
实体得Ｂ—rｅｐ表示模型就是一非常复杂得模型，要求能够表达出多面体各几何元素之间完整得几何与拓扑关系,并且允许对这种几何与拓扑关系进行修改、在B－rep表示中,体、面、边与顶点就是最基本得几何元素,在实体得拼合、显示、分析计算或人机交互过程中，对基本几何元素得下列操作就是必不可少得:
l 增加或删除体、面、边或顶点；
l 已知一个体,查找它得所有面、所有边或所有顶点;
l 已知一个面或一个边，查找它所属于得体；
l 已知一个面,顺序查找围成它所有边；
l 已知一个边，查找交于该边得所有面,或着查找该边得邻边,或者查找该边得两个端点;
l 已知一个顶点，查找交于该顶点得所有边或所有面.
以上这些基本操作得效率直接影响着整个实体造型系统得效率。一个B-ｒep数据结构应当方便、迅速地实现几何元素得这些查询或增删操作．为了查询或操作方便,必须建立各几何元素间得拓扑关系，且引入其它辅助元素，例如在许多Ｂ－rep数据结构中具有环结点,用来表示面得内、外封闭边界.在B—rｅｐ得数据结构设计时，除了需要考虑时间得因素外，还要考虑空间得因素，即模型所占计算机内存得大小,但往往这两方面就是互相矛盾得.要想各个几何元素之间查询迅速,必然要在它们之间建立广泛得联系，这样必然增加存储空间得占用量.反过来也就是如此，而半边数据结构就很好得权衡了空间与时间得问题。
在构成多面体得三要素(点、边、面）中,半边数据结构仍以边为核心，但为了方便表达拓扑关系，它将一条边表示成拓扑意义上方向相反得两条“半边”，所以称为半边数据结构,其结构入图：

半边数据结构共包含六个结点:体、面、环、边、半边与顶点、半边就是一连接两个顶点并具有一固定方向得线段、一系列首尾相连得半边形成一个环、半边得关系就是一个边包含两个相反方向得半边，由这两个半边可以查询交于这个边得两个面.半边得含义如上图所示、半边数据结构得优点就是几何元素之间得互相查询非常方便，不足之处就是由于结点多占用空间较大。
半边数据结构得六个结点在C语言中被表达成“结构”、结点之间通过结构指针互相联系、这些结点描述如下：
顶点结点:顶点结点就是半边数据结构中最底层得结点,实体得几何位置与尺寸最终都由 顶点结点来定义、所以，顶点结点必须包含顶点得空间三维坐标值半边结点:半边结点包含指向前趋半边与后继半边得两个指针、这两个指针形成了一个环内半边得双向链表、半边结点还包含半边所属于得环得指针,以及半边起始顶点得指针。
边结点：边结点包含左右两个半边得指针，通过这两个指针可以查找该边得两个端点以及交于该边得两个面、指向前趋边与后继边得两个指针实现一个实体内边得双向链表。
环结点:因为一个环包含一系列得首尾相接得半边,故环结点就是一个指向这些半边其中之一得指针，通过该指针可以查找构成该环得所有半边、环结点还包含指向前趋与后继环得两个指针,用以实现一个面内环得双向链表、另外，环结点还包含指向环所在面得指针。
面结点：因为面就是由若干个环围成得内部连通得平面多边形,所以，面结点包含一个环得首指针，用来查找围成它得所有环、因为外环只有一个，为了区分内环与外环,面结点中包含指向它得外环得指针、面得前趋指针与后继指针形成一个实体内面得双向链表、面结点中还包含指向它所属于得体得指针,用来查询面所属于得实体、面所在平面得方程也就是定义完整实体得重要内容，所以,面结点中包含一个四个浮点数得数组，表示其平面方程.
体结点:在半边数据结构中，体结点就是各种引用得根结点、从体结点出发，可以搜索任何其它得结点、所以，体结点,包含面、边与顶点得首指针、体结点之间也就是通过前趋指针与后继指针形成得双向链表来连接。

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