第8章 几何造型

1、计算机图形学计算机图形学武汉大学国际软件学院武汉大学国际软件学院 涂建光涂建光几何造型2022年4月20日18时42分1Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学概概 述述n几何造型几何造型:l利用点、线、面、体等利用点、线、面、体等几何元素几何元素，经过平移、，经过平移、旋转、比例等旋转、比例等几何变换几何变换和交、叉、并等和交、叉、并等集合运集合运算算，产生实际或想象的物体模型；，产生实际或想象的物体模型；l应用：飞机外形设计，机械零件的计算机辅助应用：飞机外形设计，机械零件的计算机辅助设计与制造，刀具、机器人运动的模拟等等。设计

2、与制造，刀具、机器人运动的模拟等等。n三维几何造型的两个主要分支：三维几何造型的两个主要分支：l曲面造型：曲面造型：研究在计算机内如何描述一张曲面研究在计算机内如何描述一张曲面,如何对它的形状进行交互式的显示与控制；如何对它的形状进行交互式的显示与控制；l实体造型：实体造型：研究如何在计算机内定义、表示一研究如何在计算机内定义、表示一个三维物体。个三维物体。2022年4月20日星期三2Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学n 造型技术的发展造型技术的发展l6070年代初：早期的实体造型技术，共同的特点是年代初：早期的实体造型技术，

3、共同的特点是不支持精确的曲面表示，用多面体表示形体不支持精确的曲面表示，用多面体表示形体 l70年代：雕塑曲面技术的发展，出现了年代：雕塑曲面技术的发展，出现了Coons曲面、曲面、Bezier曲线和曲面、曲线和曲面、B样条曲线和曲面等设计方法，在样条曲线和曲面等设计方法，在汽车、航空和造船等行业得到了广泛的应用。汽车、航空和造船等行业得到了广泛的应用。l80年代末：出现了年代末：出现了NURBS曲线曲面设计方法，已有的曲线曲面设计方法，已有的曲线曲面表示方法，如曲线曲面表示方法，如Bezier方法、方法、B样条方法等，可样条方法等，可以用以用NURBS方法统一表示，且能精确表示二次曲线曲方法

4、统一表示，且能精确表示二次曲线曲面。由于面。由于NURBS的强大的表示能力，能够精确表示形的强大的表示能力，能够精确表示形体的几何造型系统，纷纷采用了体的几何造型系统，纷纷采用了NURBS方法，国际标方法，国际标准化组织也已将准化组织也已将NURBS作为定义工业产品形状的唯一作为定义工业产品形状的唯一数学方法。数学方法。 2022年4月20日星期三3Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学n 正则形体正则形体l早期的几何造型系统只支持正则的形体早期的几何造型系统只支持正则的形体造型造型 l对于任一形体，如果它是对于任一形体，如果它是

5、3维欧氏空间维欧氏空间R3中非空、有界的封闭子集，且其表面任中非空、有界的封闭子集，且其表面任意一点的足够小的邻域在拓扑上应该是意一点的足够小的邻域在拓扑上应该是一个等价的封闭圆，我们称该形体为正一个等价的封闭圆，我们称该形体为正则形体，否则称为非正则形体。则形体，否则称为非正则形体。2022年4月20日星期三4Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学l基于正则形体表示的实体造型形体只能基于正则形体表示的实体造型形体只能表示正则的三维表示正则的三维“体体”，低于三维的形，低于三维的形体是不能存在的。这样，线框模型中的体是不能存在的。

6、这样，线框模型中的“线线”，表面模型中的，表面模型中的“面面”，都是实，都是实体造型系统中所不能表示的。体造型系统中所不能表示的。l实际应用中，有时候人们希望在系统中实际应用中，有时候人们希望在系统中也能处理象形体中心轴、剖切平面这样也能处理象形体中心轴、剖切平面这样低于三维的形体，这就要求造型系统的低于三维的形体，这就要求造型系统的数据结构能统一表示线框、表面、实体数据结构能统一表示线框、表面、实体模型。模型。2022年4月20日星期三5Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学l形体的集合运算（并、交、差）是构造形体的形体的集合运

