（计算机应用技术专业论文）模型分割与参数化的纹理合成.pdf

摘要 摘要 模型纹理绘制技术是绘制真实感图形最为常用的重要技术之一，它能有效模拟和增 强景物表面的细节特征，而不需要增加几何模型的复杂度，在三维游戏动画、虚拟现实、 计算机辅助设计等领域有着广阔的应用前景。本文对生成模型纹理的主要技术进行深入 研究，内容包括参数化、模型分割以及基于样图的纹理合成。 本文首先研究了曲面参数化问题，针对纹理映射中的纹理变形问题。提出了基于模 型上相邻三角面关系的纹理合成方法。该方法根据模型上相邻三角面的关系，采用广度 搜索策略依次为每个三角面指定纹理坐标。对于具有约束面的搜索与映射过程，首先搜 索纹理使约束面具有最小的纹理误差，最后采用图的分割技术将纹理拼接成一个连续的 整体。 本文还研究了纹理合成的模型分割方法。提出了基于法向评价的分割方法。该方法 根据模型上各相邻三角面的法向以及平均曲率，采用广度优先策略将模型划分。在划分 中采用正向投影映射将各模型块参数化并对其进行评价，对于具有较大扭曲的模型块， 将其再次细分直到扭曲值满足给定的阀值。最后采用相似堆积度合并分割的模型块。本 文将该方法结合参数化的理论，将其应用在模型纹理的绘制上。 通过对模型纹理绘制的研究表明，本文提出的两种纹理合成的方法，不但保持了纹 理原有的特性，并且对于纹理的接缝问题也能较好的处理。因此本文的方法能有效的处 理该类问题。 关键字：纹理映射；纹理合成；图的分割：参数化：三角网格：模型分割 a b s t r a c t m o d e lt e x t u r i n gt e c h n i q u ei so n eo ft h em o s tp o p u l a rt e c h n i q u e so fr e a l i s t i cg r a p h r e n d e r i n g i tc a ne f f i c i e n t l ys i m u l a t et h ed e t a i l so f3 ds u r f a c e sw i t h o u ti n c r e a s i n gt h e c o m p l e x i t yo f t h eg e o m e t r i cm o d e l ，s oi th a sb e e nw i d e l ya p p l i e di nm a n yf i e l d ss u c ha s3 d g a m e ，c o m p u t e ra n i m a t i o n ，v i r t u a lr e a l i t y ，c o m p u t e ra i d e dd e s i g n ( c a d ) a n ds of o r t h i nt h i s t h e s i s ，w ed e e p l yr e s e a r c ho ns o m em o d e lt e x t u r i n gt e c h n i q u e s ，s u c ha sp a r a m e t e r i z a t i o n ，3 d m o d e ls e g m e n t a t i o na n dt e x t u r es y n t h e s i sf r o ms a m p l e s f i r s t l y , w er e s e a r c ho naq u e s t i o no fs u r f a c ep a r a m e t e r i z a t i o n t or e s o l v et h et e x t u r em a p p i n gf o r t e x t u r ed i s t o r t i o np r o b l e m , w ep r o p o s ean o v e lt e x t u r es y n t h e s i sm e t h o d b a s e do nt h er e l a t i o no f t h en e i g h b o r i n gt r i a n g u l a t e ds u r f a c e so fm o d e l ，w eu s ea ne x t e n tp r e f e r e n t i a ls e a r c hs t r a t e g y t oa p p o i n tt e x t u r ec o o r d i n a t eo fe a c ht r i a n g u l a t e ds u r f a c e i nt h ep r o c e s s e so fs e a r c h i n ga n d m a p p i n gh a v er e s t r i c t e ds u r f a c e s ，f i r s t ，w es e a r c ham i n i m a lt e x t u r ee r r o ro fr e s t r i c t e d s u r f a c e s ，t h e n ，j o i n tt h et e x t u r e si n t oas e q u e n t i a lm a c r o c o s mb yu s i n gg r a p he a tt e c h n i q u e s e c o n d l y , an o r m a le v a l u a t i o nm e t h o do fs e g m e n tm o d e lf o rt e x t u r es y n t h e s i si s p r o p o s e d b a s e do nt h ev e c t o ra n dm e a nc u r v a t u r eo ft h en e i g h b o r i n gt r i a n g u l a t e ds u r f a c e so f m o d e l ，w eu s ee x t e n tp r e f e r e n t i a ls e a r c hs t r a t e g yt os e g m e n tt h em o d e l w eu s eo r t h o g r a p h i c p r o j e c t i o nm a p p i n gt op a r a m e t e r i z ea n de v a l u a t i o nf o re a c hm o d e lb l o c k w h e nt h em o d e l b l o c kh a sl a r g ed i s t o r t i o n w ec a nf r a c t i o n i z et h eb l o c ka g a i nu n t i ld i s t o r t i o nv a l u ea c h i e v e s t h et h r e s h o l dv a l u e f i n a l l y ，w eu s ed e g r e eo fs i m i l a ra c c u m u l a t i o nt ou n i t es o m eo fm o d e l b l o c k t h em e t h o di sc o m b i n e dt h e o r yo fp a r a m e t e r i z a t i o na n da p p l i e di nm o d e lt e x t u r i n g r e n d e r i n g t h er e s e a r c ho ft h em o d e lt e x t u r i n gt e c h n i q u e si n d i c a t e st h et w om e t h o d sp r o p o s e db y t h et h e s i sn o to n l yk e e pt h ec h a r a c t e r i s t i co ft e x t u r e ，b u ta l s oh a v eb e t t e rt r e a t m e n tf o rt h e s e a mo ft e x t u r e t h e r e f o r e ，o u rm e t h o d sa r ee f f i c i e n tf o rm o d e lt e x t u r i n gr e n d e r i n g k e yw o r d s ：t e x t u r es y n t h e s i s ；t e x t u r em a p p i n g ；g r a p hc u t ；p a r a m e t r i z a t i o n ； t r i a n g u l a rm e s h e s ；m o d e ls e g m e n t a t i o n 独创性声明 本人声明所呈交的学位论文是拳人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签名：龇硼吾。弓。，基 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定。 签名： 导师签名： 鲤 幺垒墼兰日 期：芴z , - z , 3 。多。，吕 第一章绪论 在现实世界中任何物体都有其外形与纹理。通过计算机能够模拟其物体以及形态 但是由于物体的很多特性是由一个复杂的物理过程形成( 如：划痕，油污等) 。因此物体 的建模在这种情形下变得异常的复杂与枯燥并且使得需要处理的数据增多。在这种情 形下，一般采用一个较为简单的模型来表达一个现实世界中较为复杂的物体模型中的 细节通过纹理来加以描述。这样不但使得建模更为轻松，更重要的是需要处理的数据量 大大减少。但是由于纹理的多样性使得模型上的纹理总是不能较好得表述。因此对于三 维纹理合成直是当今世界上一个热点问题。 纹理映射( t e x t u r e m a p p i n g ) 是使用图像、函数或者其他数据源来改变物体表面外观， 是将空间三维点转化为纹理坐标。纹理合成( t e x t u r es y n t h e s i s ) 是为了解决纹理腴射中 存在的接缝变形以及纹理的获取等问题而提出的，是对样本纹理的重建和再组织。纹理 映射与合成是当今世界上最常用的技术。 l t l 纹理简介 1 1 i 纹理的定义及分类 在计算机图形学领域内，纹理通常是指在局部区域内呈现不规则性，而在整体上表 现出某种规律性的特殊图像。纹理和图像是不同的，纹理显然是图像，但并不是所有的 图像都是纹理。如图1 1 所示，图1 - 1 ( a ) 是一副l e n a 图像，图1 - 1 ( b ) 是一种纹理。我们 通过较小的窗口( 图1 1 中的白色线框) 来观察它们。显然，对于图1 - 1 ( a ) 所示的普通图像， 从不同位置的窗口看到的子图像具有明显区别；而对于图1 - l e o ) 所示的纹理图像，从不 同位置的窗口看到的子图像则十分相似。因此纹理图像具有以下两个特征： ( 1 ) 稳定性：不同区域的纹理都彼此相似。 ( 2 ) 局部性：图像中的任一像素的颜色可以由其周围邻域内的像素预测得到。 ( a ) 普通翻像( b ) 纹理图像 图1 - 1 普通图像与纹理的区别 由于纹理图像来源的广泛性，其形式也是千变万化的。因此也就具有不同的分类标 准。根据纹理的表现形式，纹理可以分为：颜色纹理、过程纹理和几何纹理三大类。其 中颜色纹理主要包括呈现在物体表面上的各种花纹，图案和文字等，如大理石墙面，墙 上贴的字画，器皿上的图案等；过程纹理是指用过程来表现规则或不规则的动态变化的 自然景象，如水波、云、水和烟雾等的：几何纹理则是指基于景物表面微观几何形状的 蕊 南大学硎i ：学位论空 表面纹理，如桔子、树干和岩石等表面呈现的凹凸不平的纹理细节。 根据纹理特征分布的方式不同，按照能否从其内部分辨出纹元，可以把纹理分为三 类【1 ：结构性纹理，随机性纹理，以及半结构半随机性纹理。结构性纹理是出固定纹元 ( 保持纹理局部特性的最小纹理块) 按照一定规则捧列而成的纹理，例如砖墙、地板等。 在随机性纹理中找不到明确的纹元，例如沙粒、裂痕等。但现实世界中的大部分纹理同 时包含了以上两种特性，人们在其内部可以分辨出纹元但是纹元之间有一定的差异， 而且纹元的排放也不是很规则例如织物、犁过的田地等。这种类型的纹理称为半结构 半随机性纹理。如图1 2 所示。 f a l 结构性纹理【b ) 随机性纹理( c ) f 结构半随机性纹理 圉i 纹理的分类 1 _ 1 2 纹理映射 ( 1 ) 纹理空问 纹理映射中的纹理空间一般定义为一个单位正方形域( 0 s “1 ，0 v 1 ) 。这样定义 的二维纹理，既可以是存储在计算机中的任何一幅指定的数字图像，也可以是一些特殊 的纹理函数。例如，下式定义了常用于检测各种纹理映射算法的纹理函数，其模拟了国 际象棋棋盘的方格纹理，如图1 3 所示： 鼬朋也裳赫端篙 其中，a 与6 代表两种不州颜色，h 表示小于z 的最大整数。 圈i - 3 方格纹理 ( 2 ) 纹理映射的基本原理 c a t m u l l 3 i 于1 9 7 4 年首先提出了二维纹理映射方法。该方法首先在纹理空间中定义 维纹理，井将其从纹理空间映射到屏幕空间。这种映射需要完成两次坐标变换：纹理 第一 * 空间与景物空间的坐标变换，景物空【白j 与屏幕空问的坐标变换( 如图l - 4 ) 。 根据纹理空间和屏幕空问之白j 的映射方式，纹理映射有i f 向映射和逆向映射两种。 j 下向映射是指将纹理空f , j 定义的二维纹理经映射函数映射到景物空间中的三维物体 表面再经投影变换投影到屏幕空自j 。逆向纹理映射则是先从屏幕空日j 到景物空间，再 由景物空间到纹理空日j 的映射变换。由于正向纹理映射不能保证纹理像素和屏幕像素日j 的一一对应关系，屏幕上的部分像素可能因为没有与之对应的纹理而产生纹理空洞，因 此很少被采用。由于逆向纹理映射是按扫描线顺序进行处理的，可以采用传统的扫描线 算法，因而在纹理映射中得到普遍使用。 逆向纹理映射过程中，屏幕空间到景物空间的变换实际上就是投影变换的逆变换。 从景物空间到纹理空间的变换由纹理映射函数来确定( 参数化) ，这一过程可描述如下： 给定三维景物空间f r 3 和二维纹理空间d e r 2 ，对于f 中的任一点( z ，p ，z ) 通过纹 理映射找到它在d 中的对应点( 虬v ) ，即： z ) e f 一+ 船m 垆j ：罂2 ：| = | ! ( 1 l n l j ，h 2 刈l v j 有效的纹理映射函数应当保证景物空间坐标与纹理空间坐标是一一对应的h 。 图1 4 纹理殃射框架 1 1 3 纹理合成的研究现状 ( i ) - - - 堆纹理合成 二维纹理合成主要有两种方法：一种基于马可夫随机场( m a r k o vr a n d o mf i e l d ，m r f ) 模型：另一种基于特征集。 设随机场z = 扛( 对，z e a ) ，称z 是关于_ v 的马可夫随机场( m r r ) ，如果对于所有的 2 ，p ( z ) 0 ，并且 p ( = ( 而) l z ( x a ，弘。) = p ( z ( x j ) i z ( x , ) , v x j4 ) 其中，离散值的随机变量场的局部条件概率密度函数是用狄拉克j 函数定义的。 马可夫随机场有两个特点：一是，所有可能的状态概率非零；二是，一个特定点的 局部条件概率密度函数仅仅依赖于该点的邻域内随机场的值。通常假定纹理图像有两个 统计特点：第一，局部统计，即某一点的值仅依赖于其局部的邻近点；第二，平稳统计， 鸯 ，f 鬟一 江南人学硕+ ：学位论文 即这种依赖性对于每个点都是相同的。也就是说，m r ：模型认为纹理具有局部统计特征， 纹理中的任一部分都可以由其周围部分( 即邻域) 完全决定。因此m r f 模型适于描述纹理 图像，许多算法【5 j 【6 1 1 7 1 1 8 】【9 】都是基于m r f 模型进行纹理合成。 基于特征集是在特征空间和采样图像中直接计算整个的统计，并通过在样本图中匹 配特征生成新的纹理图像。h e e g e r 年1 b e r g e n 1 0 】提出随机噪声分层的方法，能够对随机性 的纹理合成较好的效果，但是对结构性纹理合成效果并不理想。而文献 11 】的方法适用 于结构性的纹理，但是对结构性不强的纹理合成效果不好。 基于样本的纹理合成需要搜索匹配点，计算量很大。文献【1 2 】中，提出l 形邻域搜索 的方法，采用多分辨率合成方法减小搜索范围，并用树状结构的矢量量化技术进行加速。 a s h i k h m i n 【5 】利用相关性原理改进了文献【1 2 】中的方法，把搜索范围限制在当前的邻域， 从而提高了搜索速度。 ：c u t l3 1 ，u a n g t 8 1 和e 叠的s 【6 1 采用基于块( p a t c h ) 的采样技术，特点是纹理合成速度快，特 别是l i a n g 实现了实时合成纹理。 基于块的纹理合成速度快，但是合成的图像有局限性。基于象素的方法合成速度慢， 但是容易控制合成的过程，能够根据采样图合成新的纹理图像。 ( 2 ) 曲面纹理合成 对于曲面的纹理合成是一个复杂的过程。如果采用常用的纹理映射技术把纹理直接 粘贴到曲面上会引起变形和不连续。其中一个解决方法是直接在曲面上生成纹理，使变 形最小。这需要解决三个问题【1 4 】：第一，如何从目标纹理挑选采样的匹配点；第二，如 何比较目标和采样纹理中的匹配点；第三，如何在采样中寻找最相似的匹配点。 文献u 5 采用重叠纹理技术用一个或多个不规则形状的纹理面片，把它们的拷贝按 照重叠方法放到曲面上。这些面片的矢量场由用户定义，并根据最小变形方法进行映射。 w e i 1 6 】【1 。7 】把2 d 纹理合成思想扩展到3 d 。建立随机对称的矢量场，并采用了松弛算 法和插值算法控制纹理的生长方向，避免了文献【1 5 】的方法中需要人工建立矢量场的问 题。w e i 采用随机方法扫描网格顶点，并把曲面展平后进行重采样，来查找匹配点。 基于w e i 与文献 5 中的思想，y i n g t l 4 】提出了两种新的合成方法。第一种基于w e i 的 多分辨率方法。通过映射建立图表( c h a r t ) ，在曲面的邻域和纹理样图点邻域间建立对应 联系，对于最低分辨率部分，采用曲面搜索方法查找匹配；对于其它分辨率，采用图表采 样( c h a r ts a m p l i n g ) 方法。第二种基于文献 5 】中的思想，采用纹理映射图，在曲面点的邻 域查找在样本纹理上的对应点，实现纹理合成。 在文献 1 8 】中，通过保角变换将模型块展布在二维平面上，如果在变换中发生的扭 曲过大，将缩小该合成面的大小以此来减小扭曲。这虽然降低了纹理的扭曲，但是并不 能避免扭曲。质心坐标变换【1 9 】方法较好的解决了因保角变换或保面积变换产生的纹理变 形，但是并没有解决该问题。 在纹理映射的过程中，只有三角面在任何情况下是共面且不会发生纹理变形。文献 【2 0 1 中，虽然使用了三角形的映射方法，但是由于对每一个三角面都要搜索纹理与合并， 所以较难保证纹理的接缝不走样，并且要花费大部分时间用于对纹理样图的搜索。 4 第一章绪论 双向纹理函数( b i d i r e c t i o n a lt e x t u r ef u n c t i o n b t f ) 可以按照空间变化的表面反射和表 面细微结构( m e s o s t r u c t u r e ) 描述纹理。利用采样的b t f 合成曲面纹理主要面临的挑战是： 曲面上细微结构的一致性以及b t f 采样中大量的数据。文献【2 1 】中是基于曲面纹元 ( s u r f a c et e x t o n ) 实现b t f 合成。为了提高合成速度，他们提出k 相关( k - c o h e r e n t ) 查寻方法。 其合成的b t f 不仅在所有观察和光照条件下都与b t f 采样相似，而且当观察和光照条件 变化时可以表现一致的细微结构。 1 2 本文的主要研究内容与章节安排 全文共分为五章，各章的内容安排如下： 第一章简介了纹理的基本概念，以及纹理合成的研究现状 第二章简要概述了参数化的概念，以及平面参数化的方法。并详细介绍了3 种经典 的参数化方法。比较了他们的参数化效果以及运算时间。 第三章简要概述了模型分割的概念，以及现今的研究现状。最后提出了一种基于法 向评价的模型分割方法，并给出了较多的实验结果，证明本文的方法是有效 的。 第四章提出了一种基于模型上相邻三角面关系的纹理合成方法。接着又在第2 ，3 章的基础上并结合本章中第一种方法中的一些思想提出了另一种基于模型 分割与参数化的纹理合成。最后给出了实验结果，证明这两种方法都是有效 的，并比较了2 者的差异，以及最终的合成效果。 第五章总结全文的工作，并对下一步的发展进行了展望。 5 江南人学硕l ：学位论文 第二章网格曲面的参数化及典型方法的研究与比较 网格曲面的参数化是对模型上网格几何信息与拓扑信息作进一步处理的基础，因此 参数化显得尤为重要。参数化是指将三维模型通过一种线性映射得到一个与之同构的平 面网格，其中线性映射指网格上的每个点在平面映射域内分配一个与之相对应的参数化 坐标，而同构是指三维网格曲面和二维平面网格之间存在着点与点、边与边、网格与网 格的一一对应关系。换句话说，网格参数化的目的就是在于获得三维网格曲面与二维平 面域的一种映射关系。这样的映射将三维网格曲面的操作转换为平面网格的操作，从而大 大地减小了操作的复杂度。因此被广泛地应用于纹理映射、网格重构以及曲面拟合，同 样也广泛地应用于计算机视觉，用来增强三维曲面的视觉显示效果。由于三角网格已经 成为三维数字模型中最常用的表示方法，所以三角网格的参数化显得更为重要。在本章 中主要研究平面参数化算法，以及几种经典的参数化方法的比较。 2 1 基本概念 2 1 1 三角网格 三角网格模型可以表示为三元组： m = ( ，k ，) 其中= 1 ，2 ，n 是m 的顶点集合( ，l 表示顶点的数目) ；k m 是m 中所有拓扑 连接关系得集合；r 为m 中所有顶点属性向量的集合。 k 表示的集合可以分为三种类型：顶点 i ) ，边e = f ，) ，面= 歹，k ) 。若 p ，) 则顶点 d ，u ) 称其为邻居。顶点( i ) 的1 环邻居被定义为 n ( i ) = ulp ，- ，) k ) ，顶点p ) 的入度被定义为n ( i ) 中的元素个数l m l ，边e = p ，) 的1 环邻居被定义为n ( e ) = n ( i ) u ( 歹) 一p ，办。依此类推，设共享顶点似的所有三角形集合 为t ( i ) = ( ff f ，k ) 则r ( e ) = t ( i ) wt ( j ) 。顶点p ) 的星形领域被定义为 s t a r ( i ) = u 汹距k hs ，s t a r ( e ) = s t a r ( i ) u s t a r ( j ) 。 顶点矗 处的分布密度被定义为： 阶i 等 , a r e a ( m ) ( 2 1 ) 其中a r e a ( m ) 表示网格m 的所有三角形面积之和。 兄的集合，可以表示为： 匕= o ( i ) if ) 其中o ( i ) = ( 彳( f ) ，f 2 ( i ) ，z ( f ) ) 表示顶点a ) 的n 个属性值，包括坐标，法向，颜色 等，显然名包含了m 的所有几何信息。 6 第二章州格曲血的参数化及典型方法的研究i 比较 2 1 2 三角网格参数化 对于三角网格的参数化可以归结为这样一个问题：给定一个由空间点集，r 3 组成 的二维流形三角网格m = 瓦) 和一个二维流形参数域q ，寻求一个在参数域上的点 形q 到点杉m 的一一映射妒，使得参数域上的网格与原始网格拓扑同构，并且在保 证参数域上三角形不重叠的同时，寻求某种与原始网格之间的几何度量的扭曲失真最小 化。实际上满足这种参数化的方法很多，寻找这样的函数并不是难事，但是问题在于如 何在这么多映射中找到一个相对比较好的映射。现今通常是运用模型上三角网格的几何 内在属性( 如长度、角度、面积、角度等) 并利用微分几何、弹性理论、等积映射、调和 映射、保角映射和等测度映射等理论来建立影射关系1 2 2 】【”】【3 1 1 【2 ”。因为参数域的不同和 所处理网格的拓扑信息的不同，参数化的方法具有很大的差异。 2 1 3 参数化的有效性 通常是指三角网格是一个可定向的二维流形三角网格，所以三角网格参数化是否有 效必须满足以下2 点是： ( 1 ) 原始网格顶点和参数域网格顶点在参数化映射下是一一对应的。 ( 2 ) 参数域上的三角网格不互相重叠。 如图2 1 所示的三角形网格，在参数化过程中，y 1 为v 的有效参数化点，v 2 为无 效参数化点，因为y 2 在参数域内产生了三角片重叠。 q 可 2 1 4 参数化的形变度量 视觉上的平滑效果好坏是衡量参数化变形的一个直观标准，参数化的变形有以下两 种最常用的定量标准。 第一种：一般采用参数域网格与原始网格之间的面积相对误差和角度相对误差等误 差测度来衡量变形程度【2 6 1 。 r1 2 a i s 洲o n 柏= 引器一器l l l 5 吖 f e m j ( 2 2 ) a i s t o n i o n 础。等陵2c 砉一熹，川j 他3 )，l f c i ，3 厶7 7 t f ，3 、 其中，歹为模型中三角形的个数，s ( ) 和彳代表三角形的面积和角度。e 表示三角形 7 江南人学颀 ：学位论文 的角盈( 球面域) 。该误差变形体现的是整体变形，不能体现局部三角形网格的局部变形。 第二种：基于几何变形( g e o m e t r i cs t r e t c h ) 度量空间的方法【2 7 】。 首先定义三角形之间仿射变换的特征值度量空间： 斤一 r ( r ) = 、主( r 2 + 7 2 ) ， r ( 丁) ：r ( 2 4 ) 其中r 和y 分别为仿射变换的j a c o b i 矩阵的最大特征值和最小特征值，然后在这个 度量空间的基础上定义整体网格的参数化变形 r1 rp ) = 恬p ( 劭 ( 2 5 ) 这种基于纹理扭曲程度的度量既可以反映局部三角形变形又可以衡量整体网格参 数化的变形，是一种更为普遍的度量方法。 2 2 平面参数化方法简介 2 2 1 凸组合方法 凸组合方法是由t u r e 在1 9 6 0 年提出的【2 8 填基本思想是把网格的边界映射到一个 平面上的凸多边形，而内点取以它为中心点的1 - r i n g 的平均值。t u t t e 证明了该方法所得 到的三角形不会相互重叠，但基于图论给出的这个嵌入图( g r a p he m b e d d i n g ) 方法【2 9 】没 有充分考虑到原始网格的几何信息，使得参数化结果的变形较大。在t u t t e 的基础 上，f l o a t e r 通过给每条边附加一个与边长相关的权值改进了凸组合方法【3 0 1 。它的基本思 想是固定边界点，内点由它的相邻点的加权凸组合给出，同时证明了该凸组合方法解的存 在性和惟一性。 虽然该方法产生较大的角度变形，但是由于其具有保持1 - r i n g 形状不变性，因而称之 为保形( s h a p ep r e s e r v i n g ) 参数化；另外，由于将该方法求解问题转化为一个大型的稀疏 线性方程组，而整个参数化过程只需要求解线性系统，因此是相当快速的，现在它已成为 一个应用非常广的参数化方法。f l o a t e r 将保形凸组合网格参数化方法扩展到非网格 ( m e s h l e s s ) 的点集参数化上，进行三维离散数据点重建及曲面拟合。 2 2 2 能量方程最小化方法 该类方法关键在于寻找一个能量方程，称为目标函数，并且适当地给出该目标函数的 边界条件，然后求解目标函数的极值得到一个参数化。一个最典型的方法就是引入弹性理 论的h o o k e 法则，把网格的各条边视为具有弹性的弹簧，定义整个网格的能量 e = i 1 允，i i p ：- , , ；t 1 1 , 1 2 j f ，j e e d g e a 置梯度为0 ，诱导出一个线性方程组： 器= 丑，( 覃一彳) = o 8 第- 二章州格曲由的参数化及典型方法的研究，比较 这类方法的区别在于能量系数及，的选取。系数的简单取法往往使参数化不具有很 好的保角特性。e c k 等提出调和能量方程，给出了另一个系数方程，改进了保角的特性 1 3 1 o 调和映射是一个离散的准保角映射，它是连续保角映射的一个线性逼近，在局部区域 保角性( c o n f o r m a l i t y ) 导致它具有很小的角度变形。虽然调和映射具有很好的性质，但大 部分方法只是对调和映射的一个线性逼近，并且在那些网格的尖端处的名，可能为负值。 丑，非正和边界非凸都可能产生三角形重叠，这意味着该方法的解不总是存在的。即便如 此，它仍比凸组合方法变形要小。对于负值情况，e c k 用一致参数化来代替。 能量最小化方法的关键问题在于能量系数的选择，其最大的优点就是只需求解一个 线性系统，具有很小的时间和运算复杂度，并且很容易实现，使得它成为应用最广的参数化 算法。 2 2 3 虚拟边界法 该类方法主要通过改变参数域的边界来减少参数化变。f l o a t e r 直接把弦长比例映射 到正方形作为边界【3 2 】；e c k 等则用单位圆来作边界【3 l 】；而g r e i n e r 等用最d x - - 乘意义上的 逼近边界点的曲线作为边界 3 3 】，生成一个尽可能保持边界形状不变的参数域边界；l e e 等1 3 4 】甚至引进e d g e 铆e a k i n g 方法【3 s 】生成更逼近原始网格的边界：它们共同的特点是这些 边界围成的区域必须是凸区域，否则参数化无效。虚拟边界的主要思想是通过对原始网格 增加一条或者多条虚拟的边界生成一个新的网格，然后利用凸边界方法对新的网格进行 参数化。原始网格的边界点在新网格下被视为内点，参数域上的原始网格的边界不再是一 个凸边界【3 4 】。 2 2 4 分割展平法 分割展平法的主要思想是把复杂的三角网格分割成多个可展( d e v e l o p a b l e ) 面片，然 后展平。由于可展曲面可以毫无变形地平摊到平面，因此分割过程自动完成三角网格的 平面参数化。具有代表性的是s o r k i n e 等提出的局部分割展平法【3 6 】和s h e f f e r 等提出的 基于a b f ( a n g l eb a s e df l a t t e n i n g ) 的整体展平方法【3 7 】。前者首先选取一个种子三角形， 把它安置到平面；然后从该三角形出发，依据第2 1 4 节中给出的特征值度量，每次选 取一个变形最小的相邻三角形展平，展平时保证所有三角形不会重叠，直到没有可展的 三角形；最后重新选取种子三角形进行新一轮的展平，每一次展平操作就生成一个新的 可展面片。局部分割展平法算法相当简单，具有很高的运算效率，适用于任意拓扑。后 者则是一个整体求解带约束的非线性的方法，与s o r k i n e 一样，s h e f f e r 等给出一系列防 止展平重叠的约束条件，并且证明了这些条件是保证参数化有效性的充分必要条件。虽 然a b f 方法无需设定边界，并且在纹理映射时都取得了比凸组合和调和能量更好的结 果，但是用l a g r a n g e 乘子法求解非线性系统代价是很高的，且a b f 方法不能解决多边 界问题。 9 江南人学硕l ：学位论文 2 2 5 封闭网格参数化方法 对封闭网格通常是采用分而治之的方法，即切割封闭网格成多个与圆盘同胚的面 片。它实质上是一种分段参数化( p i e c e w i s ep a r a m e t e r i z a t i o n ) ，其与分割展平法的区别在 于，它的面片不是平面可展曲面，因此必须应用带边界的参数化方法来进一步处理每一 个面片。封闭网格参数化的变形大小的关键在于切割方法的好坏。除了用交互式手工切 割之外【3 8 】【3 9 1 ，e c k 等用v o r o n o i 图和d e l a u n a y = 角化的技术来分割三角网格【3 i 】；m a i l l o t 等把一些法向相似的三角面片聚集成一个大面片【4 0 1 。但是在封闭网格的切割线上，同一 个物理点被切割线分离成两个甚至多个参数点，即同一个( x ，y ，z ) 对应多个( u ，v ) ，必将导 致各个面片之间参数化的不连续性，直接引起纹理映射视觉上的非真实性。因此，从拓 扑结构上来看，对封闭的网格是不存在连续的平面参数化的。 2 3 几种经典的参数化方法 2 3 1f l o a t e r 参数化方法 f l o a t e r 参数化方法【3 0 1 ，首先对其边界点按逆时针方向的弦长参数化到正方形上，这 样将能得到一组边界点的参数化结果。令其为： , x 2 ，- ， 其中鼍表示第i 个边界点的参数化结果，| 表示边界点的数量。这个结果作为后续 线性方程的已知条件。 其次对每一个非边界点即内部点，加入一个权值五。 i o ，( f ，歹) 正e 嗍觑的权值为一2 k o l ，奴，瑚e ，其中e 是边的集厶o l 户1 权值的计算： 对每个内部点i 以及1 - r i n g 工，五，厶，进行局部参数化。该局部参数化过程是将 z = “，x j , ，x j 2 ，屯 按照下式： 恢一p i l ：| | 屯一誓i l a n g ( p k , p ，p m ) = 2 ；r c a n g ( x j 。，x i ，+ 1 ) 幺 得到一个中间参数化结果尸= p ，p 。，p 2 ，岛，) 。这样既能保持了相邻点的夹角比 例，同时也保持了弦长。 其中：k = l ，面，谚= x k = l a 馏( 屯，薯。) ，= 屯，+ ，= a ，a n g ( a ，b ，c ) 为 矢量口一6 ，b c 的夹角。在初始情况下设定p = o ，p i = ( i l 九一薯l | ，o ) 。 在局部参数化的结果上计算权值丑。，。当呸= 3 时，p 关于卸见p 3 只有唯一的一个 重心坐标，所以 1 0 第一二章网格i l f l 血的参数化及典型方法的研究j 比较 = 黜以止= 黜以 = 黜 a i ：x j x h 3 ，这时对于每个由三个临界点所组成的三角形，如果它包 含点p 在内，则按西= 3 的情况计算一次权值，如图2 2 所示。全部计算完毕后，将每 个临近点在整个计算过程中得到的所有权值平均后得到最终该临近点的权值是，。 由于每个内部点都是邻近点的凸组合： j v 跗f 一五, j u ，= o ，i = 1 2 ，n _ ，= i 由于吩= ( u ；，v ；) r 2 ，因此需要解两个线性：y 程组a u = b l , a v = b ：，最终得到参数 化的结果。 如果在计算过程中取磊，= ，( f ，) e ，则为t u t t e 的重心参数化方法方法2 8 1 。 2 3 2h a r m o n i c 参数化方法 h a r m o n i c 参数化方法【3 l 】，首先定义整个三角网格的能量： e = i 1 五，i i p ；- 1 1 2 1 l ，j 厶 l ，j e d g e s 其中西与z 分别表示边( f ，j ) 的两个顶点映射到平面域尸中的位置。乃，为边( f ，_ ，) 的弹性系数。h a r m o n i c 参数化方法中采用拉格朗日乘法解上式使得e 最小，得到三角网 格中所有顶点映射到平面域中的坐标。及，的计算方法如下： 以，- ，= ( 叠一+ 霉一1 一置，) a r e a i _ + ( 鼍川+ 弓l 一置，) a r e a i _ 川 其中j + l ，j 一1 代表共有边( f ，j ) 的两个面的另外两个顶点，厶，为边( f ，_ ，) 的长度， a r e a i _ 。表示以i ，j ，k 为顶点的三角形的面积。 由于乃，可能产生负值，因此这样将直接导致参数化过程中出现无效的参数化点， 即参数化三角形发生重叠。这时取足，为平均弹性系数。 小，o。，；。，。；l l 江南人学硕 学位论文 2 3 3i n t r i n s i c 参数化方法 i n t r i n s i c 参数化方法【2 5 1 ，该方法综合了离散保角参数化和离散保积参数化的两种参 数化方法，通过d i r i c h l e t 和k a i 两种能量的最小化得到参数化结果。 1 - r i n g 的d i r i c h l e t 能量表示为： 幺= c o t lu ；一“ i o n ( i ) k a i 能量表示为： t = 1 c o t y 了, j + c o t 4 j ( u , - u j ) ： j e n ( i ) l 玉一x jj 其中，( f ) 为点f 的l - r i n g 集合，f 吩一u jl 为边( f ，力在平面域p 内的长度，l t x 为 三角形网格s 上边( f ，) 的长度，乃，屯为s 中边( f ，) 所在三角片中顶点为x ，的角。如图 2 3 所示： 最小化d i r i c h l e t 能量得到： 鬻。磊，( c o t 嘞+ c o t 倒训 最小化k a i 能量得到： 鲁= ，磊，等孚c ”剐钆 氙) i 一x ，j 2 r 1 ” 。 综合考虑两个能量e = 五毋+ 乓，建立如下方程： m u = 一州iz = ： c o 2 射 五，为两个任意的实数，可以简单的取为1 。c 为包含所有平面域p 边界点位置信 息的向量。这是一个稀疏矩阵，其系数为： lc o t ( ) + c o t ( 属) ，j n ( i ) m 含- t 一哦，i = jm j = l k e n ( i ) 【 o , o t h e r w i s e 塑掣，j n ( i ) ix i x i1 2 一飞v 一咝，i = j k e n ( i ) o ，o t h e r w i s e 这样解( 2 6 ) 的线性方程组，就可以得至l j i n t r i n s i c 在固定边界下的参数化结果。 1 2 * 一章m 鞯曲面的参教化典型方瞌的研宄，m 较 2 4 参数化结果比较 本文在v c + + 及o p e n g i 环境下实现了上述的3 个算法。如图2 - 4 ，是对于这三个算 法的参数化比较，第一行是网格模型以及棋盘纹理，其余各行是模型参数化到圆形域 与正方形域的结果以及采用该结果映射的纹理效果。在本文的算法中，所讨论的都是 具有自然边界的模型。对于闭合模型，由于没有边界三角形因此不能够建立初始的 参数化点也就不能进行有效的参数化。从结果能够发现这三种参数化方法在曲率较大 以及网格较为密集的地方变形也很大；并且由于模型的复杂性，参数化到规则区域内 导致纹理的拉伸也很大。从头像的】下视图中，可以看出h a r m o n i c 的方法较其他两种方 法变性更大一些。 现在来看看同一个模型与同一种参数化方法在圆形域与正方形域在边界处产生的 纹理形变。在这里本文选用一个规则模型( 球冠) 。如图2 - 5 在采用同样的方法，从 结果中可以看出当参数化到正方形时在边界处，拉忡明显大于圆域方式。对于球冠模 型，因为对于边界上的点映射到正方形域时，只有通过形变才能匹配在正方形边界上， 因此变形较大。 图2 - 6 展示的是各种模型对不同参数化方法以及不同参数域的结果及纹理的展示。 表2 - 1 列出了各种参数化在不同模型以及不同参数域上所需的时间，从中能够发现 h a r m o n i c 与l n f a i n s i c 方法花费的时间较多，但是总体上看运算速度还是较为理想的， 这是因位他们都同样只需要求解一个大型的稀疏矩阵。 西豳 数母嘶戥帚参数化方浊正方形域( 毫秒)圆形域( 毫秽 旺南 掌颅十学位娩文 ( a ) 圆形域 曲) 正方形域 圈2 - 5 球冠模型f l o a t e r 参数化 矗可一 馨 一一桃一僦震施一o -。ii参-。赢 孽薰 第一# h 擀自# 散m 型方m 的 m 批# 嵇目惶! i n s i c 方珐 图2 - 6 筹种参数化方法与各种模型的映射结果 l量羹 冀。 皤曩锣 江南人学硕士学位论文 2 5 本章小结 本章首先介绍了网格曲面参数化的基本概念以及平面参数化的分类与现状，然后研 究了几种典型的参数化方法，阐述了各算法的基本思想和具体实现过程，比较了各自参 数化结果以及参数化时间。 对于一个理想的参数化结果往往受到诸多因素的影响，比如参数域的凸多边形形 状、网格曲面本身的曲率变化幅度，以及网格的分布密度等。并且因为参数化