计算机图形学第十一章三维形体的表示高级课堂.ppt

Lecture 11Lecture 11三维形体的表示三维形体的表示三维形体的表示三维形体的表示概述概述 三维造型技术是一项研究在计算机中，如何建立恰当三维造型技术是一项研究在计算机中，如何建立恰当的模型来表示自然界中形态丰富的三维物体的技术的模型来表示自然界中形态丰富的三维物体的技术 三维造型技术根据造型对象分成三类：三维造型技术根据造型对象分成三类： •第第一一类类是是曲曲面面造造型型，，这这种种造造型型方方法法研研究究在在计计算算机机内内如如何何描述一张曲面描述一张曲面•第第二二类类是是立立体体造造型型方方法法，，它它研研究究如如何何在在计计算算机机内内定定义义、、表示一个三维物体表示一个三维物体•第第三三类类造造型型方方法法是是自自然然景景物物模模拟拟，，研研究究如如何何在在计计算算机机内内模拟自然景物，如云、水流、树等等模拟自然景物，如云、水流、树等等概述概述 三维几何造型现已开始被广泛地应用在工业生产及艺术造三维几何造型现已开始被广泛地应用在工业生产及艺术造三维几何造型现已开始被广泛地应用在工业生产及艺术造三维几何造型现已开始被广泛地应用在工业生产及艺术造型的各个领域。

型的各个领域型的各个领域型的各个领域•机械行业机械行业机械行业机械行业• •设计方面，几何造型方法可以逼真地反映物体的外观，检查零件之间的设计方面，几何造型方法可以逼真地反映物体的外观，检查零件之间的装配关系，高效、准确地生成生产图纸；装配关系，高效、准确地生成生产图纸；• •分析计算方面，它可以精确地计算出零件的质量、质心、转动惯量、表分析计算方面，它可以精确地计算出零件的质量、质心、转动惯量、表面积等物性参数；面积等物性参数；• •计算机辅助制造时，可以引用几何造型的结果，直接规划数控加工的刀计算机辅助制造时，可以引用几何造型的结果，直接规划数控加工的刀具轨迹；具轨迹；• •运动分析方面，几何造型系统可以完成机械手的动作规划、运动模拟以运动分析方面，几何造型系统可以完成机械手的动作规划、运动模拟以及零件间的干涉检查等及零件间的干涉检查等概述概述•计算机艺术、动画片制作、模拟仿真、计算机视觉、机器人等计算机艺术、动画片制作、模拟仿真、计算机视觉、机器人等计算机艺术、动画片制作、模拟仿真、计算机视觉、机器人等计算机艺术、动画片制作、模拟仿真、计算机视觉、机器人等领域都把几何造型作为基础。

领域都把几何造型作为基础领域都把几何造型作为基础领域都把几何造型作为基础•利用三维几何造型技术，既可产生已有物体的真实模型，也可利用三维几何造型技术，既可产生已有物体的真实模型，也可利用三维几何造型技术，既可产生已有物体的真实模型，也可利用三维几何造型技术，既可产生已有物体的真实模型，也可产生人们头脑中的某种设计想象或艺术模型产生人们头脑中的某种设计想象或艺术模型产生人们头脑中的某种设计想象或艺术模型产生人们头脑中的某种设计想象或艺术模型 形体的表示形体的表示 在计算机中表示形体的方法通常有三种：在计算机中表示形体的方法通常有三种：•线框模型线框模型•表面模型表面模型•实体模型实体模型 线框模型线框模型 线框模型采用三维形体的全部顶点及边的集合来描述线框模型采用三维形体的全部顶点及边的集合来描述三维形体，即用三维形体的顶点表和边表两个表的数据三维形体，即用三维形体的顶点表和边表两个表的数据结构来表示三维模型结构来表示三维模型 线框模型线框模型 线框模型的主要优点是结构简单，处理容易，框模型的主要优点是结构简单，处理容易，框模型的主要优点是结构简单，处理容易，框模型的主要优点是结构简单，处理容易，在CPUCPU时间及存储方面时间及存储方面时间及存储方面时间及存储方面开销低开销低开销低开销低 。