7、算（并、交、差）是构造形体的基本方法基本方法l正则造型和非正则造型（非正则造型是主流）正则造型和非正则造型（非正则造型是主流）2022年4月20日星期三6Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学坐坐 标标 系系n 造型坐标系（局部坐标系）造型坐标系（局部坐标系）n 用户坐标系用户坐标系l直角坐标系（左手系，右手系）直角坐标系（左手系，右手系）l仿射坐标系仿射坐标系l圆柱坐标系圆柱坐标系l球坐标系球坐标系l极坐标系极坐标系n 观察坐标系观察坐标系n 规格化的设备坐标系规格化的设备坐标系n 设备坐标系设备坐标系2022年4月20日星期三

8、7Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学几何元素几何元素n点（点（Vertex）l控制点，型值点，插值点控制点，型值点，插值点l点通过它在空间中的位置来表示。一维空间的点通过它在空间中的位置来表示。一维空间的点用一元组（点用一元组（t）表示；二维空间中的的点用二）表示；二维空间中的的点用二元组（元组（x,y）表示；三维空间中的点用三元组）表示；三维空间中的点用三元组（x,y,z）表示。）表示。n维空间中的点在齐次坐标下维空间中的点在齐次坐标下用（用（n+1）元组（）元组（x1， x2，xn，w）表示。）表示。l点是几何造型中的最基

9、本的元素，许多其它形点是几何造型中的最基本的元素，许多其它形体都可以用有序的点集表示。体都可以用有序的点集表示。l在正则形体定义中，不允许孤立的点存在。在正则形体定义中，不允许孤立的点存在。 2022年4月20日星期三8Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学n边（边（Edge）l面的边界或者几个面（包括平面和曲面）的交面的边界或者几个面（包括平面和曲面）的交l正则形体：一条边只能是两个面的交集正则形体：一条边只能是两个面的交集l非正则形体：既可以是多个面的交集，也可以非正则形体：既可以是多个面的交集，也可以是一张孤立的平面或曲面的

10、边界是一张孤立的平面或曲面的边界l边可以是直线或曲线，它的形状由边的几何信边可以是直线或曲线，它的形状由边的几何信息来表示息来表示l边有方向，它由起点和终点来界定边有方向，它由起点和终点来界定l在正则形体定义中，不允许孤立的边存在在正则形体定义中，不允许孤立的边存在 2022年4月20日星期三9Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学n环（环（Loop）l由一系列首尾相连的有向边组成的封闭边界由一系列首尾相连的有向边组成的封闭边界l环中的边不能相交，并且相邻的两条边共享一环中的边不能相交，并且相邻的两条边共享一个端点个端点l环有方向

11、、内外之分。外环边通常按逆时针方环有方向、内外之分。外环边通常按逆时针方向排序，内环边通常按顺时针方向排序，这样，向排序，内环边通常按顺时针方向排序，这样，使得环的使得环的“内部内部”始终位于环的左侧始终位于环的左侧l环主要用于定义面，包括带一个或多个孔的面环主要用于定义面，包括带一个或多个孔的面 2022年4月20日星期三10Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学n面（面（Face）l由一个外环和由一个外环和n（n0）个内环来表示）个内环来表示l内环完全在外环之内内环完全在外环之内l每个环既不能自相交，也不能与其它环相交每个环既

12、不能自相交，也不能与其它环相交l根据环的定义，在面上沿环的方向前进，左侧根据环的定义，在面上沿环的方向前进，左侧总在面内，右侧总在面外总在面内，右侧总在面外l面有方向性，一般用其外法矢方向作为该面的面有方向性，一般用其外法矢方向作为该面的正向正向l面的形状由它的几何信息来表示，可以是平面面的形状由它的几何信息来表示，可以是平面或曲面或曲面l在正则形体定义中，也不允许孤立的面存在。在正则形体定义中，也不允许孤立的面存在。 2022年4月20日星期三11Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学n体（体（Body）l是用面的并集来表示的是

13、用面的并集来表示的l用于定义体的面形成一个封闭的边界用于定义体的面形成一个封闭的边界l在正则几何造型系统中，要求体必须是正则的。在正则几何造型系统中，要求体必须是正则的。n体素（体素（voxel ）l来源：从实际形体中选择、参数轮廓线扫描产来源：从实际形体中选择、参数轮廓线扫描产生、代数半空间定义生、代数半空间定义2022年4月20日星期三12Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学表示形体的两种模型表示形体的两种模型2022年4月20日星期三13Computer GraphicsComputer Graphics计计 算算 机机

