（精密仪器及机械专业论文）基于切片数据的三维B样条曲面重构(精密仪器及机械专业优秀论文).pdf

摘要 摘要 逆向工程技术是一门随着计算机技术的发展以及数据测量技术的进步而迅 速发展起来的新兴学科与技术，在计算机辅助制造、生物医学工程、虚拟现实、 非破坏性监测等诸多方面得到越来越广泛的应用。逆向工程是一种从实物到数 据、再从数据到模型的过程。其中从数据到模型的这一过程即曲线曲面重构问题， 是逆向工程中的一个难题，却又是最重要的问题。本文的核心研究问题是如何从 给定的一系列切片重构出模型，并使重构得到的模型能由统一的数学模型表达。 本文首先回顾了逆向工程和三维曲线曲面的重构，接着介绍了文中应用的重 构的理论基础- b 样条曲线曲面的知识。然后根据重构时切片上的轮廓的特点将 重构问题分为两类：单轮廓的曲面重构和多轮廓曲面重构。其中，单轮廓的曲面 重构又是多轮廓曲面重构的基础。 单轮廓的曲面重构时，由于各层切片上均只有一条封闭轮廓线，因此不存在 对应、分支及多重封闭轮廓线等问题，重构较为简单。这时主要考虑算法的效率 及重构曲面的精度。利用b 样条方法重构时，型值点的选取是影响算法效率及 重构曲面精度的主要因素。若轮廓线较为光滑时，采用极坐标方式取点的方法， 能够避免前期的轮廓提取及后期的型值点的相容性处理，使得算法效率大大提 高，但并不适用于复杂轮廓。高曲率点含有描述边界形状特征的重要信息，可将 这些点作为特征点来代表整个轮廓。因此，首先确定特征点，根据特征点确定采 样密度，利用非均匀b 样条进行重构；或是在特征点处对轮廓进行分割，分别重 构得曲面片后组合得最终曲面。 多轮廓的曲面重构时，主要考虑以下三个问题：1 、对应问题，2 、含多重封 闭轮廓的重构问题，3 、分支问题。根据曲面的连续性，属于同一分支的轮廓线 群，其几何中心应该位于一条光滑的曲线上，因此用质心位置解决对应问题；对 于含多重封闭轮廓线的重构问题，利用改进的图像分割及填充技术将多重封闭轮 廓线分离、排序，将该问题转化为对应或分支问题；解决分支问题时，假设相邻 两层切片，第f 、f + l 层，其中第f 层有彪个封闭子轮廓，第+ l 层有一个封闭轮 廓( 多对多的情况可以转化为一对多的情况，因此这里只介绍一对多的情况) 。根 据第f 层各封闭轮廓的质心在第f + 1 层上的投影点与第f + l 层质心的相对位置对 第i + 1 层上的轮廓进行划分，划分后用b 样条曲线将轮廓段拟合为多个封闭轮 廓，计算各封闭轮廓的质心，通过与相邻层质心的匹配调整质心位置和封闭轮廓， 将分支问题转化为对应问题，再利用质心位置的连续性确定属于同一分支的轮廓 摘要 线群。 关键词：特征点计算对应问题分支问题切片数据多重封闭轮廓b 样条曲面 重构 a b s t r a c t 一 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c e sa 1 1 dt t l ea v a j l a b i l i t yo fm e a s u r i n g t e c h n i q u e s ，r e v e r s ee n g i n e e r i n gh a sb e c o m ear a p i d i yd e v e l o p i n gt e c h i l o l o g y nl l 嬲 b e e nw i d e l yu s e di nc o n l p u t e ra i d e dd e s i 朗a i l dm a l l u f a c t u r e ，b i o l o g ) ra i l dm e d i c a l e n g i n e e r i n g ，v i r t u a lr e a l i 吼n o n d e s t m c t i v ed e t e c t i n g ，e t c t h e r ei n t o ，r e c o n 髓m c t i o n o f 贴o m e t r i cm o d e lf i o ms l i c ed a t ai sam a j o r d i 伍c u l tt a s k ，b u ti ti sa l s ot h ei m p o r t a n t p r o b l e m ni st h eb a s eo fa 1 1 a l y s i s ，c a l c u l a t i o na i l d v i s u a l i z a t i o no ft l l eg e o m e t r i c m o d e l s t h ec e n t e ri s s u eo ft h i sm e s i si sm er e c o n s t m c t i o n 丘o ma s e r i o u so fs l i c ed a t 毛 a tt h es a m et i m e ，t h er e c o n s t m c t e ds l l r f a c ec a ne x p r e s sb yau i l i f o n l lm a ：t l l e m a t i c s e x p r e s s i o n i nt h i sp 印e r w eb e g i nw i t l la 1 1i n 仰d u c t i o nt or e v e r s ee n g i n e e r i n ga 1 1 d3 d c u r v e s s u r f a c e sr e c o n s 仃u c t i o nt e c h n i q u e t h e l l ，w ei m r o d l l c e dn l et e c q u e o f b s p l i n ec 眦、，e s u r f a c e b a u s eo nt h ec h a r a c t e r i s t i co ft l l ec o 咖o f l es l i c e ，w e d i v i d et h er e c o i l s t m c t i o ni n t ot 、os t e p s ：s i n g l e c o i l i l e c t i v 时s u r f a c er e c o n s t m c t i o n a 1 1 dm u l t i c o 姗e c t i v i t ys u r f 犯er e c o n s t m c t i o n t h e r ei n t o ，s i n g l e - c o n n e c t i v i t ys u r f a c e r e c o n s t m c t i o ni st l l eb a s i so ft h em u l t i c o i l n e c t i v i 够s u r f k er e c o n s t n j c t i o n s i n g l e 。c o i m e c t i v 时s u m l c er e c o n s t m c t i o n ：n l e r eh a so i l l yo n e c l o s e dc o n t o u r0 n e a c hs l i c e s o ，w en e e dn o tt a k ec o m o u rc o n e s p o n d e n c ep r o b l e m ，b 啪c hp r o b l e m a n d m u l t i c l o s e dc o n t o u rp r o b l e mi n t oa c c o u n t t h ep r o c e s so fr e c o n s n l l c t i o ni se a s y t h e e m c i e n c yo ft 1 1 ea l g o r i t 量l i i l i ca 1 1 dt h ep r e c i s i o no ft l l er e c o n s t m c t e ds u r f 犯ea r e 龇 i m p o r t a n tp r o b l e m w h i l et l l es u r f a c er e c o n s t m c t e du s i n gb - s p l i n et e c l l r l o l o g y ，t l l e s e l e c to fp o i n t sd a t ai st h em o s t l yf a c e tw h i c hi n f e c tt h ee 伍c i e n c yo ft h ea l g o r i t l m l i c a i l dt h ep r e c i s i o no fm er e c o n s 勃n j c t e ds u r f a c e w h e nm ec o n t o u ri ss m o o t h ，w eu s e t h ec e m r o i do fe a c hs l i c et og e tas e r i e so fr e g u l a rp o i n t s t m sm e m o da v o i dm e p r o c e s so fg e n e r a t et h ec o n t o u ri ne a c hs l i c ea i l do v e r c o m et h e1 0 c a t i o np r o b l e ma i l d c o n s i s t e n c yo fp o i n t si ns u r f a c er e c o n s t m c t i o n b u ti t d o e s n ta p p l ym ec o m p l e x c o n t o u r 7 n l ec u r v a t u r ec a i ld e s c r i b et h es h a p eo ft h ec o n t o u r ，t h e s ep o 缸sc a nb et l l e c h a r a c t e r i s t i c p o i n t s t or e p r e s e n tw h o l ec o n t o w s o ，f i r s t l y ，w ec o h l p u t em e c h a r a c t e r i s t i cp o i n t s ，a n dm e nu s ed i f f e r e n td e n s i t yb a s e st h ed i s t r i b u t i n go ft h e s e p o i n t so rd i v i s i o nt h ec o n t o u ra c c o r d i n g t ot h e s ep o i n t s m u l t i ，c o i l i l e c t i v i t ) ，s u r f a c er e c o n s t r u c t i o n ：t h e r ea r em r e ep r o b l e m sw es h o u l d s o l v e c o n t o u rc o 玎e s p o n d e n c e ，b r a n c hp r o b l e ma n dm u l t i c l o s ec o n t o u rp r o b l e m s o i i i a b s t r a c t t h er e c o n s t m c t i o ni sm o r ed i 衔c u l t b a s e do nt h ec o n t i n u i t yo ft h es u r f i a c e ，t h e c e n t r o i do fm ec o n t o u r sb e l o n gt ot h es 锄eb r a n c hm u s tl o c a t eas m o o mc u e s ow e s o l v et h ec o n t o u rc o r r e s p o n d e n c ep r o b l e mu s i n gt h ep o s i t i o no ft h ec e n t r o i do fe a c h c o n t o u r t bt h em u l t i c l o s ec o n t o u rp r o b l e m ，w eu s ei m p r o v e di m a g ed i v i s i o na i l d 6 l l i n gt e c l l n o l o g yt 0s 印a r a t ea i l dc o m p o s i t o rt h ec o n t o u r s t h e n ，m em u l t i c l o s e c o n t o u rp r o b l e m 仃a n s l a t e di n t oc o n t o u rc o r r e s p o n d e n c eo rb r a l l c hp r o b l e m d o d i v i s i o no ft h ec o n t o u ra tm ec h a r a c t e r i s t i cp o i n t sa i l dt h e nf i t t i n gm ec o n t o u ru s i n g b s p l i n ec u e ，w et 啪s l a t et h eb r a i l c hp r o b l e mi n t oc o n t o u rc o 订e s p o n d e n c ep r o b l e m t h e na c c o r d i n gt h ec o n t i n u i t ) ro ft h ep o s i t i o no ft h ec e n t r o i d ，w ec a l ls e p a r a t et h e c n n t n l 】r s k e yw o r d s ：c l l a r a c t e r i s t i cp o i n t s ，c o n l o l l rc o r r e s p o n d e n c e ，b r a n c hp r o b l e m ，s l i c ed a t a m u l t i c l o s ec o n t o u rp r o b l e m ，b s p l i n er e c o n s t m c t i o n 工v 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 安徽合肥 2 0 0 8 年5 作者签名：塑：堕盔 潮年5 月f 2 日 中国科学技术人学硕十论文 第一章绪论 1 1 逆向工程简介 第一章绪论 进入二十一世纪，科技的发展使得人们步入了一个信息时代。随着近二十年 信息技术高速发展，我们的生产和生活已经发生了巨大的变化。信息时代的一个 重要特征是数字化，数字化是多媒体和信息高速公路的必要前提，而后两者显然 是步入信息时代的两个最重要技术桥梁。数字化的发展伴随产生了一个生机蓬勃 的技术逆向工程技术。逆向工程是针对于传统工程中的c a d c a m 技术而 言的。传统的c a d c a m 的工作流程为：( 1 ) 概念设计，( 2 ) c a d 建模，( 3 ) 数控编 程，( 4 ) 数控加工。图1 1 是传统的c a d c a m 的工作流程简图。 团一区固岛国日固 图1 1c a d c a m 工作流程 然而数字化技术使制造业进入了新一轮更加残酷的竞争设计的竞争。数 字测量技术的飞速发展，产生了一种新的从产品到数据再到产品设计方式逆 向工程( r e s e ee n g i n e 嘶n g ) 。逆向工程是根据实物测量的数据重新构造实物的计 算机模型，然后利用c a d c a m ，c a e 等计算机辅助技术进行分析、再设计、数 控编程等操作，而后进行加工。图2 1 是逆向工程的工作原理。这样的设计流程 大大地缩减了产品设计时间，提高了产品的竞争力。 闻 【d 图l - 2 逆向工程工作原理 这个流程的分类只是逻辑分类而已，事实上，不同步骤之间往往是重叠和相 互影响制约的。例如数据采集和处理与模型重构之间，不同的重构方法对数据采 集和处理的要求不同，数据采集和处理技术往往伴随产生相应的重构方法。断层 扫描数据则需要分割技术和拓扑结构建立技术。 口司口固舀 中国科学技术人学硕+ 论文 第一章绪论 且速度慢、准确率低。从断层图像重构三维模型便于用户从任意角度、任意层次 进行观察和分析，并且可以获得任意平面的虚拟切片，最大限度地再利用了图像 信息；应用在逆向工程中，对于仿制先进设备和关键零件有重要意义；在计算机 虚拟领域，用计算机进行模拟试验，特别是耗资巨大或是危险性极大的试验，需 要建立精确的试验模型，模型越是精确试验结果越是接近实际情况，可靠性越高。 重构 二二 图1 3 切片重构示意 在过去三十年内，研究者提出了很多有重要意义的从断层图像重构三维模型 的方法，这些方法大多可以分为两类：基于切片的重构和基于三维数据点的重构。 基于三维数据点的重构的方法很多，例如径向基函数法【1 ，2 1 、多层次单位分解【3 】、 隐式代数样条拟和【4 】以及点集曲面【5 j 等。随着三维扫描技术的发展，基于三维数 据点的重构也将得到更大的发展。基于切片的三维重构目前有着深厚的应用背 景，得到了极大的重视，吸引了众多学者的关注。一般的基于切片三维重构方可 以归结为两类：表面重构和体重构。 表面重构是指在每一个切片上重构出等值线，然后将这些等值线缝合为一张 三维曲面。其中比较关键的技术是等值线缝合，这类方法一般面临四个难题： 1 ) 对应问题( c o n e s p o n d e n c ep r o b l e m ) ：如果切片上的轮廓线不止一条，相邻切 片中哪些轮廓线应该相连接。事实上，即使每张切片上只有一条轮廓线，相邻两 切片中的轮廓线未必连接成同一物体。对应关系决定了最终生成的曲面的拓扑结 构。 2 ) 分支问题( b r a n c hp r o b l e m ) ：当切片上的一条轮廓线与相邻切片的多条轮廓线 对应时，分支问题必存在。分支问题即如何生成这些轮廓线之间的多个分支表面。 通常采用两类方法：1 、插入中间层；2 、分割或合并轮廓线，使得相邻层轮廓数 相等，即将分支问题转化为对应问题。 3 ) 多重封闭轮廓的重构问题( m u l t i c l o s ec o n t o u rp r o b l e m ) ：通过计算机方法得到 的切片轮廓线数据通常具有数据量大、轮廓线多等特点，其中复杂的轮廓线一般 具有多重封闭的轮廓线，因此要对这些轮廓线进行分离和排序。 4 ) 曲面拟合( s u r f a c ec o n s t m c t i o n ) ：参数曲面根据参数定义域的不同分为矩形参 3 中国科学技术大学硕士论文第一章绪论 1 3 本文的基本思想和主要结果 本文各章的内容具体安排如下： 第一章为绪论，简要介绍逆向工程及曲面重构的技术，阐述研究目的及基本 思想，以及当前曲面重构的各种方法，最后展现论文的概貌。 第二章介绍b 样条曲面重构的理论基础，对n u r b s 曲线曲面的性质进行了 详细的讨论及比较，最终确定本文选择b 样条曲面进行重构。介绍三次b 样条 曲线曲面的反算方法。 第三章介绍单轮廓曲面重构的方法，研究了由单轮廓线进行曲面重构的基本 算法和程序实现。主要介绍两种重构方法，第一种适用于简单轮廓，第二种适用 于绝大部分轮廓。 第四章介绍多轮廓曲面重构的方法，主要介绍对应、分支和多连通问题的解 决。基于第三章介绍的单曲面重构方法，解决对应、含多重封闭轮廓的曲面重构 问题，讨论分支问题的多种情况并实现部分。 第五章对全文做了总结，并对以后的工作提出展望。 5 中国科学技术人学硕士论文 第一章绪论 ( 16 j m j o n e sa n dc h e n an e w 印p r o a c ht ot h ec o n s t r u c t o no fs u f f i a c e sf b mc o n t o u rd a t a c o m p u t e rg r a p h i c sf o r u m ，13 ( 3 ) ：7 5 8 4 ，19 9 4 【l7 】w e l o r e n s e na n dh e c h i n e m a r c h i n gc u b e s ：ah i 曲r e s o l u t i o n3 ds u r ec o n s t r u c t i o n a i g o r i t h m i nm c s t o n e ，e d i t o r c o m p u t e rg r a p h i c s ( s i g g r a p h 8 7p r o c d i n g s ) ，v o l u m e2 l ， p a g e s1 6 3 一1 7 0 ，j u i y1 9 8 7 i8 】gc o n ga n db p a r v i n s u 哺k er e c o v e 哆行o mp i a n a rs e c t i o n a lc o n t o u r s i c p r o o ，p a g e s 4 1 0 6 - 4 1 0 9 。2 0 0 0 7 中国科学技术人学硕十论文第二章b 样条曲线曲面 由上式可知，七次b 样条基是一个只在斛1 个子区间【“，“m + ) 非零的分段七 次多项式，它具有舡1 次连续导数。 b 样条曲线具有如下主要性质： a ) 局部性 曲线c ( 甜) 在参数区间 “，甜，+ 】( 七f 刀) 上的部分至多与斛l 控制顶点 d ，( 歹= f 一后，f 一七+ l ，力有关，与其他顶点无关。反过来，修改该曲线上第i 个 控制顶点z 只影响啦线c ) 在区间 吩，“m 】中的那部分曲线的形状，对曲线的其 余部分不发生影响。 d ；4 蠢，一i 坼一l甜， + l吩+ 2 图2 一l 定义在 材，材硝】上那一段虫次b 样条曲线( 煳) d ，+ l 下面给出确定b 样条曲线的定义域的方法。给定时1 个控制顶点 d ，( f = 0 ，l ，刀) ，相应要求时1 个b 样条基函数n 竹 ) ( f - o ，1 ，刀) ，以定义一 条七次b 样条曲线。这，什1 个七次b 样条由节点矢量u ：“o + 所决 定。然而，并非这节点矢量所包含的刀+ 肛1 个区间都在该曲线的定义域内，其 中两端后个节点区间不能作为b 样条曲线的定义区间。因此可以将七次b 样条 曲线方程式改写为分段表示 n， c ( “) = 嘭m 乒( 甜) = d ，。( “) ， 材陋，甜，+ 】c ，“川】( 2 3 ) j = nj = i k b ) 凸包性 曲线c ( 甜) 在区间 “，”川 ( 3 f 聆) 上的部分位于j j 个控制项点4 书或中 z 小z 的凸包内。 c ) 直线再生性 由凸包性质可知，若后个控制顶点d h ，d h ，d 川，j ，落在一条直线上，则区间 9 中国科学技术大学硕士论文第二章b 样条曲线曲面 h ，“，+ i 】内的曲线为直线。 由上可知，调节控制顶点可以控制曲线的形状，同时，b 样条曲线还可以通 过调节节点矢量加以控制。一旦控制顶点和节点矢量确定，三次b 样条就能唯 一确定。 2 1 2曲面 给定空间+ 1 ) g + 1 ) 个控制顶点4 ，( f = o ，1 ，m ；= o ，l ，z ) 的阵列，构成 一张控制网格。又分别给定参数“，的次数露= z = 3 ，和两个节点矢量 u = 瞳。，甜，甜。“+ ，】与矿= k ，v p ，“+ l 】。就定义了一张双三次b 样条曲面。其 方程为 尸g ，v ) = 4 ，f ，0 比， o 甜1 ，o ，1 ( 2 4 ) f = 0 = o 其中，b 样条曲面基函数，0 = o ，1 ，聊) 与m ，0 地= o ，1 ，玎) 分别由节点矢 量u 与y 按d e b o o r - c o x 递推公式决定。 2 2 b 样条的分类 b 样条曲线按节点矢量中节点的分布情况不同，可划分为如下4 种： 1 均匀b 样条曲线( u n i f o mb s p i i n ec u n ，e ) ：节点沿参数轴均匀或等距分 布； 2 准均匀b 样条曲线( q u a s i 一疵f o mb s p l i n ec u e ) ：其节点矢量中两端节 点具有重复度斛1 ，所有内节点均匀分布具有重复度l 。 3 分段b e z i e r 曲线( p i e c e w i s eb 6 z i e rc u n ，e ) ：其节点矢量中两端节点重复度 与类型2 相同，为胁l 。所不同的是，所有内节点重复度为尼。 4 一般非均匀b 样条( g e n e 脚n o n u 吐f o 肌b s p l i n e ) ：任意分布的节点矢量 u ：“。“。材m “，只要在数学上成立( 非递减，两端节点重复度小于 等于抖1 ，内节点重复度不大于七) 都可选。 一般地，b 样条曲线的次数取为3 ，即可满足工程中的要求。在本文中，我 们主要用到均匀三次b 样条及非均匀三次b 样条，下面详细介绍这两种样条。 2 2 1 均匀三次b 样条 对于节点矢量u = l 。，甜 ，彭卅+ ，】，若参数节点“，分布均匀，则称定义于该 节点矢量上的b 样条曲线为均匀b 样条曲线，相应的基函数为均匀b 样条基函 1 0 中国科学技术人学硕十论文 第二章b 样条曲线曲面 数。这里七= 3 。此时基函数具有平移性质，在定义域内各个节点区间上都具有 相同图形。这里可将定义在每个节点区间h ，甜】上用整体参数，表示的b 样条 基变换成用局部参数f 【o ，1 】表示。作参数变换 “= ( f ) = ( 1 一，) “f + 胁f + l ， r 【0 ，1 】；f = 七，后+ l ，刀 则b 样条曲线方程( 2 1 ) 可改写为矩阵形式 1r c 心) 2 言扭 141o 一3030 3630 一l331 4 一， 4 2 4 一。 d i ， 0 ，l 】；待3 ，4 ，刀( 2 5 ) 均匀三次b 样条曲线计算简单，但同时也放弃了利用参数节点控制曲线的 形状的能力。 2 2 2 非均匀三次b 样条 定义j = 3 ，对于节点矢量u = k ，“，材枞+ 。】，若参数节点“，分布不均匀， 则称定义于该u 上的b 样条曲线为非均匀b 样条曲线，相应的基函数为非均匀 b 样条基函数。由于节点分布不均匀，所以在生成曲线时，每个基函数都要单独 计算，其计算量比均匀b 样条大得多。但是对非均匀b 样条曲线来说，可以随 意插入、删除、修改节点，从而方便地控制曲线的局部形状。 2 2 2 1 节点矢量的确定 目前有许多定义参数节点矢量的方法，下面介绍两种最常用的方法。 a 、均匀参数化。均匀参数化方法如下式所示。 = o ，甜。= l ， 坼= 尼= 1 ，聊一1 ( 2 6 ) b 、积累弦长参数化。 该方法使每个节点区间长度与对应的曲线上的两点之间的弦长对应起来，避 免在相邻段弦长相差悬殊的情况下产生较大误差。通常将两端节点的重复度取为 七+ l ，这里取为4 。即“o = 甜l = 甜2 = “3 = o ，甜柑= 扰州= z f 硝= “舶= 1 ，这样使得 曲线的首末端点与控制顶点的首末端点相重合。中间节点的计算依据型值点的分 布。取 中国科学技术大学硕士论文第二章b 样条曲线曲面 规范化处理 w f = w f = 0 ，1 ，胛 取节点值 “o2 “l2 “22 甜32 甜，= 嵋一3 扛4 ，5 ， + 2 甜打+ 3 = “胛+ 4 = “一+ 5 = “厅+ 6 = 则节点矢量表示如下： u = “o = “l = “2 = “3 = 0 ，“，( f = 4 ，2 + 2 ) ，“。+ 3 = “。+ 4 = 甜。+ 5 = “。+ 6 = 1 ) ( 2 7 ) 2 2 2 2 节点的插入 插入节点算法是b 样条方法配套技术中最重要的技术之一。它即具有重要 的理论价值，又在曲线曲面设计中有着广泛的应用。通过插入节点：a 可以进一 步改善b 样条曲线的局部性质，提高对b 样条曲线形状控制的潜在灵活性：b 可以求出b 样条曲线上的点；c 可以实现对曲线的分割；d 在生成曲面时，可 以使不相同的节点矢量统一起来；等等。 1 ) 插入一个节点 设已知一条三次b 样条曲线 c ( 甜) = z ，( ) ， o 甜l ( 2 8 ) = 0 其中，b 样条基函数由节点矢量u = l 。，“柑+ 。】按d e b o o r - c o x 公式递推确定。 现在要在曲线定义域某个节点区间内插入一个节点甜【甜，甜川】c 陋，“川】，于是 得到新的节点矢量 u = k o ，“l ，“，甜+ l ，m + i 】 重新编号后成为 扩= - o ，瓯，玩，瓦+ ，玩+ ：，瓦+ n ：】 这个新的节点矢量扩决定了一组新的b 样条基函数冠，( 甜) ( f = o ，1 ，刀+ 1 ) 。原来 的b 样条曲线( 2 8 ) 就可以用这组新的b 样条基函数与未知新的控制顶点 z ( f ：o ，1 ，刀+ 1 ) 表示出 1 2 聆 乙b = o = i i 跟 一 p + 一m = 中国科学技术人学硕+ 论文第二章b 样条曲线曲面 2 ) 重复插入同一节点 把同一节点“重复插入，次，即插入重节点。而该节点在老节点矢量中又可 能具有重复度，即有“= 甜，= “- l = = “+ l ，则应使，+ j 尼。这时将有新 的节点矢量 u = 【_ o ，弦，瓦m 】= “o ，蹦i ，彩h + i ，扰i ，掣，铭川，掰枞+ l 】 、- 、，、，一 ，雨1 个 决定一组新b 样条基z ，。( “) ( ，= o ，1 ，刀+ z ) 。将原b 样条曲线( 2 8 ) 用这组新基函 数与未知新的控制顶点嘭( 歹= o ，l ，行+ ，) 表示 c ( 甜) = d m ，t ( 甜) ( 2 1 1 ) = o 插入算法由插入单个节点的算法推广而来。将由七一，一1 个老的控制顶点 d ，( = f 一七+ l ，f 一七+ 2 ，f 一厂一1 ) 被七一，一l + ，个新的控制顶点d l ，d 乙， d 二，以川所取代，其余老顶点不变。 这些新的控制顶点可由七一，+ 1 个顶点d ，( ，= f 一后，f 一七+ l ，i 一，) 按如下递 推公式执行，级递推得到 其中 d j = d j s = q ( 1 一口) d j 一1 + 口d 爿， s = 1 ，2 ，( 2 1 2 ) j = i k ，i r l 2 3 光滑闭曲线的构造 “一“+ j q 2 蒜 这里我们来讨论如何使三次b 样条曲线首尾相连，构成一条光滑的闭合曲 线，如图2 。3 所示。 1 4 中国科学技术人学硕十论文 第二章b 样条曲线曲面 应可确定定义域内节点值为吮+ ，= z g = o ，1 ，撒) ，即从起的定义域内节点值依 次等于从玩起的数据点参数值。现在就可由插值条件给出以珂+ 1 个控制顶点为 未知量的聊+ 1 个线性方程组成的线性方程组 一， p 0 ，) = d ，j 0 ，) = d 肚0 ，) = g h j = qj z l k “k ，群“一】ck t ，掰。+ t l f = 七，七+ 1 ，刀 ( 2 1 4 ) 对于三次b 样条曲线，由插值条件得到胁+ 1 个线性方程，该线性方程组中 包含，7 + l = 所+ 3 个未知量，因此需要添加两个边界条件。这里我们根据所拟和 的曲线类型添加两类边界条件： 1 ) 封闭的周期三次b 样条曲线：磊= 以，雹= 以小d ：= 以+ ：( 2 1 5 ) 2 ) 端点有二重控制点的三次b 样条曲线：巩= d ，以= 以+ 。 ( 2 1 6 ) 下面分别给出均匀三次b 样条曲线和非均匀三次b 样条曲线反算的矩阵表 示。 2 4 1 1 均匀三次b 样条开曲线的反算 由2 2 1 节可知，均匀三次b 样条的矩阵表示 c ( f ) = 丢b 14 3o 36 13 1o 3o 3 o 一3 1 z 一3 d 一2 z 一， d ， f o ，1 ；f = 3 ，4 ，z( 2 1 7 ) 由( 2 1 4 ) 、( 2 16 ) 得均匀三次b 样条反算的矩阵方程 l一1o o 14lo 0141 oool 0oo o 其中g o ，g l ，g ，。为朋+ 1 个型值点。 1 6 ( 2 1 8 ) 以4 以奴 叩o，ooo。o。oo。oo也 o o 0 1一 o o o 4 1 中国科学技术人学硕十论文第二章b 样条曲线曲面 2 4 2 曲面的反算 b 样条曲面的反算就是要构造一张七，次b 样条曲面插值给定呈拓扑矩形 阵列的数据点p ( f = o ，1 ，r ；_ ，= o ，l ，s ) 。通常，类似曲线反算，使数据点阵四 角的4 个数据点成为整张曲面的4 个角点，使其他数据点成为相应的相邻曲面片 的公共角点。这样数据点阵中每一排数据点就都位于曲面的一条等参数线上。曲 面反算问题虽然也能像曲线反算那样表达为求解未知控制顶点d ，( f = 0 ，1 ，朋； = 0 ，l ，刀；所= s + 七一1 ，拧= 厂+ l r 1 ) 的一个线性方程组，但这线性方程组往往过 于庞大，给求解及在计算机上实现带来困难。更一般的解题方法是表达为张量积 曲面计算的逆过程。将曲面的反算问题化解为两阶段的曲线反算问题。待求的b 样条插值曲面方程可写成为 p 白，v ) = 4 ，m ，。0 川，) ( 2 。2 3 ) f = 0 = o 又可改写为 j ，、脚 p 0 ，v ) = i 盔m ，( v ) k 0 ) = c ，( v ) 珊0 ) c ，( v ) = 巧。，( v ) f = o ，l ，聊 ( 2 2 4 ) = d 若固定个参数值v ，就给出了在这些控制曲线上研+ 1 个点c ，( v ) ( f = o ，l ，m ) 。 这些点又作为控制顶点，就定义了曲面上以“为参数的等参数线。当参数v 值扫 过它的整个定义域时，无限多的等参数线就描述了整张曲面。显然，曲面上这无 限多以“为参数的等参数线中，有，z + 1 条插值给定的数据点，其中每一条插值数 据点阵的一列数据点。这刀+ l 条等参数线称为截面曲线。于是就可由反算b 样 条插值曲线求出这些截面曲线的控制顶点z ，( f _ o ，1 ，聊；，= o ，1 ，s ) 。 j ，。委五以t ) 砥，( 2 2 5 ) f = 0 ，l ，所；= o ，l ，刀 一张以这些截面曲线为它的等参数线的曲面要求一组控制蓝线用来定义截面曲 线的控制顶点c ，h + ) = 互，( f = o ，1 ，所；_ ，= o ，1 ，s ) 。类似曲线插值，这罩选择了 一组v 为参数值v u = o ，1 ，s ) 为控制曲线的节点，即数据点，u 的v 参数值。 于是，这个问题就被表达为明十l 条插值曲线的反算问题 1 8 中国科学技术人学硕士论文 第二章b 样条曲线曲面 窆盔，m ，一+ ，) = 乏 = o 1 ，s ；f - o ，l ，z( 2 2 6 ) j = 0 由解这些方程组，得到所求b 样条插值曲面的k + 1 ) g + 1 ) 个控制顶点 矗u ( f = o ，l ，珑；歹= o ，l ，挖) 。图2 - 4 给出了b 样条曲面反算过程的图解。 2 5本章小节 严；= 鬻黧囊荔 。羲冀羹 霾誊稀鬓几何设 计，北京高等教育出版社，2 0 0 l 5 倪明田，吴良芝，计算机图形学，北京北京大 x 中国科学技术人学硕+ 论文第二章b 样条曲线曲面 参数化方法。文中同时介绍了b 样条盐线曲面反算的相关内容。因为b 样条方 法的优良性质，在实践中，人们常用它来处理插值问题，此时就会遇到如何从给 定数据点来确定节点矢量与控制项点的反算问题，这样更符合人的设计习惯，更 利用形状修改。均匀b 样条曲线的反算较为简单，非均匀b 样条反算时，由于 节点矢量的非均匀性，基函数不具有平移性，因此需要分别计算。曲面反算时， 多将其分为两次曲线的反算，不同的是，第二次曲线反算时，反算的型值点是第 一次反算过程计算得到的控制点。 2 0 中国科学技术人学硕十论文第三章单轮廓曲面重构 第三章单轮廓曲面重构 单轮廓的曲面重构是指相邻各切片层上轮廓数相等且均为一的情况，这时候 的重构较为简单。单轮廓曲面重构是多轮廓曲面重构的基础，对应、分支和含多 重封闭轮廓的重构问题的一般处理思路就是通过一定的算法将其转化为多个单 轮廓的曲面重构。因此在做单轮廓重构的时候，我们主要考虑算法的效率及重构 的精度。 在计算机三维数字化模型的表示中大量采用参数曲面。参数曲面根据参数定 义域的不同分为矩形参数域及三角参数域n 7 1 ，各自的代表有n u r b s 曲面和三 角b e z i e r 曲面。重构曲面的选择原则可以分为两种情况：针对有序数据点列，采 用矩形域曲面；无规则的离散数据点，可以构造三角拓扑关系后，基于三角参数 域进行重构。近几十年，国内外对矩形域参数曲面拟合技术进行了广泛的研究。 c d w b o d w a r d 提出了基于蒙皮的b 样条曲线曲面插值方法，这种方法需要交 互操作1 ；d f i 沁o e r s 和n gf o g 提出了约束b 样条曲面逼近的方法凹1 ，使用 最小二乘原理和一阶泰勒展开分别逼近数据点和对数据点进行迭代，生成符合精 度要求的逼近曲面；h ) 哪西u i lp a r k 和k w a i l g s 0 0k 啪提出了使用最小二乘原理 和二分法生成符合一定精度要求的最少控制顶点的曲面算法口引。n u r b s 作为 i s o 在s t e p 标准中制定的自由曲线曲面的唯一表示标准，并且为c a g d 提供了 统一的数学描述方法，已成为参数曲面造型中最通用的形式。第二章中详细介绍 了b 样条曲线曲面的理论，由于b 样条强大的设计自由曲线曲面的功能，以及 局部性、连续性与光滑性及直线再生性等优点，本文以b 样条作为重构的理论 基础。 b 样条重构时的一个关键技术就是找到合适的型值点，要求所选的型值点能 很好地保留轮廓信息。利用c t 、m 对等数据测量技术得到的图像上存在大量冗 余点，直接用这些数据点来重构曲面的话，计算量非常大，处理起来非常复杂， 而且完全没有必要。比如说一条直线由多个点来表示，然而根据b 样条的直线 再生性，只要已知直线的两端点即可恢复直线，直接利用扫描得到的点无疑增加 了下一步处理的计算量。从这些轮廓点中选取部分点一最优点，最优点是轮廓上 的一个重要的局部特征，它集中了轮廓上最重要的形状信息，在没有丢失轮廓数 据信息的条件下，最优点最小化了要处理的数据量，即用最少数目的点表达切片 上的轮廓，由此重构出满足精度要求的曲面。 2 2 中国科学技术大学硕士论文第三章单轮廓曲面重构 3 1简单单轮廓的曲面重构 在利用b 样条重构曲面时，要求相邻层切片上的型值点数或控制点数相同， 一般的型值点获取方法接下来通常要进行相容性处理，导致算法复杂、准确率低。 单轮廓线群的特征就是：它们的几何中心大致位于一条光滑曲线上。因此，我们 提出一种方法，直接利用各切片层的质心位置，以极坐标方式在各切片轮廓对应 位置处取得型值点，该算法避免了轮廓提取步骤，并解决了曲面重构过程中的定 位问题，避免了重构过程中相邻层之间型值点的相容性处理，算法效率得到很大 提高。算法的流程图如下图所示。下面详细介绍各部分。 3 1 1 型值点的获取 对各层切片计算质心位置 u 对各切片层在相应位置取点 o 反算控制点 绘制b 样条曲面 图3 一l 单