（计算机应用技术专业论文）polycube参数化自动构造与交叉参数化.pdf

浙江大学碗士学位论文 摘要 摘要 随着三维扫描技术的发展，三维网格模型成为几何造型和计算机图形学领域 中最通用的表示物体形状的方法，网格模型的处理成为热点研究内容。 网格参数化是网格处理中最基本的技术，它在网格与个恰当的参数域问建 立起一一映射。它是纹理映射、重网格化、曲面编辑、m o r p h i n g 等诸多网格处 理算法中最基本的步骤。 网格参数化方法按照参数域可以分为：平面参数化、球面参数化、单形 ( s i m p l i c i a l ) 参数化，以及最近提出的p o l y c u b e 参数化。p o l y c u b e 是由多个立方 体堆砌而成的形体，它简单而独特的结构使它具有以下优点：( 1 ) 通过对g p u 编程实现的投影机制，允许一个三角形跨越面片，并能进行纹理映射；( 2 ) 其参 数域由大小为2 ”的小正方形组成，便于m i p m a p p i n g 、存储、压缩以及重网格化； ( 3 ) 它可以较好地逼近网格形状从而减小参数化造成的扭曲。它是一种真正无 缝的参数化方法。 本论文重点研究p o l y c u b e 参数化的自动构造，以及基于p o l y c u b e 的交叉参 数化。本文的主要工作及贡献如下： 1 p o l y c u b e 参数化的自动构造 现有的p o l y e u b e 参数化技术采用手工指定p o l y c u b e ，再通过将曲面投影 到p o l y c u b e 上建立初始的参数化，然后优化。这需要大量的手工交互，影响 了p o l y c u b e 的广泛采用。本文提出了p o l y c u b e 参数化的自动构造技术。该算 法首先对网格进行特征分解，然后用立方体组成的一些基本形体逼近分解得 到的各部分网格区域，确定基本p o l y c u b e 的顶点和边在区域上的对应顶点和 路径，将各区域进一步分解为面片，从而在构造p o l y c u b e 的同时完成对曲面 的分片，最后再分片参数化并进行面片间的平滑，高效地实现了p o l y c u b e 的 自动参数化。 2 基于p o l y c u b e 的交叉参数化 许多应用要求在两个网格间建立起双射，即交叉参数化，例如m o r p h i n g 、 曲面细节传递、形状融合( b l e n d i n g ) 等。需要交叉参数化的两个网格通常具 有相似的特征，所以由两个网格自动构造的p o l y c u b e 通常也是相似的。直接 在两个p o l y c u b e 上建立双射，保持了两个模型间显著特征的对应。如果用户 浙江大学硕士学位论文摘要 在两个模型上指定了对应的特征点，算法调整面片边界，使得对应特征点在 两个网格上位于对应的面片，源网格直接参数化，目标网格中包含特征点的 矩形面片根据特征点进一步分割为三角面片，并将特征点的参数值固定为与 源网格相同，然后分片参数化。对于亏格不同的两个曲面，在允许奇异值存 在的前提下，该算法同样可以建立起映射关系，从而实现不同亏格的曲面间 的m o r p h i n g 。 本文的方法可以处理任意亏格的网格，其中的交叉参数化方法不仅适用于两 个网格间，还可直接用于实现带约束的纹理映射。 关键词：参数化、p o l y c u b e 、纹理映射、交叉参数化、m o r p h i n g i l 浙江大学硕：i 学位论文 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to f3 ds c a n n i n gt e c h n o l o g y , m e s h e sh a v eb e c o m ea w i d e s p r e a da n dp o p u l a rr e p r e s e n t a t i o no fm o d e l si nc o m p u t e rg r a p h i c s ，a n dm e s h p r o c e s s i n gt e c h n i q u e sh a v er e c e i v e dal o to f i n t e r e s tl a t e l y a p a r a m e t e r i z a t i o no fas u r f a c ec a nb ev i e w e da sao n e t o 。o n em a p p i n gf r o ma s u i t a b l ed o m a i nt ot h es u r f a c e ，w h i c hi sf u n d a m e n t a li nm a n ya r e a sd e a l i n gw i t h m e s h e s ，s u c ha st e x t u r em a p p i n g ，r e m e s h i n g ，m e s he d i t i n ga n dm o r p h i n g a c c o r d i n gt ot h ep a r a m e t e rd o m a i n a l lk i n d so fp a r a m e t e r i z a t i o nm e t h o d sc a n b ec l a s s i f i e di n t op l a n a rp a r a m e t e r i z a t i o n ，s p h e r i c a lp a r a m e t e r i z a t i o n ，s i m p l i c i a l p a r a m e t e r i z a t i o na n dt h er e c e n t l yp r o p o s e dp o l y c u b i cp a r a m e t e r i z a t i o n ap o l y c u b ei s as h a p ec o m p o s e do f a x i s - a l i g n e du n i tc u b e st h a ta r ea t t a c h e df a c et of a c e t h es p e c i a l s t r u c t u r eo f p o l y c u b el e a d st oas e a m l e s st e x t u r em a p p i n gm e t h o d i nt h i st h e s i s ，w en e s c n ta l la u t o m a t i cp o l y c u b i ep a r a m e t e r i z a t i o nm e t h o da n d p r o p o s eac r o s s - p a r a m e t e r i z a t i o na p p r o a c hb a s e do np o l y c u b e o u rm a i nw o r ka n d c o n t r i b u t i o n sc a nb es u m m a r i z e da st h ef o l l o w i n g ： 1 a u t o m a t i cp o l y c u b i cp a r a m e t e r i z a t i o n t h ee x i s t i n gp o l y c u b e - n m p sa r ec o n s t r u c t e ds e m i - a u t o m a t i c a l l yw h i c hn e e da l o to fu s e ri n t e r v e n t i o n w ep r o p o s ea na u t o m a t i cp o l y c u b i cp a r a m e t e r i z a t i o n f i r s t ，t h em e s hi sd e c o m p o s e di n t oas e to ff e a t u r er e g i o n s ，e a c ho fw h i c hi st h e n a p p r o x i m a t e db yas i m p l ep o l y c u b ea n ds p l i t t e di n t os e v e r a lp a t c h e sf u r t h e r e a c h p a t c hi sc o r r e s p o n d i n gt oar e c t a n g u l a rs u b s u r f a c eo ft h ep o l y c u b ew h i c hc a nb e p a r a m e t e r i z e di n d e p e n d e n t l y f i n a l l y , as m o o t h i n gp r o c e d u r eb e t w e e np a t c h e si s p e r f o r m e dt o r e d u c et h eo v e r a l lp a r a m e t r i cd i s t o r t i o n a tl a s t ，w eo b t a i nt h e p o l y c u b i cp a r a m e t e r i z a t i o ne f f i c i e n t l y 2 c r o s s p a r a m e t e r i z a t i o nb a s e do np o l y c u b e t h ea b i l i t yt o b i j e c t i v e l ym a po n em e s ht o a n o t h e ri su s e f u lf o rm a n y a p p l i c a t i o n s t h em o d e l sw h i c hn e e dt o b ec r o s s p a r a m e t e r i z e du s u a l l yh a v e s i m i l a rf e a t u r e sa n dt h ep a r a m e t e r i z a t i o nm u s tr e s p e c tt h o s e s i n c et h ep o l y c u b e s r e s e m b l et h es h a p eo ft h em o d e l s ，d i r e c t l ym a p p i n gb e t w e e nt h em a t c h i n g i l l 浙江大学硕p 学位论文a b s t r a c t r e c t a n g l e so ft w op o l y c u b e se a r lp r e s e r v et h el a r g ef e a t u r e so ft h em o d e l s i ft h e u s e rs p e c i f i e ss o m ef e a t u r ev e r t i c e s ，t h es o u r c em e s hi sp a r a m e t e r i z e df i r s t l y t h e n f o re a c hr e c t a n g l ec o n t a i n i n gf e a t u r ev e r t i c e s ，t h ea l g o r i t h mf i n d sat r i a n g u l a t i o n o ft h er e c t a n g l eo ft h es o u r c ep o l y c u b ea n dam a t c h i n gt r i a n g u l a t i o no ft h e c o r r e s p o n d i n gp a t c ho ft h et a r g e tm e s h t h e ne a c hp a t c ho ft h et a r g e tm e s hi s m a p p e dt ot h ec o r r e s p o n d i n gr e c t a n g l eo rt r i a n g l es u b - s u r f a c eo ft h es o u r c e p o l y c u b e ，a n dw eo b t a i nt h ef e a t u r ep r e s e r v i n gc r o s s p a r a m e t e r i z a t i o n w ec a n a l s ob u i l dm a p sw i t hs i n g u l a r i t i e sb e t w e e nm o d e l sw i t hd i f f e r e n tg e n u s o u rm e t h o d sw o r kw e l lf o rm e s h e sw i t h a r b i t r a r yg e n u s t h e c r o s s p a r a m e t e r i z a t i o nm e t h o dc a na l s ob eu s e dt oc o n s t r a i n e dt e x t u r em a p p i n gd i r e c t l y k e y w o r d s ：p a r a m e t e r i z a t i o n ，p o l y c u b e ，t e x t u r em a p p i n g ，c r o s s p a r a m e t e r i z a t i o n ， m o r p h i n g 浙江大学倾士学位论文 第一章绪论 第一章绪论 随着计算机辅助设计与计算机图形学的发展，三维几何数据作为一种新的数 据媒体，近十多年来在工业界、学术界都得到了广泛的研究和应用。多边形网格 成为最通用的表示物体形状的方法。研究者们提出了很多处理网格模型的算法， 如去噪声、编辑、几何压缩、网格简化和纹理合成，来满足各种各样的应用需求。 其中网格参数化是网格处理中最基本的技术，它是对网格的几何和拓扑信息作进 一步处理的基础。 接下来，我们将介绍参数化的一些基本知识及应用，前人的相关工作，以及 本文的主要研究内容。 1 1 参数化的研究范畴和应用领域 参数化本身是一个很古老的问题，人们最早把这种技术应用在测地学、绘图 学等领域。随着计算机技术的飞速发展和制造业与多媒体娱乐应用的推动，它在 计算机图形学领域已占据举足轻重的地位，成为国际学术界一个前沿研究领域。 曲面参数化是指在曲面与一个恰当的参数域间建立起一一映射 【f l o a t e r 2 0 0 5 。这个参数域也是一个曲面，因此参数化实际上是建立从个曲面 到另一个曲面的映射。 参数化的质量对基于其上的应用有着重要影响。人们通常使用一些几何的内 在属性( 如长度、角度和面积等) 的变形程度来衡量参数化的好坏。根据微分几 何可知，等积映射( i s o m e t r i cm a p p i n g s ) 是最理想的参数化。如图u 所示，假 定s 是具有坐标( “1 ，“2 ) 的曲面，厂是从s 到另一个曲面驴的映射。如果s 上任意 弧线的长度与s 上相等，则从s 到s + 的映射称为等积的或长度保存的。当且仅 当两个曲面的第一基本形式的系数相同，该映射是等积的。两个等积曲面在对应 点具有相同的高斯曲率。等积映射是理想的映射，因为它保存了角度、面积和长 度。但等积映射只存在于少数特殊的情况，所以许多参数化技术寻求保角、保面 积，或者最小化角度扭曲与面积扭曲的组合。 参数化在许多数字几何处理算法中都是一个最基本的步骤，它最重要的应用 是纹理映射【星k 墨i 曼i 堡嫂! 】【量型y 2 鲤! 】【壁受垫蚓【垫趔2 壁竖】。纹理映射利用参数 化信息，将一幅图象映射到几何表面上，可以有效地模拟和增强物体表面的细节 浙江大学硕十学位论文 第一章绪论 特征，增加模型的真实感。图监显示了模型纹理映射的效果。 l 们 一| 图1 1 从s 到s 的映射，与s 的参数化x 诱导了，的参数化x + = 厂。x 。 f l o a t e r 2 0 0 5 图1 , 2 纹理映射。左图 垫q 女2 q q 5 】，右图 坠疆2 q q 2 】 参数化的另一个应用是重网格化【趟! i z 2 q q 羽【鱼丛2 q q 2 】 s u r a z h s k y 2 0 0 3 p r a u n 2 0 0 3 。重网格化使用具有细分连接结构的三角形网格去逼近一个给定的三 角形网格，这种特殊的结构使得模型的显示、存储、传输、编辑更加有效。重网 格化通常要求先将曲面参数化到一个平面区域，再进行重采用( 图量量) 。 图1 3 重网格化唑! ! i z 2 q 蝗 浙江大学硕j 学位论文第一章绪论 在许多曲面编辑技术中 b i e r m a x m 2 0 0 2 】【l e v v z 0 0 3 ，通常要求对编辑区域做 一个局部参数化( 图) 。 图1 4 曲面间的剪贴 1 e v v 2 0 0 3 曲面拟合 f l o a t e r l 9 9 8 j 1 噩过参数化把离散的三维数据点用一个光顺的三维曲 面来拟合。还有很多数字几何处理，如交互式三维绘画 c a r r 2 0 0 4 、网格 m o r p h i n g 幽 幽 s h l a f m a n 2 0 0 2 等，都需要首先进行参数化。 1 2 参数化相关工作介绍 根据审视问题的角度不同，网格参数化方法基本有以下几种分类彭群生 2 q 鲣】：( 1 ) 根据参数域的不同可以分为平面参数化、球面参数化和单形参数化； ( 2 ) 根据网格的拓扑信息可以分为带边界网格参数化和封闭网格参数化，甚至 是任意拓扑的网格参数化；( 3 ) 根据不同的内在几何变量的变形，可以分为保角 参数化、保面积参数化和等距参数化；( 4 ) 根据计算复杂度不同，可以分为线性 方法和非线性方法；( 5 ) 局部参数化和全局参数化方法等。 下面，我们主要以所采用的参数域为主线，介绍各种参数化方法。 1 2 1 平面参数化 平面参数化方法用于参数化拓扑同胚于圆盘的曲面，它在益面与平面间建立 起一一映射。这是最重要也是最基本的参数化类型。对于不可展瞌面，平面参数 化必然产生扭曲。 最早的平面参数化方法之一是e c k 提出的离散调和映射 e 盘1 2 堑】。该方法 使用基于线性元素的有限元方法来逼近调和映射。它需要首先固定曲面边界，然 浙江大学倾士学位论文 第一章绪论 后最小化d i r i c h l e t 能量。离散调和映射函数被广泛地用来参数化网格，因为只需 求解线性方程组，但其并不能保证得到有效的一一映射。 f l o a t e r 提出了曲面的凸组合参数化方法 f l o a t e r l 9 9 7 ，所有内点由其周围相 邻点进行凸组合得到。2 0 0 3 年f l o a t e r 根据调和映射的中值定理，提出了改进的 中值坐标法 f l o a t e r 2 0 0 3 ，所有内点仍是由其周围顶点的凸组合得到，但是其权 系数的取法不仅与边长相关，还与三角形内的角度有关。此方法自提出后得到广 泛采用，因为它计算简单，且参数化效果与离散调和映射参数化结果相似，并且 能够保证映射的有效性。 在使用上面的方法参数化网格时，首先需要将网格的边界点映射到二维凸多 边形的边界。以下的方法在参数化时不需要预先固定边界，而是将边界点包含在 整个优化问题中求解。 h o r m a n n 和g r e i n e r 提出了一个全局的非线性不定边界方法( m i p s ：m o s t i s o m e t r i cp a r a m e t e r i z a t i o n s ) h o r m a n n 2 0 0 0 ，通过最小化一个能量函数得到尽可 能保角的映射。s h e f f e r 和s t u r l e r 提出基于点的优化方法( a b f ：a n g l e b a s e d f l a t t e n i n g ) s h e f f e r 2 0 0 1 ，其目标函数由三角形内的角度定义。将三维网格展平 时，作者希望将角度的变形能够均匀地分布在顶点周围，从而达到较好的映射效 果。 l e v y l e v v 2 0 0 2 和d e s b r u n d e s b r u n 2 0 0 2 分别独立地提出了计算离散保角映 射的线性方法。这两个线性方法可以快速地计算出角度变形较小的参数化，其纹 理映射效果优于离散调和映射和凸组合映射，但是不同于m i p s 和a b f 方法， 这些线性方法不能保证展平的三角形没有重叠。 d e g e n e r 扩展了m i p s 方法 d e g e n e r 2 0 0 3 ，其参数化函数既考虑了角度扭曲， 也考虑了面积扭曲，通过在目标函数中引入权重参数来控制保角或保面积的相对 重要性。 为了使三维网格曲面在参数空间采样尽量均匀，s a n d e r 提出了基于拉伸 ( s t r e t c h ) 的目标函数 s a n d e r 2 0 0 1 。此方法不仅减少了面积变形，同时还体现出一 定的保角性。 以上方法都是基于表面几何特征来度量参数化质量的。但表面信号如颜色、 法向、表面位移或者表面光照等，在参数化时也产生扭曲，其扭曲与几何扭曲常 4 浙江大学硕士学位论文 第一章绪论 常并不一致。s a n d e r 提出了直接根据三维表面信号来进行参数化的方法，通过最 小化信号误差，从而给表面细节丰富的区域分配更多的纹理空间 s a n d e r 2 0 0 2 】。 要处理一个封闭的曲面要求将皓面分割为一个或多个同胚于圆盘的部分，每 部分再单独参数化( 图1 5 ) 。但这不可避免地导致曲面参数值的不连续，即面片 边界处的纹理将出现断裂的缝隙。因此在分割曲面时，既需要考虑如何分割使每 块面片参数化扭曲较小，同时还要尽可能隐藏缝隙【p i p o n i 2 0 0 0 l e v v ：! q q 至】【s 照星旦童2 q q 2 【2 鱼旦旦2 q q 垒】。 1 2 2 球面参数化 图1 5 分片纹理映射【址删2 咝】 对于封闭的、亏格为0 的曲面，球面是一种自然的参数域，因为它不需要将 曲面分割( 图l ) 。球面参数化可应用于构造连续的细节纹理集或者几何图像 鱼巡】。很多方法在球面上模拟平面上的保角( 或调和) 映射，只是一些平面 上的线性方法变成了非线性的。 h a k e r 等人提出了计算从曲面到球面的全局保角映射 h a k e r 2 0 0 0 。该方法首 先将曲面映射到平面上，然后通过立体投影再将平面映射到球面上。该方法的局 限性是：使用分段线性映射来逼近非线性的立体投影会引入误差，可能导致计算 的不稳定。2 0 0 2 年，z h o u 和b a o 等人提出了任意网格的统一数字几何处理框架， 为任意网格模型构造一个全局球面参数化【堇h q 坠2 q q 2 】。g u 和y a u 等人提出了一 个逼近调和映射的迭代算法对曲面进行全局参数化 鱼正盟劲，此算法无须分割曲 面。g o t s m a n 等人提出了基于凸组合的球面参数化方法 g o t s m a n 2 0 0 3 ，把平面 向量的凸组合概念扩展到球面向量上。s h e f f e r 等人将平面a b f 方法扩展到球面 上【s h 照1 2 q q 3 】，由于此方法需要求解一个带约束的非线形系统，运行时间较长。 浙江大学硕士学位论文 第一章绪论 p r a u n 等人将s a n d e r 提出的s t r e t c h 度量【s a n d e r 2 0 0 1 】扩展到球面参数化上 【p r a u n 2 0 0 3 。 球面参数化的缺陷是扭曲较难控制。 1 2 3 单形参数化 图1 6 球面参数化巴堂! 蝗q q 3 】 一种对任意曲面都通用的方法是将模型参数化到一个同胚的基网格( b a s e m e s h ) 上【曼丛! ! 1 5 】【l 曼曼1 2 2 翱 塑! 坦2 q q ! 。该方法首先将网格分割成面片，面片 通常类似于三角形，每块面片再映射到基网格的每个三角形上。该方法重点需要 解决的问题是如何获得平滑跨越面片边界的参数化。k h o d a k o v s k y 等人，以及g u 等人提出的两种全局参数化方法【l 鱼q d 巫q y 虹2 q 妲】 鱼旦2 q 盟】较好地解决了这个 问题，可以生成全局光滑的参数化结果，仅在少数特殊点上才出现奇异点( 图 1 7 ) 。 图1 7 单燃q g k h o d a k o v s k y 2 0 0 3 t a r i n i 等人通过扩展c u b em a p 的概念，提出了p o l y c u b e 参数化方法 【t a r i n i 2 0 0 4 】。p o l y c u b e 是一种由立方体组成的三维形体。该方法为每个网格建立 6 第一章绪论 p r a u n 等人将s a n d e r 提出的s t r e t c h 度量 s 塑d ! 丝q q ! 扩展到球面参数化上 【麴出2 q q 3 】。 球面参数化的缺陷是扭曲较难控制。 1 2 3 单形参数化 图1 6 球面参数化 鲤蛔2 q 监l 一种对任意曲而都通用的方法是将模型参数化到一个同胚的摹网格( b a s e m e s h ) j 2 e c k l 9 9 5 p r a u n 2 0 0 1 。该方法首先将网格分割成面片，面片 通常类似于2 角形，每块面片再映射到基网格的每个三角形上。该方法重点需要 解决的问题是如何获得平滑跨越面片边界的参数化。k h o d a k o v s k y 等人，以及g u 等人提出的两种全同参数化方法【l 鱼q d 吐q ! s 虹2 q q 到【g 2 q q 3 】较好地解决r 这个 问题，q 以生成全局光滑的参数化结果，仅在少数特殊点上才出现奇异点( 图 1 7 ) 。 图1 7 单形参数化匹b q d 韭q ! ! 虹2 q 业 1 3p o l y c u b e 参数化 t a r l n l 等人通过扩展c u b em a p 的概念，提出了p o l y c u b e 参数化方法 【t a r i n i 2 0 0 4 。p o l y c u b e 是一种由立方体组成的2 维形体。该方法为每个网格建立 【t a f i n i 2 0 0 4 。p o l y c u b e 是一种由立方体组成的= 维形体。该方法为每个网格建立 6 浙江大学硕十学位论文 第一章绪论 一个形状大致相似的p o l y c u b e 作为参数域，表面网格通过投影映射到p o l y c u b e 表面，p o l y c u b e 表面又通过适当的分割后映射到二维纹理空间( 图l 墨) 。该方法 最大的优点是实现了无缝的纹理映射，避免了c h a r t 边界的不连续性。并且它可 以处理任意亏格的模型。 ( a ) 原模型 ( b ) p o l y c u b e 映射( c ) 对偶单元格( d u a lc e l l ) 切割 ( d ) 纹理图像 图1 8p o l y c u b e 参数化【鱼j 画2 q q 4 】 p o l y c u b e 的主要特点是： 1 每个纹理块都是2 次幂的正方形，有利于m i p m a p 的实现，便于纹理封装。 2 允许网格上的一个三角形跨越不同的纹理片。 前面提到的单形参数化虽然是一种无缝的参数化，但是当用于纹理映射时， 一个跨越不同面片的三角形，其内部由线性插值得到的纹理坐标将是悬空的，在 纹理空间中没有定义。p o l y c u b e 映射对此问题的解决方法是：模型上的每个项点 具有一个3 d 参数值。当进行纹理映射时，由三角形3 个顶点插值得到的片元的 纹理坐标，如果是悬空的，则通过图l 曼为每个单元所定义的投影方向，投影到 p o l y c u b e 表面。该投影过程是在f r a g m e n ts h a d e r 中实现的。 图1 9p o l y c u b e 的单元投影方向 里堑i 2 q q 蝴 p o l y c u b e 参数化既可以较好地逼近曲面形状从而减小参数化造成的扭曲，其 参数域又便于存储和压缩。它是一种理想的几何图像叵丛垫q 刭，除了纹理映射， 浙江大学硕士学位论文第一章绪论 也可以用于重网格化、网格信息的存储和压缩等领域。 但目前，p o l y c u b e 参数化的建立还没有完全自动的方法，其构造过程需要 大量用户交互。用户首先指定与模型大致相似的p o l y c u b e 作为参数域，然后移 动p o l y c u b e 的顶点使之大致包围模型，接着将模型顶点投影到变形后的p o l y c u b e 上，再通过逆变形将顶点映射到原来的p o l y c u b e 表面，从而获得了模型到 p o l y c u b e 的初始的参数化。最后对初始的参数化进行优化( 图l 卫) 。 图1 1 0p o l y c u b e 映射的构造过程 显d b i 2 q 丝】 1 4 本文的主要研究工作和内容 本论文重点研究p o l y c u b e 参数化的自动构造，以及基于p o l y c u b e 的交叉参 数化。本文的主要工作及贡献如下： 1 p o l y c u b e 参数化的自动构造 现有的p o l y c u b e 参数化技术需要大量的手工交互，影响了p o l y c u b e 的广 泛采用。本文提出了p o l y c u b e 参数化的自动构造技术。该算法首先对网格进 行特征分解，然后用立方体组成的一些基本形体逼近分解得到的各部分网格 区域，确定基本p o l y c u b e 的顶点和边在区域上的对应顶点和路径，将各区域 进一步分解为面片，也即建立起p o l y c u b e 上的矩形与曲面的面片间的对应， 在构造p o l y c u b e 的同时完成了对曲面的分片。最后再分片参数化并进行面片 间的平滑，高效地实现了p o l y c u b e 的自动参数化。 2 基于p o l y c u b e 的交叉参数化 许多应用要求在两个网格问建立起双射，即交叉参数化，例如m o r p h i n g 、 曲面细节传递、形状融合( b l e n d i n g ) 等。需要交叉参数化的两个网格通常具 8 浙江大学硕士学位论文 第一章绪论 有相似的特征，所以由两个网格自动构造的p o l y c u b e 通常也是相似的。直接 在两个p o l y c u b e 上建立双射，保持了两个模型问显著特征的对应。如果用户 在两个模型上指定了对应的特征点，算法调整面片边界，使得对应特征点在 两个网格上位于对应的面片，源网格直接参数化，目标网格中包含特征点的 矩形面片根据特征点进一步分割为三角面片，并将特征点的参数值固定为与 源网格相同，然后分片参数化。对于亏格不同的两个曲面，在允许奇异值存 在的前提下，该算法同样可以建立起映射关系，从而实现不同亏格的曲面间 的m o r p h i n g 。 本论文共分为四章。本章介绍了参数化的研究背景、相关工作。第二章介绍 了本文有关p o l y c u b e 参数化自动构造方面的工作。第三章介绍了基于p o l y c u b e 的交叉参数化。第四章总结了现有工作，简单余绍了未来可能的研究方向。 浙江大学硕士学位论文第二章p o l y c u b e 参数化的自动构造 第二章p o i y c u b e 参数化的自动构造 p o l y e u b e 参数化中，p o l y c u b e 的指定、p o l y c u b e 变形都需要手工交互，且通 过投影获得的初始参数化可能存在翻转和重叠，对模型上法向变化很大的区域该 问题更加严重。虽然可以通过与相邻顶点平滑来减轻翻转现象，但无法保证完全 纠正。 为了使p o l y c u b e 参数化能在实践中得到广泛应用，本论文提出了p o l y c u b e 参数化的自动构造算法，首先通过网格分解，将网格分割成一些简单区域，在对 每个区域分别构造p o l y c u b e 的同时，完成对区域曲面的分片，使曲面具有与 p o l y c u b e 一致的面片结构。然后对盟面分片参数化，最后进行全局优化。该算法 与单形参数化方法有相似之处，即都需要对模型分片，每片再分别参数化。它与 单形参数化的区别在于，每个面片都是矩形，且面片结构必须符合p o l y c u b e 的 规则。这也是p o l y c u b e 参数化与单纯的将模型分割成四边形面片参数化方法 【c a r r 2 0 0 4 的区别。 2 1 基本定义 在计算机图形学中，多边形网格是最通用的表示物体形状的方法。它便于计 算和处理，可以任意精度逼近一曲面物体，并可采用硬件加速。本文的研究对象 就是多边形网格模型。因为任意多边形可以方便地分割为三角形，我们只处理三 角形网格模型。下面，为了表述清晰，我们给出与本文相关的一些基本概念的定 义。 1 网格：网格由一个二元组m = ( k ，y ) 表示，其中世是表示网格中顶点、 边、面的连接关系的单纯复形，净( v l ，v 。) 表示网格顶点在三维空间的几何位置。 k 的元素分三种类型：顶点 i ，边e = f ， 和面f = f ，k ) 。如果 j ，) k ，则 顶点 f ) 和 n 被称为邻居。顶点 i 的1 环邻居被定义为( f ) = j l f ，以k ) 。如 果一个顶点的l 环邻居( f ) 构成一个顶点环，这样的顶点被称为内部顶点。如果 构成半环，则为边界顶点。本文只处理封闭的流形网格，对于不封闭的网格，我 们首先将网格边界封闭再做处理。 浙江大学硕上学位论文第二章p o l y c u b e 参数化的自动构造 2 p o l y c u b e ：p o l y c u b e 是由与坐标轴方向平行的彼此相邻的单位立方体拼 合而成的形体。我们将单位立方体的边长称为单位长度。 3 亏格：如果网格是封闭的( 即所有顶点都是内部顶点) ，则网格上柄 ( h a n d l e ) 的数目称为亏格。设网格顶点数、边数和三角形数分别为m 、m 和， 其亏格( g e n u s ) g 可定义如下：g = ( m m m + 2 ) 2 。任意球面网格的亏格都 为0 ，环的亏格为1 。 4 区域：我们根据特征点将网格分割成一些具有明显意义的简单形体。分 割得到的每块子网格称为一个区域，将区域与网格其余部分分离的边界称为区域 边界。本文将区域边界映射到一个矩形，与矩形4 个顶点对应的区域边界上的点 称为边界顶点。 5 面片结构：网格的面片结构是根据网格上一系列的顶点和边路径将网格 分割成互不重叠的面片而得到的。本文中的面片都是类似于矩形的，且面片结构 与网格对应的p o l y c u b e 是拓扑一致的，即网格上的一块面片对应着p o l y c u b e 表 面的一块矩形，面片边界对应着矩形边，面片的顶点对应矩形的顶点。 6 分离环：分离环是曲面上的一条封闭曲线，它能将网格分割成两个分离 的区域。对亏格为0 的网格，网格上的一条封闭曲线一定是分离环。但对于亏格 大于0 的曲面，还存在非分离环( n o n s e p a r a t i n gc y c l e ) ，它不能将网格分割成两 部分，但是沿非分离环将网格切开，能将网格的亏格减1 。 2 2 网格分解 网格分解是指将网格分割成一些更简单的形体，它在网格造型 f u n k h o u s e r 2 0 0 4 、m o r p h i n g g r e g o r y l 9 9 9 s h l a t i n a n 2 0 0 2 、简化 g a r l a n d 2 0 0 1 、 三维形体检索【旦! 9 4 2 鲤! 】、冲突检测 l i 2 嫂! 】、骨架抽取区匹z 2 q q 3 】等应用中经 常被采用。网格分解的方法有很多【l i 2 q q ! 】 s h l a f m a n 2 0 0 2 _ 】区呶2 q 鳗 _ s h a m i r 2 0 0 4 幽【k a 丝2 q 盟】。由于p o l y c u b e 的亏格必须与模型一致，才 能建立有效的参数化，所以我们选择网格分解方法的基本出发点是能识别出网格 的亏格，以便将柄与网格主体分离，再分别用p o l y c u b e 逼近。 本文中我们主要采用z h a n g 等人提出的特征识别方法进行网格分解 浙江大学硕士学位论文 第二章p o l y c u b e 参数化的自动构造 丛鲤9 2 q 笾】，它能将网格分割成一些明显的特征区域，并且可以很方便地处理 亏格大于0 的模型。该方法首先根据平均测地距生成r e e b 图，再根据r e e b 图减 少亏格并做特征分割。 我们对 垫盟9 2 q 盟】中r e e b 图的生成进行了改进，能根据指定的阈值过滤掉 用户不希望考虑的较小的特征，识别出模型上显著的特征，使生成的r e e b 图更 加清晰。在亏格减少的步骤中，我们改进了非分离环的生成以获得更短更光滑的 非分离环，从而更容易对模型切割。 2 2 1 计算平均测地距 平均测地距( a v e r a g eg e o d e s i cd i s t a n c e ) 函数由h i l a g a 引入用于形状匹配 【h i l a g a 2 0 0 1 。令g ( p ，q ) 为曲面s 上两点p 和q 问的测地距。则点p 的平均测地 距a g d 定义为： 饰，：雩筹 ( 2 1 ) 一g d ( p ) = = 志 ( 2 2 ) a g d 的值度量了一个点与曲面其余部分的偏离程度，该值是拉伸不变的， 便于不同模型间的比较。我们使用a g d 来识别和度量模型的几何特征。它的局 部极大值对应着模型上突出部位的尖点。该值越大，突出越显著( 见图2 1 ( 左) ) 。 计算一个顶点的a g d 值我们采用s u r a z h s k y 等人提出的快速计算测地距方 法 s u r a z h s k 3 , 2 0 0 5 。为网格上所有顶点计算a g d 较耗时，我们采用h i l a g a 等 人提出的近似算法阻i 1 4 9 2 q q ! 】，只需实际计算曲面上均匀分布地少量采样点 ( 1 5 0 个顶点左右) 的测地距。 2 2 2 构造胁e b 图 为了检测模型的柄和显著的突出部位，我们对网格的a g d 函数进行拓扑分 析，根据a g d 函数构造一个嵌入的r e e b 图r 。r 的叶节点对应突出部位的尖点， f 中的环揭示了柄的存在。我们按a g d 的升序从全局最小点执行区域增长，跟 1 2 浙江大学硕士学位论文第二章p o l y c u b e 参数化的自动构造 踪区域边界的拓扑变化，来构造r e e b 图。 图2 1 左图：b u n n y 上的a g d ( 红、绿、蓝、黄、紫、白表示a g d 值由小到大的等值带) 。 中图：基于a g d 按区域增长生成的嵌入的r e e b 图( 淡蓝：全局极小点，红：局部 极大点，蓝：分裂鞍点) 。相邻的临界点由曲面上的路径连接，路径用黄色 ( 可见的) 和淡黄色( 隐藏的) 显示。 右图：区域分割的结果。 2 2 2 1r e e b 图的定义 r e e b 图是一个模型的拓扑和骨架结构。令厂：s - - r 是定义在曲面s 卜的一 个连续函数，p 、q 为s 上的两个顶点，在s 上定义等价关系：p 1 当且仅当f l p ) 亏，( q ) 且p 、q 属于厂1 侦p ) ) 的同一个连通分量。则r e e b 图是由该等价关系定义的s x r 的商空间。 函数_ 厂不同，得到的r e e b 图也不同。使用较多的函数有高度函数和基于测 地距的函数。图2 量是一个曲面上的高度函数所对应的r e e b 图的例子。 图2 2 在亏格为1 的曲面上根据高度函数得到的r e e b 图 垫堑9 2 q q 习 r e e b 图经常用于分析曲面的拓扑，许多应用中都使用到r e e b 图，例如形状 匹配【! a g a 2 q q ! 】、拓扑简化【鞘殴巡】、由轮廓线重建曲面 s 丛n a g a 盟1 2 91 】、 浙江大学硕十学位论文第二章p o l y c u b e 参数化的自动构造 构造中轴线 l a z a r u s l 9 9 9 j 等。本文中构造r e e b 图的目的是揭示曲面中柄与突出 部位的位置，作为后续的亏格减少和区域分割的基础。 2 2 2 2r e e b 图的生成过程 在【姜h 熙9 2 嫂勃中r e e b 图的生成过程为：首先计算每个顶点的a g d ，一个 三角形的a g d 取为3 个顶点中最小的a g d 。从a g d 最小的三角形开始，按 a g d 的升序一次加入一个三角形，直到曲面完