第4章 图形的表示与数据结构1

第四章图形的表示与数据结构几何造型技术不规则形体的表示技术提出问题•为什么要学习几何造型技术？–什么是几何造型：计算机几何造型就是用计算机系统来表示、控制、分析和输出二维和三维形体。2提出问题•三维图形在科学研究和工程技术中有着广泛的应用。–可视化的表达设计作品，是计算机辅助设计（CAD）、计算机辅助制造（CAM）和计算机集成制造系统（CIMS）的核心技术。–在三维GIS中，几何造型是对建筑物、地下矿体、移动目标等三维形体进行建模表示的重要方法。3几何造型可以进行–形体输入，即把形体从用户格式转换成计算机内部格式；–图形数据的存储和管理；–图形控制，如对形体进行平移、缩放、旋转等几何变换；4几何造型可以进行–图形修改，如应用集合运算、欧拉运算、有理B样条操作及其交互手段实现对形体局部或整体修改；–图形分析，如形体的容差分析，物质特性分析等；–图形显示输出，如消隐、光照、颜色的控制等；5•基本概念•实体•三维形体的表示•规则实体的表示方法64.1基本概念•4.1.1几何元素–在计算机中完整的形体定义一般为六层拓扑结构，首先介绍在三维空间中基本术语的定义体(object)外壳(shell)面(face)环(loop)边(loop)顶点(vertex)曲线和直线方程点的几何坐标4.1基本概念7•体和外壳–由封闭表面围成的有效空间称为体；一个形体Q是R3空间中非空、有界的封闭子集。其边界（记为∂Q）是有限个面的并集。–外壳是形体的最大边界。一个单位立方体可定义为：{(x,y,z)∈R3|0≤x≤1,0≤y≤1,0≤z≤1}其中一个表面可表示为：{(1,y,z)∈R3|0≤y≤1,0≤z≤1}xzy4.1基本概念8•体–必须注意：并没有规定形体必须是一个连续的封闭集合；–目的是用这样的定义来扩大几何造型的域，使得形体可以由不连续的体素，或是仅有某些部分相交的形体组成。xzy4.1基本概念9•面–R3中非空、连续、共平面且封闭的子集称为面F，其边界(记为∂F)是有限条线段的并集，Pt表示含有F的唯一平面。面是形体表面的一部分，且具有方向性.FPt4.1基本概念10•环–由有序、有向边组成的面的封闭边界称为环;–环中任意边都不能自交，相邻两条边共享一个端点;–环又分为内环和外环:内环是在已知面中的内孔，其边按顺时针方向。外环是已知面的最大外边界的环，其边按逆时针方向，按定义，在面上沿着边的方向前进，面的内部始终在走向的左侧。4.1基本概念11•边–形体内两个相邻面的交界称为边，一条边是两个邻面（正则形体情况下）或者多个邻面（非正则形体情况下）的交界。两个端点确定一条边，这两个端点分别称为该边的起点和终点。4.1基本概念12–假设Q是一个形体，E(Q)是形体边的集合，V(Q)是形体上顶点的集合，则在∂Q(形体的边界)中E(Q)是满足下列条件的所有线段的集合：•边e的两个端点属于V(Q)；•边e中没有一个内部点属于V(Q)；•边e上每个点，都有两个或多个不同的面f，使得边e∈fi∩fj；•形体Q的边框线WF(Q)是由有序对(V(Q),E(Q))所组成的。4.1基本概念13•点–点是0维几何元素，分端点、交点、切点和孤立点等。–在自由曲线面的描述中常用三种类型的点•控制点、型值点、插值点4.1基本概念14•客观存在的三维形体具有这样一些性质：–刚性：必须具有一定的形状–维数的一致性：三维，不能悬挂–占据有限的空间–边界的确定性：可以确定外部和内部–封闭性•三维空间中的物体是一个内部连通的三维点集，是由其内部的点集及紧紧包着这些点的表面组成的。4.1基本概念15•4.1.2几何信息和拓扑信息图形信息本身分为几何信息和非几何信息–图形对象及构成它的点、线、面的位置、相互间关系和几何尺寸等都是几何信息；–表示图形对象的线型、颜色、亮度以及供模拟、分析用的质量、比重、体积等数据，是有关对象的非几何信息。4.1基本概念16几何信息又可以进一步分为包括：（欧氏）几何信息：形体在欧氏空间中的位置和大小；拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。4.1基本概念171、几何信息(1)几何信息的数学表示：点线面的公式(2)几何分量之间的相互关系321fff点vvv12vvv123ee12ff12面fee12边e图4-2形体几何分量间的相互关系4.1基本概念182、拓扑信息：平面立体的几何分量之间一共有九种拓扑关系4.1基本概念19面相邻性f:{f}面-顶点包含性f:{v}面-边包含性f:{e}顶点—面相邻性v:{f}顶点相邻性v:{v}顶点-边相邻性v:{e}边-面相邻性e:{f}边-顶点包含性e:{v}边相邻性e:{e:}fffeeffffvevvveeevveffevvvfeevveeee4.1基本概念20•根据图形几何信息和拓扑信息状态定义两类运动–刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。–拓扑运动：形体作弹性运动，即在拓扑关系中，对图形可以随意的伸张扭曲。但图上各点之间的连接、连通等关系不能改变。拓扑运动前后的形体具有拓扑等价的关系。4.1基本概念21•4.1.3坐标系的分类：用户坐标系建模坐标系观察坐标系设备坐标系规格化的设备坐标系坐标系直角坐标系仿射坐标系圆柱坐标系球坐标系极坐标系4.1基本概念22•4.2.1利用正则集定义实体－－使得实体可计算几个预备定义：–点的邻域：如果P是点集S的一个元素，那么点P的以R（R0）为半径的邻域指的是围绕点P的半径为R的小球（二维情况下为小圆）。–内点为点集中的这样一些点，它们在实体内部具有完全包含于该点集的充分小的邻域。–边界点：不具有内点性质的实体上的点集4.2实体的定义23•点集的正则运算：A是一个点集，定义点集的正则运算如下：–i：取内点运算–c:取闭包运算：求给定点集的最小封闭边界–正则运算r：–i·A：A的全体内点组成的集合，称为A的内部–c·i·A：为对A的内部取闭包的运算，即取i·A与其边界点的并集。–正则运算即为先对物体取内点再取闭包的运算4.2实体的定义AicAr24•正则点集–一个点集A经过正则运算得到的结果称为正则点集。A的正则点集为r·A–如果A=r·A,则A为正则点集•正则运算的意义：4.2实体的定义(a)带有孤立点和边的二维点集A(b)内点集合i·A(c)正则点集c·i·A25•二维流形（manifold）–指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的邻域，该邻域与平面上的一个圆盘拓扑等价4.2实体的定义(a)二维流形(b)非二维流形26实体–定义：对于一个占据有限空间的正则形体，如果其表面为二维流形，则该正则形体为实体。–特征•一个正则点集•表面是二维流形不是实体4.2实体的定义27•4.2.2正则集合运算为什么需要正则运算？–普通的集合运算会产生无效物体–正则集合运算是构造复杂物体的有效方法4.2实体的定义进行相交运算普通A∩B正则A∩B28•正则集合运算–把能够产生正则形体的集合运算称为正则集合运算–集合运算（并、交、差）是构造形体的基本方法。正则形体经过普通集合运算后，可能会产生悬边、悬面等低于三维的形体。–在引入正则形体概念的同时，一并定义了正则集合运算的概念。正则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面等。4.2实体的定义29•正则运算用于实体操作–分类函数：若给定一个正则形体S以及一个有界面G，则G相对于S的分类函数可为：C(S,G)={GinS,GoutS,GonS}其中，4.2实体的定义}Sip,Gpp{SinGi·S表示实体内部c·S表示实体外部}Sp,Gpp{SoutGb·S表示实体边界}Sbp,Gpp{SonG30用-G表示有界面G的反向面。即，如果有界面G在P点的法向为NP(G)，则有界面-G在P点的法向就是-NP(G)。于是：GonS={Gshared(b·S),Gshared(-b·S)}其中，4.2实体的定义})Sb(N)G(N,Sbp,Gpp{ppS)(bGshared})Sb(N)G(N,Sbp,Gpp{ppS)(-bGshared31–则G相对于S的分类函数C(S,G)可进一步表达为：C(S,G)={GinS,GoutS,GShared(b.S),GShared(-b.S)}4.2实体的定义324.2实体的定义B}bsharedAbA,inBbB,inA{bB)(Ab*B)}(b-sharedAbA),inB(b-B,outA{bB)-(Ab*正则并正则交正则差B}bsharedAbA,outBbB,outA{bB)(Ab*正则集合算子定义三个正则集合算子对边界面操作的表达式为取边界的结果表达式取边界的结果表达式取边界的结果表达式33B}bsharedAbA,outBbB,outA{bB)(Ab*AU*B的操作和结果34B}bsharedAbA,inBbB,inA{bB)(Ab*A∩*B的操作和结果35B)}(b-sharedAbA),inB(b-B,outA{bB)-(Ab*A－*B的操作和结果36