《CG10几何造型》PPT课件.ppt

几何造型 表示形体的坐标系： （1）用户坐标系（WCS）：直角坐标系，可以是左 手系也可以是右手系。仿射坐标系，圆柱坐标系，球坐标系 ，极坐标系。 （2）造型坐标系（MCS）：可以看成是用户坐标系 中的局部坐标系。 （3）观察坐标系（VCS）：是左手系：作用有两个 a,指定裁剪空间 b,把用户坐标变换成规格化的设备坐 标。 （4）规格化设备坐标系（NDC）：左手系用来定义视 区，约定取值范围是（0，0，0）到（1，1，1），这样有较 高的可移植性。 （5）设备坐标系（DC）：左手系，在指定设备上指 定窗口和视区。 一、物体的定义： 从几何意义上说，物体是空间 点的集合。按所构造的对象来划分 ，可分为规则物体和不规则物体两 大类。 不规则物体 不规则物体是指不能用欧氏几何加以描述的物 体，如山、水、树、草、云、烟等自然界物体。构 成不规则物体的方法主要有： （1）基于分数维理论的随机模型。主要用来 模拟海岩线和山脉等自然景物。 （2）基于文法的模型，用来构造植物等结构 性较强的自然景物。 （3）粒子系统模型，主要用来模拟火、烟、 雾等，也可用来模拟被风吹动的草和灌。木。 规则物体 规则物体是指能用欧氏几何进行描述的 物体，如点、直线、曲线、平面、曲面或实 体等。在几何造型中，所描述的物体都是规 则物体，统称为几何模型。 物体的拓扑元素物体的拓扑元素 （1 1）顶点：）顶点： 顶点是顶点是0 0维拓扑元素，它对应维拓扑元素，它对应0 0维几何元维几何元 素点。点分端点、交点、切点和孤立点等，素点。点分端点、交点、切点和孤立点等， 但在物体定义中一般不允许存在孤立点。一但在物体定义中一般不允许存在孤立点。一 维空间中的点用一元组表示，二维空间中的维空间中的点用一元组表示，二维空间中的 点用二元组表示，三维空间中的点用三元组点用二元组表示，三维空间中的点用三元组 表示。在自由曲线和曲面的描述中还常的三表示。在自由曲线和曲面的描述中还常的三 种类型的点：控制点、型值点和插入点。种类型的点：控制点、型值点和插入点。 （2 2）边：）边： 边是一维拓扑元素。是两个邻面或多个边是一维拓扑元素。是两个邻面或多个 邻面的交界。直线边由其端点定界曲线边 邻面的交界。直线边由其端点定界曲线边 由一系列型值点或控制点表示，也可用显式由一系列型值点或控制点表示，也可用显式 或隐式方程表示。或隐式方程表示。 （3 3）环：）环： 环是有序、有向边组成的面的封闭边界，环是有序、有向边组成的面的封闭边界， 环中各条边不能自交，相邻两条边共享一个端环中各条边不能自交，相邻两条边共享一个端 点。环有内外之分，确定面中内孔或凸台边界点。环有内外之分，确定面中内孔或凸台边界 的环称为内环，其边按顺时针方向排序；确定的环称为内环，其边按顺时针方向排序；确定 面的最大外边界的环称为外环，其边按逆时针面的最大外边界的环称为外环，其边按逆时针 方向排序。基于这种定义，在面占沿一个环前方向排序。基于这种定义，在面占沿一个环前 进，其左侧总在面内，右侧总在面外。进，其左侧总在面内，右侧总在面外。 （4 4）面：）面： 面是面是2 2维拓扑几何元素，是物体上一个有维拓扑几何元素，是物体上一个有 取非零的区域，由一个外环和若干个内环界取非零的区域，由一个外环和若干个内环界 定其范围。一个面可以无内环，但有且只有定其范围。一个面可以无内环，但有且只有 一个外环。面有方向性，一用其外法矢方向一个外环。面有方向性，一用其外法矢方向 作为该面的正向，反之则为反向面。面是欧作为该面的正向，反之则为反向面。面是欧 氏空间氏空间R R 3 3 中非空、连续、且封闭的子集，其中非空、连续、且封闭的子集，其 边界是有限条线段的并集。边界是有限条线段的并集。 （5 5）体：）体： 体是三维几何元素，由封闭表面围成的体是三维几何元素，由封闭表面围成的 有效空间，也是欧氏空间有效空间，也是欧氏空间R R 3 3 中非空有界的封中非空有界的封 闭子集，其边界是有限面的并集。闭子集，其边界是有限面的并集。 物体的边界及其拓扑元素物体的边界及其拓扑元素 1 1，物体的边界，物体的边界 所有实际物体都可看作在所有实际物体都可看作在R R 3 3 中边界是一个封闭中边界是一个封闭 表面的集合。有些物体边界斜率有不连续性，而这表面的集合。有些物体边界斜率有不连续性，而这 些不连续性构成了物体的边、顶点。对于任何区域些不连续性构成了物体的边、顶点。对于任何区域 R R都可以用完全在区域之中（都可以用完全在区域之中（R R i i ）和在其边界上（）和在其边界上（ R Rb b ）的全部点来定义，即：）的全部点来定义，即：R RR R i i URUR b b 。 对于一个给定点，它只可能是三种情况之一：对于一个给定点，它只可能是三种情况之一： （1 1）在区域内部为）在区域内部为R R i i 的成员。的成员。 （2 2）在边界上为）在边界上为R R b b 的成员。的成员。 （3 3）在区域的外部。）在区域的外部。 我们用我们用R Rm,n m,n表示 表示n n维欧氏空间维欧氏空间R R n n 中的中的mm维维 区域，则有区域，则有R Rm,n m,n=B =Bm-1 m-1,n,I ,n,Im,n m,n,m=n;B ,m=n;Bm-1,n m-1,n是 是 R R m,nm,n边界上的点集， 边界上的点集，I Im,n m,n是区域内部的点集。 是区域内部的点集。 在在R Rm,n m,n区域中的任一点仅有下列三条性质之 区域中的任一点仅有下列三条性质之 一：一： （1 1）在区域内部，是）在区域内部，是I Im,n m,n的成员。 的成员。 （2 2）在区域边界上，是）在区域边界上，是B Bm-1,n m-1,n的成员。 的成员。 （3 3）在区域边界外，不是区域集合的成）在区域边界外，不是区域集合的成 员员 在三维欧氏空间中，物体的边界具有以下性质 连通性：物体表面上任意两点都可用该表 面上的一条路径连接起来。 有界性：一个物体的表面把空间分为互不 连通的两部分，其中物体内的部分是有限的。 非自交性：一个物体的表面不可自相交 可取向性：一个物体的表面两侧可明确定 义出实体的内、外。 封闭性：对多面体而言，一个物体的表面 封闭性是由表面上多边形网格各元素的拓朴关 系确定的。 点、边、面几何元素间的连接关系 形体是由几何元素构成的，每一种形体 的边界都是由与其相对应的较低维的几何元 素组成的。几何元素间典型的连接关系(即拓 扑关系)是指一个形体由哪些面组成，每个面 上有几个环，每个环有哪些边组成，每条边 又由哪些顶点定义的等。在几何造型中最基 本的几何元素是点(V)、边(E)、面(F)，这三 种元素一共有九种连接关系。 V： V V V V V E V V F V V V V E E E V E E E E E E E E E F F F FV F F E F F F F F E： V F： V V： E E： E F： E V： F E： F F： F 点、边、面之间的拓朴关系 前面这种连接关系只适用于正则物体， 对于非正则形体还要加以扩充和改进。 正则物体 正则物体是指物体Q内部的点集iQ和紧包着这 些点的表面bQ组成，即Q=iQUbQ,Q的边界还还必 须满足以下性质： （1）bQ将iQ和cQ（Q的外部）隔离成两 个不连通的空间。 （2）除去bQ上的一点，iQ和cQ成为连通 空间。 （3）对于任一点P,若在P处有切平面存在 ，则其法矢Np是指向cQ的子空间。正则物体也就是 有效实体。 不满足上述要求的物体为非正则物体。 正则物体的性质 刚性：形状保持不变 维数均匀性：一个正则物体的各部分都是三维 的。 有界性：一个正则物体必须占有一个有限空间 。 边界确定性：根据一个正则物体的边界可区别 出物体的内部和外部。 一个正则物体经过一系列刚体运动或任意序列 的正则集合运算，仍保持为正则物体。 正则物体的欧拉公式 在几何体造型中，任意数目的顶点、边 、面之间一定要满足某种关系，即拓朴一致 性和几何一致性。对于正则物体来说，顶点 、边、面要满足的拓朴关系可用欧拉公式来 表示（简单欧拉公式）： V-E+F=2 例：立方体：例：立方体： F=6F=6，E=12E=12，V=8V=8 V-E+F=8-12+6=2V-E+F=8-12+6=2 n所有面都是简单连接，面中没有孔洞，边 界是面的单环。 n物体本身也是简单连接，即没有孔洞穿过 物体，不存在悬面、悬边和孤立点。 n每条边有且只有两个相邻的面，且有两个 端点。 n每个顶点至少是三条边的交。 满足简单欧拉公式必备条件 将简单欧拉公式推广到将简单欧拉公式推广到n n维空间：维空间： N N 0 0 -N-N 1 1 +N+N 2 2 +=1-(-1)+=1-(-1) n n 如果把三维空间分割成如果把三维空间分割成C C个多面体单元，其顶点、边、面、个多面体单元，其顶点、边、面、 单元体的欧拉公将变为：单元体的欧拉公将变为： V-E+F-C=1V-E+F-C=1 9 9 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 对于有孔洞的欧拉公式：对于有孔洞的欧拉公式： V-E+F-H+2P=2BV-E+F-H+2P=2B V V：顶点数顶点数 E E：边数边数 F F：面数面数 H H：面上的孔穴数面上的孔穴数 P P：面上的孔洞数面上的孔洞数 B B：为物体数为物体数 正则物体的欧拉操作 满足欧拉公式的物体称为欧拉 物体。通过面、边、顶点的增添或 删除可以构造一个欧拉物体。欧拉 操作设计成相应的欧拉算子。 用于增添操作的算子： 增添一条边和一个顶点（MEV） 增添一个面和一条边（MFE） 增添一个体、一个面和一个顶点（MBFV ） 增添一个空洞和一个体（MRB） 增添一条边，删除一个孔（ME-KH） 用于删除的算子： 删除一条边和一个顶点（KEV） 删除一个面和一条边（KFE） 删除一个体、一个面和一个顶点（KBFV ） 删除一个空洞和一个体（KRB） 删除一条边，构造一个孔（KE-MH） 二、表几何造型的理论基础 线框模型： 曲面造型： 实体造型： 线框模型 线框模型是在计算机图形学和线框模型是在计算机图形学和CADCAD领域领域 中最早用来表示物体的模型，其对现实物体中最早用来表示物体的模型，其对现实物体 的描述仅用空间直线或弧。的描述仅用空间直线或弧。 线框模型存在下列问题线框模型存在下列问题 由于该模型包含的信息量有限，给出的 是不连续的几何信息，不能明确定义点与物 体之间的关系，无法实现图形的消隐。 同一数据结构可能对应多个物体，产生 不确定性。 这种数据结构无法处理曲面物体的轮廓 线。 在生成复杂物体的图形时，这种线框式 的数据结构要求输入大量的数据。 不能计算模型的几何特性和物理性质。 曲面模型出现得比较早，其仅用空间物 体的表面来对现实物体进行描述，是在线框 模型的基础上，增加了有关面、边的信息以 及表面特征、棱边连接方向等内容逐步形成 的。 曲面模型具有深厚的数学理论基础， 特别强调物体表面数学特性，强调交互操作 修改曲面外形的能力，具有很大的灵活性和 就用广泛性。 曲面模型 曲面模型的局限性 对物体间的联系关注少，对复杂的组合 造型显得无力。 曲面具有二义性。如无正反面。 没有实体的概念，有时会引起混淆。 算出的体积不一定可靠 不易实现消隐 实体模型 实体模型出现于70年代初，它 对现实物体的描述是实体，即几何 实体的完全信息化，明确定义了表 面的哪 一侧存在实体。 实体模型优点是： 完整地给出立体图形，能区分内外 部 能进行消隐和干涉校验。 能提供清晰的剖面图 能准确计算质量特性和有限元网格 剖分。 可以加入颜色选择和色调浓淡控制 。 三、计算机中物体常用的表示方法 如何在计算机内部表示一个实体，是如何在计算机内部表示一个实体，是 造型系统好坏的关键。造型系统好坏的关键。8080年年RequicheRequiche曾提曾提 出下列几种表示法：出下列几种表示法： （1 1）基本体例表示法：）基本体例表示法：这是用一组参数来定义一组形这是用一组参数来定义一组形 状类似但大小不同的物体。主要应用于工业上已经定型的状类似但大小不同的物体。主要应用于工业上已经定型的 标准件，实现比较复杂。标准件，实现比较复杂。 （2 2）空间位置枚举法：）空间位置枚举法：先将空间分割成均匀的立方体先将空间分割成均匀的立方体 网格，然后根据物体所占据的网格位置来定义物体形状和网格，然后根据物体所占据的网格位置来定义物体形状和 大小。其数据结构需用三维数组来表示，每一组元素对应大小。其数据结构需用三维数组来表示，每一组元素对应 一空间位置，若此位置为物体所占据则相应的数组元素置一空间位置，若此位置为物体所占据则相应的数组元素置1 1 。这种表示方法容易实现物体的并、交、差运算，但没有。这种表示方法容易实现物体的并、交、差运算，但没有 明确给出物体的边界信息。它占据的存贮空间也较大，效明确给出物体的边界信息。它占据的存贮空间也较大，效 率不高。率不高。 （3 3）单元分解法）单元分解法：单元分解法克服了空间位置枚举法：单元分解法克服了空间位置枚举法 的缺点，它将物体表示成一些形状相同但大小不同的基本的缺点，它将物体表示成一些形状相同但大小不同的基本 体积单元和组合。但它导致数据结构的复杂性和多样性。体积单元和组合。但它导致数据结构的复杂性和多样性。 （4 4）推移表示法（）推移表示法（SWEEPSWEEP）：）：根据二维面或三维体根据二维面或三维体 沿某一曲线推移时，用外轮廓的轨迹来定义一物体的方法沿某一曲线推移时，用外轮廓的轨迹来定义一物体的方法 ，它已成为许多，它已成为许多CADCAD系统常用构造实体的手段。系统常用构造实体的手段。 （5 5）构造的实体几何表示法（）构造的实体几何表示法（CSGCSG）：）：用基本的体素用基本的体素 、并、交、差来表示，它是一棵二叉树，根节点为基本体素、并、交、差来表示，它是一棵二叉树，根节点为基本体素 ，非终节点为并、交、差和几何变换运算。，非终节点为并、交、差和几何变换运算。 （6 6）边界表示法）边界表示法（B-repB-rep）：）：边界表示法则用体、面、边界表示法则用体、面、 环、边、顶点等物体的边界信息来表示一个物体。环、边、顶点等物体的边界信息来表示一个物体。 （7 7）八叉树表示法：）八叉树表示法：八叉树表示法是平面的四叉树表八叉树表示法是平面的四叉树表 示法在三维空间的推广，也可以看成是单元分解法的一种改示法在三维空间的推广，也可以看成是单元分解法的一种改 进，提高各简化了物体之间的并、交、差的运算的手段，加进，提高各简化了物体之间的并、交、差的运算的手段，加 快了物体真实感的显示速度和有限元网格剖分的速度。快了物体真实感的显示速度和有限元网格剖分的速度。 （9 9）离散化、近似表示法：）离散化、近似表示法：它是用一系列简单多边形它是用一系列简单多边形 近似表示曲面的一种表示。近似表示曲面的一种表示。 （1010）特征表示法：）特征表示法：这种方法是从用户从应用层来定义这种方法是从用户从应用层来定义 物体的，因而可以较好地表达设计者的意图，为制造加工提物体的，因而可以较好地表达设计者的意图，为制造加工提 供了完整的信息。供了完整的信息。 表示方法的选择 先择哪种表示法，必须考虑以下的两点先择哪种表示法，必须考虑以下的两点 ： A,A,该表示法的覆盖域，即用这种表示法该表示法的覆盖域，即用这种表示法 所能定义的物体范围的大小和造型能力的强所能定义的物体范围的大小和造型能力的强 弱。弱。 B,B,该表示法的完整性，即由这种表示法该表示法的完整性，即由这种表示法 所决定的数据结构是否唯一地描述了现实生所决定的数据结构是否唯一地描述了现实生 活中的一个三维物体，能否为后续工作活中的一个三维物体，能否为后续工作CAECAE 、CADCAD、CAMCAM等提供所需要的信息。等提供所需要的信息。 构造的实体表示法（CSG） 基本原理：用刚体运动几 何变换和正则集合运算将简单 的形体组合成复杂形体。 构造实体几何表示法是一棵有 序的二叉树来实现的。其叶为基本 体素，而非叶节点为正则集合运算 节点或几何变换算符，树根表示当 前的物体。基本体素可以用下面两 种方法定义： （1）可用一些确定的尺寸参数 定义或控制其最终位置和形状的一 组单元实体，如长方体、圆柱等。 （2）由二维空间定义的一条截 面轮廓线沿一个方向、一条空间参 数曲线作扫描、旋转或蒙皮而生成 的实体，如拉起体、旋转体。 构成方法可参照右图： U CSG树表示法的优点： （1）数据结构比较简单，数据量小，用一棵 二叉树来表示； （2）每个CSG表示都和一个实际的有效物体 相对应。 （3）CSG表可以转化为B-rep表示，从而扩展 它的应用范围； （4）很容易修改CSG表示物体的形状，包括 操作类型和基本体素的参数； （5）CSG表示记录了一个产品造型的历程， 以便用户分析、调整、修改CSG树中的的节点。 CSG树表示法缺点： （1）由于没有边界信息，不容易实现局 部的欧拉操作； （2）操作码类型为交与差时，物体的消 隐和真实感显示很困难。 形体边界(Boundary) 域（region） 壳（shell） 面(face) 环(loop) 边(edge) 顶点(vertex) 边界表示法（B-rep） 边界表示法通过描述物体的边界来表示一 个物体，详细记录了构成物体的所有几何元素域 、壳、体、面、环、边、点的几何信息及其相互 连接关系即拓扑信息。 定义物体边界表示要满足以下条件： （1）每一条边必须精确地有两个端点； （2）每一条边只能也最多和两个面相关 ，以保证物体的封闭性； （3）每一个面上的顶点必须精确地属于 该面上的两条边，以保证面上的边能构成环； （4）每个顶点坐标的三元组（x,y,z）必 须表示R3中的一个确定点； （5）边与边之间要么分离，要么相交于 一个公共顶点。 （6）面与面之间要么分离，要么相交于 一条边或一个公共顶点。 边界表示法一个重要特点是包括几何和 拓扑两方面信息。 边界表示法的优点 （1）便于具体查询物体中各元素，并获 取它们的有关信息。 （2）容易支持对物体的各种局部操作， 如开孔。 （3）对于具有相同拓扑结构的面，可以 用统一的数据结构加以表示； （4）便于在数据结构上附加各种信息。 （5）表示物体的点、边、面等拓扑是显 式表示的，物体的消隐、真实感显示算法简 单、速度快； （6）便于对物体作布尔运算和局部操作 。 缺点： （1）数据结构复杂，需要大量的存储空 间，维护其拓扑关系一致性比较复杂。 （2）对物体的整体描述能力弱，没有记 录造型过程，因此修改基本体素的操作难以 实现。 （3）B-rep表示的物体作布尔运算或局 部操作时，可能因几何求交的不稳定性引起 其关系的不一致性，导致操作失败。 CSG与B-rep的混合表示 在CSG与Brep混合表示中，CSG只记录了物体的造型历程，是一棵二叉树 ，它的中间节点为正则集合运算或几何变换运算，而叶节点为基本体素。基本体 素的信息包含基本体素的参数、基本体素所含的裁剪面指针及变换矩阵。CSG树 为产品设计过程的后期修改提供了可能，使系统进一步提高了造型能力。B-rep 记录物体的边界信息，即拓扑信息和几何信息。 物体表 B-repCSG 面表（） P1 （） P2 （） P3 应用对表示方式的要求 在几何造型中，最常用的表示形式是 CSG和B-rep，由此使几何系统分为单表示形 式、双表示形式和混合表示形式。 （1）单表示形式就是基于CSG或B-rep 一种表示形式的结构。 （2）双表示形式一般是采用CSG和B- rep两种表示。 （3）混合表示是指在上述双表示形式的 上再扩充单元表示、扫描表示等。 为了扩大造型系统的覆盖域，常需要在 不同的表示形式之间进行转换，比如用CSG 可用以精确地表示形体，将CSG转换成B-rep 表示时可以有精确表示和近似表示两种形式 ，通常显示形体可用近似表示，而加工形体 则需要用精确表示。但不是在所有的表示形 式之间都能进行转换，如从B-rep表示转换到 CSG表示就相当难以实现。 求交中的主要算法 在实体造型中，拼合运算是核心算法，涉及几 何求交和拓扑处理两部分。其中几何求交一直是拼 合运算稳定性的根源，它决定实体造型软件系统实 用化程度的高低。最常用的三种基本几何元素是点 、边、面。这些几何元素之间进行求交运算的目的 在于判断它们之间的重合、相交、分离等位置关系 ，按几何元素的维数来划分，位置关系判断可分为 三类：点与点/边/面求交运算，边与点/边/面求交运 算，面与点/边/面的求交运算。这三类求交运算可以 归结为六种操作：点与点、点与边、点与面、边与 边、边与面、面与面。 由于计算机字长比较长，其浮点运算精 度很高，但还是存在误差。因此，在造型过 程中，对误差的控制主要反映在精度的设置 上。假设造型精度设为，则点可看做半径为 的球，边可看作半径为的圆管，面可看作 厚度为的板。 1，点与各几何元素的位置关系和判断 n判断空间一点与另一点是否重合，只要判 断两点之间的距离小于即可。 n判断点是否在线段上，也就是判断点与线的 最短距离位于的范围内。 设点坐标为 (x0, y0,z0),直线段端点为 p1(x1,y1,z1)和p2(x2,y2,z2),我们可以分别求出 p0p1，p1p2，p2p0，的长度。根据可以求出三 角形的面积S，设点p0在直线p1p2上的垂足为P ，而三角形的面积S P0Px /2，所以P0P2S/ P1P2。然后判断其距离是否大于。如果大于则 点不在直线上。否则点就在直线上。 点与平面区域的位置关系 首先点到平面的距离是否小于，如果小于再判断点是 否落在有效区域内，即内环之外，外环之内。判断点是否落 在有效区内一般有三种方法： （1）射线法：从点引出一条射线，如果于某环有奇数 个交点则点