三维形体的表示

《三维形体的表示》由会员分享，可在线阅读，更多相关《三维形体的表示（102页珍藏版）》请在装配图网上搜索。

1、引 言n三维图形在科学研究和工程技术中有着广泛的应用。在CAD中，需要对所设计的作品从不同的角度进行审视。计算机几何造型就是用计算机系统来表示、控制、分析和输出三维形体。所以几何造型是计算机图形学中一个十分重要的应用领域，它是CAD/CAM和CIMS系统的核心技术，也是用来实现计算机辅助设计的基本手段。几何造型的功能：n形体输入，即把形体从用户格式转换成计算机内部格式；n图形数据的存储和管理；n图形控制，如对形体进行平移、缩放、旋转等几何变换；n图形修改，如应用集合运算、欧拉运算、有理B样条操作及其交互手段实现对形体局部或整体修改；n图形分析，如形体的容差分析，物质特性分析等；n图形显示输出，

2、如消隐、光照、颜色的控制等；n询问形体的属性及其有关参数1北大计算机系多媒体与人机交互形 体n在计算机形体一般定义为六层拓扑结构，首先介绍在三维空间中基本术语的定义。形体形体(object)外壳外壳(shell)面面(face)环环(loop)边边(loop)顶点顶点(vertex)曲线和直线曲线和直线方程方程 点的点的 几何坐标几何坐标2北大计算机系多媒体与人机交互形 体n体由封闭表面围成的有效空间称为体；一个形体Q是R3空间中非空、有界的封闭子集。其 边界（记为Q）是有限个面的并集，而外壳是形体的最大边界。一个单位立方体可定义为：(x,y,z)R3|0 x1,0y1,0z1其中一个表面可表

3、示为：(1,y,z)R3|0y1,0z1 必须注意：并没有规定形体必须是一个连续的封闭集合，目的是用这样的定义来扩大几何造型的域，使得形体可以由不连续的体素，或是仅有某些相交的形体组成。xzy3北大计算机系多媒体与人机交互形 体n面R3中非空、连续、共面且封闭的子集称为面F，其边界(记为F)是有限条线段的并集，Pt表示含有F的唯一平面。面是形体表面的一部分，且具有方向性.FPt4北大计算机系多媒体与人机交互形 体n环由有序、有向边组成的面的封闭边界称为环，环中任意边都不能自交，相邻两条边共享一个端点，环又分为内环和外环。内环是在已知面中的内孔或凸台面边界的环，其边按逆时针方向。外环是已知面的最