线框模型也有非常显著的缺点线框模型也有非常显著的缺点线框模型也有非常显著的缺点线框模型也有非常显著的缺点• •不能表示表面含有曲面的物体；不能表示表面含有曲面的物体；不能表示表面含有曲面的物体；不能表示表面含有曲面的物体；• •不能明确地定义给定点与物体之间的关系，应用范围受到了很大的限制不能明确地定义给定点与物体之间的关系，应用范围受到了很大的限制不能明确地定义给定点与物体之间的关系，应用范围受到了很大的限制不能明确地定义给定点与物体之间的关系，应用范围受到了很大的限制• •线框模型容易出现二义性，对于一个线框模型，可以有不同的理解线框模型容易出现二义性，对于一个线框模型，可以有不同的理解线框模型容易出现二义性，对于一个线框模型，可以有不同的理解线框模型容易出现二义性，对于一个线框模型，可以有不同的理解表面模型表面模型 表面模型框模型的表面模型框模型的基础上，增加了物体中的基础上，增加了物体中的面的信息，用面的集合来面的信息，用面的集合来表示物体，而用环来定义表示物体，而用环来定义面的边界面的边界. 表面模型表面模型•表面模型克服了线框模型的很多缺点，比较完整地定义了三维表面模型克服了线框模型的很多缺点，比较完整地定义了三维表面模型克服了线框模型的很多缺点，比较完整地定义了三维表面模型克服了线框模型的很多缺点，比较完整地定义了三维立体的表面，因而其造型体的覆盖面较广，无论解析的或非解立体的表面，因而其造型体的覆盖面较广，无论解析的或非解立体的表面，因而其造型体的覆盖面较广，无论解析的或非解立体的表面，因而其造型体的覆盖面较广，无论解析的或非解析的目标均可用表面模型来描述。

析的目标均可用表面模型来描述析的目标均可用表面模型来描述析的目标均可用表面模型来描述•表面模型又分为平面模型和曲面模型两种前者以多边形网格表面模型又分为平面模型和曲面模型两种前者以多边形网格表面模型又分为平面模型和曲面模型两种前者以多边形网格表面模型又分为平面模型和曲面模型两种前者以多边形网格为基础由上述顶点表、边表和面表就可构成平面立体的平面为基础由上述顶点表、边表和面表就可构成平面立体的平面为基础由上述顶点表、边表和面表就可构成平面立体的平面为基础由上述顶点表、边表和面表就可构成平面立体的平面模型后者是以参数曲面块为基础后者是以参数曲面块为基础后者是以参数曲面块为基础后者是以参数曲面块为基础•表面模型也存在一些不足，这主要是它只能表示物体的表面边表面模型也存在一些不足，这主要是它只能表示物体的表面边表面模型也存在一些不足，这主要是它只能表示物体的表面边表面模型也存在一些不足，这主要是它只能表示物体的表面边界，而没有表达出真实体属性因此，也就无法切开表示物体界，而没有表达出真实体属性因此，也就无法切开表示物体界，而没有表达出真实体属性因此，也就无法切开表示物体界，而没有表达出真实体属性。

因此，也就无法切开表示物体的内部结构由此就很难确认一个表面模型表示的三维图形是的内部结构由此就很难确认一个表面模型表示的三维图形是的内部结构由此就很难确认一个表面模型表示的三维图形是的内部结构由此就很难确认一个表面模型表示的三维图形是一个实体还是一个空壳一个实体还是一个空壳一个实体还是一个空壳一个实体还是一个空壳 实体模型实体模型 • •实体模型使用有向边的右手法则来确定所在面的外法线方向，即用右手实体模型使用有向边的右手法则来确定所在面的外法线方向，即用右手实体模型使用有向边的右手法则来确定所在面的外法线方向，即用右手实体模型使用有向边的右手法则来确定所在面的外法线方向，即用右手沿边的顺序方向握住，大拇指所指的方向为该面的外法线方向沿边的顺序方向握住，大拇指所指的方向为该面的外法线方向沿边的顺序方向握住，大拇指所指的方向为该面的外法线方向沿边的顺序方向握住，大拇指所指的方向为该面的外法线方向• •数据结构不仅记录了全部的几何信息，而且还记录了所有的点、线、面、数据结构不仅记录了全部的几何信息，而且还记录了所有的点、线、面、数据结构不仅记录了全部的几何信息，而且还记录了所有的点、线、面、数据结构不仅记录了全部的几何信息，而且还记录了所有的点、线、面、体的拓扑信息。

这就是实体模型与线框模型或表面模型的根本区别实体的拓扑信息这就是实体模型与线框模型或表面模型的根本区别实体的拓扑信息这就是实体模型与线框模型或表面模型的根本区别实体的拓扑信息这就是实体模型与线框模型或表面模型的根本区别实体模型的构造方法通常使用体素，经集合论中的交、并、差运算构成复体模型的构造方法通常使用体素，经集合论中的交、并、差运算构成复体模型的构造方法通常使用体素，经集合论中的交、并、差运算构成复体模型的构造方法通常使用体素，经集合论中的交、并、差运算构成复杂形体 实体的定义实体的定义 实体就是有效的物体，亦即客观世界中确实存在的物实体就是有效的物体，亦即客观世界中确实存在的物体比如，下图所示的带有悬挂面的立方体就不是实体，体比如，下图所示的带有悬挂面的立方体就不是实体，在客观世界中也不存在这样的物体在客观世界中也不存在这样的物体实体的定义实体的定义 作为实体或者有效的物体应该满足以下的条件：作为实体或者有效的物体应该满足以下的条件：作为实体或者有效的物体应该满足以下的条件：作为实体或者有效的物体应该满足以下的条件：①①①①刚刚刚刚性性性性一一一一个个个个实实实实体体体体必必必必须须须须具具具具有有有有一一一一定定定定的的的的形形形形状状状状（（（（流流流流体体体体不不不不属属属属于于于于实实实实体体体体造造造造型型型型技术描述的对象）。

