摘要 针对传统骨架驱动变形方法中模型细节特征不能得到有效保持的问题，提出一种基于细分的骨架驱动网格模型变形方法。首先，对网格模型待变形区域基于截交线进行局部骨架提取和控制网格构建，分别建立骨架与控制网格以及控制网格所对应细分曲面与待变形模型区域之间的关联关系；然后，将基本函数作用下的自由变形方法应用于骨架变形，通过骨架变形驱动控制网格变形，将变形前后控制网格所对应细分曲面的变化信息转为网格模型泊松梯度场的改变；最后，根据改变后梯度场重建网格模型。实例表明，该变形方法针对不同网格模型均可以得到较好的编辑效果，且细节信息在变形后都得到了有效保持。与传统骨架驱动变形方法相比，该方法除具备交互操作简单直观的优势外，同时能够更好保持变形模型几何细节特征，更为适合具有丰富几何细节的复杂模型的变形编辑。
关键词 网格变形；骨架驱动；细分曲面；泊松梯度场；细节保持
中图分类号 TP391.72
文献标志码 A
0引言
骨架驱动变形技术因其控制手段灵活、操作简单一直是曲面造型领域研究的热点问题。现实中很多动植物（包括人体模型或工业产品模型都具有明显的骨架特征，可通过施加骨架驱动变形来实现模型的运动模拟或变形设计。目前骨架驱动变形技术已广泛应用于动画、工业产品设计、生物医学、航空航天等众多领域。
针对骨架驱动变形方法，国内外研究学者做了大量的工作。其中，文献[1-2]分别通过引入势函数元球和勾画线实现骨架直接驱动的模型变形，但变形后模型容易产生自交、畸变，同时其细节特征也不能得到有效保持；Capell等[3]将模型嵌入控制网格，骨架驱动控制网格，模型随控制网格变形而变形，该方法同样不能有效保持模型的细节特征且变形操作复杂；文献[4]以网格模型的简化模型作为控制网格，通过操纵骨架对简化模型进行变形，继而利用变形后简化模型顶点对原网格模型进行Laplacian变形，该方法引入微分域网格编辑技术有细节特征保持的优势，但简化网格形状与原网格模型贴合性较差，故影响到模型的变形质量。
文献[5]将细分技术引入到基于控制网格的变形方法中，采用任意拓扑的细分网格控制模型变形，使控制网格与模型表面更加贴合；但调节控制网格顶点实现变形，过程较为繁琐，且其变形也是对模型顶点坐标的直接操纵，对于细节特征较为丰富的模型，变形结果也不能有效保持其细节特征，可能出现变形不自然、扭曲等变形缺陷。
本文提出一种基于细分的骨架驱动网格模型变形方法。该方法具有传统骨架驱动变形方法交互操作简便的优势；同时将细分技术引入模型变形，细分曲面作为中间变形控制曲面，更为贴合模型表面形状，可更好保证模型变形效果；另外，该方法融合了泊松网格编辑的优势，能够有效保持变形模型细节特征。
1基于细分的骨架驱动变形流程
基于细分的三维网格模型骨架驱动变形流程如图1所示。首先对模型变形区域骨架进行提取，同时构建变形区域控制网格；然后通过骨架变形驱动控制网格变形，根据变形前后细分控制曲面实现模型变形。
2变形区域局部骨架提取
骨架作为网格模型信息的压缩表示，其提取质量的好坏直接影响骨架驱动模型变形质量。现有骨架提取方法主要有拓扑细化法、距离变换法、Voronoi图和Reeb图法，以及手工提取方法等[6-7]。这些方法中有的可以实现骨架的自动提取但算法比较复杂；有的通过交互方式得到骨架，算法简单但交互过程过于繁琐，甚至得到的骨架不够精确。文中变形作用于模型局部区域，骨架提取采用了基于截交线的交互式提取方法，具体提取步骤如下：
首先，在拟提取区域边界位置，按一定方向拾取若干网格顶点，利用Dijkstra算法[8]，根据这些顶点划定局部区域边界；然后在边界内拾取任意网格顶点作为种子点，基于种子生长算法[9]确定模型变形区域网格；之后，在待变形区域首尾处根据不共线三点确定一个平面，通过在模型表面拾取顶点的方法，交互确定初始截平面，并自动插值得到若干中间等分截平面；最后，求解这些几何截面与变形区域网格的截交线，基于截交线得到变形区域局部骨架。
以下详细给出等分截平面概念及生成算法：
1如图2所示，首先对两端初始截平面S0和S1的法向量n0和n1进行叉乘，得到旋转轴，然后由空间向量夹角公式得到旋转角度λ；
2根据要插入的预设等分截平面个数，这里不妨设为h-1个，对旋转角度λ进行h等分；
3求解S0和S1两初始截平面中心点，将其连接线段h等分，分别得到h-1个等分顶点Ci（i=1，2，…，h-1；
4由初始截平面S0的法向量n0分别绕旋转轴旋转角度值（λ·i/h（i=1，2，…，h-1，得到各等分截面的法向量pi（i=1，2，…，h-1；
5根据各等分顶点Ci（等分截面上的点和等分截面的法向量pi，可求得各等分点处截平面。
根据所确定的初始和等分截平面，求解它们与变形区域网格的截交线，将截交线的几何中心（即骨架点顺序连接即得到变形区域网格局部骨架。图3所示给出了骆驼腿部的骨架提取效果。
3构建变形区域控制网格
变形区域控制网格的构建是文中基于细分的骨架驱动变形方法中至关重要的环节，直接关系着后续细分控制曲面与网格模型关联关系的建立，影响着模型最终变形质量。本文基于截交线构建变形区域控制网格，所生成控制网格具有和变形区域网格模型拓扑一致、形状相似的特点。以下给出构建的大体步骤：
1分别对每条截交线进行简化；
2根据简化后每条截交线各顶点，分别构造三次B样条插值曲线；
3分别将每相邻B样条插值曲线控制多边形的各个控制顶点按一定规则进行连接，生成控制网格。
3.1截交线简化
本文对截交线进行简化，采用了基于最小面积和最小角度的顶点删除算法[10]，可以根据所需简化效果实时改变简化程度。以下给出具体简化算法。
设某条截交线顶点个数为t0，顶点限制夹角为β，简化后顶点个数为t1，则执行如下步骤。
1分别求出截交线上各顶点与其相邻的两顶点组成的三角形面积，并按面积从小到大的顺序将顶点序号存入集合K和集合K1。
2判断集合K中第一个顶点与截交线上相邻顶点的夹角是否大于β：若大于，对该顶点进行删除，连接两相邻顶点；否则，对集合K中下一个顶点进行判断，以此类推，直到找到夹角大于β的顶点。
3判断集合K中顶点序号的个数和集合K1中顶点序号的个数是否相等：若相等，则表示已满足β夹角条件，执行步骤5；若不相等，执行步骤4。
4判断集合K中顶点序号的个数是否为t1：若是，执行步骤5；否则，清空集合K和K1，执行步骤1。
5用户观察简化后的截交线是否达到所需要求：若达到，结束简化；否则，清空集合K和K1，重新设置限制夹角β和顶点个数t1，执行步骤1。
3.2构造三次B样条插值曲线
不妨设简化后截交线共有m个顶点，以qi（i=0，1，…，m-1表示，根据这些顶点构造三次B样条插值曲线为封闭曲线，这里以dj（j=0，1，…，m-1分别表示封闭曲线控制多边形各个控制顶点，令dm=d0，dm+1=d1，dm+2=d2。则满足：
p（ui=∑ij=i-3djNj，3（ui=qi-3； i=3，4，…，m+2（1
式（1可看作由m个未知数构成的线性方程组，其中Nj，3（u为三次规范B样条基函数。对方程组求解即可得到三次B样条插值曲线控制多边形的m个控制顶点。
3.3变形区域控制网格的生成
将每相邻B样条插值曲线控制多边形的各个控制顶点进行连接，即可得到变形区域控制网格。图4所示给出了控制网格生成示意图，下面就连接的具体算法进行详细说明。
1首先在一条B样条曲线控制多边形上选定一个顶点作为连接开始点G0；
2在与相邻B样条曲线控制多边形上搜索与G0最近的顶点作为搜索的起始点H0；
3两控制多边形分别从G0、H0两点绕相同方向搜索，顶点G0、G1、H0、H1组成四边形，连接该四边形对角线较短的G1、H0两顶点，G1、H0两顶点作为两控制多边形新的搜索起始点，按照此规则连接控制多边形上的顶点；
4当一控制多边形L0上的控制顶点已连接到开始点H0，另一控制多边形L1还有控制顶点没有连接，直接将剩余的控制顶点连接到控制多边形L0的开始顶点H0。
上述算法生成的初始控制网格存在两个问题：1模型变形区域的变形端部控制网格不能完全包络模型；2模型变形区域的变形端部控制网格未封闭；这都将较大程度地影响模型变形端部的变形质量。为提高模型变形质量，本文针对变形区域变形端部控制网格不能完全包络模型的问题，对控制网格和骨架线进行适当的外延，在变形质量较好的前提下，使待变形区域尽可能落在控制网格内；针对控制网格变形端未封闭问题，对变形端的控制多边形各顶点和其对应的骨架点相连接。
4骨架驱动控制网格变形
4.1骨架变形
本文将基本函数作用下的自由曲线变形方法[11-12]应用于骨架变形。
定义Q是骨架上任意骨架点，Q*是变形后此骨架点的位置，P为约束骨架点，P*是约束骨架点移动后的位置，P*v是一个与P*相对应的虚拟控制骨架点。则骨架变形满足：Q*=Q+F（Q，P，P*，P*υ，其中，F（Q，P，P*，P*v是基本函数或由基本函数组合成的复合函数。
基本函数可以是多种形式，本文采用F（Q，P，P*，P*υ=γe- Q-Pα2ε2·（Q-P*，可以通过调节γ、α和ε三个参数值来实现不同的骨架变形效果。图5所示为约束骨架点的位移，图6（a、（b分别给出了不同参数γ下的骨架变形效果。
根据流程图，若变形前骨架为直线，可先建立变形后骨架上各点的局部坐标系，对变形前骨架上各点，其局部坐标系的u、v、w三个坐标轴方向均与变形后骨架首点局部坐标系各轴方向一致。若变形前骨架不是直线，这时先对变形前骨架上各点建立局部坐标系，然后对变形后骨架进行分析，若变形后骨架为直线，则其上各点局部坐标系各轴方向与变形前骨架首点相一致；若变形后骨架不为直线，假设其上骨架点Vk（k∈[0，i]均与变形前对应骨架点位置相同，则针对各骨架点Vk（k∈[0，i-1]，局部坐标系的各轴方向与变形前对应骨架点局部坐标系相一致，对于其他骨架点局部坐标系的建立参照流程图进行。
以下针对流程图中的内容进行相关说明
1第i点局部坐标系建立。
如图8所示，不失一般性，以骨架点Vi的局部坐标系建立为例，与Vi相邻的两个顺序骨架点分别为Vi-1和Vi+1，则首先确定ui=e1/‖e1‖（e1表示骨架点Vi-1到Vi+1的向量；然后，过点Vi以ui为法向量作平面T，求前骨架点Vi-1在T上的投影点P，确定vi=e2/‖e2‖根据流程图，若变形前骨架为直线，可先建立变形后骨架上各点的局部坐标系，对变形前骨架上各点，其局部坐标系的u、v、w三个坐标轴方向均与变形后骨架首点局部坐标系各轴方向一致。若变形前骨架不是直线，这时先对变形前骨架上各点建立局部坐标系，然后对变形后骨架进行分析，若变形后骨架为直线，则其上各点局部坐标系各轴方向与变形前骨架首点相一致；若变形后骨架不为直线，假设其上骨架点Vk（k∈[0，i]均与变形前对应骨架点位置相同，则针对各骨架点Vk（k∈[0，i-1]，局部坐标系的各轴方向与变形前对应骨架点局部坐标系相一致，对于其他骨架点局部坐标系的建立参照流程图进行。
以下针对流程图中的内容进行相关说明
1第i点局部坐标系建立。
如图8所示，不失一般性，以骨架点Vi的局部坐标系建立为例，与Vi相邻的两个顺序骨架点分别为Vi-1和Vi+1，则首先确定ui=e1/‖e1‖（e1表示骨架点Vi-1到Vi+1的向量；然后，过点Vi以ui为法向量作平面T，求前骨架点Vi-1在T上的投影点P，确定vi=e2/‖e2‖
2骨架点局部坐标系补建。
分两种情况进行说明：①第i骨架点Vi局部坐标系已定，补建k∈[0，i-1]连续骨架点Vk局部坐标系；②第i骨架点Vi局部坐标系已定，补建k∈[m，i-1]∪[i+1，n-1]连续骨架点Vk局部坐标系。两种情况下的求解步骤类似，首先确定uk，当k=0时（即Vk为骨架首点，u0=f1/‖f1‖（f1表示骨架点V0到V1的向量；当k=n-1时（即Vk为骨架末点，un-1=f2/‖f2‖（f2表示骨架点Vn-2到Vn-1的向量；否则，uk=f3/‖f3‖（f3表示骨架点Vk-1到Vk+1的向量，然后根据ui×uk确定旋转轴xk，ui·uk确定旋转角度θk，将Vi骨架点局部坐标系绕轴xk旋转角度θk即得到骨架点Vk局部坐标系。
3局部坐标系后处理。
为避免骨架发生大扭转，需要分别对变形前后骨架局部坐标系进行后处理。分别以Vi和Vi+1表示骨架上两个相邻的骨架点，判断其局部坐标轴wi和wi+1的夹角是否大于π/2，若是，则令Vi+1骨架点局部坐标轴vi+1和wi+1方向取反。
4.3骨架驱动控制网格变形方法实现
骨架驱动控制网格变形实现主要涉及三个步骤：1控制网格顶点与骨架之间关联关系的建立；2控制骨架变形前后对应关联点局部坐标系的建立；3控制网格顶点位置更新。针对第2步，4.2节中给出了详细过程，以下分别就第1和第3步进行具体说明。
考虑到本文变形区域控制网格的构建是将每相邻截平面内B样条插值曲线控制多边形的各个控制顶点进行连接而实现的，每个截平面都对应一个骨架点，因此针对控制网格顶点与骨架之间关联关系的建立，本文采取较为简单的方法，使处于一个截平面内的所有控制网格顶点都与其所在截平面的骨架点相关联。
针对第3步，当骨架变形时，控制网格顶点关联骨架点的位置及局部坐标系发生改变，而控制网格顶点局部坐标值不变，由此可计算变形后控制网格各顶点位置。不失一般性，设控制网格顶点Vm，关联骨架点为Vs，于Vs处建立局部坐标系三个单位轴是u、v、w，则Vm可表示为：Vm=Vs+xu+yv+zw，其中x、y、z分别表示Vm在局部坐标系下的局部坐标值。骨架变形后，关联骨架点位置改变为V′s ，其局部坐标系变更为u′、v′和w′，则控制网格顶点Vm位置更新为：V′m=V′s+xu′+yv′+zw′。
需要说明的是骨架驱动控制网格在进行一定程度的大角度变形时，变形后的控制网格会出现不可避免的局部自交现象。为不影响模型的后续变形质量，需要对变形后控制网格上的三角面片进行相交性检测[13]；然后对产生自交的控制网格顶点进行修正。
5细分控制网格
细分曲面是指通过采用一定加密规则对初始控制网格进行逐层加密顶点所得到的极限曲面。根据加密规则的不同，有很多种细分方法，其中应用最多的主要有4种：CatmullClark细分、Loop细分、蝶形细分以及DooSabin细分。
本文对变形前后控制网格进行有边界CatmullClark细分，细分之后网格面片均为四边形，为有效建立待变形模型与细分控制网格之间的关联关系，需要对CC细分网格进行三角化处理。对于细分次数的选择，因对控制网格细分次数越多，细分曲面越光顺，模型变形效果越好，但考虑时间开销，这里一般取细分1～2次即可满足变形要求。
6泊松变形方法实现
泊松变形[14-15]求解是本文基于细分的网格模型骨架驱动变形方法的最后环节，也是最为重要的一个环节。首先需要建立控制网格所对应细分曲面与待变形模型区域之间的关联关系；然后通过骨架驱动控制网格变形，将变形前后控制网格所对应细分曲面的变化信息转化为待变形网格模型泊松梯度场的改变，根据改变后梯度场对模型变形局部区域进行重建。
6.1关联关系的建立
控制网格所对应细分曲面与待变形模型区域之间的关联求解主要涉及2个方面：1求解待变形模型区域内每个三角面片中心在细分曲面上的关联位置；2求解待变形模型区域内每个顶点在细分曲面上的关联位置。这里关联位置也即在细分曲面上距离最近的点，此点可能是细分网格顶点，也可能在网格边上，或在网格面内。
通过2的求解，针对待变形模型区域网格顶点在细分曲面上的关联位置，可提取其邻域网格，继而判断细分曲面变形前后，邻域网格所有顶点位置是否均保持不变：若是，将此类待变形模型区域网格顶点称为约束顶点，这些顶点即构成泊松求解的边界条件；否则，称为自由顶点。对于模型变形区域内任意三角面片，若三个顶点不全为约束顶点，则这种三角面片集合即构成泊松变形自由区域，模型局部旋转、缩放变换正是基于这些三角面片进行。
通过1的求解，对于泊松变形自由区域内任意三角面片，都可以得到其在细分曲面上的关联位置，于变形前后细分曲面对应关联位置处分别建立局部正交标架及求解邻域细分网格局部周长，就可以确定变形自由区域内任意三角面片的局部变换，用于泊松方程的求解。
6.2关联位置局部标架的建立
不失一般性，以关联位置位于细分网格某三角面内进行说明，其他情况可以作类似求解。
如图9所示，设R为细分网格上某关联位置，首先需求解R处法向量m0。其所在三角面片三个顶点的平均法向量分别以m1、m2、m3表示，是通过将每个顶点周围邻域三角形的单位法向量进行面积加权平均得到，则R处法向量m0即可表示为： m0=am1+bm2+cm3。
关联位置R处建立局部正交标架，其中一个方向即上面所求得的R处法向量m0，另外两个方向都在垂直于m0的切平面内，其中之一可由与关联位置R相邻接的某一顶点在切平面上的投影向量得到，另外一个可通过将前两个向量进行叉乘得到。
6.3变形区域模型泊松重建
本文骨架驱动网格模型变形针对的是三角网格模型的局部，当骨架驱动控制网格发生变形时，根据模型局部变形区域内各三角面片中心点在变形前后细分曲面关联位置处局部正交标架的改变确定旋转矩阵，根据关联位置变形前后附近三角面片周长的变化确定缩放矩阵。因为梯度场具有平移不变性，所以只需对三角面片进行旋转和缩放即可。
模型各三角面片独自进行局部变换后得到的变形后网格是零散，不连续的。通过计算变形后每个自由顶点的散度，将其带入泊松方程即可求解得到变形后的网格模型，约束顶点在求解过程中起边界条件的作用。
7变形实例
本文使用VC++6.0和OpenGL图形库对所提出的基于细分的骨架驱动变形方法进行了验证，分别给出了单峰骆驼的腿部、驼峰以及水壶壶嘴部位的骨架驱动变形过程。图10所示为骆驼腿部较大角度弯曲变形，可以看出变形后脚部特征得到较好保持；图11所示给出了骆驼驼峰的伸缩变形，骨架定义在驼峰位置，从图11（g与图11（h可以看出取得了较好的驼峰伸长效果；图12所示为水壶壶嘴部位的变形，变形后壶嘴呈现下弯形状，且特征较变形前保持良好。
需要说明的是这三个模型实例中生成的初始控制网格均不能完全包络模型变形区域，本文为保证模型变形质量，对控制网格变形端连同骨架线都进行了适当的外延，如图10（b、图11（b和图12（b所示；同时对控制网格变形端都进行了封闭。
8结语
基于细分的三维网格模型骨架驱动变形方法，通过操纵骨架实现变形，以细分曲面作为中间变形控制曲面，根据变形后模型梯度场重构网格模型，控制手段灵活，模型细节特征可以获得有效保持。
变形过程存在不足之处为：由于网格模型表面拓扑结构的复杂性，构建的控制网格某一部位可能不能很好地贴合模型表面形状，会影响到模型的变形质量，如何更好地构建控制网格是今后需要进一步研究的问题。