4、大外边界的环，其边按顺时针方向，按这种方式定义，在面上沿着边的方向前进，面的内部始终在走向的右侧。5北大计算机系多媒体与人机交互形 体n边形体内两个相邻面的交界称为边，一条边有且仅有两个相邻面。两个端点确定一条边，这两个端点分别称为该边的起点和终点。假设Q是一个形体，E(Q)是形体边的集合，则在Q(形体的边界)中E(Q)满足下属条件的所有线段的集合：n边e的两个端点属于V(Q)；n边e中没有一个内部点属于V(Q)（所有顶点的集合）n边e上每个点，都有两个不同的面，即存在两个面fi，fiQ使得边efifj；n形体Q的边框线WF(Q)是由有序对(V(Q),E(Q)所组成。v1v2ef1f26北大计

5、算机系多媒体与人机交互形 体n点边的端点称为点，点不能出现在边的内部，也不能孤立地位于物体内、物体外或面内，顶点又是F(面边界)中两条不共线的线段的交点。v1v2ef1f27北大计算机系多媒体与人机交互形 体n体素具有有限个参数定义，且简单的连续封闭的形体称为体素，如长方体、圆柱体、圆锥、球、环等。n半空间集合P|F(P)0成为半空间，其中P为R3中的一点，F为一个平面，当F=0时，表示一个平面，这个平面的半空间可以由F(P)=ax+by+cz+d定义的平面加上在平面某一侧的所有点组成。显然一个长方体可以看成是6个平面半空间的交。n几何信息用来表示形体的几何性质和度量关系称为几何信息。n拓扑信

6、息用来表示形体之间的连接关系称为拓扑信息。8北大计算机系多媒体与人机交互表示形体的两种模型n数据模型n完全以数据描述n例如n用以8个顶点表示的立方体n以中心点和半径表示的球n以数据文件的形式存在n包括-特征表示、空间分割表示、推移表示、边界表示、构造实体几何表示等n进一步分为n线框模型n表面模型n实体模型9北大计算机系多媒体与人机交互线框模型线框模型：将形体表示成一组轮廓线的集合。n一般地，画出了形体的棱线与轮廓线就能唯一地表示出来。如图，八个顶点可以定义一个长方体，但还不足以识别它，如果定义了棱线，则无论如何放置长方体都能唯一地表示了。对于多面体由于其轮廓线和棱线通常是一致的，所以多面体的线

7、模型更便于识别，且简单。e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s410北大计算机系多媒体与人机交互线框模型n优点：简单、处理速度快n缺点：1、对于非平面多面体，如圆柱、球等形体，其轮廓线随观察方向的改变而改变，无法用一组固定的轮廓线来表示它们。2、线框模型与形体之间不存在一一对应关系：它仅仅通过给定的轮廓线约束所表示形体的边界面，而在轮廓线之间的地方，形体的表面可以任意变化。3、没有形体的表面信息，不适于真实感显示，由此导致表示的形体可能产生二义性。11北大计算机系多媒体与人机交互表面模型n表面模型n将形体表示成一组表面的集合

8、n如果把线框模型中的棱线包围的部分定义为面，所形成的模型便是表面模型。其数据结构是在线模型的基础上附加一些指针，有序地连接棱线。下图中表面编号表示第几个表面，表面特征表面是平面还是曲面。n形体与其表面一一对应，适合于真实感显示4顶点个数1起始指针0表面特征5表面编号14043032021连接指针属性顶点号1423234112北大计算机系多媒体与人机交互表面模型n缺点：n不能有效的用来表示实体n原因：n1、表面模型中的所有面未必形成一个封闭的边界n2、各个面的侧向没有明确定义，即不知道实体位于面的哪一侧13北大计算机系多媒体与人机交互实体模型n实体模型n用来描述实体，主要用于CAD/CAMn包含

9、了描述一个实体所需的较多信息，如几何信息、拓扑信息，可以支持多种运算，如欧拉运算等。14北大计算机系多媒体与人机交互表示形体的两种模型n过程模型n以一个过程和相应的控制参数描述n例如n用一些控制参数和一个生成规则描述的植物n以一个数据文件和一段代码的形式存在n包括-粒子系统、L系统、迭代函数系统等15北大计算机系多媒体与人机交互表示形体的两种模型n模型分类16北大计算机系多媒体与人机交互实体的定义n 抽象带来的问题n计算机中表示的物体是无效的n不能够客观存在n为什么要求客观存在nCAD/CAM的需求n什么是客观存在（有效）实体的定义n具有一定的形状n具有封闭的边界（表面)n内部连通n占据有限的

10、空间n经过运算后，仍然是有效的物体17北大计算机系多媒体与人机交互实体的定义n将三维物体看做一个点集，它由内点和边界点共同组成。n内点：具有完全包含于该点集的充分小的邻域n边界点：不具有内点性质的点集18北大计算机系多媒体与人机交互实体的定义 A是一个点集，定义点集的正则运算如下：ni：取内点运算nc:取闭包运算n正则运算rni A：A的全体内点组成的集合，称为A的内部nc i A为A的内部的闭包的运算，是i A与其边界点的并集。19北大计算机系多媒体与人机交互实体的定义n正则点集n 称为A的正则点集n称A为正则点集，如果它满足n问题：正则点集是实体？20北大计算机系多媒体与人机交互实体的定义

11、-举例说明n阴影部分：物体的内部区域n黑色部分：边界n(a)图取内点-(b)图求闭包-(c)图n正则运算：去除与物体维数不一致的悬挂部分或孤立部分。21北大计算机系多媒体与人机交互实体的定义n实体的定义可计算的条件n正则点集n表面是二维流形n二维流形n其上任意一点存在充分小的领域与圆盘同构（存在连续的一一映射）22北大计算机系多媒体与人机交互正则集合运算n为什么需要正则集合运算n正则集合运算是构造复杂物体的有效方法正则集合运算是构造复杂物体的有效方法n普通的集合运算会产生无效物体n(b):ABn(c):普通ABn(d)：正则AB23北大计算机系多媒体与人机交互正则集合运算n集合运算（并、交、差

12、）是构造形体的基本方法。正则形体经过集合运算后，可能会产生悬边、悬面等低于三维的形体。nRequicha在引入正则形体概念的同时，还定义了正则集合运算的概念。正则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面等。24北大计算机系多媒体与人机交互正则集合运算n正则集合运算的定义n正则并n正则交n正则差25北大计算机系多媒体与人机交互 任一实体S可以用它的边界bS和它的内部iS来表示，即 S=bS iS 由实体的定义可知，bS是封闭的，它将整个三维空间分成了三个区域：S的内部iS,S的边界bS,S的外部eS。边界bS与实体S是一一对应的。确定了边界，也就唯一确定了一个实体。因此，为了

