第4章 造型技术 提出问题 如何在计算机中建立恰当的模型表示不同图形对象 第4章 造型技术 提出问题 如何在计算机中建立恰当的模型表示不同图形对象 如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快 2019/1/18 华中理工大学计算机学院 陆枫 99-7

把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。 有两类图形对象： 规则对象：几何造型、几何模型 不规则对象 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.1 基本概念 4.1.1 基本图形元素与段的概念 基本图形元素：图素或图元、体素 4.1 基本概念 4.1.1 基本图形元素与段的概念 基本图形元素：图素或图元、体素 图素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

体素是三维空间中可以用有限个尺寸参数定位和定形的体，常有三种定义形式： (1)从实际形体中选择出来，可用一些确定的尺寸参数控制其最终位置和形状的一组单元实体 (2)由参数定义的一条(或一组)轮廓线沿一条(或一组)空间参数曲线作扫描运动而产生的形体。 (3)用代数半空间定义的形体 2019/1/18 华中理工大学计算机学院 陆枫 99-7

段是指具有逻辑意义的有限个图素（或体素）及其附加属性的集合， 段（也称图段、结构和对象） 段是指具有逻辑意义的有限个图素（或体素）及其附加属性的集合， 2019/1/18 华中理工大学计算机学院 陆枫 99-7

图素或体素用数据来描述，段用规则来描述。 段可以嵌套 段一般具有三个特性：可见性、醒目性、可选择性。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.1.2 几何信息与拓扑信息 图形对象及构成它的点、线、面的位置、相互间关系和几何尺寸等都是图形信息； 4.1.2 几何信息与拓扑信息 图形对象及构成它的点、线、面的位置、相互间关系和几何尺寸等都是图形信息； 表示图形对象的线型、颜色、亮度以及供模拟、分析用的质量、比重、体积等数据，是有关对象的非图形信息。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。 图形信息又包括： 几何信息：形体在欧氏空间中的位置和大小 拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。 1. 几何信息 (1)几何分量的数学表示 2019/1/18 华中理工大学计算机学院 陆枫 99-7

(2)几何分量之间的相互关系 2019/1/18 华中理工大学计算机学院 陆枫 99-7

平面立体的几何分量之间一共有九种拓扑关系 几何信息的二义性 2. 拓朴信息 平面立体的几何分量之间一共有九种拓扑关系 2019/1/18 华中理工大学计算机学院 陆枫 99-7

刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。 拓扑运动：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。 拓扑等价、拓扑性质 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.1.3 坐标系 2019/1/18 华中理工大学计算机学院 陆枫 99-7

点是0维几何元素，分端点、交点、切点和孤立点等。 4.1.4 几何元素 点是0维几何元素，分端点、交点、切点和孤立点等。 在自由曲线面的描述中常用三种类型的点： 控制点、型值点、插值点 边是1维几何元素，是两个邻面（正则形体）或多个邻面（非正则形体）的交界。直线边、曲线边 2019/1/18 华中理工大学计算机学院 陆枫 99-7

面是2维几何元素，是形体上一个有限、非零的区域，由一个外环和若干个内环界定其范围。 一个面可以无内环，但必须有一个且只有一个外环。 面有方向性 2019/1/18 华中理工大学计算机学院 陆枫 99-7

环是有序、有向边（真线段或曲线段）组成的面的封闭边界。 环中的边不能相交，相邻两条边共享一个端点 确定面的最大外边界的环称之为外环 确定面中内孔或凸台边界的环称之为内环 在面上沿一个环前进，其左侧总是面内，右侧总是面外。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

体是3维几何元素，由封闭表面围成空间，也是欧氏空间R3中非空、有界的封闭子集，其边界是有限面的并集。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.1.5 实体的定义 2019/1/18 华中理工大学计算机学院 陆枫 99-7

三维空间中的物体是一个内部连通的三维点集，是由其内部的点集及紧紧包着这些点的表皮组成的。 客观存在的三维形体具有这样一些性质： (1)刚性 (2)维数的一致性 (3)占据有限的空间 (4)边界的确定性 (5)封闭性 三维空间中的物体是一个内部连通的三维点集，是由其内部的点集及紧紧包着这些点的表皮组成的。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