技术描述的对象）技术描述的对象）技术描述的对象）②②②②维维维维数数数数一一一一致致致致性性性性在在在在三三三三维维维维空空空空间间间间中中中中，，，，一一一一个个个个实实实实体体体体的的的的各各各各个个个个部部部部分分分分必必必必须须须须都都都都是是是是三维的，不能存在悬挂的、孤立的边界三维的，不能存在悬挂的、孤立的边界三维的，不能存在悬挂的、孤立的边界三维的，不能存在悬挂的、孤立的边界③③③③有限性一个实体必须占有有限的空间一个实体必须占有有限的空间一个实体必须占有有限的空间一个实体必须占有有限的空间④④④④边界的确定性根据实体的边界可以确定实体的内、外部边界的确定性根据实体的边界可以确定实体的内、外部边界的确定性根据实体的边界可以确定实体的内、外部边界的确定性根据实体的边界可以确定实体的内、外部⑤⑤⑤⑤封闭性经过一系列的刚体运动及任意序列的集合运算之后，封闭性经过一系列的刚体运动及任意序列的集合运算之后，封闭性经过一系列的刚体运动及任意序列的集合运算之后，封闭性经过一系列的刚体运动及任意序列的集合运算之后，仍然是有效的实体仍然是有效的实体仍然是有效的实体仍然是有效的实体 实体的定义实体的定义 一个实体的表面必须具备以下的性质：一个实体的表面必须具备以下的性质：一个实体的表面必须具备以下的性质：一个实体的表面必须具备以下的性质：①①①①连通性。

实体表面上任意两点都可用该表面上的一条路径连接起来实体表面上任意两点都可用该表面上的一条路径连接起来实体表面上任意两点都可用该表面上的一条路径连接起来实体表面上任意两点都可用该表面上的一条路径连接起来②②②②有有有有界界界界性性性性一一一一个个个个实实实实体体体体的的的的表表表表面面面面把把把把空空空空间间间间分分分分为为为为互互互互不不不不连连连连通通通通的的的的两两两两部部部部分分分分，，，，其其其其中中中中实实实实体体体体内内内内的部分是有限的的部分是有限的的部分是有限的的部分是有限的③③③③非自相交性一个实体的表面不可自相交非自相交性一个实体的表面不可自相交非自相交性一个实体的表面不可自相交非自相交性一个实体的表面不可自相交④④④④可定向性一个实体的表面两侧可明确定义出实体的内侧和外侧可定向性一个实体的表面两侧可明确定义出实体的内侧和外侧可定向性一个实体的表面两侧可明确定义出实体的内侧和外侧可定向性一个实体的表面两侧可明确定义出实体的内侧和外侧⑤⑤⑤⑤封封封封闭闭闭闭性性性性对对对对多多多多面面面面体体体体而而而而言言言言，，，，一一一一个个个个实实实实体体体体表表表表面面面面的的的的封封封封闭闭闭闭性性性性是是是是由由由由表表表表面面面面上上上上多多多多边边边边形形形形网网网网格格格格各各各各元元元元素素素素的的的的拓拓拓拓扑扑扑扑关关关关系系系系确确确确定定定定的的的的，，，，即即即即每每每每条条条条边边边边连连连连接接接接且且且且仅仅仅仅连连连连接接接接两两两两个个个个面面面面，，，，每每每每条条条条边边边边有有有有且仅有两个端点。

且仅有两个端点且仅有两个端点且仅有两个端点实体的定义实体的定义 从从点点集集拓拓扑扑角角度度给给出出实实体体的的定定义义将将三三维维物物体体看看作作是是空间中点的集合，它由内点与边界点共同组成空间中点的集合，它由内点与边界点共同组成•内内点点是是指指点点集集中中的的这这样样一一些些点点，，它它们们具具有有完完全全包包含含于于该该点集的充分小的邻域点集的充分小的邻域•边界点就是指那些不具备此性质的点集中的点边界点就是指那些不具备此性质的点集中的点 三维物体三维物体A可表示为：可表示为： bA为物体为物体A的边界点集，的边界点集，iA为物体为物体A的内部点集的内部点集 实体的定义实体的定义定义点集的正则运算定义点集的正则运算定义点集的正则运算定义点集的正则运算r r如下：如下：如下：如下： i i为取内点运算；为取内点运算；为取内点运算；为取内点运算；c c为取闭包运算；为取闭包运算；为取闭包运算；为取闭包运算；A A为一个点集那么为一个点集那么为一个点集那么为一个点集那么i·Ai·A即即即即为为为为A A的全体内点组成的集合，称为的全体内点组成的集合，称为的全体内点组成的集合，称为的全体内点组成的集合，称为A A的内部，它是一个开集。