13、求实体A，B的正则集合运算结果A op*B，只要求出其边界b（A op*B）即可。正则集合运算26北大计算机系多媒体与人机交互正则集合运算考察A,B两物体的交所形成拼合体的边界，由于A,B为正则点集，它们均可表示为边界点与体内点的集合，即A=bA iA;B=bB iB A物体的边界 bA可按其位于B物体内、B物体上、B物体外而分别表示为 bA=(bAiB)(bAbB)(bAeB)同理，bB=(bBiA)(bBbA)(bBeA)A27北大计算机系多媒体与人机交互正则集合运算其中bA bB=bB bA是A与B的公共边界，它可以分成两部分：（bA bB）同侧、(bA bB)异侧(bA bB)同侧由这

14、样一些边界构成：A、B位于边界的同侧(bA bB)异侧由这样一些边界构成：A、B位于边界的异侧28北大计算机系多媒体与人机交互正则集合运算n对于A*B，由交的定义可知：n1）A、B两物体的边界位于对方内部的部分边界位于对方内部的部分，即bA iB 和bB iA是b(A*B)的组成部分。n2）A、B两物体的边界位于对方外部的部分边界位于对方外部的部分，即bA eB 和bB eA不是b(A*B)的组成部分。n3）对于A、B的重合边界重合边界有：(bA bB)同侧属于b(A*B);(bA bB)异侧不属于b(A*B)因此：nb(A*B)=(bA iB)(bB iA)(bA bB)同侧29北大计算机系

15、多媒体与人机交互正则集合运算n同理：nb(A*B)=(bA eB)(bB eA)(bAbB)同侧nb(A*B)=(bA eB)(bB iA)(bAbB)异侧30北大计算机系多媒体与人机交互一些非正则形体的实例n一些非正则形体的实例31北大计算机系多媒体与人机交互n为了能够处理非正则形体，产生了非正则造型技术。n九十年代以来，基于约束的参数化、变量化造型和支持线框、曲面、实体统一表示的非正则形体造型技术已成为几何造型技术的主流。32北大计算机系多媒体与人机交互形体表示模型n在实体模型的表示中，基本上可以分为分解表示、构造表示和边界表示三大类。n1、分解表示将形体按某种规则分解为小的更易于描述的部

16、分，每一小部分又可分为更小的部分，这种分解过程直至每一小部分都能够直接描述为止。33北大计算机系多媒体与人机交互分解表示-空间位置枚举表示n形体空间细分为小的均匀的立方体单元。n用三维数组CIJK表示物体，数组中的元素与单位小立方体一一对应n当CIJK=1时，表示对应的小立方体被物体占据n当CIJK=0时，表示对应的小立方体没有被物体占据34北大计算机系多媒体与人机交互分解表示-空间位置枚举表示n优点n简单，可以表示任何物体n容易实现物体间的交、并、差集合运算n容易计算物体的整体性质，如体积等n缺点n占用大量的存储空间，如1024*1024*1024=1G bitsn物体的边界面没有显式的解析

17、表达式，不适于图形显示n对物体进行几何变换困难，如非90度的旋转变换n是物体的非精确表示35北大计算机系多媒体与人机交互分解表示-八叉树表示n八叉树表示n对空间位置枚举表示的空间分割方法作了改进：均匀分割 自适应分割n八叉树建立过程八叉树的根节点对应整个物体空间八叉树的根节点对应整个物体空间如果它完全被物体占据，将该节点标记为如果它完全被物体占据，将该节点标记为F(Full)，算法结束；算法结束；如果它内部没有物体，将该节点标记为如果它内部没有物体，将该节点标记为E(Empty)，算法结束；算法结束；如果它被物体部分占据，将该节点标记为如果它被物体部分占据，将该节点标记为P(Partial)，

18、并将它分割成并将它分割成8个子立方体，对每一个子立方体进个子立方体，对每一个子立方体进行同样的处理行同样的处理36北大计算机系多媒体与人机交互分解表示-八叉树表示n8叉树的表示应用三维形体的分解，它对一个外接立方体的形体进行前后、左右、上下等部分8个小立方体，如果小立方体单元为满或为空，表示该立方体完全在形体中或完全不在形体中，则其停止分解；对部分形体占有的小立方体需进一步分解为8个子立方体，直至所有小立方体单元要么全部满，要么全部空，或已分解到规定的分解精度为止。236720131375具有子孙的节点具有子孙的节点(P)(P)空节点空节点(E)(E)实节点实节点(F)(F)37北大计算机系多

19、媒体与人机交互分解表示-八叉树表示n优点n可以表示任何物体，且形体表示的数据结构简单n简化了形体的集合运算。只需同时遍历参加集合运算的两形体相应的八叉树，无需进行复杂的求交运算。n简化了隐藏线（或面）的消除，因为在八叉树表示中，形体上各元素已按空间位置排成了一定的顺序。n分析算法适合于并行处理。n缺点n没有边界信息，不适于图形显示n对物体进行几何变换困难n是物体的非精确表示n占用大量存储。实际上，八叉树表示是以存储空间换取算法的效率38北大计算机系多媒体与人机交互分解表示-线性八叉树表示线性八叉树：用一可变长度的一维数组来存储一棵八叉树。数组中仅存储八叉树的性质为FULL的终端结点。并用一个八

