第32卷 第10期2009年10月
计 算 机 学 报
C HIN ESE J OU RNAL OF COM PU TERS
Vol.32No.10
Oct.2009
收稿日期:2009207215；最终修改稿收到日期:2009208227.本课题得到国家“八六三”高技术研究发展计划项目基金(2009AA01Z304)、国家自然科学基金(60673003,60603077)和山东自然科学基金(Z2006G05)资助.何 军，男,1982年生，博士研究生，主要研究方向为计算机辅助几何设计、计算机图形学.张彩明(通信作者)，男,1955年生，博士，教授，博士生导师，主要研究领域为计算机辅助几何设计、计算机图形学、医学图像处理.E 2mail :czhang @sdu.edu.
何 军1) 张彩明
1),2)
1)(山东大学计算机科学与技术学院 济南 250101)
2)
(山东经济学院计算机科学与技术学院 济南 250014)
摘 要 提出了一种三维模型尺寸调整的新方法.新方法通过对每条边的缩放来驱动模型尺寸的调整，然后以缩 放前后三角形法向的叉乘为目标函数项进行优化，几何意义上，该法向叉乘项表示极小化每个三角形的法向变化;Willmore 能量意义上，该项可以近似地极小化缩放带来的能量变化.对需要精确保持某些特征区域的模型，采用带约束的尺寸调整方法，通过引入拉格朗日乘数来求解满足约束条件的优化问题，从而能够精确保持模型的重要特征，目前已有的三维模型尺寸调整方法还不能做到这一点.最后，实例表明文中方法在调整模型尺寸的同时，既能很好地保持模型的敏感特征，也能精确保持某些重要的模型特征.关键词 三维模型尺寸调整；非均匀缩放；带约束的尺寸调整；法向叉乘中图法分类号TP391 DOI 号:10.3724/SP.J.1016.2009.02014
Feature Preserving R esizing of 3D Mesh Models
H E J un 1) ZHAN G Cai 2Ming 1
),2)
1)
(School of Com p uter S cience Technolog y ,S handong Universit y ,J i ′nan 250101)
2)
(S chool of Com puter S cience and Technolog y ,S handong Economic Universit y ,J i ′nan 250014)
Abstract This paper present s a new met hod for resizing 3D mesh models.The resizing is driven by scaling each edge of t he mesh.And an objective f unction co mponent ,which is exp ressed as t he cross p roduct of normal vector of every t riangle before and after scaling ,is devised to optimize t he resizing model.It s geomet ric meaning is to minimizing t he variation of normal vector of every t ri 2angle.In t he sense of Willmore energy ,t he cro ss p roduct item can approximately minimize t he variation of t he Willmore energy before and after resizing.For some important feat ured regions of t he model ,who se shape should be accurately preserved ,a const rained resizing met hod is also presented.Lagrange multiplier met hod is used to preserve t he shape of t hese regio ns.However ,e
xisting resizing met hods have not considered t he accurate p reserving of t hese important feat ured regio ns.Finally ,examples are included to show t hat t he new met hod can be used to resize 3D mesh models wit h feat ures p reserved well and important feat ured regions accurately p reserved.K eyw ords 3D model resizing ;non 2uniform scaling ;const rained resizing ;cross p roduct of nor 2mal vectors
1 引 言
20世纪90年代后期，随着三维扫描获取技术
的发展，数字几何模型逐渐成为一种新的数字媒体
形式，在工业制造、数字娱乐、数字文化遗产保护等方面取得了广泛的应用.大量的三维模型被构建出来，比如网络上的A IM @SHA PE 模型库和3D
CAD Browser 模型库以及普林斯顿大学的3D 在线
模型检索系统.在丰富的模型资源中，三角网格模型
因其结构简单、表达能力强、直观易用等优点成为使用最广泛的模型格式.随着各种模型库的建立和逐渐充实，在设计工作中，如果能够有效地利用已有的这些模型资源，无疑会大大提高设计效率.但是，要到一个完全符合应用要求的模型并不容易，可能仅仅因为尺寸不符合要求，已有的三角网格模型就不能直接拿来使用.比如:(1)由于应用场景的改变，一个模型必须改变尺寸适应场景的要求后才能使用;(2)基于实例的建模[1]中，从模型库中到匹配的部件后，通常其各部件的尺寸并不匹配.这都需要对已有模型进行尺寸调整以满足具体应用的要求.当然，在调整尺寸的同时，模型的主要特征需要尽量得到保持或者某些重要特征需要精确满足特定的要求，这也就是带约束的模型尺寸调整问题.比如，在对零件进行尺寸调整的同时，保证该零件和其它零件的兼容性就是一个常见的应用需求.
关于模型尺寸调整，最直观的思路是沿模型的长、宽或者高方向对模型直接进行均匀缩放，使之满足目标尺寸要求.但是，如图1(b )所示，将模型沿Z 方向均匀缩放115倍后，模型下面的球形特征被扭曲.可见，从感知的角度来说，人对模型各部位的感知是不均匀的，有的区域会得到更多的注意，因此人对于这里发生的扭曲很敏感，缩放的时候就需要对这些区域特别关注，这就需要对模型做非均匀的缩放.Kazhdan 等[2]提出了各向异性缩放的概念，但是，在每个缩放方向上(沿X ,Y 或Z 轴)，仍然是均匀缩放，因此不便于保持模型的敏感区域特征.Vladislav 等[3]于2008年首次提出对三维模型进行内容相关的尺寸调整问题.该方法着重保持感知敏感区域的特征，将尺寸变化带来的变形或者扭曲尽量分布到
模型的非敏感区域，取得了比较好的效果.但是，该方法不能精确保持模型的特征.在精确性要求较高的工程应用中，仍然不能满足需要
.
图1 麋鹿模型沿Z 轴的缩放
本文提出一种新的保持模型特征的尺寸调整方法，可以很好地保持模型的感知敏感区域的特征，将变形尽量分布到非敏感区域.同时，对于有精确要求的工程应用，通过带约束的模型尺寸调整方法，针对这些特征引入硬约束，这样在对模型尺寸变化的同时，模型的指定特征能够精确地满足给定的条件，从而可以很好地满足实际应用的要求.
本文的主要工作:(1)采用缩放前后面片的法向叉乘作为新的模型缩放的优化项;(2)提出带约束的模型尺寸调整方法，通过引入拉格朗日乘数求解满足约束条件的优化问题，从而可以精确保持模型的重要特征.本文第2节介绍模型尺寸调整的相关工作；模型尺寸调整问题的具体描述在第3节给出；第4节具体讨论新的尺寸调整方法，包括基本思想和目标函数；关于带约束的模型尺寸调整将在第5节中讨论；第6节给出实验结果和分析；最后，结
论和进一步的工作在第7节中讨论.
2 相关工作
三维模型的尺寸调整，本质上是一种特殊的模型变形方式.目前主要的网格模型变形方法有基于空间的变形、基于表面的变形、多分辨率的变形等.早期的变形方法都是假设模型由同一种材料组成，变形是均匀分布的.因此，为了有效地处理包含多种材料属性的模型，又引入了材料相关的模型变形方法[426]，根据材料属性的不同，变形在模型上的分布是非均匀的.但是，使用现有的变形方法对模型进行非均匀缩放，不仅需要施加复杂的约束条件，还要指定相应的材料属性等等，操作过程通常是比较繁琐的.因此，这就有必要对模型的缩放问题进行专门的研究.
最近，在图像和视频领域，内容相关的尺寸调整已经得到广泛的关注和研究[7211].Avidan 等[7]展示
5
10210期何 军等：保持特征的三维网格模型尺寸调整
了通过将误差分布到有限的“缝”集合，图像的大部分像素维持不变从而使图像的整体得以保持.与此相反,Gal等[8]提出的方法采用全局的观点使误差在所有像素内分布.这样的全局观点使得图像的重要区域可以旋转或者均匀缩放，从而将误差尽可能地分布到非重要区域.
十七大报告
2008年,Vladislav等[3]将内容相关的图像尺寸调整推广到三维网格模型，提出了一种基于空间的非均匀尺寸调整方法.首先将网格模型嵌入到保护性格中；接下来基于面的slippage敏感性分析和法曲率，确定每个格的缩放因子；然后将模型的整个格缩放到指定大小；最后，重新计算得到新的网格模型.最近,Wang[12]等基于表面的变形方法，也提出一种内容相关的三维模型尺寸调整方法.该方法通过边的敏感性分析(也是根据slippage和法曲率)，确定每条边的可伸缩性，采用迭代的方法逐步将模型缩放到指定的大小，将缩放带来的变形主要分布在非敏感的部分.这两种方法，能够在一定程度上保持模型的敏感区域，但是都不能精确保持某些特征，这使其应用受到很大的局限.
对网格曲面的约束变形问题,Masuda等[13]基于表面的变形方法，由用户提供重要性映射，从而将扭曲变形分散到整个模型.在变形中，通过硬约束保持某些重要的Form feat ures及其可能的共线、共面关系.
对带约束的Nurbs曲面缩放最初的方法是Zhang等[14]提出的Attach2and2Deform方法.该方法先把原曲
面按要求进行缩放，然后把要保持的特征附加到已缩放的曲面上.附加特征的操作会使已缩放的曲面产生变形，为了保证这个变形最小，使用了一个目标函数.该方法效果不甚理想，所允许的放大倍数很小，且曲面特征不能保持完全不变.2001年,Zhang等[15]提出了Fix2and2St retch方法，该方法能够允许更大的放大倍数，且可以保证要保持的特征完全不变.该方法的基本思想是先将给定曲面上含有特征和剪切曲线(trimming curve)的区域固定住，再延展曲面的其余部分，使其和靠近边界的部分光顺地过渡.伯彭波等[16]采用一个完全基于几何概念的新的目标函数———导矢叉乘目标函数.该目标函数在导矢叉乘平方的积分意义下，保证了两曲面在各点的法向尽可能地接近，从而在高光线意义下保证了新、旧曲面的形状最为接近.上述几种带约束的Nurbs曲面缩放可以保持曲面上含有特征和剪切曲线的区域形状不变，但是，对其余区域采用的是均匀缩放的方法，而且，这些方法还没有用于网格的缩放.
3 问题描述
三角网格模型可表示为M=(V,E,F)，其中V 为顶点集合,E为边的集合,F为三角形面片集合.给定一个三角网格模型以及模型上需要保持的重要特征集合C,C主要包括用户交互指定的需要精确保持的重要特征区域或者特征线、边等.本文的目标是对该模型进行尺寸调整，通过沿长宽高方向做适当的缩放来实现.缩放后的模型为M′=T s M.要求M′能够保持模型的形状特征，而且对于C中的重要特征则要精确满足.这里,T s是模型的整体缩放因子:
T s=〈S x,S y,S z〉,
其中,S x,S y和S z分别是X,Y,Z方向的缩放因子.这里假定这3个坐标轴方向与模型的长宽高3个方向一致(如果不一致，可先进行坐标变换).因此，本文只考虑沿坐标轴方向对模型进行缩放.
4 模型的尺寸调整
三角网格模型由点、边及面构成，对模型调整尺寸，其直接表现就是每条边的边长和每个三角形面片的面积都发生了一定比例的缩放.反过来考虑，如果对网格中的每条边(或者每个三角形面片)都进行缩放，那么必然导致模型整体尺寸发生变化，从而达到调整尺寸的目的.基于这个简单的观察，本文方法通过对网格的每条边进行一定比例的缩放，从而驱动整个模型的尺寸调整.例如，每条边都放大2倍，其结果也就是整个模型放大了2倍.
由引言的讨论，人对于模型各部位的感知是不均匀的，为了保持模型的敏感区域，就需要对模型进行非均匀的缩放.也就是说，在模型的缩放中，模型的每条边都有一个缩放因子.那么，如何为每条边选择合适的缩放因子呢?对此,Wang等[12]最近提出将每条边视为一根弹簧，使用模型的每条边因缩放而产生的弹性能量做最小二乘，从而优化得到缩放后的模型.其基于边定义的弹性能量缺乏从整体上反映模型网格表面变化的能力.因此，本文提出以缩放前后三角形面片的法向叉乘作为目标函数进行优化，在几何意义上，该目标函数可以极小化三角形面片的法向变化；在Willmore能量意义上，使用本文
6102计 算 机 学 报2009年
方法，可以优化模型缩放带来的能量变化.注意，本文方法不能精确地极小化缩放带来的能量变化，这是因为本文采用的Willmore能量并非曲面精确能量，而极小化Willmore能量变化本身也会导致非线性问题，而本文方法只是近似的线性化的方法.
考虑到边长和法向均与几何位置无关，因此通过添加顶点位置约束来确定模型的位置.综上所述，本文使用如下目标函数对模型进行缩放
E total=αE scale+βE nv+γE pos(1)其中,E scale是边缩放项,E nv是极小化三角形面片的法向叉乘项,E pos是顶点位置约束项,α,β,γ分别是3项所占的权重，第6节中对如何确定这些权重进行了讨论.
4.1 边缩放项E scale
E scale的目的是驱动模型的缩放，方法是通过对网格的每条边进行缩放，其表达式如下:
E scale=∑
i∈E (v′i0-v′i1)-T s(v i0-v i1)
(v
i0
-v i1)+ε
2
(2)
其中,v
i0
,v i1和v′i0,v′i1分别是网格边e i缩放前后的两个端点.ε是扰动项，用来避免出现分母为零的情况(本文使用ε=10-6)，这是因为具体缩放过程中是对T s的逐个方向依次进行缩放的，因而在某个方向上的边长可能出现零值的情况.
事实上,E scale的定义中，式(2)使用的是衡量每条边在缩放方向上的变化误差情况.通过引入原边长做分母，误差度量中使用的是相对误差，从而对网格中较长的边和较短的边都能起到同等的约束作用，因而用于不均匀网格模型(本文中表示边长相差较大的模型)时，也能得到很好的结果.
4.2 法向叉乘项E nv
顾名思义，式(1)中的法向叉乘项E nv可表示如下:
E nv=∑
i∈F N′f
i
A f
i
×N f
i
2
(3)
其中,A f
i 是原模型中面片f i的面积,N f
i
是缩放前市政道路工程
面片f i的单位法向，缩放后的法向N′f
i
=e′01×e′02, e′j k(j=0,1,2;k=0,1,2)是三角形f i的一条边.注
意，这里的N′f
i 并非单位向量，所以使用A f
i
做近似
单位化.
如果同时对模型进行X,Y和Z方向的缩放，会导致非线性问题.因此，本文方法每次仅对某一方向使用相
应的缩放因子分别进行缩放.这样，问题就简化为将模型在某一方向上进行缩放.比如，以在Z 方向上进行缩放为例，这时,
N′f
i
=(v′i1-v′i0)×(v′i2-v′i0)
=(y01z′02-y02z′01,z′01x02-z′02x01,x01y02-x02y01).因此只有z′01和z′02中含有未知数z′0,z′1和z′2.N′f
i
可
简记为(N′i x,N′i y,N′iz),N f
i
简记为(N i x,N i y,N iz)，从而，式(3)可整理如下:
E nv=∑
i∈F
(N′i y×N i z-N i y×N′i z)
A f
i
,
(N′i z×N i x-N i z×N′i x)
A f
i
,
(N′i x×N i y-N i x×N′i y)
A f
i
2
=∑
i∈F
(N′i y×N i z-N i y×N′i z)
A f
i
2
+
(N′iz×N i x-N iz×N′i x)
A f
i
2
+
(N′i x×N i y-N i x×N′i y)
A f
i
2
,
因此，可以通过解线性方程组求解.同理，可沿X和Y方向进行缩放.
4.2.1 E nv的几何意义
从几何意义上来说,E nv实质上就是极小化法向的变化.两个法向量的叉乘
‖
n′×n‖=‖n′‖·‖n‖sin(θ),
θ是两向量的夹角，在缩放的过程中0<θ<
π
2
.图2是一个二维的示例，对线段ab沿X轴拉伸(即在X轴上放大)得到a′b′，其法向的夹角为θ，显然0<θ<
π
2
，同理三维空间中，沿某一轴方向缩放时，三角形的法向变化角度满足0<θ<
π
2
.在此区间内, sin(θ)是单调的.又由于两个向量一个是单位向量，一个是准单位向量(因为使用原三角形面积进行了近似单位化)，所以，极小化两个向量的叉乘，也就是要是其夹角θ极小.而且,sin(θ)对于θ的较小的变化非常敏感，因此可以有效地极小化法向的变化.
图2 2维空间中线段ab缩放到a′b′的法向变化示例
进一步的，在几何意义上，法向叉乘的目标函数优化项有如下特点:
(1)E nv是缩放无关的.将一个模型整体缩放s
7102
10期何 军等：保持特征的三维网格模型尺寸调整
倍，其每个三角形面片的法向不变，因此E nv为零;
(2)可以较好地保持模型的特征.一般地说，模型上法向的变化能够较好地反映模型的特征[17]；而且，法向对尖锐特征和高曲率区域更加敏感;
(3)能够较好地保持模型的高光线特性.工业设计中，高光线模型[18]是常用的检测曲面光顺性的重要工具，而高光线模型也是利用了曲面的法向会放大曲面的不光顺性.因此，极小化缩放前后网格模型中每一个面片的法向变化，能够较好地保持模型的高光线特性.
4.2.2 从曲面能量观点看E nv
本节根据Willmore能量进行分析，说明E nv可以近似地极小化缩放前后模型的Willmore能量变化.
对一个三角形网格，在属于v i的网格表面上，总的绝对平均曲率[19]为
| H i|=∫A i|H i|=14∑d j=1‖e j‖|βj|(4)其中,|H i|是v i点处的绝对平均曲率(即平均曲率的绝对值),d为v i的度
数,e j是与v i邻接的边,βj是共享边e j的两个三角形面片法向的夹角,A i为属于v i的网格表面面积，可定义为v i的所有邻接三角形面积总和的三分之一.易得v i点处的绝对平均曲率为
|H i|=| H i|/A i(5)三角网格表面的离散Willmore能量[20]可以定义为
E=∑
i∈V
H2i A i(6)将式(5)代入式(6)整理可得
E=∑
i∈V ∑d
j=1
‖e j‖|βj|2/16A i(7)
注意到，将上式的分子部分展开，主要含有如下两种类型
‖e j‖2|βj|2
16A i ,
‖e j‖‖e k‖|βj||βk|
16A i
(8)
其中,1ΦkΦd且k≠j.注意到式(8)中分子含有边长的平方项或者乘积项，而分母中含有面积项，如果v i的邻接边长度差别不大,A i=d‖e‖2sin(θ)/6，约去边长的平方项，分母上剩下sin(θ)项，而θ在π/2左右时sin(θ)的变化不敏感.即如果A i可由v i的邻接边长度的平方来近似表示，那么随着缩放项E scale 开始驱动对模型进行缩放，极小化邻接的两个三角形法向的夹角变化，就可以近似地极小化模型缩放的能量变化.但是，法向夹角的约束优化是非线性问题，将其转变为极小化每个三角形面片的法向变化最小.因此，本文采用的方向叉乘项E nv可以近似地极小化缩放前后模型的Willmore能量变化.
4.3 位置项E pos
本文方法是按T s的各个缩放轴S u,u=x,y,z 方向依次进行缩放.因此，首先出沿坐标轴方向的包围盒，假设其左下角和右上角的两个顶点分别是v min和v max；然后选择在u方向上包围盒一端的顶点，其选取条件是(v i-v min)·uΦε′，其中u是缩放方向向量,ε′使用10-12即可，选取的约束顶点记为b i(i当爱已成负担
=1,2,…,p).最后添加位置约束
E pos=∑
p
i=1
(u
b′i
-u
b i
)2(9)
其中,u
b i
,
u
b′i
分别是缩放前后b i的u轴坐标.高坠
4.4 缩放到指定尺寸
虽然式(2)中使用目标缩放因子T s对边长进行了缩放，但是，由于法向叉乘项E nv的约束优化作用，对初始模型缩放一次一般不能满足目标尺寸要求.为此，本文采用迭代方法，就是通过迭代到合适大小的边缩放因子.
为简化问题的讨论，假定沿u方向进行缩放，第一次缩放使用该方向上的目标缩放因子S d.缩放后，通过计算包围盒的缩放，得到模型的实际缩放倍数S′1.对第n次缩放，可以建立如下关系
S n
S′n
=
S n+1
S d
(10)其中,S d为目标缩放因子,S n+1为下一次缩放所需的缩放因子.要达到实际缩放S d倍，则S n+1=S n
×S d
S′n
西辽河.然后，以令S=S n+1为缩放因子再次进行缩放.
迭代多次，当达到|S′-S d|小于某一阈值(本文使用0101)或者迭代达到一定次数以后，停止迭代. 5 带约束的模型尺寸调整地面沉降
对模型的重要特征集合C中某一个特征(一条特征边或线，或者一个特征区域等)，本文使用模型顶点集合c i(i=0,1,2,…,m)来表示.因此，要保持该特征不变，只需要对该顶点集合中的网格顶点添加约束条件，保持它们之间的相互距离.一个特征区域至少包含2个顶点(一条特征边)，本文通过保持顶点间的相对位置来保持特征不变，因此，特征的形状约束条件如下
c′i-c′0=c i-c0,i=1,2,…,m(11)
8102计 算 机 学 报2009年
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议