的内部，它是一个开集的内部，它是一个开集的内部，它是一个开集c·i·Ac·i·A为为为为A A的内部的闭包，是的内部的闭包，是的内部的闭包，是的内部的闭包，是i·Ai·A与其边界点的并集，它本身是一与其边界点的并集，它本身是一与其边界点的并集，它本身是一与其边界点的并集，它本身是一个闭集 实体的定义实体的定义 正则点集不一定是实体如下图所示的物体，它是正则点集，但它正则点集不一定是实体如下图所示的物体，它是正则点集，但它正则点集不一定是实体如下图所示的物体，它是正则点集，但它正则点集不一定是实体如下图所示的物体，它是正则点集，但它不是有效的物体为了得到有效的物体，我们必须排除下图所示的情况，不是有效的物体为了得到有效的物体，我们必须排除下图所示的情况，不是有效的物体为了得到有效的物体，我们必须排除下图所示的情况，不是有效的物体为了得到有效的物体，我们必须排除下图所示的情况，在此我们引入二维流形的概念所谓二维流形是指对于实体表面上的任在此我们引入二维流形的概念所谓二维流形是指对于实体表面上的任在此我们引入二维流形的概念所谓二维流形是指对于实体表面上的任在此我们引入二维流形的概念。

所谓二维流形是指对于实体表面上的任何一点，都可以找到一个围绕着它的任意小的邻域，该邻域在拓扑上与何一点，都可以找到一个围绕着它的任意小的邻域，该邻域在拓扑上与何一点，都可以找到一个围绕着它的任意小的邻域，该邻域在拓扑上与何一点，都可以找到一个围绕着它的任意小的邻域，该邻域在拓扑上与平面上的一个圆盘是等价的平面上的一个圆盘是等价的平面上的一个圆盘是等价的平面上的一个圆盘是等价的 实体的定义实体的定义 有有了了二二维维流流形形的的概概念念之之后后，，我我们们可可以以这这样样来来描描述述实实体体：：对对于于一一个个占占据据有有限限空空间间的的正正则则点点集集，，如如果果其其表表面面是是二维流形，则该正则点集为实体二维流形，则该正则点集为实体(有效物体有效物体)正则集合运算正则集合运算 能产生正则几何体的集合运算称为正则集合运算正则集合运算保证能产生正则几何体的集合运算称为正则集合运算正则集合运算保证能产生正则几何体的集合运算称为正则集合运算正则集合运算保证能产生正则几何体的集合运算称为正则集合运算正则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面集合运算的结果仍是一个正则形体，即丢弃悬边、悬面集合运算的结果仍是一个正则形体，即丢弃悬边、悬面集合运算的结果仍是一个正则形体，即丢弃悬边、悬面 。

正则集合运算与传统集合运算的区别主要是在对产生结果的边界面的正则集合运算与传统集合运算的区别主要是在对产生结果的边界面的正则集合运算与传统集合运算的区别主要是在对产生结果的边界面的正则集合运算与传统集合运算的区别主要是在对产生结果的边界面的处理上，其内部点是一致的处理上，其内部点是一致的处理上，其内部点是一致的处理上，其内部点是一致的 正则集合运算正则集合运算 在正则集合运算中，要考虑如何消除或不产生悬点，悬边和悬面，在在正则集合运算中，要考虑如何消除或不产生悬点，悬边和悬面，在在正则集合运算中，要考虑如何消除或不产生悬点，悬边和悬面，在在正则集合运算中，要考虑如何消除或不产生悬点，悬边和悬面，在实体造型中，实现正则集合运算有两种方法：间接法和直接法实体造型中，实现正则集合运算有两种方法：间接法和直接法实体造型中，实现正则集合运算有两种方法：间接法和直接法实体造型中，实现正则集合运算有两种方法：间接法和直接法• •间接法是先按普通集合运算求出结果，后用一些规则判断，消除不符合间接法是先按普通集合运算求出结果，后用一些规则判断，消除不符合间接法是先按普通集合运算求出结果，后用一些规则判断，消除不符合间接法是先按普通集合运算求出结果，后用一些规则判断，消除不符合正则几何定义的部分正则几何定义的部分正则几何定义的部分正则几何定义的部分( (即悬边、悬面等即悬边、悬面等即悬边、悬面等即悬边、悬面等) )，从而得到正则几何体；，从而得到正则几何体；，从而得到正则几何体；，从而得到正则几何体；• •直接法则是定义正则集合算子的表达式，用以直接得出符合正则几何体直接法则是定义正则集合算子的表达式，用以直接得出符合正则几何体直接法则是定义正则集合算子的表达式，用以直接得出符合正则几何体直接法则是定义正则集合算子的表达式，用以直接得出符合正则几何体定义的结果。