20、进制数表示该结点在八叉树中的位置。编码方式为：Q1Q2Qm,其中Q1表示该结点所属的一级父结点的编号（0-7），以此类推。例右图为：1X,30X,31X,323X,33X236720131375具有子孙的节点具有子孙的节点(P)(P)空节点空节点(E)(E)实节点实节点(F)(F)39北大计算机系多媒体与人机交互分解表示-单元分解表示n单元分解表示n对空间位置枚举表示的空间分割方法作了改进：单一体素 多种体素n三种空间分割方法的比较n空间位置枚举表示-同样大小立方体粘合在一起表示物体n八叉树表示-不同大小的立方体粘合在一起表示物体n单元分解表示-多种体素粘合在一起表示物体40北大计算机系多媒体

21、与人机交互分解表示-单元分解表示n优点n表示简单n容易实现几何变换n基本体素可以按需选择，表示范围较广n可以精确表示物体n缺点n物体的表示不唯一n物体的有效性难以保证41北大计算机系多媒体与人机交互构造表示n扫描表示n构造实体几何表示（CSG）n特征表示42北大计算机系多媒体与人机交互构造表示-推移表示n将物体A沿着轨迹P推移得到物体B，称B为sweep体n平移sweep-将一个二维区域沿着一个矢量方向推移43北大计算机系多媒体与人机交互构造表示-推移表示n旋转sweep-将一个二维区域绕旋转轴旋转一周44北大计算机系多媒体与人机交互n 三维形体也能在空间通过扫描变换生成新的形体：如左图，一个

22、圆柱体按指定方向在长方体上运动生成新的形体，这个过程犹如长方体与运动者的圆柱体不断的作差运算操作。有时经过扫描变换所生成的形体可能会出现维数不一致问题。构造表示构造表示-推移表示推移表示扫描线方向扫描线方向U U45北大计算机系多媒体与人机交互l构造表示-推移表示n广义sweepn任意物体沿着任意轨迹推移n推移过程中物体可以变形46北大计算机系多媒体与人机交互构造表示-推移表示n优点n表示简单、直观n适合做图形输入手段n缺点n作几何变换困难n对几何运算不封闭n用扫描变换产生的形体可能出现维数不一致的问题。n扫描方法不能直接获取形体的边界信息，表示形体的覆盖域非常有限。47北大计算机系多媒体与人

23、机交互构造表示-构造实体几何表示(CSG).通过对体素定义运算而得到新的形体的一种表示方法。体素可以是立方体、圆柱、圆锥等，也可以是半空间，其运算为变换或正则集合运算并、交、差。CSG表示可以看成是一棵有序的二叉树。n其终端节点或是体素、或是形体变换参数。n非终端结点或是正则的集合运算，或是变换（平移和/或旋转）操作，这种运算或变换只对其紧接着的子结点（子形体）起作用。48北大计算机系多媒体与人机交互构造表示-构造实体几何表示(CSG)49北大计算机系多媒体与人机交互构造表示-构造实体几何表示(CSG)nCSG树是无二义性的，但不是唯一的.CSG表示的优点：n数据结构比较简单，数据量比较小，内

24、部数据的管理比较容易；n物体的有效性自动得到保证；nCSG方法表示的形体的形状，比较容易修改。50北大计算机系多媒体与人机交互构造表示-构造实体几何表示(CSG)CSG表示的缺点：n对形体的表示受体素的种类和对体素操作的种类的限制，也就是说，CSG方法表示形体的覆盖域有较大的局限性。n对形体的局部操作不易实现，例如，不能对基本体素的交线倒圆角；n由于形体的边界几何元素（点、边、面）是隐含地表示在CSG中，故显示与绘制CSG表示的形体需要较长的时间。n表示不唯一 51北大计算机系多媒体与人机交互构造表示-特征表示n用一组特征参数表示一组类似的物体n特征包括形状特征、材料特征等n适用于工业上标准件

25、的表示52北大计算机系多媒体与人机交互构造表示-特征表示n从应用层来定义形体，因而可以较好的表达设计者的意图。从功能上可分为形状、精度、材料和技术特征。n特征是面向应用、面向用户的。特征模型的表示仍然要通过传统的几何造型系统来实现。不同的应用领域，具有不同的应用特征。n在几何造型系统中，根据特征的参数我们并不能直接得到特征的几何元素信息，而在对特征及在特征之间进行操作时需要这些信息。n特征方法表示形体的覆盖域受限于特征的种类。53北大计算机系多媒体与人机交互构造表示的特点n构造表示的特点：n构造表示通常具有不便于直接获取形体几何元素的信息、覆盖域有限等缺点，n但是，便于用户输入形体，在CAD/

