（计算机科学与技术专业论文）网格曲面造型技术研究.pdf

浙江大学麟士学位论支搦要 摘要 照营三维激光扫攒按术静窭盏成熟，a 弼可双方谨选获取曩霄丰富 几何细节的兰维模型出予多边形网格的简单性和酱适性，使之成为该 类模型较为滤宜的表示方法但网格曲面的线性分片逼近特性，融使其 在刻垂模型袭嚣复杂细节对，往往器要太量麓基本多边形，绘蓐续处理 带来了投大的疆壤。 本文j e 是围绕阿格曲面后续处理的若干关键闻越展开研究，它们分 别是；网格曲面到光滑连姨曲面的正向生成问题网格曲面上的细分， 阚播叠蓦匿变辑( 编辑) 阀题，班及弼搐曲蕊到参数曲霹的逆匀拟台趣题一 一蓝覆势冀蕊建具体两言，本文懿主簧霓献包括以下三方委 结合c b 样条研究的鳢新进展。本文提出了定义在三角网格上时一 豢特殊参数曲面四状兰向c b o x 一样条，给出了捆应的解析表j 表，并 对其牲厦进舒了分析涯明，进丽研究了该样条魏萄的离数表达即半静态 l o o p 筑分魏西，对该类细分鳇嚣耱连矮性进荐了详零分辑，并将其在各 向异性、灾锐特征表达等方面进行了扩展 针对当前网格曲面避型研究的热点网格曲耐编辑，提出了网格 按匿频谱编辑的糖方法演方注籍变形傣息作为几何信号，与原始攘型 的坐标晁薅信号在簇蠛肉进程台瘫、齄理，最后季遵齑变换蓟空闽蠛癌， 从而完成对艨始模型的编辑该方法其有控制简单、结果模型光滑性易 于保持等特点针对频谱编辑方法中的两个关键环节自适应采样和 特征点对齐，提出了镙持凡辑耀节尺度对应的自适成采样方法和特征点 对齐辩无网捂法等 参数瞌面重建对三维模型盼重用和快速建横篡有举足轻黉的作 用本文提出了一个实用新型的分片冀建方法，其莪键创新在于：将变 分逼近运用予嬲格模型约分剽，提出了多技术耦台的参数盐嚣耍建毵方 法蓄壳，扩震了原有变分逼遥方法，丰富了它鲍见弱代理粪型，饕诺 助改进变分遇近方法将网格模型分割为不同类型的分片其次。谶行多 方法耦合的参数曲面重建；普通分片采用t - s p l i n e s 麟小二乘拟台；而旋 转嚣分片采用控割点和节点漫整相接台魏方式，单步生戒分片豹糙确表 示i 对于奇异点姓g 震t o n u r c c s 逼近虽然不嚣分肆鲍优纯策酪霄籀， 僵皆为t - s p l i n e s 表示，散裕结构一致，生成方式统一。本文方法可商精 度重建工业设计中常见的旋转曲面，遥台于工业造型和其它复杂模型的 浙江大学博士学位论文：同格曲面造型技术研究 重建 综上所述，本文对网格曲面的构造、编辑和重构等关键问题提出了 新方法t 大量实例证明了这些方法具有很好的应用前景 关键词计算机辅助几何设计，网格曲面编辑，曲面分片重建，半静态 细分，b o x - s p l i n e ，l o o p 细分，频谱编辑，数字几何处理，小波分析， 自适应采样，特征对齐，无网格法，t - s p l i n e s ，t - s p l i n e s 迭代插值，变 分逼近 浙江大学博士论文a b s t r a c t a b s t r a c t r e c e n t l y , f o l l o w l n gt h er a p i dd e v e l o p m e n to f 3 dd a t aa e q u i s i t i o nt e c h n i q u e s ，i t i sc o n v e n i e n tt oo b t a i n3 dm o d e l sw i t hf i n ed e t a i l sf o rt h es i m p l i c i t ya n ds u i t - a b i l i t yo ft h ep o l y g o nm e s h e s ，t h e yh a v eb e c o m et h em o s ta p p r o p r i a t er e p r e s e n t a t i o no ft h o s em o d e l s h o w e v e r , t h ep i e e e w i s el i n e a rc h a r a c t e r i s t i co fm e s hs a r - f a c ec a u s e sm i l l i o n so fp o l y g o n s 据r e p r e s e n tt h ec o m p l e xg e o m e t r yd e t a i l s ， w h i c hw i l ir e s u l tj nm o r ed i 脯c u r i e sf o rt h es u b s e q u e n c t p r o c e s s i n g t h i sd i s s e r t a t i o ni sc o n c e r n e dw i t ht h ea b o v ep r o m i s i n gi s s u e s ，a n ds o m en o v e l t e c h n i q u e so fm e s hm o d e l i n ga r ee x t e n s i v e l yi n v e s t i g a t e d t h e s et e c h n i q u e sa r c ， t h e 岛r w a r dt r a n s f o r m a t i o np r o b l e mf r o md i s c r e t em e s ht oc o n t i n u o u ss n r f a c e t h a ti s ，t h es u b d i v i s i o nm e t h o do fm e s hm o d e l ；m e s he d i t i n g ；a n dt h ei n v e r s ef i t - t i n gp r o b l e mf r o mt h em e s hs u r f a c et ot h ep a r a m e t r i cs u r f a c e ，t h a ti s ，s u r f a c er e - c o n s t r u c t i o n d e t a i l e ds p e a k i n g ，t h em a i nc o n t r i b u t i o n so fo u rw o r kc o n t a i nt h r e ei s s u e sa s f o l l o w s f i r s t l y ，c o m b i n e dw i t ht h el a t e s td e v e l o p m e n to fc - b - s p l i n e ，an e wt y p eo f p a r a m e t r i c s u r f a c ei s p r o p o s e d ，n a m e l y f o r t h o r d e ra n dc u b i cd i r e c t i o n c * b o x - s p l i n e ，w h i c hi sd e f i n e do nt h et r i a n g u l a rm e s h ，i t sa n a l y t i c a lf o r m u l a t i o n i sd e r i v e da n di t sg e o m e t r i cp r o p e r t i e sa r ca l s od i s c u s s e d m o r e o v e r , w ei n v e s t l g a t et h ed i s c r e t er e p r e s e n t a t i o no fc - b o x s p l i n e as e m i - s t a t i o n a r yl o o ps u b d i v i - s i o ns c h e m e ，w ep o i n to u tt h a tt h es u b d i v i s i o np r o c e d u r ei sc o n v e r g e n t ，a n dt h e s u b d i v i s i o ns u r f a c eh a st h ep r o p e r t y o ft a n g e n tp l a n ec o n t i n u i t y i na d d i t i o n ，w e e x t e n dt h em e t h o dt ot h ea n i s o t r o p i ev e r s i o na n dt h eo n ec a p a b l eo f r e p r e s e n t i n g s h a r pf e a t u r e s s e c o n d l y , t oa d d r e s st h ek e yi s s u eo fm e s hm o d e l i n g ，an o v e lm e s hs p e c t r u m e d i t i n gm e t h o di sp r o p o s e di nt h i st h e s i s ，w h i c hi n t e g r a t e st h et e c h n i q u e so f f l e e 。f o r md e f o r m a t i o na n dg e o m e t r ys i g n a lp r o c e s s i n g w et a k et h ed e f o r m a t i o n o fp r o x ya sg e o m e t r ys i g n a l ，a n di m p o s ei t ss p e c t r u mu p o nt h eg e o m e t r ym o d e l | ob ed e f o r m e d ，弧er e s u l t a n ts i g n a li si n v e r s e l y 打a f l s f o r m e di n t ot h es p a c ed o m a i n ，a n dt h e nt h ee d i t e dm e s hc o u l db co b t a i n e d t h ep r o p o s e dm e t h o dh a sa d v a n t a g e so fe a s ym a n i p u l a t i o na n df a c i l i t a t i v ep r e s e r v i n gf o rt h es m o o t h n e s so f r e s u l t a n tm o d e l s a sa ne s s e n t i a ls t e p ，a l la d a p t i v es a m p l i n gs c h e m e ，w h i c hi s 浙江大学博士学位论文：网格曲面造型技术研究 u s e dt op r e s e r v et h es p e c t r u m ，i sp u tf o r w a r d i na d d i t i o n ，af e a t u r ea l i g n m e n t a p p r o c hb a s e do nt h em e s h l e s sm e t h o di sd e s i g n e d t h i r d l y , nf a m i l yo fs u r f a c er e c o n s t r u c t i o na l g o r i t h m sb a s e do nt - s p l i n e si s p r e s e n t e d w ei n t r o d u c et h ev a r i a t i o n a la p p r o x i m a t i o nm e t h o dt ot h es e g m e n t a - t i o no fm e s hs u r f a c e ，a n di m p r o v ei tb yi n c r e a s i n gt h et y p e so fg e o m e t r yp r o x y m o r e o v e r ，w ep r e s e n tuc o u p l i n gm e t h o do fs u r f a c ep a t c hr e c o n s t r u c t i o n d i f f e r - e n tr e p r e s e n t a t i o n sa n do p t i m i z a t i o ns t r a t e g i e sa r ea p p l i e dt od i f f e r e n tp a t c h e s a c c o r d i n gt ot h eg e o m e t r yp r o p e r t i e so f t h e i rp r o x y t h el e a s b s q u a r er e c o n s t r u c - t i o nm e t h o di se m p l o y e di ng e n e r a lp a t c h ，w h i l et h ea c c u r a t er e p r e s e n t a t i o no f c u b i cn u r b si su t i l i z e di nt h er e v o l u t i o np a t c h ，w h i c ht u n e st h ec o n t r o lp o i n t s a n dk n o tv e c t o r s ，a n de m p l o y st h et - n u r c c sa ts i n g u l a rp o i n t s i ns p i t eo ft h e d i f f e r e n c e so f o p t i m i z a t i o ns t r a t e g i e s ，t h e ya r ea l lr e p r e s e n t e di nt - s p l i n e s ，w h o s e d a t as t r u c t u r e sa n de v a l u a t i o np r o c e d u r e sa r ei d e n t i c a l t h em e t h o di sm o s ts i g - n i f i c a n tt or e c o n s t r u c tc o m p l e xm o d e l s i ns u m a r y , t h i sd i s s e r t a t i o np u t sf o r w a r dt h en o v e lm e t h o d sf o rt h er e p r e s e n t a t i o n ，e d i t i n ga n dr e c o n s t r u c t i o no fm e s hs u r f a e e l o t so fd e m o n s t r a t i o n sa r ep r o - v i d e dt oe x h i b i tt h ef e a s i b i l i t ya n dr o b u s t n e s so f t h ep r e s e n t e dm e t h o d s ，a n ds h o w t h e i re f f i c i e n tp e r f o r m a n c ea n dp o t e n t i a la p p l i c a t i o n si nt h eg e o m e t r ym o d e l i n g f i e i d k e y w o r d sc a g d ，s e m i - s t a t i o n a r ys u b d i v i s i o n ，m e s he d i t i n g ，s u r f a c ep a t c h r e c o n s t r u c t i o n ，b o x s p l i n e ，l o o ps u b d i v i s i o n ，s p e c t r u me d i t i n g ，d i g i t a lg e o m e t r y p r o c e s s i n g ，w a v e l e ta n a l y s i s ，a d a p t i v e l yr e s a m p l i n g ，f e a t u r ea l i g n m e n t ，m e s h l e s s m e t h o d ，t - s p l i n e s ，i t e r a t i v ei n t e r p o l a t i o no f t - s p l i n e s ，v a r i a t i o n a la p p r o x i m a t i o n 第一章绪论 第一章绪论 随着信息技术的快速发展，数字化已成为当今社会的主旋律，以数字声音、 数字图像、数字视频为代表的多媒体信息已渗透到现代社会的每一个角落，对人 类生活产生了深刻的影响从技术发展的进程来看，多媒体信息的维数不断提高， 出现了以三维几何数据为代表的新型媒体形式，其互动性亦日益增强，鉴于这种 三维媒体在计算机辅助设计、虚拟现实和数字媒体等领域有着广阔的应用前景， 如何高效地获取和处理三维几何数据已成为当前计算机辅助设计和图形学研究 最具挑战性的问题之一 由于多边形网格表示的简单性和普适性，以及与现代图形绘制流水线的兼容 性，多边形网格表示方法已成为三维几何媒体的主要表示形式但其线性分片逼 近特性，使得该表示方法在刻画复杂细节表面时，往往需要大量的基本多边形， 不仅导致巨大的计算、存储耗费，而且还给后续处理带来了极大的困难本文将 着重于研究网格曲面造型中的关键问题，结合几何造型研究的最新进展，为实际 应用提出切实可行的解决方案 本章将首先对形体的曲面表示方法进行简要介绍，然后介绍本论文的相关工 作最后扼要介绍本文研究内容和主要创新点 1 1 曲面造型技术 曲面表示方法利用基本面元对实体的表面进行描述从而完成实体模型的构 造，是c a d & c g 中广泛采用的几何形体表示方法之一按照基本面元的不同， 曲面表示方法可分为参数曲面表示、隐式曲面表示、多边形网格曲面表示以及其 它表示方法等 参数曲面使用连续的基函数，利用一组初始控制向量的线性( 或有理线性) 组 合来得到形体的连续表示参数曲面的优点是赋值计算简单，易于离散且显示方 便参数曲面适合于精确描述规则几何形状，又因与工业生产、国防建设密切相 关，因此，它较早受到关注，研究程度也最为深入，已经形成了以b 6 z i e r 和b 样条方法为代表，以插值、拟合、逼近为主要处理手段的实用几何理论体系【l ”但 是，参数曲面在处理拼接和高亏格曲面等问题时比较繁琐，表示具有丰富细节的 复杂形体时比较困难 隐式曲面由三维空间中的函数f ( x ，y ，z ) = 0 定义，具有几何求交容易，表示 浙江大学博士学位论文：网格曲面造型技术研究 封闭光滑形体方便等优点，在表现人体的肌肉、水滴、云、烟等物体的造型和动 画方面有很大的优势【1 蚓然而隐式曲面表示丰富细节和尖锐特征时十分不便 多边形网格直接使用点、直线段和平面面片来表示三维形体，数学原理简单， 容易理解，适合于绘制，配合纹理映射与光照材质，可以表现出极具真实感的绘 制效果“网格曲面具有表现丰富细节的能力，顺应了当前几何设计应用需 求，适宜于复杂形体造型，因此被越来越广泛地应用于三维几何媒体的表示鉴 于此，本文选择了以网格曲面作为主要研究对象但是， 光滑连续的几何模型可以给后续处理和工业生产带来方便，而网格模型 是分片线性的，因此，基于网格曲面的光滑连续曲面的构造问题必须妥 善解决； 网格曲面的基本面元数量通常十分巨大，而且顶点之间几何无关，操控 顶点或面元的直接编辑方式不再适用，传统的f f d 方法又因易于造成细 节丢失而不能很好地运用于复杂细节网格模型的编辑，因此，寻找方便 高效的编辑方法是当前网格曲面造型的研究热点； 参数曲面赋值计算简单、可精确表示规则形体等，在工业界被广泛使用， 因此，网格曲面向参数曲面转换是网格曲面模型步入工业生产的关键， 寻找切实可行的参数曲面重建方法是当前亟待解决的问题之一 为此，本论文围绕网格曲面的上述关键问题展开了深入研究 1 2 曲面细分构造 细分技术的研究最早可追溯到上世纪5 0 年代gd er a h m 提出的多边形割角 算法】上世纪七十年代末，e c a t m u l l 和j c l a r k 提出了c a t m u l l c l a r k 细分曲 面构造方法 1 6 】，c a t m u l l c l a r k 细分曲面由双三次b 样条递推性质导出，可适用 于任意拓扑结构几乎同时，d d o o 和m s a b i n 将双二次b 样条向任意拓扑曲 面进行了推广【2 5 】，这标志着细分技术正式成为几何造型的重要手段经过二十多 年的发展，新的细分模式 5 3 ，1 0 8 1 不断出现，细分规则的统一性理论【8 9 ，1 3 7 1 和收敛性 证明统一模式【l o l ，1 3 5 相继产生，细分理论日益成熟并逐渐走向实用 细分曲面是定义在多边形网格上参数曲面的过程式表示从初始网格 厶出 发，递归地调用细分规则细化控制网格，形成一个网格序列 肘。，m ，肘， ，当 ，斗m 时，有m 。_ m 称为细分曲面细分规则包括拓扑规则和几何规则，前者 确定新网格的顶点插入方法及连接关系；后者用于计算新网格顶点的位置，它的 图形表示称为模板 第一章绪论 c a t m u l l c l a r k 1 6 】最早提出了基于四边形网格细分曲面构造方法，三角形网格 上细分曲面的构造最早由l o o p t ”】提出，且c a t m u l l c l a r k 细分和l o o p 细分均为 逼近细分模式随后，三角网格和四边网格上的插值细分模式先后被提出，它们 的细分模板均可由三次插值多项式计算得出迭代细分过程可得到不同分辨率的 中间网格模型，为增加或减少中间网格模型的数目，研究者又提出了其它细分曲 面构造方式前期的细分模式大都采用1 - 4 分裂算子，网格面片每次增加3 倍k o b b e l t 提出的3 细分方法，可使网格面片每次增加2 倍口“，v e l h o 和z o f i n 又提出了4 8 细分模式，网格面片每次细分仅增长1 倍l l ”j m a i l l o t 和s t a r e 提出 了一类允许1 一d 2 分裂的细分模式，网格面片每次分裂成d 2 个新网格面片【7 ”，当 d 2 时，可达到加速面片分裂的目的此外，在探讨细分模式统理论的过程 中，部分已知细分模式不但被统一了起来，而且还衍生出了一些新模式借助分 裂与平均操作，c o h e n 等人的b 样条曲线离散生成技术阻陀3 可得到任意阶b 样 条曲线z o r i n 和s c h r o d e r 利用这一思想建立了主x 寸_ 偶( p r i m a l d u a l ) 四边形细分 模式的统一框架”，在此基础上很容易给出c a t m u l l c l a r k 和d o o s a b i n 的变种 细分模式s t a m 也进行了类似推广口，除与z o r i n 方法在实现上有所不同外， s t a r e 还进一步把算法移植到了三角网格上有些模式本身还可以进一步改进， 比如提高连续阶、改善光顺性因此，借助特征值分析，围绕细分曲面质量改进， 众多学者又提出了不同的细分曲面构造方法p r a u t z s c h 和u m l a u f 对 c a t m u l l c l a r k 模式和l o o p 模式的细分矩阵特征值进行修改，获得了全局g 2 连续 的曲面 9 6 t ”】稍有遗憾的是，该类方法所得细分曲面在奇异顶点处的曲率为零与 上述方法类似，l o o p 改进了他早年提出的l o o p 细分模式】，设计了一组新的权 值，从而可获得曲率有界、具有保凸性的改进l o o p 细分模式” 细分技术对曲面拼接和高亏格曲面的表示不再敏感，表现丰富，造型方便但 是传统细分方法仍然存在一些不足：( 1 ) 一些重要的形状特征( 如圆柱面) 无法精确 逼近( 2 ) 控制网格给定时极限曲面形状随之固定，细分方法依然不够灵活，同 时对已有曲面的精确逼近能力较弱国内外学者提出了非静态细分方法【9 9 】，这些 工作部分弥补了原有静态方法的不足结合c - b 样条( c b s p l i n e ) 7 4 ”2 】的最新进 展，张宏鑫和王国瑾以统一算子观点，定义了半静态细分方法 j 3 1 】半静态细分 方法拓宽了曲线曲面细分规则的构造模式，它通过改变核函数的硬度，来调节极 限曲线与控制网格之间的逼近程度，同时也增加了细分方法的灵活性但是上述 工作主要是针对四边形网格，针对三角网格的半静态细分方法的讨论还较少 细分曲面的连续性分析是曲面细分造型技术研究的核心问题之一细分曲面 规整点处为张量积或b o x - 样条【23 】曲面，其连续性自然保持，因此连续性分析都 浙江大学博士学位论文：网格曲面造型技术研究 是对奇异顶点展开d o o 和s a b i n 较早利用局部细分矩阵的特征值对 c a t m u l l c l a r k 曲面连续性进行分析【2 5 】，这一证明模式被后来者广泛使用不过 更加严格的分析却由b a l l 和s t o r y 给出【6 】，他们考虑了更大的邻域范围，并增加 了两切向量外积的连续性证明在这些连续性证明工作中，研究者均利用了细分 规则本身的循环对称性，分别对细分矩阵和奇异点周围顶点重新排列后实施离散 f o u r i e r 变换，用于辅助局部细分矩阵特征值分析r e i f 注意到切平面连续的曲 面有可能出现自相交的扭曲情形，通过引入特征映射( c h a r a c t e r i s t i c m a p s ) 的概念， 建立了细分极限曲面c 1 连续的充分条件概括地说，就是需要保证特征映射满 足正则性( r e g u l a r i t y ) 和单射性( i n j e c t i v i t y ) 条件据此，r e i f 证明了c a t m u l l c l a r k 模式在奇异顶点处的c 1 连续性质【1 0 l 】p e t e r s 和r e i f f ”】对d o o s a b i n 模式和 c a t m u l l c l a r k 模式特征映射的单射性和正则性进行了系统的分析u m l a u f 则利 用上述结论证明了l o o p 模式的特征映射的单射性和正则性d 2 0 在r e i f 理论的 基础上，z o r i n 建立了一类更一般的细分模式c 连续的准则，并设计了一个验证 c 1 连续的算法 1 3 6 p r a u t z s c h 推广了r e i f 的结果，利用特征映射对细分曲面进行 参数化，给出了任意静态细分模式的极限曲面g 连续的充要条件f 9 8 1 利用这一 连续性准则，p r a u t z s c h 等又先后给出了c a t m u l l c l a r k 模式和l o o p 模式在奇异点 处达到g 2 连续的细分规则，以及b u r e r f l y 模式在奇异点处达到g 1 连续的细分规 则p “”j 文献 1 0 8 和 1 2 2 对s e d e r b e r g 和郑建民提出的n u r s s e s 极限性质进行 过探讨【1 ”j n u r s s e s 是非静态细分模式，文献1 0 8 和 1 2 2 的分析过程却是借助 于将其近似转化为静态形式来展开分析的 在图形学界，采用数值方法对细分模式的连续性进行验证是较为通用的作法 盼”】比如特征映射的性质证明时，常依据特征控制网格若干次细分后的 性状，判断它是否满足单射性和正则性的条件本文也借鉴这一方法来分析细分 曲面的连续性 1 3 网格曲面编辑 直接操控网格曲面模型上的点、线、面等基本单元的局部编辑方法，原理简 单，容易实现，但是，交互繁琐，特征保持困难因此，寻找网格曲面的高效编 辑方法成为图形学研究的热门课题 b a 一7 1 率先将变形思想引入形体造型，他模拟了力学中常用的几种变形，给 出了这些变形的数学表示，并通过这些基本变形的组合来得到更加复杂的操 作s e d e r b e r g 和p a r r y 提出了自由变形的概念【1 0 6 】，该方法将物体形变定义为从 第一章绪论 原始物体空间到目标物体空间的三维映射在具体实现时，将物体嵌入一个三变 元b 6 z i e r 体中，用户通过编辑b 6 z i e r 体的控制顶点，改变这一参数体的形状， 进而使嵌入其中的物体发生形变由于b 6 z i e r 体本身不具有局部性，因此形体的 控制仍然比较困难，操作依然不够方便，但是它的这一变形思想却被众多后来者 所借鉴改变b 6 z i e r 的b e r n s t e i n 基为b 样条基，g r i e s m a i r 提出了b 一样条体作 为变形空间的自由变形方法【3 6 】k a l r a 等则提出了使用有理b e r n s t e i n 基函数的 r f f d ( r a t i o n a lf r e e f o r md e f o r m a t i o n ) 方法t 4 ”，以及使用n u r b s 基的n f f d 方 法【6 0 】等这些方法都有一个共同点，即初始的变形空间( l a t t i c e ) 为一平行六面 体c o q u i l l a r t 提出的扩展f f d 方法f 简称e f f d ) ”】使得初始变形空间可以有更多 的形状，如棱柱体、圆柱体等，从而增加了f f d 技术的使用范围改变变形空 间控制点到物体表面上，h s u 提出了直接操纵的f f d 方法【4 ”鉴于许多物体的 变形具有轴向性，部分研究者还讨论了轴变形方法i l * ”j 自由变形方法具有算法简单、几何直观性强等优点但为方便交互，几何代 理通常较为简单，这一特点直接导致自由变形方法不适宜于细节编辑此外，变 形过程中模型表面各顶点相对位置缺乏必要的约束，容易造成细节丢失文献 5 2 l 提出了将变形空间依附在三角网格表面上的方法，增加了几何代理的编辑灵活鹭 性，可构造较为复杂的表面细节，但是，该方法的变形计算复杂，而且细节丢失 现象依然无法避免0 ，基于物理模型的变形方法上世纪8 0 年代后期开始步入动画领域，经过近几1 年的发展，已成为图形学中极具潜力的三维造型和运动模拟技术该方面的工作 主要集中在将待变形物体视为弹塑性体，研究它们在外力作用下形变的快速计算 方法由于传统的表面变形均是基于几何的，其形变状态完全人为给定，因而变 形过程缺乏真实性w e i l 首次讨论了基于物理模型的柔性物体的变形问题，并用 它来模拟悬挂布料的形态【4 7 1 f e y n m a n 提出了更完善的布料悬挂模型i ”】此后 许多研究者开始采用各种物理模型对非刚性物体进行运动变形的模拟【1 “ 1 2 4 1 m i l l e r 用质点弹簧系统模拟蛇和虫子等无腿动物的蠕动动画，用弹簧的 收缩来模拟肌肉的收缩，并考虑了动力学模型中的方向摩擦，由于动画的高度逼 真在变形研究邻域引起了很大的反响【8 3 1 t u 等设计了种模拟鱼类行为的动画， 可以在动画师较少干涉的情况下生成真实的个体和群体运动【1 1 9 】t e r z o p o u l o s 在 基于物理的变形研究方面开展了系列工作采用连续弹性理论，通过考虑物体的 分布式物理属性( 如质量、弹性等) ，t e r z o p o u l o s 成功地模拟了柔性物体对外力的 动力学响应”此后，他进一步完善了上述变形模型使之能够模拟各种变形效 果，包括：完全弹性变形、非完全弹性变形、塑性变形、断裂等m “进步， 浙江大学博士学位论文：网格曲面造型技术研究 采用l a g r a n g i a n 方程和热方程，t e r z o p o u l o s 等又模拟了变形物体的融化过程f “8 1 基于物理的变形方法可获得高逼真的变形结果，因此近年来受到了研究者的 关注，揭示变形物体的物理规律，寻找加速算法成为基于物理变形方法研究的主 要内容但是，该类方法原理复杂，计算量偏大此外，目前很多算法都是针对 光滑物体的整体变形，小尺度的细节变形或局部编辑效果的研究仍不够充分 保持几何细节和特征是网格曲面编辑方法关注的核心问题常规的编辑 方法通常是直接修改网格顶点的绝对坐标，这种编辑方式很容易造成几何细节的 丢失因此，研究者们提出了用相对坐标表示网格曲面的局部细节信息，并开发 了相关的变形技术用于克服上述问题文献1 3 0 提出了网格曲面梯度编辑方法， 该方法通过编辑影响的插值扩散完成梯度场的改变：而后将梯度信息还原到空间 网格上，从而达到修改曲面形状的目的此外，s o r k i n e 等提出了利用1 邻域顶 点编码中心顶点的局部坐标表示方法，并将它利用到了l a p l a c e 曲面编辑方法中 1 1 0 1 同年，文献 1 2 8 提出了利用运动旋转不变坐标编码的网格曲面变形方法此 后，许栋又提出了微分曲面处理的理论框架，并将其应用于网格混合形变和多分 辨率编辑 1 2 6 ，1 27 1 ，取得了良好的编辑效果 上述方法均利用不规整网格上的离散微分算子，将局部细节和基网格分离描 述，独立处理事实上，多分辨率编辑d o ，5 5 , 1 3 8 1 与这一类方法有异曲同工之处， 但是多分辨率编辑需显式维护局部标架微分曲面编辑方法将基网格和细节信息 用稀疏线性系统的形式描述，表示简洁，处理方便，计算效率也更高现有的微 分域方法考虑了两类约束：边界顶点的几何位置和几何细节的微分属性，然而， 在一些特殊的应用中，需增加其它的约束：骨架的约束、体积约束等此外，微 分域方法通常需求解一个大型线性方程组，该方法的实时性尚有待进一步提高 此外，众多研究者围绕网格编辑相关问题开展了大量的研究，如网格曲面的 c u t p a s t e 1 0 , 5 9 , 1 、曲面融合( f i l s i o n ) 5 川和网格曲面混合【i 】等文献【8 8 】则从直观交 互出发，提出了基于勾绘的细节保持曲面编辑方法该方法将传统的移动柄 ( h a n d l e ) 从点集扩展到侧影轮廓或任意勾画的曲线，为用户提供了更高效的交互 手段 1 4 网格曲面的频谱分析与处理 几何信号处理技术近年来获得了飞速发展，利用网格曲面的频谱处理技术进 行变e g ( 编辑) 的研究也取得了较大的成功按照信号处理方法适用的网格拓扑连 接不同，可以将其分为面向非规整网格的方法、面向半规整网格的方法以及面向 全规整网格的方法 第一章绪论 1 1 面向半规整网格的方法 半规整网格是具有细分结构的三角网格模型，其大多数顶点的入度都为 六研究者们发现通过细分操作可以构造小波基函数，从而对任意流形的半规整 网格进行多分辨率分析这一优良特性受到了研究者们的广泛关注，将其运用到 网格编辑和变形上，取得了较大的成功【6 2 ，” l o u n s b e r y 最先提出了一类基于细分曲面的流形上的细分小波1 7 2 这种小波 是标准多分辨率分析的直接拓展，与传统的小波基构造方法不同，这里的小波基 来源于逐步细化的伸缩函数细分曲面进行多分辨率分析的关键步骤是构造满足 条件约束的高通和低通滤波器，这些约束包括 低分辨率模型是原始模型的较好逼近； 小波系数值的大小能反映系数所对应误差的大小： 分析和合成滤波器的时间复杂度与顶点数目是线性关系 据此l o u n s b e r y 设计了细分小波滤波器，并同时给出了一个滤波器仓库分析算法， 用它可以在帽子函数展开和小波基展开之间进行转换】 此外，s c h r s d e r 提出了利用提升技术在球面上构造具有定制性质的二进正交 小波即球面小波 i 0 3 ( s p h e r i c a lw a v e l e t s ) 提升小波构造方法的时间和空间效率都“ 要高于l o u n s b e r y 的线性小波，因此，目前基于半规整网格的数字几何处理算法 都采用提升小波作为信号分析工具 上述小波分析算法仅仅适用于具有细分连接结构的三角网格由于一般的三。 角网格模型通常不具有这种连接性而无法直接使用这些算法，这个问题在很长时+ 间内阻碍了细分小波方法的应用e c k 等人【2 6 】提出了用于解决这一问题的重网格 化方法，但因其时间复杂度过高而无法推广应用直到1 9 9 8 年，l e e 等人提出 的m a p s 6 3 算法才较好解决了该问题 多分辨率编辑f 】和网格变形吲是基于半规整网格的d g p 技术的典型应 用在多分辨率模型中，几何信息被编码成一个基网格和若干层细节信息，其中 细节信息用局部坐标描述利用这种表示方式，用户可以在特定的细节层次上执 行多种模型操作，可以在较好保持细节的前提下，方便地完成复杂模型的编辑修 改此外，细分小波对半规整网格可以进行滤波、增强、卷积运算等，为该类网 格的变形操作提供了丰富的手段和工具 2 ) 面向非规整网格的方法 细分小波对网格拓扑连接的特殊要求，限制了它的进一步推广应用重采样 算法虽然能较好地解决这一问题，但是它的时空复杂度仍然偏高，而且重采样质 量的好坏受很多因素制约为此，探索适用于任意三角网格( 非规整网格) 的几何 浙江大学博士学位论文：网格曲面造型技术研究 图1 - 1 几何信号频谱分析一般流程 信号处理技术，引起了众多学者的兴趣 t a u b i n i “4 ，“5 】首次将离散傅立叶变换推广到网格曲面上，并据此推导出了用 于光顺造型的有限脉冲响应滤波器，它具体表现为非规整网格上的松弛算子 k o b b e l t 等【55 j 从带约束的能量最小化磨光方法出发，推出了和文献11 4 类似 的均匀松弛算子，该方法通过最小化定义在曲面上的能量函数来达到磨光的目 的为实现快速光顺，k o b b e l t 采用网格简化技术，构造了多层次光顺算法由 于简化网格的顶点数目远小于原始网格模型的顶点数目，因此，在多层简化网格 上进行光顺的收敛速度比直接在原网格上进行光顺要快得多 g u s k o v 等唧j 进一步发展了文献1 5 5 的方法，提出了非均匀松弛算子，通过 结合网格简化技术，该算法把一般的信号处理工具，如向下采样、向上采样和滤 波推广到了任意三角形网格之上借助文献【3 9 】的方法，可以构造出更为合理的 多分辨率结构，为非规整网格的交互编辑提供了方便此外，适用于任意拓扑连 接的松弛算子可方便地进行光顺造型，为网格曲面变形提供了高效的辅助工具 应该说明的是，多分辨率编辑方法提供了同一物体的不同分辨率版本，既可 以整体控制，又可局部编辑但是，它需要构造几何模型的累进表示，构造过程 复杂，机内表示繁琐多分辨率编辑仍以直接操纵顶点坐标的局部编辑完成，所 能提供的交互方式有限 。 3 1 面向全规整网格的方法 半规整网格上的几何信号分析方法应用最为成功，但是，这种方法的连续性 很难证明，并且不能处理几何信号的某些低频分量面向非规整网格的几何信号 方法源于三维网格上的d f t ，理论基础相对完备，但是由于直接计算d f t 的时 间代价太高，因此这种方法无法支持大多数f o u r i e r 频率域内的应用，一般只能 用来做网格光顺造型面向全规整网格的方法通过把任意网格参数化到平面上生 成能存储模型各种属性的图像，可以利用大量成熟的数字图像处理工具，进行滤 波、压缩等l l “1 g u 等 3 7 1 在2 0 0 2 年提出了一种新型的三维几何模型的表示方法几何图 像( g e o m e t r yi m a g e ) 该方法首先对任意网格实施切割，将其转换为一拓扑同构 第一章绪论 于圆盘的开网格，进一步将此开网格参数化到一个单位矩形内，所有网格表面信 号如顶点位置、法向量和颜色都可以被均匀采样成图像g u 方法的核心是寻找 一个最优的切割路径，可以使参数化后网格扭曲最小 周昆提出了基于球面参数化和球面规则重采样的数字几何处理统一框架 1 4 q 该方法首先通过球面参数化将几何信号转移到球面之上，而后利用球面上 的自适应采样将几何信号转化为规则信号，最终利用球面调和分析进行滤波、增 强等处理逆向返回可将频谱信号转换到三维空间域内文献 1 4 1 方法的完整 处理流程参见图1 1 此外，从细节迁移的角度，周昆尝试性地将该方法应用于 网格编辑但是，利用全规整网格的处理方法进行网格编辑的理论探讨有待进一 步加深，所涉及的关键技术也有待进一步完善 1 5 模型分割与曲面重建 本文曲面重建侧重基于网格曲面的细分曲面重建和参数曲面重建细分曲面 重建不受拓扑制约，容易处理高亏格的网