14、图图 形形 学学表示形体的数据模型表示形体的数据模型n线框模型线框模型l用顶点和棱边来表示形体用顶点和棱边来表示形体2022年4月20日星期三14V8V1V2V8V7V6V5V4V3e1e2e4e3e12e11e10e9e5e6e7e8长方体V7V4e1e2e11e12V3V1V2(a)(b)Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学l线框模型缺点线框模型缺点u数据结构包含的信息有限，无法实现图形数据结构包含的信息有限，无法实现图形的自动消隐；的自动消隐； u同一数据结构可能对应多个物体，产生二同一数据结构可能对应多个物体，产生二义性

15、；义性； u无法表达连续的几何信息，不能明确的定无法表达连续的几何信息，不能明确的定义点和几何物体之间的关系；义点和几何物体之间的关系； u在生成复杂物体的图形时，采用线框式的在生成复杂物体的图形时，采用线框式的数据结构要求输入大量的初等数据，这不数据结构要求输入大量的初等数据，这不仅加重了用户的负担，而且很难保证数据仅加重了用户的负担，而且很难保证数据的有效性和统一性。的有效性和统一性。 2022年4月20日星期三15Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学n表面模型表面模型l用有向棱边围成的部分来定义物体表面，由面用有向棱边围成

16、的部分来定义物体表面，由面的集合来定义物体。的集合来定义物体。l表面模型是在线框模型的基础上，增加了有关表面模型是在线框模型的基础上，增加了有关生成三维物体各表面的数据信息，这些信息包生成三维物体各表面的数据信息，这些信息包括定义表面的环、表面特征、棱边连接方向等括定义表面的环、表面特征、棱边连接方向等内容；内容；l可以满足面和面的求交、线面消隐、明暗色彩可以满足面和面的求交、线面消隐、明暗色彩图、数控加工等应用问题的需要；图、数控加工等应用问题的需要；l缺点：没有说明形体究竟在面的哪一侧。缺点：没有说明形体究竟在面的哪一侧。2022年4月20日星期三16Computer GraphicsCo

17、mputer Graphics计计 算算 机机 图图 形形 学学n实体模型实体模型l明确定义了表面的哪一侧存在实体；明确定义了表面的哪一侧存在实体；l在表面模型的基础上可用三种方法来定义：在表面模型的基础上可用三种方法来定义：（a）在定义表面的同时，给出实体存在侧的一点）在定义表面的同时，给出实体存在侧的一点P；（b）直接用表面的外法矢来指明实体存在的一侧；）直接用表面的外法矢来指明实体存在的一侧；（c）是用有向棱边的方向表示表面的外法矢方向，）是用有向棱边的方向表示表面的外法矢方向，右手法则确定外法矢量，图（右手法则确定外法矢量，图（d）所示。）所示。 2022年4月20日星期三17(a)(

18、c)(b)(d)PComputer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学常用的形体表示方式常用的形体表示方式 n 前面三种表示模型是一种广义的概念，不反映实前面三种表示模型是一种广义的概念，不反映实体在计算机内部，或对最终用户而言所用的具体体在计算机内部，或对最终用户而言所用的具体表示方式。针对不同的表示方式，几何造型系统表示方式。针对不同的表示方式，几何造型系统采用的数据结构也有所不同，常用的有：采用的数据结构也有所不同，常用的有：l构造实体几何表示：以一组简单的物体通过正则集合构造实体几何表示：以一组简单的物体通过正则集合运算来构造新的物体，

19、这些简单的物体称为基本体素，运算来构造新的物体，这些简单的物体称为基本体素，可以是立方体、长方体、圆柱体、圆锥体等。可以是立方体、长方体、圆柱体、圆锥体等。l边界表示：通过描述构成实体边界的点、边、面而达边界表示：通过描述构成实体边界的点、边、面而达到表示实体的目的，实体与其边界一一对应。到表示实体的目的，实体与其边界一一对应。l空间分割表示：将基本体素通过空间分割表示：将基本体素通过“粘合粘合”构造新的物构造新的物体。单元分解表示、八叉树表示等属于这种表示方法，体。单元分解表示、八叉树表示等属于这种表示方法，特征表示法也可看作这种表示方法的特例。特征表示法也可看作这种表示方法的特例。2022