26、CAM系统中，通常作为辅助表示方法。54北大计算机系多媒体与人机交互边界表示n边界表示（BR表示或BRep表示）n按照体面环边点的层次，详细记录了构成形体的所有几何元素的几何信息及其相互连接的拓扑关系。n边界表示的一个重要特点是在该表示法中，描述形体的信息包括几何信息（Geometry）和拓扑信息（Topology）两个方面。n拓扑信息描述形体上的顶点、边、面的连接关系，拓扑信息形成物体边界表示的“骨架”。n形体的几何信息犹如附着在“骨架”上的肌肉。55北大计算机系多媒体与人机交互边界表示n边界模型表达形体的基本拓扑实体包括：n1.顶点n2.边。边有方向，它由起始顶点和终止顶点来界定。边的形状

27、（Curve）由边的几何信息来表示，可以是直线或曲线，曲线边可用一系列控制点或型值点来描述，也可用显式、隐式或参数方程来描述。56北大计算机系多媒体与人机交互边界表示n3.环。环（Loop）是有序、有向边（Edge）组成的封闭边界。环有方向、内外之分，外环边通常按逆时针方向排序，内环边通常按顺时针方向排序。n4.面。面（Face）由一个外环和若干个内环（可以没有内环）来表示，内环完全在外环之内。n若一个面的外法矢向外，称为正向面；反之，称为反向面。57北大计算机系多媒体与人机交互边界表示n面的形状可以是平面或曲面。平面可用平面方程来描述，曲面可用控制多边形或型值点来描述，也可用曲面方程（隐式、

28、显式或参数形式）来描述。对于参数曲面，通常在其二维参数域上定义环，这样就可由一些二维的有向边来表示环，集合运算中对面的分割也可在二维参数域上进行。n5.体。体（Body）是面的并集。58北大计算机系多媒体与人机交互边界表示n边界表示模型是一种采用描述形体表面的方法来描述的几何表示模型。一个形体一般可以通过其边界拆成一些有界的“面”或“小片”的子集来表示，而每一个面又可以通过其边界的边和顶点来表示。若面的表示无二义性，则其边界表示模型也无二义性，但通常不一定只有唯一的表示。59北大计算机系多媒体与人机交互边界表示的数据结构n边界表示法的数据结构有四种方法：以面为基础、以顶点为基础、以边为基础和翼

29、边结构；n以面为基础的数据结构以面为基础的数据结构n以面为基础，按照体、面、顶点坐标的树结构层次组织元素数据；如n面 顶点坐标nF1 (X1Y1Z1,X2Y2Z2,X3Y3Z3,X4Y4Z4)nF2 (X1Y1Z1,X2Y2Z2,X6Y6Z6,X5Y5Z5)n.n其中顶点按照外观顺时针顺序；60北大计算机系多媒体与人机交互边界表示的数据结构n2 2以顶点为基础的数据结构以顶点为基础的数据结构n以顶点/坐标和面/顶点序列两张关系表表示，如：n顶点 坐标 面 顶点序列nV1 X1Y1Z1 F1 V1V2V3V4n.n3.3.以边为基础的数据结构以边为基础的数据结构n以边/顶点，顶点/坐标，面/边三

30、张关系表表示；61北大计算机系多媒体与人机交互边界表示模型n四棱椎边界表示的例子如右，由4个面组成，且这种表示可以看作是含有体、面、边、顶点为节点的有向图n四棱椎边界表示也可以基于边界的三角形分解，即把形体的边界拆成一些互不重叠的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱四棱柱面节点面节点边节点边节点顶点坐标顶点坐标f1f2f3.e1e2e3e4.v1v2v3.(x1,y1,z1)组合组合结构结构坐标坐标信息信息.62北大计算机系多媒体与人机交互边界表示的数据结构-翼边数据结构n翼边数据结构：在1972年，由美国斯坦福大学Baumgart作为多面体的表示模式提出。n

31、它用指针记录了每一边的两个邻面（即左外环和右外环）、两个顶点、两侧各自相邻的两个邻边（即左上边、左下边、右上边和右下边），用这一数据结构表示多面体模型是完备的，但它不能表示带有精确曲面边界的实体。63北大计算机系多媒体与人机交互边界表示的数据结构-翼边数据结构n翼边结构由四种结点Solid,Face,edge和Vertex组成的，各结点描述如下：nn Solid 构成引用的根节点。n在任意时刻，会存在几个数据结构引用；为了存取其中的任何一个，需要指向其Solid节点的指针。通过指向三个双向链表的指针，Solid 节点给出对该模型的面、边和顶点的访问。所有实体被链接到一个双向链表中，这个表通过指

