（应用数学专业论文）网格曲面的展开与可展性优化.pdf

摘要 摘要 可展曲面由于具有的优良性质，在工程实践中有广泛的应用关于可展曲面的 相关研究也一直是计算机辅助几何设计和图形学中的重要研究问题随着三维数据 采集技术和硬件设备的长足进步，网格曲面正在逐渐成为计算机图形学和几何设计 领域中的新宠于是，对离散形式的可展曲面的研究也引起人们更多的兴趣本文围 绕离散可展曲面的相关问题进行深入的研究，取得了一系列理论和算法结果 一般只有可展曲面才能在展开到平面时不会发生任何扭曲和撕裂，对一般的曲 面做展开时我们的目标是让这样的扭曲尽量小对网格曲面，我们提出基于整体捧 列的新的网格展开方法网格上每个顶点和它的的1 一邻域顶点构成的区域首先最优 地展开成平面块，所有的平面块在一个目标函数下，通过一个整体排列算法得到网 格曲面的一个整体展开平面我们的整体排列算法尽量保持每个局部平面块的几何 结构不交，所以使得最后得到的展开平面的几何扭曲尽量小用户无需事先指定参 数域的边界位置，参数化后的边界通过优化目标函数自然得到我们方法适合于非 封闭的网格模型，网格上可以有一条或者多条内部边界网格的采样率对算法的影 响不大顶点位置约束或者其他线性约束很容易添加到我们的算法框架中，这些约 束在纹理映射的特征点或者特征曲线对应中非常有用 平面参数化方法要求处理的网格是开网格，对于封闭的网格或者开口比较小的 网格需要对它先做分割我们给出了一种基于轻松勾画交互的网格分割方法该方法 交互简单自然，用户只要用鼠标在物体表面上大致勾画一下分割的种子区域，就能 得到各块的分割结果，分割边界由算法自动计算得到该算法采用区域增长法，计算 快速，满足用户实时交互的要求结合网格参数化方法和平面纹理合成方法，我们给 出了制作三维网格模型纹理映射的多种实用工具，包括网格分块、平面纹理坐标计 算、纹理特征对应、以及平面纹理合成等 对于近似可展的网格曲面，我们讨论它的可展性度量方法基于新的可展性度 量函数，给出了一个网格可展性整体优化方法在优化曲面的过程中始终参考一个 平面网格，保持优化后网格和平面网格之问的等距映射，即保证了优化后网格的可 i l i 浙江大学博士学位论文 展性质和局部算法相比，对原始曲面形状的改变较小并且我们利用拟插值技术， 使得优化后的网格和原始网格之间的误差距离得到严格控制在原始网格上用户可 以指定一些特征线，这些特征线在优化过程中始终保持位置不变优化后曲面比较 光顺，没有出现明显的褶皱现象 一些形状优美的空间曲面可以通过带曲线折痕的可展曲面造型得到我们深入 地研究了带曲线折痕的可展曲面的连续和离散性质，提出了带曲线折痕的可展曲面 设计和重建方法采用以四边形为主的网格作为可展曲面的离散表示形式，在这种 离散表示的基础上，提出了计算离散曲率和弯曲能量的新方法对于给定的近似可 展的三角网格模型，提取它的母线，并以母线为边重建新的以四边形为主的网格模 型优化该网格使之更加可展，并且逼近原始网格形状，具有一定的光顺性质，以及 极小化弯曲能量等基于同样的优化框架，给出了更多的应用，比如弯曲能量极小化 的可展曲面变形、带曲线折痕的可展曲面设计等我们的结果不仅有利于工业和建 筑上可展曲面的设计，也对研究可展曲面在曲线折痕处的性质提供了一个新的方法 关键词：多边形网格，可展曲面，参数化，纹理映射，网格分割，可展性优化，曲线 折痕，几何重建 i v a b s t r a c t a b s t r a c t d e v e l o p a b l es u r f a c e sa r ew i d e l yu s e di ni n d u s t r i a la p p l i c a t i o n sd u e t ot h e i rn i c ec a - p a b i l i t yo fb e i n gm a d ef r o ma f l a ts h e e tw i t h o u ta n ys t r e t c h i n ga n dt e a r i n g h e n c e , d e v e l - o p a b l es u r f a c e sh a v ea t t a i n e da l o to fr e s e a r c hi n t e r e s t si nt h ef i e l do fc o m p u t e ra i d e dg e o - m e t r i cd e s i g na n dc o m p u t e rg r a p h i c s w i t ht h ed e v e l o p m e n to f3 da c q u i s i t i o nt e c h n o l o g i e s a n dh a r d w a r ed e v i c e s ，d i s c r e t ep o l y g o n a lm e s hs u r f a c e sh a v eb e c o m ei n c r e a s i n g l yp o p u l a r i ti sw o r t h w h i l et os t u d yt h ed i s c r e t ec o u n t e r p a r to fd e v e l o p a b l es u r f a c ei nd i g i t a lg e o m e t r y p r o c e s s i n g i nt h i sp a p e r , w ei n v e s t i g a t e t h ed i s c r e t ed e v e l o p a b l es u r f a c ea n di t sa s s o c i a t e d p r o b l e m s t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w s i ng e n e r a l ，o n l yd e v e l o p a b l es u r f a c ec a nb ef l a t t e n e di n t op l a n ew i t h o u ta n yd i s t o r t i o n w h e nf l a t t e n i n gan o n - d e v e l o p a b l es u r f a c e ，o u rg o a li st om i n i m i z et h eg e o m e t r i cd i s t o r - f i o n w ep r e s e n tan o v e lp a r a m e t e r i z a t i o nm e t h o df o ran o n - c l o s e dt r i a n g u l a rm e s h f o r e v e r yf l a t t e n e di - r i n gn e i g h b o r s ，t h el o c a lg e o m e t r ys t r u c t u r ei sr e p r e s e n t e d 觞l o c a lp a r a m e t r i cc o o r d i n a t e s t h e nt h eg l o b a lo p t i m a lp a r a m e t r i cc o o r d i n a t e sa f ea t t a i n e db ya l i g n i n g a l lt h el o c a lp a r a m e t r i cp l a n e s t h eb o u n d a r yc o n d i t i o n sa r en o tn e c e s s a r yi no u rm e t h o d i na d d i t i o n ，o u rm e t h o dc a no p e r a t ed i r e c t l y0 1 1m e s hs u r f a c ew h i c hh a sh o l e sw i t h o u ta n y p r e p r o c e s s i n go fs u r f a c ep a r t i t i o no rh o l ef i l l i n g l i n e a rc o n s t r a i n t sa l e a l l o w e di nt h ep a r a m e t e r i z a t i o ni nal e a s ts q u a r e ss e n s e o u rm e t h o di sv e r ys u i t a b l ef o rc o m p u t e rg r a p h i c s a p p l i c a t i o n sw h i c hr e q u i r ep a r a m e t e r i z a t i o nw i t hl o wg e o m e t r i cd i s t o r t i o n ，s u c ha st e x t u r e m a p p i n g p l a n e rp a r a m e t e r i z a t i o nm e t h o da s s u m e st h a tt h em e s hs u r f a c ei sat o p o l o g i c a ld i s c ， o rh a si n n e rb o u n d a r i e s f o rc l o s e dm e s h ，w eh a v et os e g m e n ti ti n t op a t c h e s ，a n dt h e n p a r a m e t e d z ee a c hp a t c hi n t op l a n e w ep r o p o s ea ni n t e r a c t i v em e s hc u t t i n gt o o l ，w h i c h i si n t u i t i v ea n de a s y - t o u s e b a s e do ns k e t c h i n gi n t e r f a c e ，u s e r sc a r ls e g m e n tt h em e s hi n s t a n t l yb ys i m p l yd r a w i n gf r e e h a n ds k e t c h e so nt h em e s hw h i c hm a r kt h es e e dr e g i o nf o r e a c hp a t c h a n dt h ec u t t i n gb o u n d a r yo fe a c hp a t c hi sc o m p u t e da n dr e f i n e da u t o m a t i c a l l y v 浙江大学博士学位论文 t h es e g m e n t a t i o na l g o r i t h mi sb a s e do na l li m p w 泔r e g i o ng r o w i n ga l g o r i t h m ，w h i c h i sf a s ta n dp r o v i d e si n s t a n tv i s u a lf e e d b a c kt ot h eu s e r s c o m b i n i n gs e g m e n t a t i o n ，p l a n e r p a r a m e t e r i z a t i o na n dt e x t u r es y n t h e s i st e c h n i q u e s ，w eh a v ea r i c ht o o l b o xf o rt e x t u r em a p - p i n g d e v e l o p a b l es u r f a c ec a nb ei d e n t i f i e db yc o m p u t i n gi t sg a u s sc u r v a t u r e ，w h i c hi s i d e n t i c a l l yz e r o f o rn o n - d e v e l o p a b l es u r f a c e s ，t h e r ei sn ou n i f i e df o r m u l at oq u a n t i f yh o w f a rt h e ya r ef r o mb e i n gd e v e l o p a b l e w ep r e s e n tan e wm e t h o dt oe v a l u a t et h ed e v e l o p a - b i l i t yo ft h em e s hs u r f a c e t oi m p r o v et h ed e v e l o p a b i l i t yo fag i v e nm e s hw i t hm i n i m u m s h a p ec h a n g e ，ae n e r g yf u n c t i o ni sd e s i g n e dt os i m u l t a n e o u s l ye n s u r et h a tt h eo p t i m i z c d m e s hb e c o m em o r ed e v e l o p a b l e ，f i t st h ei n p u td a t a ，a n ds a t i s f i e st h es m o o t hr e q u i r e m e n t s o ft h ea p p l i c a t i o n ai t e r a t i v en u m e r i c a ls o l u t i o ni sp r o p o s e df o rs o l v i n gt h i so p t i m i z a t i o n p r o b l e m b yu s i n gt h en e a r l yi n t e r p o l a t i o nt e c h n i q u e ，t h et o l e r a n c eo ft h ei n p u tm e s ha n d t h eo p t i m i z e dm e s hc a na l s ob ec o n t r o l l e d f e a t u r el i n e ss p e c i f i e db yt h eu s e r sc a nk e e p f i x e dd u r i n go u r o p t i m i z a t i o n f a s c i n a t i n ga n de l e g a n ts h a p e sm a yb ef o l d e df r o mas i n g l ep l a n a rs h e e to fm a t e - r i a l ，i fo n ei n c o r p o r a t e sc u r v e df o l d si n t ot h ed e s i g n w ei n v e s t i g a t et h ec o n t i n u o u sa n d d i s c r e t ep r o p e r t i e so ft h ed e v e l o p a b l es u r f a c e sa l o n gc u r v e df o l d s ，a n dp r e s e n ta no p t i m i z a t i o nb a s e dc o m p u t a t i o n a lf r a m e w o r kf o rd e s i g na n dd i g i t a lr e c o n s t r u c t i o no fs u r f a c e s w h i c hc a nb ep r o d u c e db yc u r v e df o l d i n g g i v e nan e a r l yd e v e l o p a b l et r i a n g u l a rm e s h ， w ed e t e c ti t sr u l i n g s ，a n dc o n s t r u c tai n i t i a lq u a dm e s hu s i n gt h o s er u l i n g s a no p t i m i z a - t i o nb a s e dc o m p u t a t i o n a lf r a m e w o r ki sp r o p o s e dt or e f i n et h ei n i t i a lq u a dm e s h b a s e do n t h eo p t i m i z a t i o nf r a m e w o r k ，m o r ea p p l i c a t i o n sa r ei n t r o d u c e d ，s u c ha sd e v e l o p a b l es u r f a c e d e s i g nw i t hm i n i m u mb e n d i n ge n e r g y , b e n d i n gi nt h ep r e s e n c eo fac u r v e df o l d ，e t c o u r w o r kn o to n l yc o n t r i b u t e st oa p p l i c a t i o n si na r c h i t e c t u r ea n di n d u s t r i a ld e s i g n ，b u ti ta l s o p r o v i d e sa n e ww a yt os t u d yt h ec o m p l e xa n dl a r g e l yu n e x p l o r e dp h e n o m e n aa r i s i n gi n c u r v e df o l d i n g k e y w o r d s ：p o l y g o n a lm e s h ，p a r a m e t e r i z a t i o n ，t e x t u r em a p p i n g ，m e s hs e g m e n t a t i o n , d e - v e l o p a b l es u r f a c e ，d e v e l o p a b i l i t yo p t i m i z a t i o n ，c u r v e df o l d ，d i g i t a lr e c o n s t r u c t i o n v i 图目录 图目录 1 1 样条曲面：( a ) 用n u r b s 表示的曲面；( b ) 用t 样条表示的曲面；( c ) t 样 条曲面的渲染结果( s e d e r b e r g 等【1 1 ) 2 1 2 分别利用不同的细分方法三次得到的细分曲面：( a ) 控制网格；( b ) d o o - s a b i n 细分方法；( c ) c a t m u l l - c l a r k 细分方法；( d ) l o o p 细分方 法；( e ) 3 - 细分方法 3 1 3隐式曲面表示方法4 1 4 非流形网格：( a ) 非流形边，相邻的三角形个数大于2 ；( b ) 非流形顶 点，连接两个伞形邻域 5 1 5 多边形网格：( a ) 三角网格模型；( b ) 带颜色和材质等属性的多边形网 格的渲染结果 6 1 6 l a p l a c e - b e l t r a m i 算子离散方法，阴影部分为顶点的v o r o n o i 区域 9 1 7 平面参数化的几何扭曲度量1 2 1 8参数化方法的各种应( h o r m a n n 等t 4 3 b 1 4 1 9 可展开网格顶点：( a ) 顶点v t 和它l 一邻域点，图中显示的伞形区域不 可展；( b ) 顶点在同一平面上；( c ) 顶点在两个平面上；( d ) 相邻的边既 有凸边也有凹边；( e ) 用平面去截图( d ) 中的邻域，得到的多边形为凹 多边形；臣t ( b - d ) 显示的都是可展开网格顶点 1 7 1 1 0 可展曲面的四边形为主的网格表示：( a ) 离散柱面；( b ) 离散锥面；( c ) 离散切线面1 8 1 1 1 可晨曲面的应用：( a ) 在工业制造中的应用，如船体、汽车和飞机机 身的制造等( 图片来自互联网，版权归原公司或原作者所有，下文 同) ；( b ) 计算机辅助制衣系统( d e c a u d i n 等 5 3 1 ) 1 9 i x 浙江大学博士学位论文 x 1 1 2 可展曲面在建筑设计中的应用：位于美国洛杉矶的迪斯尼音乐厅，由 f r a n k o g e h r y 设计，采用了可展曲面造型；右边两个子图显示了曲 面在拼接地方的细节，由于在拼接线上曲面并不可展，导致纹理拼接 不连续2 0 2 1 算法概览：( a ) 网格模型上的局部区域；( b ) 3 d 模型上局部区域展开 为平面块；( c ) 整体排列所有平面块2 5 2 2 顶点1 邻域以及它的局部和整体参数坐标：( a ) 顶点和它的l - 邻域 点；( b ) 最优局部展开；( c ) 整体参数坐标2 7 2 3 采样非均匀网格的参数化例子：( a ) 人脸网格模型，左侧网格疏，右侧 网格密；( b ) 参数化结果；( c ) 从不同角度观察下的黑白棋盘纹理映射 结果3 0 2 4 与f l o a t e r 参数化方法【2 5 1 作比较：( a ) v e n u s 模型；( b ) 我们方法的纹理 映射结果；( c ) f l o a t e r 方法的纹理映射结果 3 0 2 5 带洞的近似可展网格曲面的展开：左图为3 d 网格模型，右图为它的 平面展开 3 0 2 6 与z i g e l m a n 方法剀作比较：( a ) 带洞的人脸模型；( b ) z i g e l m a n 方法 的参数化结果；( c ) 我们方法的纹理映射结果；( d ) 我们方法的参数化 结果3 l 2 7 b e t t l e 模型例子：( a ) 3 d 模型；( b ) 参数化结果，上一行为我们方法结 果，下一行为z i g e l m a n 方法 2 9 1结果；( c ) 和( d ) 为不同视角下的纹 理映射结果，同样上一行是我们方法结果，下一行是z i g e l m a n 方法 的结果3 l 2 8 带约束的纹理映射：( a ) 3 d 人脸模型，红色点为用户标记的特征点； ( b ) 纹理图片，以及对应的特征点；( c ) 和( d ) 不同视角下纹理映射结果3 4 2 9 用户实时交互的参数化结果：( a ) 3 d 模型；( b ) 和( c ) 用户交互得到的 两个参数化结果 3 4 2 1 0 带线约束的纹理映射：( a ) 带尖锐边的网格曲面；( b ) 纹理图片；( c ) 纹 理贴图结果3 4 图目录 2 1 1 基于勾画的网格分割：( a ) 导入网格；( b ) 用户勾画式输入；( c ) 网格分 割结果3 7 2 1 2 恐龙模型的分割例子：( a ) 用户输入两条画线和分割结果；( b ) 增加一 条画线后的结果 3 9 2 1 3 手掌模型的分割结果：( a ) 用户输入的画线和对应的分块；( b ) 从背面 观察分割结果，虽然用户只在模型正面画线，背面的分割线也满足用 户的意图 3 9 2 1 4 纹理图集：( a ) 输入模型以及分块结果；( b ) 每一块都参数化到纹理坐 标域；( c ) 纹理映射结果3 9 2 1 5 基于最优化方法的纹理合成：小图为输入纹理样本，大图为合成纹理 4 l 2 1 6 纹理合成结果：小图为输入纹理样本，大图为合成纹理；( a ) 砖墙例 子；( b ) 青藤例子4 2 2 1 7 合成纹理用于纹理映射：( a ) 输入纹理样本；( b ) 纹理样本的简单平铺 结果；( c ) 合成纹理；( d ) 平铺图片映射到三维网格模型的结果，图片 间的接缝明显；( e ) 合成图片映射到三维网格模型的结果，没有出现 图( d ) 中的接缝，纹理更加美观 4 2 2 1 8 图像修复算法4 4 2 1 9 纹理修复：( a ) 原图；( b ) 填充区域；( c ) 横向线性插值初始化；( d ) 迭 代5 次后的结果；( e ) 算法第一遍运行结果；( 0 我们算法的最终结 果；( g ) b e r t a l m i o 等f s 9 j f 法结果；( 1 1 ) c r i m i n i s i 等1 9 0 算法的结果4 5 3 1 离散等距弯曲能量模型：网格上的一条内边，和它相邻的两个三角 形；每条内边上定义一个弯曲能量，网格整体弯曲能量是各个边上弯 曲能量的累加5 3 3 2 可展性整体优化：( a ) 和( d ) 分别为输入网格m 和优化后的网格 ；( b ) 和( e ) 分别显示m 和m 7 的每个三角片上的值，红色表示 最大值，蓝色表示最小值，即为零；( c ) 和( f ) 分别显示了m 和m 7 上 顶点处的内角和与2 7 r 的差值5 5 x i 浙江大学博士学位论文 x 3 3距离误差控制：( a ) 输入网格；( b ) 优化后的网格；( c ) 原网格和优化网 格的距离偏移，限制网格的边界固定不动；( d ) 原网格上顶点的内角 和与2 7 r 的差值；( 0 优化后网格上顶点的内角和与2 7 r 的差值5 7 3 4 与w a n g 等【5 0 1 算法结果比较：( a ) 输入网格；( b ) 我们算法优化后的网 格；( c ) w a n g 等【剐算法优化后的网格5 7 4 1 传统的折纸艺术，纸张沿着直线折痕折叠，折痕两侧的面都是平面6 2 4 2 带曲线折痕的折纸，曲线折痕的两侧都是曲面，使得曲面造型更丰 富图中两个例子为d a v i dh u f f m a n 的作品 6 2 4 3 带曲线折痕可展曲面在工业设计中的应用6 2 4 4 连续可展曲面上折痕曲线的性质：右图中黄色平面为折痕曲线的密 切面，紫色和绿色平面分别是折痕两侧曲面的切平面 6 4 4 5 右图是一张连续的可展曲面，左图是右图可展曲面的一个离散表示 形式相邻两个平面四边形的公共边p t 吼为离散母线，它们的交点构 成了离散的脊线n 通过不断细分四边形，在极限的情况下，折线r i 就是可展曲面的极限r ( t ) 折线c 的边t i c 件1 与相邻两条母线的角平 分线垂直，它是主曲率线的离散表示平面四边形只的单位法向用 珥表示6 5 4 6 两个四边形序列在曲线折痕处相交，如果给定一侧的四边形序列d 1 ， 则在顶点仇处，d 2 上的母线必须落在一个二次圆锥t 上6 6 4 7 离散曲率和弯曲能量：( a ) 平面四边形序列的母线由尼= p i q i 给出& 是尼和忍+ 1 在平面内的角平分线，点c t 在边民上，并且c 忍+ 1 和 最垂直；( b ) 为了避免在圆锥点处曲率的值出现无穷大，公式4 3 仅 计算沿母线方向缩进后的四边形区域，如图中的灰色区域；( c ) 由两 条主曲率线a d 和线& 一1 ，最包围的区域，如图中棕色区域，它的弯 曲能量由公式4 。4 给出6 8 4 8 优化算法概览6 9 4 9 测地圆上函数盯( q ) 的性质：( a ) 网格上四个不同区域上的测地圆；( b ) 对应测地圆上矿( q ) 的函数图7 0 图日录 4 1 0 离散母线提取：( a ) 利用测地圆估计母线方向，并标记平面区域，如图 中的黄色区域；右边放大的局部图显示了在测地圆上的盯( q ) 的函数 值；( b ) 母线延长并经过挑选删除后的结果；( c ) 最后的母线以及平面 区域( 黄色区域) ，平面区域的边界利用相邻的母线得到7 2 4 1 1 初始平面四边形网格p 的构造：( a ) 网格上母线和特征线在它平面展 开上的投影；( b ) 母线的端点粘附到特征线和边界线上，其中棕色的 点为圆锥顶点；( c ) 添加母线防止得到的网格出现t 连接；黄色区域 对应于空问网格上的平面区域 7 2 4 1 2 优化算法的基本设置：d 为要逼近的原始曲面；平面上和空间上颜色 相同的四边形全等7 6 4 1 3 算法优化过程：( a ) 初始的多边形集合m ；( b ) 平面展开网格p ；( c ) 经 过一次优化细分后的m ；( d ) 经过三次优化细分后的m 7 8 4 1 4 优化算法的稳定性7 8 4 。1 5 弯曲能量极小化：初始网格为长方形序列，如左图所示；用户指定边 界边且和易的空闻位置以及这两条边所在面的法线后，通过极小 化弯曲能量函数得到右图的形状8 0 4 1 6 用户给定边界不同的位置和法向约柬后，极小化能量函数得到的曲 面形状；在优化过程中不断细分初始网格，使得最终的曲面比较光顺8 0 4 1 7 带畦b 线折痕的曲面弯曲：左图，用户在可展曲面上指定折痕曲线；右 图，利用我们的优化算法框架计算得到沿着给定曲线折叠后曲面的 形状，其中有多条折痕曲线，我们逐条处理8 2 4 1 8 纸模型的重建：所有模型都先利用纸做出造型，然后扫描到计算机， 重建出三角网格曲面，然后运行我们算法得到可展曲面8 3 4 1 9 带曲线折痕曲面的弯曲序列：左上方的第一副图中的曲面是通过逼 近一个扫描的纸模型得到，其他图中的曲面是结合尽量等距的变形 方法和我们的重建方法计算得到8 3 浙江大学博士学位论文 4 2 0 汽车模型的可展曲面重建：右上子图为曲面的平面展开，右下子图为 重建后的可展曲面，左列子图显示了曲面局部的母线分布我们利用 颜色标记不同类型的可展曲面，黄色表示平面，绿色表示柱面，红色 表示圆锥面，蓝色表示切线面8 5 4 2 l 建筑上的应用：在所有例子中我们都可以看到纹理没有发生任何扭 曲，即使在曲线折痕处纹理仍然连续过度；右上子图显示了利用可展 曲面的母线作支撑结构的例子 8 6 术语表 表目录 2 1 网格展开算法的运行时问以及几何扭曲度量3 6 3 1 可展性优化算法的结果和运算时间5 9 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得浙江大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：签字日期： 年月 日 学位论文版权使用授权书 本学位论文作者完全了解浙江大学有权保留并向国家有关部门或机构送交 本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江大学可以将学位 论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 导师签名： 签字日期：年月日签字日期：年月日 致谢 致谢 在论文完成之际，回首五年来学习工作中的点点滴滴，我非常感激那么多的师 长和朋友给予我的帮助。正是他们在研究上的指导和合作，在生活上的关心和照顾， 才使得我顺利完成研究生阶段的学习和研究任务。 首先要感谢王国瑾教授和刘利刚副教授，本论文是在两位导师的悉心指导下完 成的王国瑾老师严谨的治学态度、广博的学识、独到的见解令我深深折服；他平易 近人的和蔼气质、高尚的学术风格、一丝不苟的科研作风，始终是我辈之楷模特别 感谢刘利刚老师，是他带我走上了科研的道路，本论文的大部分工作也是在他指导 下完成的我的每一点成长都与刘老师的指导和关心密不可分，是他对我无数次的 耐心面谈中，让我学习到许多专业知识；是他对科研的饱满激情深深地感染了我， 让我体会到了科研的乐趣；是他活跃的创新思维、迎难而上的挑战劲头、精益求精 的科研精神，鼓舞着我在研究道路上不断向前刘老师对我的教诲不仅仅在科研方 法方面，他乐观豁达的生活态度、主动积极的做事态度也在潜移默化中改交着我王 老师和刘老师对学生无比负责，能成为他们的学生我感到很幸运在此，再次向两位 导师致以最深的感谢 感谢课题组的汪国昭教授、杨勋年副教授，他们治学态度严谨，学问渊博，思路 开阔；他们在讨论班上曾给我许多宝贵建议和指导，拓宽了我的思路另外特别要感 谢维也纳技术大学的p o t t m a n n 教授和香港大学的王文平教授给我提供了宝贵的学 习交流的机会，和他们一起工作的经历，让我迅速开阔学术眼界，并体会到成为学 术大家所具有的基本特质 感谢课题组胡倩倩、辛士庆、计忠平、赵宏艳、徐惠霞、徐岗、陆利亚、邓重阳、 李亚娟、曾兰玲、武丹、沈莞蔷等师兄师姐对我的帮助和鼓励；感谢张磊、方林聪、 胡建伟、朱平、陈仁杰、张冬梅、陈军、周联、周红光、孟敏、周世哲、徐寅、朱薇、 林彬彬、吴金亮、金亮、吴晓群、孟凡慧等同学，大家互相学习，团结互助感谢鄢 楚楠、俞金平、张安、方琳、陈平等多年同窗好友给予我美好的求学时光另外感谢 浙江大学博士学位论文 n i l o yj m i t r a 、m a r t i nk i l i a n 、s i m o nf l i s r y 、a l e x a n d e rs c h i f t n e r 、h e i n zs c h m i e d h o f e r 在维也纳时给我科研和生活上的热情帮助 感谢父母、哥嫂、姐和姐夫长久以来对我无尽的关爱、支持和鼓励，你们是我强 大的后盾，也给予了我生活、学习和工作无穷的动力特别感谢女友曹娟，我们互相 勉励，一起完成了各自的博士论文 最后要感谢评阅博士学位论文和出席博士学位论文答辩会的各位专家学者，感 谢您们在百忙之中给予指导! 陈中贵 二零零九年六月于求是园 绪论 第1 章绪论 随着计算机图形学和计算机硬件的发展，三维几何场景的模拟和绘制已经不是 新鲜的技术三维技术已经被广泛地应用于生产生活当中，比如三维游戏、电影特 效、虚拟城市、以及医疗诊断等 在过去的几年里，三角网格的曲面表示方法被大家广泛地采用，并逐渐成为 计算机图形学和几何设计领域中的新宠三角网格的曲面表示方法有很多的优点， 比如它表示方法简单，可以表示复杂拓扑的曲面，并且客易处理，易于绘制等网 格模型数据的获得一般有两种方法：一种是通过3 d 建模软件制作得到，比如3 d s m a x ，m a y a ，b l e n d e r 等；另一种是通过扫描现实世界中的物体得到随着三维数据采 集技术的长足进步，人们越来越容易将现实世界中的三维物体转化为计算机中的网 格模型，这也是网格模型之所以流行的另一个原因通常由三维扫描仪得到的原始 三维点云数据还不能直接用于产品，还需要对原始数据进行一系列的后处理，比如 曲面重建、拓扑修复、去噪、参数化、简化和形状优化等，所有这些过程构成了数字 几何处理的研究内客 可展曲面由于具有的优良性质，在工程实践中有广泛的应用关于可展曲面的 相关研究也一直是计算机辅助几何设计和图形学中的重要研究问题由于离散网格 莹面的广泛应用，可展曲面的离散表示形式与离散性质便逐渐引起人们的研究兴趣 本文正是围绕着离散可展曲面和它的相关问题展开研究 1 1 三维曲面表示 在开始我们讨论之前，首先介绍一下图形学中三维曲面的表示方法，因为这是 几何处理算法的基础常用的曲面表示方法有样条曲面、细分曲面、隐式曲面和网格 曲面等每种表示方法都是自身的优缺点，应用的领域也有所不同 斯江大学博 位论i 鎏震 图li 样紊曲面：( a ) ) 目n u r b s 表示的曲面；( b ) 用t 样杂表示的曲面：( c ) t 样条曲 面的渲染结果( s e d e r b e r g 等) 1 1l 样条曲面 在现夸的c a d 系统中，张量积样条曲面巳经成为自由曲面的标准表示形武它 们被用作构造高质量的曲面，或者拉制曲面的变形 样杂曲面可以方便地表示为一些样条基函数的张量积”一张n 次的张t 积样 条c a 面f ，是一个分段的多项武曲面，不同块的多项武曲面拼接后p q 连续样条 曲面的表达武为 f ( u ，”) = c “岬( “) 凹( ”) = 0 其中 ? ( ) 为b 样条基函教，。构成了曲面的控制网格因为岬( u ) 20 ，且。婶( “) ； 1 ，所以曲面上每个点t ( u ，口) 是控制顶点的。“的凸组合，所以曲面落在控制网格的 凸包内由于基函数的局部支撑性，每个控制顶点仅影响曲面的的局部区域这两个 性质使得曲面逼近控制网格，而且我们可以通过调整控制网格来调整曲面的形状 图li ( a ) 显示了一个非均匀有理b 样条曲面( n o n u n i f o r m r a t i o n a l b s p l i n es u r - f a c e ) ，t n u r b s 曲面；图1 1 ( b ) ( 0 是s e d e r b e r g 等提出的t 样条表示方法，t 样条 能以比n u r b s 曲面更少的控制顶点来构造曲面 张量积曲面是定义在一个矩形的参数区域上，所以曲面本身也是嵌入在r 3 中 的四边形区蛾为了表示具有更复杂拓扑结构的曲面，薷要将曲面分割为很多块张 量积曲面由于张量积曲面表示方法在拓扑上的限制，一般的c a d 模型都由很多块 篇 图12 分别利用不同的细分方法三次得到的细分曲面：( a ) 控制网格；( b ) d o o - s a b i n 细分方法；( c ) c a t m u l l c l a r k 细舟方法；( d ) l o o p 细分方法；( e ) 届细舟方法 曲面片拼接而成选样就要考虑曲面拼接时的连续阶问意，对每个张量积曲面增加 鞭升的几何限制张量积曲面表示方法的拓扑限制和不同块之阿拼合的连续性要求， 增加了张量积曲面建模的复杂性 ll2 细分曲面 细分曲面可以认为样枭曲面的推广形武“和掸条曲面类似，我们也可以通过 调整控制顶点控制细分曲面的形状，但是细分曲面可以袁示任意拓扑的曲面细分 曲面由不斩地细分韧始的控制网格得到，在每一次细分后，蹰格的顶点根据它局部 相邻顶点的坐标作调整通过仔细分析细分规则可以得到极限曲面的连续性细分曲 面造型不受曲面拓扑和其他几何约束，而且细分曲面内在的多层次结构使得一些算 法更加有效但是细分曲面的奇异点受拉钢网格的奇异的限制，并且在奇异点处，网 椿不够光颅一些方法通过对同椿进行重呆样，改变奇异点的位置，但是重新网格化 又涉及到逼近误差和信