（计算机软件与理论专业论文）代数b样条曲线插值与拟合.pdf

新江大学硕士论文摘要 摘要 曲线曲面造型是计算机辅助几何设计和计算机图形学的重要内容，其中曲线 造型技术是曲面造型技术的基础。代数b 样条曲线是一种分段定义的隐式代数 曲线，它具有次数低、分段光滑和局部支撑性等优势。本文从曲线造型的基本问 题出发研究基于代数b 一样条曲线的插值和拟合方法，为进一步对代数b 一样条曲 面的插值和拟合方法奠定基础。论文的整体结构如下： 第一章介绍了自由曲线曲面造型的背景知识和国内外的研究现状，引入了两 类代数曲面( 线) 形式：基于b e r n s t e i n - b 6 z i e r 形式的分片( 段) 代数曲面( 线) 和代数b 一样条曲面( 线) ，并给出了本文的主要研究思路。 第二章提出了一种基于有向距离场的代数b 样条曲线插值重构方法。对于给 定的具有较小噪声的平面点集，我们用一个代数b 样条函数插值该点集并且 拟合该点集的有向距离场，插值曲线即为该代数b 一样条函数零点集。该方法 可以获得高质量的重构曲线，并且可以真实地表达曲线几何特征。为了提高 求解线性方程组的效率，我们提出了相应的并行算法。 第三章研究了平面点集噪声较大情况下的代数b 样条曲线插值方法。该方法 在拟合给定的平面点集的有向距离场的同时，插值用户交互指定的型值点， 从而达到快速重构代数b 样条曲线的目的。同时，根据此方法和b 样条基 函数的局部支撑性，在曲线最后的绘制过程中采用于局部区域m a r c h i n g c u b e 的方式加速，大大提升了曲线绘制的速度。 第四章对研究工作进行了总结，并对未来工作提出了展望。 关键词：代数b 样条曲线，有向距离场，插值，拟合，并行计算 浙江大学硕士论文 a b s t m e t a b s t r a c t c u r v ea n ds u r f a c em o d e l i n gi st h ef u n d a m e n t a lo fc o m p u t e r - a i d e dg e o m e t r i c d e s i g n ( c a g d ) a n dc o m p u t e rg r a p h i c s ( c g ) t h ec u r v em o d e l i n gi st h eb a s i so f t h e s u r f a c em o d e l i n g a l g e b r a i cc u r v ei sap i e c e w i s ee o n t i n u o a sa l g e b r a i cc u r v ew h i c h h a sa d v a n t a g e ss u c ha sl o wd e g r e e ，p i e c e w i s es m o o t h n e s s ，l o c a ls u p p o r t ，e t c i nt h e t h e s i s ，t h ea l g e b r a i cb s p l i n ec h i v ei n t e r p o l a t i o na n df i t t i n gf o rp l a n a rp o i n ts e ta r e i n v e s t i g a t e dw h i c hc a nb ee x t e n d e dt ot h ea l g e b r a i cs u r f a c em o d e l i n gi nt h ef u t u r e t h et h e s i si so r g a n i z e da sf o l l o w s ： i nc h a p t e ri t h eb a c k g r o u n da n dt h es t a t eo f a r to f r e s e a r c h i n go nf r e ef o r mc u l w e s u r f a c em o d e l i n ga r eb r i e f l yi n t r o d u c e d e s p e c i a l l y , t w ot y p e so ft h ep i e c e w i s e a l g e b r a i cc u r v e s u r f a c e ，t 最，b e r n s t e i n - b d z i e rp i e e e w i s ea l g e b r a i cc u r v e s u r f a c e a n da l g e b r a i cb s p l i n ec r a v e s u r f a c e ，a r ed e s c r i b e di nd e t a i l f i n a l l yt h em a i n c o n t r i b u t i o n so f o u rr e s e a r c ha r eg i v e n i nc h a p t e r a na l g e b r a i cb s p l i n ec u l w ei n t e r p o l a t i n ga l g o r i t h mb a s e do nt h e s i g n e dd i s t a n c ef i e l di sp r o p o s e df o rt h eg i v e np l a n a rp o i n ts e to f t h el o wn o i s e a b s p l i n ef u n c t i o ni n t e r p o l a t e st h eg i v e np o i n ts e t ；m e a n w h i l ei tf i t st h es i g n e d d i s t a n c ef i e l do ft h eg i v e np o i n ts c t t h ez e r os e to ft h eb s p l i n ef u n c t i o ni st h e c o n s t r u c t e dc u r v e t h u sah i g hq u a l i t yi n t e r p o l a t i n gc u n r ei so b t a i n e dw h i c hc a n r e v e a lt h eg e o m e t r i cf e a t u r e so ft h ep o i ms e t f i n a l l y , t h ea c c e l e r a t i o no ft h e a l g e b r a i cb s p l i n ei n t e r p o l a t i o na n df i t t i n g i sd i s c u s s e dw h e r et h el a r g e - s c a l e l i n e a re q u a t i o n sa l ep a r a l l e ls o l v e db yu s i n gd u a lc o r ec p u i nc h a p t e ri n a n o t h e ra l g e b r a i cc u r v ei n t e r p o l a t i n gm e t h o db a s e do nt h es i g n e d d i s t a n c ef i e l di sp r o p o s e df o rt h eg i v e np l a n a rp o i n ts e to fh i g hn o i s e f i r s tt h e p r o p o s e dm e t h o df i t st h es i g n e dd i s t a n c ef i e l d , a n dt h e ni ti n t e r p o l a t e ss o m e p o i n t ss p e c i f i e db yu s e r s t h i sm e t h o dc a l lr e c o n s t r u c tt h ea l g e b r a i cb s p l i n e c u l w ef a s t t h eg u r v er e n d e r i n ga c c e l e r a t i o ni sa l s od i s c u s s e db yu s i n gt h el o c a l s u p p o r tp r o p e r t yo f t h eb s p l i n ef u n c t i o n f i n a l l y , t h ec o n c l u s i o ni sd r a w na n df u t u r ew o r k i sp r o p o s e d k e y w o r d s ：a l g e b r a i cb s p l i n ec u r v e ，s i g n e dd i s t a n c ef i e l d ，i n t e r p o l a t i o n ， f i t t i n g , p a r a l e l lc o m p u t i n g 浙江大学硕十论文图目录 图目录 图1 - 1 代数曲面实例，f ( x ，y ，z ) 为x 2 + y 3 一z 2 = 0 5 图1 2 代数曲面实例，f ( x ，y ，z ) 为，+ j ，2 一z 2 = 0 5 图1 3 四次代数曲面6 图1 43 次代数曲面控制顶点蚴7 图1 5 左：八分之一球面的控制顶点及系数右：八分之一球面的等势线1 0 图3 1 曲线编辑流程3 7 l 浙江大学硕士论文 表目录 表目录 表1 1 代数曲面次数与多项式项数关系表6 表2 一ll e v e ls e t 方法实验结果1 6 表2 2 点集插值重构曲线实验结果1 9 表2 3l e v e ls e t 建立拓扑复杂给定点集2 2 表2 - 4 重构结果2 3 表2 5 光顺项调节2 6 表2 - 6 不同阶数的代数b 一样条曲线重构结果2 8 表2 7 改变距离场剖分数的实验结果3 0 表2 - 8 光顺项实验结果3 2 表2 - 9 并行优化实验结果3 4 表3 - 1 宜接操控代数b 样条曲线3 9 表3 - 2 带距离场约束编辑4 l 表3 3 重构后曲线的形状4 2 表3 - 4 局部绘制实验结果“ 浙江大学硕士论文第l 章绪论 第1 章绪论 曲面造型是计算机图形学和计算机辅助几何设计( c o m p u t e ra i d c dg e o m e t r i c d e s i g n ) 的一项重要内容，主要研究在计算机图像系统的环境下对曲面的表示、 设计、显示和分析。它肇源于飞机、船舶的外形放样工艺，由c o o n s 、b 6 z i e r 等 大师于六十年代奠定理论基础【1 】。经三十多年发展，现在已经形成了以非均匀有 理b 样条( n u r b s ：n o n - u n i f o r mr a t i o n a lb s p l i n e ) 参数化特征设计 ( p a r a m e t e r i z e da n dc h a r a c t e r i s t i cd e s i g n ) 和隐式代数曲面表示这两类方法为主 体，以插值( i n t e r p o l a t i o n ) 、拟合f l i t t i n g ) 、逼近( a p p r o x i m a t i o n ) 这三种手段为骨 架的几何理论体系【2 】。 本章先对自由曲线曲面( f r e ef o r mc u r v e s s u r f a c e s ) 造型技术作一个概要的 回顾，再详细介绍代数曲面以及代数b ，样条曲面。最后介绍本文的组织结构与 主要内容。 1 1 自由曲线曲面( f r e ef o r mc u r v e s s u r f a c e s ) 造型技 术 计算机辅助设计中由已知曲线或曲面的数学方程生成的曲线曲面称为规则 曲线曲面，例如柱、锥、球面等，由常用的隐式函数或二次方程的显函数来表示。 但在汽车、轮船、飞机、模具、艺术品等产品设计中，存在大量的曲线曲面是不 能用简单的数学方程来描述，这类曲线曲面称为自由曲线( f r e ef o r mc u r v e s ) 和自 由曲面( f r e ef o r ms u r f a c e s ) 。这类曲线曲面是计算机辅助几何设计研究的主要几 何形状1 4 。 本节的1 1 1 和1 1 2 两小节概略介绍了自由曲线曲面造型中常用的参数曲线 曲面造型和隐式曲线曲面造型技术。 1 1 1 参数曲线曲面造型技术 在几何造型系统中，参数曲线曲面指将曲线曲面方程表示成参数的形式，曲 线上任一点的坐标均表示成给定参数的函数。假定用t 表示参数，平面曲线上任 一点p 可表示为： h f ) = 瞰f ) ，删】 ( 1 1 1 ) 空i b j 曲面上任一三维点p 可表示为： 浙江大学硕+ 论文 第1 章绪论 p ( d = 瞰f ) ，) f ) ，z ，k l 而，i = m + l ，m + 2 ，肋一l ，节点 的重数最多为 m 。 i6 1i = l 2 n 乃= 乃一n + i i = n + i ，+ 2 ，。j l 1 6 2 i = 玎+ l ，”+ 2 ，埘+ 蜘+ i y n ，只“ 儿，z “ 乃，i = n + i ，n + 2 ，n - 1 ，节点咒的重数最多为 n 。 8 浙江大学硕十论文第1 章绪论 铲卜誊三誊二2 + q 乃“ z 口，乃“ z 叮，缸。 ，i = q + i ，q + 2 ，g 一1 ，节点乙的重数最多为q 。 然后将公式1 2 7 中的be r ! n s t e i n 基函数替换为b ，样条基函数，则在彤内的代数 曲面片可以定义为如下张量积形式的分片代数曲面： f ( x , y , z ) ：羔窆壹m 朋( x ) n j ，。( y ) m 口( z ) ( 1 - 2 8 ) j = lj * lk = l 其中 b ( 功，。o ) ，机詹0 ) 为m ，n ，q 阶的b 一样条基函数，为控制系数， 其个数为m x n x q 个，m 、n 、q 分别满足m m ，疗n , q q 。公式1 2 8 称为代 数b 样条曲面。 定义# ，z ，z ：为x ，y 和z 在h ，a 2 ， 6 l ，如1 和【c 1 ，c 2 】上的b 一样条线性组合的系 数： 工= 艺# 爿，) ，：主z t y ) ，z ：羔五m ，口( z ) ( 1 2 - 9 ) i 2 1 j - li ，l 则z ，t ，z ：可以由相应节点向量的节点来计算( 公式1 2 1 0 只列出# 的计算公式， 一，z ：的计算与z 类似) ： u 1 f 薯2 j 而k 己* i + l 雄 ( 1 2 1 0 ) 通过1 2 9 和1 _ 2 1 0 的定义，可以将1 2 8 中的f ( x ，y ，z ) 看成是一个参数形式的张 量积三变量b 一样条超曲面= p ( u ，v , t ) 与妒= o 相交的结果： 以m ，v ，f ) ：窆窆妻缘m 朋似) ，( v ) m ，口( f ) ：0 ( 1 2 1 1 ) i = l ，一lk = l 其中，= 瞳，z ，z ：，】。 1 2 9 ，1 2 1 0 和1 2 1 l 解释了控制系数锄的几何意义：作为由1 2 1 1 定义 的参数b 一样条超曲面的控制多边形的第四维坐标。当在代数b 一样条曲面片的定 义域包围盒腰上按照公式1 2 9 定义的方式插入控制顶点( i ，巧，乏) 时，可以 9 浙江大学硕上论文第1 章绪论 看作是落在相应控制顶点上的控制系数。图1 5 左给出了一个八分之一球面在定 义域中的控制顶点以及相应的控制系数，图i - 5 右给出了这个八分之一球面的等 势线【3 2 1 。 x 图1 - 5 左：八分之一球面的控制顶点及系数 z 右：八分之一球面的等势线 1 2 3 代数b 样条曲线曲面造型技术的优势 代数b 样条曲线曲面造型技术属于隐式曲线曲面造型技术的一种，其本身具 备了隐式曲面曲线造型技术相对与参数曲线曲面造型技术的优势：( i ) 参数曲面 在表示人体肌肉、器官、水滴、云、烟等物体的造型和表现动画等方面存在着许 多困难，而代数b 一样条曲面则在这些流形的表达上有很大的优势。( 2 ) 代数b 样条曲面提供了足够的自由度来满足复杂产品外表面建模的需要，且代数b 样 条所具有的较多的自由度使得采用低阶函数满足几何设计约束的要求成为可能。 ( 3 ) 代数b 样条曲面用多项式函数来表示，多项式的运算比一般的解析函数和 有理函数的运算更为简单，计算效率更高。( 4 ) b 样条代数曲面由于采用了隐式 函数的表达方式，使得例如判定空间一个点是否落在曲面上或者落在曲面哪一侧 这类问题大大简单，只需要将空间点的坐标带入b 样条曲面函数即可判定。而 且，隐式曲面将空间自然的分割为，y ，z ) o 和，弘z ) 0 两部分，这对于几 何造型应用中的求交( i n t e r s e c t i o n ) 、混合( b l e n d i n g ) 和偏移( o f f s e t ) 操作具 有很多的帮助，在计算机动画应用中，特别是碰撞检测中，更能发挥其优势。( 5 ) 插值、拟合和逼近操作常常作为一个成熟的几何理论体系的骨架，相比较于参数 曲线曲面造型技术，代数b 样条曲线曲面造型技术在插值、拟合等操作时不需 要对原始数据预先参数化，能更好的适用于原始数据拓扑复杂的情况。( 6 ) b 样条曲线曲面造型技术能够在有限的区域内直接表达物体落在该区域的部分，且 对于这部分物体的编辑也具备几何直观性【3 2 】。 同时，代数b 样条曲线曲面造型技术相对于b e r n s t e i n - b d z i e r 形式的分片代 数瞌线曲面造型技术，也有如下的优势：( 1 ) 由于代数b 样条曲线曲面采用了 b 样条基函数，相对于b e r n s t e i n 基函数，代数b 一样条曲线曲面造型技术具备了 1 0 浙江大学硕上论文第1 章绪论 b 一样条基函数的局部支撑性，在曲线曲面的编辑及其之后的绘制中相对于 b e m s t e i n - b 6 z i e r 形式的分片代数曲线曲面造型技术有很大的优势。( 2 ) 代数b 样条的控制系数具有明显的几何意义，可以直观的通过调节控制系数控制曲 线曲面的变化。 1 2 4 本文主要内容和组织结构 自由曲线曲面造型是一个很大的课题，涉及到很多方面的研究。其中曲线造 型技术是曲面造型技术的基础，在很多问题上两者具有相似性。文本所研究的代 数b 样条曲线从表达形式上看，是代数b ，样条曲面( 公式1 2 8 ) 的低一维表达 形式。其具体的表达形式为： f ( x ，力= 白i ，。( x ) 以) ( 1 2 1 2 ) 扭l j - i 其中m ( 力，哆，。( 力为m ，n 阶的b 一样条基函数，白为控制系数，其个数为肌撑 个，m 、n 分别满足m m ，n 2 n 。本文中定义的节点向量均为两端重节点，内 部均匀等距的节点向量。设定义域为q = h ，a z x b i ，6 2 】，则x 方向上的节点向量 u = 缸l ，m 2 ，“，+ ) 为： 吩= a i i = 1 2 。埘 考莩若告。一m ) + q z = m + - ，膨+ 2 ，m ( 1 2 1 3 ， a 2 i = m + 1 ，m + 2 ，j ，l + 肘 y 方向上的节点向量v = “v 2 以+ 。 为： f 6 lf = 1 2 峙= 鼎( f 一忉+ 岛f = + l + 2 ，咒 ( 1 2 “) i6 2 i = n + l ，n + 2 ，刀+ n 本文的主要工作和创新如下： 基于有向距离场的代数b 样条曲线插值重构。 曲线重构是曲面重构的基础。本文提出一种以代数b 样条函数为表达形式， 基于给定点集的有向距离场隐式曲线插值方法。该方法的前提条件是给定点 浙江大学颂t 论文第1 章绪论 集的噪声较小，分布较均匀。其核心思想是针对给定点集采用l e v e ls e t 方法 建立其离散几何距离场，然后结合重构曲线的光顺条件用一个代数b 。样条函 数插值给定点集的点，同时拟合其建立的几何距离场。最后求解得到的代数 b 一样条曲线即为该代数b 样条函数的零点集。整个求解过程归结为求解一个 线性方程组，使得该方法快速、稳定。采用该方法插值重构曲线，不仅得到 了高质量的曲线，同时也求得了表达给定点集几何特征的代数b 一样条函数， 方便之后的编辑、变形。 基于用户交互的代数b 样条曲线插值重构( 简称“拟合后插值”) 。 本文针对噪声较大的给定点集，提出了通过用户交互模式，插值部分用户指 定的型值点的方法重构曲线的方法。给定点集的大噪声，使得插值给定点集 的全部点没有实际使用意义。本文通过现有成熟的m l s 技术对给定点集的 重采样，获得了噪声较小，分布较均匀的平面点集。采用l e v e ls e t 方法对重 采样后的平面点集建立离散的有向距离场，并用一个代数b 一样条函数拟合该 有向距离场。然后通过用户交互方式，记录用户需要重构后曲线精确经过的 型值点，最后采用最d x - 乘法重新修正己求得的代数b 样条函数的控制系 数，使其插值用户指定的型值点。由于代数b 一样条曲线拟合有向距离场的代 价要远远小于同等条件下代数b 样条曲线插值给定点集的代价，该方法可以 在用户满意度大致相当的情况下，快速的重构代数b 样条曲线。 代数b 样条曲线插值和拟合过程中的计算加速。 代数b 样条曲线的插值和拟合过程最后归结为求解一个线性方程组。由于该 线性方程组的自由度与代数b 样条函数的x ，y 方向上的节点向量分割数相 关，当节点向量分割较密的情况下，该线性方程组的系数矩阵计算量很大。 本文通过对该系数矩阵的分析，针对目前的双核c p u 进行了并行计算优化， 大大提升了计算系数矩阵的时间。同时，本文针对“拟合后插值”的代数 b 样条曲线的绘制过程，根据b 样条基函数的局部支撑性，对该代数b 样 条曲线的局部采用m a r c h i n gc u b e 算法，大大提升了隐式曲线的绘制速度。 1 2 浙江人学硕士论文第2 章基于有向距离场的代数b 一样条曲线插值莺构 第2 章基于有向距离场的代数b 样条曲线插值重构 2 1 概述 曲面重构一直是计算机视觉和逆向工程中深入研究的问题，重构的目的是将 真实世界中的物体转换为计算机可以处理的数学形式。随着三维数字摄影技术和 三维扫描系统的发展，人们已经能够直接获得真实世界中物体的由基本元素为点 所表示的点采样几何信息。 计算机图形学中将以点为基本表示元素的曲面称为点集曲面( p o i n ts e t s u r f a c e ) 。在c a d c a m 、计算机图形学、科学计算可视化等领域中常常遇到这 样的问题：如何将这种点集曲面转化为传统的网格曲面、参数曲面或隐式曲面。 这类问题就是经典的曲面重构问题，它可以描述为：对给定的或采集到的、表示 某一几何形状的无序点集( 又称点云) ，如何重构其内含表示的目标曲面，使得 点集离该目标曲面在某种度量意义下偏差最小。随着计算机技术和数据采集技术 的发展，点采集几何信息往往数据量巨大、目标曲面的拓扑结构复杂，对于此类 数据的曲面重构显的十分困难，近年来已形成了一个新兴的研究领域。 目前的曲面重构算法，大致可以分为网格重构方法、参数重构方法和隐式重 构方法。点集的网格表示是一种应用很广泛的曲面表示形式，点集网格重构后的 结果是三角面片表示的曲面，因此比较容易绘制曲面，并且得到了大多数显卡的 硬件支持；参数重构方法将目标曲面表达成一张参数曲面或由若干参数曲面片拼 接的曲面，通过拟合的方式使得点集到该目标曲面的误差最小；隐式重构方法构 造目标曲面为某一隐式函数的等值面，通过拟合或插值的手段求解该隐式函数获 得目标曲面。 本章将重点放在点集的隐式重构表示上。点集的隐式重构方法分为拟合和插 值两种，若原始点集没有噪声或者噪声很小时，可以采用插值的方法；若原始点 集的噪声很大时，可以采用拟合的方法来重构曲面。在很多情况下，平面点集的 曲线重构是曲面重构的基础1 3 ”，本章着重讨论了在点集没有噪声或者噪声很小 时采用插值的方法重构曲线，所给的方法可以很自然的推广到三维点集重构曲面 的情形。 2 1 1 插值重构曲线的思路 由于插值方法一般用于给定的点集没有噪声或噪声很小的情形，本章所介绍 的方法主要针对噪声很小的平面点集重构曲线这一类问题。本章提出的基于代数 b 样条曲线的插值重构方法属于隐式重构方法的一种，通过求解相应的隐式函数 1 3 浙江大学硕十论文第2 章基于有向舜离场的代数b 样条曲线插值重构 来描述平面点集。根据公式1 2 8 对代数b 一样条曲面函数的定义，可以给出代数 b 样条曲线函数的定义： f ( x ，y ) = 勺m 朋( x ) 坼，( ) ，) = o ( 2 1 1 ) 扛ij t l 其中，m ( 力，m ，( 力为m 、n 阶的b 一样条基函数，为控制系数，其个数为 m n 个。m 和n 分别满足肼m ，h n 。 本章的思路是首先建立给定点集的内含几何距离场，将点云信息“无损”地 转化为几何距离场信息，再用一个代数b 一样条函数( 2 1 1 ) 插值点集且同时拟 合该几何距离场，最后求解得到代数函数的零等值线即为重构的曲线。 2 2 插值重构拓扑简单曲线 本节所介绍的插值重构方法针对于噪声极小、分布均匀的“线状”的给定点 集，点集的有向距离场采用l e v e ls e t 方法建立。 2 2 1 建立给定点集的有向距离场( l e v e ls e t 方法) l e v e ls e t 方法最早由s e t h i a n 和o s h e r 于1 9 8 8 年提出，是处理封闭运动界面 ( 曲线或曲面，对于曲线的讨论均适用于曲面，故在此略去曲面) 随时间演化过 程中拓扑变化的有效工具。简单的说，l e v e ls e t 方法是把当前正在演化的曲线看 作是一个更高维函数的l e v e ls e t ，借用双曲守恒定律的计算方法，利用曲线曲面 演化与h a m i l t o n - j a e o b i 方程的相似性，给出了一种曲线曲面演化的强鲁棒性的 计算方法。l e v e ls e t 方法自提出以来，已经广泛的应用在图像处理、计算机视觉、 计算机图形学和科学计算可视化等领域。 设r ( f ) 为一个随时间t 演化的界面，r ( 0 上的点沿着该点法向以速度f 运动。 f 可以是多个变量的函数，如曲率、法向等，f 的方向与该点的法向相同或相反。 将r ( f ) 嵌入三维空间并隐式的表示为随着时间变化的标量场函数中( x ，f ) 的一个 等值面。场函数o ( 工，f ) 满足： r ( f ) = 肖i 中( 石，f ) = 七 ( 2 2 1 ) 其中，k r 是标量值，t 表示时间，x = x ( f ) 表示点随着时间运动的轨迹函数。 r ( f ) 称为l e v e l s e t 函数，其零等值面表示目标函数，即： 浙江人学硕士论文第2 章基于有向距离场的代数b 样条曲线插值重构 r ( f ) = x ( f ) l ( ( f ) ，f ) = o ( 2 2 2 ) 由于点x 沿着方向运动，所以置一= ，( 彳o ) ) 。对方程m ( ( f ) ，f ) = 0 两边分别对 t 求导，得到： 西( f ) + v m ( j ( f ) ，t ) x ( f ) = 0 ( 2 2 3 ) 再将置n = ，( j ( f ) ) 和矗= v o v o i 代入公式2 2 3 ，得到： 西( f ) + ，i v m ( f ) l = 0 ( 2 2 4 ) 上述的h a m i l t o n - - j a c o b i 方程即为l e v e ls e t 方程，标量场函数m 一般取r ”( 在 本文中取r 2 ) 中的有向距离函数： f d ( 并) x f 界定的区域 e o ( x ( t ) ，f ) = 0 x f( 2 2 5 ) l d ( x )x 仨f 界定的区域 其中，d ( x ) = m 。i n ，u p x l l y 0 点x 到曲线r 的最近距离嘲。 当速度函数f 恒正时，l e v e ls e t 方程( 公式2 2 4 ) 可以转化为与时间无关 的静态方程。用t 表示界面经过空间一点的时间函数，则t 满足如下的方程： i v t f = 1 ( 2 2 6 ) 若f 只依赖位置变量，则公式2 2 6 为e i k o n a l 方程的一种形式，其直观的理解 为到达时间函数的梯度和速度成反比。对公式2 2 6 所示方程的求解最常用的是 s e t h i a n 等提出的f a s tm a r c h i n g 方法，可以用差分格式得到如下的解( 公式2 2 7 给出的是曲线形式的解，三维曲面形式的解也可以很容易的求得) ： 阿f = 嚣t 茹喇+ m i n ( d 磊；t 卜，乃 旺2 肿 。l + m a x 峨7 ，o ) 2 7 ，o ) 2l 9 其中，d ，d ”，d ，d + ，分别是x ，y 轴的向前和向后差分算子。 结合以上的讨论，对给定点集建立有向距离场的算法如下： ( 1 ) 初始化： 取点集正包围盒k 倍( k 1 ) 作为距离场的范围，按照给定的距离场 剖分份数将距离场剖分为正规网格，记网格步长为。 设r = 3 ，以点集为中心，r 为半径构成包围目标曲线的一条窄带 q 。对落在q 内的网格点，设定其距离值为它到点集的最近距离的 1 s 浙江大学顽上论文 第2 章基于有向距离场的代数b 样条曲线插值蕈构 绝对值，符号为有向距离的符号，其余的网格点的值为无穷大。 将所有距离值小于的网格点标记为a l i v e ，其余的网格点标记为 f a r 。 将a l i v e 中距离值为正的网格点加入p l u s 集合，负的网格点加入 m i n u s 集合。 ( 2 ) 演化。演化分为两个步骤：向外演化和向内演化。向内演化的机制与 向外演化基本一致，故在此只介绍向外演化。 将p l u s 集合中任意一点置，的四个相邻的点，即只川，巳，墨u 中没有标记a l i v e 的点加入到c l o s e 集合。 将c l o s e 集合中网格点距离值最小的点标记为t r i a l ，将其标记为 a l i v e 并从c l o s e 集合中删除，符号为正。 将与t r i a l 相邻且标记为f a r 的网格点加入c l o s e 集合，采用求解公 式2 2 7 所示的方程更新在c l o s e 集合中且与t r i a l 相邻的网格点的 距离值。 如果c l o s e 集合不为空，则转，否则结束。 实验结果如表2 1 所示。 表2 1l e v e ls e t 方法实验结果 1 6 浙江大学顾上论文第2 章基于有向距离场的代数b 样条曲线插值鼋构 2 2 2 基于有向距离场的曲线插值重构算法 代数b 样条曲线的形式为： d f ( x ，j ，) = r 捌( 砷m ，( y ) r = ls = l ( 2 2 8 ) 其中r 埘( 功，j ，( y ) 为m 、n 阶的b 一样条基函数，为控制系数，其个数为m n 个。i l l 和n 分别满足历m ，” - n 。记c = “l ，c 1 2 , - - , e 2 l ，c 2 2 ，) 为代数b 一 样条函数y ) 的控制系数拉直向量，q = ( q l 。，q l ：， q 2 ，q 2 ：吼。) 为厂阮y ) 中x ， y 方向上b - 样条基函数乘积的拉直向量，= ，( 曲m ，( y ) ，则2 2 8 式可以 表达为： f ( x ，y ) = c 圩，o ) i ，( ) ，) = 9 7 c ( 2 2 9 ) ，l ，。l 构造该代数曲线在x ，y 方向上的节点向量【，= “。，地删。+ 。 ，v = “，v 1 以+ ， 满 足： u i 。 u = “l q + 尝m 南1 ( f m ) 一肘+ 、 口2 岛 a + 揣( f 一) 6 i = 1 2 a t 4 f = m + 1 ，m + 2 ，一聊 i = ，卵+ 1 聊+ 2 j ，l + m i = l ，2 ，n i = + 1 ，+ 2 ，n i = + 1 玎+ 2 m + n ( 2 2 1 0 ) ( 2 2 1 1 ) 其中h ，a ：】，【6 i ，6 2 】为x ，y 方向节点向量的范围，一般需要比距离场的包围盒稍 大。 代数b 一样条曲线在点集的有向距离场中的误差为： e r r ( c ) ：壹勃，( 而，乃) 一办1 1 2 ( 2 2 1 2 ) 其中，q ，g 为x ，y 方向上距离场的剖分数，而，乃为距离场中编号为( i ，j ) 的 网格点的x ，y 坐标。以表示距离场中编号为( i ，j ) 的网格点的有向距离值。 1 7 浙江大学硕 论文 第2 章摹于有向距离场的代数b 样条曲线插值黄构 ，( ，j ，) 为距离场中编号为( i ，j ) 的网格点在重构后的曲线中的值。 由此，可以给出优化方程； i n i n e 打( 。) ；塞壹i i ，( 玉，乃) 一嘞i f s 一 ( 2 2 1 3 ) ( 五，五) = 0 七= 1 2 三 其中，( 置，k ) 表示给定点集的第k 个点的x ，y 坐标，l 表示给定点集中点的个 数对公式2 2 1 3 所示的优化方程，可以采用拉格朗日( l a g r a a g e ) 最小二乘法 求解。将约束条件乘以系数五代入目标函数胁( 力，得到： q ( c ) ：妻壹“，乃) 一吃j j 2 + 壹五厂( 五，) ( 2 2 1 4 ) 将代入i = y ；，- - | 2 2 9 2 21 4 可以得到： q ( c ) ：壹圭忙( 墨，乃) ，c 一吃1 1 2 + 竞五g ( 以，) r c ( 2 2 1 5 ) 求解目标函数e r r ( c ) 的最小值，即求解q ( c ) 的极值点。对上式( 2 2 1 5 ) 两边分 别求和五的偏导，得到； 吲墨乜。 乡乞= 2 善乳( ) r c 吲u 批“乃) 】 ( 2 2 舶) + 五，朋( 五) m ，( ) = o 设a = “，如，五) ，则2 2 1 6 两个等式可以联立成一个线性方程组，如下： 浙江大学硕上论文第2 章基于有向盛| 离场的代数阻样条曲线插值重构 g ( 置，x ) g ( t ，艺) q ( x l ，圪) l ，。( ) l ( y ，) g ( 一，y j ) 1 = 1 ，q 曲 艺| j ，( t ) ：，( ”) g ( 一，y ，) o o - - o ,vj。r(xoniv(to坐导竽盟下nj,u(xl)n”(yz) 艺兰以。( t ) 虬，( y ，) g ( 葺，乃) 生些芋! 业监业掣业监出譬纽型 f - l ，- l 0 o o 宝壹l 。“) m ，( ”) d o 羔妻i 。( ) m 。( ) 吒 兰壹。瓴) 虬( 乃) 毛 ( 2 2 1 7 ) 对上述的线性方程组可以采用l u 分解进行求解。实验结果如表2 - 2 所示： 表2 - 2 点集插值重构曲线实验结果 匿名称一，i 。募集数黾一。 。阮n 值i n , n 值距离场剡分数i c r o w n1 5 5 3 ，33 1 ，3 13 7 。3 7 9 浙江大学硕士论文第2 章基于有向距离场的代数b 样条曲线插值重构 一 实验结粟 c o n c u r v e2 1 63 ，33 5 ，3 54 1 ，4 1 i实验结粜i r e v s1 3 23 。32 6 ，2 63 2 ，3 2 2 0 浙江大学硕士论文第2 章基于有向距离场的代数b 样条曲线插值蓬构 ， 实验结果 争 “ 。 鼋 j 2 3 插值重构拓扑复杂曲线 对复杂拓扑点集的插值重构在思想上与简单拓扑点集的插值重构基本一致。 为了针对点集拓扑复杂的特性，需要修改l e v e ls e t 方法中初始化的步骤，重新 确定距离场网格点距离值。由于距离场网格点的距离值为该网格点到给定点集的 最小距离的绝对值，故只需要重新确定网格点距离值的符号即可。 本节在2 3 1 小节中给出了修改后的有向距离场建立方法，并在2 3 2 小节给 出了相应的实验结果。 2 3 1 建立给定点集有向距离场 拓扑复杂点集有向距离场的建立通过第2 2 1 小节介绍的l e v e l s e t 方法建立， 在此不再赘述。下面给出l e v e ls e t 方法的初始化步骤中的改进： 初始化： 取点集正包围盒k 倍( k 1 ) 作为距离场的范围，按照给定的距离场 剖分份数将距离场剖分为正规网格，记网格步长为。 设r = 3 ，以点集为中心，r 为半径构成包围目标曲线的一条窄带 q 。对落在q 内的网格点，设定其距离值为它到点集的最近距离的 绝对值，其余的网格点的值为无穷大。对落在q 内的每个网格点，分 2 1 浙江大学硕上论文第2 章摹于有向距离场的代数b 样条曲线插值蕈构 别与给定的“线状”点集相交，计算每个网格点与点集相交的交点个 数。若交点个数为奇数，则该网格点的符号为负，反之则为正。若相 交的交点为给定点集中的点，则在i n t e r s e c t i o n 集合中查看是否有 该交点，若有该交点，则本次相交的交点不计入该网格点与点集的交 点总数中；若没有该交点，将该交点( t k 就是给定点集中的点) 的编 号放入i n t e r s e c t i o n 集合，并将本次相交的交点计入该网格点与点 集的交点总数中。 将所有距离值小于的网格点标记为a l i v e ，其余的网格点标记为 f a r 。 将a l i v e 中距离值为正的网格点加入p l u s 集合，负的网格点加入 m i n u s 集合。 - z v e ls e t 方法的演化步骤则不需要修改，与2 2 1 小节介绍的演化步骤一致。 2 3 2 实验结果 采用了修改初始化步骤的l e v e ls e t 方法，可以处理不少拓扑复杂的给定点 集。实验结果如表2 - 3 所示： 表2 3l e v e ls e t 建立拓扑复杂给定点集 浙江大学硕七论文 第2 章基于有向距离场的代数b 样条曲线插值重构 根据上述实验结果，可以很好的区分距离场网格点的内外。通过上述距离场的曲 线插值重构结果如表2 - 4 所示： 表2 - 4 重构结果 、+ 名j 彰。- 。二点集个数! fm 、馨值 。 m 、1 1 尴距离场剖分数i n e i q i e 1 3 2 i 3 ，33 2 ，3 23 8 ，3 8 i实验结果i ! i i