20、年4月20日星期三18Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学构造实体几何表示构造实体几何表示n 构造实体几何（构造实体几何（Construction Solid Geometry）表示，或称）表示，或称CSG树表示树表示n 是一种应用广泛的物体表示与构造方法，它的是一种应用广泛的物体表示与构造方法，它的基本思想是将一些简单的基本体素通过正则集基本思想是将一些简单的基本体素通过正则集合运算来构造、表示新的物体。合运算来构造、表示新的物体。2022年4月20日星期三19（b）CSG树（a）实体模型*Computer GraphicsC

21、omputer Graphics计计 算算 机机 图图 形形 学学2022年4月20日星期三20Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学2022年4月20日星期三21Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学lCSG树表示的优点：树表示的优点：u数据结构简单，数据量小，内部数据管理容易；数据结构简单，数据量小，内部数据管理容易；u每个每个CSG树都能表达有效的形体，无二义性；树都能表达有效的形体，无二义性；u可方便的转换成可方便的转换成BRep表示，从而支持更广泛的表示，从

22、而支持更广泛的应用；应用；u容易编辑。容易编辑。lCSG树表示的缺点：树表示的缺点：u产生、修改形体的操作种类有限，集合运算对形产生、修改形体的操作种类有限，集合运算对形体的局部操作不易实现；体的局部操作不易实现；u绘制困难。绘制困难。2022年4月20日星期三22Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学边界表示法边界表示法n边界表示法边界表示法(Boundary Representation，BRep):n边界就是物体内部点与外部点的分界面。边界就是物体内部点与外部点的分界面。 2022年4月20日星期三23(a)实体模型(b)模

23、型的边界Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学p边界表示法与传统的工程绘图有密切的联系。边界表示法与传统的工程绘图有密切的联系。u输入两个点，即可以通过两个给定点连接一条线。输入两个点，即可以通过两个给定点连接一条线。u若干条首尾相接的线段若干条首尾相接的线段(即棱边，在计算机图形学中即棱边，在计算机图形学中它们被定义成物体的相邻表面的交线它们被定义成物体的相邻表面的交线)可形成一个闭可形成一个闭合环，一个或多个环给出一个面的边界。合环，一个或多个环给出一个面的边界。u最后，若干个表面闭合后围成一个最后，若干个表面闭合后围成一个“

24、体体”。p 边界表示法的一个很重要的特点是在该表示法中，边界表示法的一个很重要的特点是在该表示法中，描述物体的信息包括几何信息与拓扑信息两个方描述物体的信息包括几何信息与拓扑信息两个方面。面。 2022年4月20日星期三24Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学p拓扑信息拓扑信息 u物体的拓扑信息是指物体上所有的顶点、物体的拓扑信息是指物体上所有的顶点、棱边、表面间是怎样连接的。棱边、表面间是怎样连接的。p几何信息几何信息 u物体的几何信息指的是顶点、边、面的物体的几何信息指的是顶点、边、面的位置、大小、形状等几何数据。位置、大小

25、、形状等几何数据。2022年4月20日星期三25Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学n拓扑信息与几何信息分开表示有下述优点：拓扑信息与几何信息分开表示有下述优点：p便于具体查询物体中各元素，获取它们便于具体查询物体中各元素，获取它们的相关信息。的相关信息。 p容易支持对物体的各种局部操作。容易支持对物体的各种局部操作。 p对于具有相同拓扑结构而只是大小、尺对于具有相同拓扑结构而只是大小、尺寸不同的一类物体可以用统一的数据结寸不同的一类物体可以用统一的数据结构加以表示构加以表示 。 p便于在数据结构上附加各种非几何信息便于在数据结

26、构上附加各种非几何信息 。2022年4月20日星期三26Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学nBrep表示的优点：表示的优点：l表示形体的点、边、面等几何元素是显式表示表示形体的点、边、面等几何元素是显式表示的，使得绘制形体的速度较快，而且比较容易的，使得绘制形体的速度较快，而且比较容易确定几何元素间的连接关系；确定几何元素间的连接关系；l容易支持对物体的各种局部操作；容易支持对物体的各种局部操作；l便于在数据结构上附加各种非几何信息，如精便于在数据结构上附加各种非几何信息，如精度、表面粗糙度等。度、表面粗糙度等。nBrep表示