定义的结果定义的结果定义的结果 物体的物体的CSG树表示树表示 物物体体的的体体素素构构造造表表示示法法（（CSG，，Constructive Solid Geometry））是是用用两两个个物物体体间间的的并并、、交交、、差差正正则则集集合合运运算算操作生成一个新的物体的方法操作生成一个新的物体的方法•用用CSG法法时时，，实实体体的的构构造造过过程程是是集集合合运运算算的的过过程程这这个个过程可用二叉树结构表示，这种树称为过程可用二叉树结构表示，这种树称为CSG树 •树树的的叶叶节节点点表表示示体体素素或或带带有有几几何何变变换换参参数数的的体体素素，，非非终终止止节节点点表表示示施施加加于于其其子子节节点点的的正正则则集集合合算算子子，，或或称称布布尔尔算算子子树树的的根根节节点点表表示示集集合合运运算算的的最最终终结结果果，，也也即即希希望望得到的实体得到的实体 物体的物体的CSG树表示树表示 CSG树节点数据结构的一种组织方式树节点数据结构的一种组织方式 物体的物体的CSG树表示树表示•CSG树中的每一节点由操作码、坐标变换域、基本体素树中的每一节点由操作码、坐标变换域、基本体素指针、左子树、右子树等指针、左子树、右子树等5个域组成。

个域组成•操作码按约定方式取值当操作码为零时，表示该节点操作码按约定方式取值当操作码为零时，表示该节点为一基本体素，相应左、右子树指针取零对于非终节为一基本体素，相应左、右子树指针取零对于非终节点，操作码取约定的整数，表示左子树节点和左子树节点，操作码取约定的整数，表示左子树节点和左子树节点间进行集合运算点间进行集合运算•装配操作是将两个体素并列在一起，成为一个整体，而装配操作是将两个体素并列在一起，成为一个整体，而每个体素本身仍保持原状每个体素本身仍保持原状•节点的坐标变换域存储该节点所表示物体在进行新的集节点的坐标变换域存储该节点所表示物体在进行新的集合运算前所作的坐标变换信息合运算前所作的坐标变换信息 物体的物体的CSG树表示树表示 CSG树是无二义性的，但不是唯一的，它的定义域取树是无二义性的，但不是唯一的，它的定义域取决于其所用体素以及所允许的几何变换和正则集合运算决于其所用体素以及所允许的几何变换和正则集合运算算子 物体的物体的CSG树表示树表示CSGCSG树表示具有以下优点：树表示具有以下优点：树表示具有以下优点：树表示具有以下优点：①①①① 数据结构比较简单，数据量比较小，内部数据的管理比较容易。

数据结构比较简单，数据量比较小，内部数据的管理比较容易数据结构比较简单，数据量比较小，内部数据的管理比较容易数据结构比较简单，数据量比较小，内部数据的管理比较容易②②②② CSGCSG表示可方便地转换成边界（表示可方便地转换成边界（表示可方便地转换成边界（表示可方便地转换成边界（BrepBrep）表示③③③③ CSGCSG方法表示的形体的形状，比较容易修改方法表示的形体的形状，比较容易修改方法表示的形体的形状，比较容易修改方法表示的形体的形状，比较容易修改但但但但CSGCSG树表示也如下的缺点：树表示也如下的缺点：树表示也如下的缺点：树表示也如下的缺点：①①①① 对对对对形形形形体体体体的的的的表表表表示示示示受受受受体体体体素素素素的的的的种种种种类类类类和和和和对对对对体体体体素素素素操操操操作作作作的的的的种种种种类类类类的的的的限限限限制制制制，，，，也也也也就就就就是是是是说说说说，，，，CSGCSG方法表示形体的覆盖域有较大的局限性方法表示形体的覆盖域有较大的局限性方法表示形体的覆盖域有较大的局限性方法表示形体的覆盖域有较大的局限性②②②② 对形体的局部操作不易实现，例如，不能对基本体素的交线倒圆角。

