（计算机应用技术专业论文）基于网格模型的二维纹理映射方法改进研究及其应用.pdf

摘要 随着虚拟现实应用领域的同益扩大及应用内容的复杂化，尤其近两年网络图 形技术的高速发展，对高效纹理映射技术的需求急剧增加。有一些应用领域( l l 如试衣效果展示系统) 对场景的复杂度要求不高，不需要三维场景的视角切换， 仅需系统给出某一视角的纹理映射效果，而更加注重纹理映射算法的速度、真实 感和易用性。基于此，本文通过对基于图像的绘制技术和二维纹理映射真实感的 研究，针对现有纹理二维映射算法存在得问题，提出了一种改进的基于网格模型 的二维纹理映射方法。 针对伪曲面网格对光顺性的要求本文提出了一种改进的控制网格绘制方法， 更好地利用了三次样条曲线的光顺性特征，利用较少的网格控制点更加贴切地表 现了光顺的纹理走势，这样生成控制网格的计算量大大减小，也使得调整网格更 加方便。同时给出了一些应用实例。 为了充分继承控制网格的纹理走势特征，本文提出一种插值型四角网格面分 裂算法，是一种1 一n n + m 的细分策略。该网格细分算法基于三次参数样条曲 线分割算法，既保留了原控制网格的特征点，又均匀地生成了新的型值点，并且 具有较高的效率。该算法可以较快地生成满足c 1 连续的稠密网格，生成的伪曲 面网格对场景特征的表现力较高。同时我们给出了一些应用实例。 同样，为了解决黑一白失真问题，本文还提出了一种新的图像融合算法，有 效地避免了黑一白失真。该图像融合算法遵循人眼对颜色的观感，采用h s b 色彩 空间模型，在图案纹理映射时继承场景表面的材质特征和光照分布，用图像处理 的方法避免高复杂度的图形学转换，并且具有较高的效率，和相对低的计算资源 消耗。同时我们给出了一些应用实例。 关键字：虚拟现实，纹理映射，控制网格，网格细分，黑一白失真，图像融合 a b s t r a c t w i t ht h ea p p l i c a t i o nf i e l do fv i r t u a lr e a l i t yb e i n gm o r el a r g e ra n dt h ec o n t e n tb e i n g m o r ec o m p l e x ，e s p e c i a l l yt h ef a s td e v e l o p m e n to fn e t w o r kg r a p h i ct e c h n i q u e s ，t h e r e q u i r e m e n to f h i g he f f i c i e n c yt e x t u r em a p p i n gt e c h n i q u e si n c r e a s e dr a p i d d l y i ns o m e f i e l d ( f i t t i n ge f f e c td i s p l a ys y s t e m ) s c e n ed o n tn e e dt ob ec o m p l e x ，v i s u a la n g l eo f3 d s c e n ed o n tn e e dt ob es w i t c h ，o n l yt h ee f f e c to ft e x t u r em a p p i n gi no n ev i s u a la n g l e s h o u l db eg i v e nb yt h es y s t e m b u tt h es p e e d 、r e a l i t ys e n s ea n dc h a r a c t e ro f e a s yt ou s e a r ep a i da t t e n t i o nt o a c c o r d i n gt ot h i ss i t u a t i o n ，t h r o u g ht h er e s e a r c ho ns c e n ed e s i g n w h i c hi sb a s e do ni m a g ea n dt h er e s e a r c ho nr e a l i t ys e n s eo f2 dt e x t u r em a p p i n ga n d a i ma tt h em a t t e ri ne x i s ta l g o r i t h mo f2 dt e x t u r em a p p i n g ，w ep u tf o r w a r dai m p r o v e d m e t h o do f2 dt e x t u r em a p p i n gb a s eo nt h em e s hm o d e l f o rt h er e q u i r e m e n to fl u b r i c i t yi n p s e u d o c u r v i n gs u r f a c em e s h e s ，w eb r i n g f o r w a r dai m p r o v e dm e t h o do fc o n t r o lm e s hd e s i g n t h em e t h o dm a k ef u l lu s eo ft h e l u b r i c i t yc h a r a c t e ro fc u b i cp a r a m e t r i cs p l i n ec u r v e s i tc a nr e p r e s e n tt h es l i c kt e x t u r e t r e n dw i t hf e wc o n t r o lp o i n tr e l e v a n t l y i nt h i sw a y , t h ec o m p u t eq u a n t i t yo f g e n e r a t i n g c o n t r o lm e s hw a sr e d u c e dg r e a t l y , a n dt h em e s hc a nb ea d j u s tm o r ee x p e d i e n t l y w e a l s op r e s e n taf e wa p p l i c a t i o ne x a m p l e so ft h i sk i n d f o ri n h e r i tt h et e x t u r et r e n dc h a r a c t e ro fc o n t r o lm e s ha d e q u a t e l y , w ep u tf o r w a r d an f o u r s q u a r em e s hs u r f a c ed i s p a r ta l g o r i t h mb yi n s e r t i n gv a l u e i ti sa ns u b d i v i s i o n s t r a t e g yo f1t on t h e nnt on 4 m t h i sm e s hs u b d i v i s i o na l g o r i t h mw h i c hi sb a s e do n t h ec u b i cp a r a m e t r i cs p l i n ec u r v e sd i v i s i o nm e t h o dn o to n l yr e s e r v et h ek e yp o i n t s i nc o n t r o lm e s h ，b u ta l s o g e n e r a t i n gn e wm o d e lp o i n t se q u a b l y a n di tw a s e f f i c i e n t l y i l a ea l g o r i t h mc a ng e n e r a t et h i c km e s hw h i c hi sc 1s e q u e n t i a lf l e e t l y , a n d t h ep s e u d o c u r v i n gs u r f a c em e s h e sg e n e r a t e db yt h ea l g o r i t h mh a sp o w e r f u l e x p r e s s i v ef o r c ef o rt h es c e n ec h a r a c t e r w ea l s op r e s e n taf e wa p p l i c a t i o ne x a m p l e so f t 1 _ l i sk i n d b e s i d e s ，i nt h ei n t e r e s to fs e t t l et h ep r o b l e mo fb l a c k w h i t ed i s t o r t i o n ，w ea l s op u t f o r w a r dan e wa l g o r i t h mo fi m a g es y n t h e s i s i tc a na v o i db l a c k w h i t ed i s t o r t i o n t h i s i m a g es y n t h e s i sa l g o r i t h ma d o p t i n gt h eh s bc o l o rs p a c em o d e lk e e pt ot h eh a m a n i m p r e s s i o n so nc o l o r t h ea l g o r i t h ma v o i dc o m p l e xg r a p h i c sc o n v e r t i o nb yu s i n gt h e m o t h o do fi m a g ed i s p o s e i n g ，s oi tw a se f f i c i e n ta n dn e e df e wc o m p u t er e s o u r c e w e a l s op r e s e n taf e w a p p l i c a t i o ne x a m p l e so f t h i sk i n d k e y w o r d s ：v i r t u a lr e a l i t y , t e x t u r em a p p i n g ，c o n t r o l m e s h ，m e s h s u b d i v i s i o n ，b l a c k w h i t ed i s t o r t i o n ，i m a g es y n t h e s i s 1 1 概念介绍 1 1 1 三维纹理映射 第一章绪论 在计算机图形学中，传统的纹理映射是将纹理图案映射到3 d 模型的表面， 这些3 d 模型通常是表示真实世界或虚拟的场景。通过纹理映射的方法，可以添 加物体表面的细节，有效提高真实感，选到模拟现实世界的目的。纹理图通过简 单的仿射变换，正交映射到模型表面。相关的技术有：纹理分片( t e x t u r e t i l i n g ) 、 单元纹理，贴图、反射图环境映射等。这里所说的表面可以是平面或非平面的 多边形，甚至是二次物体像圆柱体和球体的整个表面因此，一个纹理图案通过 仿射变换或双线性变换，可任意扩展到一个平面四边形：也可以通过参数化的方 法使纹理图案沿着柱面或球面缠绕，若任意映射到非平面的物体上，纹理套产生 变形。传统纹理映射的几何关系见图1 1 。 图1 1 传统纹理映射的几何关系 在传统的纹理映射方法中对物体空间的三维建模是一个比较复杂的过程，这 个特点限制了三维纹理映射的易用性。 1 1 2 二维纹理映射 随着虚拟现实应用领域的日益扩大及应用内容的复杂化，尤其近两年网络图 形技术的高速发展，纹理映射技术的需求急剧增加。研究并采用一些可以应用在 现有通用计算机平台上，高效的纹理映射算法以进一步加速对复杂场景和造型的 模拟，解决模拟算法在速度、质量及场景复杂度之间越来越突出的矛盾，已经成 为计算机图形学领域一个j f 常重要的课题。有一些应用领域( 比如试衣效果展示 系统) 对场景的复杂度要求不高，不需要三维场景的视角切换，仅需系统给出某 一视角的纹理映射效果，而更加注重纹理映射算法的速度、真实感和易用性。针 对这样的需求，人们提出了二维纹理映射方法。该方法是指通过一组预先获得的 图像，而不是用三维模型来编码一个场景，并且通过适当地融合这些图像来产生 场景的新视图，以完成纹理映射工作。 与传统的基于三维模型的纹理方法相比，二维纹理映射方法有以下优点： ( 1 ) 作为已知的源图像不仅可来自于绘制系统，也可从真实环境中捕获， 因此可以反映更加丰富的明暗、颜色、纹理等信息【6 j ： ( 2 ) 该纹理映射技术所需计算量相对较少，对计算资源的要求不是很高， 因而可以在普通工作站和个人计算机上实现复杂场景的实时显示。 1 1 3 基于网格模型的二维纹理映射方法 基于网格模型的二维纹理映射方法的设计框架图如图1 2 所示它从二维原 始场景开始，建立场景中面料的伪曲面网格模型和映射区域边界，最后生成面料 的场景效果图。 图1 2 设计框架 1 。2 研究目的和主要内容 传统纺织c a d 系统中，设计的织物只有在生产出样品后才可以看到其实际效 果。一种织物的设计往往需要反复多次才可以进入最后批量生产。这种生产方式 不仅浪费了大量人力、物力，还延长了设计周期，使产品丧失了市场。如果在 c a d 系统中增加面料的虚拟场景模拟功能，将各种面料和场景输入计算机，通过 计算处理，生成面料在场景中的真实感效果，这样既有利于设计者的设计，也有 利于面料销售商的销售。但是如果通过三维场景模拟来实现面料的虚拟场景模 拟，建模复杂度高、计算量大，相比之下二维场景模拟建模简单，而且场景模拟 效果也非常逼真，具有更大的实用性和方便性。针对此，文献 1 提出了一种基 于网格模型的面料二维虚拟场景模拟方法，文献 2 提出了种采用向量化运算 进行图像融合的真实感纹理映射方法，这两种方法在一些二维纹理映射系统中进 行了应用，很好地满足了企业对场景模拟效率和便捷性的要求。但是在实际应用 中仍然存在两个主要的问题：一是伪曲面网格的建立方法很难符合复杂场景的要 求；二是当场景于纹理亮度相差过大时存在纹理失真问题。 本文针主要针对文献 2 提出的二维纹理映射方法在实际应用中存在的问 题，提出了一种改进的二维纹理映射方法，并给出了该方法在新的二维纹理映射 系统中的使用效果。本文研究的内容主要分为以下几个部分： 1 2 1 伪曲面网格建立方法改进 本文提出的改进后的伪曲面网格建立方法分为两步，分别是：( 1 ) 控制网格生 成与调整；( 2 ) 网格细分。两步走的伪曲面网格建立方法很好地解决了原来网格 一步生成存在的网格精度与调整复杂度之间的矛盾。 控制网格生成与调整方法更好地利用了三次样条曲线的光顺性特征，利用较 少的控制点表现了光滑的纹理走势，这样既使生成网格的计算量大大减小，也使 得调整网格更加方便。 我们的网格细分算法是一种插值型四角网格面分裂算法，是一种1 一n n * m 的细分策略。算法的效率较高，可以较快地生成满足c 1 连续的稠密网格， 该细化算法生成的新网格很好地继承了原始控制网格的控制点，对场景特征的表 现力较高。 1 2 2 边界绘制方法改进 文献【2 】提出的曲线拟合算法，基于三次参数样条曲线对映射区域边界的精确 勾勒，采取跟踪绘制的手段，对映射区域边界的曲线进行折线化，该方法可以在 曲线平坦处减少顶点数目以提高算法判断效率。 在曲线拐角处文献【2 】通过增加顶点数目以提高拟合的近似精度，本文提出的 改进的边界绘制方法，则引入了“重点”，并利用“重点”实现曲线拐角处的曲 线拟合，不但提高了拟合的精度而且降低了操作的复杂度。 1 2 3 纹理映射和图像融合方法改进 本文继承了文献 2 】的基于向量运算的纹理映射算法，并分析了图案在纹理映 射中的真实感要素，提出了一种新型的象素点图像融合算法。该算法解决了文献 【2 】中图像融合算法在场景与纹理亮度相差较大的失真问题。改进的象素点图像 融合算法遵循人眼对颜色的观感，采用h s b 色彩空问模型，在图案纹理映射时 继承场景表面的材质特征和光照分布，用图像处理的方法避免高复杂度的图形学 转换。该方法在保证图案映射真实感的前提f ，有较高的效率，和相对低的计算 资源消耗。 1 3 本文的组织结构 本文总体e 按照图1 2 的设计框架进行组织，分为以下几个部分： 第一部分即第一章，主要介绍了纹理映射的一些相关概念，阐述了本文的研 究背景、目的意义和内容。 第二部分包括第二、三、四章，详细讨论了我们对基于网格模型的二二维纹理 映射方法多个关键技术的改进。 第三部分为总结和今后工作的展望，在第五章中给出。 下面分章节介绍一下每章的具体内容。 第一章绪论阐述了本文的研究背景、目的意义和内容。对纹理映射作了简 单的介绍，分析了三维纹理映射在某些领域应用的局限性。最后，介 绍了我们提出的基于网格模型的二维纹理合成算法的主要内容和意 义。 第二章伪曲面网格建立方法及其改进基于现有控制网格划分技术的一些 不足，我们提出了一种新的控制网格划分算法：基于三次参数样条曲 线的控制网格绘制算法。我们的算法简单快速，并且能够贴切地描绘 各种场景的纹理走势。网格细分是基于三次参数样条曲线的控制网格 绘制算法的后续操作，我们提出了一种新的网格细分算法，解决了细 分过程丢失原控制网格特征和细分效率低的问题。另外，我们给出了 一些有趣的应用实例。 第三章边界绘制方法及其改进再一次充分利用了三次参数样条曲线良好 的光顺性，我们提出了映射区域边界多边形化算法。该算法较好地平 衡了对点在映射区域那判断的效率与映射区域边界拟合精确程度之 间的关系。 第四章纹理映射与图像融合算法及其改进我们采用了基于向量运算的纹 理映射算法，提出了一种新型的象素点合成算法，该算法遵循人眼对 颜色的观感，采用h s b 色彩空间模型，在图案纹理映射时继承场景 表面的材质特征和光照分布，用图像处理的方法避免高复杂度的图形 学转换。该方法在保证图案映射真实感的前提下，有较高的效率，和 相对低的计算资源消耗。作为基于网格模型的二维纹理映射方法的最 后一步，我们给了一些二维纹理映射的应用实例。 第五章总结和展望对本文的工作进行了总结，介绍了本文主要的贡献、创 新之处和工作中仍需要进一步改进和完善的地方。最后，对维纹理 映射的下一步工作方向作了展望。 第二章伪曲面网格建立方法及其改进 2 1 基于边界的伪曲面网格建立方法 2 1 1 网格建立总体思想 为体现映射效果的融入感，对场景实体的纹理映射必须继承实体表面的纹理 走势。通过勾勒覆盖实体的网格区域来反映总体纹理走势并生成初始网格划分。 对于实体上局部的纹理走势变化，如表面的收缩、凹凸、褶皱等，通过调整网格 点或网格线的方法来实现。 2 1 2 控制网格划分的关键：三次参数样条曲线 2 1 2 1 三次参数样条曲线的应用 三次参数样条曲线在c a d c a m 的应用中是一种很重要的曲线，不但具有一一、 二阶导数的连续性和几何不变性，而且具有严格通过全部控制点的独特优点，是绘 制各种等值线的首选曲线。 自1 9 4 6 年美国数学家s c h o e n b e r g 提出样条函数【】以来，样条函数以其构造 简单、易于计算又有很好的力学背景等特点而被广泛用于科学计算、工程设计和 计算机辅助设计等领域，成为最重要的曲线和曲面构造方法之一。在样条函数的 应用中，三次样条函数由于具有极小模性质、最佳逼近性质和很强的收敛性p 。” 等而成为应用于构造插值曲线和曲面最主要的方法。 用样条函数方法构造三次插值曲线，曲线的连续性基本可满足实际应用的要 求。当曲线的端点条件确定之后，曲线的精度和形状是由曲线需满足的连续性方 程唯一决定的。在小挠度的情况下，插值曲线的精度和形状都是非常理想的。对 大挠度曲线和任意平面数据点，则需推广三次样条函数方法构造三次参数样条曲 线，此时需知道每个数据点处的参数值( 节点值) 。在实际应用中，这些参数值一 般是无法预先给定的，所以构造三次参数样条曲线的第一步是对给定数据点参数 化，即为每个数据点指定节点值。如果指定的节点值是精确的，给定适当的端点 条件，可使构造的插值曲线的代数精度达到三次参数多项式。构造三次参数样条 曲线，当曲线的端点条件确定之后，能够决定曲线插值精度的量只有节点。因此 6 构造三次参数样条曲线的关键是如何选择节点。常用的节点选取方法有4 种，均 匀参数化法、累加弦长参数化法、向心参数化法和修正弦长参数化法。 2 1 2 _ 2 三次参数样条曲线的表示 设有n 个控制点p i ( x i ，y i ) ，i = l ，2 ，- - - , n 。我们知道三次参数样条曲线可用一个三 次多项式来表示。如果我们设参变量为t ，则在区间【0 ，t 】上的三次参数样条曲线 可表示为： p o ) = ( x ( f ) ，y ( f ) ) = e + b 2 ，+ 鸟f 2 + 玩， 0 f f ，i = 1 2 一7 1 ( 2 1 ) 其中l i 为第i 段弦长 t = i p 9 , + l ( 薯“一一) 2 + ( m + 1 一y j ) 2 对于节点有 t i = ( f 1 2m 一1 ) 其几何意义为累加弦长，三次参数样条曲线在各节点t ，处连续且一、二阶导数 连续。 ( 2 1 ) 式系数矢量由两端点矢量p i 、p i + l 以及切矢量p i 、p 。i + j 所确定。对p ( t ) 两 次求导得： p ( f ) = b 2 + 2 马f + 3 b , t 2 p ”( f ) = 2 垦+ 6 8 4 t 2 由第i 段两端条件可得： 尸( o ) = p = e p ( 0 ) = p ，= 岛 p ( ) = # + 。= 墨+ 最+ 马2 + 蜀3 p u ) = p = b 2 + 2 马+ 3 b j , 2 由以上四式求出( 2 1 ) 式系数矢量为： 岜= 手( 吲一 l + 2 p i ) 蜀= 旁( # “一只) 一古( p m + p ，) 攀誊：- 半旷b z ， + c 鼍掣一气芦矿 、 整理得 令 则 堑墨二墨= ! ! 一! ! ! ! ! ! ： 一，2一， 一! ! 墨! ! 二墨! 一! ! 出! l ? l 。 一6 ( p 志“铊只+ 惫，+ 上! ! ! ! ! ! 竺：! 一 忐t , = 1 - a = 惫， c + ，：3 【a 等生每冯 t1t 暑p h + 2 尸，+ 一尸f + 】= c + i = 2 2 一，n 一1 ( 2 - 3 ) ( 2 3 ) 式是n 一1 个方程的n 元方程组，我们给出端点条件【1 】： 器冀+ 2 p 暑c 。 4 ， 。= 。 8 o 瓦 意 ( 2 3 ) 式和( 2 ，4 ) 式可以合写成矩阵形式 2 p 2 2 l 七0 五2 地 o 一。 2 氏 j p i p 3 p 2 h p 。一 j p 。 c l c + 2 c + 3 c + c + 。 ( 2 5 ) 式是关于p i 的n 元方程组，而( 2 4 ) 式只有n 一2 个方程，为确定p i 我们给出 端点条件如下： ( 1 ) 夹持端 h = 以= 0 c i = 2 p t i ，c + l = 2 p 。 ( 2 ) 自由端 h = 无= 1 c ，= 3 ( 8 一# ) c + 。= 3 ( 只一只一，) 一 ( 3 ) 抛物端 。= 五= 2 c ，= 4 ( 8 一p , ) l j c + 。= 4 ( 只一0 一。) 乇一。 将以上条件分别与( 2 4 ) 式联立可求得玛，从而可确定b ( i - 1 ，2 ，3 ，4 ) 使( 2 1 ) 式成 立， 2 1 2 3 三次参数样条曲线的生成 我们设计的对三次参数样条啮线的生成算法如下所述： ( 1 ) 给出控制点p i ( i = l ，2 ，n ) ； ( 2 ) 计算l i ， l i = ( 蕾t 1 一一1 2 + ( 只“一”) 2 j = 1 ，2 ，n 一1 ； ( 3 ) 根据实际情况，确定端点条件，由端点条件计算c + l ，c + 。 ( 4 ) 计算c i ( i = 2 ，3 ，n 1 ) a 。叫 警+ “竽， 矗i 焘h 。1 一 i = 2 3 ，n 一1 ； ( 5 ) 计算p 。( i _ 1 ，2 ，n 一1 ) _ 讲怫一一畚船等 i = 1 2 ，仃一1 p t c 。一九q 一 一、万 对每一段三次参数样条曲线有b 2 = 一； ( 6 ) 计算每一段三次参数样条曲线的b 3 、b 4 b 3 = 丢( p 。一只) 一( 尸。一2 p ，) 肌一吾( 督伊i ，( p + t - p ) ( f = 1 2 ， 一1 ) ； ( 7 ) 将每一段插入m 个点，参数t 的取值序点列为 量，翌，盟堕( f _ 1 2 ，肝一1 )，一， ( 8 ) 由每一个t 的取值可得到每一段的m 个点 ( r ) = ( x t ) ，y j ( t ) ) = 只+ p ，t + 印+ t + b 4 t + t + r i = 1 2 ，”一1 ，= i 2 一，脚； ( 9 ) 将( 8 ) 得到的各点用直线顺次连接，即可产生所求的三次参数样条曲线。 图2 1 是以上算法所构造的一条示例三次参数样条曲线，我们可以看出，该 算法构造的三次参数样条曲线有良好的光顺性，非常适应作为对自然场景的网格 划分区域的边界，能体现网格划分的自然性。 图2 1 示例二次参数样条曲线 o 2 1 3 初始网格区域及网格生成 2 1 3 1 网格边界 观感上的纹理走势呈平滑性，对网格区域边界勾勒须直观的体现这种平滑 性。由于三次样条曲线满足c 2 连续，所以通过构造插值三次样条曲线来满足平 滑性要求。同时，因网格区域为一广义的四边形，故取两条横向曲线和两条纵向 曲线围成一个网格区域。关于三次参数样条曲线的构造与绘制在上文中已有洋细 叙述。 2 1 3 2 网格顶点计算 定义2 1 称网格粒度为网格区域细分的程度。将网格区域的顶点集定义为一一 个矩阵，则矩阵的行、列数分别称为网格的行粒度和列粒度。 现将边界曲线按对应的网格行粒度、列粒度进行等分，所得等分点即为网格 区域的边界顶点，对于网格区域的内顶点，可按如下方法求得： n m 图2 2 网格内顶点坐标计算 p 。 如图2 2 ，令： 5 ，= i ( m 一，) l 匕巴l 一歹x b 易 万。= l ( ，z f ) ) ( f 厶巴i i f 厶名f j = ( 万。+ j 2 ) 2 对图2 2 区域内所有点，取6 值最小的点为( f ，) 位置网格内顶点只。 图2 , 3 是我们的使用上述网格划分方法得到的几个实验结果。 图2 3 网格划分效果 2 1 4 交互式网格调整方法 由于网格初始划分并没有考虑物体表面部分异于总体走势的变化情况，为了 更细致地描述表面细节，需要对网格进行交互地调整，我们把网格调整方式分为 网格线调整和网格点调整。调整方法为： 1 、表面收缩区域，如褶皱区域，缩小这些区域网格线间距离，按收缩方向 调整收缩区域网格点； 2 、表面重叠处，合并网格线或网格点； 3 、表面拉伸区域，如突起区域，增大网格线问距离，以拉伸方向调整拉伸 区域网格点。 图2 4 为一个网格调整示例。 f a ) n 格区域初始生成 图2 4 网格调整示例 ( b ) 网格调整结果 2 2 基于边界的伪曲面网格建立方法存在的问题 2 1 节网格划分方法可以生成较平滑的伪曲面控制网格，如图2 5 ( b ) 所示， 伪曲面网格与实际场景的总体纹理走势相近。但是该伪曲面网格与场景的一些内 部纹理走势偏差较大。图2 5 ( a ) 中场景里的床单实际纹理走势如红线所示， 伪曲面网格在该部分的纹理走势如图( b ) 中粉线线条所示，与实际纹理走势偏 差较大。由于2 1 节中的网格划分方法只可以调整伪曲面网格的边界，内部的复 杂走势，是该方法所无法表现的，上述的这种偏差是2 1 节中的网格生成方法所 无法避免的。而2 1 节中给出的交互式调整方法只可以改善细微的纹理走势不一 致问题，对于比较严重的纹理走势不一致情况，该方法的调整工作量大，而且很 难保持纹理的大小一致性。 ( a ) 场景内部纹理走势 ( b ) 伪曲面网格走势 图2 5 纹理走势偏差 2 3 伪曲面网格建立方法的改进 2 3 1 控制网格建立 2 1 节中的网格牛成方法中各网格点之间以直线相连，这就导致只有网格点 足够密时才能近似地表现光顺性，而网格点过密计算复杂度相当高，按照3 3 节中的方法计算1 4 t 4 的网格需要3 0 秒，计算大于1 4 1 4 的网格时需要5 分钟 以上，而型值点以直线相连的1 4 1 4 的网格远远卜能光顺地表现纹理变形。 网格划分是体现映射真实感的关键步骤之一，此时网格划分是否有效地反映 场景纹理特征成为一个关键问题以图2 5 中的场景为例，场景中的被套具有 自身的折皱、明暗效果，例如，床铺本身的形状特点及摆放的不同姿态，使得被 套各部分发生相应的变形( 如收缩、凹凸、起皱、下垂等) ，自然面料也具有阴 影、纹理映射结果应能同时描述面料纹理、场景纹理的特点，所以网格划分需 要反映出场景中被套纹理的自然纹理信息不同的场景网格划分情况是不同的 首先，不同场景的自然纹理信息不同，网格的划分情况不同，太细影响效率， 太疏不能反映细节再者，同一场景的不同区域网格的疏密也不一样，信息复杂 的部分网格密集，反之则稀疏：网格的全貌反映场景纹理的走势这样就实现 网格划分的一般实现思想，如果网格划分的结果真实地反映场景变形( 如收缩、 凹n 、起皱、下垂等) ，网格节点还应具有连续性否则，映射的结果将是不光 1 4 顺的节点满足光顺性比较困难且效率低f ，本文利用三次样条曲线较好地实 现了一卜述要求。利用三次样条曲线良好的光顺性，使得稀疏的控制网格能较好地 放映纹理变形，然后再通过效率较高的三次样条细分算法细分控制曲面，最终生 成较好表现纹理变形的网格。 控制网格的网格点生成沿用2 1 节方法，首先勾勒控制网格边界，采用3 3 节的网格点计算方法生成完整网格，2 1 节的方法训算稀疏的网格效率是较高 的，根据经验控制网格一般为4 * 4 即足够，然后采用三次样条曲线连接各网格点， 保证每一条控制线均为光顺的三次样条曲线。最后可以调整网格点，调整完成后 进入第二步网格细化。图2 6 为控制网格实例图。 调整前 2 3 2 网格细化 图2 6 控制网格实例图 2 3 2 1 网格细分算法的分类 ( 1 ) 概念与术语 调整后 定义1 权图( m a s k s ) 表示由旧控制点计算新控制点规则的映射，其中新控制 点在映射中用黑点表示，在每个旧控制点旁边的数字代表细分系数。 定义2奇点( o d dv e r t i c e s ) 是在每一级细分中，按照某种细分规则所有新生 成的点。在三角网格中，奇点也就是边点，实际上是将每条边的中点作为一个新点 重新计算新的位置所得到的点。 定义3偶点( e v e nv e r t i c e s ) 是在每一级细分中，所有从上一级控制点继承得 到的点。 定义4 某顶点的价( v a l e n c e ) 是指与该顶点通过公共边相连的顶点个数。 定义5 正规点与非正规点( r e g u l a ra n de x t r a o r d i n a r yv e r 2 t i c e s ) 。在三 角网格细分过程中，产生的新点的v a l e n c e 在网格内部为6 、边界处为4 。定义 内部v a l e n c e 为6 、边界v a l e n c e 为4 的点为三角网格的正规点：类似地，内部 v a l e n c e 为4 、边界v a 2 1 e n c e 为3 的点为四角网格的正规点。不符合e 述条件 的点称为非j 卜规点。 定义6我们把控制网格中具有公共边的两个顶点称为邻接点。对于曲线而言， 给定控制点p i ，很显然( p i 一1 ，p i ) 和( p i ，p i + 1 ) 就是控制多边形的边，所 以p i 2l 和p i + 1 就是p j 的邻接点。对于任意控制点网格曲面而言，建立各控 制点之间的关系就是为网格中每个顶点找到相应的邻接点，为了方便算法的实现 对这些邻接点按照某种规则进行排列，我们把按照这种规则排列的邻接点的集合 称为该顶点的有序邻接表( o r d e r e da d j a c e n c yl i s t ) 。 ( 2 ) 细分算法的分类 一般情况下，对于网格细分算法的分类包括以下四个标准 ( 1 ) 生成网格的类型( 三角网格和四角网格) ： ( 2 ) 细分规则的类型( 面分裂和点分裂) ： ( 3 ) 算法是逼近型还是插值型： ( 4 ) 规则曲面的极限曲面光滑性( c 1 ，c 2 等) 。 表1细分算法分类 面分裂点分裂 三角网格四角网格d o o s a b i n | 1 5 逼近型 l o o p ( c 2 ) i n , , 2 1c a t m u l l c l a r k ( c 2 、1 4 1 m i d e d g e ( c 1 ) 插值型 m o d b u t t e r f l y ( c 1 、【1 3 】k o b b e l t ( c 1 ) b i q u a r t i c ( c 2 ) 表1 对现有的典型细分算法进行了分类。面分裂的细分方法，实际上就是一 种l 一4 的细分策略，如图2 7 ( a ) 所示。对于三角网格，在每一次细分过程中， 保留每个三角网格中所有旧控制点的同时，在网格的每条边上插入新点并两两相 连，然后与旧控制点一起得到四个新的三角网格：对于四角网格，除了在网格的每 条边上插入新点外，还需要在网格中间另外插入一个新点并与另外四条边上的新 点相连，从而得到四个新的四角网格。点分裂细分方法则是一种l n 的细分策 略，如图2 7 ( b ) 所示，n 为该点的v a l e n c e ，每个顶点将分裂为n 个新顶点，然后 按照一定的规则将新顶点重新连接组成新的网格。 1 6 三角型面分裂 蒸 r t i 四边型面分裂 ( a ) 面分裂 ( 3 ) 几种经典细分算法 鼻 。i ( b ) 点分裂( 四边形) 图2 7 两种分裂细分方法示意 在细分算法中比较具有代表性的包括l o o p 算法、改进的 蝶型算法、d o o s a b i n 算法以及c a t m u l l c l a r k 算法，下面对这几种细分 算法分别介绍并进行比较。 ( 1 ) l o o p 算法 l o o p 细分算法是美国犹他大学的c h a r l e sl o o p 于1 9 8 7 年在其硕士论文中 提出的一种逼近型三角形面分裂细分算法。它是基于b o x 样条的一种策略，应用 于规则网格时可以产生c 2 连续的曲面，在非正规点处则可达到c 1 连续。 ( 2 ) 改进的蝶型算法 蝶型细分算法最初由d y n ，g r e g o r y 和l e v i n 提出，它是一种定义在三角网 格上的策略，应用于规则网格时可以产生c 1 连续的曲面，在v a l e n c e = 3 和 v a l e n c e 7 的非正规点处则不能达到c 1 连续。蝶型细分算法不同于其他的基 于样条的逼近策略，它是一种插值型算法，因此不产生分段的多项式极限曲面。由 于该算法属插值类型，上一细分级别的所有控制点都位于曲面上，因此e v e n 点 无需重新计算，只要计算o d d 点即可。 ( 3 ) c a t m u 卜c l a r k ( c c ) 算法 c c 算法是一种基于张量积双三次样条的逼近型四边形面分裂细分策略，该策略 除了在非正规点处仅c 1 连续外可以达到处处c 2 连续。其细分规则源于双三次b 样条的细分权图，如图2 8 所示。 j f ij 6 。3 6 。6 2 4 。2 4 4 。2 4 。4 i l f 1 。6 。1 4 。4 4 。2 4 4 a r 图2 , 8 双三次b 样条的细分权图 1 6 1 6 i 1 6 1 6 c 图2 8 中，利用权a 可以得到和旧控制网格中每个点相对应的新控制点：权b 则生成对应于每条边的新点：而权c 生成的新点与控制网格中的每个面相对应。 这三种新生成的点分别称为v ( v e r t e x ) 型点、e ( e d g e ) 型点和f ( f a c e ) 型点。 显然，v 型点是o d d 点，e 型点和f 型点是e v e n 点。f 型点为其控制多边形的 质心；e 型点则取该边端点以及两个相邻多边形质心的平均值：v 型点的计算相 对复杂，它取决于该点的v a l e n c e ，而边界与褶皱上的细分规则与l o o p 格式相 同。 ( 4 ) d o os a b i n 算法 该算法从概念与原理上在几种细分算法中最简单，它是一种点分裂细分策略 仅使用一个权图就可以定义该策略( 对边界需要应用特殊的规则，实际上边界处 的极限曲线是一个二次样条曲线) 。d o n s a b i n 算法实际上是从t h a i k i n 快速 曲线生成算法的思想推广而来的一种生成光滑曲面的方法，生成的曲面可以达到 c 1 连续。 上面介绍了四种经典细分算法的概念、光滑性以及细分规则。它们都是基于 常规格式的细分算法，其中l o o p 格式和改进的蝶型策略是基于三角网格 的，c a t m u 卜c l a r k 和d o o s a b i n 算法是基于四角网格的细分方法。对于l o o p 格式、改进的蝶型策略以及c a t m u l lc l a r k 三种面分裂细分算法，在算法的实 现过程中需要以某个面为单位进行递归细分，其关键足根据算法的细分规则为每 个面上各个点建立有序邻接表( o a l ) ，但是由于o a | ，的构造比较复杂，而且在细分 的实现过程中会出现重复绘制的情况，因此这种通过有序邻接表来实现递归细分 的方法效率不高。d o o s a b in 细分算法是种点分裂细分策略。 ( 4 ) 我们的算法 在二维纹理映射系统中，网格细分的目标是在保留控制网格模型特征的基础 上生成具有光滑性的伪曲面网格。如上节所述，插值型细分算法继承了上一级控 制点即新网格中的偶点( e v e nv e r t ic e s ) ，这一特征恰好符合二维纹理映射希望 网格细分的要求，所以，我们设计了一一种基于三次样条曲线插值的网格细分算法。 设给定( n + 1 ) ( m + 1 ) 个二维网格控制点v 0 。，v 。v 岫的位置坐标，给定 期望细分后邻接点间曲线长度s u b d i v i s i o n l e n ，并将二维网格控制点保存在( n + 1 ) ( m + 1 ) 的二维数组中。 v2 、2 v 0 0v o l v l o v 1 1 _ v n 0v n l v o m v l m v u v n m 图2 9 控制网格二维数组 ” v 2 o 对这些网格顶点先后进行u 、v v 图2 1 0 控制网格割结果对二：维数组进行更 新。分割时新的曲线段长度均等于指定的曲线长度( s u b d i v i s i o n _ l e n ) ，这就保证 了细分后网格的均匀。以u 向左边界为例，它包含v 0 0 ，v i 1 ，v i 0 v n o ( o = i = n ) 共n + l 一个点，它们构成一条三次样条曲线，根据2 1 2 3 中( 7 ) 、( 8 ) 、( 9 ) 式： ( 7 ) 将每一段插入m 个点，参数t 的取值序点列为 立，堕，丛，m l , ( i ：1 2 ， 一1 )，”，o ， 州mm f 8 ) 由每一个t 的取值可得到每一段的m 个点 f ( r ) = ( x ，o ) ，y ，( f ) ) = 只+ p ? t + 马f + t + 色f + ，+ t i = 1 2 ，疗一l ，j = 1 ，2 ，m ； ( 9 ) 将( 8 ) 得到的各点用直线顺次连接，即可产生所求的三次参数样条曲线。 可以求出每对邻接点( v i 1 ，0 ，v i ，o ) 之间的所有点，根据两点之间的直线距离公 式可方便地求出相邻相邻两点之间的距离，累加所有相邻特征点( v i 一1 ，0 ，v i ，o ) 之 间的相邻点距离即可得相邻特征点之间的曲线距离，求出的每对邻接点之间的曲 线距离保存在大小为n 的数组s e g l e n s n e 0 。 t = i o 一。l - ( t x il ) 2 + ( _ y ，一y h ) 2 ( 1 ) r = s e g l e n s i 2 ( t + l 一) 2 + ( m + l 一只) 2 ( 2 ) t = 0 每对相邻特征点细分为s e g s u b n t m _ r o w i 段， s e g s u b n u m _ r o w i = ( ( s e g l e n s i