计算机图形学_第十一章_三维形体的表示

Lecture11三维形体的表示概述三维造型技术是一项研究在计算机中，如何建立恰当的模型来表示自然界中形态丰富的三维物体的技术。三维造型技术根据造型对象分成三类：•第一类是曲面造型，这种造型方法研究在计算机内如何描述一张曲面。•第二类是立体造型方法，它研究如何在计算机内定义、表示一个三维物体。•第三类造型方法是自然景物模拟，研究如何在计算机内模拟自然景物，如云、水流、树等等。概述三维几何造型现已开始被广泛地应用在工业生产及艺术造型的各个领域。•机械行业•设计方面，几何造型方法可以逼真地反映物体的外观，检查零件之间的装配关系，高效、准确地生成生产图纸；•分析计算方面，它可以精确地计算出零件的质量、质心、转动惯量、表面积等物性参数；•计算机辅助制造时，可以引用几何造型的结果，直接规划数控加工的刀具轨迹；•运动分析方面，几何造型系统可以完成机械手的动作规划、运动模拟以及零件间的干涉检查等。概述•计算机艺术、动画片制作、模拟仿真、计算机视觉、机器人等领域都把几何造型作为基础。•利用三维几何造型技术，既可产生已有物体的真实模型，也可产生人们头脑中的某种设计想象或艺术模型。形体的表示在计算机中表示形体的方法通常有三种：•线框模型•表面模型•实体模型线框模型线框模型采用三维形体的全部顶点及边的集合来描述三维形体，即用三维形体的顶点表和边表两个表的数据结构来表示三维模型。线框模型线框模型的主要优点是结构简单，处理容易，在CPU时间及存储方面开销低。线框模型也有非常显著的缺点。•不能表示表面含有曲面的物体；•不能明确地定义给定点与物体之间的关系，应用范围受到了很大的限制•线框模型容易出现二义性，对于一个线框模型，可以有不同的理解。表面模型表面模型在线框模型的基础上，增加了物体中的面的信息，用面的集合来表示物体，而用环来定义面的边界.表面模型•表面模型克服了线框模型的很多缺点，比较完整地定义了三维立体的表面，因而其造型体的覆盖面较广，无论解析的或非解析的目标均可用表面模型来描述。•表面模型又分为平面模型和曲面模型两种。前者以多边形网格为基础。由上述顶点表、边表和面表就可构成平面立体的平面模型。后者是以参数曲面块为基础。•表面模型也存在一些不足，这主要是它只能表示物体的表面边界，而没有表达出真实体属性。因此，也就无法切开表示物体的内部结构。由此就很难确认一个表面模型表示的三维图形是一个实体还是一个空壳。实体模型•实体模型使用有向边的右手法则来确定所在面的外法线方向，即用右手沿边的顺序方向握住，大拇指所指的方向为该面的外法线方向。•数据结构不仅记录了全部的几何信息，而且还记录了所有的点、线、面、体的拓扑信息。这就是实体模型与线框模型或表面模型的根本区别。实体模型的构造方法通常使用体素，经集合论中的交、并、差运算构成复杂形体。实体的定义实体就是有效的物体，亦即客观世界中确实存在的物体。比如，下图所示的带有悬挂面的立方体就不是实体，在客观世界中也不存在这样的物体。实体的定义作为实体或者有效的物体应该满足以下的条件：①刚性。一个实体必须具有一定的形状（流体不属于实体造型技术描述的对象）。②维数一致性。在三维空间中，一个实体的各个部分必须都是三维的，不能存在悬挂的、孤立的边界。③有限性。一个实体必须占有有限的空间。④边界的确定性。根据实体的边界可以确定实体的内、外部。⑤封闭性。经过一系列的刚体运动及任意序列的集合运算之后，仍然是有效的实体。实体的定义一个实体的表面必须具备以下的性质：①连通性。实体表面上任意两点都可用该表面上的一条路径连接起来。②有界性。一个实体的表面把空间分为互不连通的两部分，其中实体内的部分是有限的。③非自相交性。一个实体的表面不可自相交。④可定向性。一个实体的表面两侧可明确定义出实体的内侧和外侧。⑤封闭性。对多面体而言，一个实体表面的封闭性是由表面上多边形网格各元素的拓扑关系确定的，即每条边连接且仅连接两个面，每条边有且仅有两个端点。实体的定义从点集拓扑角度给出实体的定义。将三维物体看作是空间中点的集合，它由内点与边界点共同组成。•内点是指点集中的这样一些点，它们具有完全包含于该点集的充分小的邻域。•边界点就是指那些不具备此性质的点集中的点。三维物体A可表示为：bA为物体A的边界点集，iA为物体A的内部点集。,AbAiA实体的定义定义点集的正则运算r如下：i为取内点运算；c为取闭包运算；A为一个点集。那么i·A即为A的全体内点组成的集合，称为A的内部，它是一个开集。c·i·A为A的内部的闭包，是i·A与其边界点的并集，它本身是一个闭集。rAciA实体的定义正则点集不一定是实体。如下图所示的物体，它是正则点集，但它不是有效的物体。为了得到有效的物体，我们必须排除下图所示的情况，在此我们引入二维流形的概念。所谓二维流形是指对于实体表面上的任何一点，都可以找到一个围绕着它的任意小的邻域，该邻域在拓扑上与平面上的一个圆盘是等价的。实体的定义有了二维流形的概念之后，我们可以这样来描述实体：对于一个占据有限空间的正则点集，如果其表面是二维流形，则该正则点集为实体(有效物体)。正则集合运算能产生正则几何体的集合运算称为正则集合运算。正则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面。正则集合运算与传统集合运算的区别主要是在对产生结果的边界面的处理上，其内部点是一致的。正则集合运算在正则集合运算中，要考虑如何消除或不产生悬点，悬边和悬面，在实体造型中，实现正则集合运算有两种方法：间接法和直接法。•间接法是先按普通集合运算求出结果，后用一些规则判断，消除不符合正则几何定义的部分(即悬边、悬面等)，从而得到正则几何体；•直接法则是定义正则集合算子的表达式，用以直接得出符合正则几何体定义的结果。物体的CSG树表示物体的体素构造表示法（CSG，ConstructiveSolidGeometry）是用两个物体间的并、交、差正则集合运算操作生成一个新的物体的方法。•用CSG法时，实体的构造过程是集合运算的过程。这个过程可用二叉树结构表示，这种树称为CSG树。•树的叶节点表示体素或带有几何变换参数的体素，非终止节点表示施加于其子节点的正则集合算子，或称布尔算子。树的根节点表示集合运算的最终结果，也即希望得到的实体。物体的CSG树表示CSG树节点数据结构的一种组织方式物体的CSG树表示•CSG树中的每一节点由操作码、坐标变换域、基本体素指针、左子树、右子树等5个域组成。•操作码按约定方式取值。当操作码为零时，表示该节点为一基本体素，相应左、右子树指针取零。对于非终节点，操作码取约定的整数，表示左子树节点和左子树节点间进行集合运算。•装配操作是将两个体素并列在一起，成为一个整体，而每个体素本身仍保持原状。•节点的坐标变换域存储该节点所表示物体在进行新的集合运算前所作的坐标变换信息。物体的CSG树表示CSG树是无二义性的，但不是唯一的，它的定义域取决于其所用体素以及所允许的几何变换和正则集合运算算子。物体的CSG树表示CSG树表示具有以下优点：①数据结构比较简单，数据量比较小，内部数据的管理比较容易。②CSG表示可方便地转换成边界（Brep）表示。③CSG方法表示的形体的形状，比较容易修改。但CSG树表示也如下的缺点：①对形体的表示受体素的种类和对体素操作的种类的限制，也就是说，CSG方法表示形体的覆盖域有较大的局限性。②对形体的局部操作不易实现，例如，不能对基本体素的交线倒圆角。③由于形体的边界几何元素（点、边、面）是隐含地表示在CSG中，故显示与绘制CSG表示的形体需要较长的时间。边界表示法物体的边界表示•边界表示法（Brep-BoundaryRepresentation）通过描述物体的边界来表示一个物体。•所谓的边界指的就是物体内部点与外部点的分界面，因此，定义了物体的边界，该物体也就被唯一地定义了。边界表示法边界表示法的一个很重要的特点是：描述物体的信息包括几何信息与拓朴信息两个方面•几何信息是指物体在欧氏空间中的位置、形状和大小；•拓扑信息是指拓扑元素(顶点、边和表面)的数量及其相互间的连接关系；•拓扑信息构成物体的“骨架”，而几何信息则犹如附着在这一“骨架”上的“肌肉”。边界表示法边界表示的数据结构•翼边数据结构：以边及其相关的环和棱边来组织数据结构。•半边数据结构：是对翼边数据结构的改进，多面体的边界表示在拓扑上分为5个层次，即体（Solid）←→面（Face）←→环（Loop）←→半边（HalfEdge）←顶点（Vertex）。半边数据结构边界表示法•欧拉公式：对于任意的简单多面体，其面（f）、边（e）、顶点（v）的数目满足：•在对形体的结构进行修改时，必须保证这个公式成立，才能够保证形体的有效性。-+=2vef边界表示法广义欧拉公式：对于任意的正则形体，引入形体的其他几个参数：形体所有面上的内孔总数（r）、穿透形体的孔洞数（h）和形体非连通部分总数（s），则形体满足公式：-+=2(-)+vefshr欧拉操作•欧拉公式给出了形体的点、边、面、体、孔、洞数目之间的关系，在对形体的结构进行修改时，必须保证这个公式成立，才能够保证形体的有效性。•由此而构造出一套操作，来完成对形体部分几何元素的修改，修改过程中保证各几何元素的数目保持这个关系式不变，这一套操作就是欧拉操作。扫描表示扫描（Sweep）表示是基于一个基体（一般是一个封闭的平面轮廓）沿某一路径运动而产生形体。扫描表示需要两个分量：•被运动的基体；•基体运动的路径；•如果是变截面的扫描，还要给出截面的变化规律。扫描表示有3种扫描方式：•平移Sweep•旋转Sweep•广义Sweep平移Sweep将物体A沿着轨迹P平移得到物体B，称B为sweep体平移sweep----将一个二维区域沿着一个矢量方向推移。旋转Sweep将一个二维区域绕旋转轴旋转一周。广义Sweep广义sweep•任意物体沿着任意轨迹推移；•推移过程中物体可以变形。八叉树法三维物体的八叉树表示是一种层次数据结构，它首先在三维空间中定义一个能够包含所表示物体的立方体，且立方体的3条棱边分别与x、y、z轴平行，边长为2n。•若立方体内空间完全由所表示的物体所占据，则物体可用这个立方体予以表示，否则将立方体等分为8个小块，每块仍为一个子立方体，其边长为原立方体边长的1/2。将这8个子立方体依次编号为0，1，2，…，7，并对每一个子立方体重复上述分割过程。若子立方体的体内空间全部被所表示的物体占据，则为“满”；•若它与所表示物体无交，则为“空”；该子立方体可停止分解，否则就继续分割下去，直至子立方体的边长为单位长。依此方式，物体在计算机内可表示为一棵八叉树。由上述可以看出，八叉树表示形式是一种近似方法。八叉树法八叉树表示法优点主要是：①形体表示的数据结构简单。②简化了形体的集合运算。③简化了隐藏线（或面）的消除。④分析算法适合于并行处理。八叉树表示的缺点也是明显的，主要是占用的存储多，只能近似表示形体，以及不易获取形体的边界信息等。分型几何方法—自然景物的模拟分形指的是数学上的一类几何形体，在任意尺度上都具有复杂并且精细的结构。一般来说分形几何体都是自相似的，即图形的每一个局部都可以被看作是整体图形的一个缩小的复本。分形造型的常用模型•随机插值模型•粒子系统模型•正规文法模型•迭代函数系统模型随机插值模型•模型不是事先决定各种图素和尺度，而是用一个随机过程的采样路径作为构造模型的手段。•构造二维海岸线的模型可以选择控制大致形状的若干初始点在相邻两点构成的线段上取其中点，并沿垂直连线方向随机偏移一个距离，再将偏移后的点与该线段两端点分别连成两个线段。这样下去可得到一条曲折的有无穷细节回归的海岸线。粒子系统模型•它是用大量的粒子图元来描述景物的。•粒子可以随时间推移发生位置和形态的变化。每个粒子的位置、取向及动力学性质都是由一组预先定义的随机过程来说明的。正规文法模型•基本思想是用正规文法生成结构性强的植物的拓扑结构，再通过进一步几何解释来形成逼真的画面。迭代函数系统模型迭代函数系统是以下述方式工作的：取空间