32、向该表的后继和前趋实体的指针来实现的。具体包括：n 64北大计算机系多媒体与人机交互边界表示的数据结构-翼边数据结构nSolid ID;n 指向face的链表指针；n 指向edge的链表指针；n 指向vertex的链表指针；65北大计算机系多媒体与人机交互边界表示的数据结构-翼边数据结构nFace 表示多面体的一个小平面,包括：nFace ID；n指向face的链表首元素的指针；n 指向face的下一元素的指针；n66北大计算机系多媒体与人机交互边界表示的数据结构-翼边数据结构nEdge 由Edge节点构成，是整个数据结构的核心，每个Edge结点代表一条边，包括：nEdge ID;nEdge的

33、起始顶点指针；nEdge的终止顶点指针；nEdge的右邻面的指针；nEdge的左邻面的指针；nEdge的右方向向前邻边指针；nEdge的右方向向后邻边指针；nEdge的左方向向前邻边指针；nEdge的左方向向后邻边指针；n67北大计算机系多媒体与人机交互边界表示的数据结构-翼边数据结构nVertex 由vertex节点构成，包括：nVertex ID;n顶点坐标(x,y,z);n指向与该vertex相连的第一条边指针；n指向下一个Vertex结点指针；n68北大计算机系多媒体与人机交互边界表示的数据结构-半边数据结构n半边数据结构，是在80年代提出的，作为一种多面体的表示方法。在构成多面体的三

34、要素（顶点、边、面）中，半边数据结构以边为核心。一条边表示成拓扑意义上方向相反的两条“半边”，所以称为半边数据结构。n其中各节点的数据结构及含义如下：69北大计算机系多媒体与人机交互边界表示的数据结构-半边数据结构ntypedef float vector4;ntypedef short ID;ntypedef struct solid Solid;ntypedef struct face Face;ntypedef struct loop Loop;ntypedef struct edge Edge;ntypedef struct halfedge HalfEdge;ntypedef str

35、uct vertex Vertex;70北大计算机系多媒体与人机交互边界表示的数据结构-半边数据结构n多面体struct solid ID solidno;/多面体序号 Face*sfaces;/指向多面体的面；Edge*sedges;/指向多面体的边；Vertex*sverts;/指向多面体的顶点 Solid*nexts;/指向后一个多面体 Solid*prevs;/指向前一个多面体；71北大计算机系多媒体与人机交互边界表示的数据结构-半边数据结构n面Struct face ID faceno;/面序号 Solid*fsolid;/指向该面所属的多面体 Loop*floops;/指向构成该面

36、的环 Vector feq;/平面方程 Face*prevf;/指向前一个面；Face*nextf;/指向后一个面；72北大计算机系多媒体与人机交互边界表示的数据结构-半边数据结构n环 struct loopnn HalfEdge*ledge;/指向构成环的半边n Face*lface;/指向该环所属的面n Loop*prevl;/指向前一个环n Loop*nextl;/指向后一个环nn 73北大计算机系多媒体与人机交互边界表示的数据结构-半边数据结构n边 struct edge nn ID edgeno;/边的序号n HalfEdge*he1;/指向左半边n HalfEdge*he2;/指向

37、右半边n Edge*preve;/指向前一条边n Edge*nexte;/指向后一条边n74北大计算机系多媒体与人机交互边界表示的数据结构-半边数据结构n半边 struct halfedgenn Edge*edge;/指向半边的父边n Vertex*vtx;/指向半边的起始顶点n Loop*wloop;/指向半边所属的环n HalEdge*prv;/指向前一条半边n HalfEdge*nxt;/指向后一条半边n75北大计算机系多媒体与人机交互边界表示的数据结构-半边数据结构n顶点 struct vertex n n ID vertexno;/顶点序号n HalfEdge*vedge;/指向以该

38、顶点为起 点的半边n Vector vcoord;/顶点坐标n Vertex*nextv;/指向前一个顶点n Vertex*prevv;/指向后一个顶点n76北大计算机系多媒体与人机交互欧拉运算和正则集合运算n在边界表示法中，可以定义一系列运算来构造或修改三维实体，常用的这类运算有：n欧拉运算n正则集合运算77北大计算机系多媒体与人机交互欧拉运算欧拉运算是三维物体边界表示数据结构的生成操作。运用欧拉运算，可以正确、有效构建三维物体边界表示中的所有拓扑元素和拓扑关系。该运算之所以称为欧拉运算，是因为每一种运算所构建的拓扑元素和拓扑关系均要满足欧拉公式。78北大计算机系多媒体与人机交互欧拉运算n欧