对形体的局部操作不易实现，例如，不能对基本体素的交线倒圆角对形体的局部操作不易实现，例如，不能对基本体素的交线倒圆角对形体的局部操作不易实现，例如，不能对基本体素的交线倒圆角③③③③ 由于形体的边界几何元素（点、边、面）是隐含地表示在由于形体的边界几何元素（点、边、面）是隐含地表示在由于形体的边界几何元素（点、边、面）是隐含地表示在由于形体的边界几何元素（点、边、面）是隐含地表示在CSGCSG中，故中，故中，故中，故显示与绘制显示与绘制显示与绘制显示与绘制CSGCSG表示的形体需要较长的时间表示的形体需要较长的时间表示的形体需要较长的时间表示的形体需要较长的时间 边界表示法边界表示法 物体的边界表示物体的边界表示 • •边界表示法（边界表示法（边界表示法（边界表示法（Brep-Boundary Brep-Boundary RepresentationRepresentation）通过描述物体）通过描述物体）通过描述物体）通过描述物体的边界来表示一个物体的边界来表示一个物体的边界来表示一个物体的边界来表示一个物体 • •所谓的边界指的就是物体内部所谓的边界指的就是物体内部所谓的边界指的就是物体内部所谓的边界指的就是物体内部点与外部点的分界面，因此，点与外部点的分界面，因此，点与外部点的分界面，因此，点与外部点的分界面，因此，定义了物体的边界，该物体也定义了物体的边界，该物体也定义了物体的边界，该物体也定义了物体的边界，该物体也就被唯一地定义了。

就被唯一地定义了就被唯一地定义了就被唯一地定义了 边界表示法边界表示法边界表示法的一个很重要的特点是：描述物体的信息包边界表示法的一个很重要的特点是：描述物体的信息包括几何信息与拓朴信息两个方面括几何信息与拓朴信息两个方面•几何信息是指物体在欧氏空间中的位置、形状和大小；几何信息是指物体在欧氏空间中的位置、形状和大小；•拓扑信息是指拓扑元素拓扑信息是指拓扑元素(顶点、边和表面顶点、边和表面)的数量及其相的数量及其相互间的连接关系；互间的连接关系；•拓扑信息构成物体的拓扑信息构成物体的“骨架骨架”，而几何信息则犹如附着，而几何信息则犹如附着在这一在这一“骨架骨架”上的上的“肌肉肌肉” 边界表示法边界表示法 边界表示的数据结构边界表示的数据结构 •翼边数据结构：以边及其相关的环和棱边来组织数据结翼边数据结构：以边及其相关的环和棱边来组织数据结构•半边数据结构：是对翼边数据结构的改进，多面体的边半边数据结构：是对翼边数据结构的改进，多面体的边界表示在拓扑上分为界表示在拓扑上分为5个层次，即体（个层次，即体（Solid））←→←→面面（（Face））←→←→环（环（Loop））←→←→半边（半边（HalfEdge））←←顶顶点（点（Vertex）。

半边数据结构半边数据结构 边界表示法边界表示法•欧拉公式：对于任意的简单多面体，其面（欧拉公式：对于任意的简单多面体，其面（f）、边）、边（（e）、顶点（）、顶点（v）的数目满足：）的数目满足： •在对形体的结构进行修改时，必须保证这个公式成立，在对形体的结构进行修改时，必须保证这个公式成立，才能够保证形体的有效性才能够保证形体的有效性 边界表示法边界表示法广义欧拉公式广义欧拉公式：对于任意的正则形体，引入形体的其他对于任意的正则形体，引入形体的其他几个参数：形体所有面上的内孔总数（几个参数：形体所有面上的内孔总数（r）、穿透形体的）、穿透形体的孔洞数（孔洞数（h）和形体非连通部分总数（）和形体非连通部分总数（s），则形体满足），则形体满足公式：公式： 欧拉操作欧拉操作•欧拉公式给出了形体的点、边、面、体、孔、洞数目之欧拉公式给出了形体的点、边、面、体、孔、洞数目之间的关系，在对形体的结构进行修改时，必须保证这个间的关系，在对形体的结构进行修改时，必须保证这个公式成立，才能够保证形体的有效性公式成立，才能够保证形体的有效性•由此而构造出一套操作，来完成对形体部分几何元素的由此而构造出一套操作，来完成对形体部分几何元素的修改，修改过程中保证各几何元素的数目保持这个关系修改，修改过程中保证各几何元素的数目保持这个关系式不变，这一套操作就是欧拉操作。

式不变，这一套操作就是欧拉操作 扫描表示扫描表示 扫描（扫描（Sweep）表示是基于一个基体（一般是一个封）表示是基于一个基体（一般是一个封闭的平面轮廓）沿某一路径运动而产生形体闭的平面轮廓）沿某一路径运动而产生形体 扫描表示需要两个分量：扫描表示需要两个分量：•被运动的基体；被运动的基体；•基体运动的路径；基体运动的路径；•如果是变截面的扫描，还要给出截面的变化规律如果是变截面的扫描，还要给出截面的变化规律 扫描表示扫描表示 有有3种扫描方式：种扫描方式：•平移平移Sweep•旋转旋转Sweep•广义广义Sweep 平移平移Sweep 将物体将物体A沿着轨迹沿着轨迹P平移得到物体平移得到物体B，称，称B为为sweep体体平移平移sweep----将一个二维区域沿着一个矢量方向推移将一个二维区域沿着一个矢量方向推移旋转旋转Sweep 将一个二维区域绕旋转轴旋转一周将一个二维区域绕旋转轴旋转一周广义广义Sweep 广义广义广义广义sweepsweep•任意物体沿着任意轨迹推移；任意物体沿着任意轨迹推移；任意物体沿着任意轨迹推移；任意物体沿着任意轨迹推移；•推移过程中物体可以变形。

