（机械制造及其自动化专业论文）基于cb样条的catmullclark细分曲面造型技术的研究.pdf

l 礤 3 9 9 g 3 摘要 p ( 细分方法在国际上已成为图形学的研究热点，特别是c a t m u l l - - c l a r k 细分 方法最为流行。尽管c a t m u l l c l a r k 细分曲面的算法在计算机图形显示中非常成 功，然而近年来工程上的曲面造型却仍然停留在n u r b s 曲面上，改进不大。其 主要原因是基于均匀三次c a t m u l l - - c l a r k 的细分方法难以精确地处理工程上最 常见的圆和圆柱等。) 本文结合国家自然科学基金项目，通过对细分方法及c - b 样条曲线、曲面的分析和研究，完善了c b 样条的功能，成功地将c - b 样条应用 于c a t m u l l - - c l a r k 细分曲面，得到基于c b 样条的c a t m u l l - - c l a r k 细分算法， 为细分曲面用于工程造型进行了成功的试验。这种新的细分曲面方法不但能够象 c - b 样条曲线、曲面一样，精确地表示圆柱等常规曲面，统一工程曲面的造型： 同时它仍然保持细分曲面的造型特点：解决n u r b s 曲面难以解决任意拓扑结构的 造型问题，初步解决了细分方法在工程上难以应用的问题。同时由于控制参数a 的调节作用，改善了曲面的细分效果。住要研究内容如下： 首先，介绍和分析了曲面细分的现状、特点和相关算法，较为全面地讨论了 c a t m u l 卜c l a r k 、d o s a b i n 、和l o o p 等细分模式的基本原理和算法，比较了他们 的优缺点，指出了c a t m u l l c 1 a r k 方法在细分曲面中的优势。 然后，在分析c 曲线的基础上，研究了c b 样条曲线、曲面的特性，和修 改控制参数和控制顶点对c b 样条曲线形状的调节作用，实现了用c b 样条来 表示圆弧和椭圆弧。同时又进一步将结果推广到曲面上。构造了平移、旋转、椭 球等常见的工程曲面。 最后，利用c b 样条细分算法的特性 同时提出一种新的在奇异点处的细分算法 将它用于c a t m u l l - - c 1 a r k 细分曲面， 构造了基于c - - b 样条的c a t m u l l c l a r k 细分曲面，使得c a t m u li - - c l a r k 细分曲面的形状可以调整，并能生成圆 柱等工程上常见曲面。同时还为进一步的研究和试验用v i s u mc + + 和o p e n g l _ 丌= 发了专用的软件包。夕巧 关键词：纽分矧c b 样条，c a t m u l l - - c l a r k 细分曲面，曲线曲面造型 c a d ，c a m a b s t t a c t a l t h o u g ht h es u b d i v i s i o nm e t h o d se s p e c i a l l ya b o u tc a t m u l l - c l a r ks u b d i v i s i o n s u r f a c e sb e c o m em o r ea n dm o r ep o p u l a ri nt h er e s e a r c ho fc o m p u t e rg r a p h i c sa n d a c h i e v eg r e a ts u c c e s s ，t h es u r f a c em o d e l i n gi ne n g i n e e r i n gw a ss t i l lb a s e do nn u r b s s u r f a c ei nr e c e n ty e a r sa n dd e v e l o p e ds l o w l yt h er e a s o no ft h i sp h e n o m e n o ni st h a t c a t m u l l c l a r kb a s e do nc u b i cu n i f o r mb s p l i n e sc a r l ts o l v et h ep r o b l e mo fp r e c i s e r e p r e s e n t a t i o no fs t a n d a r da n a l y t i cs h a p e ss u c ha sc i r c l e ，c o n i c s h o w e v e r , t b r o u 【g h r e s e a r c h i n g t h es u b d i v i s i o nm e t h o do fc b s p l i n e s ，t h i s p a p e r c o n c l u d e san e w c a t m u l l c l a r ks u b d i v i s i o na l g o r i t h mb a s e do nc - b s p l i n e s t h i sn e wm e t h o dn o to n l y s o l v e st h ep r o b l e mo ft h ep r e c i s er e p r e s e n t a t i o no fs t a n d a r da n a l y t i cs h a p e s ，b u ta l s o o v e r c o m e st h ed i f f i c u l t yo fg e n e r a t i n gs u r f a c e so na r b i t r a r yt o p o l o g i c a lm e s h e sf a c e d b yn u r b s t h e m a i nc o n t e n t so ft h i sp a p e ra r ea sf o l l o w i n g ： f i r s t l y t h e a r t i c l ei n t r o d u c e sa n da n a l y z e st h ec h a r a c t e r i s t i c sa n dt e c h n o l o g yo f s u b d i v i s i o nm e t h o d s i td i s c u s s e sc o m p l e t e l yt h eb a s i cp r i n c i p l e sa n da l g o r i t h mo f t h e s o m es u b d i v i s i o nm o d e ss u c ha sc a t m u l l c a r k ，d o - s a b i n ，l o o pm o d e a n dt h e n ， t h e i rc h a r a c t e r i s t i c sa r ec o m p a r e da n dt h ea d v a n t a g e so fc a t m u l l c l a r km o d ei n s u b d i v i s i o na r ep o i n t e do u t f u r t h e r m o r e ，t h e c u r v e sa n ds u r f a c e s m o d e l i n g w i t h c - b s p l i n e s a r e s y s t e m a t i c a l l ys t u d i e d a f t e rt h ea n a l y s i so f c c u r v e ，t h ec h a r a c t e r i s t i c so f c b s p l i n e s a r es t u d i e d a n dt h i sp a p e rp r e s e n t sm e t h o d st oc h a n g et h es h a p ep a r a m e t e r sa n d c o n t r o l p o i n t s a n d s u c c e s s f u l l yd e s i g n s c i r c l e sa n d e l l i p s e s w i t h c - b s p l i n e s m e a n w h i l e ，s o m er e s u l t sa r ea p p l i e di n t o s u r f a c e sw i t hf o l l o w i n gb yc o n s t r u c t i n g g e n e r a lc y l i n d e r s ，r u l e ds u r f a c e s ，s u r f a c e so f r e v o l u t i o n sa n ds oo n f i n a l l y , u s i n gc h a r a c t e r i s t i c so f t h es u b d i v i s i o na l g o r i t h m ，t h i sa r t i c l ea p p l i e si ti n c a t m u l l c l a r ks u b d i v i s i o ns u r f a c e sa n da d v a n c e san e wa l g o r i t h mi ne x t r a o r d i n a r y p o i n t s i no na r b i t r a r y t o p o l o g i c a lm e s h e s ，a n dt h e np u t s f o r w a r dan e wk i n do f c a t n m l l c l a r ks u b d i v i s i o ns u r f a c e sb a s e do nc b s p l i n e s i nt h i sw a y ，t h es h a p e so f t h es u r f a c e sc a nb ea d j u s t e da n dt h es t a n d a r da n a l y t i cs h a p e ss u c ha sc y l i n d e r sc a nb e c o n s t r u c t e d m o r e o v e r as o f t w a r es y s t e mi sd e s i g n e dw i t hv i s u a lc + + a n do p e n g l i no r d e rt or e s e a r c ha n de x p e r i m e n td e e p l y k e y w o r d s ：s u b d i v i s i o ns u r f a c e ，c - b s p l i n e ，c a t m u l l c l a r k s u b d i v i s i o ns u r f a c e ， s t i r f a c em o d e l i n g ，c a d ，c a m 浙江大学硕士学位论文 第1 章绪论 【内容提要】本章在回顾曲面造型技术的发展历史和国内外曲面造型技术现状和趋势 的基础上，简述细分曲面造型技术的产生发展历程；同时在分析c b 样条造型方法主 要特点的基础上给出了本文的选题背景及主要研究内容。 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 技术应 用的深入而不断发展、日趋完善 h u b e l i2 0 0 0 、苏步青1 9 8 1 1 。 1 9 6 3 年弗格森( f e r g u 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 6 z i e r 方法。b 6 z i e r 方法是曲面造型中的个里程碑，它以 逼近原理为基础，应用b 6 z i e r 方法，人们可以方便地逼近数学曲线或设计师勾画 的草图，真正起到“辅助设计”的作用。b 6 z i e r 曲线曲面在c a d c a m 领域发挥 了重要的作用。 但b 6 z i e r 方法也有缺点。首先，方法不具备局部性，亦即特征多边形( 网格) 的每个顶点都对曲线、曲面的形状作贡献。修改任一顶点都会影响整条曲线或整 张曲面的形状，故不能作局部修改。其次，当曲线、曲面的形状复杂时，需增加 特征多边形的顶点数，曲线、曲面的幂次也随之增高，从而增加了计算量。最后， 当曲线的幂次较高时，b d z i e r 曲线、曲面的形状与其定义多边形( 顶点网格) 有较 大差异，亦即不够直观旅法中1 9 9 4 】。 1 9 7 2 年wg o r d o n 和r r i e s e n f e t 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 r i l l e 在r i e s e n f e l d 的研究基础上，于1 9 7 5 年提出有理b 样条方法最 后在p i g e l 和t i l l e r 等人的努力下，终于在8 0 年代后期发展起来非均匀有理b 样 浙江大学顺士学位论文 条( n u m 3 s ) 的一整套方法，把有理和非有理b 6 z i e r 曲线和b 样条曲线曲面及圆 锥曲线和初等解析曲面统一在一种表示之中【搠i 法中1 9 9 4 ，f a r i n1 9 9 7 ，朱心雄 2 0 0 0 】。它具有功能完善的几何配套工具( 包括节点插入细分消去升阶分割等1 ， 能用于设计、分析、与操作等各个环节等，在曲线曲面造型上还是显示了强大的 威力，使n u r b s 成为c a d c a m 行业的工业标准。与此同时，一些c a d c a m 商品软件纷纷开发和推出n u r b s 功能，n u r b s 方法将在实践中不断得到补充、 完善和发展。 1 2 曲面造型技术的现状和发展趋势 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着几 何设计对象向着多样性、特殊性和拓扑结构复杂性靠拢的趋势的日益明显，随着 图形工业和制造工业迈向一体化、集成化和网络化步伐的日益加快，随着激光测 距扫描等三维数据采样技术和硬件设备的日益完善，曲面造型在近几年来得到了 长足的发展。曲面造型技术已从传统的研究曲面表示、曲面求交和曲面拼接，扩 充到曲面变形、曲面重建、曲面简化、曲面转换和曲面位差 k o b b e l t1 9 9 8 1 。 曲面变形( d e f o r m a t i o no rs h a p eb l e n d i n g ) ：传统的n u r b s 曲面模型，仅允许 调整控制顶点或权因子来局部改变曲面形状，至多利用层次细化模型在曲面特定 点进行直接操作；一些简单的基于参数曲线的曲面设计方法，如扫掠法 ( s w e e p i n g ) ，蒙皮法( s k i n n i n g ) ，旋转法和拉伸法，也仅允许调整生成曲线来改变 曲面形状。计算机动画业和实体造型业迫切需要发展与曲面表示方式无关的变形 方法或形状调配方法，于是产生了自由变形( f f d ) 法。 曲面重建( r e c o n s t r u c t i o n ) ：在精致的轿车车身设计或人脸类雕塑曲面的动画 制作中，常用油泥制模，再作三维型值点采样。在医学图象可视化中，也常用 c t 切片来得到人体脏器表面的三维数据点。从曲面上的部分采样信息来恢复原 始曲面的几何模型，称为曲面重建。采样工具为：激光测距扫描器，医学成象仪， 接触探测数字转换器，雷达或地震勘探仪器等。根据重建曲面的形式，它可分为 函数型曲面重建和离散型曲面重建这两类。 曲面简化( s i m p l i f i c a t i o n ) ：与曲面重建一样，这一研究领域目前也是国际热 点之- - k a l v i nt 9 9 6 1 。其基本思想在于从三维重建后的离散曲面或造型软件的输 出结果( 主要是三角网格) 中去除冗余信息而又保证模型的准确度，以利于图形 显示的实时性、数据存储的经济性和数据传输的快速性。对于多分辨率曲面模型 而言，这一技术还有利于建立曲面的层次逼近模型，进行曲面的分层显示，分层 传输和分层编辑。具体的曲面简化方法有：网格顶点剔除法，网格边界删除法， 网格优化法，最大平面逼近多边形法以及参数化重新采样法。 浙江大学硕士学位论文 曲面转换( c o n v e r s i o n ) ：同一张曲面可以表为不同的数学形式，这一思想不仅 具有理论意义，而且具有工业应用的现实意义。例如，n u r b s 这种参数有理多 项式曲面虽然包括了参数多项式曲面的一切优点，但也存在着微分运算繁琐费 时、积分运算无法控制误差的局限性。而在曲面拼接及物性计算中，这两种运算 是不可避免的。这就提出了把一张n u r b s 曲面转化成近似的多项式曲面的问题。 同样的要求更体现在n u r b s 曲面设计系统与多项式曲面设计系统之间的数据传 递和无纸化生产的工艺过程中。再如，在两张参数曲面的求交运算中，如果把其 中一张曲面的n u r b s 形式转化为隐式，就容易得到方程的数值解。 曲面位差( o f f s e t ) ：也称为曲面等距性，它在计算机图形及加工中有广泛应用， 因而成为这几年的热门课题之。例如，数控机床的刀具路径设计就要研究曲线 的等距性。但从数学表达式容易看出，一般而言，一条平面参数曲线的等距曲线 不再是有理曲线，这就越出了通用的n u r b s 系统的使用范围，造成了软件设计 的复杂性和数值计算的不稳定。因此解决等距性问题难度很大，但具有广泛的应 用。 1 3 细分曲面造型技术的发展背景和阶段 1 3 1 细分曲面造型技术的发晨背景 在计算机辅助几何设计中，自由曲线曲面往往由离散数据通过指定的基函数 表示成连续的参数形式。但这种连续的信息一旦用于实际，如在计算机屏幕或在 绘图仪上绘制出来，或数控机床进行加工，还需要将连续的模型离散化。这是个 “离散连续一离散”的过程，然而，以连续表示作为中间媒介有时并非必要， 而且还增加麻烦，降低效率。相反，放弃连续模型，直接用离散数据表示、操作 曲面曲线更适合于显示、加工和曲面求交运算等，也更适合于外形设计。另一方 面，尽管b 样条曲面在c a d 中己得到广泛的应用，n u r b s 已成为c a d c a m 行业的工业标准，但是，n u r b s 曲面只能表示敞开的矩形域面、柱面和环面等 三种简单的拓扑结构。其最大的困难在于本身无法解决任意拓扑结构，特别是闭 曲面造型等问题，难以处理生产工程和计算机图形显示中所遇到的复杂曲面。通 常采用逐片构造方法表示复杂物体表面，这时候需要对曲面片进行剪裁 ( t r i m m i n g ) 或直接在非规则的四边形网格上构造曲面片，但代价昂贵，又有数值 误差；同时，对特征动画来说，在片与片之间的光滑连接是困难的。因为模型是 运动的f 王国谨2 0 0 1 1 。此外，n u r b s 曲面要求各行( 列) 控制点的个数一样，各 控制点的位置和有理因子的相对分布也不能太不均匀。但细分曲面能克服以上困 难。 细分曲面( s u b d i v i s i o ns u r f a c e s ) 是一个网格序列的极限，网格序列则是通过采 浙江大学硕士学位论文 用一组规则( 一般是加权平均) 在给定初始网格中插入新顶点并不断重复此过程而 获得。这种方法克服了参数曲面处理任意拓扑r l l l 当r ( a r b i t r a r yt o p o l o g ym e s h e s ) 存 在的困难。因为，在不规则拓扑处只须采用特殊的细分规则就可以了，不存在拼 接的问题。 另方面，由于三维扫描仪( 3 ds c a n n e r ) 、测距仪( r a n g ef i n d e r ) 和c t 等三维 数据获取设备的日益完善，为几何形状不能或难于用分析曲面表示的对象建模提 供了有力的工具，例如医学的人体器官建模 l o r e n s e n1 9 8 7 1 、考古学中的古代器 件和艺术领域的雕塑作品三维重构 l e v o y2 0 0 0 1 等等。离散曲面逐渐成为一种重 要的几何表示方法。细分模式作为从给定规则产生离散曲面的方法统一了传统的 参数曲面与多边形两种实体表面的表示。另外，由于实验获取的三维数据量一般 都非常大，多分辨率分析( 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 t t r a n s f o r m a t i o n ) 之间的深刻 联系也是目前细分模式受到关注的个重要原因。 1 9 9 9 年，t o n yd e r o s e 因为把细分方法创造性地应用于解决图形学中的实际 问题中，被授予a c ms i g g r a p h 的成就奖。这标志着细分方法作为c a g d 和 计算机图形学的重要造型方法之一，得到了图形学界的一致公认。 1 3 2 细分曲面造型技术的发展阶段 细分方法可以追溯到5 0 年代g r h a m 的通过对折线角点进行切害1 ( c o m e rc u t ) 来生成光滑曲线的思想。7 0 年代中期，c h a i k i n 生成曲线的细分方法 c h a i k i n ，1 9 7 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 细分模式 c a t m u l l1 9 7 8 1 ，标志着细分方法正式成为曲面建模的手段 当矩形网格没有奇异顶点f 共享顶点的边数，称为顶点的价。对于四边形网格， 价不等于4 的顶点称为奇异顶点) 时，c a t m u l l c l a r k 模式生成三次b 样条曲面： 对于有奇异顶点的网格，生成的曲面除有限个点外，具有二阶光滑，可以说是一 张“几乎处处”的三次b 样条曲面与此同时，d o o 和s a b i n 采用离散f o u r i e r 变换的方法，对c a t m u l l c l a r k 模式的收敛性进行了分析，开创了细分模式收敛 性矩阵特征分析的先河。大致可以把细分方法的发展历史分成如下三个阶段： 7 0 年代后期c a t m u l l c l a r k 细分模式以及d o o s a b i n 关于奇异点处行为的分 析理论标志着细分方法正式成为曲线曲面造型的一种手段。 8 0 年代未到9 0 年代初的形成期。在这一阶段，提出了很多著名的细分方法， 对旧方法也有许多改进以适应不同要求。规则情形的收敛性和连续分析理论也逐 渐完善，例如给出了单变元细分模式任意阶光滑的充要条件 m i c c h e l l i1 9 9 3 。不 过，各种模式之间仍然缺乏联系，一般情形的收敛性分析方法也是“随身定作”， 缺乏一般的理论指导。 浙江大学硕士学位论文 9 0 年代中期到现在的发展期。这一时期开始建立系统的收敛性理论，提出了 多变元模式任意拓扑情形下收敛性分析的理论框架 w a r r e n1 9 9 5 r e i f1 9 9 5 ， z o r i n1 9 9 8 】。这些理论反过来指导细分模式的构造，尤其是二阶以上连续曲面的 构造。此外，各种细分模式的内在联系也逐渐被揭示出来。更为重要的是，在这 一时期，细分方法得到了广泛应用，尤其是复杂网格曲面的多分辨率分析的研究 取得了大量成果。 1 9 9 8 年的s i g g r a p h 国际图形学年会中有八篇有关曲面造型的论文发表， 除了有一篇是介绍几何体的变形方法以外，其余七篇均是关于曲面离散造型的算 法或者在离散型曲面上精确求值及适当参数化的工作。特别是，有三篇论文 f d e r o s e1 9 9 8 ，s t a r e1 9 9 8 ，s e d e r b e r g1 9 9 8 都与c a t m u l l 和c l a r k 在1 9 7 8 年所创 立的用网格细分产生离散曲面的方法紧密相关 c a t m u l l1 9 7 4 ，c a t m u l l1 9 7 8 1 。同 时2 0 0 0 年c a g d 出了个细分专辑，都是讨论细分的研究。从这里我们可以看出 当今国际图形界在曲面造型理论研究和实际应用中的热点所在，细分的方法逐渐 成为主流的方法。 1 4c b 样条理论的提出和主要特点 c 。b 样条理论 z h a n g1 9 9 6 ，z h a n g1 9 9 7 ，z h a n g1 9 9 9 作为种新颖的曲线曲面 造型方法于1 9 9 6 年由张纪文老师提出，它包含在c 曲线曲面理论之中。c b 样 条理论提出的首要目的是为了方便、简洁、精确地构造工程曲线曲面。 我们知道，目前越来越多的机械零件以曲面造型的形式进行设计，并在数控 机床上进行加工。这些曲面按其形成方式可分为：平移曲面、直纹面、旋转面和 扫掠面等。其中旋转面是工程曲面中最常见的曲面之一，但由于b 6 z i e r 和b 样 条方法不能精确表示圆，所以这两种造型方法都不能用于描述旋转面。而对于其 它几种工程曲面，曲面上截面曲线或边界线往往包含有圆弧、椭圆弧、抛物线弧 等二次曲线弧，这些形状在设计上都由图纸明确无误的给出，在制造上又要求有 较高的精度，因为b 6 z i e r 和b 样条方法由于不能精确地表示除抛物线以外的二 次曲线，从而不能精确地表示这些曲面。若采用近似的方法不但带来处理上的麻 烦，使本来简单的问题复杂化，还带来原来不存在的设计误差。若对这些二次曲 线单独地用另外一套数学描述方法，如用隐式方程表示，这样不仅重新带来隐式 方程表示所存在的问题，而且将导致几何模型中并存的两种不同数学方式，使得 系统变得庞大的问题。 显然n u r b s 方法能表达二次曲线弧，因而能够满足精确表达工程曲面的要 求。n u r b s 提出的目的也就是为了能够用统一的形式描述自由曲线曲面和二次 曲线曲面。但是我们必须看到n u r b s 并不是b 6 z i e r 和b 样条方法简单推广，在 浙江大学硕士学位论文 n u r b s 方法造型过程中会遇到非有理方法中未出现的一系列新问题，计算变得 复杂，特别是权因子、参数化、曲面连续性等问题，至今没有完全解决。权因子 的存在，为表达曲面提供了灵活性，同是也对设计人员和用户提出了更高的要求， 并增加了存储空间。尤其在精确描述形状相对简单的，但含有部分二次曲线弧的 工程曲面情况时，n u r b s 的统一表达自由曲线曲面和二次曲线曲面的优势未能 得到充分的发挥 旋法中1 9 9 4 。 c 曲线曲面理论基本原理是用基 s i n t c o s tt i i 代替三次多项式曲线方程 中的幂基 t 3 ft 1 ，相应于传统的弗格森( f e r g u s o n ) 、b 6 z i e r 、b 样条造型方 法，c 曲线曲面理论包括为c 弗格森、c b 6 z i e r 、c b 样条理论。其中c b 样条 理论一方面具有b 样条方法描述自由曲线曲面的许多优点，另一方面能够精确地 描述二次曲线曲面，非常适合于构造工程曲面。 通过对c b 样条方法的理论分析和工程应用可知，c b 样条方法进行工程曲 线曲面造型时具有下述特点： 1 1 能够以统一的形式表示自由曲线曲面和二次曲线曲面； 2 ) 控制参数的引入，增加了这一方法表达曲线曲面的能力，调整d ，对 曲线和曲面的形状有调节作用，而且a 的值容易选择： 3 ) 定义曲线曲面时所需的存储空间较n u r b s 方法少，如对一段圆心角小 于n 2 的圆弧，用n u r b s 方法以有理二次b 样条曲线定义时，需2 1 个数据， 而用c b 样条定义时，只需1 6 个数据； 4 ) b 样条方法包含在c b 样条理论内，使原先用三次b 样条方法建模的曲 线曲面能够比较方便地转换为用c b 样条表示； 5 ) 表示曲线曲面的算法较n u r b s 简单，计算速度快。 1 5 本文选题背景和主要内容 1 5 1选题依据 细分方法在国际上成为图形学的研究热点，特别是c a t m u l l c l a r k 由于是 基于四边域的，因此数据的存储比较方便，因此在这种方法最为流行。然而近年 柬工程上的曲面造型却仍然停留在n u r b s 曲面上，改进不大。c a t m u l 卜c l a r k 细 分曲面的算法虽然在计算机图形显示中非常成功，但是用于工程曲面的造型还很 少有文章提到。其主要原因是工程对曲面造型的要求，和计算机图形显示对曲面 造型的要求并不完全相同：多媒体动态显示要求的是外形优美、真实感强和快速 的实时动态处理；而工程上的曲面造型则更强调的是功能和便于制造，要求精度 高和能统一精确地处理工程上最常见的圆和圆柱等。 c a t m u l l 算法是在三次均匀b 样条的基础上发展起来的。以均匀b 一样条为背 浙江大学硕士学位论文 景的c a t m u l 卜c l a r k 细分曲面无法精确表示圆柱等常规工程曲面。工程上用它， 又会碰到采用n u r b s 曲线以前的表示圆的老问题。虽然9 8 年浙江大学郑建明等 人已将c a t m u l l 算法推广到了非均匀的情况 s e d e r b e r g1 9 9 8 ，理论上进了一大步， 但是距离显示的实用都还很远。若想再进一步采用有理的方法( 即推广到n u r b s 曲面) ，来解决工程曲面的造型，则还有更多、更艰难的工作要做。此外，一般 细分过程中的网格点是不断移动的，其极限才是曲面上的点，也是细分曲面在工 程应用中的一个困难。但是我们注意c b 样条将三次曲线的基1 ，t ，r 2 ，f3 拓宽成 1 ，t ，c o st s jn t ，它也具有：局部性、连接点处二阶导数连续性、保凸性、 凸包性、对称性、控制顶点的系数和恒等于l 、几何不变性、变差缩减( v d ) 特 性、和其他两种形式( c - b e z i e r 、c - f e r g u s o n ) 的可互换性、以及可用张量积来 构造曲面等。但是，它还能够象n u r b s 一样精确地表示圆弧、圆柱等，统一工程 上曲线、曲面的表示。它的细分计算简单，形状调整方便，参数口有明显的几 何意义。相对于有理方法，c 一曲线特别是其中的c b 样条更容易同时满足工程上 的精确表示，和计算机动态显示时的快速要求。可是c 曲线也遇到了象n u r b s 曲 线一样问题：目前它还无法解决任意拓扑结构的造型。 然而幸运的是：由于c 曲线是三次曲线的推广，当参数o f - ) 0 时，c b 样条 就是均匀三次b 样条 z h a n g1 9 9 6 。两者的定义和细分公式，在结构和格式上相 同，计算也差不多样简单 z h a n g1 9 9 6 。所以直接用c 一8 样条来取代c a t m u l l 算法中的均匀三次b 样条，很容易生成以c - b 样条为背景的c a t m u l 】细分曲面。 均匀三次b 样条是c a t m u 1 细分曲面的基础。正是这个基础，保证了c a t m u l l 细 分曲面的连续、光滑和具有三次均匀b 样条曲面的属性。把它换成c b 样条以后， 显然，新的c a t m u l l 细分曲面不但能够象c - b 样条曲面样，精确地表示圆柱等 常规曲面，统一工程曲面的造型。同时它仍然保持细分曲面的造型特点：解决 n u r b s 曲面难以解决任意拓扑结构的造型问题。并且造型过程是直接从离散点到 离散点，中间实际上不再生成连续曲面。相对于开发n u r b s 的c a t m u l l - - c 1 a r k 细分曲面，这无疑是曲面造型中一条值得探索的捷径。 因此，本文主要想通过深入研究和完善c b 样条的技术，建立基于c b 样条 c a t m u l i 算法来寻找工程曲面造型的新方法。 1 5 2 内容组织 本文具体章节安排如下： 第1 章主要介绍本文工作的背景、选题目的以及本文的主要内容 第2 章是数学基础，对曲面造型的主流方法b 样条曲线、曲面的定义、常用 技术和相关算法作了介绍，详细描述了细分方法的基本原理、研究状况，讨沦细 浙江大学硕士学位论文 分方法中的理论和应用技术问题。为了便于后续各章的叙述，对细分方法的基本 原理如曲线细分方法等进行阐述。 第3 章对曲面细分的特点、常用技术和相关算法作了介绍和分析，较全面地 描述细分方法的基本原理、基本算法。并将这些算法推广到任意拓扑结构，得到 一些基本的细分模式。同时着重讨论c a t m u l l c l a r k 细分模式、d o s a b i n 细分模 式、l o o p 细分模式等的基本算法及其实现，以及对他们进行比较。说明了选择 c a t m u l l c l a r k 细分模式的原因。本章为第5 章中c b 样条曲线在c a t m u l l c l a r k 细分曲面中的应用奠定了基础。 第4 章在分析c 曲线的基础上，主要研究了c b 样条曲线的特性，以及控 制参数和控制顶点的修改对c b 样条曲线曲面形状的调节作用，实现了c b 样 条表示各种角度的圆弧和椭圆弧的几何构造方法，并对三种c b 样条曲线表达式 间的关系进行了讨论与分析。在曲线的基础上，将c b 样条曲线的性质推广到 曲面上。研究了c b 样条曲面的性质以及控制参数和控制顶点对曲面形状的调节 作用。最后分析和构造了平移曲面、旋转曲面、椭球曲面等常见工程曲面。 第5 章在前面几章分析的基础上，主要研究了c b 样条曲线的细分分割算 法的特性，以及控制参数口的几何意义以及它的修改对c b 样条细分曲线形状 的调节作用。同时提出了任意拓扑结构中奇异点处的算法，实现了基于c b 样 条的c a t m u l l c l a r k 细分曲面的算法，并用此方法生成常见工程曲面。最后为了 进一步的研究和试验，用v i s u a lc + + 和0 p e n g l 开发了专用的软件包，本文对这个 软包做了简要介绍，并生成较为的复杂形体。 第6 章是总结和展望。提出以后需要完成的工作。 浙江大学硕士学位论文 第2 章算法基础 【内容提要】本章对曲面造型的主流方法b 样条曲线、曲面的定义、常用技术和相关 算法作了介绍，较全面地描述细分方法的基本原理、研究状况，讨论细分方法中的理 论和应用技术问题为了便于后续各章的叙述，对细分方法的基本原理如曲线细分方法 等进行阐述，为后续章节c b 样条曲线曲面理论的研究以及它们在c a t m u l l c l a r k 细分 曲面中的的应用奠定数学基础。 2 1 引言 曲面造型是计算机辅助几何设计( c o m p u t e ra i d e dg e o m e t r i cd e s i g n ，简称 c a g d ) 中的重要分支，同时又是c a d c a m 系统最关键部分之一它随着 c a d c a m 技术应用的深入而不断发展和目趋完善。 人们在b 6 z i e r 的基础上提出了b 样条方法。b 样条方法是在保留b e z i e r 方 法的优点，同时克服其在整体表示带来不具有局部性质的缺点，及解决在描述复 杂时带来的连接问题下提出来的、但是均匀b 样条方法最大的缺点是不能表示工 程上常用的园、椭圆等规则形状，n u r b s 方法的提出的首要理由就是为了找到 与描述自由型曲线曲面的b 样条方法相统一的又能精确表示园弧等的数学方法。 曲面生成是计算机图形学和计算机辅助几何设计研究中的一个重要课题。尽 管目前n u r b s 己成为工业标准，但n u r b s 不能处理任意拓扑的形状，因此具 有局限性，而细分曲面恰恰克服了此弱点，这就是细分曲面的逐渐成为研究热点 的主要原因，但是细分的思想已产生很长一段时间了，它的基本思想也比较简单。 本章简要介绍与分析b 样条曲线曲面的定义、常见技术和相关算法，简述了 细分曲线曲面的数学方法和主要特点，并且分析了蓝线细分加细的过程，为后续 章节的数学推导、性质比较奠定基础，有关b 样条、细分曲线曲面理论分析和 算法研究的具体内容可参阅文献孙家广1 9 9 5 、朱心雄2 0 0 0 、王国谨2 0 0 1 、施 法中1 9 9 4 。 2 2 b 样条曲线曲面造型基础 孙家广1 9 9 5 以b e r n s t e i n 基函数构造的b e z i e r 曲线或曲面有许多优越性，但有两点不足 其一是b e z i e r 曲线或曲面不能作局部修改；其二是b e z i e r 曲线或曲面的拼接比 较复杂。1 9 7 2 年，g o r d o n 、r i e s e n f e l d 等人提出了b 样条方法，在保留b e z i e r 方法全部优点的同时，克服了b e z i e r 方法的弱点 施法中1 9 9 4 。 浙江大学硕士学位论文 2 2 1 b 样条曲线的定义和性质： 1 b 样条曲线的定义 b 样条曲线由分段逼近曲线组成，也是n u r b s 曲线的基础。它具有b e z i e r 曲线的优点，又克服了其不具备局部性质的缺点。k 次b 样条曲线的数学方程为 p ( f ) = 只计( f ) f ；0 其中数据点只称为控制( 或特征) 顶点，顺序连接顶点的折线称为控制( 或特 征) 多边形。曲线有n k + 1 段。( f ) 称为b 样条基函数( 简称b 样条) ，由参 数t 的非递减序列形成的节点矢量丁= i t 。t n - k + 1 确定。 b 样条有多种等价定义，在理论上较多地采用截尾幂函数的差商定义。我们 只介绍作为标准算法的d eb o o r c o x 递推定义，又称为d eb o o r c o x 公式。约定 0 0 = 0 州归亿 t f x o ，每个群可写成： 1 p f = 。p k 。 ( 2 7 ) i = 0 即对于任何可写成由上一步生成的控制多边形的控制顶点 彤，只“1 ，p ： 的线性组合。对于每个固定的j 和k ，口。t 通常被称为m a s k 但是这种普通的方法很复杂，很难进行分析，它包括两种情况：一是每一次细分 后形成的控制多边形的控制顶点增加，例如c h a i k i n 曲线 c h a i k i n ，1 9 7 4 】和 d o o s a b i n 细分曲面：另一种是控制顶点减少，例如用d ec a s t e l i j a u 算法生成 b e z i e r 朱一心雄2 0 0 0 1 曲线就属于这种情况。 我们也可以用矩阵形式表示细分原理： 等式： 彤2 口w 此等式等价于 ( 28 ) 卜 只 ， 口 1 1 斗， 成写以可 浙江大学硕士学位论文 = s k 其中s 。是为( 心+ 1 ) x ( n + 1 ) 矩阵 s 。 口o 且k 口0 l 女 口i 且k 口1 1 i 女 c l ”i i 口k 口h 小l ，l 口o ，”女，女口i ，“i 女 。 口“t i ，h i 举个例子，假设给定控制多边形 只，只，p 1 ) 其细分方法如下 呓= ；夥+ ；嘭， 呓，；钟+ ；吆， ( j 2 0 ，1 ，2 , 3 ) p p 鲁tp ；。 砹； 倒2 2 捌盱阳觋r 千衣习i 图 以此我们得到新的控制多边形： 列= ；只+ ；鼻 肛；局+ ；只 爿= ；e + ；只 爿= 扣+ ；只 这种细分方法就是c h a i k i n 曲线生成方法，每一次细分后，控制顶点的数目 都增加，同时越来越逼近同一条曲线。 2 3 2 二次b 样条曲线细分 曲线生成方法是计算机图形学和几何造型的重要内容。在b e z i e r 曲线和 浙江大学硕士学位论文 b s p l i n e 曲线中，我们通过控制多边形利用基函数，用解析的方法生成曲线上的 点。而在曲线细分过程中，我们同样利用控制多边形逐步细分，形成新的控制多 边形；随着细分的次数的增加，新形成的控制多边形就越来越逼近一条曲线，即 细分曲线。 假设给定控制对边形溉，鼻，p 2 定义一二次b 样条曲线p ( t ) ，此控s t i r , 边形 只有三个控制顶点，如图所示： p 2 图2 3 均匀二次b 样条曲线图2 4 一次细分后的均匀二次b 样条曲线 利用矩阵r 等到如下的细分公式： 爿 只】