（计算机应用技术专业论文）离散细分方法在几何造型中的应用.pdf

一淘人学坝h 仓文 摘要 随着计算机硬件和计算机图形学的飞速发展，人们对动画、游戏等三维形体真 实感的要求电不断提高。与传统的连续型曲面重建造型相比，离散细分方法显然更 加适合于计算机的处理，所谓细分方法，就是定义一条曲线( 曲面) 为一个不断加细 的多边形( 多面体网格) 系列的极限，是曲面重建和造型的一种离散型方法。 细分曲面造型作为- - s t 离散曲面造型方法，结合了多边形造型和n u r b s 样条造 型的优点，算法简洁、稳定，可适用于任意拓扑网格，在计算机动画造型、c a d 以 及游戏等领域都有广泛的应用背景。近十几年来，细分曲面造型技术得到了迅速发 展，现已经成为计算机图形学中常用的造型工具之一，并已经在一些商业软件中出 现，但在实际应用和研究中还没有出现专门的细分造型系统。 本文研究了离散细分技术在几何体造型中的实际应用，具体实现了一个基于细 分方法的三维几何造型系统。该系统建立了三维建模造型软件与细分模块的接口， 细分方法处理的初始网格，作为数据源从三维数据文件中读取。对于三维形体的网 格表示，常用的方法有两种：三角形网格和四边形网格。针对三角形网格，本文研 究了l o o p 细分格式在该系统中的应用：针对四边形网格，研究了c a t m u l 卜c l a r k 细分格式在该系统中的应用。为了提高效率，本系统把每次细分前的数据保存下来， 供以后细分使用。考虑到j a v a 的网络特性和平台无关性，以及计算机动画、游戏 都朝着网络方向发展，本系统是基于j a v a3 d 环境开发的。该系统可以和3 dm a x 等造型软件接口，利用造型软件的原始建模，快速细分生成具有真实感的任意复杂 的形体。本系统可以作为一个几何造型模块用于游戏、动画的制作中，帮助生成不 同细分层次的形体，具有良好的通用性。 考虑剑传统的各种细分算法形式不同，作用在不同的拓扑网格上，在插值和逼 近e 无法在统一的框架下给予实现。本文的另一个贡献是，在仔细研究了b 样条曲 线的细分牛成方法后，提出了一类光滑曲线细分的统一格式，通过设置控制参数， 使得目前存在的大部分细分格式，不论是基于样条的还是插值型的，都成为其特例， 克服了目前存在的传统细分格式在插值和逼近上不能兼容的缺点。通过大量实例运 行，发现效果良好。 关键闻：离散细分，形体，造型，计算机图形学，j a v a3 0 卜海大学 l ! j ! 士论立 a b s t r a c t w i t ht h eq u lc k l vd e v e l o p m e n to fe o m p u t e rh a r d w a r ea n dc o m p u t e rg r a p h ic s ， t h er e q u i r e m e n to fr e a l i t ys e n s ew h i c hp e o p l ed e m a n df o rm o t iv a t i o na n dg a m e p r o m o t es t e pb ys t e p c o m p a r e dw i t h t h et r a d i t i o n a lc o n s i s t e n c ys u r f a c e m o d e ii n g ，t h ed i s c r e t es u b d i v i s i o nm o d e l i n g i sm o r ef i tt ot h e p r o c e s s f e a t u r eo fc o m p u t e r s u b d i v i s i o ns c h e m ei sa l s oc a l l e dm e s hs u b d i v i s i o f i ，a n d i tm e a n st h a tap i e c eo fc u r v e ( s u r f a c e ) i sd e f i n e dt oap o l y g o n ( p o ly g o n m e s h ) m i t w h i c hi ss u b d i v i d e dm o r ea n dm o r e a san e wr e c u r s i v ed i s c r e t e m o d e l i n gm e t h o d s u b d i v i s i o ns c h e m ec o m b i n e st h ev i r t u eo fp o l y g o nm o d e l i n g a n dn u r b ss p l i n em o d e l i n s t h es c h e m ei sc o n c i s ea n ds t a b l e ，a n di ti sf i t f o ra r b i t r a r yt o p o l o g i c a lm e s h w i t ht h eq u i c kd e v e l o p m e n to fr e c e n t2 0y e a r s ： i ti sw i d e l yu s e di nt h ef i e l d so fc o m p u t e rm o t i v a t i o n ，c a d ，g a m ea n ds oo n n o wi th a sb e c o m eo n eo ft h em o s tc o f f m l o nm o d e l i n gt o o l so fc o m p u t e rg r a p h i e s ， a n da p p e a t 、e di ns o m ee o r a m e r c i a lm o d e l i n gs o f t w a r e h o w e v e r ，t h e r ei sn o ta n y s p e c i f i cm o d e l i n gs y s t e mt h a ti sb a s e do ns u b d i v i s i o n t h jst h e s i si st om a k er e s e a r c ha n dd is e u s s i o r s o ft h e p r a t t i c e a p p li c a t j o na b o u th o wt h es u b d i v i s i o nm o d e l i n gt e c h n o l o g yi su s e di ns u l 、f a c e m o d e l i n g ，a n df u l f i i l e da3 d i m e n s i o n sg e o m e t r ym o d e l i n ss y s t e m t h ed a t a s o u r c eb e i n ga st h ei n i t i a im e s ho ft h es u b d i v i s i o np r o c e s si sr e a df r o m 3 - d i m e n s i o nd a t af i l e s t h et h e s i sm a d er e s e a r c ho ft h eo u t p u to ft h eb u i t d i n g m o d e l i n go f3d i m e n s i o nm o d e l i n gs o f t w a r e t h e r ea r et w ok i n d so fm e s h e s i n 3 - d i m e n s i o no b j e c t o n ei st r i a n g l em e s h ，a n dt h eo t h e ri sq u a d r a n g l em e s h c o m b i n e dw i t ht h et w ok i n d so fm e s h ，t h et h e s is m a d er e s e a r c ho ft h e a p p l i c a t i o no ft h el o o ps u b d j v i s i o ns c h e m ea n dt h ec a t m u l l 一c i a r ks u b d i v i s i o b s c h e m ejnt h es y s t e m i no r d e rt om a k ee f f i c i e n t ，t h es y sc e ms a v e dt h ed a t a b e f o r e e v e r y s u b d i v i s i o n s t e p t o p r o v i d e f o rt h el a t e rs u b d i v i s i o n c o n s i d e r e dl h en e t w o r kd e v e l o p i n gd i r e c t i o no fg a m ea n dj a v a ，t h es y s t e mi s d e v e l o p e db a s e do nj a v a3 d e n v i r o n m e n t ，t h es y s t e mc a nu s et h em o d e l i n go f 3 dm a x ，c a nq u i c k l yg e n e r a t ea n yc o m p l e xs h a p ew i t hr e a l i t y i tc a nb eu s e d “ t h ep r o c e s so fg a m e ，m o t i v a t i o n ，a n dg e n e r a t ev a r i o u ss u b d i v i s i o n1 e v e l s h a p e ，t h ea p p r o a c hi sg e n e r o u s c o n s i d e r e dt h a tt h et r a d i t i o n a li n t e r p o l a t i n g a n d t h e a p p r o x i m a t i n g s c h e m e sc a n n o tb ef u l f i l l e di nau n i f yf r a m e a f t e rd i s c u s s i n gt h er e l a t i o n b e t w e e ns u b d l v i s i o ns c h e m e a n db s p l i r e ，b ys e t t i n g s e v e r a lc o n o l ! 堡奎兰堡主望苎 p a r a m e t e r s ak i n d o fu n i f i e ds c h e m ef o rs m o o t h c u r v e s g e t ) e r a t i o n is p r o p o s e d ，a n di tm a d et h a tt h em o s te x is t n gs u b d i v i s j o ns c h e m e s w h a t e v e r i tlsb a s e do ns p l i n eo ri n t e r p o t a t i n g ，b e c a m et h es p e c i a lc a s e si nt h i sf r a m e m o r e o v e r ，i to v e r c a m et h es h o r t c o m in go ft h a tt h et r a d i t i o n a ls u b d i v i s i o n s c h e m ec a n n o tc o m b i n ei n i n t e r p o l a t i n ga n da p p r o x i m a t i n g al o to fe x a m p l e s w e r ea l s or u nt os h o wt h ev a l i d i t ya n de f f i c i e n c yo ft h i su n i f i e ds u b d i v i s i o n f r a m e k e y w o r d s ：d i s c r e t es u b d i v i s i o n ，s h a p e ，m o d e li n g ，c o m p u t e rg r a p h i c s j a v a3 d 原创性声明 本人声明：所呈交的论文是本人在导师指导f 进行的研究工作。除 了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰 写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意。 签名： 日期 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校 有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 日期： 卜海大学倾 论立： 第一章绪论 本章前两节简要介绍曲面造型的背景及发展历史，第三节则是本文工作内容及 后续章节的安排。 1 1 曲面造型技术 c a d c a m 是现代设计和制造系统中的一项核心技术，已成为衡量一个国家科技 现代化和工业现代化的重要标志。曲面造型技术一直是c a d c a m 系统中关键的部分 之一。五十多年来，曲线曲面造型技术从参数样条、c o o n s 曲面、b 6 z i e r 曲线曲面 和b 样条到n u r b s ，己取得了辉煌的成果，并随着c a d c a m 技术应用的深入而不断 发展、日趋完善 i 、2 。 1 9 6 3 年弗格森( f u g e r s o n ) 首先在飞机设计中应用了参数三次曲线，并构造了 组合曲线和由四角点的位置矢量及两个方向上切矢定义的弗格森双三次曲面片。 1 9 6 4 年，孔斯( c o o n s ) 提出了一个具有一般性的曲面描述方法，即给定围成封闭 曲线的四条边定义块c o o n s 曲面片。1 9 7 1 年b 6 z i e r 提出了一种控制多边形定义 曲面的方法一b z i e r 方法，人们可以方便地逼近数学曲线或设计师勾画的草图，真 正起到“辅助设计”的作用。b 6 z i e l 曲线曲面在c a d c a m 领域发挥了重要的作用。 但是b 6 z i e r 方法也有缺点。首先，方法不具备局部性，亦即特征多边形( 网格) 的每个顶点都对曲线、曲面的形状做出贡献。修改任一顶点都会影响整条曲线或整 张曲面的形状，故不能做局部修改。其次，当曲线、曲面的形状复杂时，需增加特 征多边形的顶点数，曲线、曲面的幂次较高时，b e z i e r 曲线、曲面的形状与其定义 多边形( 顶点网格) 有较大的差异，办即不够直观 3 。 1 9 7 2 年w g o r d o n 和r r i e s e n f e l d 在b 6 z i e r 方法的基础上，提出了b 样条方 法，b 样条方法不仅保持了b 6 z i e r 方法的优点，克服了b 6 z i e r 方法存在的缺点， 较成功地解决了局部控制问题，又在参数连续性基础上解决了连接问题，并提供了 节点插入和升阶等配套技术。但在自由曲线曲面设计中经常会遇到的二次益线与二 次曲晒表示的形状，b 样条方法不能对其做精确表示( 抛物线和抛物面除外) 。为此 v e r s p f ，i 1 1 e 在r i e s e n f e l d 的研究基础上，在1 9 7 5 年提出有理b 样条方法。最后在 p i g e l 和t 订l e t 等人的努力下，终于在8 0 年代后期发展起来非均匀有理b 样条 ( n u r b s ) 的一整套方法，把有理和非有理b 6 z i e r 曲线和b 样条曲线曲面及圆锥曲线 和初等解析曲面统一在种表示之中，最终使n u r b s 成为c a d c a m 行业的工业标准 3 、4 、5 。n u r b s 具有功能完善的几何配套工具( 包括节点插入细分消去升阶 j ：海人学坝h 它文 分割等) ，能用于设计、分析、与操作等各个环节等在曲线曲面造型上还是显示了强 大的威力，使它成为c a d c a m 行业的工业标准。与此同时，一些c a d c a m 软件纷纷 开发和推出n u r b s 功能，n u r b s 方法在实践中不断得到补充、完善和发展。 随着计算机图形显示对真实性、实时性和交互性要求的日益增强，随着几何设 计对象向着多样性、特殊性和拓扑结构复杂性靠拢的趋势的f | 益明显，随着图形工 业和制造工业边向一体化、集成化和网络化步伐的日益加快，随着激光测距扫描等 三维数据采样技术和硬件设备的目益完善，曲面造型在近几年来得到了长足的发展。 曲而造型技术已从传统的研究曲面表示、曲面求交和曲面拼接，扩充到曲面变形、 曲面重建、曲面简化、曲面转换和曲面位差等 6 j 。 曲面的表示方法大致包括以下四类：多边形网格表示方法，参数曲面表示方法， 隐式曲面表示方法和细分曲面表示方法 7 。 1 多边形网格表示方法 多边形网格表示方法，是最直接的表示方法，在计算机图形学诞生之时就已开 始使用。而今，配合纹理映射与光照材质，仍广泛地运用于各类动画系统。多边形 网格的最大优点是数学模型简单，它直接使用点、直线段和平面面片来逼近真实的 形体，因此容易理解，适于绘制。在具体系统中，它往往是其他表示方法与绘制模 块的中| 白j 媒介。对于多边形网格表示，为解决在计算机中的灵活存储与快速检索的 平衡问题，人们提出了翼边( w i n g e d g e ) 数据结构以取代单纯使用数组来表示顶点、 边界和多边形面的原始方法，而后它被改进为更加简洁的半边( q u a d - e d g e ) 数据结构 f 8 。 2 参数曲面表示方法 参数曲线曲面表示直是描述几何形状主要工具，它起源于飞机船舶的外形放 样设训。工艺。由c o o n s ，b 4 z i e r 等人在6 0 年代奠定其理论基础。1 9 7 1 年，法国r e n a u l t 汽车公司的b 6 甜e f 提出了用控制网格定义曲线的方法，并将其成功地用于自由曲线 曲面设计系统u n i s u r f 中。稍早于他，法国c i t r o e n 汽车公司的d ec a s t e j a u 曾 得出类似方法，但未公开结果。b 4 z i e r 曲线具有端点插值等多种良好交互性。而后 f o r r e s t 分析了最初的b e z i e r 定义形式，将其转化为基于控制顶点和b e r n s t e i n 基 表示的现代定义形式 9 。在此基础上，人们陆续提出了张量积形式和三角域上的 b e r n s t e i n b e z i o r 劓b - b 曲面。 b 6 z i e r 曲线曲面仍旧存在着难于处理连续拼接和难于进行局部控制的不足。有 鉴于此，d eb o o r 1 0 和c o x 1 1 在 9 7 2 年分别独立地提出了b 一样条的d eb o o r c o x 递推公式。1 9 7 4 年，通用汽车公司的g o r d o n 和r i e s e n i e l d 首次将b 一样条理论应用 i 形状描述，提出b 样条曲线曲面，使之得以广泛的应用。该方法继承了b 6 z i o r l 海人学坝l 论文 方法的优点，而且较成功地解决了局部控制问题，并在参数连续性的基础上解决了 拼接问题。但是它不能精确表示除抛物线外的二次曲线曲面，只能给出近似表示。 1 9 7 5 年，v e r s p r i l l e 在其博士论文中首先提出了有理b 样条方法它可解决二次曲 面的精确表示问题。而后主要由于p i e g l 和t l l l e t 等人的功绩 1 2 ，1 3 ，至8 0 年 代末，非均匀有理b 一样条( n o n t n i f o r mr a z i o n a lb - s p l j l 3 e ) 即n u r b s 成为曲线曲 面描述中的最流行技术。1 9 9 1 年国际标准组织i s o 颁布的工业数据交换标准s t e p ， 将n u r b s 作为定义工业产品几何形状的唯一数学方法 1 4 。整个9 0 年代是n u r b s 走向完美的阶段，今天的多数主流造型系统都包含有n u r b s 功能，如著名的几何建 模软件r h i n o 就完全用n u r b s 作为其基本的数学表示模型。 总之，参数曲线皓面造型的基本思想是以一组基函数为权因子，利用一组初始 控制向量的线性( 或有理线性) 组合来得到形体的连续表示。如今，该类方法已经形 成以拟合( f i t t i n g ) 、插值( i n t e r p o l a t i o n ) 和逼近( a p p r o x i m a t i o n ) 这三种手段为主 的实用几何理论体系。 3 隐式曲面表示方法 在数学和计算机科学中，以隐函数定义几何物体的方法也比较常见。在三维空 涮情形，我们可用不等式f ( x ，y ，z ) 0 所定义的半空间来描述实体；用等式 f ( x ，y ，：) = 0 所定义的空间边界来表示隐函数曲面，当函数厂是多项式时，上式定义 了一张代数曲面。隐函数表示的优点是几何求交方便，而且善于表示封闭光滑形体， 因此更适于面向绘制的应用。二次代数曲面是最早实用化的曲面模型之一，作为实 体造型方法的基础，它可以方便地表示球体，圆锥面，抛物面和双曲面。 离散扫描表示，包括图像和体数据可被看成是某个连续函数g ( x ，y ) 在整数格点 上的取值g 进一步，令g ( ，y ) 一g ，。：0 即转化为隐函数表示。基于此观点，可方 便地进行图像光淆设计、边缘提取、距离场求解等多种图像处理操作；它也是这一 领域的主要思想方法。 参数曲面在表现人体的肌肉、器官及其运动等方面存在着许多困难。为此，8 0 年代，b 1 i n l 提出了b l o b b y 模型；n i s h m u r a 提出了类似的m e t a b a t l 模型 1 5 ，并 作了很多开拓性的工作。m e t a b a l l 造型是一种隐函数造型技术，该技术采用具有等 辫场值的点集来定义自由曲面，其造型过程与c s g 造型相似。经过发展 1 6 ，现在 它己在各类动画造型软件，如著名的人体建模软件p o s e r 中广为应用。 4 细分曲面表示方法 上海人掌顿士论文 细分表示方法虽然于七十年代已被明确地提出来 1 8 ，但直到九十年代随着计 算机硬件能力的提高和应用的深入，才得以大放异彩。它是( 1 ) ( 2 ) 两种方法的有机 结合，大有后来居上之势。我t l j 4 , 哿在第一二章中给出详细的综述。 综观以上这四种形体静态表示方法，我们认为它们各有其优缺点和适用场合， 图1 1 列出了在描述曲面情况时应用以卜四类方法的性能比较。当然一个必然会产 生的问题是各种系统之间，各种表示形式之间以及曲线曲面相同表示形式的不同精 度和不同次数之间的数据转化。 a c c u r a t e c o n c i s e i n t u i t i v es p e c i f i c a t i o n l o c a is u p p o r t a 竹i n ei n v a r i a n i a r b i t r a r yt o p o lo g y g u a r a n t e e dc o n t i n u i t y n a t u r a lp a r a m e t e r i z a t i e f f i c i e n id i s p l a y e f f i c i e n ii n t e r s e c t i o n s 鹫1 1 曲面的四种静态表示方法的性能比较【1 9 除了以上四种基本曲面表示方法之外，还有一些常用的造型方法，如变形曲面 造型技术，基于形状混合的曲面造型技术，以及其它曲面造型技术。 1 2 细分造型技术 缅分曲面( s u b d i v is i o ns u r f a c e s ) 是一个网格序列的极限，网格序列则是通过 采用组规则(般是加权平均) 在给定初始网格中插入新顶点并不断重复此过程而 获得。这种方法克服了参数曲面处理任意拓扑网格( a r b i t r a r yt o p o l o g ym e s h e s ) 存在的困难。因为，在不规则拓扑处只须采用特殊的细分规则就可以了，不存在拼 接的问题。 细分方法，尤其是作为其主体的细分曲面的生成技术，是一种全新的形体表示 思路。如所周知，以参数形式和隐函数形式表示曲面的计算机处理方法总要将用户 海人学岫i 论互 给定的离散控制顶点和其他信息输入计算机，通过插值、逼近或者拟合的方法转化 为连续表示，然后在显示和其他处理坏节再次转换回离散形式。这是个从离散到 连续，再到离散的过程。而且当形体变得复杂后，以上处理往往随之复杂，造成计 算代价的明显增加。多边形网格表示的直接方法虽然避免了当中的连续转换环节， 但其存储代价高、冗余表示多，不利于统一处理 7 。 细分方法就是个直接从离散到离散的过程，但它同时具有参数表示的许多优 点。从图1 2 的分析可以看出，用细分方法表示形体，少了生成连续曲线曲面这个 步骤，并且只存储离散点列，适合计算机处理的特点，可以大大加快计算机处理速 度。同时该造型方法可以有效作用于任意拓扑结构的形体，比较容易操纵和绘制， 特别适合于复杂形体的造型i 2 7 。 离散点笔旨嘉i 呜连续曲线或曲面星叠斗离散点( 传统方法) 山型塑堕型型型叫个( 细分方法) 剧1 2 传统方法和细分方法去面造型的比较 从个称之为控制网格( 网格多半可用激光从手工模型上输入) 的多面体开始， 递归地计算新网格上的每个顶点，这些顶点都是原网格上某几个顶点的加权平均。 如果多面体的一个面有n 条边，绌分一次后，这个面就会变成n 个多边形。随着细 分的不断进行，控制网格就被逐渐磨光，其极限状态就是一一张自出曲面。它是无缝 的，因而是平滑的，邸使模型是活动的。这种方法显著地压缩了设计和建立一个原 始模型的时间。更重要的，允许原始模型局部地精制化。这就是它优于连续曲面造 型方法之处。 1 2 1 细分造型技术的发展背景 在计算机辅助几何设计中，自由曲线曲面往往由离散数据通过指定的基函数表 示成连续的参数形式。但这种连续的信息一旦用于实际，如在计算机屏幕或在绘图 仪上绘制出来，或数控机床进行加工，还需要将连续的模型离散化。这是个“离散一 连续一离散”的过程，相反，放弃连续模型，直接用离散数据表示、操作曲面曲线更 适合于显示、加工和曲面求交运算等，也更适合于外形设计。另一方面，尽管b 样 条曲面在c a d 中已得到广泛的应用，n u r b s 己成为c a d c a m 行业的工、i p 标准，但是， u r b s 曲面只能表示敞开的矩形域面、柱面和环面等三种简单的拓扑结构。其最大 的困难在于本身无法解决任意拓扑结构，特别是闭曲面造型等问题，难以处理生产 工程和计算机圈形显示中所遇到的复杂曲面。通常采用逐片构造方法表示复杂物体 表面，这时候需要对曲面片进行剪裁( t r i m m i n g ) 或直接在非规则的四边形网格上 构造曲面片，但代价昂贵，又有数值误差；同时，对特征动画来说，在片与片之间 的光滑连接是困难的。因为模型是运动的 2 9 。此外，n u r b s 曲面要求各行( 列) 上海大学坝，h 仑丈 控制点的个数一样，各控制点的位置和有理因子的相对分布也不能不均匀。但是细 分曲面能克服以卜困难。 另一方面，由于二维扫描仪( 3 ds c a n n e r ) 、测距仪( r a n g ef i n d e r ) 和c t 等三维 数据获取设备的同益完善，为几何形状不能或难于用分析曲面表示的对象建模提供 了有力的工具，例如医学的人体器官建模、考古学中的古代器件和艺术领域的雕塑 作品三维重构 2 9 等等。离散曲面逐渐成为一种重要的几何表示方法。细分格式 作为从给定规则产生离散曲面的方法，统一了传统的参数曲面与多边形两种实体表 面的表示。另外，由于实验获取的三维数据量一般都非常大，多分辨率分析 ( m u l t i r e s o l u t i o na n a l y s i s ) 成为有效地处理这类数据的重要手段。细分方法与多 分辨率分析、小波变换( w a v e l e tt r a n s f o r m a t i o n ) 之问的深刻联系也是目前细分方 法受到关注的一个重要原因。 i 2 2 细分造型技术的发展阶段 细分方法可以追溯到5 0 年代gr h a m 的通过对折线角点进行切割( c o r n e rc u t ) 来生成光滑曲线的思想。7 0 年代中期，c h a i k i n 生成曲线的细分方法 4 1 正是这种 角叨割思想的具体实现。稍后c a t m u l l 和c l a r k 提出了著名的c a t m u l l c l a r k 细分 格式 1 8 ，标志着细分方法正式成为曲面建模的手段。当矩形网格没有奇异顶点( 共 幽l3 细分方法形成与发展时间表 l q 8 t 吣b t o 制角 浊总 享顶点的边数，称为顶点的价。对于四边形网格，价不等于4 的顶点称为奇异顶点) 时，c a t m u l 卜c l a r k 格式生成三次b 样条曲面；对于有奇异顶点的网格，生成的曲 面除有限个点外，具有二阶光滑，可以说是一张“几乎处处连续”的三次b 样条曲 面。与此同时，d o o 和s a b jn 采用离散f o u rj e r 变换的方法，对c a t m u 卜c a r k 格 海大学删士论史 式的收敛性进行了分析，开创了细分格式收敛性矩阵特征分析的先河。大致可以把 细分方法的发展历史分成如下三个阶段： 7 0 年代后期c a t m u 卜c l a r k 细分格式以及d o o s a b f n 关于奇异点处行为的分析 理论标志着细分方法正式成为曲线曲面造型的一种手段。 8 0 年代术到9 0 年代初的形成期。在这阶段，提出了很多著名的细分方法， 对1 日方法也有许多改进以适应不同要求。规则情形的收敛性和连续分析理论也逐渐 完善，例如给出了单变元细分格式任意阶光滑的充要条件 3 0 。不过，各种格式之 间仍然缺乏联系，般情形的收敛性分析方法也是“随身定作”，缺乏一般的理论指 导。 9 0 年代中期到现在的发展期。这一时期开始建立系统的收敛性理论，提出了多 变元格式任意拓扑情形下收敛性分析的理论框架 3 1 ，3 2 ，3 3 。这些理论反过来指 导细分格式的构造，尤其是二阶以上连续曲面的构造。此外，各种细分格式的内在 联系也逐渐被揭示出来，例如z o r i n 和s c h r s d e r 为主( p r i m a l ) 四边形网格细分格式 和对偶( d u a l ) 四边形网格细分格式建立了统一的框架 3 4 。更为重要的是，在这一 时期，细分方法得到了广泛应用，尤其是复杂网格曲面的多分辨率分析的研究取得 了大量成果。 最近，细分规则的统性研究成为热点。参照一般次数的均匀b 一样条离散规则， z o r i n 3 5 提出了针对四边网格p r i m a l d u a l 的一个统一细分框架。与此同时， s t a m 3 6 也进行了类似的研究。他们给出了将任意次的均匀b 样条推广到任意拓扑 网格的统一算法，丽不必再针对不同次的b 样条构造不同的细分规则。m a i l o t 3 7 和张宏鑫 7 分别提出了回插细分算法，可对细分过程提供更多的控制手段。并且， m a i l l o t 的方法还可应用于生成任意网格的层次细节( l e v e lo fd e t a i l ) 模型。相应 地，o s w a l d 等找到了一类三角网格的统一细分形式 2 1 ，并由其对偶形式导出一 类新颖的基于六边形网格的细分方法 7 。 1 3 本文的组织结构 绌分方法有坚实的理沦基础，对于该理论，在计算机几何造型中，如何实际应 用，是本文要探讨的内容。 本文研究了l o o p 细分格式和c a t m u 1 一c l a r k 细分格式在基于、；a v a3 i ) 的几何造 型系统中的应用，该系统可以快速生成具有真实感的任意复杂的形体。 传统的算法在插值和逼近上无法在统一的框架下给予实现。本文通过设簧控制 参数，提出了一类光滑曲线细分的统一格式，使得目前存在的大部分细分格式，不 论是基于样条的还是插值型的细分格式，都成为其特例，从而克服了目前存在的传 统细分格式在插值和逼近上不能兼容的缺点。 第一章主要介绍本文工作的背景以及本文的贡献。 第二章是细分方法的综述，归纳了细分方法在以后两章的实际应用中用到的 些理论，包括细分曲面概念、细分格式的分类、l o o p 细分格式、c a t m u l 卜c l a r k 细 分格式以及细分方法的特点等内容。 第三章介绍细分方法在基于j a v a 3 d 的几何体造型系统中的应用。搭建了一个 j a v a3 d 开发平台，研究了细分模块与造型软件的接口，做了一个语法分析器；针 对三角形网格和四边形网格，分别研究了l o o p 细分格式和c a t m u l 卜c l a r k 细分格 式在造型系统中的应用，开发出了一个可以与3 d m a x 造型软件接口的通用造型系统， 给出了一些细分实例及相应数据。 第四章介绍了种统一细分格式。研究了细分理论与b 样条曲线之划的关系以 及如何用细分方法生成b 样条曲线，并提出了一种基于控制参数的统一细分格式， 最后给出一些特殊的格式及相应的数值例子，验证该理论的效果。 卜诲人学顺卜论立 第二章细分理论与经典细分格式 本章主要归纳了细分方法在实际应用中用到的一些理论，以及后面要用到的两 种细分格式。 在第一章介绍曲面造型过程中，提到曲面细分是当前造型方法的研究热点，它 能处理传统方法中难于处理的问题。它是多边形网格的极限状态，在实现时也只能 把它当作某一细分层次的多面体来处理，可以说细分方法处理的就是多边形网格， 因此有必要对多边形网格及与其有关的概念做较为形式化的处理。 2 1 细分曲面基本概念 简略地说，多边形网格就是一个多面体的表面，是由顶点、边和面组成的一个 集合。它和图论中的图相比多了一种元素，即由顶点和边构成的面。如果忽略网格 顶点的几何位置信息，只考虑网格的拓扑关系，那么得到一种抽象的多边形网格 7 。 考虑任意一个控制多边形网格尸o ，p o 可表示为一个三元组p o = ( p o , y ”，e 。) ， 其中p o = f 。) 为多边形集，v 。2 口) 为顶点集，e 。= e ： 为边集。这里，网格 ( m e s h e s ) 是指由顶点、边和面构成的整个或部分多面体表面 3 8 。 如果所有网格面均为三角形，称其为三角网格( t r i a n g u l a rm e s h e s ) ；类似地有 四边形网格( o u a d r i l a t e r a lm e s h e s ) ：如果p 司格面中包含有不同类型的多边形面， 则称为任意多边形网格( a r b it r a r il yp o ly g o n a lm e s h e s ) 。 一个网格顶点的邻接边条数称为它的入度( v a l e n c e ) 。对三角( 四边形) 网格，入 度为六( 四) 的顶点称为规则的( r e g u l a r ) ，否则称为非规则或奇异的( i r r e g u l a i e x t r a o r d jn a r y ) 。如果三角( 四边形) 网格的所有内部项点的入度都为六( 四) ，则 称该网格是规则网格，否则称为非规则网格。如果一条网格边的两个端点都是规则 的，则称该边为规则边；一个网格面的所有顶点都是规则的，则称其为规则面。 如果网格的一条边只属于一个面，称这条边为边界边( b o u n d a r ye d g e ) ：如果 个顶点属于边界边则称此顶点为边界顶点( 或边界点，b o u n d a r yv e r t e x ) ：至少 包含个边界顶点的面称为边界面( b o u n d a r yf a c e ) 。非边界的边、顶点和面分别称 为内部边( i n t e r n a le d g e ) 、内部顶点( i n t e r n a lv e r t e x ) 和内部面( i n t e r n a f a c e ) 。 ：海人学坝 论文 如果一个网格有边界边，称其为开网格，否则称为闭网格。 【3 9 。 2 2 细分格式及分类 细分曲面( s u b d i v i s i o ns u f f a c e s ) ，也称子分面或剖分曲面。利用一组拓扑规 则和几何规则对除是多边形网格进行细化，生成更细密的新网格。不断重复这一过 程，得到一个网格序列。其极限 m 。= l i m m o 称为细分曲面( s u b d i v is i o ns u r f a c e s ) ，有时细分曲面称为极限曲面。其中，拓扑 规则确定新网格的顶点插入方法及连接关系，而几何规则则用以计算新网格顶点的 位置。拓扑规则和几何规则的集合称为细分格式( s u b d i v i s i o ns c h e m e ) ，几何规则 的图形表示称为模板( m a s k s ) 细分曲面的重要特点是思想简洁、适用于任意拓扑网 格且具有多分辨率结构。 细分拓扑规则必须使得网格不断加密。一般可以用网格的基本元素( 即顶点、 边和面) 的分裂操作来加以描述，因此也称为分裂算子( s p l i t t i n go p e r a t o r s ) 。待 分裂的网格称为旧网格，所得的结果称为新网格。在每个网格面中插入的新顶点称 为f 一顶点，在每条边中插入的新顶点则称为e 一顶点，而新网格中与原来顶点对应的 顶点称为v 一顶点。 般地，细分格式的每次细分或加细( r e f i n e m e n t ) 可分解成两步操作。 首先， 通过增加新顶点形成新的网格拓手卜，称为网格分裂( s p l i t t i n g ) ，所用的方法称为拓扑 规l j ( t o p o l o g i c a lr u l e s ) ，分裂操作可在在单纯复形上进行。其次，计算所有顶点的位 置，这一过程称为平均( a v e r a g i n g ) ，相应的方法称为几何规贝j j ( g e o m e t r i cr u l e s ) 。 典型的拓扑分裂方法有两种：顶点分裂和面分裂。 簿e - n 移 顶点分裂规则。左蚓：原始网格，右幽：顶点1 分裂为 = 个顶点( 窄心圆) ，虚线嘲格为分裂得到的新嗍格。 幽21 面分裂舭则。左尉：塬始驯格，右图 新州格j i 中是v 顶点和e 一点 幽2 2 顶点分裂按如下方式进行：对任意给定的顶点f ，设以其为一个顶点的相邻面 卜海大学蟛! i 艟文 有个，则把顶点i 分裂成历个新顶点，每个顶点与其中一个邻面对应。对每个内 部顶点i ，f ) l l j 把这些新顶点依次相连形成一个 i l 。边形，称为新网格的v 一面。 对每条内部边辑) ，设其两个相邻面为石和六，出i ，分裂的与z 和工相对 应的顶点分别为，之和，j 二t 则连接i ，i 2 ，j ：和_ 形成个四边形面，称为新网 格的e 一面。 对每个多边形面厂，依次相连与每个顶点对应的新顶点，得到一个与面厂边数 相同的面，称为f 一面。如图2 i 所示。 面分裂是在网格边和面上插入适当的新顶点，然后对每个面进行剖分，从而得到 新网格如果不对分裂作任何限制，情况可能相当复杂这里我们针对三角网格和 四边形网格给出两种以后用到的面分裂形式。 ( 1 ) 卜4 三角形分裂：在三角网格的每条边上插入一个新顶点，称为边顶点( e 一顶点) 。 然后把每个三角形面的三条边的e 顶点两两相连，从而把该三角形面分裂成四个小 三角形面，原网格的顶点则称为顶点点( v 一顶点) ，如图2 2 所示。 ( 2 ) 卜4 四边形分裂：思想与( 1 ) 类似，只是这里把一个四边形面分裂成4 个四边形 面，因此除边顶点外还要在面的中心插入一个新顶点，称之为面顶点( 卜顶点) ，e 一 顶点和v 一顶点定义同( 1 ) ，如图2 3 为四边形网格的卜4 分裂示意图 圈2 3 从左到右：初始网格、一次1 4 分裂后的网格 自细分算法提出以来，已经出现了许多细分格式，例如c a t m u l 卜c l a r k 格式、 l o o p 格式、蝶形格式、d o o s a b i n 格式等，各有其特色和适用范围。本节将从儿个 不同的角度对细分方法作一个粗分类 2 7 。 ( 1 ) 根据几何规则与细分层次的关系分类。 若几何规则在细分过程中保持不变，则称为静态细分方法( s t a t i o n a r y ) ；反之 称为动态细分方法( d y n a m i c ) ( 2 ) 根据