这就是使得成为一个新控制顶点而要插入的新节点 t∈ 制顶点所替代,如图,+使2成为新控制顶点的同时,将有k2个老控制顶点被包括2在内的新控 当插入新节点 图3.1.38使P成为新控制顶点 3.1.4.6非均匀有理B样条( NURBS)曲面 1. NURBS曲面的定义 由双参数变量分段有理多项式定义的 NURBS曲面是: ay Py Ni,p ( u)ng(v) @yN, p u)Ns(v) ∑∑孕码p(,y),v∈[0, 式中”是矩形域上特征网格控制点列,是相应控制点的权因子,规定四角点处用正权因子,即 0,00,0,Om0.其Og≥0NM,Q)gMya(y) 是p阶和q阶的B样条基函数, ,1 是双变量有理基函数 M,()M2(y) pi g(u,v)= 20M N(yi 入节点矢每U=[40,41,…m+]v=[v、.、按deBo递推公式决定,通常具有 面的形式 U=[0,0,…,0 11,…J, 个q个 v=[0,0,…,0,v p个q个 2. NURBS曲面的性质 有理双变量基函数,p,y 与非有理B样条基函数相类似的性质: 计算机图形学第三章(2)第52页共26页
计算机图形学 第三章(2) 第 52 页 共 26 页 这就是使得 成为一个新控制顶点而要插入的新节点。 当插入新节点 使 成为新控制顶点的同时，将有 k-2 个老控制顶点被包括 在内的新控 制顶点所替代，如图 3.1.38 所示。 3.1.4.6 非均匀有理 B 样条（NURBS）曲面 1.NURBS 曲面的定义 由双参数变量分段有理多项式定义的 NURBS 曲面是： 式中 是矩形域上特征网格控制点列， 是相应控制点的权因子，规定四角点处用正权因子，即 ，其余 。 和 是 p 阶和 q 阶的 B 样条基函数， 是双变量有理基函数： 节点矢量 和 按 de Boor 递推公式决定，通常具有 下面的形式： p 个 q 个 p 个 q 个 2.NURBS 曲面的性质 有理双变量基函数 与非有理 B 样条基函数相类似的性质：
(1)局部支承性质:,以9(,y)=0M生[4,2+]vg[y,计+ 22.y)=1 (2)权性: (3)可微性:在每个子矩形域内所有偏导数存在,在重复度为r的u节点处沿u向是p-r-1次连续可微 在重复度为r的v节点处沿v向是q-r-1次连续可德 (4)极值:若p,q1,恒有一个极大值存在 R,(,v) 是双变量B样条基函数的推广 NURBS曲面与非有理B样条曲面也有相类似的几何性质,权因子的几何意义及修改、控制顶点的修改等也 与NRBS曲线类似,这里不在赘述 3.2形体在计算机内的表示 我们已经知道,计算机中表示形体,通常用线框、表面和实体三种模型。线框模型和表面模型保存的三维 形体信息都不完整,只有实体模型才能够完整地、无歧义地表示三维形体。前面我们已经介绍了曲线曲面常 用的的表示形式及其理论基础,从本小节开始,我们介绍实体造型技术的有关问题,主要包括形体在计算机 内的表示、分类求交算法和典型的实体造型系统。 3.2.1引言 实体造型技术的研究可以追到溯到六十年代初期,不过,直到六十年代后半期,有关实体造型的报道仍然 很少。七十年代初期,出现了一些实体造型系统,如英国剑桥大学的 BUILD-1系统,德国柏林工业大学的 COMPAC系统,日本北海道大学的TIPS-1系统和美国罗切斯特大学的PADL-1、PADL-2系统等 这些早期的实体造型系统有一个共同的特点:不支持精确的曲面表示,用多面体表示形体。多面体模型的 优点是数据结构相对简单,集合运算、明暗图的生成和显示速度快。但是,同一系统中存在两种表示:精确 的曲面表示和近似的多面体逼近,违背了几何定义唯一性原则;而且,曲面形体使用多面体模型只是近似表 示,存在误差,若要提高表示精度时,就需要增加离散平面片的数量,庞大数据量影响计算速度和计算机的 存储管理,也是难以接受的。显然,要为了解决这个问题,就需要在几何造型系统中采用精确的形体表示模 六、七十年代,雕塑曲面的研究取得了很大的进展, Coons曲面、 Bezier曲线和曲面、B样条曲线和曲面 等设计方法相继提出,并在汽车、航空和造船等行业得到了广泛的应用。曲面造型系统由于缺乏面片的连接 关系,不仅使曲面的交互修改非常复杂,而且也难于构造封闭的形体。实体造型系统则由于不能有效地处理 复杂曲面,也使其几何造型的覆盖域受到了很大的限制。自然,如何构造能够精确表示形体的几何造型系统, 成了人们研究的目标。1978年,英国 Shape data公司推出了实体造型系统 Romulus,并首次引入了精确的 二次曲面,二次曲面的表示采用了代数方程的形式 八十年代末,出现了 NURBS曲线曲面设计方法,已有的曲线曲面表示方法,如 Bezier方法、B样条方法 等,可以用NRBS方法统一表示,且能精确表示二次曲线曲面。由于 NURBS的强大的表示能力,能够精确表 示形体的几何造型系统,纷纷采用了 NURBS方法,国际标准化组织也已将 NURBS作为定义工业产品形状的唯 数学方法。 早期的几何造型系统还有一个特点,就是只支持正则的形体造型。正则形体集(R-Set)的概念由罗切斯 特大学 Requicha引入造型系统,并为几何造型奠定了初步的理论基础, 为了描述正则形体,引入了二维流形(2- manifold)的概念。所谓二维流形是指这样一些面,其上任 点都存在一个充分小的邻域,该邻域与平面上的圆盘是同构的,即在该邻域与圆盘之间存在连续的1-1映射 对于任一形体,如果它是3维欧氏空间中非空、有界的封闭子集,且其边界是二维流形(即该形体是 连通的),我们称该形体为正则形体,否则称为非正则形体。图3.2.1给出了一些非正则形体的实例 计算机图形学第三章(2)第53页共26页
计算机图形学 第三章(2) 第 53 页 共 26 页 （1）局部支承性质： ，当 或 ； （2）权性： ； （3）可微性：在每个子矩形域内所有偏导数存在，在重复度为 r 的 u 节点处沿 u 向是 p-r-1 次连续可微， 在重复度为 r 的 v 节点处沿 v 向是 q-r-1 次连续可微； （4）极值：若 p，q>1，恒有一个极大值存在； （5） 是双变量 B 样条基函数的推广。 NURBS 曲面与非有理 B 样条曲面也有相类似的几何性质，权因子的几何意义及修改、控制顶点的修改等也 与 NURBS 曲线类似，这里不在赘述。 3.2 形体在计算机内的表示 我们已经知道，计算机中表示形体，通常用线框、表面和实体三种模型。线框模型和表面模型保存的三维 形体信息都不完整，只有实体模型才能够完整地、无歧义地表示三维形体。前面我们已经介绍了曲线曲面常 用的的表示形式及其理论基础，从本小节开始，我们介绍实体造型技术的有关问题，主要包括形体在计算机 内的表示、分类求交算法和典型的实体造型系统。 3.2.1 引言 实体造型技术的研究可以追到溯到六十年代初期，不过，直到六十年代后半期，有关实体造型的报道仍然 很少。七十年代初期，出现了一些实体造型系统，如英国剑桥大学的 BUILD-1 系统，德国柏林工业大学的 COMPAC 系统，日本北海道大学的 TIPS-1 系统和美国罗切斯特大学的 PADL-1、PADL-2 系统等。 这些早期的实体造型系统有一个共同的特点：不支持精确的曲面表示，用多面体表示形体。多面体模型的 优点是数据结构相对简单，集合运算、明暗图的生成和显示速度快。但是，同一系统中存在两种表示：精确 的曲面表示和近似的多面体逼近，违背了几何定义唯一性原则；而且，曲面形体使用多面体模型只是近似表 示，存在误差，若要提高表示精度时，就需要增加离散平面片的数量，庞大数据量影响计算速度和计算机的 存储管理，也是难以接受的。显然，要为了解决这个问题，就需要在几何造型系统中采用精确的形体表示模 型。 六、七十年代，雕塑曲面的研究取得了很大的进展，Coons 曲面、Bezier 曲线和曲面、B 样条曲线和曲面 等设计方法相继提出，并在汽车、航空和造船等行业得到了广泛的应用。曲面造型系统由于缺乏面片的连接 关系，不仅使曲面的交互修改非常复杂，而且也难于构造封闭的形体。实体造型系统则由于不能有效地处理 复杂曲面，也使其几何造型的覆盖域受到了很大的限制。自然，如何构造能够精确表示形体的几何造型系统， 成了人们研究的目标。1978 年，英国 Shape Data 公司推出了实体造型系统 Romulus，并首次引入了精确的 二次曲面，二次曲面的表示采用了代数方程的形式。 八十年代末，出现了 NURBS 曲线曲面设计方法，已有的曲线曲面表示方法，如 Bezier 方法、B 样条方法 等，可以用 NURBS 方法统一表示，且能精确表示二次曲线曲面。由于 NURBS 的强大的表示能力，能够精确表 示形体的几何造型系统，纷纷采用了 NURBS 方法，国际标准化组织也已将 NURBS 作为定义工业产品形状的唯 一数学方法。 早期的几何造型系统还有一个特点，就是只支持正则的形体造型。正则形体集（R-Set）的概念由罗切斯 特大学 Requicha 引入造型系统，并为几何造型奠定了初步的理论基础。 为了描述正则形体，引入了二维流形（2-manifold）的概念。所谓二维流形是指这样一些面，其上任一 点都存在一个充分小的邻域，该邻域与平面上的圆盘是同构的，即在该邻域与圆盘之间存在连续的 1-1 映射。 对于任一形体，如果它是 3 维欧氏空间 中非空、有界的封闭子集，且其边界是二维流形（即该形体是 连通的），我们称该形体为正则形体，否则称为非正则形体。图 3.2.1 给出了一些非正则形体的实例
气 (a)有悬面 (c)一条边有两个以上 (b)有悬边 的邻面(不连通) 图3.2.1非正则形体实例 基于正则形体表示的实体造型形体只能表示正则的三维“体”,低于三维的形体是不能存在的。这样,线框 模型中的“线",表面模型中的“面”,都是实体造型系统中所不能表示的。但在实际应用中,有时候人们希望在 系统中也能处理象形体中心轴、剖切平面这样低于三维的形体,这就要求造型系统的数据结构能统一表示线 框、表面、实体模型 集合运算(并、交、差)是构造形体的基本方法,正则形体经过集合运算后,可能会产生悬边、悬面等低 于三维的形体,如图3.2.2所示。 Requicha在引入正则形体概念的同时,还定义了正则集合运算的概念,正 则集合运算保证集合运算的结果仍是一个正则形体,即丢弃悬边、悬面等,如图3.2.3所示。但是,这些信 息在很多应用中是有用的,不能丢弃,这也要求几何造型系统要能够表示边、面等低于三维的形体。即是说, 几何造型系统要求能够处理非正则形体,于是,产生了非正则造型技术。 A 图3.2.2二个二维图形的交产 生一个退化的结果 A B B 悬边 C=A∩B C=A∩B 集合论的求交计算 正则集合下的求交运算 图3.2.3集合和正则的交运算 计算机图形学第三章(2)第54页共26页
计算机图形学 第三章(2) 第 54 页 共 26 页 基于正则形体表示的实体造型形体只能表示正则的三维“体”，低于三维的形体是不能存在的。这样，线框 模型中的“线”，表面模型中的“面”，都是实体造型系统中所不能表示的。但在实际应用中，有时候人们希望在 系统中也能处理象形体中心轴、剖切平面这样低于三维的形体，这就要求造型系统的数据结构能统一表示线 框、表面、实体模型。 集合运算（并、交、差）是构造形体的基本方法，正则形体经过集合运算后，可能会产生悬边、悬面等低 于三维的形体，如图 3.2.2 所示。Requicha 在引入正则形体概念的同时，还定义了正则集合运算的概念，正 则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面等，如图 3.2.3 所示。但是，这些信 息在很多应用中是有用的，不能丢弃，这也要求几何造型系统要能够表示边、面等低于三维的形体。即是说， 几何造型系统要求能够处理非正则形体，于是，产生了非正则造型技术
九十年代以来,基于约束的参数化、变量化造型和支持线框、曲面、实体统一表示的非正则形体造型技术 已成为几何造型技术的主流。 3.22形体表示模型 在实体模型的表示中,出现了许多方法,基本上可以分为分解表示、构造表示和边界表示三大类 1.分解表示 分解表示是将形体按某种规则分解为小的更易于描述的部分,每一小部分又可分为更小的部分,这种分解 过程直至每一小部分都能够直接描述为止。分解表示的一种特殊形式是每一小的部分都是一种固定形状(正方 形、立方体等)的单元,形体被分解成这些分布在空间网格位置上的具有邻接关系的固定形状单元的集合,单 元的大小决定了单元分解形式的精度。根据基本单元的不同形状,常用四叉树、八叉树和多叉树等表示方法 分解表示中一种比较原始的表示方法是将形体空间细分为小的立方体单元,与此相对应,在计算机内存中 开辟一个三维数组。凡是形体占有的空间,存储单元中记为1:其余空间记为0。这种表示方法的优点是简单 容易实现形体的交、并、差计算,但是占用的存储量太大,物体的边界面没有显式的解析表达式,不便于运 算,实际上并未采用。 图3.2.4是八叉树表示形体的一个实例。八叉树法表示形体的过程是这样的,首先对形体定义一个外接 立方体,再把它分解成八个子立方体,并对立方体依次编号为0,1,2,…,7。如果子立方体单元已经一致, 即为满(该立方体充满形体)或为空(没有形体在其中),则该子立方体可停止分解:否则,需要对该立方 体作进一步分解,再一分为八个子立方体。在八叉树中,非叶结点的每个结点都有八个分支。八叉树表示法 有一些优点,近年来受到人们的注意。这些优点主要是: (1)形体表示的数据结构简单。 2)简化了形体的集合运算。对形体执行交、并、差运算时,只需同时遍历参加集合运算的两形体相应 的八叉树,无需进行复杂的求交运算 (3)简化了隐藏线(或面)的消除,因为在八叉树表示中,形体上各元素已按空间位置排成了一定的顺 (4)分析算法适合于并行处理 八叉树表示的缺点也是明显的,主要是占用的存储多,只能近似表示形体,以及不易获取形体的边界信息 O具有子孙的节点 口空节点 百百白白白口 口实节点 图3.2.4用八叉树表示形体 2.构造表示 计算机图形学第三章(2)第55页共26页
计算机图形学 第三章(2) 第 55 页 共 26 页 九十年代以来，基于约束的参数化、变量化造型和支持线框、曲面、实体统一表示的非正则形体造型技术 已成为几何造型技术的主流。 3.2.2 形体表示模型 在实体模型的表示中，出现了许多方法，基本上可以分为分解表示、构造表示和边界表示三大类。 1．分解表示 分解表示是将形体按某种规则分解为小的更易于描述的部分，每一小部分又可分为更小的部分，这种分解 过程直至每一小部分都能够直接描述为止。分解表示的一种特殊形式是每一小的部分都是一种固定形状(正方 形、立方体等)的单元，形体被分解成这些分布在空间网格位置上的具有邻接关系的固定形状单元的集合，单 元的大小决定了单元分解形式的精度。根据基本单元的不同形状，常用四叉树、八叉树和多叉树等表示方法。 分解表示中一种比较原始的表示方法是将形体空间细分为小的立方体单元，与此相对应，在计算机内存中 开辟一个三维数组。凡是形体占有的空间，存储单元中记为 1；其余空间记为 0。这种表示方法的优点是简单， 容易实现形体的交、并、差计算，但是占用的存储量太大，物体的边界面没有显式的解析表达式，不便于运 算，实际上并未采用。 图 3.2.4 是八叉树表示形体的一个实例。八叉树法表示形体的过程是这样的，首先对形体定义一个外接 立方体，再把它分解成八个子立方体，并对立方体依次编号为 0，1，2，…，7。如果子立方体单元已经一致， 即为满（该立方体充满形体）或为空（没有形体在其中），则该子立方体可停止分解；否则，需要对该立方 体作进一步分解，再一分为八个子立方体。在八叉树中，非叶结点的每个结点都有八个分支。八叉树表示法 有一些优点，近年来受到人们的注意。这些优点主要是： （1）形体表示的数据结构简单。 （2）简化了形体的集合运算。对形体执行交、并、差运算时，只需同时遍历参加集合运算的两形体相应 的八叉树，无需进行复杂的求交运算。 （3）简化了隐藏线（或面）的消除，因为在八叉树表示中，形体上各元素已按空间位置排成了一定的顺 序。 （4）分析算法适合于并行处理。 八叉树表示的缺点也是明显的，主要是占用的存储多，只能近似表示形体，以及不易获取形体的边界信息 等。 2．构造表示