39、拉公式V：顶点数E：棱线数F：面数n凡是满足欧拉公式的形体n均称为欧拉形体n欧拉公式是简单多面体n的必要条件。n附加条件：每边连接两个顶点n每条边只被两个面共享等来保证有效性V-e+f=279北大计算机系多媒体与人机交互欧拉运算n广义欧拉公式V-e+f-r=2(s-h)V：顶点数，E：棱线数，F：面数r:多面体表面上孔的个数s:相互分离的多面体数h:贯穿多面体的孔洞个数80北大计算机系多媒体与人机交互欧拉运算n若将广义欧拉公式n中的v,e,f,h,r,s分别看作独立的坐标变量，则上式在六维空间中定义了一张平面（平面是五维的），该平面通过原点。n由于各坐标变量的取值只能是非负的整数，所以上式实际

40、上对应了一张五维平面上的网格，每个多面体都对应一个网格点。但并不是每个网格都对应一个有效的多面体（只是必要条件）。如果要构造的多面体对应的网格点的坐标是（v,e,f,h,r,s），那么构造该实体的过程就是从原点开始沿网格一步一步向这个坐标点前进的过程。由于网格上的每点都满足欧拉公式，最后的多面体也必然满足它。V-e+f-r=2(s-h)81北大计算机系多媒体与人机交互欧拉运算n前进的“走法”是多种多样的，因为只有五个自由变量，所以只需五种基本走法就可以了。要求：每一步至多只能使某一坐标变量增（减）一个单位。每一步行走都有明显的几何意义。n欧拉运算是对形体进行增加，删除点、边、面而生成的一个新的

41、欧拉形的处理。最基本的五种欧拉运算是：n增加一条边和一个顶点；n增加一个面和一条边；n增加一条边,一个面和一个顶点；n增加一条边和一个顶点；n增加一条边,且删除一个孔穴。82北大计算机系多媒体与人机交互欧拉运算n相应的五种补运算是：n删除一条边和一个顶点；n删除一个面和一条顶点；n删除一个体,一个面和一个顶点；n删除一个孔洞和一个体；n删除一条边,且增加一个孔穴；n任何一种欧拉形体(或欧拉运算)都可以用最基本的欧拉运算的现行组合来表示。用最基本的欧拉运算操作生成的形体必定是一个欧拉形体。83北大计算机系多媒体与人机交互正则集合运算通过对边界表示的物体做正则集合运算可以构造新的边界表示的物体。对

42、具有平面边界、曲面边界的物体进行集合运算的算法有很多，算法的大致步骤如下：(1)预检查两物体是否相交 第一步：计算两个待求交物体的包围盒，若两包围盒不相交，则两物体不相交，正则集合运算结束，否则进行下一层。第二步：计算两物体每一个表面片的包围盒，当某个面片的包围盒与另一物体的包围盒相交时，将该面片与另一物体的所有表面片一一求交，否则该面片与另一物体的所有表面片都无交。同样，只有在用边界盒法无法判断时才进行求交计算，从而避免许多不必要的复杂的求交计算。84北大计算机系多媒体与人机交互正则集合运算(2)计算两物体各表面之间的交线。由于物体表面均为有界表面，因此物体表面之间的交线是有界的直线或曲线。

43、计算两物体表面之间的交线的一般步骤如下 a.基于两相交表面的方程，建立交线的方程，确定出初始交线。初始交线可能为无界。b.分别确定初始交线位于两相交表面内部的部分。c.计算位于两相交表面内部的两相交区段的重叠部分，即为两相交表面之间的真正交线。85北大计算机系多媒体与人机交互(3)对物体的表面进行分类 两物体之间的交线将它们的表面分割成两部分，其中一部分落在拼合体的表面上，形成新的边界，另一部分位于拼合体内或拼合体外，应在集合运算最后一步予以删除。(4)建立结果物体的边界表示。正则集合运算86北大计算机系多媒体与人机交互边界表示nBrep表示覆盖域大，原则上能表示所有的形体，而且易于支持形体的

44、特征表示等，Brep表示已成为当前CAD/CAM系统的主要表示方法。nBrep表示的优点是：n表示形体的点、边、面等几何元素是显式表示的，使得绘制Brep表示的形体的速度较快，而且比较容易确定几何元素间的连接关系；n容易支持对物体的各种局部操作，比如进行倒角。n便于在数据结构上附加各种非几何信息，如精度、表面粗糙度等。87北大计算机系多媒体与人机交互边界表示nBrep表示的缺点是：n数据结构复杂，需要大量的存储空间，维护内部数据结构的程序比较复杂；nBrep表示不一定对应一个有效形体，通常运用欧拉操作来保证Brep表示形体的有效性、正则性等。88北大计算机系多媒体与人机交互各种表示方法的比较n