27、的缺点：表示的缺点：l数据结构复杂，需要大量的存储空间，维护内数据结构复杂，需要大量的存储空间，维护内部数据结构的程序比较复杂；部数据结构的程序比较复杂；l不一定对应一个有效形体，通常运用欧拉操作不一定对应一个有效形体，通常运用欧拉操作来保证来保证Brep表示形体的有效性、正则性等。表示形体的有效性、正则性等。2022年4月20日星期三27Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学 欧拉运算欧拉运算 n 欧拉运算是三维物体边界表示数欧拉运算是三维物体边界表示数据结构的生成操作，它的每一种据结构的生成操作，它的每一种运算所构运算所构 建

28、的拓扑元素和拓扑关建的拓扑元素和拓扑关系均要求满足系均要求满足 欧拉公式：欧拉公式：n 以保证所建边界表示的有效性。以保证所建边界表示的有效性。式中式中v、e、f分别表示物体上的顶分别表示物体上的顶点、棱边和表面的数目，而点、棱边和表面的数目，而r、s、h分别表示物体表面的内环数，分别表示物体表面的内环数，不相连接的物体个数以及物体的不相连接的物体个数以及物体的通孔数目。通孔数目。2022年4月20日星期三282()vefshr v=24, e=36f=15, r=3s=1, h=1Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学n满足欧拉

29、公式的欧拉运算多种多样，下满足欧拉公式的欧拉运算多种多样，下表列出了五个具有鲜明几何意义的基本表列出了五个具有鲜明几何意义的基本欧拉操作欧拉操作2022年4月20日星期三29Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学nBRep的半边数据结构：的半边数据结构：l在构成多面体的三要素在构成多面体的三要素(顶点、边、面顶点、边、面)中，中，半边数据结构以边为核心。半边数据结构以边为核心。l为了方便表达拓扑关系，它将一条边表为了方便表达拓扑关系，它将一条边表示成拓扑意义上方向相反的两条示成拓扑意义上方向相反的两条“半半边边”，所以称为半边数据

30、结构。，所以称为半边数据结构。l半边数据结构在拓扑上分为五个层次，半边数据结构在拓扑上分为五个层次，即体即体-面面-环环-半边半边-顶点。顶点。2022年4月20日星期三30Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学2022年4月20日星期三31多面体面 顶点 环半边prevsnextsprevfprevlnextfnextlprevvnextprvfloopsfsolidsfacesnextvwloopledgelfacevedge vtx边sedgesprevenexte右环边左半边左环右半边左指针右指针v2v2v1v1Compu

31、ter GraphicsComputer Graphics计计 算算 机机 图图 形形 学学基于空间分割的八叉树表示基于空间分割的八叉树表示n一种层次数据结构一种层次数据结构n表达方法：表达方法：l首先在空间中定义一个能够包含所表示物体的首先在空间中定义一个能够包含所表示物体的立方体，立方体的三条棱边分别与立方体，立方体的三条棱边分别与x, y, z轴平轴平行，边长为行，边长为2n；2022年4月20日星期三32zx4051673yp若立方体内空间完全由所表若立方体内空间完全由所表示的物体占据，则物体可用示的物体占据，则物体可用这个立方体予以表示，否则这个立方体予以表示，否则将立方体等分为八个

32、小块，将立方体等分为八个小块，每块仍为一个小立方体，其每块仍为一个小立方体，其边长为原立方体边长的边长为原立方体边长的1/2，并依次编号为并依次编号为0,1,2,7； Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学l若某一小立方体的体内空间全部被所表示物体若某一小立方体的体内空间全部被所表示物体占据，则将此立方体标识为占据，则将此立方体标识为“FULL” ;l若它与所表示物体无交，则该立方体被标志为若它与所表示物体无交，则该立方体被标志为“EMPTY” ;l否则将它标识为否则将它标识为“PARTIAL”，并继续分割下，并继续分割下去；去；

33、l依此方式，物体在计算机内可表示为一棵八叉依此方式，物体在计算机内可表示为一棵八叉树。凡是标识为树。凡是标识为“FULL”或或“EMPTY”的立方的立方体均为终端节点，而标识为体均为终端节点，而标识为“PARTIAL”的立的立方体为非终端节点；方体为非终端节点；l当分割生成的每一小立方体的边长为单位长时当分割生成的每一小立方体的边长为单位长时，分割即告终止。此时，应将每一标识为，分割即告终止。此时，应将每一标识为“PARTIAL”的小立方体重新标识为的小立方体重新标识为“FULL”或或“EMPTY”。 2022年4月20日星期三33Computer GraphicsComputer Graph

