图形学第八章.doc

第八章 三维物体的表示 171第八章 三维物体的表示图形场景中能够包括的物体的种类和类型很多，如树、花、云、石、水、砖、木版、橡胶、纸、大理石、钢、玻璃、塑料和布等等。因此，不存在某一种方法能用来描述具有上述各种不同物质的所有特征的物体。为了用计算机产生景物的真实感图形，就需要使用能精确地建立物体特征的表示方法。多边形和二次曲面能够为诸如多面体和椭球体等简单欧氏物体提供精确描述；样条曲面及造型技术可用于设计机翼、齿轮及其他有曲面外形的机械结构；过程方法，如分形结构和粒子系统，可以给出云、草丛和其他自然景物的精确表示；运用相互作用力的基于物理的建模方法可用来描述布或胶状球的非刚性行为；八叉树编码可用来表示物体的内部特征，如医用CT影象；而等值面显示、体绘制和其他可视化技术则可以用于三维离散数据集来获得数据的可视化。三维实体表示方法通常分为两大类：边界表示和空间分割表示，尽管并非所有的表示都能完全属于这两类范畴中的某一类。边界表示(B-reps)用一组曲面来描述三维物体，这些曲面将物体分为内部和外部。边界表示的典型例子是多边形平面和样条曲面。空间分割表示(Space-Partitioning)用来描述内部性质，将包含一物体的空间区域分割为一组小的、非重叠、连续实体(通常是立方体)。三维物体的一般空间分割描述是八叉树表示。本章将讨论三维物体的各种表示方法的特点及其如何应用到实际中去。8.1 多边形表面三维图形物体中运用边界表示的最普遍方式是使用一组包围物体内部的表面多边形。大多数图形系统以一组表面多边形来存储物体的描述。由于所有表面以线性方程加以描述，因此简化并加速了物体的表面绘制和显示。故，多边形描述被称为“标准图形物体”。多面体的多边形表示精确地定义了物体的表面特征，但对其他物体，则是通过多边形网格逼近表示的。通过沿多边形表面进行明暗处理消除或减少多边形边界，以实现真实感绘制。为了提高逼近精度，可通过将曲面分成更小的多边形面片加以改进。8.1.1 多边形表用顶点坐标集和相应的属性参数可指定一多边形表面。一旦每个多边形的信息输入后，它们便被存储在多边形数据表中，以用于后续对场景中物体的处理、显示和管理。多边形数据表分为几何信息表和属性信息表来组织。几何信息表包括顶点坐标和标识多边形表面空间方向的参数；属性信息表则包括指明物体透明度和表面反射度的参数和纹理特征。几何数据存储的最方便的方法之一是建立三张表：顶点表、边表和多边形表，物体中的每个顶点坐标存储在顶点表中。含有指向顶点表指针的边表，用来为多边形每条边标识顶点。多边形表则含有指向边表的指针，以标识每个多边形的边。例如图8.1给出了一个物体表面的二个相邻多边形。 V1 顶 点 表 边 表 多边形表 E1 E3 E6 V1：x1，y1，z1 E1：V1，V2 S1：E1，E2，E3 S1 S2 V5 V2：x2，y2，z2 E2：V2，V3 S2：E3，E4，E5 E2 V3 E4 E5 V3：x3，y3，z3 E3：V1，V3 E6 V2 V4 V4：x4，y4，z4 E4：V3，V4 V5：x5，y5，z5 E5：V4，V5 E6：V5，V1图8.1 两个相邻多边形面片的几何数据表表示，由6条边禾个顶点组成采用三张表分列几何数据可方便地引用每个物体的单个组成部分(顶点、边、多边形)，同样，用边表中的数据可画出组成物体的线，可以得到物体的线框显示。存储集合数据的另一种方法是使用顶点表和多边形表，但这种方法不十分便利，某些边可能要画两次。还有一种方法就是只用多边形表，由于每个多边形中的每个顶点的坐标值都需列出，因此坐标信息重复，而且边信息也由多边形表中的顶点重复构造。当然，还可以在三表中增加额外信息来加快信息析取，比如，将边表扩充以包含指向多边形表的指针(图8.2)，这样两多边形的公共边可更快地标识。这对在明暗处理时，对跨越一边的两个多边形之间的平滑过渡的绘制特别有利。类似地，亦可扩充顶点表以增加指向相应边的指针。 E1：V1，V2，S1 E2：V2，V3，S1 E3：V1，V3，S1，S2 E4：V3，V4，S2 E5：V4，V5，S2 E6：V5，V1，S2 图8.2 图8.1中表面的边表扩充为包含指向多边形的指针通常存储在数据表中的:附加信息有：每一条边的斜率和每一个多边形的坐标内容，一旦顶点输入后，可很快计算出边的斜率，通过扫描坐标值计算出每个多边形的坐标最大值和最小值，这对以后的处理是有用的。由于几何数据表可以包含复杂物体中顶点和边的扩充列表，因此数据的一致性检验和完整性检验非常重要。当顶点、边及多边形被指定后，某些输入错误有可能导致物体显示失真。包含在数据表中的信息越多，检查错误越容易。使用三张表的方案因提供了更多的信息，而使错误检验更方便。需要完成的检验有： 每个顶点至少是两条边的顶点； 每条边至少是一个多边形的部分； 每个多边形是封闭的； 每个多边形至少有一条公共边； 对于包含多边形指针的边表，每一个被多边形指针引用到的边有一个逆指针指回到多边形。8.1.2 平面方程平面方程的表示形式为 （8.1）一旦多边形的顶点坐标和其他信息输入到多边形数据结构中，则可由三个不共线点计算出A、B、C、D，并且同其他多边形数据一并存储。平面的空间方向用平面的法向量表示，其坐标分量为（A，B，C）。因为通常讨论的是包含物体内部的多边形平面，因此需要区分平面的两个侧面。面向物体内部的一面称为“内侧”面，面向外的称为“外侧”面。若多边形顶点逆时针编号，则在右手坐标系中观察平面的外侧时，法向量由里向外。平面方程可用来检测空间中点与物体平面的位置关系。对不在平面上的点（x，y，z ），有由值的符号判断点在面的内部或外部：，点（ x，y，z ）在面的内部，点（ x，y，z ）在面的外部8.1.3 多边形网格利用多边形网格逼近物体表面时，采用的多边形网格通常有两种：1. 三角形网格：由n个顶点产生n-2个三角形；2. 四边形网格：给出n行m列顶点，产生(n-1)(m-1)个四边形。8.2 二次曲面和超二次曲面二次曲面是一类常用的物体，由二次方程描述，包括球面、椭球面、环面、抛物面和双曲面。二次曲面，尤其是球面和椭球面，是最基本的图形物体，经常作为图元用在图形包中，由此可以构造更复杂的物体。8.2.1 球面在笛卡儿坐标系中，球心在原点，半径为r的球面定义为满足下列方程的点集(x，y，z)： （8.2）我们也可以用参数形式来描述球面，使用球面坐标可得球面的参数方程： （8.3）8.2.2 椭球面椭球面可以看成是球面的扩展，它的三条相互垂直的主半轴有不同的长度。椭球面中心在原点的笛卡儿表示式为： （8.4）相应地，椭球面的参数方程为： （8.5）8.2.3 环面环面是轮胎形状物体，将圆或其他二次曲线绕指定轴旋转而成。在笛卡儿坐标系中，环面的方程是： （8.6）其中， r是给定的偏移量。环面的参数方程类似于椭球面，其表示式如下： （8.5）8.2.4 超二次曲面超二次曲面(superguadrics)由二次方程添加参数而成，对调整物体形状增加了方便。增加的参数数目等同于物体的维数：曲线一个参数，曲面二个参数。l 超椭圆在椭圆相应的方程中，允许x和y的指数是变量，这样可以得到超椭圆的笛卡儿表示式。笛卡儿坐标系下，超椭圆方程的表示形式之一是： （8.6）其中参数s是任何实数，当s=1时，为一般椭圆的表示式。相对于方程（8.6），超椭圆的参数方程是： （8.7）l 超椭球面超椭球面的表示式是由椭球面方程增加二个指数参数而得： （8.8）当时，得到一般的椭球面。相对于方程（8.8），超椭球面的参数方程是： （8.9）8.3 柔性物体有些物体不具有固定形状，当处于运动状态或接近其他物体时会变化其表面特征。如分子结构、水珠、带状物体、人类肌肉等。这些物体具有“柔性”，称之为柔性物体(blobby objects)，因为这些物体具有一定程度的流动性。例如，分子形状在独立存在时可用球面描述，但当分子接近其他分子时，其形状发生改变。电子云形状的变形便是由于两个分子间发生“结合”而产生延伸、分裂和收缩效果。这些特性不能简单地用球面或椭球面来描述。目前已开发了几种用分布函数来表示柔性物体的建模方法，其一是用Gauss密度函数的组合来对物体建模，表面函数定义如下： (8.10) 其中，T是某个特定临界值，参数用来调整单个柔性物体。另一些用来生成柔性物体的方法是使用在几个区间取0值而不是指数形式的密度函数。元球(metaball)模型将混合物体看成几个二次密度函数的集合： (8.11)软物体(soft object)模型使用函数： (8.12)8.4 曲面的表示8.4.1 Bzier曲面Bzier技术是由法国Renault汽车公司的Bzier提出的，是构造自由曲线曲面的最重要最基本的方法之一。由于它能满足造型对曲线曲面的要求，因此在应用和理论上均得到了极大的重视和发展。Bzier曲面是Bzier曲线向曲面的直接推广。给定三维空间(n+1)(m+1)个点，张量积形式的参数多项式曲面： (8.13)称为nm次Bzier曲面。称为的控制顶点，由两组多边形 和组成的网格叫做的控制网格，分别为n次和m次Bernstein多项式。类似于Bzier曲线，曲面具有下述性质： 角点位置：的四个角点是。 边界线位置：的四条边界线、和分别是以、和为控制多边形的Bzier曲线。 角点切平面：三角形、和所在平面分别在角点与曲面相切。 角点法向量：由切平面可知，是在处的法向量，其余各角点的法向量类似。 凸包性：曲面位于控制顶点的凸包内。 几何不变性：曲面的形状和位置与坐标系的选取无关。 交互能力：的控制网格可作为曲面的输入和人机交互的良好手段。 易拼接性：两块曲面相连接时，若过其公共边界上任一点的任意平面与两曲面的交线在该点处连续(具有连续的切线方向)，则称这两曲面沿其公共边界连续。现讨论Bzier曲面与另一次Bzier曲面 （8.14）的拼接问题。如果下列条件满足： （8.15）其中是常数，则和沿其公共边界达到连续。 易离散性可按下列方法分成四块小的Bzier曲面片 （8.16）其中,上式中各控制顶点由下列递推关系式决定：（8.17）（8.18）（8.19）根据上述递推关系可设计实现Bzier曲面的离散算法。递归对Bzier曲面进行离散，可得到一个收敛于原曲面的控制多面体序列，用此可实现Bzier曲面的多面体逼近。 8.4.2 B样条曲面Bzier技术能够方便地用于设计一段曲线、一片曲面，但是当需要用多段曲线或多片曲面设计形体时，采用Bzier技术，就必须处理曲线或曲面的拼接，这有时是很不方便的。此外，Bzier技术在实际造型中还有下述缺陷： Bzier曲线曲面的次数与控制顶点的数目相关联； 形状的控制是整体的。为了弥补Bzier技术的不足，增加外形设计的灵活性，Resenfeld将B样条技术因入CAD和计算机图形学领域。 B样条基函数给定参数轴上的一个分割（节点向量），由下列递推公式定义的函数称为节点向量上的阶（次）B样条基函数： （8.20） （8.21）在上述递推关系中如遇到，则取其结果为0.在节点向量中，如果有，则称节点为中的重节点。B样条基函数的定义有多种等价定义，如差分定义、卷积定义等。上述的递推定义由Cox-deBoor给出。 B样条基函数的性质l 局部支撑性 （8.22）区间称为的支撑区间。l 权性（归一性） （8.23）或者 （8.24）l 分段多项式在每一长度非零的区间上都是次数不超过的多项式。l 连续性在区间上连续，在节点处次连续，其中为节点的重数。l 导数计算公式 （8.25） B样条曲线给定空间点，下列参数多项式曲线 （8.26）称为阶B样条曲线，折线称为的控制多边形，叫作控制顶点或deBoor点。为节点向量确定的阶样条基函数。由B样条基函数的性质，可得B样条曲线的性质如下：l 定义域：B样条曲线的定义域为。l 强凸包性： 在区间上的部分位于定义它的deBoor点的凸包内，整条曲线则位于各凸包的并集之内。l 分段参数多项式：在区间内，是次参数多项式曲线，在区间上，是参数的分段次多项式曲线。l 连续性：在内节点处阶连续，其中是的重数。整条曲线在定义域上阶连续，。l 几何不变性：B样条曲线的形状和位置与坐标系的选取无关。l 保凸性：当定义B样条曲线的控制顶点形成一个平面凸多边形时，在为一平面凸曲线。l 变差缩减性(VD性质)：任意平面与的交点数目不多于该平面与定义的控制多边形的交点数目。l 局部性：的每一段仅受到个控制顶点的影响，任一控制顶点最多影响段曲线。l 对Bzier曲线的包含性：当节点向量为时，B样条曲线退化为Bzier曲线。实际应用中，定义B样条曲线的节点向量有四种形式：均匀节点向量(Uniform Knot)；准均匀节点向量(Quasi-Uniform Knot)；Bzier型节点向量(Bzier-Like Knot)和非均匀节点向量(Non-Uniform Knot)。 deBoor-Cox算法现讨论B样条曲线的计算问题，对于给定的参数，由（8.21），将化简如下： （8.26）令： （8.27）则式（8.26）可表示为上式是同一条曲线从阶B样条表示到阶B样条表示的递推公式，运用此公式，得到于是，值可通过递推公式（8.27）求得，这就是著名的deBoor-Cox算法。用deBoor-Cox算法由求的递推过程，可列表如下：反映在几何上，deBoor-Cox算法是一个割角过程。 样条曲面给定列、行空间点，张量积参数曲面 （8.28）称为阶的B样条曲面，其中B样条基函数、分别由节点向量和所确定，称为曲面的控制顶点，它们顺次构成的空间四边网格叫做曲面的控制网格。除保凸性外，B样条曲面的性质类似于B样条曲线，在此不再详细讨论。8.4.3 NURBS曲线面B样条技术在表示和设计自由型曲线面形状时显示了强大的威力，然而在表示与设计由二次曲面和平面构成的初等曲面时却遇到了麻烦。因为B样条曲线不能精确地表示除抛物线外的二次曲线，B样条曲面不能精确表示除抛物面外的二次曲面，只能给出近似表示。近似表示将带来处理上的麻烦，使本来简单的问题复杂化，还带来原来不存在的设计误差问题。为了精确表示二次曲线和二次曲面，就不得不采用另外一套数学描述方法，比如用隐式方程表示。这不仅又重新带来隐式方程表示所存在的问题，而且将导致一个几何设计系统采用并存的两种不同数学方法。这将使系统变得十分庞杂，是系统研制人员最为忌讳的。解决这个问题的途径显然应该是改造现有的B样条技术，在保留它描述自由型曲线面的长处的同时，扩充其精确表示二次曲线曲面的能力。人们所寻求的这种数学方法就是有理B样条技术，由于在形状描述实践中，它经常以非均匀类出现，所以习惯上称之为NURBS技术。1991年，国际标准委员会(ISO)颁布的关于工业产品数据交换的STEP国际标准，将NURBS作为定义工业产品几何形状的惟一数学方法。 NURBS曲线给定个空间点，和非负实数，其中，下列分段有理参数阶多项式曲线 （8.29）称为阶NURBS曲线，叫作控制顶点或deBoor点，称为与控制顶点相关联的权因子，折线称为的控制多边形，。为节点向量确定的阶B样条基函数。 NURBS曲线的性质l 局部性：阶NURBS曲线上参数为的点至多与个控制顶点及权因子相关，与其他控制顶点及权因子无关。改变一个控制顶点或改变的权因子，仅仅影响定义在区间 上的那部分曲线的形状，不影响NURNS曲线的其他部分。l 变差缩减性：任意平面与的交点数目不多于该平面与定义的控制多边形的交点数目。l 强凸包性：在区间上的部分位于定义它的deBoor点的凸包内，整条曲线则位于各凸包的并集之内。l 在仿射变换与射影变换下的不变性：NURBS曲线面在比例、旋转、平移、剪切以及平行和透视投影变换下仍然是NURBS曲线面。l 连续性：在内节点处阶连续，其中是的重数。整条曲线在定义域上阶连续，。l 若某个权因子，则相应的控制顶点对曲线不产生影响。若，则 （8.30）l Bzier曲线面、B样条曲线面以及圆锥曲线和二次曲面都是NURBS曲线面的特例，由此可以看出NURBS既为标准解析形状，也为自由型曲线面的精确表示与设计提供了一个统一的数学形式。因此一个统一的数据库就能存储这两类形状信息。l 权因子的引入增强了曲线面设计的灵活性。 圆锥曲线的NURBS表示给定节点向量，那么由控制顶点和权因子确定的二次NURBS曲线 （8.31）是一条圆锥曲线，其形状分类如下： （8.32） NURBS曲线的计算基于齐次坐标的观点，NURBS曲线可看作是四维空间的B样条曲线在三维空间的中心投影变换 （8.33）下的象曲线。对此，一条阶NURBS曲线可按以下步骤确定：a. 由控制顶点和权因子确定带权控制顶点 （8.34）b. 用带权控制顶点定义阶B样条曲线c. 将其投影到超平面上，所得中心投影象曲线即为阶NURBS曲线由此，NURBS曲线的计算可采用B样条计算的deBoor-Cox公式在高一维空间进行，然后取其在超平面上的投影即可。 NURBS曲面类似于NURBS曲线，一张阶NURBS曲面定义如下： （8.35）这里，称为曲面的控制顶点，它们顺次构成的空间四边网格叫做曲面的控制网格。为权因子，满足条件，B样条基函数、分别由节点向量和所确定， 权因子的几何意义NURBS曲线面有别于B样条曲线面之处在于引入了权因子，所以有必要对权因子的几何意义作以讨论。形式上看，权因子是一纯数量。实质上，权因子具有明显的几何意义。对于NURBS曲线若令则有于是上述两个比值是直线上四点的交比，即 dj n R m 图8.3 权因子的几何意义由此，我们得到了权因子的明显的几何意义：权因子等于过控制顶点的一条直线上分别具有权因子和的那四个点 的交比，这四个点中的前三个点是特定的(图8.3)。8.4.4 Coons曲线面Coons曲面造型方法是由MIT的S. A. Coons于1964年提出的。Bzier曲面、B样条曲面以及NURBS曲面的特点是曲面逼近控制网格，而Coons曲面的特点是插值，即构造出的曲面满足给定的边界条件，如通过给定边界，具有给定的跨边界导矢等等，所以有时Coons曲面亦称作超限插值曲面。常用的Coons曲面有三种。 双线性混合Coons曲面片给定由四条参数曲线围成的空间封闭曲边四边形，使两对边分别定义在与上，要求构造一张以这四条曲线为边界曲线的曲面：图8.4 曲边四边形 （8.36） 即，已知曲面的四条边界，求该曲面。这个问题有无穷多解，其中的一种就是双线性混合Coons曲面。在每一对边界曲线间由线性插值构造直纹面： （8.37）两张曲面与的简单叠加并减去曲面片四个角点决定的一张双线性张量积曲面： （8.38）即得到所求的双线性混合Coons曲面片其矩阵表示如下： （8.39） 局部双三次混合Coons曲面片双线性混合Coons 曲面片利用了两对线性混合函数。有许多其他的混合函数也能用来满足插值曲面四条边界的要求。惟一的限制是每对混合函数之和恒等于1。采用两对三次混合函数：则得到了局部双三次混合Coons曲面片 （8.40）尽管Coons曲面片仍然由两个直纹面相加减去一个张量积曲面，张量积曲面没有任何改变，两个直纹面的形状也没有改变，但沿着直母线的点的分布发生了改变即参数化变了。因而导致最后叠加得到的Coons曲面片的形状发生了变化。局部双三次混合Coons曲面片较之双线性混合Coons曲面片的优点在于实现了光滑连接，即当两相邻Coons曲面片在公共边界两端点处连续时，沿公共边界处处两跨边界切矢也连续。 双三次混合Coons曲面片虽然局部双三次混合Coons曲面片解决了连接问题，但新的问题又出现了。采用双三次混合函数的结果，导致了曲面片在角点处的扭矢(混合偏导)为零矢量，从而引起曲面角点处出现“伪平点”。出现这种不良性能的原因在于我们仅仅用了四个一组的三次Hermite基函数中的两个。在区间端点处这两个函数的导数都为零，而传递到曲面角点处引起。为了避免这个问题，必须修改局部双三次混合Coons曲面片。三次Hermite插值不仅要求端点位置信息，而且还要求端点切矢信息。由于这里的位置信息是整条曲线，而不是点，相应的切矢信息也应沿整条曲线提供。因此生成双三次混合Coons曲面片的输入数据应包括：四条边界曲线：，四条跨边界切矢：，利用三次Hermite基函数 ，构造向插值曲面：类似地，构造向插值曲面：如在双线性混合中那样，定义对角点数据的插值曲面：则双三次混合Coons曲面片为：或者以矩阵形式表示为：（8.41）由此可以看出，双三次混合Coons曲面片除四条边界曲线、四边界跨边界切矢外，还要求提供四角点扭矢。一般来说，提供四边界跨界切矢和四角点扭矢并非易事。对此，我们不做进一步的讨论，有兴趣的读者可参阅相关文献。8.5 实体的表示8.5.1 三维实体的定义实体造型的核心问题是如何在计算机内定义、表示一个三维物体。我们知道任何一个三维物体都具有完全封闭的边界表面，而物体的封闭的边界表面由一组面所构成，各个面均有方向，明确地划分出物体的内部和外部。每个面均有单独的数学定义，每个面又由封闭的环确定其边界。每个环由一组边构成，每条边也有单独的数学定义，且由两个端点所界定，一个为边的起点，另一个为边的终点。每个顶点由空间三个坐标值来确定。三维物体的这种内在的层次结构便给出了在计算机内定义实体的拓扑结构，即实体在计算机内通常采用六层拓扑结构来定义。 Body ShellFace Surfaces Loop Edge Curves Vertex Points 拓扑信息 几何信息 图8.5 三维物体的层次结构为了保证所描述的三维物体的合法性，各层次的元素君有严格的定义，现简要说明如下： 体(Body)：体是由封闭表面围成的维数一致的有限空间。通常把具有良好边界的实体称为正则实体。 壳(Shell)：壳是方向一致的一组面的集合，形成封闭的单一连通空间。一个三维物体可以有多个壳，其中仅有一个外壳，其余为内壳。外壳就是在观察方向上所能看到的物体的最大外边界，内壳的内部则为空腔。 面：面是形体表面的一部分，是有界、不自交的连续表面，且有方向性。面的有效范围由一个外环和若干个内环界定。面可以无内环，但必须有外环。一张面只能属于一个壳。与面对应的几何表面可以是平面、二次曲面、参数曲面。 环：环是由有序、有向边组成的面的封闭边界。环中各边不能自交，即组成环的各条边除了共享端点外不能再有其他交点。环有内环和外环之分，确定面的最大外边界的环是外环。外环按逆时针定向，根据外环的走向按右手法则确定面的外法向量。确定面的内孔或凸台边界的环称为内环，内环按顺时针定向。基于环的这种定向，在面上沿一个环的定向前进时，左侧总是面内，右侧总是面外。 边：边实体两个相邻面的交界。一条边只能为两个相邻面共享，边由一对端点界定，其一是起点，另一是终点。边的定向从起点指向终点。与边相应的几何线段可以是直线、圆弧、二次曲线、参数曲线。 顶点：顶点是边的端点，不允许出现在边的内部，也不能孤立地存在于物体的内外部或面内。顶点所对应的几何点在中用坐标表示。现在，我们考察体和面、边、顶点之间的层次关系。设是一无空腔的三维物体，是实体的所有面之集合，是实体之边的集合，是实体顶点的集合，表示的外壳，则： , , 。实体的生成和表示方法很多，目前常用的实体表示方法有以下七种： 参数化实体及其调用； 单元分解法； 扫描变换法(把一维、二维实体经过平移或旋转等变换生成二维、三维实体)； 构造实体几何法(CSG法)； 边界表示法(B-rep法)； 半空间法； 线框表示法。实体的任何一种表示法都需要回答以下问题：l 实体的边界是否提供了足够的信息，能否自动地计算实体的几何性质，包括显示、绘图等所需要的信息。l 一个系统或算法如何确定它们操作的数据的有效性。l 对一个实体是否有一种以上的表示方法？l 相同的实体是否有不同的表示形式？如有，又如何表示之？l 实体的某些几何性质是否只能从一种表示形式中求得，而不能从其他的表示形式中求得？l 实体是否有最佳表示形式？就当代造型系统而言，实体的上述七种表示方法中以CSG、B-rep和单元分解法最为重要，我们这里重点就这三种实体表示方法予以讨论。8.5.2 实体的CSG表示CSG表示法也称为体素构造法，它是用称之为体素的基本实体经集合运算构造复杂实体的一种实体表示法。例如，图8.6所给出的三维实体可以看作是由两个长方体和一个圆柱体经集合运算而构成，其几何定义为Part=Cube1+Cube2-Cylinder1U图8.6 三维实体的CSG构造 物体间的正则集合运算物体间的并、交、差运算是CSG表示法构造物体的最基本的手段之一。由于三维实体的一个最显著的特征是：它们可以用一个具有边界子集和内部子集的封闭点集来描述。执行物体间的并、交、差操作的结果也应该是具有边界子集和内部子集的封闭点集，并保持初始物体的维数，而传统的点集之间的并、交、差运算可能会改变点集的正则性。例如，图8.7中A、B两个物体都具有边界子集bA、bB和内部子集iA、iB。交运算在数学上是正确的，但在几何上是不正确的，因为此时不象A、B那样具有内部子集，不再是二维物体。为此，我们必须对传统的点的集合运算施加一些限制，引入正则集合和正则集合运算。 A B a b 图8.7 二维实体的交运算l 正则集合：三维空间中的集合S称为正则集，如果S=kiS 。l 正则算子：对于中的点集A、B，相应的正则算子定义如下：正则算子具有以下重要性质：若是两个正则集合，则l 正则运算： 对于三维物体进行正则运算的关键是算法，其最基本的算法步骤有求交、包含性测试、跟踪边界、形成回路和重新参数化回路等。下面我们以二维物体A、B的正则运算为例，对正则运算的算法步骤作以介绍。 正则交运算记如图8.8所示。由于，所以必须找出bQ和iQ的子集以构成封闭的维数一致的形体，的侯选部分只能从上式四部分求得。 1 A B 2图8.8 二维实体的正则交运算因，所以。因此，确定的关键是求。值得注意的是任何新物体的边界都是由初始物体的边界组成，内部点会变成边界点，而边界点自身却不能变成内部点。所以，对于正则交运算，无须证明有：下面需要确定中哪一部分子集是的有效子集。首先孤立点不是的有效元素，这是因为有效元素总是属于和的。图8.8中形体A和B有两处明显的重叠交，这些交的特点是它既不在A的内部，也不在B的内部，我们如何区分呢？通常有两种方法，一种是在边界上取一点P，从P的垂直方向沿左右移动一距离产生两个点PL，PR，然后构造一表格来测试PL，PR是否既在A内又在B内（图8.9）。若有一点满足要求，则该部分为的有效边界，否则为非有效边界。以图8.8为例，其测试结果为边界1不是有效边界，边界2为有效边界。有效边界的另一种测试方法是利用一致的参数化方向约定，对的每一子集，计算某一点处的切矢。若切矢同向，其相应的边界为有效边界，若反向为无效边界。 线段1 在A中 在B中 A B 线段1 在A中 在B中 PL 1 0 PL PR PL 1 1 PR 0 1 PR 0 0 PL PR图8.9正则交运算下的边界测试综合以上讨论，两个形体A和B的正则交运算的结果可表示为 （8.42）注意，式（8.42）并没有指出物体的维数，即它可以适用于一维、二维、三维或n维形体。 正则并运算记据此来确定和，从而确定。由于在并运算下，一些边界点会变成内部点，如果不包含这些点在中，将会出现“洞”，因此 A B 图8.10二维实体的正则并运算这里，是不在iB中，部分在bB上的bA，即再一次看到在中存在二义性，必须象讨论正则交运算那样，通过测试方法来解决，所以值得注意的是，被分为二部分，一部分属于，另一部分属于，而，从而得到： （8.43） 正则差运算记据此来确定和，从而确定。 A B 图8.11二维实体的正则差运算由图8.11可以看出：第一，此处为两个不连接的子集；第二，因为的某些元素在bQ中丢失了。若在Q中加上，其边界仍不完整。丢失的线段是的子集，因此必须对作进一步的有效性测试，以决定有效的边界。对差而言，有效的是那些仅仅与或邻接的边界，因此所以，正则差运算的结果为：（8.44）对于实际应用而言，形体A、B之间的位置关系是千变万化的，图8.12所示便是一例，这里形体A完全包含了形体B。AB 图8.12二维实体的正则运算实例如果对形体执行两次以上的正则集合运算，则所得结果取决于实际运算的顺序。 物体的CSG树表示一般地，物体的CSG表示都可以描述成一棵二叉树，这棵二叉树的叶结点或是基本元素，或是坐标变换的变换参数。非叶结点或是正则集合运算或是几何变换。每棵子树表示其下面两个结点运算的结果，根结点表示了最终的复杂物体。CSG树的语义为：=|CSG树只定义了物体的构成体素和构造方式，不反映物体的面、边、顶点等有关的边界信息，因此这种表示又称为物体的隐式模型(Unevaluated Model)或过程模型(Procedural Model)。CSG树的结点数据结构为： OP-Code 操作码 OP-Code Transformation Primitive =0：基本体素 坐标变换 基本体素 =1：并运算* Left-Subtree Right-Subtree =2：交运算* 左子树 右子树 =3：差运算*图8.13 CSG树的结点数据结构每个结点由操作码、坐标变换指针、基本体素指针、左子树指针和右子树指针5个域构成。除操作码外，其余各域都以指针形式存储。操作码按约定方式取值，当操作码为零时，表示该结点为一基本体素，相应的左、右子树指针为空(Null)；对于非叶结点，操作码取约定的正整数，表示左子树和右子树结点间进行正则集合运算，此时基本体素域为空。结点的坐标变换域存储该结点所表示形体在进行新的集合运算前所做的坐标变换信息，即将体素及其局部坐标系置于物体的整体坐标系中给定位置。用CSG树表示一个复杂物体比较简洁。它所表示的物体的有效性是由基本体素的有效性和集合运算的正则性而自动得到保证的。由于CSG树提供了足够的信息，以判断空间任一点在它所定义的内部、外部或体的表面上。因此它可惟一地定义一个物体，并支持对这个物体的一切几何性质的计算。这里指的物体的几何性质既包括它自身的性质，如体积、面积、重心等，也包括它与别的物体相互关联的性质，如计算这个物体与一相邻物体之间的最短距离等。计算物体几何性质的算法和描述一个物体的数据结构是密切相关的，不同的数据结构对应不同的算法。CSG表示法最适宜采用“分而治之”算法(divided & conquer)。设F是关于一个CSG树所定义物体的几何性质的函数，则计算F的算法框架如下：F(tree, data)=if (tree_is_a_leaf) Prim_F(tree, data) elseCombine (F(left-subtree, data), F(right-subtree, data), node(tree)其中Prim_F为计算基本体素的几何性质F之函数，Combine为依据CSG树非叶结点进行的运算对左右子树的几何性质F进行合成的函数。虽然CSG树表示可以支持关于它所表示物体的多种几何性质的计算及其他应用，但它并非适用于一切场合。例如，它不适用于对物体形状做局部修改，生成工程设计中常用的线框图效率底，此时常需要将物体的CSG树表示转化为边界表示，以便获取边界信息。8.5.3 实体的边界表示实体的边界表示法就是通过描述物体的边界来表示一个物体，边界就是物体内部点与外部点的分界面。显然，定义了物体的边界，该物体就被惟一地定义了。 边界表示法表示物体的方式用边界表示法定义物体有两种方式，其一是把面组成CSG表示中的体素，再通过装配体素形成更复杂的物体；另一种是直接通过适当表面的组合和相交产生复杂的物体。 边界表示法的翼边结构在边界表示法中，表示面、边和顶点相互邻接关系的信息，属于拓扑信息，表示这些邻接关系的拓扑信息在建立边界模型以及对边界模型进行处理和交互操作中非常重要。描述面、边、顶点三种拓扑元素的邻接关系可分为三组共九种表示方式，如图8.14所示： VV EV FV VE EE FE VF EF FF 相邻于顶点的邻接关系 相邻于边的邻接关系 相邻于面的邻接关系图8.14 面、边、顶点的邻