《维实体的表示》PPT课件.ppt

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