45、精确性：能否精确的表示实体。特征表示-能够精确表示一个实体。构造实体几何表示-依赖于它所采用的基本体素，如果基本体素足够丰富，则能精确描述较大范围内的实体。边界表示-如果以多面体表示实体，则仅是一种近似表示；若允许曲面边界，则可以精确表示实体。推移表示-与边界表示类似。空间分割表示-近似表示一个实体。89北大计算机系多媒体与人机交互各种表示方法的比较n表示域：指一种表示法所能表示的实体的范围。表示域越大，表示能力越强。特征表示法、推移表示法：表示能力有限空间分割表示法：可以表示任何实体。边界表示法：理论上说，可以表示所有实体。但若将边界表示法中的边界限制在某个范围之内（如平面多边形），则表示能

46、力降低。实体构造表示法：依赖其基本体素的范围。90北大计算机系多媒体与人机交互各种表示方法的比较n唯一性：实体的表示形式唯一。只有空间位置枚举方法和八叉树具有唯一性。91北大计算机系多媒体与人机交互各种表示方法的比较n封闭性：若其表示域内的实体经过某种运算（如正则集合运算，几何变换）后，结果实体仍然落在表示域之内。特征表示：实体之间不能进行集合运算。简单推移表示，单元分解表示：不封闭。空间位置枚举表示，八叉树表示，CSG树表示封闭。边界表示虽然对正则集合运算不封闭，但可以附加约束条件避免。92北大计算机系多媒体与人机交互各种表示方法的比较n有效性：通常，边界表示（包括推移表示）物体的有效性难以

47、检验。特征表示的物体有效性自动得到保证。其它表示方法的有效性验证也比较简单。93北大计算机系多媒体与人机交互各种表示方法的比较n简洁性：空间分割表示：占用空间大特征表示、推移表示、CSG树表示较简洁。边界表示介于其间。94北大计算机系多媒体与人机交互各种表示方法的比较n输入：特征表示、推移表示、CSG树表示和单元分解表示都是面向用户的，只需输入少量参数，即可生成所需实体。空间位置枚举和八叉树表示很难由用户直接建立，一般都由其它表示形式转化过来。若采用边界表示作为输入手段，则一方面用户能方便的控制实体的形状，另一方面，需输入大量数据，且数据一致性很难保证。95北大计算机系多媒体与人机交互各种表示

48、方法的比较n输出：实体造型的输出包括图形、计算机辅助制造系统进行数控加工所需的数据以及实体的性质（重量、体积等）。图形显示和数控加工主要要求实体的边界信息，所以边界表示较好。若需实体性质等方面的计算，则空间分割表示、CSG树表示更好。96北大计算机系多媒体与人机交互模型的考虑n模型的考虑必须考虑以下一些问题：n根据形体边界给定的信息，是否能自动的获取形体的几何特征？n如何确定对形体操作数据的有效性？n形体的表示模型是否唯一？不同的表示模型是否可以转换？是否最佳表示模型？n对于几何造型系统来说，按照不同的目的可以采用不同的最佳表示模型。97北大计算机系多媒体与人机交互不规则形体的建模方法n迭代函

49、数系统n基于文法的模型n粒子系统n动力系统98北大计算机系多媒体与人机交互L系统n由生物学家Lindenmayer创立n基本思想：n用文法表示植物的拓扑结构n通过图形学方法生成逼真的画面nDOL系统（确定的上下文无关的L系统）n定义为三元组，其中V-表示字母集合V*-表示V上所有单词的集合w-是一个非空单词，称为公理P-产生式集合 ，使得如果没有明显的产生式，则令99北大计算机系多媒体与人机交互赠送精美图标1、字体安装与、字体安装与设置置如果您对PPT模板中的字体风格不满意，可进行批量替换，一次性更改各页面字体。1.在“开始”选项卡中，点击“替换”按钮右侧箭头，选择“替换字体”。（如下图）2.

50、在图“替换”下拉列表中选择要更改字体。（如下图）3.在“替换为”下拉列表中选择替换字体。4.点击“替换”按钮，完成。1012、替、替换模板中的模板中的图片片模板中的图片展示页面，您可以根据需要替换这些图片，下面介绍两种替换方法。方法一：更改图片方法一：更改图片1.选中模版中的图片（有些图片与其他对象进行了组合，选择时一定要选中图片 本身，而不是组合）。2.单击鼠标右键，选择“更改图片”，选择要替换的图片。（如下图）注意：注意：为防止替换图片发生变形，请使用与原图长宽比例相同的图片。101PPT放映设置PPT放映场合不同，放映的要求也不同，下面将例举几种常用的放映设置方式。让让PPT停止自动播放停止自动播放1.单击”幻灯片放映”选项卡，去除“使用计时”选项即可。让让PPT进行循环播放进行循环播放1.单击”幻灯片放映”选项卡中的“设置幻灯片放映”，在弹出对话框中勾选“循 环放映，按ESC键终止”。102