推移过程中物体可以变形推移过程中物体可以变形推移过程中物体可以变形八叉树法八叉树法 三三三三维维维维物物物物体体体体的的的的八八八八叉叉叉叉树树树树表表表表示示示示是是是是一一一一种种种种层层层层次次次次数数数数据据据据结结结结构构构构，，，，它它它它首首首首先先先先在在在在三三三三维维维维空空空空间间间间中中中中定定定定义义义义一一一一个个个个能能能能够够够够包包包包含含含含所所所所表表表表示示示示物物物物体体体体的的的的立立立立方方方方体体体体，，，，且且且且立立立立方方方方体体体体的的的的3 3条条条条棱棱棱棱边边边边分分分分别别别别与与与与x x、、、、y y、、、、z z轴平行，边长为轴平行，边长为轴平行，边长为轴平行，边长为2n2n• •若若若若立立立立方方方方体体体体内内内内空空空空间间间间完完完完全全全全由由由由所所所所表表表表示示示示的的的的物物物物体体体体所所所所占占占占据据据据，，，，则则则则物物物物体体体体可可可可用用用用这这这这个个个个立立立立方方方方体体体体予予予予以以以以表表表表示示示示，，，，否否否否则则则则将将将将立立立立方方方方体体体体等等等等分分分分为为为为8 8个个个个小小小小块块块块，，，，每每每每块块块块仍仍仍仍为为为为一一一一个个个个子子子子立立立立方方方方体体体体，，，，其其其其边边边边长长长长为为为为原原原原立立立立方方方方体体体体边边边边长长长长的的的的1/21/2。

将将将将这这这这8 8个个个个子子子子立立立立方方方方体体体体依依依依次次次次编编编编号号号号为为为为0 0，，，，1 1，，，，2 2，，，，……，，，，7 7，，，，并并并并对对对对每每每每一一一一个个个个子子子子立立立立方方方方体体体体重重重重复复复复上上上上述述述述分分分分割割割割过过过过程程程程若若若若子子子子立立立立方方方方体体体体的的的的体体体体内内内内空空空空间间间间全全全全部部部部被被被被所所所所表示的物体占据，则为表示的物体占据，则为表示的物体占据，则为表示的物体占据，则为“ “满满满满” ”；；；；• •若若若若它它它它与与与与所所所所表表表表示示示示物物物物体体体体无无无无交交交交，，，，则则则则为为为为“ “空空空空” ”；；；；该该该该子子子子立立立立方方方方体体体体可可可可停停停停止止止止分分分分解解解解，，，，否否否否则则则则就就就就继继继继续续续续分分分分割割割割下下下下去去去去，，，，直直直直至至至至子子子子立立立立方方方方体体体体的的的的边边边边长长长长为为为为单单单单位位位位长长长长依依依依此此此此方方方方式式式式，，，，物物物物体体体体在在在在计计计计算算算算机机机机内内内内可可可可表表表表示示示示为为为为一一一一棵棵棵棵八八八八叉叉叉叉树树树树。

由由由由上上上上述述述述可可可可以以以以看看看看出出出出，，，，八八八八叉叉叉叉树树树树表表表表示示示示形形形形式式式式是是是是一一一一种种种种近近近近似方法 八叉树法八叉树法 八叉树表示法优点主要是：八叉树表示法优点主要是：八叉树表示法优点主要是：八叉树表示法优点主要是：①①①①形体表示的数据结构简单形体表示的数据结构简单形体表示的数据结构简单形体表示的数据结构简单②②②②简化了形体的集合运算简化了形体的集合运算简化了形体的集合运算简化了形体的集合运算③③③③简化了隐藏线（或面）的消除简化了隐藏线（或面）的消除简化了隐藏线（或面）的消除简化了隐藏线（或面）的消除④④④④分析算法适合于并行处理分析算法适合于并行处理分析算法适合于并行处理分析算法适合于并行处理 八叉树表示的缺点也是明显的，八叉树表示的缺点也是明显的，八叉树表示的缺点也是明显的，八叉树表示的缺点也是明显的，主要是占用的存储多，只能近似主要是占用的存储多，只能近似主要是占用的存储多，只能近似主要是占用的存储多，只能近似表示形体，以及不易获取形体的表示形体，以及不易获取形体的表示形体，以及不易获取形体的表示形体，以及不易获取形体的边界信息等。

