（计算机科学与技术专业论文）微分网格处理技术.pdf

摘要 摘要 自上个世纪八十年代以来，三维模型编辑领域发生了两次大的技术突破。第 一次突破发生在八十年代，称之为自由变形( f r e e f 0 肌d e f o m a t i o n ) 技术r 以操纵 代理模型为手段来进行模型编辑。第二次突破发生在九十年代，称之为多分辨率 编辑f m u h i 啪s 0 1 u t i o ne 西t i n g ) 技术，以操纵简化模型为手段来进行网格编辑。这两 次技术突破为三维几何建模提供了强大动力，尤其是发展相当成熟的自由变形技 术已经成为商业造型软件不可或缺的组成部分。 然而，随着三维扫描技术的快速进步，几何模型的精度和数据复杂程度达到 了新的高度，这些三维模型包含着十分丰富的几何细节，在精确刻画局部几何特 征的同时也为模型的编辑处理提出了新的挑战一几何细节在编辑过程中难以有 效保持。针对具有丰富几何细节的三维扫描数据，我们和国内外其他同行一道， 提出了新的几何表示方法和计算模型来迎接挑战，我们将这些算法统称为微分域 方法。比之于前两次技术突破，微分域方法的优势主要体现在几何编辑过程中细 节特征的有效保持方面，因此该技术特别适合于编辑三维扫描数据。目前，尽管 微分域方法仍在进一步的深化研究之中，但一些国外学者已经将其视为三维模型 编辑领域中的第三次技术突破，而本文的工作正是这次新突破中的主要组成部分 之一。 不同于传统方法，本文提出的微分网格处理技术不再将三维几何模型视为欧 氏空间中的连续或离散点集，而是将其视为定义在三维域网格上的标量场。相应 地，几何处理算法从空间点集或其控制点集的直接坐标操纵转化为间接的微分属 性操纵。我们承认直接操纵顶点的空间坐标简单易行且具有几何直观性，但是与 微分属性相比，顶点坐标缺乏刻画局部几何特征的能力。正是这一点导致了基于 直接坐标操纵的传统编辑算法在编辑过程中难以做到几何细节特征的有效保持， 而保持几何细节恰好是微分处理算法的优势所在。 我们的网格处理框架以离散流形上的泊松方程为理论基础，将用户编辑操作 映射为对定义在域网格上的梯度场的操纵以及对边界条件的修改，最终的编辑结 果则通过泊松方程重建得到。之所以采用梯度场操纵加泊松重建的编辑框架，主 要基于如下的两点考虑：其一，梯度作为微分属性可以方便地进行局部修改，而 随后的重建过程可使得局部的梯度修改产生全局的编辑效果，通常传统方法要做 到这一点需要进行大量的人工交互。其二，由于基于最小二乘优化的重建过程具 有均匀分布逼近误差的特点，使得梯度局部调整产生的瑕疵能被有效地扩散到整 个几何模型上，从而产生高质量的处理结果。这两点直接导致了微分网格处理技 术能够以较少的交互操作来产生高质量的编辑结果。 在微分网格处理框架下，我们给出了一系列具体的应用算法，包括网格变 形、网格融合、网格光顺和网格形状插值。这些算法的共性问题是如何将用户的 编辑意图有效地转换成对梯度场的操纵以及对边界条件的修改。与同类其它算法 相比，这些应用算法在编辑结果的质量上都有着质的提升。例如，在相同的用户 交互下，以三维扫描数据为编辑对象，采用我们提出的泊松网格变形算法和网格 融合算法生成的编辑结果都要显著优于采用商业造型软件m a y a ”中的自由变形工 具w i r e 所生成的相应结果，这一点已经得到w i r e 工具的设计者 a r a ns i n 曲的认 可。此外，采用泊松形状插值算法生成的过渡序列由于能够正确地表达模型之间 一i i 摘要 的相对旋转关系，因而可以显著减少关键帧动画中所需要的关键帧的数量。 采用微分网格处理技术并不是无代价的，由于离散泊松方程实质上是一个稀 疏线性系统，其未知数个数与兴趣区域的自由顶点个数成正比，所以泊松方程的 数值求解成为整个框架的瓶颈问题。为此，我们提出了由两个层面组成的加速技 术。其一，通过矩阵c h 0 1 e s k y 分解，我们将方程的系数矩阵进行预先分解并将其 存储起来，这样整个编辑过程只需要根据新的边界条件进行快速回代即可，该方 案使得在目前的个人电脑上，可以交互编辑中等规模的几何模型。其二，对于较 大规模的几何模型，直接求解计算代价过高乃至不可能完成f 维数过高会导致内存 无法容下泊松方程) ，因此，我们设计了一套累进求解方法。该方法首先将原始模 型进行累进简化至顶点个数满足交互编辑的需求，简化过程中各个层次之间的几 何细节通过一套相似变换不变系数进行编码记录。对于变形后的物体，该技术可 以通过求解一系列的局部泊松方程来完成整个重建过程，最后得到原始模型的编 辑结果。 图层概念的提出曾经使得图像处理软件在系统设计上有了质的飞跃，然而三 维模型的数据特点使得现有的网格编辑系统难以引入层模型。我们在编辑技术上 取得的新突破，使得重新设计网格编辑系统的架构成为可能。基于微分表示方 法，我们提出了一个新的以“几何层”为核心的网格表示和编辑系统，该系统借 鉴了图像处理软件中的“图层”模型，为编辑操作提供了新的空间维度。相应 地，我们给出了网格模型的几何层表示、分解、属性操纵和合成方法，使得复杂 的编辑任务能够分解成为一系列独立的分层操作，从而增加了系统的灵活性，提 高了编辑效率。 最后，我们简要列出本文的主要贡献： 三维网格的微分表示方法以及基于该表示方法的通用几何处理算法框架。 基于梯度场操纵和泊松重建的微分网格处理算法，具体包括网格变形、网格 融合、网格光顺和网格形状插值算法。 适用于巨型几何模型处理的泊松方程累进求解技术，其核心是具有相似变换 不变性的细节编码算法和基于局部模板的泊松重建算法。 以几何层为核心概念的统一网格表示和处理框架，并形成个原型编辑系 统。 关键字：图形学、数字几何处理、泊松方程、梯度场操纵、网格变形、网格融 合、网格光顺、网格形状插值、多分辨率编辑、几何层。 i i i 夔壅垫蔓 a b s t r a c t s i n c e1 9 8 0 s w eh a v ew i n l e s s e dt w om a j o rb r e a k t h r o u g h si nt h e 矗e l do fg e o m e 啊c m o d e l i n g t h ef i r s to n eh a p p e n e di n19 8 0 s ，c a l i e d 施e f 0 衄d e f o m l a t i o n ，e d j t sg e o m e t - r i cm o d e l sv i am o d j f y i n gap r o x 矿t h es e c o n do n eh a p p e n e dj n19 9 0 s ，n a m e dm u l t i - r e s o l u t i o ne d i t i n g ，p r o c e s s e sg e o m e t r i cm o d e l sb ym a n i p u l a t i n gac o a r s es h a p e g e o m e t r i cm o d e l i i l gh a sb e e np m m o t e db y 也e s et w ob r e a k m r o u g h ss i g n i f l c a n t l y 1 np a r t i c u l a r ， 矗c e f 0 锄d e f o m a t i o nb e c o m e ss om a t i l r em a th a 8b e e na l lm d i s p e n s a b l ec o m p o n e mo f c o m m e r c i a lm o d e l i l l gs o f t w a r e s t 0 d a y ，t 1 1 er a p i da d v a n c eo f3 ds c 础gt e c h n i q u e sh a v em a d eg e o m e t r i cm o d e l s w i t hh u n d r e d so f t h o u s a n d so f p r i m 矗i v e su b i q u i t o u s o no n eh a n d ，t h em o ep r i m i t 王v e sa m o d e lc o n t a i n s ，也em o r ea c c u r a t ei t sg e o m e t r i cf e a t i l r ec a nb e 矗g u r e do u t o nt h eo t l i e r h a l l d ，s c 籼e dm o d e l sp o s en e wc h a l l e n g e st og e o m e t r i cp r o c e s s i i l g ，i e ，i ti sr a t h e rd * 6 c u l tt op r e s e eg e o m e 衄cd e t 8 i l sd u 曲ge d i t i n g t 0m e e t 也i sc h a l l e n g e ，o t h e rr e s e 挑h t e 砌sa n du si n t r o d u c en o v e l 窖e o m e t r yr e p r e s e n _ 亡a t i o n sa sw e l la sc o m p u t a t i o n a im o d e l s f o rs c a n n e dm o d e l sw ec a l lt h e s en e wa p 口r o a c h e sd i f r e r e n t a 1d o m a i nm e t h o d s ( d d m s ) c o m d n gw i t hp r e v i o u sm e t h o d s ，d d m sh a v e 也er e m a r k a b i ef e a n l r et l l a tg e o m e 虹i c d e t a i l sc a 工lb ew e l l p r e s e r v e dd u r i n ge d i t i n 2 t h e r e f o r c ，d d m sa r ep a r t i c u l a rs l l i t a b l ef o r p f o c e s s i n 2s c a n n e dm o d e l s o 埔c l l t l y ，d d m sh a v eb e e nah o tr e s e a r c ht o p i ca i l dh a v e b e e nc o n s i d e r e da st h et h i r db r e a k t h r o u 足hb ys o m ef b f e i g nr e s e a r c h e r s o u rw o r k ，a s p r e s e n t e di nm i sd i s s e r t a t i o n ，a r eo n eo f m a i o rp a r t so f 戗l i sn e wb r e a k m r o u g h ， u n l j k et r a d i t i o n a lm e t h o d s ，o u rt e c h n i q u er e g a r d s3 dg e o m e t wa ss c a l a r 矗e l d sd e 五n e do nt h ec o m m o nd o m a i nm e s hi n s t e a do fc o n t i n u o n l s d i 8 c r c t ed o i n ts e t sd e f m e di n e u c l i d e a ns p a c e c o n s e q u c n n y ，w ep r o c c s sg e o m e 扛i cm o d e l sv i a 妇p l i c “l ym a i l i p u l a t i l l g d i 丘b r e n t i a l 口r o p e r t i e s v b n e xp o s i t i o n sd on o th a v et h ea b i l i t yt od e s c r i b el o c a li n 幽s i c 南a t u r e sw h i l ed i 疗i e r e n t i a 王p r o p c n i e sd oh a v e t h e r e f 出e ，d d m sa r es u p e r i o rt 0e d i t i n g m e t h o d st 1 1 a tm a l l i p u l a t ev e n e xp o s i t i o n se x p l i c i t l yi nn l ew a yt h a t 譬e o m e t r i cd e t a i l sc a n b ew e l l 一p r e s e r v e dd u r i n gp r o c e s s i n g ， t h et h e o r e t i c a lf - o u n d a 6 0 no fo u rt e c h n i q u ei st h ep o i s s o ne q u a t i o n i n0 u r 丹a m e w o r k ，e m t i n gam o d e lc a nb ea c h i e v e db ym o d i 母i n gi t sg r a d i e n tf i e i da n db o u n d a r yc o n d i t i o n ，a n das u c c e e d i i l gr e c o n s t 兀i c t i o nu s i l l gt h ep o i s s o ne q u a t i o n t h em o t i 、忸t i o no f t h i sa p p i o a c hi s 协o f b l d f i r s t ，m e2 r a d i e n ti sad i 摄e r e 】啦i a lp r a p e r t yt h a tc a nb em o d i 五e d l o c a l j ys u b s e q u e mr e c o n s t r u c t i o nf b mt i l em o d i 五e d 硎i e n tc a n 窟i v er i s et oa9 1 0 b a l e f 凳c tw h i c hw o u l do t h e n i s er e q u i r eal a r g e ra m o u n to f u s e ri n t e r a c t i o n s e c o n d l y ，a n i f a c t si n t r o d u c e dd u r i n g1 0 c a ie d i t i n gc a nb er e m o v e dd u r 主n gr e c o n s t n l c t i o nb e c a u s el e a s t s q u a r e sm i 工l i m i z a t i o nt e n d st od i s 虹i b u t ee r r o r su 工1 i f 0 咖1 ya c r o s st l l e 如n c t i o n t h e r e f o r e ， o u rf h m e w o r kc a ng e n e r a 把h i 詈h q u a i i 母r e s u l t sw i t hl c s su s e ri m e r a c t i o n s o u r 丘a m e w o r ks u p p o r t ss e v e m la p p l i c a t i o n s ，r a n g j n g 丘o md e f o m l a t i o n ，o b j e c t m e 唱i n 岛s m o o t h i n gt oi n t e r p 0 1 a t i o n t h ec o m m o nr e s e a r c hp m b l e mo ft h e s ea p p l i c a “o n si sh o wt oe 日e c t i v e l yt r a n s f o r mu s e ri m e r a c t i o n si n t og m d i e n tn e l dm a n i p u l a t i o n s a s w e l la sm o d i f i c a t i o n so f b o u n d a r yc o n d i t i o n s a ) m p a r i n gw i t hp r e v i o u sm e t h o d s ，r e s u i t s g e n e r a t e db yo u ra l g o i i t h m sh a v e1 l i 曲e rq u a l i 够f o re x 蛐p l e ，1 1 1 l d e rt h cs a m eu s e rm - t e r a c t i o n s ，f o rs c a n n e dm o d e l s ，0 1 1 rd e f o n n a t i o nr e s u l t sa r eb e “e rt h a i lt h o s eo b t a i l l e db v i v 英文摘要 矗e e - f o m id e f o m a t i o nt o o iw i r ei nc o m m e r c i a i8 0 最w a r em a y a im ( c o n 五n n e db yk a r a n s i n 曲，t h ed e s i g n e ro ft h ew i r ea l g o r i t h m ) a n o t h e re x a m p l ei sk e y f r 锄e sc a nb es i g - n i 矗c a n t l yr e e i u c e dw i mt 1 1 eh e l 口o fo u rs h a p ei m e r p 0 1 a t i o na l g o r i t h m ，s j n c ei tc a nh a n d l e m er e 】a 石v er o t a “0 nb e t w e e nm o d e l sc o n e c n v s i n c eo u rt e c h n i q u ef e q u i r e ss o l v i n 2as 口a r s el i r l e a rs y s t e m ，i tc a 工lb e 恤eb o t t l e n e c k o fo u rf r a m e w o r k t os p e e du p 也ec o m p u t a t i o n ，w ep r o p o s eat w o l e v e la c c e l e r a t i o n t e c h n i q u e t h e 矗r s tl e v e l i sb a s e do nt h ec h o l e s k yd e c o m p o s i t i o n w i mi t ，t 1 1 ec o e 街 c i e n tm a 研xj sp r e f a c t o z e d a 疗e r 也a t ，t h ep o i s s o ne q u a t i o nc a nb es o l v e de 璇c i e n t l y b yb a c ks u b s t i t u t i o n t h i ss c h e m em a k e st o d a v sp cc a n 口r o c e s sm o d e m t em e s h e s t h e s e c o n dl e v e l i sap r o g r e s s i v es 0 1 v e rf o rm e s h e st h a ta r es o1 a r g et 1 1 a ts o l v i n gp o i s s o ne q u a - t i o n sd e 丘n e do nt h e md i r e c t l yw i l lb eu n a 丘o r d a b l e 门b om a n yu m m o w n sm a yc a u s et h e p o i s s o ne q u a t i o ne x c e e d sm em e m o r yc a p a b j l i t y ) f i r s 订y ，t 1 1 eo r ig i n a lm e s hi ss i m p l 值e d a c c o r d i n gt ou s e r s p e c i 6 e dt h r e s h o l d 【h n 足s i m p l m c a t i o n ，鹭e o m e t r i cd e t a i l sb e t w e e n s u c c e s s i v es u r f a c e1 e v e l sa r er e c o r d e db vas e to fs i m i 】a r i t v i n v a d a n tc o e 茄c i e n t s a r e r t h eb a s em e s hi sd e f o r m e d ，山eh i 2 h r e s o 】u o nr e s u l t w i l lb eo b t a i n e dv i aas er j e so f 】o c a l p o i s s o n b a s e dr e c o n s t m c d o np r o c e d u r e s i m a g ep r o c e s s i gs o f w a r e sa d v a n c e da1 a 玛es t e pb yi n c o r p o r a t i n gt h ec o n c e p to f l a y e lh o w e v e r ，a r b i t r a r yt o p o 】o g ya n di r r e “l a rs a i l l p l i l l gp r e v e n tm e 印p l i c a t i o no f l a y e r t om e s l le d i t j n gs y s t c 翻s o u rp o w e r & l t e e l l 工l i q u em a k e si 亡p o s s i b i et ou p g 豫d et h ea r c h i - t e c t u r eo fm e s he d j t i n gs y s t e m b a s e do nd i f f b r e n t i a lm e s hr e p r e s e n t a t i o n ，w ep m p o s e an o v e ls u 响c er e p r e s e n t a t i o na n de d i t i n gs y s t e ml e v e r a 窖e db yg e o m e t r i c1 a v e ls p e c m i c a l l y w ep r e s e n ta 】g o r i 也m sf o rs u i f a c ed e c o m p o s i t i o n ，d e t a ne n c o d i n l a y e ra t 仃i b u t e s m a 碰p u j a t i o na n ds u r f 毫c ec o m p o s i t i o n w i t h 协eh e i po f g e o m e t r i c1 a y e r s ，c o m p r e h e n s i v e e d i t i n gt a s k sc a nb ed e c o m p o s e di m os e v e r a li n d e p e n d e n t1 a y e r b a s e do p e r a t i o n s ，砌c h m a k e s0 1 1 re d i t i n gs y s t e mf l e x i b l ea 1 1 de f b c i e n t f i l l a l l mw el i s t t h em a o rc o n t r i b u t i o n so f t 1 1 ed i s s e r t a t i o n ： w ei n t m d u c ean o v e lm e s hr e p r e s e n t a t i o nb a s e do nd i f i 鼍r e n t i a lp r o p e r t i e sa i l da g e n e r a lm e s hp r o c e s s i n g 丘啦e w o r kb a s e do nt h i sr e p r e s e n t a t i o n 飞p m p o s es e v e r a lm e s hp r o c e s s i n ga l g o r i t h m s ，m n g i n g 疗o md e f o 加a 矗o n ，o b j e c t m e r g i n g ，s m o o t h i n ga i l ds h 印ei n t e i p 0 1 a t i o n ，b a s e do ng r a d i e n tn e l dm a l l i p u l a t i o n 蛆d 血ep o i s s o ne q u a t i o n w 。p r o p o s eap r o g r e s s i v ep o 主s s o ns 0 1 v e rf 撕l a 猎em e s h e s ，w h i c hc o n 虫s t so f an o v e l s i m j l 州哆i n v a r i a n td e t a i lr e p r e s e n t a t i o na n dal o c a lp o i s s o n - b a s e df e c o n s t r u c t i o n a l g o r i t l l m w e p r o p o s eau d 访e dm e s hr e p r e s e n t i n ga n de d i t i n gm m e w o r kb a s e do ng e o m e 打i c l a y e r s ，a n di m p l e m e n t al a y e l _ e d _ b a s e dp r o t o t y p e de d i t m gs y s t e m k e y w o r d s ：c o m p u t e rg r a p h i c s ，d i g i t a lg e o m e t r yp m c e s s n 备p o j s s o ne q u a t i o i l g r a d i e n tf i e l dm a n j p u 】a t i o n ，m e s hd e f o n n a t i o n ，o b j e c tm e 唱i n g ，m e s hs m o o t h i n g ， s h 叩ei n t e r p o l a t i o n ，m u l t i r e s 0 1 u t i o nt e c h i l i q u e ，g e o m e t r i cl a y e r ， v 第一章引言 第一章引言 1 1 数字几何模型及其表示方法 数字几何模型是继声音、图像和视频之后的又一类新的数字媒体【1 1 4 】。在英 文中，几何( g e o m e t r y ) 一词的词根来源于两个希腊单词“g e o ”和“m 晰o n ”，意 思是测量地球。随着虚拟现实技术的进步和影视娱乐行业的发展，数字几何模型 正逐渐走进人们的日常生活之中，其应用也早已超出测量地球的范畴，并逐渐渗 透到模拟仿真、造型设计、医疗诊断、遗产保护、影视特效和互动娱乐等领域之 中( 参见图1 1 ) 【4 4 】。 从计算机图形学的角度来看，数字几何模型是真实世界的各种物理实体的数 字化表达，亦即数字化的物理实体。在上述各应用领域之中，数字几何模型均扮 演着应用主体的角色，例如在虚拟现实应用之中，数字几何模型是构筑虚拟世界 的基本要素，因此如何快速有效地获取几何数据就成为各应用领域研究中的一个 核心问题。目前，几何数据的获取手段多种多样：在影视娱乐领域中，几何数据 第一章引言 往往来源于艺术家的创造；在医疗诊断领域中，几何数据常常来自于对c t 断层扫 描、核磁共振成像以及正电子成像等技术获取的医疗影像的重建；在模拟仿真领 域中，几何数据则大多来自于对模拟对象实体的测量和构造。近年来，三维激光 扫描技术得到了快速发展，各种手持或固定扫描仪器逐步问世，其数据获取的精 度和尺度不断提高，三维激光扫描已成为几何数据快速获取的重要手段 7 6 。本 文处理的几何模型大都通过激光扫描设备获取，我们将这种通过激光扫描获取的 几何数据简称为扫描数据。 数字几何模型的表示方法多种多样，存在着不同的分类准则 2 】。整体而言， 几何数据的表示方法可以分为实体表示( c o n s t n i c t i v es 0 1 i dg e o m e t r y ，简称c s 回和 边界表示( b o u n d a r yr e p r c s e n t a t i o n ，简称b r e p ) ，前者侧重描述物体占据的实体空 间，而后者则侧重描述物体的表面边界。实体表示是通过对体素定义运算而得到 新的形体的表示方法，体素可以是立方体、圆柱、圆锥等，也可以是半空间，其 运算为变换或并、交、差等正则集合运算。其优点有三个，即数据结构简单，易 于转换成为边界表示和易于修改；缺点也有三个，即形体的表示受体素种类和体 素操作类型的限制，形体的局部操作不易实现以及难于绘制。c s g 方法可采用一 棵有序的二叉树来表示，c s g 树无二义性，但一般不唯一。边界表示表示的是实 体的边界，它是几何造型中最成熟、无二义性的表示方法。实体的边界通常由面 的并集来给出，边界表示的一个重要特点是在该表示方法中，描述形体的信息 包括几何信息( g e o m e t 忉和拓扑信息( t o p o l o g y ) 荫部分 3 。几何信息描述形体的大 小、尺寸、位置和形状，而拓扑信息则描述几何元素之间的相互连接关系。边界 表示的优点有三点，即凡何元素显式给出从而易于索引，方便对物体进行各种局 部操作和便于在数据结构上附加各种非几何信息；其缺点主要有两点，数据结构 复杂导致维护困难和需要运用欧拉操作来保证所表示形体的有效性、正则性等。 多边形网格是一种典型的边界表示模型，它将物体的表面表示成为一系列面片的 交集，其特点是可以任意精度来表示任意拓扑物体的表面。由于现有图形绘制流 水线硬件设计的内在要求，无论原始数据最初采取何种方式表达，最终都需转换 为一系列离散三角形作为绘制的基本单元因此三角形网格已成为当前数字几何 模型的主流表示方法。本文的研究对象主要是三角形网格，简称三角网格。如无 特别说明，文中提到的网格特指三角网格。 除了上述准则之外我们还可以根据基本元素f p r i m i t 、吧) 的类型进行分类， 具体包括点云表示、隐式表示和体素表示，有兴趣的读者可以参见相关文 献 1 2 ，1 1 ，3 1 ，4 0 】，在这里我们不再赘述。图1 2 给出了常见的几种数字几何模型 的表示方法。 罔l2常见的数字几何模型的表示方法。( a ) 到( e ) 分别是网格表示 1 1 2 】 几何图像 5 0 】、隐式表示 1 0 2 】和c s g 实体表示 5 4 】。 1 2 数字几何处理的基本问题 ( e ) 点云表示 3 0 】、 应用领域的迫切需求推动了数字几何处理的基础理论与实用算法的研究，自 上个世纪九十年代以来，国内外的科研人员发表了大量数字几何处理方面的研究 工作，总结起来，可以归纳为以下几个基本方面( 参见图1 3 ) 。 1 2 1 数据获取与重建 数据获取技术解决数字几何模型的来源问题。目前常见的手段包括通过建模 工具手工创建【1 2 5 】通过医疗影像自动抽取【1 9 】和通过扫描点云自动重建 7 6 】三个 方面。手工创建无拘无束，可以方便地反映创作人员的创作意图，其缺点是需要 专业建模知识+ 交互工作量较大，一般用户难以掌握。影像抽取是通过图像( 平面 或立体) 分割等手段将影像中的实体( 一般为人体器官) 抽取出来，从而获得三维几 何信息，其优点是数据获取过程高度自动化，缺点是抽取结果受图像噪声影响较 大，重建精度比较低。扫描重建常用于日常实物的数字化，一般适用于雕塑等静 态实体的几何建模其优点是数据精度较高，扫描过程自由灵活，且可支持材质 信息的同步获取；缺点是多步扫描数据之间需要对齐( r e g i s 蛔t i o n ) ，获取数据量有 时过大，重建结果容易受到扫描噪声影响。需要指出的是，尽管已有大量的自动 重建算法，要得到理想的结果，适当人工交互有时是必要的。 1 。2 。2 数据存储与压缩 数字几何模型的数据量往往较大，特别是通过三维激光扫描设备获取的模 型，其面片数目动辄数百万，甚至达到上亿个面片。此外，数字几何模型除了包 含坐标信息和连接关系之外，往往还包括法向量信息、颜色信息、材质信息等其 它辅助信息，这更加剧了数据存储的负担。实验结果表明，通用的压缩工具，例 第一章引言 如z l p 或者r a r 由于缺乏对数字几何模型内在数据特点的了解，一般不能获得理想 的压缩效果，这使得研究人员必须专门针对几何数据设计压缩算法 1 l6 】。目前的 几何压缩算法，一般将数字几何模型分解为三部分信息，即坐标信息、拓扑信息 和其它信息，并分别针对各种信息的特点设计专用算法。目前最好的几何压缩算 法，其压缩比可以高于通用z i p 算法两个数量级 3 】。 1 - 2 3 数据表示 在数字几何处理的各个子问题中，数据表示居丁核心地位，其原因是数据表 示决定了适宜采用何种计算模型来进行计算，同时也间接决定了适用于那些具体 应用类型。数据表示是数字几何处理中的一个热点问题，常见的数据表示方法参 见本章第一节。此外，为了处理包含海量基本单元的巨型模型。研究人员还提出 了一系列的多分辨率表示方法。所谓多分辨率表示方法 6 5 ，7 5 ，是通过简化技术 将一个精细的几何模型累进地降低精度，直到达到用户指定的闽值或能够为当前 的计算机所交互处理为止。累进简化的结果是原始模型的一个不同分辨率的累进 序列，其中的每一层次表示原始模型在一定分辨率下的逼近。多分辨率表示为巨 型模型的处理提供了一种解决方案，并且可以方便地推广到外存( o u t o f - c o r e l 处 理模式 1 0 0 】。 1 | 2 4 数据编辑 原始获取的数据一般难以满足特定应用的需求，这就需要对原始数据进行适 当的编辑处理。常见的几何编辑类型包括： 几何滤波：通过将离散f o u r i e r 变换 6 6 】或小波变换【1 1 4 】等推广到三维几何上 来，将三维模型的空间坐标转换成为频谱信号，从而可以针对特定的信号频段 进行处理，包括去噪、增强、带通带阻等具体滤波类型。问题的难点在于如何 定义三维几何的频谱以及具体的频谱分析方法。其他滤波技术包括双边滤波技 术 6 l ，4 1 】，基于曲率流的滤波技术 3 8 ，8 7 】和w i e r i i l e r 滤波技术【8 9 ，8 8 】和基于球面 调和函数的滤波技术 4 】等。 几何变形：研究如何高效地根据用户的设计意图将原始模型进行形变，常用 于计算机动画或三维特效的生成【99 ，1 2 6 ，1 2 2 】。问题的难点在于如何有效地理解 用户意图，并转换成为内在计算模型所需要的参数信息。考察算法好坏的指标主 要有两点，一是变形结果的质量。二是完成特定任务所需的用户交互工作量。 几何插值：研究如何在多个输入模型之间进行插值，从而生成一个随时问渐 变的序列，常用于计算机动画的生成 7 3 ，6 9 。问题的难点在于如何建立多个模型 之间的保持特征对应关系的映射，以及如何生成自然的符合物理运动规律的过渡 4 第一章引言 序列【6 9 】。 几何融合：将来自于不同模型的多个部分组件融合成为一个新的整体，常用 于原型数据的快速获取【8 5 ，4 5 】。问题的难点在于如何根据融合边界自适应地调整 各个组件的大小和形状以保持融合边界能够自然过渡。 几何信息重用：将源模型上的几何信息，如几何细节特征或者变形信息重用 于目标模型之上，常用于数据驱动的快速建模 2 4 ，1 1 1 】。问题的难点在于如何将 从源模型中抽取的几何信息自适应地调整，以保证能够适用于可能与源模型几何 相差较大的目标模型之上，并得到自然的重用效果。般为了保证几何信息重用 的质量，常常隐含要求源模型与目标模型基本相似。 几何重采样：由于原始模型的采样常常不能满足特定编辑操作的需求，为 此，需要根据具体应用的要求对原始模型进行重新采样 1 5 ，1 3 】。常见的重采样要 求包括采样密度均匀，采样密度随表面曲率自适应调整，顶点之间满足子分连接 关系等。问题的难点在于如何尽可能地降低重采样误差以及如何有效保持模型表 面的尖锐特征等。 1 2 5 数据绘制 这方面的研究旨在解决以各种形式表示的数字几何模型的绘制问题，将模型 组成的三维场景信息转换成为特定视点下的图像 1 】。不同表示形式的几何模型， 其绘制效率相差很大。由于目前的图形绘制硬件的设计要求，几何模型的各种表 示最终必须转换成为可绘制的基本单元三角形或者点，因此像隐式表示的几何模 型就必须先进行三角化之后才能进行绘制，从而影响了其绘制效率。而以三角网 格形式表示的几何模型则无需转换，直接进行绘制即可。此外，通过有效重组三 角网格顶点之间的绘制顺序，可以提高高速缓存的命中次数，从而显著提高绘制 效率。而对于数据绘制的另外一个重要衡量指标一一真实感，由于超出了本文的 研究范畴，这里不再介绍( 参见文献1 1 ) 。 1 2 6 数据检索 随着各种获取手段的丰富和增强，工业界和学术界每天都在创建新的几何模 型，其数量正在快速增长，目前已经达到相当规模。在这背景下，一个新的模 型创建方法适时地诞生了，它通过有效重组重用已有模型来实现快速建模 4 5 】。 成功运用该技术的前提是，计算机能够按照特定要求快速、准确地查找出目标备 选几何模型，这就是几何数据检索的研究目的。一个几何数据检索系统需要如下 几个关键技术 4 6 】： 数据搜集：数据检索是针对几何模型数据库进行的，这里有一个前提是几何 5 第一章引言 模型数据库是已经存在的。若不预先存在，则有个数据搜集的问题。目前的典型 解决方案有两类，一类是共享现成的商业或者科研数据库，另一类是通过网络搜 索器( c l a w e r ) 进行自动搜索和更新。 数据索引：对于数据库中已经存在的数据模型，必须进行索引化的工作，即 根据选定的特征组合方式，将原始模型转换成为一个相对较小的抽象指标集合， 用于代表原始模型。数据索引的设计，必须与用户交互方式以及数据匹配方式相 适应，即选择什么样的数据匹配方式，则需用户提供相应的交互信息作为输入， 同时也要求索引方式能够有效反映出待匹配模型的特征组合。 数据匹配：是数据检索应用中的核心技术，它直接决定了用户的交互方式和 数据索引的类型。数据匹配的核心是特征组合的选取，一般而言，单一特征难以 适宜复杂的检索需求，一个实用的系统往往选择一组特征构成特征组合集体作为 匹配对象。抽象的特征组合由相应的索引化函数转换成为数据索引，进而与索引 化后的用户提供的待检索特征组合信息进行一致性匹配，最终根据匹配程度的高 低将一系列候选匹配结果返回给用户。 图l3 数字几何处理的基本问题。( a ) 到( 0 分别代表数据获取 7 6 】，数据表示 5 0 】、数据 编辑 8 6 、数据绘制【1 0 3 】、数据存储 1 4 】和数据检索示例 4 6 】。 一般而言，广义的数字几何处理包括上述各个子问题，而狭义的几何处理则 特指数据编辑子问题。在本文后续章节中除非特别提及，我们采用几何处理的 狭义定义，即几何处理是几何数据编辑的同义词。此外，值得特别指出的是，本 文的研究工作主要侧重于数字几何处理的数据表示和数据编辑子问题。 6 第一章引言 1 ，3 数字几何模型的数据特点 以声音、图像和视频为代表的传统媒体有着一个共同的数据特点，即它们可 以看作是均匀采样定义在平坦欧氏空间中的函数而得到的信号。数字几何模型则 可以看作为非均匀采样任意曲面函数所得到的信号，其表达的信号的拓扑结构可 以是任意复杂的，即可以有任意的亏格数以及任意条边界。这导致数字几何模型 的数据特点显著区别于其它传统媒体，进而以f o u r