（计算机软件与理论专业论文）基于多尺度csrbf离散曲面融合研究.pdf

浙江工业人学硕十学位论文 基于多尺度c s r b f 离散曲面融合研究 摘要 随着电影、游戏等娱乐事业以及军事、工业等对三维技术的需求增大，三维处理技术 得到了迅速的发展。伴随着各种模型获取手段的增多，无论是网格模型还是点模型，使得 模型库变的异常庞大，模型资源异常丰富。如何有效的利用这些模型，使三维创作人员更 加高效进行编辑操作，模型编辑技术也就应运而生。本文主要研究了两方面内容：基于点 模型的布尔运算及其融合方法；基于网格模型的离散曲面融合方法。 本文的提出的两种方法，无论是布尔运算还是离散曲面融合，都涉及到隐函数，所以 如何找到一个能够快速插值拟合曲面，能够使曲面光滑过渡的隐函数，也是重要目标之 一。 首先利用自适应八叉树进行插值加速，利用多尺度c s r b f ( c o m p a c t l ys u p p o r t e x ir a d i a l b a s i sf u n c t i o n s ，紧支径向基函数) 隐式化点模型，进行内外测试判断，最后实现布尔运算， 能把简单的点模型构造成复杂的点模型。并把布尔运算技术运用到网格模型上，实现了一 种曲面融合方法。 其次，根据以往一些网格模型融合算法的缺点，并结合其优点，提出了一种离散曲面 融合算法。该方法首先提取融合模型间的边界轮廓线，然后进一步网格化边界轮廓线。用 多尺度c s r b f 插值过渡曲面，得到零值面，最后用网格细分优化算法进一步细分网格， 通过控制点迭代逼近零值面。最终实现了曲面的无缝拼接及光滑过渡。因为过渡曲面的生 成是受周围点的影响的，离过渡曲面越近的点，其影响度较大，反之越小，本文根据此特 点，给出了一种加速插值曲面的方法，特别对于模型复杂或包含拓扑点较多的模型，加速 越明显。 最后总结了全文，结合本文方法中还存在着一些不足，给出了进一步工作的思路。 关键词：隐函数，布尔运算，多尺度c s r b f ，离散曲面融合，轮廓线间网格化，插值加 速算法 浙江下业人学硕十学位论文 r e s e a r c ho nm u i r i s c a l ec s r b fb a s e d d i s c r e t es u r f a c ef u s i o n a b s t r a c t w i t hm o v i e s ，g a m e sa n do t h e re n t e r t a i n m e n ti n d u s t r ya sw e l la st h em i l i t a r y , i n d u s t r y , i n c r e a s e dd e m a n df o rt h r e e - d i m e n s i o n a lt e c h n o l o g y , t h r e e d i m e n s i o n a lp r o c e s s i n gt e c h n o l o g y h a sb e e nr a p i dd e v e l o p m e n t a l o n gw i t ht h ei n c r e a s ei nav a r i e t yo fm o d e l st oo b t a i n ，w h e t h e ri t i sa 妍dm o d e l ，o rp o i n tm o d e l ，i tm a k e sm o d e l b a s eb e c o m ee x c e p t i o n a l l yl a r g ea n d e x t r a o r d i n a r i l yr i c h h o wt oe f f e c t i v e l yu s et h e s em o d e l st om a k eo f f i c i a l sm o r ee 伍c i e n t t h r e e d i m e n s i o n a le d i t i n go p e r a t i o n , m o d e le d i t i n gt e c h n i q u e sa b o u n d t l l i st h e s i ss t u d i e st w o a s p e c t s ：t h eb o o l e a no p e r a t i o n so np o i n tm o d e l sa n dt h ef u s i o n ；g r i d b a s e dm o d e lo fd i s c r e t e s u r f a c ef u s i o nm e t h o d t l l i st h e s i sp r o p o s e at w om e t h o d s e i t h e rb o o l e a no p e r a t i o n so rd i s c r e t es u r f a c ef u s i o n , a r e r e l a t e dt ot h ei m p l i c i tf u n c t i o n h o wc a l lw ef i n dai m p l i c i tf u n c t i o nw h i c hi sf a s ti n t e r p o l a t i n g | f i t t i n gs u r f a c e ，a n dm a k et h et r a n s i t i o ns u r f a c es m o o t h , i sa l s oai m p o r t a n tg o a l o u rt h e s i su s eo f a d a p t i v e o c t r e ei n t e r p o l a t i o na c c e l e r a t i o n a n dm u l t i s c a l e c s r b f ( c o m p a c t l ys u p p o r t e dr a d i a lb a s i sf u n c t i o n s ) i m p l i c i tp o i n tm o d e li no r d e rt oc a r r yo u t i n t e r n a la n de x t e r n a lt e s t i n g ，a n df i n a l l yr e a l i z a t i o no fb o o l e a no p e r a t i o n sw h i c ha b l et o c o n s t r u c tt h es i m p l ep o i n tm o d e l si n t oac o m p l e xp o i n tm o d e l a n du s i n go fb o o l e a n c o m p u t i n gt e c h n o l o g i e st ot h eg r i dm o d e l t h a ta c h i e v eas u r f a c ef u s i o nm e t h o d b a s e do ns o m e m e s hf u s i o na l g o r i t h ms h o r t c o m i n g s ，c o m b i n e d 埘t l li t sm e r i t s ，w ep r e s e n ta d i s e r e t es u r f a c ef u s i o na l g o r i t h m t i l i sm e t h o df i r s te x t r a c tt h eb o u n d a r yc o n t o u rl i n e sb e t w e e n t h ef u s i o nm o d e l s ，a n dt h e nf u r t h e rg r i dt h eb o u n d a r yc o n t o u r s u s i n go fi n t e r p o l a t i o nt h e t r a n s i t i o ns u r f a c ew i t hm u l t i s c a l ec s r b f - t h a tg e n e r a t e st h es u r f a c eo fz e r o l e v e ls e t a tl a s t , t h em e s hs u b d i v i s i o no p t i m i z a t i o na l g o r i t h mi sf u r t h e rs u b d i v i d i n gt h em e s h a n dt h e nu s i n go f t h ec o n t r o lp o i n t si t e r a t e sa p p r o x i m a t i o no ft h ez e r o 1 e v e ls e ts u r f a c e e v e n t u a l l yw er e a l i z et h e s e a m l e s ss p l i c i n ga n das m o o t ht r a n s i t i o ns u r f a c e b e c a u s eo ft h eg e n e r a t i o no ft r a n s i t i o ns u r f a c e i ss u b j e c tt ot h ep o i n t sa r o u n dw h i c hi st h en e a r e r , t h el a r g e ri m p a c to nt h es u r f a c e b a s e do nt h i s c h a r a c t e r i s t i c ，w eg i v eaw a yt os p e e du pt h ei n t e r p o l a t i o no fs u r f a c e ，i np a r t i c u l a r , f o rt h e c o m p l e xm o d e la c c e l e r a t ew h i c hi st h em o r eo b v i o u s f i n a l l y , w ec o n c l u d et h et h e s i s t h em e t h o d sp r o p o s e di n t h i st h e s i s s t i l lh a v es o m e d e f i c i e n c i e s a n dw eg i v es o m es u g g e s t i o n sf o rf u r t h e ri m p r o v e m e n to ft h e s ew o r k s k e yw o r d s ：i m p l i c i tf u n c t i o n , b o o l e a no p e r a t i o n , m u l t i s c a l ec s r b f , d i s c r 6 t es u r f a c e f u s i o n , m e s h i n gb e t w e e nc o n t o u r s ，i n t e r p o l a t i o na c c e l e r a t ea l g o r i t h m 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：飒l 虱年日期：7 口o c | 年j 月? 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密匝 ( 请在以上相应方框内打“) 作者签名： 导师签名： 浙江i ：q k 大学硕七学位论文 第1 章绪论 1 1几何造型与三维模型表示 数字几何模型是物体的几何表示，足继声音、图像和视频之后的叉一数字媒体i ”，它 可以在数字设备卜进行显示，观察，评价，操作等。数字几何模型是三维计算机图形应用 的核心数据，所以数字几何处理的理论和方法一直是计算机圈形学研究的热点。每年 s i g g r a p h 会议约1 5 的论文与此有关。数字几何模型在影祝、游戏娱乐、工程设计、医学 可视化、模拟仿真都有广泛的应用。 几何模型表示方法多种多样，存在着各种不同的分类准则闭。一般常用的表示方法， 有基于实体( c o n s t r u c t i v es o l i dg e o m e t r yc s g ) 的表示方法和边界( b o t m d a r y r e p r e s e n t a t i o n ，b r e p ) 的表示方法。基于实体表示有利于布尔操作，形状变换等操作。基 于边界表示，描述形体的信息包括几何信息和拓扑信息，拓扑信息描述了点、边、面的连 接戈系，拓扑信息形成了边界袁示的“骨架”，几何信息如“骨架”j 一的“肌肉”。边界表 示有隐函数曲面法、参数曲面法、细分曲面法等，有些可以相t 转换。 的三维模型( b ) 阿格表示 “) 点表示“ 浙江业人学硕+ 学惶论文 慝 d q s p a t 绘制 e 椭瞰平均加权法绘制1 5 l 图i it 维模型的嵌示方式以及点模型绘制方式 通常基于实际绘制需求的不同，义可以分为基于点模型表示和基于网格模型表示。 近年来，随着三维扫描仪的普及及扫描技术的发展，使得点表示的模型得到了极大的发展 和应用。并且有些如火、水、雾等粒子不能用三维网格很好的表示，而点表j j 模型可以和 好的解决这个问题。当描述复杂的三维模型，特别是些细节部分，若用网格模型表示的 话可能需要大量的三角面片，这会导致绘制与计算的瓶颈而点模型在这些细节呈现上有 明显的优势。点模型常用的绘制方法有o s p l a t 方法，椭圆加权平均法同等。点模型研究 的内容包括几何修复、简化压缩、布尔运算、雕刻、自由形变等，在许多领域都得到了广 泛的研究和应用。 但是在i 维世界中嘲洛模型仍旧是最流行的表示方式。网持模型有如f 优点首先 阿格模型町以表示极大部分的物体，对于甲坦光滑的表面，比起点模型表示，反而网格表 示更具有优势。其次现在的显卡对网格绘制进行了优化加速，使其绘制速度效果更佳。 再者，对网格表示的模型的几何处理算法已经相当成熟，许多处理算法都得到了较好的应 j j 。 埘于二维模型的网格表示或者点表示，各有各的特点以及应用范围，如果交互使用能 够发挥各自的特点，起到优势互补。 1 2 几何模型融合 几何数据获取手段多种多样：在影视娱乐领域。几何数据往往源于艺术家的创造：在 医疗诊断领域，几何数掘常常束源于c t 断层扫描、核磁共振成像以及电子等技术取得的 医疗影像重建：在模拟仿真领域中，几何数捌则大多来自于对模拟对象实体的测量和构造。 2 浙江i ：_ k 太学硕十学位论文 三维激光扫描仪的快速发展，使得= 三维激光扫描技术成为获取几何数据的重要手段州。当 然还能从多幅二维同像重建中获取( i b m ，i m a g e - b a s e d m o d e l i n g ) 。 原始获取的数据一般滩以满足特定的需求，如游戏、电影里面存在的某蝗人物，怪物 不是现实世界中存在的。这时我们需要对现实世界获取的模型进行加工处理，如几何变形、 几何融合等。 在几何融合中，用多个不同的模型融合成一个所需的模型是一种快速的建模方法用。 一般而言，已存在的成熟的东西总是可靠的，从已存在的东西构造出复杂的东西或者现实 l r 不存在的东西，对于事物的藿用也是一种提高生产效率的表现。用“移花接木”米形容 几何融合是非常形象的，截取个事物我们所需要的部分，然后再截取另一个事物我们所 需要的部分，然后再把这两个所需要的部分进行融合，得到我们完全想要的事物，这是我 们对几何融合的。种通俗理解。它已经广泛使用于现实的三维游戏、电影特效，电视广告、 虚拟现实，如安徒生动画中的美人鱼、埃及神话中的人面狮身、中固鬼故事中的牛头马面， 都u ，以通过“移花接木”柬获得。 1 3隐函数简介 隐函数拟合方法就是用个零值函数集柬表示张曲面的方法。设i ( x 1 定义曲面s 若满足，( x ) = o ，则肖在曲面sh 。用隐函数表示的曲面，我们称其_ = i 隐式曲面。 x l f ( x ) 仉z e 集合在曲面内 ，( x ) = 0 ( x ) 0 ( x ) o 分别定义了两个半空白j - 它们分别表示整个空间被隐式曲面分为 两部分。若隐式曲面是个封闭曲面，则( x ) 0 。仃较小的话，插值表面会出 现小尖点及斑点，仃太大的话线性方程组的系数矩阵会变的不再稀疏，计算就比较耗时。 根据不同的连续性c 以及维数d ，这里假设盯= l ，给出不同的w e n d l a n d 基函数如下 表： 表2 1不同维数下的w e n d l a n d 基函数表 c ”c 2c 4c 6 d l - r ) + ( 1 一，) ：( 3 ，+ 1 ) ( 1 - r f + ( s r z + 5 ，+ 1 ) 扛3 l - r ) ：( 1 一，) ：( 4 ，+ 1 ) ( 1 - ，) ：( 3 5 r 2 + 1 8 广+ 3 ) ( 1 一，) 3 ( + 砰+ 和+ 1 ) 拈5 ( 1 - r ) ：( 1 - r f + ( 5 ，+ 1 ) ( 1 - r f + ( 1 6 r 2 + 7 r + 1 ) 薄板样条径向基函数由于其良好的视觉效果和大数据的稳定性，被广泛应用，但是其 是全局的，当采样数据点比较多时，线性方程组的系数矩阵几乎都是非零，求解比较耗时， 新江l 业人学硕t 学仲论文 并且任何一个采样点的改变都会影响其他插值点，所以任意采样点的变化都必须重新求解 方程组。 表2 - 2 紧支径向基函数与薄板样条径向基函数性能比较 薄板样条往向基函数紧立径向丝两数 建”a w m ! 辑牯o ( n 2 1o ( ”】。g ) 解a 样运算饿 。( 一，)。( ”) 内存消耗 0 h 单点误差影响全局 0 f n 局部 从表22 中可以看 ，紧支径向基函数的插值速度是很快的。 2 2基于多尺度的c s r b f 从上一节中，我们知道c s r b f 能使系数矩阵尽量稀疏，使求解速度比起已往的基函 数能极丈提高，并且总能保持系数矩阵正定对称，从而保证有解。由于有这两点明碌的优 势，被许多人广泛采用。但c s r b f 是基于局部的，所以从修复曲面能力而言还有所欠缺， 所以我们希望找到一种既插值速度较快，又能有较好的修复能力的方法，而多尺度c s r b f 方法i f 好满足我们的要求。我们知道利用基于局部的c s r b f 或基于全局r b f 快速多极法 m 】都能加快对离散点集的拟合速度。换句话说，基于仝局r b f 在曲面修补方法效果比较 出色，但此方法在插值近似时受到离散点的密度影响较大。o h t a k e 等1 人提出了一种多 尺度的c s r b f 方法，利用空间向下采样，从粗到细层次化架构离散点集。此方法集中了 局部和全局方法的优势，能够对缺省曲面进行修补，并速度优于快速多极法。 圈2 - 2 利用多尺度c s r b f 填充修补缺省部分 1 2 浙江工业大学硕士学位论文 2 2 1基于多尺度的c s r b f 单层插值 多尺度的径向基函数的定义： 下： 厂( x ) = ( x ) = ( x ) + 五 丸( 忙一只0 ) ( 2 6 ) 其中尸为离散点集，丸( ，- ) = ( ，仃) ，( ，) = ( 1 一r ) 4 ( 4 r + 1 ) w e n d l a n d 基函数。 对于每一个只p ，零水平集蜀( x ) = o 表示在忍周围p 的形状。岛( x ) 的具体定义如 假设p f 对应的法向量为吩，建立局部直角坐标系( “，w ) ，以b 为原点，平面( ”， ，) 垂 直于吩， i v 正方向与吩一致。用二次曲面来近似忍附近点p 的形状。 则 w = 乃( 甜，) - a u 2 + 2 b u v + c v 2 ( 2 - 7 ) 彳、b 、c 用最小二乘求得： ，；疙( 0 岛一尼叭一办( 哆，吩) ) 2 专曲 ( 2 8 ) 心，1 ：，_ ：，j i 乃p g i ( x ) = w - h ( u ，v ) 参数磊的确定，可以给定一点乃p ，则 ( 乃) = o = ( 乃) + 五】丸( 0 乃一只i ) z x , o 。- - - z g , ( p , ) o 驴 矿= 屯( 1 i 乃一只) 。 图2 - 3 a 、岛、h ( u ，1 ，) 的几何意义 1 3 ( 2 9 ) 浙江丁业人学硕十学位论文 2 2 2 基于多尺度的c s r b f 多层插值 c s r b f 插值的限制：特别在插值不规则的采样点时，修复能力以及填充能力有限。 插值时在边缘容易出现一些窄带。 作者提出的多尺度c s r b f 法刚好能克服上述的一些缺点，主要思想如下： 点的层次架构建立 p 1 ，p 2 ，= p 。先计算p 的包围盒，然后用八叉树递归划分成 八个子空间，对于包含点集p 的子空间，计算每一个子空间的中心、单位向量( 通过计算 平均向量，标准化得到) 。点集尸1 由八叉树首次划分包围盒得到。 递归定义插值函数： f ox ) = - 1 ，f ( x ) = 厂一( x ) + o ( x ) ，k = l ，2 ，m 。 ( 2 1 0 ) 其中f ( x ) = o 插值点集， 扩( x ) = 乏。 矿( x ) + 硝 略( 忙一i i ) ( 2 1 1 ) 碱e r - 基于多尺度的c s r b f 方法，能够比快速多极法提供更快速的拟合速度，更强的抗向 量噪声干扰，克服了基本c s r b f 方法不能很好修复曲面的情况。多尺度的c s r b f 方法 提供了众多优点，本章主要采用此方法插值、拟合隐式表面。 2 3对几种曲面融合方法的分析与研究 2 3 1 基于全局调和映射算法和基于局部调和映射算法 k a n a i 等【5 1 1 在1 9 9 9 年提出的基于全局调和映射的网格融合算法是一种比较实用的算 法，此后刘刚掣5 2 1 在k a n a i 等人的算法基础上提出的局部调和映射算法，对全局调和映射 算法的不足作了相应改进。k a n a i 等人的算法思想是根据m e t a m o r p h o s i s 思想形成的。此 思想基本处理过程分为两步：第一步，建立原始要融合网格面与目标网格面的一致性关系， 把原网格面的点与目标网格面的点建立一一映射关系；第二步，插值对应点产生一个光滑 过渡面。 给定两个三角网格模型m 1 和m 2 ，以及定义两个需要融合的子网格区域f 1 和，2 ， 一m 1 ，f 2 m 2 ，同时定义了卵1 ，卵2 为一和f 2 的边界，如图2 4 。 1 4 浙江】q k 学硕f 。学位论文 舭 0 三l翰型 “卜一词圈黔一】 厂影v 。 ( c )卿( 砷 翻2 4 基r 全局调和函数的网格融台框架图 c 。 基于争局调和映射的网格融合算注叮以大致分为4 步。 ( 1 ) 用户在原始网格村1 和m 2 上选取相同的网格点数用柬定义所需要融合的区域 一和f 2 ，它们表示网格上被选取的白区域。 ( 2 ) 通过算 杰( 对卵边界 二的点做旋转、甲移，缩放，变形) 使a 一与萨2 相匹 配。 ( 3 ) 通过调和映射参数化一和p ，得到一维空问i r ! 】多边形h 1 和圩2 ，台并h 1 和打2 得到h ，h 1 和2 分别保留了一和f 2 的拓扑结构。 ( 4 ) 通过反求f ，p 2 = m 2 一f 2 ，山于建立了两个融合区域刚格顶点之m 的对 应关系，通过控制函数f c f ( f u s i o nc o n t r o lf l m c t i o n ) 进行交互控制得到目标网 格m 。= f u p 2 。 k a n a i 算法的缺点：效率低，假设融合区域的网格顶点数为n 剥我们要近似求解4 月2 的线性方程组，若融合区域点比较多的时候就比较耗时。稳定性差，当网格顶点较多时， 容易产生奇异情况，包括。与2 重合，片1 的点位于h 2 边上等。拓扑限制，由于剪切的 一和f 2 必须同构与圆盘，这使得应用范酮得到了限制。 浙江l 。业人牛硕十学化论文 匹囊 。，w ( - )( c )伸( c )( 0 幽2 - 5 基j ：局部调和函数的喇格融合框架凹 对十k a n a i 等人提出算法的不足，刘刚等人提出了一种基于局部调和函数的时格融合 算法。由于在融合处我们只要考虑边界的密切缝合，对于剪切网格的细节要尽量保留，h 需要控制过渡区的局部光滑即可，所以提出了一种基于局部的调和映射网格融合算法。 作者做的两方面改进： ( 1 ) k a n a i 的全局算法是用户交互的拾取需融合部分的对应点，然后对每组点的相 邻点之f b j 分别用近似最短路径算法求得一条边界，该方法用户交互过多，提出 了种近似等距线算法。近似等距线算法用户只需选取一组点，并指定距离值， 然后系统根据用户所提供的信息在网格上等距线抽取。 口鹫o 逖口 图2 同构环形圆盘 ( 2 ) 把全局调和映射改为局部调和映射，拓扑同构从圆盘变为圆环。 ( a ) 牛头马身的融合 圈 7 在局部调丰映射算法完成的融台结果， 1 6 0 ) 茶杯柄与人头的融台 这两种方法都无法在全局调和映射r 完成i ”j 浙江业大学硕 学位论文 通过算法的改进，基于局部调和映射算法减少了计算量，降低了拓扑限制 2 32 基于水平集方法 水平集方法主要是从界面传播等研究领域中逐步发展起来的，它是处理封闭运动曲面 随时白j 演化过程中几何拓扑变化的有效计算工具沱的主要思想是将移动的界碰作为零水 平集嵌入高一维的水平集函数中。这样，闭超曲面的演化过程叮以得到水平集函数的演化 过程，而嵌入的闭超曲面总足零水平集，最终只要确定水平集函数的零水平集即可确定移 动界面的演化结果。 ( a ) w i a g 和c h j g o n 的c s g 操作( b ) 产生的梧皱 凹2 - 8 基r 水平集方法融合过程1 。i m u s e t h 等 4 9 人提出了一种基于水平集框架的曲而编辑方法把b l e n d i “g 、 s m o o t h i n g s h a r p e m n g 、p o i n ta t t r a c t i o ne m b o s s i n g 等操作信息都被封装到一系列速度函 数中，提供了一个简单、统一的框架。 作者给出的速度两数的定义： y ( x ) = 皿p ) c ( r ) g ( ，) ( 2 1 2 ) 其中乜( d ) 是一个取决下距离单位d 的基于距离的剪切函数，其中d 相对应卟儿何 结构g 。c ( ，) 是一个控制g ( ，) 对速度函数贡献的剪切函数。g ( ，) 足由源于水平集表面的 几何测量单位r ( 如曲率等) 决定的。 m u s c t h 等给出了一个分段函数p ( 卢) 柬分别定义q ( d ) 和c ( r ) 。 浙江工业大学硕士学位论文 尸( ) = 0 f o r p o 2 ，加0 洲( 2 - 1 3 ) 1 - 2 ( f l - 1 ) 2f o r o 5 a d d l e a f s i z e 0 a d d l e a f s i z e ( ) 如果节点是叶节点，则计算叶节点对应子立方体对角线的长度l ，o u n t ，s u m + = l ； 若不是叶节点，则调用自身c h i l d i - a d d l e a f s i z e 0 ，c h i l d i 为子节点。 ) 然后平均叶节点长度l = s u m c o u n t ； 多尺度的紧支径向基函数的插值过程就是求解方程组( 2 6 ) 式的蜀( x ) 及4 的过程， 我们为每个点只建立局部坐标系( ”，v ，w ) ，然后通过最小二乘法及s v d ( 奇异值分解法) 来计算构造的局部坐标系的二次曲面( x ) 的系数彳、b 、c ，二次曲面( x ) 用来描述 浙江- t 业大学硕士学位论文 在只附近的p 的形状，& ( x ) = w h ( u ， ，) 。名通过预处理双共轭梯度法 6 4 来求解，预处 理双共轭梯度法专门用来求解大型线性方程组。 3 4布尔运算 3 4 1 已往一些布尔运算 布尔运算我们可以归结为，设石= o 和五= 0 为两个隐式曲面，通过石和石等并、交、 差等布尔运算生成石。w y v i l l 等6 5 1 给出可以融合函数的极限形式定义隐式函数曲面的布 1 尔运算形式：正= ( 石”+ 刀) _ 。p a s k o 等删给出了一个包含布尔运算融合函数的一般形式： 五：( 石+ 五+ 口0 f 砺) 0 f i 虿，口【一1 ，1 】。当口= 一1 时，此式等价为交运算，当口= l 时，此式等价为并运算。a d a m s 等卿给出了一种内外测试算法( 3 1 ) 式来做布尔运算： 设彳和曰为基于s u r f e l s 的表示的基于点模型的集合，e 和品为彳和曰所覆盖点模型的表 面，圪和为邑和& 所包围的实体，而，是为s u r f e l ，岛邑，品。 f 彳邶= 焉+ 是i 焉穆膨嘟取奶桫嘲 a ib = 西+ 龟i 置在的内音匦在圪的内勰 ( 3 1 ) l 么一曰= 西+ 是i 焉召彬慨在圪的内胡 3 4 2 本文采用的布尔运算方式 本文在内外判别也是采用a d a m s 等( 3 - 1 ) 式的思想，但实现的算法主要结合了( 卜1 ) 式隐函数的思想，设髟和也为模型a 和模型b 的点集，厶( x ) = 0 和厶( x ) = o 定义了 模型彳和模型曰的两个隐式曲面，而一，x n ，六( ) o 表示模型b 在模型彳里面的部分，厶( 硝) o 亦然，布 尔运算可以表示为： 而+ 而i 无( 而) o 砀+ i 正( ) o ，厶( 而) m e s h g e o o p 进行模型配准。s c a l e 是对模型进行缩放，刻度x 、 y 、z 分别表示对模型的三个方向进行缩放。r o t a t e 模块可以选定朝x v 、yz 方 向旋转及旋转的幅度。m o v e 模块操作模型在i 个方向的平移幅度。 蹭3 1 3 模型配准 闰3 1 4 单层拟合 ( 4 ) 在e d i t - ) s i n g l ef i t t i n g 对模型进行插值，拟台，如图3 - 1 4 。 ( 5 ) 在b o o l o p e r a t i o n 菜单下分别进行“并交”“差”运算 3 4 浙江r 业人学硕士学位论文 薹薰巍 。”。引 一氏 瀹 馥 崩娥鞑辩 ( a )“并”运算( b ) 恐龙球 ”。= 。l 2 = 二二! i 口 o c ) 球恐龙 酗3 - 】5 实现的布尔操作 d ) “交”运肆 ( 6 ) 网格模型转化为点模型，利用f i l e - ) e x p o r tp w n ，提取网格模型拓扑点转化为点 模型p w n 格式。 浙江l 业大学硕1 一学位论空 鋈4 。 叠引。i 。1 ”1 ”! ! = i 二= 爹 慕二：一一一 沁 ( a ) f a c e 网格模7 n c o ) t e a p o t 网格模型 夕 ( c ) f a c e 点模型 ( d ) t e a p o t 点模型 圈3 1 6 网格模型转化为点模型 ( 7 ) 进一步的配准、布尔求“并” 浙江】业人学硕1 学 # 论文 x 移垮 刚3 1 7 点模型配准幽3 1 8 布尔“井”运算 ( 8 ) 对f 布尔求“并”后的模型，再一次插值拟合，并多边形化e d i t - - ) p o l y g o n i z c 圈3 1 9 多让形化结果 3 8本章小结 随着三维数据获取设备( 如三维扫描仪) 的普及和应用，获取的物体表面数据常以点 云数据的形式表示，因此点模型在逆向工程、数字娱乐造型领域有着重要应用。本章通过 由已有点模型来快速构建新的模型，提出和实现了种基丁多尺度c s r b f 的点模型布尔运 算方法。此方法实现思想简单，但腌着点模型数据量的增大，隐式化时间也会随之增加， 浙江t 业大学硕十学位论文 本章采用自适应八叉树结构来预划分空间及多尺度拟合，提高了搜索速度，从而加快计算 时间。并且把点模型的布尔运算思想应用到网格模型上，来进行网格模型的曲面融合。用 此融合方法易于实现，不需要考虑融合网格曲面间的拓扑映射关系，也不需要考虑融合时 目标网格边界与源网格边界的重合问题，但该方法若对网格模型进行曲面融合后不能保留 原始网格的结构。 浙江t 业大学硕+ 学位论文 第4 章离散曲面融合及其融合区域光滑过渡 4 1引言 中国神话中的龙，是古人崇拜大自然的能力，把各种图腾如骆头，蛇脖，鹿角，龟 眼，鱼鳞，虎掌，鹰爪，牛耳等组合出来的。西方神话中的狮鹫，也是鹰与狮子的 组合。安徒生故事中的美人鱼，也可以通过人身和鱼尾组合出来。若这些都是三维 模型的话，我们把这个组合技术称为融合技术。通过已有的模型，构造出现实不存 在的，想象出来的模型，这就是“重用 思想，进行“移花接木 。随着三维采样、 造型技术的不断发展，现有的模型已经相当丰富了，并且在现实设计中有些模型在 真实世界是不存在的，需要靠技术制作人员的丰富想象，“重用”思想为艺术家等技 术人员提供了极大的方便，通过模型融合技术可以为他们从已有的模型构造出复杂 的模型，可以极大的提高效率。 对于模型曲面的融合方法，许多学者作了详细的研究，我们已经在1 5 节进行 了基本介绍。我们在2 3 节对现有的方法作了归类并进行分析，主要存在着两方面 缺点。首先许多方法都受到拓扑结构的限制，如k a n a i 等【5 l 】基于全局调和映射的算 法需要融合目标的拓扑