利用正则集的概念来定义上述的三维有效物体： 点的领域：如果P是点集S的一个元素，那么点P的以R（R>0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。 内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。 边界点 2019/1/18 华中理工大学计算机学院 陆枫 99-7

定义点集的正则运算r运算为： 正则运算即为先对物体取内点再取闭包的运算。r·A称为A的正则集。

2019/1/18 华中理工大学计算机学院 陆枫 99-7

二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。 该定义条件可检测 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.1.6 正则集合运算 有效实体的封闭性 把能够产生正则形体的集合运算称为正则集合运算 2019/1/18 4.1.6 正则集合运算 有效实体的封闭性 把能够产生正则形体的集合运算称为正则集合运算 2019/1/18 华中理工大学计算机学院 陆枫 99-7

2019/1/18 华中理工大学计算机学院 陆枫 99-7

点的领域，即集合S在点P附近的局部几何性质： 当且仅当P的领域为满时，P在S之内； 当且仅当P的领域为空时，P在S之外； 有两种方法实现正则运算 间接方式： 点的领域，即集合S在点P附近的局部几何性质： 当且仅当P的领域为满时，P在S之内； 当且仅当P的领域为空时，P在S之外； 当且仅当P的领域既不满也不空时，P在S的边界上。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

2019/1/18 华中理工大学计算机学院 陆枫 99-7

在三维空间中，给定一个正则形体S，空间点集被分为三个子集： 直接方式： 在三维空间中，给定一个正则形体S，空间点集被分为三个子集： S的内部点集 S的边界点集 S之外的点集 2019/1/18 华中理工大学计算机学院 陆枫 99-7

若给定一个正则形体S及一个有界面G，则G相对于S的分类函数可为： 分类函数： 若给定一个正则形体S及一个有界面G，则G相对于S的分类函数可为： C(S,G)={G in S, G out S, G on S} 其中， 2019/1/18 华中理工大学计算机学院 陆枫 99-7

用-G表示有界面G的反向面。即，如果有界面G在P点的法向为NP(G)，则有界面-G在P点的法向就是-NP(G)。 于是：G on S={G shared (b·S), G shared (-b·S)} 其中， 2019/1/18 华中理工大学计算机学院 陆枫 99-7

C(S,G)={G in S, G out S, G shared (b·S), G shared (-b·S)} 正则集合算子 则G相对于S的分类函数C(S,G)可为： C(S,G)={G in S, G out S, G shared (b·S), G shared (-b·S)} 正则集合算子 定义三个正则集合算子关于边界面的表达式： 2019/1/18 华中理工大学计算机学院 陆枫 99-7

2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.1.7 平面多面体与欧拉公式 平面多面体是表面由平面多边形构成的三维物体。 简单多面体指与球拓扑等价的那些多面体。 4.1.7 平面多面体与欧拉公式 平面多面体是表面由平面多边形构成的三维物体。 简单多面体指与球拓扑等价的那些多面体。 欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下关系：V-E+F=2。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

2019/1/18 华中理工大学计算机学院 陆枫 99-7

令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G） 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.2 三维形体的表示 线框模型 线框模型存在着几个缺陷： 二义性 2019/1/18 华中理工大学计算机学院 陆枫 99-7

容易构造出无效形体 2019/1/18 华中理工大学计算机学院 陆枫 99-7

不能正确表示曲面信息。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

无法进行图形的线面消隐。  加重用户的输入负担 难以保证数据的统一性和有效性。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

边界表示（Boundary representation, B-reps） 构造实体几何表示 实体模型（实体造型技术） 可以将实体模型的表示大致分为三类： 边界表示（Boundary representation, B-reps） 构造实体几何表示 空间分割（Space-partitioning）表示 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.2.1 多边形表面模型 边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。

1. 多边形表 几何表 属性表 例如：顶点表、边表和多边形表。 为图4-17所示的四面体建立的三张表如下： 2019/1/18 1. 多边形表 几何表 属性表  例如：顶点表、边表和多边形表。 为图4-17所示的四面体建立的三张表如下： 2019/1/18 华中理工大学计算机学院 陆枫 99-7