边界信息等边界信息等边界信息等 分型几何方法分型几何方法—自然景物的模拟自然景物的模拟 分分形形指指的的是是数数学学上上的的一一类类几几何何形形体体，，在在任任意意尺尺度度上上都都具具有有复复杂杂并并且且精精细细的的结结构构一一般般来来说说分分形形几几何何体体都都是是自自相相似似的的，，即即图图形形的的每每一一个个局局部部都都可可以以被被看看作作是是整整体体图图形形的一个缩小的复本的一个缩小的复本分形造型的常用模型分形造型的常用模型 •随机插值模型随机插值模型•粒子系统模型粒子系统模型 •正规文法模型正规文法模型•迭代函数系统模型迭代函数系统模型 随机插值模型随机插值模型•模型不是事先决定各种图素和尺度，而是用一个随机过程的采模型不是事先决定各种图素和尺度，而是用一个随机过程的采模型不是事先决定各种图素和尺度，而是用一个随机过程的采模型不是事先决定各种图素和尺度，而是用一个随机过程的采样路径作为构造模型的手段样路径作为构造模型的手段样路径作为构造模型的手段样路径作为构造模型的手段•构造二维海岸线的模型可以选择控制大致形状的若干初始点在构造二维海岸线的模型可以选择控制大致形状的若干初始点在构造二维海岸线的模型可以选择控制大致形状的若干初始点在构造二维海岸线的模型可以选择控制大致形状的若干初始点在相邻两点构成的线段上取其中点，并沿垂直连线方向随机偏移相邻两点构成的线段上取其中点，并沿垂直连线方向随机偏移相邻两点构成的线段上取其中点，并沿垂直连线方向随机偏移相邻两点构成的线段上取其中点，并沿垂直连线方向随机偏移一个距离，再将偏移后的点与该线段两端点分别连成两个线段。

一个距离，再将偏移后的点与该线段两端点分别连成两个线段一个距离，再将偏移后的点与该线段两端点分别连成两个线段一个距离，再将偏移后的点与该线段两端点分别连成两个线段这样下去可得到一条曲折的有无穷细节回归的海岸线这样下去可得到一条曲折的有无穷细节回归的海岸线这样下去可得到一条曲折的有无穷细节回归的海岸线这样下去可得到一条曲折的有无穷细节回归的海岸线 粒子系统模型粒子系统模型•它是用大量的粒子图元来描述景物的它是用大量的粒子图元来描述景物的•粒子可以随时间推移发生位置和形态的变化每个粒子粒子可以随时间推移发生位置和形态的变化每个粒子的位置、取向及动力学性质都是由一组预先定义的随机的位置、取向及动力学性质都是由一组预先定义的随机过程来说明的过程来说明的 正规文法模型正规文法模型•基本思想是用正规文法生成结构性强的植物的拓扑结构，基本思想是用正规文法生成结构性强的植物的拓扑结构，再通过进一步几何解释来形成逼真的画面再通过进一步几何解释来形成逼真的画面 迭代函数系统模型迭代函数系统模型 迭代函数系统是以下述方式工作的：取空间中任一点迭代函数系统是以下述方式工作的：取空间中任一点Z0，以，以Pi概率选取变换概率选取变换Mi，作变换，作变换Zi=Mi(Z0)，再以，再以Pi的的概率选取变换概率选取变换Mi，对，对Z1做变换做变换Z2=Mi(Z1)，以此下去，，以此下去，得到一个无数点集。

得到一个无数点集 曼德勃罗集曼德勃罗集 曼德勃罗集是人类有史以来做出的最奇异曼德勃罗集是人类有史以来做出的最奇异, ,最瑰丽的几何图最瑰丽的几何图形形. .这个点集均出自公式这个点集均出自公式:Z:Zn+1n+1=Z=Z2 2n n+C,+C,这是一个迭代公式这是一个迭代公式, ,式中的式中的变量都是复数变量都是复数. .这是一个大千世界这是一个大千世界, ,从他出发可以产生无穷无尽从他出发可以产生无穷无尽美丽图案美丽图案, ,他是曼德勃罗教授在二十世纪七十年代发现的他是曼德勃罗教授在二十世纪七十年代发现的. .你看你看上图中上图中, ,有的地方象日冕有的地方象日冕, ,有的地方象燃烧的火焰有的地方象燃烧的火焰, ,只要你计算只要你计算的点足够多的点足够多, ,不管你把图案放大多少倍不管你把图案放大多少倍, ,都能显示出更加复杂的都能显示出更加复杂的局部局部. .这些局部既与整体不同这些局部既与整体不同, ,又有某种相似的地方又有某种相似的地方, ,好像着梦好像着梦幻般的图案具有无穷无尽的细节和自相似性幻般的图案具有无穷无尽的细节和自相似性. .曼德勃罗教授称曼德勃罗教授称此为此为“魔鬼的聚合物魔鬼的聚合物”. .为此为此, ,曼德勃罗在曼德勃罗在19881988年获得了年获得了“科学科学与艺术大奖与艺术大奖".".曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集曼德勃罗集。