34、ics计计 算算 机机 图图 形形 学学2022年4月20日星期三34Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学2022年4月20日星期三35Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学l八叉树表示的优点：八叉树表示的优点：u容易实现物体之间的正则集合运算。由于物容易实现物体之间的正则集合运算。由于物体的八叉树表示就是由它内部含有的大大小体的八叉树表示就是由它内部含有的大大小小的立方体（称体元）组成，因此对物体执小的立方体（称体元）组成，因此对物体执行并、交、叉运算时，只需同时

35、遍历参加集行并、交、叉运算时，只需同时遍历参加集合运算的两物体相应的八叉树，就可以获得合运算的两物体相应的八叉树，就可以获得拼合的八叉树，而无需进行复杂的求交运算；拼合的八叉树，而无需进行复杂的求交运算；u容易实现隐藏线和隐藏面的消除。消除隐藏容易实现隐藏线和隐藏面的消除。消除隐藏线和隐藏面的关键是对物体（及其不同部分）线和隐藏面的关键是对物体（及其不同部分）按其距视点的远近排序，而在八叉树表示中，按其距视点的远近排序，而在八叉树表示中，各结点之间的序的关系是简单且固定的，使各结点之间的序的关系是简单且固定的，使得计算比较容易；得计算比较容易；2022年4月20日星期三36Computer G

36、raphicsComputer Graphics计计 算算 机机 图图 形形 学学u易计算物体的整体性质，如体积、质量等。易计算物体的整体性质，如体积、质量等。在计算物体的体积或质量时，只需从物体的在计算物体的体积或质量时，只需从物体的八叉树的根节点开始，逐层计算所表示物体八叉树的根节点开始，逐层计算所表示物体的最大和最小体积（质量）。当标识为的最大和最小体积（质量）。当标识为“PARTIAL”的体元以的体元以“FULL”计时得最大计时得最大体积（质量），若不计入时得最小体积（质体积（质量），若不计入时得最小体积（质量）。由于树的每一层都是在一定精度下对量）。由于树的每一层都是在一定精度下对所

37、表示物体的一种近似，因此若所得的最大所表示物体的一种近似，因此若所得的最大最小体积（质量）之差小于给定的允差，计最小体积（质量）之差小于给定的允差，计算即结束。算即结束。 2022年4月20日星期三37Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学l八叉树表示的缺点：八叉树表示的缺点：u不能精确地表示一个物体，并且对八叉树表不能精确地表示一个物体，并且对八叉树表示的物体做任意的几何变换也比较困难；示的物体做任意的几何变换也比较困难；u它占用的存储空间很多，这是因为每一体元它占用的存储空间很多，这是因为每一体元都是立方体，且体元各表面分别与

38、三个坐标都是立方体，且体元各表面分别与三个坐标平面平行。只有当所表示的物体具有相似的平面平行。只有当所表示的物体具有相似的形状和位置时，才会获得简洁的八叉树表示。形状和位置时，才会获得简洁的八叉树表示。在每一个八叉树结点中，除去一个描述该结在每一个八叉树结点中，除去一个描述该结点性质（点性质（FULL或或EMPTY等）的域外，还存等）的域外，还存储它指向父结点及八个子结点地址的指针，储它指向父结点及八个子结点地址的指针，从而使物体的八叉树表示在空间花费上十分从而使物体的八叉树表示在空间花费上十分昂贵。实际上，八叉树表示是以存储空间换昂贵。实际上，八叉树表示是以存储空间换取了算法的效率。取了算法的效率。 2022年4月20日星期三38Computer GraphicsComputer Graphics计计 算算 机机 图图 形形 学学构造形体的构造形体的SweepSweep运算运算n一个在空间移动的几何集合，可扫描出一一个在空间移动的几何集合，可扫描出一个实体。它是以沿着某种轨迹移动点、曲个实体。它是以沿着某种轨迹移动点、曲线或曲面为基础的，这一过程所产生的轨线或曲面为基础的，这一过程所产生的轨迹定义为一维、二维或三维物体。迹定义为一维、二维或三维物体。n