顶点表 边表 面表 A A,B B B,C C C,A D A,D C,D x1,y1,z1 x2,y2,z2 x3,y3,z3   边表 面表 A x1,y1,z1 AB A,B ABC AB,BC,AC B x2,y2,z2 BC B,C ABD AB,BD,AD C x3,y3,z3 CA C,A BCD BC,CD,BD D x4,y4,z4 AD A,D ACD AC,CD,AD CD C,D 2019/1/18 华中理工大学计算机学院 陆枫 99-7

例如，翼边结构表示（Winged Edges Structure） 表示其拓扑信息  例如，翼边结构表示（Winged Edges Structure） 2019/1/18 华中理工大学计算机学院 陆枫 99-7

2. 平面方程 可以利用平面方程： 求得平面的法向量 鉴别空间上的点与物体平面的位置关系。 判别点在面的内部或外部 2019/1/18 2. 平面方程 可以利用平面方程： 求得平面的法向量 鉴别空间上的点与物体平面的位置关系。 判别点在面的内部或外部 2019/1/18 华中理工大学计算机学院 陆枫 99-7

三维形体的曲面边界通常用多边形网格（polygon mesh）的拼接来模拟。 3. 多边形网格 三维形体的曲面边界通常用多边形网格（polygon mesh）的拼接来模拟。 三角形带、四边形网格 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.2.2 扫描表示（sweep representation） 包含两个要素： 一是作扫描运动的基本图形； 二是扫描运动的方式。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

扫描运动的方式有： 旋转扫描 非圆形路径扫描 广义扫描法 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.2.3 构造实体几何法 构造实体几何法（CSG，Constructive Solid Geometry） 4.2.3 构造实体几何法 构造实体几何法（CSG，Constructive Solid Geometry） 由两个实体间的并、交或差操作生成新的实体。

在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述： 树的叶子 树的非终端结点 二叉树根结点 2019/1/18 华中理工大学计算机学院 陆枫 99-7

解决：光线投射（Ray-casting）算法 构造实体几何法的优点： 可以构造出多种不同的符合需要的实体。 问题： 求交困难 CSG树不能显式地表示形体的边界 解决：光线投射（Ray-casting）算法 2019/1/18 华中理工大学计算机学院 陆枫 99-7

光线投射（Ray-casting）算法 核心思想： 2019/1/18 华中理工大学计算机学院 陆枫 99-7

1)将射线与CSG树中的所有基本体素求交，求出所有的交点。 具体算法是： 1)将射线与CSG树中的所有基本体素求交，求出所有的交点。 2)将所有交点相对于CSG树表示的物体进行分类，确定位于物体边界上的那部分交点。 3)对所有位于物体边界上的交点计算它们在射线上的参数值并进行排序，确定距离最近的交点。得到其所在基本体素表面的法矢量。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.2.4 空间位置枚举表示 空间位置枚举表示法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对象。 二维情况，常用二维数组存放。 三维情况下，常用三维数组p[i][j][k]来存放。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.2.5 八叉树 八叉树（octrees）又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体。 4.2.5 八叉树 八叉树（octrees）又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

四叉树 2019/1/18 华中理工大学计算机学院 陆枫 99-7

八叉树 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.2.6 BSP树 二叉空间分割（binary space partitioning，BSP）方法每次将一实体用任一位置和任一方向的平面分为二部分。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.3 非规则对象的表示 基于分数维理论的随机模型 基于文法的模型 粒子系统模型 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.3.1 分形几何(fractal geometry) 分形几何物体具有一个基本特征：无限的自相似性。 无限的自相似性是指物体的整体和局部之间细节的无限重现。 分形物体的描述又包含： 分形维数，又称分数维数 生成过程：初始生成元（initiator）、生成元（genenator） 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.3.2 形状语法 形状语法（shape grammars）：给定一组产生式规则，形状设计者可以在从给定初始物体到最终物体结构的每一次变换中应用不同的规则。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.3.3 微粒系统 用于模拟自然景物或模拟其它非规则形状物体展示“流体”性质的一个方法是微粒系统（particle systems）。 4.3.3 微粒系统 用于模拟自然景物或模拟其它非规则形状物体展示“流体”性质的一个方法是微粒系统（particle systems）。 这一方法尤其擅长描述随时间变化的物体。 微粒运动的模拟方式：随机过程模拟、运动路径模拟、力学模拟 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.3.4 基于物理的建模 基于物理的建模方法：描述了物体在内外力相互作用下的行为。 4.3.4 基于物理的建模 基于物理的建模方法：描述了物体在内外力相互作用下的行为。 通常用一组网格结点来逼近物体。网格结点间取为柔性连接，再考虑贯穿物体网格的力传递。 基于力学方程的动画描述比基于运动学方程的描述产生的运动更真实。实例 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.3.5 数据场的可视化 科技计算可视化（scientific visualization）指的是运用计算机图形学和图象处理技术，将科学计算过程中及计算结果的数据转换为图形及图象在屏幕上显示出来并进行交互处理的理论、方法和技术。   有三种不同类型的数据需要实现可视化： 2019/1/18 华中理工大学计算机学院 陆枫 99-7

