《三维形体的表示》由会员分享，可在线阅读，更多相关《三维形体的表示（96页珍藏版）》请在金锄头文库上搜索。
1、2017/8/14,浙江大学计算机学院,1,第八章 三维形体的表示,表示形体的两种模型实体的定义正则集合运算特征表示空间分割表示推移表示边界表示构造实体几何表示不规则形体的建模方法L系统,2017/8/14,浙江大学计算机学院,2,引 言,三维图形在科学研究和工程技术中有着广泛的应用。在CAD中，需要对所设计的作品从不同的角度进行审视。计算机几何造型就是用计算机系统来表示、控制、分析和输出三维形体。所以几何造型是计算机图形学中一个十分重要的应用领域，它是CAD/CAM和CIMS系统的核心技术，也是用来实现计算机辅助设计的基本手段。几何造型的功能：形体输入，即把形体从用户格式转换成计算机内部格式
2、；图形数据的存储和管理；图形控制，如对形体进行平移、缩放、旋转等几何变换；图形修改，如应用集合运算、欧拉运算、有理B样条操作及其交互手段实现对形体局部或整体修改；图形分析，如形体的容差分析，物质特性分析等；图形显示输出，如消隐、光照、颜色的控制等；询问形体的属性及其有关参数,2017/8/14,浙江大学计算机学院,3,形 体,在计算机中形体一般定义为六层拓扑结构，首先介绍在三维空间中基本术语的定义。,形体(object),外壳(shell),面(face),环(loop),边(loop),顶点(vertex),曲线和直线方程,点的 几何坐标,2017/8/14,浙江大学计算机学院,4,形 体,
3、体素具有有限个参数定义，且简单的连续封闭的形体称为体素，如长方体、圆柱体、圆锥、球、环等。半空间集合P|F(P)0成为半空间，其中P为R3中的一点，F为一个平面，当F=0时，表示一个平面，这个平面的半空间可以由F(P)=ax+by+cz+d定义的平面加上在平面某一侧的所有点组成。显然一个长方体可以看成是6个平面半空间的交。几何信息用来表示形体的几何性质和度量关系称为几何信息。拓扑信息用来表示形体之间的连接关系称为拓扑信息。,2017/8/14,浙江大学计算机学院,5,表示形体的两种模型,模型分类,2017/8/14,浙江大学计算机学院,6,表示形体的两种模型,数据模型完全以数据描述例如用以8个
4、顶点表示的立方体以中心点和半径表示的球以数据文件的形式存在包括-特征表示、空间分割表示、推移表示、边界表示、构造实体几何表示等进一步分为线框模型表面模型实体模型,2017/8/14,浙江大学计算机学院,7,线框模型,线框模型：将形体表示成一组轮廓线的集合。一般地，画出了形体的棱线与轮廓线就能唯一地表示出来。如图，八个顶点可以定义一个长方体，但还不足以识别它，如果定义了棱线，则无论如何放置长方体都能唯一地表示了。对于多面体由于其轮廓线和棱线通常是一致的，所以多面体的线模型更便于识别，且简单。,e12,v4,v8,s3,e2,e4,e6,e8,e2,e7,e11,e10,e9,e3,e1,v2,v
5、3,v1,v7,v5,v6,s2,s6,s5,s1,s4,2017/8/14,浙江大学计算机学院,8,线框模型,优点：简单、处理速度快缺点：1、对于非平面多面体，如圆柱、球等形体，其轮廓线随观察方向的改变而改变，无法用一组固定的轮廓线来表示它们。2、线框模型与形体之间不存在一一对应关系：它仅仅通过给定的轮廓线约束所表示形体的边界面，而在轮廓线之间的地方，形体的表面可以任意变化。3、没有形体的表面信息，不适于真实感显示，由此导致表示的形体可能产生二义性。,2017/8/14,浙江大学计算机学院,9,表面模型,表面模型将形体表示成一组表面的集合如果把线框模型中的棱线包围的部分定义为面，所形成的模型
6、便是表面模型。其数据结构是在线模型的基础上附加一些指针，有序地连接棱线。下图中表面编号表示第几个表面，表面特征表面是平面还是曲面。形体与其表面一一对应，适合于真实感显示,4,顶点个数,1,起始指针,0,表面特征,5,表面编号,1,4,0,4,3,0,3,2,0,2,1,连接指针,属性,顶点号,1,4,2,3,2,3,4,1,2017/8/14,浙江大学计算机学院,10,表面模型,缺点：不能有效的用来表示实体原因：1、表面模型中的所有面未必形成一个封闭的边界2、各个面的侧向没有明确定义，即不知道实体位于面的哪一侧,2017/8/14,浙江大学计算机学院,11,实体模型,实体模型用来描述实体，主要
7、用于CAD/CAM包含了描述一个实体所需的较多信息，如几何信息、拓扑信息，可以支持多种运算，如欧拉运算等。,2017/8/14,浙江大学计算机学院,12,表示形体的两种模型,过程模型以一个过程和相应的控制参数描述例如用一些控制参数和一个生成规则描述的植物以一个数据文件和一段代码的形式存在包括-粒子系统、L系统、迭代函数系统等,2017/8/14,浙江大学计算机学院,13,实体的定义,抽象带来的问题计算机中表示的物体是无效的不能够客观存在为什么要求客观存在CAD/CAM的需求什么是客观存在（有效）实体的定义具有一定的形状具有封闭的边界（表面)内部连通占据有限的空间经过运算后，仍然是有效的物体,2
8、017/8/14,浙江大学计算机学院,14,实体的定义,将三维物体看做一个点集，它由内点和边界点共同组成。内点：具有完全包含于该点集的充分小的邻域边界点：不具有内点性质的点集,2017/8/14,浙江大学计算机学院,15,实体的定义,A是一个点集，定义点集的正则运算如下：i：取内点运算c: 取闭包运算正则运算ri A：A的全体内点组成的集合，称为A的内部c i A为A的内部的闭包的运算，是i A与其边界点的并集。,2017/8/14,浙江大学计算机学院,16,实体的定义,正则点集 称为A的正则点集称A为正则点集，如果它满足问题：正则点集是实体？,2017/8/14,浙江大学计算机学院,17,实
9、体的定义-举例说明,阴影部分：物体的内部区域黑色部分：边界(a)图取内点-(b)图求闭包-(c)图正则运算：去除与物体维数不一致的悬挂部分或孤立部分。,2017/8/14,浙江大学计算机学院,18,实体的定义,实体的定义可计算的条件正则点集表面是二维流形二维流形其上任意一点存在充分小的领域与圆盘同构（存在连续的一一映射）,2017/8/14,浙江大学计算机学院,19,一些非正则形体的实例,一些非正则形体的实例,2017/8/14,浙江大学计算机学院,20,正则集合运算,为什么需要正则集合运算正则集合运算是构造复杂物体的有效方法普通的集合运算会产生无效物体(b):AB(c):普通AB(d)：正则
10、AB,2017/8/14,浙江大学计算机学院,21,正则集合运算,集合运算（并、交、差）是构造形体的基本方法。正则形体经过集合运算后，可能会产生悬边、悬面等低于三维的形体。Requicha在引入正则形体概念的同时，还定义了正则集合运算的概念。正则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面等。,2017/8/14,浙江大学计算机学院,22,正则集合运算,正则集合运算的定义正则并正则交正则差,2017/8/14,浙江大学计算机学院,23,任一实体S可以用它的边界bS和它的内部iS来表示，即 S=bS iS 由实体的定义可知，bS是封闭的，它将整个三维空间分成了三个区域： S的内部
11、iS , S的边界bS ,S的外部eS。边界bS与实体S是一一对应的。确定了边界，也就唯一确定了一个实体。 因此，为了求实体A，B的正则集合运算结果A op* B，只要求出其边界b（A op* B）即可。,正则集合运算,2017/8/14,浙江大学计算机学院,24,正则集合运算,考察A,B两物体的交所形成拼合体的边界，由于A,B为正则点集，它们均可表示为边界点与体内点的集合，即A=bA iA ; B=bB iB A物体的边界 bA可按其位于B物体内、B物体上、B物体外而分别表示为 bA = (bAiB)(bAbB) (bAeB) 同理，bB = (bBiA)(bBbA)(bBeA),A,201
12、7/8/14,浙江大学计算机学院,25,正则集合运算,其中bA bB = bB bA是A与B的公共边界，它可以分成两部分： （bA bB）同侧、 (bA bB)异侧(bA bB)同侧由这样一些边界构成：A、B位于边界的同侧(bA bB)异侧由这样一些边界构成：A、B位于边界的异侧,2017/8/14,浙江大学计算机学院,26,正则集合运算,对于A * B ，由交的定义可知：1）A、B两物体的边界位于对方内部的部分，即bA iB 和bB iA是b(A * B )的组成部分。2） A、B两物体的边界位于对方外部的部分，即bA eB 和bB eA不是b(A * B )的组成部分。3）对于A、B的重合
13、边界有： (bA bB)同侧属于b(A * B ); (bA bB)异侧不属于b(A * B ) 因此：b(A*B)=(bA iB) (bB iA)(bA bB)同侧,2017/8/14,浙江大学计算机学院,27,正则集合运算,同理：b(A*B)=(bA eB) (bB eA)(bAbB)同侧b(A*B)=(bA eB) (bB iA)(bAbB)异侧,2017/8/14,浙江大学计算机学院,28,形体表示模型,在实体模型的表示中，基本上可以分为分解表示、构造表示和边界表示三大类。1、分解表示将形体按某种规则分解为小的更易于描述的部分，每一小部分又可分为更小的部分，这种分解过程直至每一小部分都
14、能够直接描述为止。,2017/8/14,浙江大学计算机学院,29,分解表示-空间位置枚举表示,形体空间细分为小的均匀的立方体单元。用三维数组CIJK表示物体，数组中的元素与单位小立方体一一对应当CIJK = 1时，表示对应的小立方体被物体占据当CIJK = 0时，表示对应的小立方体没有被物体占据,2017/8/14,浙江大学计算机学院,30,分解表示-空间位置枚举表示,优点简单，可以表示任何物体容易实现物体间的交、并、差集合运算容易计算物体的整体性质，如体积等缺点占用大量的存储空间，如1024*1024*1024 = 1G bits物体的边界面没有显式的解析表达式，不适于图形显示对物体进行几何
15、变换困难，如非90度的旋转变换是物体的非精确表示,2017/8/14,浙江大学计算机学院,31,分解表示-八叉树表示,八叉树表示对空间位置枚举表示的空间分割方法作了改进：均匀分割 自适应分割八叉树建立过程,八叉树的根节点对应整个物体空间如果它完全被物体占据，将该节点标记为F(Full)，算法结束；如果它内部没有物体，将该节点标记为E(Empty)，算法结束；如果它被物体部分占据，将该节点标记为P(Partial)，并将它分割成8个子立方体，对每一个子立方体进行同样的处理,2017/8/14,浙江大学计算机学院,32,分解表示-八叉树表示,8叉树的表示应用三维形体的分解，它对一个外接立方体的形体进行前后、左右、上下等部分8个小立方体，如果小立方体单元为满或为空，表示该立方体完全在形体中或完全不在形体中，则其停止分解；对部分形体占有的小立方体需进一步分解为8个子立方体，直至所有小立方体单元要么全部满，要么全部空，或已分解到规定的分解精度为止。,2,3,6,7,2,0,1,3,1,3,7,5,
