计算机图形学简明教程第10章

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,第10章 三维几何造型,第10章 三维几何造型,三维几何造型:三维几何信息在计算机内的表示和处理。,三维几何造型包括两个分支-曲面造型（主要研究在计算机内如何描述一张曲面，如何对它的形状进行交互的设计和显示）和实体造型（着重研究如何在计算机内定义、生成一个三维物体）。,本章我们将介绍实体在计算机内的三种表示方式：物体的体素构造表示、边界表示和空间分割表示。,10.1,体素构造表示（,CSG,树表示）,体素构造表示（,Construction Solid Geometry），,或称,CSG,树表示，基本思想是用一些简单的基本体素通过正则集合运算来构造、表示新的复杂物体。,10.1.1 正则集合,三维欧氏空间,E,3,中点集,X,的正则集合定义为,rX,=k,i,X,式中,X,表示,E,3,中一个点集,r,表示正则化算子,k,i,分别表示点集的闭包和内部。,点集,X,的正则集合的含义是：取点集,X,的内部部分，然后用一张“皮”将它紧紧地包裹起来。,10.1.2,物体间的正则集合运算,为了保证物体的集合运算结果的有效性，定义正则集合运算如下：,其中、分别为正则并、正则交、正则差运算，为正则运算（,取集合运算后得到点集的内部，再用一张“皮”将它紧紧包裹起来,）。,上式的含义是：先对,A,B,作普通的集合运算，再作正则运算。,10.1.3,物体的,CSG,树表示,CSG,树的基本思想：一个复杂的物体可以被分解成两个相对简单的物体，每个相对简单的物体又可以分解为相对更为简单的物体，依次类推，因此，任意复杂形状的物体可用一些简单的基本体素通过正则集合运算来构造。,CSG,树：在体素构造表示中，一个复杂的物体可以被表示成一个二叉树，它的中间结点是正则集合运算，而叶结点为基本体素，这棵树就叫做,CSG,树。,（,b,）,（,a,）,图,10.3,物体的,CSG,树表示,10.1.3,物体的,CSG,树表示,CSG,树的每一结点由操作码、坐标变换域、基本体素指针、左子树、右子树组成，图10.4给出了,CSG,树结点数据结构的一种组织方式。,CSG,树表示支持对物体的一切几何性质的计算。采用,CSG,树表示物体直观简洁，其表示物体的有效性由基本体素的有效性和正则集合运算的有效性来保证。,图10.4,CSG,树结点的数据结构,Left-subtree,(,左子树),Right-subtree,(,右子树),Op-code,（,操作码）,Transform,(,坐标变换域),Primitive,（,基本体素）,10.2,边界表示法,边界表示法:通过描述物体的边界来表示物体的方法。,边界表示法的一个很重要的特点是在该表示法中，描述物体的信息分为几何信息（,顶点、边、面的位置、大小、形状等几何数据,）与拓扑信息（,物体上所有的顶点、棱边、表面间是怎样连接的,）。,10.2.1,物体的边界表示,物体,的拓扑信息与几何信息是分开表示的优点如下：(1)便于具体查询物体中各元素，获取它们的相关信息。(2)容易支持对物体的各种局部操作。,(3)对于具有相同拓扑结构而只是大小、尺寸不同的一类物体可以用统一的数据结构加以表示，这对于处理机械工程中具有相同类别的一类零件有很大的实际意义。,半边数据结构,在构成多面体的三要素(顶点、边、面)中，半边数据结构以边为核心。,为了方便表达拓扑关系，它将一条边表示成拓扑意义上方向相反的两条“半边”，所以称为半边数据结构。,多面体,面,顶点,环,半边,prevs,nexts,prevf,prevl,nextf,nextl,prevv,nxt,prv,floops,fsolid,sfaces,nextv,wloop,ledge,lface,vedge,vtx,图,10.10,半边数据结构的层次结构,边,sedges,preve,nexte,边,左半边,左环,右半边,右环,图,10.9,半边数据结构,左指针,右指针,v,2,v,2,v,1,v,1,10.2.2 Sweep,运算,平移,Sweep：,一个二维区域（图形）沿着轨迹作直线移动而形成空间区域（三维图形）。,常用的立方体和圆柱体等基本体素即可用此法生成。,Sweep,运算大致分为三种：平移式、旋转式和广义,Sweep。,（1）平移,Sweep,Sweep,运算以沿着某种轨迹移动点、曲线或曲面为基础，移动过程所产生的轨迹分别为一维、二维或三维物体。,旋转,Sweep：,将一平面区域沿某一轴线旋转某一角度生成一个三维物体的运算。,将广义,Sweep：,一平面区域（该区域可以在移动过程中按一定的规则变化）沿任意的空间轨迹线移动生成一个三维物体的运算。,（3）广义,Sweep,（2）旋转,Sweep,一般情况下，,Sweep,运算生成的形体需转换成其他表示形式后才能对其进行正则集合运算。,一般实体造型系统提供用户,Sweep,操作，但用户操作的结果被自动转换成相应的表示形式，例如边界表示形式。,10.2.3,局部运算,局部运算仅涉及对物体的几何信息或拓扑结构做某些局部的修改，它比在整个意义下的物体间的集合运算效率高很多。,局部运算是一种用户控制的运算，因此，用户必须保证对物体形状的修改不破坏物体的整体性质。,1修改物体的几何信息,例如，改变图10.17物体顶部表面的几何定义，用户必须保证顶部表面形状修改后不改变它与四个面片的邻接关系，即与修改面片的相邻接的四个面的相应边也要同时修改。,图10.16 调整某些表面的位置,图10.17 改变物体表面的几何定义,2,结构平面,结构平面：一个立体图形的输入，可以由简到繁、一步一步地进行，如要生成10.21所示的图形，可以先生成10.19中的二维半图形，再在平面,ABCD,上用推移方法拉伸出一个柱体来。平面,ABCD,就叫做结构平面。,可以把平面,ABCD,旋转到它的法线与坐标轴平行的位置，如图10.20，然后在平面,ABCD,上绘一个圆，并指定在平面上生成的圆柱体的高度，通过拉伸操作在平面,ABCD,上生成一个柱体，得到要输入的图形。,A,B,C,D,A,B,C,D,B,C,D,A,A,图,10.19,指定结构平面,ABCD,图,10.20,把结构平面转成面向用户,图,10.21,形成要输入的图形,10.2.4,集合运算,在边界表示中，物体是通过描述其边界定义的。显然，两物体经过正则集合运算后，所产生的新物体的边界是两原物体边界的一个子集，即,式中,b,表示物体的边界，,表示所施加的正则集合运算。,1集合运算,令,iB,表示,B,的内部。由于物体,A,和,B,为正则点集，所以它们均可表示为边界点与体内点的集合，即,A,物体的边界,bA,可按其位于,B,物体内，,B,物体上，,B,物体外分别表示为,bA,iB,，,bA,bB,bA,outB,三部分。同理，,bB,亦可分为,bB,iA,，,bB,bA,bB,outA,三部分。注意,bA,bB,=,bB,bA,。,1集合运算,考察,A,B,两物体的交所形成拼合体的边界，见图10.22。设正则集合点集,C,表示,A,和,B,两物体的交，,C=A,*,B,。,由点集求交定义知，,A,和,B,两物体边界位于对方体内的部分组成,C,的部分边界；而,A,和,B,两物体边界分别位于对方体外的部分必定不在,C,的边界上。重合部分边界构成拼合体边界一部分的充要条件是,bA,bB,中的同法向部分，故,类似的,其中表示,bA,bB,中的同法向部分；表示,bB,iA,的反法向部分；表示,bA,bB,中的反法向部分。,图,10.22,AB,拼合体的边界,A,B,A,B,A,B,S,1,S,4,S,3,S,2,2,集合运算的具体实现,当物体采用边界表示时，它们之间的集合运算可分为以下四步。,（1）预检查两物体是否相交,常采用的方法是用边界盒技术预检查两物体是否相交。,（2）计算两物体各表面之间的交线,计算两物体表面之间的交线是整个集合运算的核心，它直接影响集合运算的效率和速度，必须慎重予以考虑。,如果待处理的两个物体都是平面多面体，其表面是一个个平面多边形，其求交过程就十分简单。如果两物体具有曲面边界，涉及到曲面片与曲面片的求交，求交过程相对复杂。一般有两种处理方法。,首先联立两曲面片的表示式建立交线的方程，用解析方法确定出初始交线，初始交线一般无界，图10.23中的,A,即为图中两相交曲面的相交曲线。然后，用每一曲面的边界对初始交线进行裁剪，分别确定出初始交线位于两相交曲,1）解析求交,面内部的区段，在图10.23中，,ac,和,bd,分别为,A,位于两曲面内部的区段。最后，计算这两个区段的重叠部分，即为两相交曲面之间的真正交线，如图10.23中的,bc。,当两曲面为简单曲面时，用解析方法求交的优点是解的精度高，求解过程稳定可靠。,图10.23两曲面交线段,bc,b,A,a,c,d,对一般的自由曲面，用解析方法求交的计算极为复杂，可靠性和效率都难以保证，此时应采用离散方法求交。首先将曲面片离散成许多四边形或三角形，然后用解析方法求出这些多边形间的交线，将它们连接起来近似表示两曲面间的交线。这种方法的优点是计算简便，程序处理一致。,2）离散求交,并且常用的参数曲面如,Bzier,曲面、,B,样条曲面、,NURBS,曲面等都有高效的离散算法。该方法的缺点是存在逼近误差，解的精度低。,（,a）,(,b),图10.24(,bB,bA,),a-s,和(,bB,bA,),s,两物体之间的交线将它们的表面分割成两部分，一部分形成新物体的边界，另一部分位于拼合体内或拼合体外。,3）对物体表面进行判定分类,在边界表示中，物体的所有表面均为有向面,即它们都有确定的外法向。我们可以把,A,物体上的所有表面根据它们对,B,物体的位置关系分为,bAinB,、,bAoutB,、(,bA,bB,),s,、(,bA,bB,),a-s,四个子集合,见图10.24(,a),和图10.24(,b)。,同样，用,bBinA,、,bBoutA,、(,bB,bA,),s,、(,bB,bA,),a-s,表示,B,物体上所有表面对,A,物体的分类。显然，(,bA,bB,),s,等于(,bB,bA,),s,；,但(,bA,bB,),a-s,不等于(,bB,bA,),a-s,。,下面以图10.25为例说明表面边界的分类判定方法。其中，物体,A,和,B,均为长方体，如图10.25（,a）,和(,b),所示。两物体表面求交后，交线将物体,A,的原有六个表面分成10部分。设,S,(,v,1,v,2,v,n,),表示由顶点,v,1,v,2,v,n,组成的表面，顶点,v,1,v,2,v,n,的排列顺序与表面,S,的外法线方向符合右手螺旋法则，则,3）对物体表面进行判定分类,图10.25,A,B,物体的并和差,A,(,a),(,b),B,(,c),m,1,d,a,c,b,m,g,h,f,e,b,1,d,1,a,1,c,1,e,1,f,1,g,1,h,1,n,n,1,(,d),m,1,d,a,c,b,m,g,h,b,1,d,1,a,1,c,1,g,1,h,1,n,n,1,(,e),m,1,d,a,c,b,m,g,f,e,b,1,d,1,a,1,c,1,e,1,f,1,n,n,1,如图10.25（,c）,所示。图11.25（,d）,和（,e）,分别为,A,、,B,两长方体求并和差的结果。,3）对物体表面进行判定分类,4）建立新物体的边界表示,得到新物体的边界面之后，要依据该边界表示所采用的数据结构，建立新物体的边界表示。,10.3,空间分割表示,10.3.1 单元分解表示（,Cell Decomposition）,单元分解表示以不同类型的基本体素通过“粘合”运算来构造新的物体。这些基本体素可以是任何简单物体，如球、圆柱、圆锥、多面体等。粘合运算生成的物体的特点是：相粘合的两个物体在边界上接触，但不相交。,(,a),基本体素,(,b),同一实体的不同表示,图10.26 物体的单元分解表示,图