标量：若对每一个直角坐标系oxyz有一个量，它在坐标变换时满足下式，即保持其值不变，则此量定义了一个标量。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

矢量：对于每一个直角坐标系ox1x2x3来说有三个量x1,x2,x3，它们可根据下式变换到另一个坐标系ox1'x2'x3'，则此时三个量定义了一个矢量。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

二阶张量：如果对每一个直角坐标系ox1x2x3，有9个量Xij(i=1,2,3;j=1,2,3)，它可以按照以张量形式表示的下述公式转换为另一个直角坐标系中的9个量Xij'(i=1,2,3;j=1,2,3)，则这9个量定义了一个二阶张量。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

显然，二阶张量可以表示为一个3×3矩阵： 2019/1/18 华中理工大学计算机学院 陆枫 99-7

当n=0时，张量的分量只有1个，它是一个标量。因此，可将标量视为零阶张量。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

对于分布在三维空间的体数据来说，有两类不同的可视化算法： 一是首先由三维空间数据场构造出中间几何图元（如曲面、平面等），然后再由传统的计算机图形学技术实现面绘制。 体绘制（volume rendering）算法，或称为直接体绘制（direct volume rendering）算法。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.4 图形的层次结构 4.4.1 段的层次概念 2019/1/18 华中理工大学计算机学院 陆枫 99-7

4.4.2 层次结构的实现 系统的层次式模型可通过将一个图段嵌套到另一个图段中形成树形图段来创建。 4.4.2 层次结构的实现 系统的层次式模型可通过将一个图段嵌套到另一个图段中形成树形图段来创建。 在结构层次中，需要将在建模坐标系中定义的基本图素和段放在用户坐标系中来建立引用。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

它把功能相同的部分归类，并把它们绘在一层上。 不同的层可用不同的颜色及线型 不同层可一起显示，也可任挑几个层来显示 层不再嵌套。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

习题 1．名词解释：造型技术、规则对象、不规则对象、几何造型、几何模型、数据放大技术、图元、图素、体素、段、图形信息、非图形信息、几何信息、拓扑信息、刚体运动、拓扑运动、拓扑等价、建模坐标系、用户坐标系、观察坐标系、规格化设备坐标系、设备坐标系、控制点、型值点、插值点、正则集、二维流形、非二维流形、翼边结构表示、多边形网格、构造实体几何法、空间位置枚举法、八叉树、BSP树、无限自相似性、层 2019/1/18 华中理工大学计算机学院 陆枫 99-7

2．欧氏空间中的几何元素包含那些内容，如何表示。 3．利用正则集的概念简述实体的定义。 4．用间接方式如何实现正则集合运算，用直接方式呢？ 5．简单多面体的欧拉公式满足何条件？复杂多面体的呢？ 6．试比较线框模型和实体模型的优缺点。 7．简述有哪些方法来实现多边形表面模型。 8．简述三维形体的扫描表示方法。 9．简述如何利用CSG树来表示三维形体。 2019/1/18 华中理工大学计算机学院 陆枫 99-7

10．举例说明如何用空间位置枚举法表示二维形体。 11．举例说明如何用四叉树表示二维形体。 12．试说明何谓分形几何。 13．利用形状语法表示三维形体有何特征。 14．利用微粒系统表示三维形体有何特征。 15．基于物体的建模通常应用在哪些方面。 16．数据场的可视化可应用在哪些方面。 17．图形系统中为什么要建立图形对象的层次结构。 2019/1/18 华中理工大学计算机学院 陆枫 99-7