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

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