（应用数学专业论文）t样条实现封闭曲面重建.pdf

n 枷i n gu 1 1 i v e r s i t ) ro f a e r o n a u t i c sa n da s t r o n a u t i c s t h eg r a d _ u a t es c h 0 0 1 c 0 1 l e g eo fs c i e n c e c l o s e ds u r f a c er e c o n s t r u c t i o nb a s e d0 n t s p l i n es u r f a c e s a 。i h e s l sm a p p l i e dm a t h e m a t i c s b y c h e n gz e i i l i n g a d 听s e db y p r o t 趾gy u e h o n g s u b n l i t t e di np 枷a lf u l f i l l n l e r l t o ft h er e q u i r e m e n t s f o rm e d e g r e eo f m a s t e ro fs c i e n c e m a r c h ，2 0 1 0 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本承诺书) 作者签名：旌瑷链 日 期： 窆f ! 2 。g 南京航空航天大学硕士学位论文 摘要 本文以s e d e r b e 曙tw 等人提出的t - 样条作为逼近工具，对三角网格曲面到光滑曲面的重 建进行研究主要研究结果如下： ( 1 ) 实现简单拓扑三角网格曲面的重建运用l s c m 参数化方法把三角网格曲面同胚映射 到参数化平面上，利用四叉树自动生成t 网格，由g c v 方法确定光顺项系数，运用最小二乘 法求得t - 样条曲面的控制顶点，从而重建出达到任意指定精度的曲面 ( 2 ) 研究隐式t - 样条曲面表达式中混合函数的代数性质通过将隐式t - 样条曲面3 d 控制 网格和相应的隐式b 样条曲面控制网格相比较，按三个坐标方向缺失点的可能情况，寻找发生 变化的混合函数，利用b 样条的细分性质，证明了隐式t - 样条混合函数的线性无关性 ( 3 ) 对于复杂拓扑三角网格曲面提出一种新的隐式t - 样条曲面重建算法首先根据给定的 采样点确定三维t - 网格，然后，基于隐式t 样条曲面建立目标函数，其中利用偏移点集来控制 曲面的形状，运用g c v 方法确定最优的光顺项系数，将曲面重建问题转化为最优化问题，通 过求解方程组实现曲面重建在误差较大的区域局部插入控制顶点，使得重建曲面达到指定的 精度本文算法和童伟华等提出的采用法向偏差模来控制曲面形状的方法不同，由于对其中的 曲面光滑性的苛刻不必要的约束条件进行了合理的减弱，同时又选取了最优的光顺项系数，所 以应用范围更广且重建精度更高 ( 4 ) 在s u 2 l ls t u d i o 平台下以c h 语言为基础，利用本文算法实现了人脸，动物，机械零 件等复杂曲面的重建，结果也表明：曲面重建速度快，仿真结果逼真 关键词：隐式曲面，曲面重建，平方逼近，代数性质，t - 样条，三维t - 网格，光顺，g ( n 方法 样条实现封闭曲面重建 a b s t r a c t h l 仳sp a p e r ，m er e c 0 璐缸u c 6 0 no f 锄o o ms u r f i a c e s 丘o ms u c hm e s hm o d c l sw i t l lt 二s p l i i l e 弱柚 a p p r o x i m a t er 印r e s e n t a t i o ni ss t u d i e d t h em a i na c k e v e m 即t sa 咒硒f 0 1 1 0 w s ： ( 1 ) s m o o t l ls u r f 配e s 粥i i l gt - s p l i l l e 嬲aa p p r o x i i i l a t er e p r c s e n t a t i o na r er e c o 地t f l j c t c d 丘锄 t r i 锄鲥盯m e s hs 耐i a c e s a f i c r m a p p 吨m e3 d t r i 锄g u l a r m e s h t 0a 2 d d o m 痂谢t l l l s c m ，w c l l s e a 础e t os 删v i d em e2 dd o l i l a i l l i n t o f o l l r q 似l 瑚t s 僦u r s i v e l y - t h 饥m ec o m 驴n 幽gt r s h i s c o 硒饥l c t e d b y 哪：i i l gl e 罄ts q 岫r ea p p x 疵眦i o nw ec 锄g e tt l l ec o n t r o lp o i n _ t so fm et - s p l i i l es u r f k e 趾d 觚s h o u r a l 9 0 r i t h l 丑w i l t l l e l o c a l r e 缸e 删m t o f t - s p l i r l c w ec 锄删妞位a p p r 0 删o n 锄_ 0 r 诵吐l i i lm ep r e s c r i b e de 玎o rt o l e m c e ( 2 ) t h ep r o p e f t i e so fi i l l p l i c i tt - s p l i l l eb l e i l d i l l gf l m c t i o 璐a r cs t u d i e d b ym e 锄so ft l l ep r o p e n i e so f m e3 dh m s h 孤dm cc o r r e s p o n d i i l gc o n 仃0 l 鲥do f i m p l i c i tb 却l 岫唧饥e ，w e p r o v e 也a ta l lt l l o s e i 甲l i c i tt - s p l i i ：i eb l e n d i i l g 劬c t i o i l sa r ea l w a y sl i l l e 砌y 协d 印e n d e n t ( 3 ) a n “g 硎t l l mf o rr e c o i l s m l c t i n gs m o o t hs u r f k e s 丘d mc o m p l i c a t e dt r i a n g u l a rm e s hs 眦f a c e sw 雒 p 他s e n tb yu s i l l gi r 印l i c i tt - s p l i i l er e p 佗s e n t a t i o ni i lt h i sp a p e r - t h es h a p e so ft l l e 鲫k e sa r ec o n t r o l l e d b ya d d i l l go 尽s u r f a c ep o i i l t s ho l l r l u t i o i l w ef i r s tc 0 i l s 缸u c t3 dt - m e s h 舶ms 锄p l 抽gp o 证t s 1 1 l e n a no b j e c t i v em n c t i o ni si i l 廿d d u c e db a s e d0 ni m p l i c i tt - s p l i i l e a f i e rl l s m gt h eg c vm e m o dt oc l l o o s e t t l e 0 p t i m a lf a i 玎1 e s sp a r a m e t e r ，w ec a ng e tt l l e 咖l i c i tt - s p l i n es u r f a c eb yu s i i l gl e 笛ts q u a r e 雒l p r o x i l 】1 a t i o n a 盘e rp 晌肋i 1 1 9l o c a lh o ti 璐硎o n ，w ec 锄m a k em ea p p r o x i l i 谢o ne 玎0 r 、历m i i lt l l e p r e s c n b e de o rt o l e r a n c e ( 4 ) 1 h ep r o g r a m sf o ra l lo f m ea l g o r i m 嬲i nt l l i sp 印盯i s 训t t i i lc + + 1 a 1 1 9 l l a g e0 nt h e s u a l s t u d i op l a t f o m la n dm e s hs u m c e ss u c h 勰孤妇i sa r e 咒c o i l 曲n l c t e d k e y w o r d s ：i i i l p l i c i ts u 托配e s ，s u r f i a c er e c o l l s m l c t i o ml e a s ts q u a a p p r o x i i i l a t i o n ，a l g e b m i cp r o p e ：m e s ， t - s p l i i l e s ，3 d1 m e s h ，f a i m e s s ，( vm e m o d i i 南京航空航天大学硕士学位论文 目录 第一章绪论1 1 1 研究背景1 1 2t - 样条曲面理论基础3 1 2 1 节点区间3 1 2 2p b 样条曲面3 1 2 3t - 样条曲面4 1 3g c v 方法4 1 4 隐式曲面重建及其误差度量5 1 5 隐式曲面绘制以及移动立方体法6 1 6 本文主要内容和结构安排7 第二章简单拓扑三角网格曲面重建9 2 1 曲面重建算法概述9 2 2 三角网格曲面的参数化9 2 3t - 网格的构造1 0 2 4 曲面拟合数学模型的建立1 2 2 5t 样条曲面的局部修正1 4 2 6 曲面重建实例1 4 第三章隐式t - 样条曲面及其基底性质研究1 8 3 1 三维t - 网格及隐式t - 样条曲面1 8 3 2b 样条基函数加细公式1 9 3 3 混合函数线性无关的证明2 0 3 3 1 沿一个参数方向缺失一点的情形2 0 3 3 2 沿一个参数方向缺失若干点的情形2 3 3 3 3 沿两个参数方向缺失若干点的情形2 5 3 3 4 沿三个参数方向缺失若干点的情形2 7 第四章复杂拓扑三角网格曲面重建2 8 4 1 曲面重建算法概述2 8 4 2 三维t 网格的构造2 8 4 3 曲面重建模型的建立3 0 4 4 隐式t - 样条曲面的局部修正3 3 4 5 曲面重建实例3 3 第五章总结与展望3 8 i i i t 样条实现封闭曲面重建 5 1 全文总结3 8 5 2 未来工作展望3 8 参考文献3 9 致谢4 2 攻读学位期间的研究成果及发表的学术论文4 3 i v 南京航空航天大学硕士学位论文 图表清单 图1 1 节点区间3 图1 2 体素顶点不同取值组合对应的曲面的三角化7 图2 1三角网格曲面的参数化。l o 图2 2t 网格的生成1 2 图2 3p 1 龃es p h e 陀模型的重建1 5 图2 4m 锄e q u i i l 模型的重建1 6 图2 5n e f e n i t i 模型的重建。1 7 图3 1三维t - 网格及t 节点1 8 图3 2t - 网格和相应的b 一网格一2 0 图3 3 沿一个参数方向缺失一点的情况。2 1 图3 4 沿一个参数方向缺失若干点的情况2 3 图3 5 两个参数方向均缺若干个点2 5 图4 1 三维t - 网格的构造。2 9 图4 2e i 曲t 网格模型的重建。3 3 图4 1 3e g e a 网格模型重建3 4 图4 4r d c k 盱网格模型重建3 5 图4 5s q u i r r e l 网格模型重建3 6 图4 6g e 肌s 网格模型重建3 7 表4 1隐式曲面重建数据比较。3 4 表4 2 相关统计数据3 7 v 南京航空航天大学硕士学位论文 第一章绪论 1 1 研究背景 随着快速、准确的三维数字化扫描设备( 如激光扫描仪，计算机辅助断层扫描仪，接触式探 测扫描仪) 的不断涌现，获取描述物体表面细节的网格曲面已经变得越来越容易由于网格曲面 表示方法的简单性和普遍适用性，网格曲面成为了3 d 数字媒体的主要表示形式但是其线性分 片的逼近特性使得在刻画几何形体表面复杂细节时需要大量的基本多边形，这给重建曲面的分 析、计算等处理带来了诸多困难，也不适合光滑性要求较高的应用场合因此，由网格曲面到光 滑曲面的重建就成为了一个非常重要的问题曲面重建技术被广泛应用于计算机辅助几何设计、 计算机图形学、医学图像处理、计算机视觉等众多领域 m 瓜b s ( n o n - u i l i f o 肋r a t i o n a lb s p l i i l e s ) 方法已有大量的理论和应用研究成果【1 1 传统 的m 爪b s 曲面控制网格的顶点需要整行整列规则摆放，使得很多控制顶点仅仅是为了保持控制 网格的拓扑形状而不携带任何的几何信息大量的冗余控制顶点给后续的处理带来了很多不 便对曲面进行局部修正时，由于控制网格的拓扑限制，为了插入一个控制顶点必须要插入成排 的控制顶点，难以实现真正意义上的局部修正多张曲面合并时也由于控制网格拓扑限制而难以 操作 s e d e r b e r gtw 【2 】等人于2 0 0 3 年提出了t - 样条曲面t - 样条曲面是带有t - 节点的m 瓜b s 曲 面t - 节点的出现，使得曲面的控制网格线不必再全部贯穿，从而t - 样条曲面可以大量地减少控 制顶点的冗余，高效地实现真正意义上的局部细化同时，若将两张b 样条曲面进行拼接 ( 刀= o ，1 ，2 ) ，只需将控制网格对应边界附近的刀+ l 列进行合并此外，t - 样条还是一种p b 样条， 即除了奇异点之外，每个控制顶点都有一个与之对应的基函数因此，t - 样条曲面在非奇异点处 有统一的表达式，有利于曲面的分析和处理 近年来，关于t - 样条技术的研究较为活跃，已有相当多的文献给出了t - 样条理论方面和应 用方面的研究s e d e r b e 毽tw 【”j 等提出了t - 样条控制点简化与局部细分算法，适合于更一般 的拓扑结构，容易实现不同节点序列的张量积b 一样条曲面片光顺拼接d e n gj i 锄s o n g 【5 】等利 用b 网方法给出了当光顺度小于样条函数次数的一半时t - 样条函数空间的维数公式该维数公 式只与t - 网格的拓扑性质有关，但是当光顺度接近次数时维数公式并未给出l ic h 裔啪【6 】等 利用光顺余因子方法给出了t 样条函数空间的维数公式，但仍然有限制条件张明等【7 】证明了 双三次t 样条混合函数的线性无关性所有这些t 样条基的线性无关性和t - 样条空间的维数证 明，完善了t 样条的理论框架，为t - 样条曲面的应用提供了可靠的理论依据文献 8 】给出了利 用t 样条拟合z 加a p 数据点的方法，其主要应用于净m a p 等拓扑简单的情形该方法给出的初 l b 样条实现封闭曲面重建 始t 网格曲面非常粗糙，经过若干步的迭代后对初始网格进行了加细，这样要达到一定的精度 就可能需要多次的迭代，非常消耗资源文献【9 】提出了一种三角网格的t - 样条曲面重建算法， 但是该方法只能实现简单拓扑三角网格曲面的重建 尽管以m 爪b s 曲面为代表的参数曲面具有几何不变性，易于分片表示，易于离散，计算 南京航空航天大学硕士学位论文 1 2t - 样条曲面理论基础 本节详细介绍二元t - 样条曲面：带有t - 结点的非均匀有理b 样条曲面考虑到双三次 m 瓜b s 曲面的广泛适用性，讨论集中在双三次t - 样条曲面上双三次t 样条曲面在没有重节 点的情况下是c 2 连续的下面介绍t - 样条曲面的基本理论 1 2 1 节点区间 对于三次b 样条曲线，控制多边形的每条边都对应一段曲线段节点区间就是控制多边形 的每条边所对应的非负数节点区间主要用来传递节点信息图1 1 所示是一条三次b 样条曲 线，节点向量为【1 ，2 ，3 4 ，6 ，9 ，i o ，l l 】，控制多边形每条边上的盔就是对应的节点区间每个节点 区间都是节点矢量中两相邻节点的差分 对于非周期的曲线，在首末端点处各添加一条虚边，该边所带的非负数就是首末节点区间 ( 如图中的以，和以) 控制多边形的非首末边所对应的节点区间表示该边所对应的曲线段的参 数长度 对于曲线的节点向量来说，所有节点可以同时加上一个常量而不改变该曲线的节点区间因 此，当我们已知节点区间想要推出其节点向量时可以随意选取节点向量的初始值 d 产1 i ： d 与= 1 ? 一- 1 2 2p b 样条曲面 图1 1 节点区间 2 张量积b 样条曲面的控制顶点呈矩形网格分布，称之为基于网格的b 样条曲面这种性质 给张量积b 样条曲面带来了其他类型曲面所不具备的优势，但同时对曲面设计也是一个约 束因此，那些基于点的b 样条曲面，亦即p b 样条曲面，受到越来越广泛的关注p b 一样条 里面没有控制网格的概念，控制项点之间无拓扑连接关系，每个控制顶点有一个相对应的混合 函数 定义1 1 以p ，尺3 ，f = l ，2 ，以为控制顶点的p b 一样条曲面p ( s ，f ) 为： 3 b 样条实现封闭曲面重建 p ( s ，f ) = 至竹色( j ，f ) l = l ，( s ，f ) d ， ( 1 1 ) 互岛( s ，f ) 其中b ( s ，f ) = 醒( s ) 心( f ) 为混合函数，三o ) ，心o ) 分别为定义在节点向量 s ，= 【屯，屯，屯，屯】，= 【气，乞，气，气】上的三次b - 样条基函数 由此，为了描述一个p b 一样条曲面，必须知道一系列控制顶点以及与每个控制顶点对应的 节点向量 1 2 3t - 样条曲面 定义1 2 称矩形网格中s 坐标为常量的线段为s 边，f 坐标为常量的线段为f 边 定义1 3 在矩形网格的内部项点处，若有两条s 边，一条f - 边或者两条扣边，一条s 一边通过 该顶点，则称这样的内部顶点为t - 节点 定义1 4 含有t - 节点的矩形网格称之为t - 网格 t - 节点是t - 网和b 一网的本质差别若t - 网中没有t 节点，则退化为b 网 t - 网格的边和对应的节点区间需满足以下规则： 规则lt - 网格的任意一个面中，对边的节点间距之和必须相等 规则2t - 网格中，位于一个面的一条边上的t 节点，若可以与对边的t - 节点相连而不违 背规则1 ，那该边就包含于t - 网格中 定义1 5 定义在t - 网上的p b 样条曲面称之为t - 样条曲面 t - 样条曲面控制顶点对应的节点向量可以从t - 网格中得到 设所( 黾，气) 为t 网格中的控 制顶点，考虑空间中的射线r ) = ( 屯+ 口，气) ，口 o ，屯，屯是与该射线相交的s - 边中最靠近 黾的两条j 边的s 坐标，其它节点值的选取方法与此相同 利用t - 样条曲面控制网格和对应的b 样条曲面控制网格之间的关系，可以证明2 3 】 定理1 1t - 样条曲面的基底性质t - 样条曲面每个控制顶点对应的混合函数都可以表示为一 些彼此不完全重合的b 样条曲面基函数的线性组合，因此它们彼此线性无关，构成一组基函数 1 3g c v 方法 考虑拟合模型 ”= 厂( ) + 毛， o ，l 】，f = 1 ，2 ，刀， ( 1 2 ) 其中 岛( o ，矿) ，f = 1 ，2 ，l ；厂呢= 矿： ，厂纠绝懒e 厂”切 o 为光顺项系数将厶写为如下矩阵形式 称彳( 元) 为影响矩阵 l 厶( 厶( 乞 & 。 ( y l l ：彳( 允) l 誓 l ： l 咒 我们用均方差( 1 5 ) 来度量拟合的效果： 肌) = 丢喜( 讹) 训2 则最优的旯是使得尺( 兄) 取最小值时候的允值 o c v 方法提供了一种估计最优旯的途径定义g c v 函数矿( 旯) 如下： y ( 兄) ：! | i ( i 一么( 旯) ) y0 2 三7 妇钟( i 一彳( 旯) ) 】z ， ，l刀 ( 1 3 ) ( 1 4 ) ( 1 5 ) ( 1 6 ) 其中l j | l 为r “空间的e u c l i d 范数，i 为r 的单位矩阵，y = ( 乃，兑，咒) r ，胁( m ) 为矩 阵m 的迹o c v 定理p q 指出，使得y ( 旯) 取得最小值的旯是最优的光顺项系数的一个估计 1 4 隐式曲面重建及其误差度量 设p = 佃f ( ，；，墨，) ) ：l 是采样点集，隐式曲面重建即要寻找隐函数厂：qc 尺3 一r ，使得： 厂( ，岛，) = o ，f = l ，2 ，以记z ( 厂) = ( 工，y ，z ) qc 尺3i 厂( x ，y ，z ) = o ) ，贝up ( 工，y ，z ) 到 z ( 厂) 的距离定义为： 艿( p ，z ( 朋2q 现) 扯q i f ) ( 1 7 ) 其中i | i 为r 3 中的e u c l i d 范数称( 1 7 ) 表示的距离为e u c l i d 距离 设q z ( 厂) 为z ( 厂) 中到p 的e u c l i d 距离最近的点，由t a y l o r 展式得： 厂( q ) = 厂( p ) + w ( p ) r ( q p ) + d 训q p i l 2 ) ( 1 8 ) 由三角不等式和c 孤c h y - s c h 、a r z 不等式，有： 5 b 样条实现封闭曲面重建 帅挑( p ) + y q ) r ，眇h w ( p ) r ( q p ) l ( 1 9 ) i 厂( p ) i - 1 1 w ( p ) 圳q p 8 驰砌) 2 踹 ( 1 1 0 ) 称( 1 1 0 ) 表示的距离为t a u b i l l 距离m 3 8 1 定理1 2 伫刀设厂：qcr 3 一r ，p o z ( 厂) 为正则点，厂在p o 附近邻域内二阶导数连续， w 为z ( 厂) 在p o 处的单位法向量，p f = p o + 舸，f r ，则有 1 i m 垒皿兰塑2 ：1( 1 1 1 ) h o 万 ，z ( ) ) 因此，我们可以用t a u b i i l 距离来度量曲面的拟合误差 1 5 隐式曲面绘制以及移动立方体法 隐式曲面的绘制算法有很多种根据绘制方式不同，可以将其归类为：光线跟踪和多边形 光线跟踪算法直接从隐式曲面方程出发，通过计算光线和隐式曲面的交点进行绘制光线 跟踪法可以绘制出高质量的图像，但是由于要计算每根光线与隐式函数的交点，因此，光线跟 踪算法的共同缺点是绘制速度非常慢此外，光线跟踪算法还包括阴影检测和反射、折射光线 由于大多数的图形加速卡和商业动画软件包都支持高性能的、基于多边形的绘制，因此， 隐式曲面多边形化成为隐式曲面绘制的另一种方法通过对隐式曲面采样，多边形化方法可以 为该曲面生成一个多边形网格模型通过隐式曲面的多边形化，我们可以把隐式曲面的定义从 曲面的拓扑和几何复杂性上分离出来一般来说，隐式曲面的多边形化算法大大超过光线跟踪 法的绘制速度此外，隐式曲面的多边形化处理通常是被当做一个黑盒子处理，亦即，更复杂 的隐式曲面并不需要特别的多边形化算法 移动立方体法p 9 1 是最常用的多边形化隐式曲面的方法首先将空间剖分为立方体体素单 元，给体素的各个顶点赋值计算隐式曲面在顶点处的值，若大于( 等于) o ，则定义该顶点位 于曲面之外，将该顶点对应的值赋为o ：若小于0 ，则定义该顶点位于曲面之内，将该顶点对应 的值赋为1 由于每个体素有8 个顶点，每个顶点有2 种状态，因此共有2 8 种组合状态根据 互补对称性，即体素的顶点值置反后不变，则2 5 6 种构型可以简化为1 2 8 种再根据旋转对称 6 南京航空航天大学硕士学位论文 留够印够 图1 2 体素顶点不同取值组合对应的曲面的三角化 确定体素内三角剖分模式后，就要计算三角片顶点位置使用线性插值计算曲面与体素边 的交点对于体素的某条边，若它的两个端点v ( 玉，m ，z 1 ) ，v 2 ( 屯，咒，z 2 ) 对应的值分别为。和 l ，那么曲面必定与该棱边相交，交点v ( z ，y ，z ) 可以通过公式( 1 1 2 ) 计算： 工2 五+ 了揣( 屯一 ) y 训鼎( 儿训 n 1 2 ) z = z l + 了揣( z z z 1 ) 其中，厂o ，y ，z ) 为隐式曲面的方程求出曲面和体素的交点后，就可以根据体素对应的三角 剖分模式，对该体素内的曲面三角化 1 6 本文主要内容和结构安排 本文根据网格曲面造型技术的最新进展，结合t - 样条这一最新的曲面表示工具，研究网格 曲面到光滑l 样条曲面的重建问题 t 样条实现封闭曲面重建 本文主要研究内容如下： 第一章介绍课题的研究背景，预备知识，论文的结构和研究内容等 第二章对于简单拓扑的网格曲面，实现了自适应的t - 样条曲面的重建，并和相应的b 一样 条曲面进行了比较对于输入的三角网格曲面，将其同胚映射到二维参数平面上，利用四叉树 对其剖分生成二维t - 网格，确定每条网格边对应的节点区间以及每个控制顶点对应的节点向量， 基于t - 样条曲面建立目标函数表达式，由g c v 方法确定光顺项系数，使用最小二乘法求解得 到控制顶点坐标从而得到重建曲面，并在误差较大的区域插入t - 网格控制顶点，进行t - 样条的 局部修正，以使得重建曲面和原始网格曲面的误差达到指定的精度 第三章研究了隐式t - 样条曲面表达式中混合函数的性质通过将隐式t - 样条曲面控制网 格和相应的隐式b 样条曲面控制网格相比较，寻找发生变化的混合函数通过将这些发生变化 的混合函数写成不完全重合的b 样条基函数的线性组合的形式，简单直观地证明了混合函数的 线性无关性 第四章对于复杂拓扑的网格曲面，提出了一种新的自适应的基于隐式t - 样条曲面的重建算 法和文献【3 3 】中采用法向偏差来控制曲面形状不同，文中将采用偏移点集来控制曲面的形状， 同时增加了。吖方法来自动选取最优的光顺项系数对于输入的三角网格曲面，利用八叉树 对其剖分以生成三维t - 网格，确定每条网格边对应的节点区间以及每个控制项点对应的节点向 量，基于隐式t 样条曲面建立目标函数表达式，通过g c v 方法选取最优的光顺项系数，使用 最小二乘法求解的控制顶点对应的系数从而得到重建曲面在误差较大的区域通过插入控制顶 点，进行t - 样条的局部修正，使得重建曲面和原始网格曲面之间的误差达到任意指定的精度 第五章总结本文的研究工作，提出进一步研究的问题和今后努力的方向 8 南京航空航天大学硕士学位论文 第二章简单拓扑三角网格曲面重建 本章详细介绍简单拓扑三角网格的t - 样条曲面重建由于t 节点的存在，相对于b 一样条曲 面而言，t 样条曲面大大减少了控制顶点的数量，从而不但使得处理时运算量更小，而且避免 了多余的控制顶点所带来的褶皱曲面的重建过程是自适应的，可以不断地插入控制顶点以达 到任意指定的精度 2 1 曲面重建算法概述 本节首先给出曲面重建算法的总体步骤，后面予以详细描述 算法2 1 简单拓扑三角网格的t - 样条曲面重建 输入三角网格曲面品= y ，e ，明，其中y = p l ，p 2 ，n ) 为顶点集，e = e ，e 2 ，e j 为边集， r = t l ，t 2 ，t 。) 为三角面片集 输出t - 样条曲面厂 ，d 算法步骤 ( 1 ) 将三角网格曲面品= 矿，e ，刀参数化到二维参数平面 ( 2 ) 利用四叉树对参数平面上的参数点集进行划分，从而生成二维t - 网格给t - 网格中 的每条边赋予节点区间，根据t - 网格的拓扑获取每个控制顶点对应的节点向量，从而得到每个 控制顶点对应的基函数 ( 3 ) 建立优化模型，通过最小二乘法解得t - 样条曲面的控制顶点 ( 4 ) 检验上面得到的t - 样条曲面是否满足精度要求，若达不到精度要求，则在误差较大 的区域通过局部插入控制顶点来对t - 网格进行局部修正，然后返回上一步直到所有区域均达到 了精度要求 2 2 三角网格曲面的参数化 三角网格曲面的参数化是指参数区域与3 d 网格曲面之间的一一映射关系参数区域可以 是平面区域、球面或多面体等对于参数域为平面的三角网格参数化可以归结为如下问题：给 定一个三角网格曲面品= y ，e ，刀和一个二维参数域q ，寻求一个参数域q 上的点到网格曲 面品上的点的一一映射厂，如图2 1 所示，使得参数域上的网格与原始网格拓扑同构，并在保 证参数域上所有三角片之间不相互重叠的同时，谋求某种与原始网格之间几何度量的变形最小 化三角网格曲面的参数化可以将一些对三维网格曲面的操作转换为对平面网格的操作，减少 了操作的复杂度，是曲面重建、纹理映射等操作的重要环节 9 t 样条实现封闭曲面重建 图2 1 三角网格曲面的参数化 目前已经有大量的参数化技术，其中，l s c m 【柏1 所具有的既保角又保面积的性质能够很好 地满足曲面重建的要求 对三角网格曲面品= y ，e ，丁】的任一三角形建立局部坐标，其顶点的局部坐标为 互= ( 墨，乃) ，f = 1 ，2 ，3 设s 为三角网格曲面所在的参数曲面方程，即有= s ( 吨，坼) ，则s 的逆映射u ：( 工，y ，z ) 一 ，1 ，0 ) 在每个三角面片上满足c 跚c h y 一黜e i i 埘m 等式： 箜一f 箜：o 或型+ f 型：o ( 2 1 ) 抛加出 砂 l s c m 参数化方法定义如下目标映射u 的保角能量函数孝以最小化角度扭曲： 乞= ! i 掣+ ，警1 2 班， 住2 ， o 嬲 哕 其中f 为三角网格曲面中一个三角面片最终可写为： ( z 2 一z 1 ) ( 一u ) = ( z 3 一z 1 ) ( 一u ) ， ( 2 3 ) 其中= “j + 以为对应点乙( ，= 1 ，2 ，3 ) 的参数值的一个线性方程 将所有三角形上的能量相加，所得的最终能量方程为： 乞= 乞( 咖丁 ( 2 4 ) 通过预处理的共轭梯度法可以很快地求解( 2 4 ) 表示的超定方程组，从而实现三角网格曲 面的参数化 2 3t - 网格的构造 t - 样条是定义在t - 网格上的p b 样条，每个控制顶点对应的混合函数都是从t - 网格中获取 的，因此t - 网格的构造是t - 样条曲面重建的关键 本章t - 网格是根据参数化到二维参数平面上的三角网格构 1 0 南京航空航天大学硕士学位论文 论上t - 网格的构造并无约束，只要控制顶点满足一定的拓扑关系，同时边满足1 2 3 节中的相 应规则即可为了充分描述原曲面的几何特征，提高曲面重建的质量和减少资源消耗，在采样 点密集的地方需要插入更多的控制顶点本文利用四叉树根据参数化的三角网格自动生成t - 网 格 m | | l l l l l l l | | | | l l l | l l l | l | l l | | | i | | l l | l | l l l l l 殴义拣l | | l l l l l l l l l l l l | l l l l l l | l | l l | | | l | | l l l l l l l l l | | | l | | i l l l l | | l l l l l | l | c l a s sc q u a 幽陀e p d v a t e ： b 0 0 lmb s u b d i v i d e d ：是否被细分 d o u b l emw i d t l l ：矩形的宽度 d o u b l e mi 肋g t t l ；矩形的长度 c p o i n t emv c t e r ：矩形的中心 缸mp o m c 0 u 嗽矩形内包含的数据点数目 c p o i n t e 搴mp p o 缸s ；矩形内包含的数据点集 c q u a d 骶e 宰i h _ p q 岫慨e n o d e s 【4 】；四个子节点 c q u a d 卸e 幸m _ p q 腑d 能e n o d e ；父节点 ) ： 汹l | | | | | l l | l l | | | l | | l | | l l | l l l | | | l l | | | | l | | l l | | l l | | l | | 融ji 镀| | | l | | | | | | l l | | l l | | l | | | l m | | | i l | | l l | | l l l | l | | l | | | l l | | | l | | | | l | l | 定义一个阈值，z 。，表示每个矩形内允许包含的最大的点数对于某个矩形，若里面包含的 数据点大于指定的咒。，则对其细分，然后对其每个子结点( 也即小矩形) 做同样的处理，直到所 有矩形里面包含的点均不大于初始矩形为包含数据点集的最小矩形 图2 2 ( a ) 为舀r l 白c e 网格模型，7 6 3 个采样点，1 4 8 2 个三角片，图2 2 ( b ) 为l s c m 方法的 参数化结果， 图2 2 ( c ) 为根据参数平面上的三角网格构造的t - 网格，图2 2 ( d ) 为对应b 一网格 ( a ) 帅c e 网格模型 ( b ) l s c m 参数化 样条实现封闭曲面重建 ( c ) t - 网格 图2 2t 网格的生成 ( d ) b 网格 构可以 ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) 南京航空航天大学硕士学位论文 解方程组形r 啦= 形r p ，矩阵肜= ( 。f ) 的元素为k 。f = 忍 i ，吃) 再加上光顺项，有： ( 形r 形+ 五( 吃既+ 2 嘭+ 嘭) ) q = 形r 尸， ( 2 9 ) 其中既，既的元素( ) 分别为掣，掣，掣 光顺项系数a 可以使用g ( n 方法来自动选取由( 2 9 ) 可以得到 q = ( 形r 形+ 元( 磁既+ 2 蝶+ 嘭既) ) _ 1 矿r p ( 2 1 0 ) 又魄“，m ) ，五他，吃) ，厶心，”1 = 阳= 职矿形+ 似屹虼+ 2 嘭+ 磁”q 矿尸 由此可以得到影响矩阵彳( 旯) ： 彳( 兄) = 形( 矿形+ 允( 吮既+ 2 蝶+ 蝶) ) 1 形r ( 2 1 1 ) 求得影响矩阵后，本文使用经典的b r e n t 方法【4 u 来寻找g c v 函数的极小值点通过取试探 点使得包含极小值点的区间不断缩短，当区间长度小到一定程度时，区间上各点的函数值均接 近极小值，任意一点均可作为极小值点的近似具体算法如下： 算法2 2 极小值点求取 符号约定0 ，6 ) ：去掉对应的离极小值点最远的点后得到的新的包含极小值点的区间；x ： 函数值厂( 工) 在当前求出的几个函数值中最小的点；w ：函数值厂( 叻是当前求出的几个函数值 中的第二小函数值的点；，：前一次的w 值；“：最新求函数值的点 输入包含局部极小值点的区间【口，6 】 算法步骤 ( 1 ) 尼= o ，y = w = x ，厂( v ) = 厂( w ) = 厂( 工) ( 2 ) 计算当前区间的中点x ：竺# 若1 6 一口i g ，则可将石作为近似的极小值点；否则 转( 3 ) ( 3 ) 若点z ，1 ，共线，则转( 4 ) ；若新找的近似点1 ，与当前函数的最小值点x 之间满足 l “一x 巨吾m a ) 【 i 口一石l 1 6 一z i ) ，转( 4 ) ；若i “一x l 6 的情况，可以反复利用下面的公式 设 ) = m “o ，嘶，“3 ，心 ) ， 若u = “o ，七，“l ，“2 ，“3 ，】， 贝( “) = c j 厂【“o ，忌，“l ，“2 ，鸭】( “) + d j m 尼，“2 ，坞，“4 】( “) 其中c o = 生塑，氐= l ； 鸭一m o 若u = “o ，七，“2 ，“3 ，甜4 】， 贝u ( 甜) = c i r “o ，“l ，七，”2 ，屹】( “) + 4 厂【“l ，尼，坞，“4 】( “) 其中q ：且，吐：譬； m 3 一“om 4 一m l 若u = 【”o ，越l ，”2 ，尼，“3 ，“4 】， 则 ) = 乞m ，“l ，屹，七，坞】 ) + 畋【蚝，吃，七，坞，】 ) 其中岛：兰塑，以：! 丝； 。z 岛一甜o “4 一 若u = 【“o ，“2 ，z 岛，七，“4 】， 贝u ( “) = c 3 礓“o ，“l ，”2 ，甜3 ，七】( “) + d ： r “l ，“2 ，“3 ，后，甜4 】( “) 1 9 ) ) ) ) 2 3 4 5 3 3 3 3 ， ( t - 样条实现封闭曲面重建 其中巳：1 ，以= 丝生 k 一“1 若尼或七，则 ) 不变化 定义3 4 将三维t - 网格中的所有面全部贯穿，会得到一隐式b 样条曲面的控制网格，这个 新网格称之为与t - 网格对应的b 网格在贯穿过程中新产生的交点，称之为原t 网格的缺失点 性质3 1 三维t - 网格和其对应的b 网格而言，t - 网中有些贯穿点处的节点向量与对应的 b 网格中该点的节点向量完全相同，因此，在这样的贯穿点处的混合函数就是定义在对应节点 向量上的三个b - 样条基函数的乘积，我们称该贯穿点的混合函数为该点的b 一样条基函数 图3 2 ( a ) 为一个三维