1 计计 算算 机机 图图 形形 学学Computer Graphics 王汝传王汝传 南京邮电大学南京邮电大学 计算机学院计算机学院28.1 概述概述8.1.18.1.1几何造型定义几何造型定义 几何造型是计算机及其图形几何造型是计算机及其图形工具表示描述物体形状，设计几工具表示描述物体形状，设计几何形体，模拟物体动态处理过程何形体，模拟物体动态处理过程的一门综合技术。包括：的一门综合技术。包括：1 1、曲面造型：、曲面造型：B样条曲面，样条曲面，Coons2、实体造型实体造型3 3、特征造型：面向制造全过程，实现、特征造型：面向制造全过程，实现CAD/CAM集成重要手段集成重要手段三种造型关键是实体造型，后面重点讨论实体造型。三种造型关键是实体造型，后面重点讨论实体造型。第八章第八章 几何造型简介几何造型简介第七章真实感图形生成技术8.1 概述8.1.1几何造型定义8.1.2几何造型历史8.1.3几何造型应用8.2几何造型三种模型8.3实体模型构造几何造型：在计算机内几何造型：在计算机内生成生成所需要的几何形状。所需要的几何形状。计算机图形学：在输出设备上计算机图形学：在输出设备上显示显示所生成的图形。所生成的图形。38.1 概述概述8.1.28.1.2几何造型历史几何造型历史 几何造型的基本理论和方法是在本世纪几何造型的基本理论和方法是在本世纪70年代开始创立的，经过二十几年代开始创立的，经过二十几年的发展和研究，现已开始被广泛地应用在工业生产的各个领域。年的发展和研究，现已开始被广泛地应用在工业生产的各个领域。 1973年在英国剑桥大学由年在英国剑桥大学由ICBraid等建成了等建成了BUILD系统系统 1973年日本北海道大学公布了年日本北海道大学公布了TIPS-1系统系统 1978年，年，Shape Data的的ROMULUS系统问世系统问世 1980年年 Evans和和Sutherland开始将开始将ROMULUS投放市场投放市场 第八章第八章 几何造型简介几何造型简介 目前市场上已有许多商品化的几何造型系统。目前市场上已有许多商品化的几何造型系统。国外：国外： AUTOCAD、CATIA、I - DEAS 、Pro/Engineer、 Unigraphics、 ACIS、Parasolid等。等。国内：高华、金银花、管道国内：高华、金银花、管道CAD、 制造工程师制造工程师 （ME）、）、 NPU-CAD/CAM系统系统48.1 概述概述8.1.3 几何造型应用几何造型应用工业上应用：工业上应用：1 1、航空工业：飞机设计、航空工业：飞机设计22、汽车工业：车身设计、汽车工业：车身设计33、船舶工业、船舶工业44、模具设计、模具设计医学上应用：医学上应用：1、CT图象三维模型图象三维模型 2、模拟解剖、模拟解剖建筑工业：建筑工业： 1、建筑图自动绘制、建筑图自动绘制 2、物理特性计算，如：计算重心、体积、物理特性计算，如：计算重心、体积 3、结构有限元分析、结构有限元分析第八章第八章 几何造型简介几何造型简介服装业应用、动画制作、人体造型、计算机辅助教学服装业应用、动画制作、人体造型、计算机辅助教学58.2 几何造型系统三种模型几何造型系统三种模型1、线框模型、线框模型2、表面模型、表面模型3、实体模型、实体模型由构成物体的一组顶点和边由构成物体的一组顶点和边来表示物体的几何形状，其来表示物体的几何形状，其中边可以是直线，也可以是中边可以是直线，也可以是曲线，如圆弧、二次曲线、曲线，如圆弧、二次曲线、B 样条曲线和样条曲线和Bezier曲线。曲线。表面模型是以物体的各个表表面模型是以物体的各个表面为单位来表示其形体特征面为单位来表示其形体特征的，在线框模型的基础上增的，在线框模型的基础上增加了有关面和边的几何信息、加了有关面和边的几何信息、拓扑信息。拓扑信息。实体模型的核心问题是采用什实体模型的核心问题是采用什么方法来表示实体。与线框模么方法来表示实体。与线框模型和表面模型的根本区别在于：型和表面模型的根本区别在于：实体模型不仅记录了全部几何实体模型不仅记录了全部几何信息，而且记录了全部点、线、信息，而且记录了全部点、线、面、体的拓扑信息。面、体的拓扑信息。68.2 几何造型系统三种模型几何造型系统三种模型1、 线框模型线框模型 最早表示形体模型，用线框表示物体，如图。最早表示形体模型，用线框表示物体，如图。线框模型的数据结构线框模型的数据结构 7 构造模型时操作简便，处理速度快且占构造模型时操作简便，处理速度快且占 用内存少。用内存少。 特别适用于设计构思、建立特别适用于设计构思、建立 设计图的总体空间位置关系及图形的动态设计图的总体空间位置关系及图形的动态 交互显示。交互显示。 利用投影变换，从三维线框模型可方便利用投影变换，从三维线框模型可方便 地生成各种正投影图、轴测图和任意观地生成各种正投影图、轴测图和任意观 察方向的透视投影图。察方向的透视投影图。线框模型的优缺点线框模型的优缺点优点优点:8缺点缺点:中间打孔的长方体中间打孔的长方体 易出现二义性理解；易出现二义性理解； 缺少曲面边缘侧影轮廓线；缺少曲面边缘侧影轮廓线；缺少边与面、面与体之间关系的信息，不能描述产品。缺少边与面、面与体之间关系的信息，不能描述产品。98.2 几何造型系统三种模型几何造型系统三种模型2、表面模型、表面模型 在线框模型基础上，增加了有关生成立体各表面的数据而构成的模型。在线框模型基础上，增加了有关生成立体各表面的数据而构成的模型。表面模型的数据结构表面模型的数据结构 10按生成方式不同，表面模型有以下几种：按生成方式不同，表面模型有以下几种：（1）基本面：通过对一条线扫描操作得到）基本面：通过对一条线扫描操作得到（2）旋转面：对一个平面绕某一轴旋转得到）旋转面：对一个平面绕某一轴旋转得到（3）相交面）相交面（4）分析法表面）分析法表面（5）雕塑曲面（自由曲面）雕塑曲面（自由曲面）（6）组合平面：通过四边形网格和纵横边界构成）组合平面：通过四边形网格和纵横边界构成11表面模型的优点与不足：表面模型的优点与不足：优点优点利用曲面造型能够构造诸如汽车、飞机、船舶、模具等非常复杂的物体。利用曲面造型能够构造诸如汽车、飞机、船舶、模具等非常复杂的物体。并并且且，由由于于表表面面模模型型比比线线框框模模型型提提供供了了形形体体更更多多的的几几何何信信息息，因因而而还还可可实实现现消消隐隐、生生成成明明暗暗图图、计计算算表表面面积积、生生成成表表面面数数控控刀刀具具轨轨迹迹及及有有限限元元网格等。网格等。 12缺点缺点 操作复杂，需具备一定的曲面造型知识。操作复杂，需具备一定的曲面造型知识。 由于缺乏面与体的关系，不能区别体内与体外由于缺乏面与体的关系，不能区别体内与体外， 不能指出哪里是物体的内部与外部信息不能指出哪里是物体的内部与外部信息， 因此，表面模型仅适用于描述物体的外壳。因此，表面模型仅适用于描述物体的外壳。133、实体模型、实体模型 反映物体三维形貌，明确定义表面哪一侧存在实体。反映物体三维形貌，明确定义表面哪一侧存在实体。实体表示模型实体表示模型 实体模型的优点：实体模型的优点：（1）完整定义了立体图形，能区分内外部；）完整定义了立体图形，能区分内外部；（2）能提供清晰的剖面图；）能提供清晰的剖面图；（3）能准确计算质量特征和有限元网格；）能准确计算质量特征和有限元网格；（4）方便机械运动的模拟。）方便机械运动的模拟。8.2 几何造型系统三种模型几何造型系统三种模型14 8.3 实体模型的构造实体模型的构造8.3.1 概述概述 目前常用实体造型方法有：目前常用实体造型方法有：边界方法边界方法、构造实体几何法构造实体几何法、扫描法扫描法和和分解表示法分解表示法。(a)正则形体 (b) 非正则形体图8.5 正则形体和非正则形体1、形体描述、形体描述 在计算机内，通常用体、面、环、边、顶点五个层次来在计算机内，通常用体、面、环、边、顶点五个层次来描述。描述。（1）体：由封闭表面围成，如）体：由封闭表面围成，如右图。右图。（2）面：由外环和内环所定范）面：由外环和内环所定范围，如图围，如图8.5(a)有六个环。有六个环。（3）环：有序、有向边组成的）环：有序、有向边组成的面上封闭边界，如图面上封闭边界，如图8.5(a)V5V6V7V8（4）边：环的组成元素边：环的组成元素（5）顶点：边端点或曲线的型值点）顶点：边端点或曲线的型值点15 8.3 实体模型的构造实体模型的构造8.3.1 概述概述2、实体表示基本要求、实体表示基本要求（1）适用范围尽量大）适用范围尽量大 （2）无二义性）无二义性 （3）惟一性）惟一性（4）近似性）近似性 （5）有效性）有效性 （6）为节省存储空间，表示方法应该紧凑）为节省存储空间，表示方法应该紧凑168.3.2 边界表示（边界表示（B-rep）法法1、形体的拓扑关系、形体的拓扑关系 对于一个形体，不但有几何信息（大小、位置等），同时对于一个形体，不但有几何信息（大小、位置等），同时还有拓扑信息。还有拓扑信息。所谓形体的拓扑信息是指形体上所有顶点、所谓形体的拓扑信息是指形体上所有顶点、棱边、表面之间的相互连接关系，实体的面、边、点之间共棱边、表面之间的相互连接关系，实体的面、边、点之间共有有9 9种不同类型的拓扑关系。种不同类型的拓扑关系。如图，如图，V：顶点，顶点，E：边，边，F：面，面，VE表示由一表示由一个顶点对应相交于此顶点个顶点对应相交于此顶点的所有边；的所有边；F表示由一表示由一个面找出该面所有边。个面找出该面所有边。画、边、点之间的拓扑关系画、边、点之间的拓扑关系178.3.2 边界表示（边界表示（B-rep）法法2 2、形体边界表示法、形体边界表示法（1 1）分层表示）分层表示将形体面、边、顶点的信息分别记录，建立层与层之间的关系，其信息将形体面、边、顶点的信息分别记录，建立层与层之间的关系，其信息包括包括几何信息几何信息和和拓扑信息拓扑信息。（2 2）翼边结构）翼边结构以边为核心来组织形体数据以边为核心来组织形体数据（3）优缺点）优缺点优点：可直接用几何体面、边、点来定义数据，优点：可直接用几何体面、边、点来定义数据， 方便图形绘制。方便图形绘制。缺点：数据结构复杂，存储量大。缺点：数据结构复杂，存储量大。188.3.3 构造实体几何法（构造实体几何法（CSG）1、正则集合运算正则集合运算（1）定义）定义 对两个实体进行普通的布尔运算产生的结果并不一定对两个实体进行普通的布尔运算产生的结果并不一定是实体。是实体。为此，我们不使用普通布尔运算，而是采用正则布尔为此，我们不使用普通布尔运算，而是采用正则布尔运算。正则化运算符可以分别用运算。正则化运算符可以分别用* *，* *和和* *表示。定义表示。定义这些运算符后，对实体进行布尔运算时总是产生实体。这些运算符后，对实体进行布尔运算时总是产生实体。198.3.3 构造实体几何法（构造实体几何法（CSG）1、正则集合运算正则集合运算任意一个三维形体都可用三维欧氏空间中点的集合表示，任意一个三维形体都可用三维欧氏空间中点的集合表示，而三维空间中任意点的集合却不一定对应一个形体，因此而三维空间中任意点的集合却不一定对应一个形体，因此必须定义正则集。必须定义正则集。数学上正则集的定义是：数学上正则集的定义是：S=kiS式中式中k表示闭包，表示闭包，i表示内部，表示内部，S表示集合。该式定义是：表示集合。该式定义是：给定一个集合给定一个集合S,如果此集合内部闭包与所给原集合相等，如果此集合内部闭包与所给原集合相等，则原集合称为正则集。则原集合称为正则集。20图（图（a）中原来的集合中原来的集合S不等于不等于 S（ S=kiS），），故故S不是正则集；不是正则集；图（图（b）中原来的集合中原来的集合S=S,故故S是正则集。是正则集。正则集的定义正则集的定义 21（2 2）正则集运算）正则集运算以二维平面上物体以二维平面上物体A和和B为例，为例，按照下图（按照下图（b）的位置求交运算，照一般的位置求交运算，照一般求交运算得到图（求交运算得到图（c），），这不是正则形体，因为这不是正则形体，因为有悬边，若去掉悬边就有悬边，若去掉悬边就是正则形体，因此引入正则运是正则形体，因此引入正则运算符进行运算，定义如下：算符进行运算，定义如下：A *B= ki(A B) 通过通过Ki作用，使作用，使A B运算后变成正则形体运算后变成正则形体A*B= ki(AB) 通过通过Ki作用，使作用，使AB运算后变成正则形体运算后变成正则形体A*B= ki(AB) 通过通过Ki作用，使作用，使AB运算后变成正则形体运算后变成正则形体集合和正则集合的交运算集合和正则集合的交运算 22 下面考察下面考察正则集合运算正则集合运算CAB。对于形体对于形体A，令令bA表示表示A的边界点集，的边界点集，iA表示表示A的内部点集，由前面定义则有：的内部点集，由前面定义则有： A=bA iA同理，对形体同理，对形体B则有：则有：B=bB iB23如图所示，如图所示，A的边界的边界bA可分为在可分为在B内、在内、在B上和上和B外三种可能，外三种可能，分别表示分别表示bAib、bAbB和和bAcB，其中其中cB表示位于形体表示位于形体B外的点集合。同理，外的点集合。同理，bB也可分为也可分为bBiA、bBbA和和bBcA三部分，其中三部分，其中bBbAbAbB。由点集求交可知，由点集求交可知，A、B的边界位于对方体内的部分组成的边界位于对方体内的部分组成 C的部分边界，的部分边界，A、B分别分别位于对方体外的部分边界不在位于对方体外的部分边界不在 C的边界上，也就是说的边界上，也就是说 bAiB和和bB iA组成组成C的部分边界，另外的部分边界，另外C的部分边界则由的部分边界则由图可以看出是由图可以看出是由bAbBk（iAiB）组成。组成。A*B的边界的边界 24故故b（A*B）=（bAiB） （bBiA） （bAbBk(iAiB）同理可得：同理可得： b（A *B）=（bAcB） （bBcA） （bAbBk(cAcB)） b（A*B）=（bAcB） （bBiA） （bAbBk(iAcB)）正则集合运算正则集合运算 252、构造实体几何法（、构造实体几何法（CSG法）法） 构造实体几何法是当前许多构造实体几何法是当前许多CADCAM系统采用的表示三维形体的一种系统采用的表示三维形体的一种方法。方法。CSG用系统定义的简单几何形体（体素）经正则集合运算，构造出所用系统定义的简单几何形体（体素）经正则集合运算，构造出所需要的复杂实体。需要的复杂实体。CSG方法示意图方法示意图 通过下图大家可以很容易地发现这种方法的通过下图大家可以很容易地发现这种方法的基本思想：基本思想：一个三维形体可以通过一些基本形体（这里是两个长方体和一个圆柱体）的一个三维形体可以通过一些基本形体（这里是两个长方体和一个圆柱体）的并、差等集合运算来得到正确表示。并、差等集合运算来得到正确表示。268.3.4 扫描法扫描法 通过在空间移动的几何集合，扫描出一个实体。通过在空间移动的几何集合，扫描出一个实体。a、要定义移动物体，如曲线、曲面或实体要定义移动物体，如曲线、曲面或实体b、要定义移动轨迹要定义移动轨迹1、平移扫描法、平移扫描法一个二维图形沿着轨迹作直线移动而形成三维图形，这种方一个二维图形沿着轨迹作直线移动而形成三维图形，这种方法称为平移扫描。如图，扫描线是一条直线，扫描得到曲面。法称为平移扫描。如图，扫描线是一条直线，扫描得到曲面。平移扫描平移扫描 旋转扫描旋转扫描 2、旋转扫描法、旋转扫描法绕某以轴线旋转某一角度而形成实体。如图，扫描体是一条绕某以轴线旋转某一角度而形成实体。如图，扫描体是一条曲线，旋转轴是一直线，旋转后得到一个曲面。曲线，旋转轴是一直线，旋转后得到一个曲面。278.3.5 分解表示法（分解表示法（D-rep） 分解表示法是把一个几何体有规律地分解为有限个单元，这种方法不仅可以表分解表示法是把一个几何体有规律地分解为有限个单元，这种方法不仅可以表示平面的几何体，也可以表示复杂的示平面的几何体，也可以表示复杂的包括内部有孔的几何体。包括内部有孔的几何体。 D-rep法主要有：法主要有：八叉树法八叉树法、细胞分解法、空间堆叠法等。、细胞分解法、空间堆叠法等。 D-rep法便于进行几何体的并、交、差运算，容易计算几何体几何特性。但这法便于进行几何体的并、交、差运算，容易计算几何体几何特性。但这种方法不是一种精确的表示法，其近似程度完全取决于分割精度，与几何形体种方法不是一种精确的表示法，其近似程度完全取决于分割精度，与几何形体的复杂程度无关。的复杂程度无关。 288.3.5 分解表示法（分解表示法（D-rep）先讨论四叉树再讨论八叉树。先讨论四叉树再讨论八叉树。1、四叉树、四叉树 四叉树处理图形基本思想：四叉树处理图形基本思想：假定图形由假定图形由N N个像素构成，个像素构成，且且 N 2m。将图形四等分，划分后可能出现三种情况：将图形四等分，划分后可能出现三种情况：（1 1）图形不占区域：白色区域，不必再划分；）图形不占区域：白色区域，不必再划分；（2 2）图形全占区域：黑色区域，不必再划分；）图形全占区域：黑色区域，不必再划分；（3 3）不一致，继续划分。）不一致，继续划分。298.3.5 分解表示法（分解表示法（D-rep）2、八叉树、八叉树 原理同四叉树。原理同四叉树。30 用八叉树表示空间实体具有许多优点，可以用统一而简单的形体（即立用八叉树表示空间实体具有许多优点，可以用统一而简单的形体（即立方体）表示空间任意形状的实体，因而数据结构简单划一；易于实现物体之间方体）表示空间任意形状的实体，因而数据结构简单划一；易于实现物体之间的集合运算的集合运算,易于计算物体的性质，如物体的体积、质量、转动惯量等。但采易于计算物体的性质，如物体的体积、质量、转动惯量等。但采用八叉树表示物体的最大缺点是它占用内存很多，但可用线性八叉树方法来解用八叉树表示物体的最大缺点是它占用内存很多，但可用线性八叉树方法来解决这个问题，即用一个可变长度的一维数组来存放一棵八叉树，这样很容易将决这个问题，即用一个可变长度的一维数组来存放一棵八叉树，这样很容易将空间任一物体转化为线性八叉树的编码表示。空间任一物体转化为线性八叉树的编码表示。 一个功能完善的八叉树造型系统应包括如下几类算法：一个功能完善的八叉树造型系统应包括如下几类算法：（l）八叉树的生成。八叉树的生成。（2）集合运算。）集合运算。（3）几何运算。）几何运算。（4）分析例程。）分析例程。（5）显示生成。）显示生成。31小小结除上述四种实体造型方法以外，还有其它一些方法，如基本体素表示法、除上述四种实体造型方法以外，还有其它一些方法，如基本体素表示法、空间位置枚举法、描述性造型和基于物理的造型。空间位置枚举法、描述性造型和基于物理的造型。对于不规则形体的造型，例如山、水、树、草、云、烟等自然界丰富多彩对于不规则形体的造型，例如山、水、树、草、云、烟等自然界丰富多彩的物体，不能用欧氏几何加以描述，可用分形理论的随机插值模型、粒子的物体，不能用欧氏几何加以描述，可用分形理论的随机插值模型、粒子系统模型和基于文法模型等对这些不规则形体进行造型。系统模型和基于文法模型等对这些不规则形体进行造型。32小小结由于计算机辅助设计和动画技术的飞速发展，在传统的几何造型技术得到由于计算机辅助设计和动画技术的飞速发展，在传统的几何造型技术得到了广泛应用的同时，其它造型技术正在迅速兴起和发展。其特点是不断拓了广泛应用的同时，其它造型技术正在迅速兴起和发展。其特点是不断拓宽造型技术的覆盖域，由规则形体发展到不规则形体，而形体的表示方法宽造型技术的覆盖域，由规则形体发展到不规则形体，而形体的表示方法则不断从低层向高层发展，以尽可能减少用户的负担，将更多工作交给计则不断从低层向高层发展，以尽可能减少用户的负担，将更多工作交给计算机去做，也更便于与应用系统相结合。算机去做，也更便于与应用系统相结合。可以预计，在这一发展道路上，将会不断出现新成果。可以预计，在这一发展道路上，将会不断出现新成果。 33作业作业1几何造型有哪三种模型？各有什么特点？几何造型有哪三种模型？各有什么特点？2分析比较分析比较CSG法与法与B-rep法优缺点。法优缺点。