第4章 图形的表示与数据结构2

4.3三维形体的表示•模型分类14.3三维形体的表示•8.3.1线框模型将形体表示成一组轮廓线的集合。–一般地，画出了形体的棱线就能表示出来。如图，八个顶点可以定义一个长方体e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s42–优点：简单、处理速度快–缺点：1、没有形体的表面信息，不适于真实感显示，由此导致表示的形体可能产生二义性2、容易构造无效形体4.3三维形体的表示(a)有效形体(b)无效形体34.3三维形体的表示3、不能正确表示曲面信息。4、无法进行图形的线面消隐。4•4.3.2表面模型–使用一组包围物体内部的平面多边形来描述实体。4.3三维形体的表示体面边顶点VABCABDBCDACDABBCCAADBDCDABCD四面体及其点、边、面的关系BCDA5•表面模型的构造–把线框模型中棱线包围的部分定义为面，所形成的模型便是表面模型。其数据结构是在线模型的基础上附加一些指针，有序地连接棱线。下图中表面编号表示第几个表面，表面特征表示是平面还是曲面4顶点个数1起始指针0表面特征5表面编号014043032021连接指针属性顶点号142323414.3三维形体的表示6顶点表边表面表Ax1,y1,z1ABA,BABCAB,BC,ACBx2,y2,z2BCB,CABDAB,BD,ADCx3,y3,z3CAC,ABCDBC,CD,BDDx4,y4,z4ADA,DACDAC,CD,ADBCB,CCDC,D表面模型的表示:（1）多边形表：几何表、属性表等分别存储几何信息和属性信息4.3三维形体的表示7拓扑信息的表示–显示表示：在数据结构中显式的存储拓扑结构。例如，翼边结构表示（WingedEdgesStructure）–隐式表示：即根据数据之间的关系在运行时实时的解算。EF1V2V1F2翼边结构表示4.3三维形体的表示8•ax+by+cz+d=0;•主要操作：•求平面的法向量•鉴别空间上的点与物体平面的位置关系。•判别点在面的内部或外部表面模型的表示：（2）使用平面方程：4.3三维形体的表示9三维形体的曲面边界通常用多边形网格（polygonmesh）的拼接来模拟。三角形带、四边形网格表面模型的表示（3）多边形网格：此四边形网格含6个四边形，由3*4个顶点形成此三角形带由10个三角形和12个顶点相连而成4.3三维形体的表示104.4实体模型—规则实体的表示在实体模型的表示中，基本上可以分为分解表示、构造表示和边界表示三大类。•4.4.1分解表示–将形体按某种规则分解为小的更易于描述的部分，每一小部分又可分为更小的部分，这种分解过程直至每一小部分都能够直接描述为止。–分为空间位置枚举表示、八叉树表示、单元分解法等114.4.1.1第一种分解表示法--空间位置枚举表示–形体空间细分为小的均匀的立方体单元。–用三维数组C[I][J][K]表示物体，数组中的元素与单位小立方体一一对应•当C[I][J][K]=1时，表示对应的小立方体被物体占据•当C[I][J][K]=0时，表示对应的小立方体没有被物体占据4.4实体模型—规则实体的表示12–优点•简单，可以表示任何物体•容易实现物体间的交、并、差集合运算•容易计算物体的整体性质，如体积等4.4实体模型—规则实体的表示13–缺点•占用大量的存储空间，如1024*1024*1024=1Gbits•物体的边界面没有显式的解析表达式，不适于图形显示•对物体进行几何变换困难•物体表示不精确4.4实体模型—规则实体的表示14•4.4.1.2第二种分解表示法—八叉树表示–对空间位置枚举表示的空间分割方法作了改进：均匀分割自适应分割–八叉树建立过程•八叉树的根节点对应整个物体空间•如果它完全被物体占据，将该节点标记为F(Full)，算法结束；•如果它内部没有物体，将该节点标记为E(Empty)，算法结束；•如果它被物体部分占据，将该节点标记为B（Boundary），并将它分割成8个子立方体，对每一个子立方体进行同样的处理4.4实体模型—规则实体的表示15–8叉树的表示应用于三维形体的分解，它对形体的外接立方体的进行前后、左右、上下等分8个小立方体，如果小立方体单元中该形体为满或为空，表示该立方体完全在形体中或完全不在形体中，则其停止分解；对部分形体占有的小立方体需进一步分解为8个子立方体，直至所有小立方体单元要么全部满，要么全部空，或已分解到规定的分解精度为止。236720131375具有子孙的节点(P)空节点(E)实节点(F)4.4实体模型—规则实体的表示16–优点•可以表示任何物体，且形体表示的数据结构简单•简化了形体的集合运算。只需同时遍历参加集合运算的两形体相应的八叉树，无需进行复杂的求交运算。•简化了隐藏线（或面）的消除，因为在八叉树表示中，形体上各元素已按空间位置排成了一定的顺序。4.4实体模型—规则实体的表示17–缺点•没有边界信息，不适于图形显示•对物体进行几何变换困难•是物体的非精确表示•占用大量存储。实际上，八叉树表示是以存储空间换取算法的时间效率4.4实体模型—规则实体的表示18–八叉树的改进线性八叉树：用一可变长度的一维数组来存储一棵八叉树。数组中仅存储八叉树的性质为FULL的终端结点。并用一个八进制数表示该结点在八叉树中的位置。编码方式为：Q1Q2…Qm,m为树的深度，其中Q1表示该结点所属的一级父结点的编号（1－8），以此类推，当其为叶子节点时，其后面的编码都为0。也可以理解为从根结点沿着其祖辈的路径依次走下来，所途经的各个层的节点位置。4.4实体模型—规则实体的表示19236720131375具有子孙的节点(P)空节点(E)实节点(F)•例右图为：{1200,1410,1420,1434,1440}4.4实体模型—规则实体的表示20{1440,1450,1464,1470,1600}4.4实体模型—规则实体的表示21•4.4.1.3第三种分解表示--单元分解法–对空间位置枚举表示的空间分割方法作了改进：单一体素多种体素–将空间几何体分解成单一体素的组合。4.4实体模型—规则实体的表示22–优点•表示简单•容易实现几何变换•基本体素可以按需选择，表示范围较广•可以精确表示物体–缺点•物体的表示不唯一•物体的有效性难以保证4.4实体模型—规则实体的表示23–三种空间分割方法的比较•空间位置枚举表示----同样大小立方体粘合在一起表示物体•八叉树表示----不同大小的立方体粘合在一起表示物体•单元分解表示----多种体素粘合在一起表示物体4.4实体模型—规则实体的表示24•4.4.2构造表示构造表示主要分成以下几类：–扫描表示–构造实体几何表示（CSG）–特征表示4.4实体模型—规则实体的表示25•4.4.2.1第一种构造表示—扫描（推移）表示–将物体A沿着轨迹P推移得到物体B，称B为sweep体（1）平移sweep----将一个二维区域沿着一个矢量方向推移4.4实体模型—规则实体的表示26（2）旋转sweep----将一个二维区域绕旋转轴旋转一周4.4实体模型—规则实体的表示27（3）三维Sweep：三维形体也能在空间通过扫描变换生成新的形体，如图，一个圆柱体按指定方向在长方体上运动生成新的形体，这个过程犹如长方体与运动着的圆柱体不断的作差运算操作。扫描线方向4.4实体模型—规则实体的表示28（4）广义Sweep任意物体沿着任意轨迹推移推移过程中物体可以变形4.4实体模型—规则实体的表示29优点–表示简单、直观–适合做图形输入手段缺点–作几何变换困难–对几何运算不封闭–用扫描变换产生的形体可能出现维数不一致的问题。4.4实体模型—规则实体的表示30•4.4.2.2第二种构造表示—构造实体几何表示（ConstructSolidGeometry,CSG）–通过对体素定义运算而得到新的形体的一种表示方法。体素可以是立方体、圆柱、圆锥等，也可以是半空间，其运算为变换或正则集合运算并、交、差。–CSG表示可以看成是一棵有序的二叉树。•其终端节点或是体素、或是形体变换参数。•非终端结点或是正则的集合运算，或是变换（平移和/或旋转）操作，这种运算或变换只对其紧接着的子结点（子形体）起作用。4.4实体模型—规则实体的表示31•CSG结构示例CSG树是无二义性的，但不是唯一的.4.4实体模型—规则实体的表示32CSG表示的优点：•数据结构比较简单，数据量比较小，内部数据的管理比较容易；•物体的有效性自动得到保证；•CSG方法表示的形体的形状，比较容易修改。4.4实体模型—规则实体的表示33CSG表示的缺点：•对形体的表示受体素的种类和对体素操作的种类的限制，所表示形体的覆盖域有一定的局限性。•由于形体的边界几何元素（点、边、面）是隐含地表示在CSG中，故显示与绘制CSG表示的形体需要较长的时间。•表示不唯一4.4实体模型—规则实体的表示34•4.4.2.3第三种构造表示—特征表示–用一组特征参数表示一组类似的物体–特征包括形状特征、材料特征等–适用于工业上标准件的表示4.4实体模型—规则实体的表示35特征表示的特点–从应用层来定义形体，因而可以较好的表达设计者的意图。从功能上可分为形状、精度、材料和技术特征。–特征是面向应用、面向用户的。特征模型的表示仍然要通过传统的几何造型系统来实现。不同的应用领域，具有不同的应用特征。–在几何造型系统中，根据特征的参数我们并不能直接得到特征的几何元素信息，而在对特征及在特征之间进行操作时需要这些信息。–特征方法表示形体的覆盖域受限于特征的种类。4.4实体模型—规则实体的表示364.4.2.4构造表示的特点：–构造表示通常具有不便于直接获取形体几何元素的信息、覆盖域有限等缺点，–但是，便于用户输入形体，在CAD/CAM系统中，通常作为辅助表示方法。4.4实体模型—规则实体的表示37