第七章-三维实体的表示.ppt

第七章三维实体的表示,1,真实世界存在着千姿百态的物体，研究如何在建立恰当的模型表示这些物体的技术称为造型技术计算机图形学研究的重要内容之一。其中，实体造型技术关注表示实体的信息的完备性和可操作性，它是由于计算机辅助设计与制造的需要而发展起来的，现在已经广泛应用于各种造型系统中。,三维实体的表示,表示实体的方法空间分割表示法；由简单物体基本体素，通过粘合构造新的物体。（立方体，长方体，圆柱体等）单元分解表示，八叉树表示，特征表示法构造实体几何表示法；方法基本同上，将实体表示称基本体素的组合，采用更多的运算，如并、交、差等。边界表示法。通过描述构成实体边界的点、边、面来表示实体。推移表示法,2,3,实体的定义,实体造型中必须保证物体的有效性(客观存在)。真实世界中物体具有的性质具有一定的形状；具有确定的封闭的边界；是一个内部连通的三维点集；如果该物体分成了独立的几个部分，不妨将其看作多个物体。占据有限的空间，即体积有限；经过任意的运算(切割、粘合)，仍为有效物体；满足以上性质的物体，称为有效物体或实体。,4,实体的定义,从点集拓扑的角度给出实体的简洁定义将三维物体看作一个点集，它由内点及边界点共同组成。内点：具有完全包含于该点集的充分小邻域。边界点：指那些不具有这个性质的点集中的点。定义正则运算r如下：rA=ciA。其中，i为取内点运算，c为取闭包运算，A为一个点集。那么iA为A的全体内点组成的集合，称作A的内部(一个开集)。ciA为A的内部的闭包，是iA与其边界点的并集(一个闭集)。正则运算即为先对物体取内点再取闭包的运算。rA为A的正则点集。但正则点集未必是实体。,5,实体的定义,下图是带悬挂边与孤立点、边的二维物体，以此为例来说明正则运算的过程。二维流形：是指这样一些面，其上任一点都存在一个充分小的邻域，该领域与平面上的圆盘是同构的，即在该邻域与圆盘之间存在连续的一一映射。对于一个占据有限空间的正则点集，如果其表面是二维流形，则该正则点集是实体(有效物体)。这个描述中的条件在计算机中是可检测的。,6,正则集合运算,通过对简单实体做适当的运算来构造复杂实体是一个有效的方法。实体可看作点集，对实体进行的运算主要是集合运算。但是对两个实体做普通的集合运算并不能保证其结果仍是实体。如下，两个二维实体A、B求交：,7,正则集合运算,为了保证运算结果仍为实体，定义正则集合运算op*为：Aop*B=r(AopB)；其中op=是普通集合运算，r为正则运算，op*=正则交、正则并、正则差。(注意定义的含义),8,正则集合运算,计算机中正则集合运算的实现任意实体S可以用它的边界bS和内部iS来表示：由实体的定义可知，bS是封闭的，它将整个三维空间分成了三个区域(iS,bS,eS)。边界bS与实体S是一一对应的，确定了边界，也就唯一确定了一个实体。为了求实体A,B的正则运算结果Aop*B，只要求出其边界b(Aop*B)即可。我们有：,9,正则集合运算,10,下面来讨论A、B两实体正则交、正则并、正则差的边界构成。,通过类似的讨论，可以得到A，B正则并、正则差的边界表达式：,正则集合运算,11,实体表示方法,空间分割表示边界表示特征表示推移表示构造实体表示,12,实体表示方法空间分割表示,空间分割表示在此表示方法中，实体被分割表示为互不相交的粘合在一起的更基本的体素。基本体素的大小、位置、类型可以多种多样，但它们的一般形状比较简单。空间位置枚举表示二维平面，为表示图像，平面分割成大小相同、形状规则的像素，然后用像素的集合来表示图像，采用的数据结构是二维数组。推广到三维即是空间位置枚举表示法。选择一个包含物体的立方体作为考虑空间，将立方体划分成均匀的小立方体，建立一个三维数组CIJK。,13,实体表示方法空间分割表示,数组中的元素Cijk与左下角点坐标是(i,j,k)的小立方体对应。当该立方体被物体占据时，取Cijk的值为1，否则为0。这样数组C就唯一表示了包含于立方体之内的所有物体。其中为小立方体的边长。数组的大小取决于空间分辨()的大小和我们感兴趣的立方体空间的大小。优点：可以表示任何物体(通常情况下是近似表示)，容易实现物体的集合运算以及计算物体的体积等许多整数性质。缺点：没有明确给出物体的边界信息，不适于图形显示；占据的存储量非常大。,14,实体表示方法空间分割表示,八叉树表示此法对空间位置枚举法中的空间分割方法作了改进，即并非统一将物体所在的立方体空间均匀分成边长为的小立方体，而是对空间进行自适应划分，采用具有层次结构的八叉树表示物体。类似于二维图形的四叉树表示。对于四叉树表示，我们在一个包含二维图形区域的正方形区域中考虑问题，此正方形区域为四叉树的根节点，它可能处于三种状态：完全被图形覆盖(F)、部分被覆盖(P)或完全没有被覆盖(E)。若根节点处于状态F或E，则四叉树建立完毕；否则，将其分成四个小正方形区域，分别标0,1,2,3。,15,实体表示方法空间分割表示,这四个小正方形成为第一层子节点，对它们做类似根节点的处理，如此下去，直到建立图形的四叉树表示。对状态P的节点的分割层次根据实际需要予以指定。如图，一个空间自适应分割过程：,16,实体表示方法空间分割表示,建立物体的八叉树表示的过程与四叉树表示大体一样。此时，每个节点代表的是一个立方体，对它分割的结果产生八个子节点。编码是0到7。用八叉树表示实体，具有许多优点：容易实现实体之间的正则集合运算；容易计算实体的整体性质；容易实现隐藏线和隐藏面的消除。缺点：通常不能精确地表示一个实体，并且对八叉树表示的实体做任意的几何变换比较困难。如旋转角度为非90o倍数的旋转变换，放缩的比例非2的倍数的放缩变换。八叉树需要较大存储空间。,17,实体表示方法空间分割表示,减少所需存储空间的方法很多，最简单有效的是线性八叉树：用一个线性结构存储八叉树，在数组中仅仅存放八叉树中状态为F的节点。,18,实体表示方法单元分解表示,单元分解表示从另一角度对空间位置枚举表示做了改进。它以不同类型的基本体素(不是单一的立方体)通过粘合运算来构造新的实体。这些基本体素可以是任何简单实体，如圆柱、圆锥、多面体等。粘合运算使两个实体在边界面上相接触，但它们的内部并不相交。只要基本体素的类型足够多，单元分解表示法能表示范围相当广泛的物体。单元分解表示法不具有唯一性，即同一实体可具有多种表示形式。另外，此法所构造物体的有效性难以保证,19,实体表示方法边界表示,边界表示即通过描述实体的边界来表示一个实体的方法。边界与实体是一一对应的，定义了实体的边界，该实体就被唯一确定。边界可以是多边形或曲面片。通常，曲面片被近似地离散成多边形来处理。本节讨论多面体的边界表示。,20,实体表示方法边界表示,多面体及欧拉公式：平面多面体是指表面由平面多边形构成的三维体，其表面上的每条边被偶数个多边形共享。多面体表面具有二维流形的性质，即多面体的每条边只严格属于两个多边形。,21,实体表示方法边界表示,简单多面体是指与球拓扑同构的的多面体，可连续变换成一个球。它满足下面的欧拉公式：v-e+f=2其中v,e,f分别是多面体的顶点数、边数和面数。欧拉公式是一个多面体为简单多面体的必要但非充分条件。,22,实体表示方法边界表示,检验一个具有多边形表面的体是不是简单多面体，除了要验证欧拉公式外，还要附加一些条件，如每条边连接两个顶点，每条边只被两个面共享，每个顶点至少被三条边共享。如图所示的非简单多面体，满足广义欧拉公式：v-e+f-r=2(s-h)。其中r表示多面体表面上孔的个数，h为贯穿多面体的孔洞的个数，s为相互分离的多面体数。并且，广义欧拉公式仍是检查一个多边形表面的体是否为实体的必要条件。,23,实体表示方法边界表示,平面方程的计算构成平面多面体边界的是多边形。我们讨论求多边形所在平面的方程。平面方程表示为：其中，N=Nx,NyNz取作平面的单位法矢量，空间任意一点V到平面的距离为NV+d。当V落在平面的某一侧时，它的值为正，另一侧的值为负，落在平面上时为0。当多边形是三角形时，三个顶点唯一确定一个平面。其单位法向量为：,24,实体表示方法边界表示,将N和P0(或P1,P2)的坐标代入方程，可求出：这样，可求出要求的平面方程。当多边形的顶点多于3个时，它们不一定共面，此时，只有以一张与各个顶点距离之和最小的平面来近似表示它们。设多边形的顶点为Pi(xi,yi,zi)，则所求平面的单位法矢量为：其中，取Pn+1=P0。展开上式得到：,25,实体表示方法边界表示,边界表示的数据结构最简单的边界表示方法将多面体表示成其边界的一列多边形，每个多边形又由一列顶点坐标来表示。将顶点统一按一个方向(如逆时针或顺时针)排列。由于每个顶点属于多个多边形，在多边形中只保存各顶点的序号，将多面体的所有顶点存放在一个数组中。这里，边的信息是隐含的，即多边形顶点序列中相邻两个顶点构成一条边。,26,实体表示方法边界表示,边界表示的数据结构此法数据结构简单，但效率不高。如查找共享某条边的两个多边形，则需要遍历组成该多面体边界的所有多边形，才能确定哪两个多边形包含这条边。(原因：数据结构中包含多面体边界的拓扑信息不完整。),27,实体表示方法边界表示,几何信息指的是顶点、边、面的位置、大小、形状等几何数据。拓扑信息指的是顶点、边、面之间的连接关系。多面体的顶点、边、面之间的拓扑关系可用九中不同的形式描述：vv,ve,vf,ev,ee,ef,fv,fe,ff。每一种关系都可由其它关系通过适当的运算得到。,28,实体表示方法边界表示,在表示法中究竟采用哪种拓扑关系或哪几种关系的组合取决于边界表示所支持的各种运算以及存储空间的限制。数据结构中保存的拓扑关系越多，对多面体的操作越方便，但占用的存储空间也越大。拓扑关系的选择要合理折中。,29,实体表示方法边界表示,半边数据结构在构成多面体的三要素(顶点、边、面)中，此法以边为核心。为了方便表达拓扑关系，将一条边表示成拓扑意义上方向相反的两条半边，其结构如图。,30,实体表示方法边界表示,多面体的边界表示结构如图：,31,实体表示方法边界表示,半边数据结构类型solid,face,loop,edge,halfedge,vertex将在后面定义。对每种类型定义一个同类型的类名，分别分别是Solid,Face,Loop,Edge,Halfedge,Vertex，同时说明一个浮点数组vector4、一个短整型Id。后面对其分别进行介绍。,32,实体表示方法边界表示,多面体structsolidIdsolidno;Face*sfaces;Edge*sedges;Vertex*sverts;Solid*nexts;Solid*prves;多面体是数据结构最上层的节点，任何时候都可以通过连接各节点的双向指针遍历多面体边界的面、边、顶点等元素。,33,实体表示方法边界表示,面structfaceIdfaceno;solid*fsolid;Loop*floops;Vertexfeq;Face*nextf;Face*prvef;面结构表示多面体表面的一个平面多边形，该多边形所在的平面方程为feq0x+feq1y+feq2z+feq3=0边界由一系列环构成，floops指向其外环。,34,实体表示方法边界表示,环structloopHalfEdge*ledge;Face*lface;Loop*prevl;Loop*nextl;一个环由多条半边组成，环的走向一定。若规定外环逆时针，则内环顺时针。反之亦然。,35,实体表示方法边界表示,边structedgeIdedgeno;HalfEdge*he1;HalfEdge*he2;Edge*preve;Edge*nexte;一条边分为拓扑意义上方向相反的两条半边。在多面体中保存边的信息是为了方便对多面体以线框的形式进行显示处理。,36,实体表示方法边界表示,半边structhalfedgeEdge*edge;Vertex*vtx;Loop*wloop;HalfEdge*prv;HalfEdge*nxt;半边是整个数据结构的核心，一条条首尾相连的半边组成一个环，通过指针edge，可以访问与该半边同属一条边的另一半边。,37,实体表示方法边界表示,顶点structvertexId*vertexno;HalfEdge*vedgeVectorvcoord;Vertex*nextv;Vertex*prevv;顶点是构成多面体的最基本元素，它包括了多面体的所有几何信息，即顶点坐标vcoord。,38,实体表示方法边界表示,以半边数据结构为基础的多面体的边界表示包含了多种拓扑关系，如ve,ev,ef,等，可以方便地查找各元素之间的连接关系。例如，若要查找共享某条边的两个面，首先由指针he1,he2找到两条半边，再由半边的指针wloop找到所属的环，最后由环结构中的指针lface便能确定所求的面。这种表示中存储的信息量大，需要较多的存储空间，但却获得了较快的处理速度。在边界表示法中，可以定义一系列运算来构造或修改三维实体，常用的这类运算有欧拉运算，正则集合运算。,39,实体表示方法边界表示,欧拉运算将广义欧拉公式：v-e+f-r-2s+2h=0中的v,e,f,r,s,h看成独立的坐标变量，上式为六维空间的平面(过原点)，坐标变量为非负整数，对应为一张五维平面的网格，每个多面体对应一个网格点(并非每一网格点对应一个有效的多面体)。如果要构造的多面体对应的网格点坐标是(v,e,f,r,s,h)，那么构造该实体的过程就是从原点开始沿网格一步一步向这个坐标点前进的过程。由于网格上的每点满足上式，从而最终得到的多面体也必满足。这些走法多种多样。,40,(1)mvfs(s,v,f,x,y,z)：创建一个序号为s的多面体，它包含一个顶点v和一个面f，顶点v的坐标为(x,y,z)。,实体表示方法边界表示,上式有五个自由变量，故有五种基本走法。而多种多样的走法是五种基本走法的合成。最典型的是欧拉运算：,41,(2)mev(s,v1,v2,v3,v4,f1,f2,x,y,z)输入一个顶点v4，生成一条新边v1v4。使得原来围绕顶点v1的边中，v1v2的顶点变成以v4为顶点。当v2=v3,f1=f2时，该运算仅仅生成一条新边。,实体表示方法边界表示,42,(3)mef(s,f1,f2,v1,v2,v3,v4)连接面f1的两条边v1v2与v3v4的顶点v1与v3，生成一条新边，并将f1分成两个面f1和f2。其中，有向边v1v3所在的面为f2，有向边v3v1所在的面为f1。,实体表示方法边界表示,43,(4)kemr(s,f,v1,v2)删除连接v1与v2的边，生成一个新环。,(5)kfmrh(s,f1,f2)合并f1与f2，使得f2变成f1的一个内环(被删除)，由此产生一个新的通孔。,实体表示方法边界表示,44,以构造一个带孔的立方体为例说明欧拉运算，由点到边、由边到环、由环到面、由面到体一步一步来构造三维立体。如图,实体表示方法边界表示,45,mvfs(s0,v0,f0,x0,y0,z0);mev(s0,v0,v0,v0,v1,f0,f0,x1,y1,z1);mev(s0,v1,v0,v0,v2,f0,f0,x2,y2,z2);mev(s0,v2,v1,v1,v3,f0,f0,x3,y3,z3);mef(s0,f0,f1,v3,v2,v0,v1);,实体表示方法边界表示,46,mev(s0,v0,v3,v3,v4,f1,f1,x4,y4,z4);mev(s0,v4,v0,v0,v5,f1,f1,x5,y5,z5);mef(s0,f1,f2,v5,v4,v1,v2);,实体表示方法边界表示,47,mev(s0,v5,v4,v4,v6,f2,f2,x6,y6,z6);mef(s0,f2,f3,v6,v5,v2,v3);,f2:v2v6v5v1v2f3:v6v2v3v0v4v5v6,mev(s0,v6,v5,v5,v7,f3,f3,x7,y7,z7);mef(s0,f3,f4,v7,v6,v3,v0);mef(s0,f4,f5,v7,v3,v4,v5);,f3:v3v7v6v2v3f4:v7v3v0v4v5v6v7,f4:v4v7v3v0v4f5:v7v4v5v6v7,实体表示方法边界表示,48,实体表示方法边界表示,正则集合运算通过对边界表示的物体做正则集合运算可以构造新的边界表示的物体。对具有平面边界，曲面边界的物体进行集合运算的算法有很多，大致步骤如下：(1)预检查两个物体是否相交：物体表面求交运算计算量大，非常费时。如经过大量计算，物体表面并不相交。一般，采用包围盒技术加速，预检查两个物体是否相交。所谓包围盒，指的是包围物体的最小长方体(或任何简单形体如球、圆柱等)。如二维空间的三角形，其包围盒是矩形。,49,实体表示方法边界表示,包围盒在这里的应用分为两个层次：a.计算两个待求物体的包围盒，若包围盒无交，则物体不相交，正则集合运算结束，否则，进入下一层。b.计算两物体每一个表面片的包围盒，当某个面片的包围盒与另一物体的包围盒相交时，将该面片与另一物体的所有表面片一一求交，否则，该面片与另一物体的所有表面片都无交。采用此法预检查能分离出许多物体与物体或表面片与物体无交的情况，从而避免了许多不必要的复杂的求交计算。,50,实体表示方法边界表示,(2)计算物体表面之间的交线。平面多面体的处理(平面与平面求交)；曲面边界的处理，涉及到曲面片与曲面片的求交，一般有两种处理方法：a.解析求交：根据两曲面片的解析方程，建立交线的方程。b.离散求交：先将曲面片离散成一块块平面多边形，然后求出这些平面多边形间的交线，将它们连接起来近似表示两曲面间的交线。此算法计算简便，程序处理一致，但存在逼近误差，解的精度低。(3)对物体的表面分类。(4)建立结果物体的边界表示。,51,实体表示方法特征表示,特征表示用一组特征参数来定义一族类似的物体。特征从功能上分形状特征和材料特征。形状特征如体素、孔、半孔、槽等。材料特征如硬度、密度、热处理方法等。如，只考虑形状特征，一个圆柱或圆锥可用参数组(R,H)来定义，一个正n棱柱可用参数组(n,R,H)定义。特征表示适用于表示工业上定型的标准件。标准件既可以十分简单，也可以相当复杂。所有的标准件保存在一个数据库中，使用时，用户只要指定参数。特征表示面向用户，用户还可根据需要向数据库中增加新的体素类型。,52,实体表示方法推移表示,推移表示将物体A沿空间一条轨迹P推移时，A的轨迹定义了一个新的物体B，则物体B可以由物体A与轨迹P共同表示。这种表示法称为推移表示法。如A是一个二维的平面区域，轨迹是垂直于该平面的直线段，推移的结果得到一个柱体，这种简单推移表示方法叫平移sweep，由此得到的物体叫平移sweep体。如：正四棱柱、圆柱。如果将平移sweep进行推广：允许二维区域在推移的过程中大小可变，轨道可以不垂直于二维区域所在的平面。正方形区域沿任一方向推移得到一个平行六面体。若正方形沿轨迹向前推移时，其边长呈线性递减，得到的平移sweep体是四棱锥。,53,实体表示方法推移表示,旋转sweep通过将一个二维区域绕一个轴旋转而构成新的物体。如直角三角形区域绕一条直角边旋转一圈形成的旋转sweep体是一个圆锥。允许待推移的物体A在推移过程中任意变化，轨道P为任意曲线，那么所得到的推移方法称广义sweep。其中，物体A的尺寸、形状、朝向在前进过程中都可以改变。故广义sweep体是非常复杂的物体，表示能力强于平移sweep与旋转sweep，但需要的计算复杂得多。一般，对sweep体做正则运算是困难的，简单sweep体在正则运算下也不是封闭的。但推移表示简单、直观，是许多造型系统采用的输入手段。,54,实体表示方法推移表示,55,实体表示方法推移表示,56,实体表示方法构造实体几何表示,构造实体几何表示(CSG树)一种应用广泛的实体表示和构造方法。基本思想将一些简单的基本体素通过正则集合运算来构造、表示新的实体。一个复杂的物体表示成二叉树，它的中间节点是正则集合运算，叶节点为基本体素，这棵树就是CSG树。