CN104143204A - 考虑拓扑结构的移动最小二乘二维角色变形方法 - Google Patents

Abstract

本发明公开了一种考虑拓扑结构的移动最小二乘二维角色变形方法，本发明首先基于用户的交互约束配置，在角色形状上最小化拉普拉斯能量函数，得到调和权值w_ij；然后，以调和权值作为变形约束权值，对卡通角色进行移动最小二乘变形。本发明具有不仅能够产生视觉真实的变形结果，并且可以有效避免传统移动最小二乘变形方法中可能产生的变形扭曲，增强了移动最小二乘变形方法的实用性特点。

Description

考虑拓扑结构的移动最小二乘二维角色变形方法

技术领域

本发明涉及动画技术领域，特别是涉及一种不仅能够产生视觉真实的变形结果，并且可以有效避免传统移动最小二乘变形方法中可能产生的变形扭曲，增强了移动最小二乘变形方法的实用性的考虑拓扑结构的移动最小二乘二维角色变形方法。

背景技术

随着数字媒体技术的发展，产生了诸多的数字娱乐应用，如电影、网络、游戏等。角色动画是这些应用中的一个重要内容。因此，为了进一步推动并普及这些应用，需要设计并提供相应的工具，让普通用户能够直观容易地制作角色动画。

二维形状变形是计算机动画领域中的一项重要技术。给定一个二维角色，该技术通过改变角色形状可以为角色创造出丰富的姿势效果，进而制作出相应的角色动画序列。在计算机二维商业动画软件中，自由变形方法(free-form deformation，FFD)是一种常见的形状变形工具。在FFD中，待变形形状首先被嵌入到一个简单的中间包围盒中，然后用户通过编辑中间包围盒来对嵌入形状实施变形。但是，构建形状的包围盒是一件非常繁琐费时的工作。最近，人们提出了许多基于能量优化的保刚性形状变形方法。这些方法允许用户通过点、线段等各类交互方式来对形状进行变形。但是，上述方法通常需要求解一个非线性优化问题，会产生较大的时间开销，而在一定程度上限制它们的实时交互应用。

针对上述问题，研究人员提出了一种移动最小二乘图像变形方法(Moving Least Squares，MLS)。该方法允许用户通过点和线来操作二维角色。与基于能量优化的保刚性变形方法类似，该方法也考虑了形状的刚性，通过最小化形状的变形扭曲，产生了视觉真实的变形结果。但是，与基于能量优化的变形方法需要全局求解一个非线性优化问题不同，该方法为形状内部的各个顶点局部求解一个极小规模的线性优化问题。此外，该方法还为每个局部线性优化问题提供了解析解，最终该方法对包含上万顶点的形状也能够进行实时变形。但是，该方法的一个重要缺陷在于它采用欧氏距离作为变形约束权值，而没有考虑角色形状的拓扑结构，导致可能产生扭曲的变形结果(如图1所示)。

因此，为了使移动最小二乘图像变形方法更加适合实际应用，需要为它的上述缺点提供一个完美的解决方案。

中国专利授权公开号：CN101276474，授权公开日2008年10月1日，公开了一种基于局部坐标的线性约束二维角色变形方法，该方法包含以下步骤：对输入的二维二维角色进行四边域的网格化操作，并采用局部坐标来描述网格的几何特征；对顶点之间的相对位置进行仿射约束；对相邻边之间的夹角进行角度约束；调节α和β的比值平衡两种约束条件，并求解线性方程组；生成二维动画形象的多种复杂变形效果。该发明的不足之处是，会产生较大的时间开销。

发明内容

本发明的发明目的是为了克服现有技术中的变形方法会产生较大的时间开销及可能产生扭曲的变形结果的不足，提供了一种不仅能够产生视觉真实的变形结果，并且可以有效避免传统移动最小二乘变形方法中可能产生的变形扭曲，增强了移动最小二乘变形方法的实用性的考虑拓扑结构的移动最小二乘二维角色变形方法。

为了实现上述目的，本发明采用以下技术方案：

一种考虑拓扑结构的移动最小二乘二维角色变形方法，包括如下步骤：

(1-1)用三角形网格来表示一个二维角色(4)：

计算机显示屏中显示一个二维角色，用户用鼠标沿二维角色边缘上画出用于表示该二维角色边界轮廓的多边形；

以多边形作为边界约束，计算机利用标准Delaunay三角化方法计算出用于填充多边形内部的三角形网格，三角形网格包括网格顶点以及顶点之间的连接边，网格顶点的连接关系构成所述二维角色的拓扑结构；

(1-2)在角色上放置若干个控制点(1)，计算控制点相对三角形网格顶点的MLS变形影响权值w_ij，拖动控制点(1)，计算任意网格顶点j的最优变形位置地址，实现三角形网格的变形：

(1-2-1)用户通过鼠标在角色上设置n个控制点并拖动其中一个或多个控制点移动；

(1-2-2)基于三角形网格的拓扑结构，求解拉普拉斯方程位置地址，计算出考虑拓扑结构的控制点i相对三角网格中的任意一个顶点j的变形影响权值w_ij，为散度运算符；

(1-2-3)计算机利用公式计算顶点j的最优变形刚性变换M，并得到 $M=\frac{1}{{\mathrm{\μ}}_r}\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\left[\begin{array}{c}{\widehat{\stackrel{\‾}{p}}}_i\\ -{{\widehat{\stackrel{\‾}{p}}}_i}^{\⫬}\end{array}\right]\left[\begin{array}{cc}{p_i}^T& -{\left({p_i}^{\⫬}\right)}^T\end{array}\right],$ 其中， $\left[\begin{array}{c}{\widehat{\stackrel{\‾}{p}}}_i\\ -{{\widehat{\stackrel{\‾}{p}}}_i}^{\⫬}\end{array}\right]$ 为二维列向量， ${\left[\begin{array}{cc}x& y\end{array}\right]}^{\⫬}=\left[\begin{array}{cc}-y& x\end{array}\right]$ 为二维行向量。

其中，为设定的使 ${\left[\begin{array}{cc}x& y\end{array}\right]}^{\⫬}=\left[\begin{array}{cc}-y& x\end{array}\right]$ 的二维向量运算符， ${\mathrm{\μ}}_r=\sqrt{{\left(\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{\hat{p}}_i{{\widehat{\stackrel{\‾}{p}}}_i}^T\right)}^2+{\left(\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{\hat{p}}_i{\left({{\widehat{\stackrel{\‾}{p}}}_i}^{\⫬}\right)}^T\right)}^2};$ 其中，T为矩阵转置运算符，||·||为范数运算符；

${\widehat{\stackrel{\‾}{p}}}_i={\stackrel{\‾}{p}}_i-{\stackrel{\‾}{p}}_{*},{\hat{p}}_i=p_i-p_{*},{\stackrel{\‾}{p}}_{*}=\frac{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{\stackrel{\‾}{p}}_i}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}},$ $p_{*}=\frac{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{p}_i}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}},$ 为控制点i的初始位置地址，p_i为控制点i被移动之后的位置地址；

(1-2-4)利用公式计算任意网格顶点j的最优变形位置地址v_j；其中，为顶点j的初始位置地址；当计算得到三角形网格中每个顶点的最优变形位置地址后，计算机利用线性纹理映射法在显示屏中画出变形后的二维角色。

本发明首先基于用户的交互约束配置，在角色形状上最小化拉普拉斯能量函数，得到调和权值w_ij；然后，以调和权值作为变形约束权值，对卡通角色进行移动最小二乘变形。由于调和权值考虑了形状的拓扑结构并且以一种局部扩散的方式传播了用户交互约束的变形影响，最终有效避免了可能的变形扭曲。

本发明有效解决了二维数字角色的快速变形问题，主要用于计算机二维角色动画制作。针对特定的便携式设备，例如平板电脑，本发明也产生了一项新型的娱乐应用：通过直观的交互显示屏，用户可以在显示屏上方便容易地操作一个二维角色，并制作出简单的动画。

本发明是的用户可以通过点来操作二维角色，相比于传统的移动最小二乘变形方法，新方法引入了一组考虑拓扑结构的MLS变形影响权值，以作为变形的约束权值，通过局部扩散的方式传播了用户交互约束相对角色各处的变形影响。因此，本发明具有不仅能够产生视觉真实的变形结果，并且可以有效避免传统移动最小二乘变形方法中可能产生的变形扭曲，增强了移动最小二乘变形方法的实用性的特点。

作为优选，利用如下步骤代替步骤(1-2-1)：

用户通过鼠标在三角形网格图上设置若干条控制线段(2)，计算机计算控制线段和三角形网格之间的交点(3)，将交点和各条线段的端点作为控制点，控制点为n个；

用户通过鼠标拖动其中一个或多个控制点移动。

控制线段的设置，使本发明的用户可以通过线来操作二维角色的变形。

作为优选，利用下述步骤代替步骤(1-2-2)：

基于三角形网格的拓扑结构，求解拉普拉斯方程Lw_ij＝0，计算出考虑拓扑结构的控制点i相对三角网格中的任意一个顶点j的变形影响权值w_ij，

其中，矩阵L为离散的三角形网格上的Laplace-Beltrami算子矩阵。

作为优选，所述二维角色为位图图片或者二维矢量图片。

作为优选，控制点为8至100个。

作为优选，三角形网格包括若干个相互连接的三角形。

因此，本发明具有如下有益效果：

(1)不仅能够产生视觉真实的变形结果，并且可以有效避免传统移动最小二乘变形方法中可能产生的变形扭曲；

(2)减少了变形时间开销，实时交互性好；

(3)增强了移动最小二乘变形方法的实用性。

附图说明

图1是传统的移动最小二乘变形方法的一种变形结果(左图：原始形状；右图：变形结果)；

图2是本发明的考虑拓扑结构的移动最小二乘变形方法的一种变形结果(基于控制点的操作)；

图3是本发明的考虑拓扑结构的移动最小二乘变形方法的一种变形结果(基于控制线段的操作)；

图4是本发明的实施例1的一种流程图。

图中：控制点1、控制线段2、交点3、二维角色4。

具体实施方式

下面结合附图和具体实施方式对本发明做进一步的描述。

实施例1

如图4所示的实施例是一种考虑拓扑结构的移动最小二乘二维角色变形方法，包括如下步骤：

步骤100，如图2所示，用三角形网格图代替计算机显示屏显示一个二维角色4，二维角色为二维矢量图片；

计算机显示屏中显示一个二维角色，用户用鼠标沿二维角色边缘上画出用于表示该二维角色边界轮廓的多边形；

以多边形作为边界约束，计算机利用标准Delaunay三角化方法计算出用于填充多边形内部的三角形网格，三角形网格包括网格顶点以及顶点之间的连接边，网格顶点的连接关系构成所述二维角色的拓扑结构；

步骤200，在角色上放置控制点1，计算控制点相对三角形网格顶点的MLS变形影响权值w_ij，拖动控制点1，计算任意网格顶点j的最优变形位置地址，实现三角形网格的变形：

步骤210，用户通过鼠标在三角形网格图上设置n＝8个控制点并拖动其中一个或多个控制点移动；

步骤220，基于三角形网格的拓扑结构，求解拉普拉斯方程计算出考虑拓扑结构的控制点i相对三角网格中的任意一个顶点j的变形影响权值w_ij，为散度运算符；

步骤230，计算机利用公式计算顶点j的最优变形刚性变换M，并得到 $M=\frac{1}{{\mathrm{\μ}}_r}\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\left[\begin{array}{c}{\widehat{\stackrel{\‾}{p}}}_i\\ -{{\widehat{\stackrel{\‾}{p}}}_i}^{\⫬}\end{array}\right]\left[\begin{array}{cc}{p_i}^T& -{\left({p_i}^{\⫬}\right)}^T\end{array}\right],$

${\mathrm{\μ}}_r=\sqrt{{\left(\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{\hat{p}}_i{{\widehat{\stackrel{\‾}{p}}}_i}^T\right)}^2+{\left(\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{\hat{p}}_i{\left({{\widehat{\stackrel{\‾}{p}}}_i}^{\⫬}\right)}^T\right)}^2};$ 其中，T为矩阵转置运算符，|| ||为范数运算符；

${\widehat{\stackrel{\‾}{p}}}_i={\stackrel{\‾}{p}}_i-{\stackrel{\‾}{p}}_{*},{\hat{p}}_i=p_i-p_{*},{\stackrel{\‾}{p}}_{*}=\frac{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{\stackrel{\‾}{p}}_i}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}},$ $p_{*}=\frac{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{p}_i}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}},$ 为控制点i的初始位置地址，p_i为控制点i被移动之后的位置地址；

步骤240，利用公式计算任意顶点j的最优变形位置地址v_j；其中，为顶点j的初始位置地址；当计算得到三角形网格中每个顶点的最优变形位置地址后，计算机利用线性纹理映射法在显示屏中画出变形后的二维角色。

实施例2

实施例2中，利用如下步骤代替实施例1中的步骤210：

如图3所示，用户通过鼠标在三角形网格图上设置7条控制线段3，计算机计算控制线段和三角形网格图之间的交点4，将交点和各条线段的端点作为控制点，控制点为10个，n＝10；

用户通过鼠标拖动其中一个或多个控制点移动。

利用下述步骤代替实施例1中的步骤200：

基于三角形网格的拓扑结构，求解拉普拉斯方程Lw_ij＝0，计算出考虑拓扑结构的控制点i相对三角网格中的任意一个顶点j的变形影响权值w_ij，

其中，矩阵L为离散的三角形网格上的Laplace-Beltrami算子矩阵。

实施例2中的其它步骤部分与实施例1中相同。

应理解，本实施例仅用于说明本发明而不用于限制本发明的范围。此外应理解，在阅读了本发明讲授的内容之后，本领域技术人员可以对本发明作各种改动或修改，这些等价形式同样落于本申请所附权利要求书所限定的范围。

Claims (6)

1.一种考虑拓扑结构的移动最小二乘二维角色变形方法，其特征是，包括如下步骤：

(1-1)用三角形网格来表示一个二维角色(4)：

计算机显示屏中显示一个二维角色，用户用鼠标沿二维角色边缘上画出用于表示该二维角色边界轮廓的多边形；

以多边形作为边界约束，计算机利用标准Delaunay三角化方法计算出用于填充多边形内部的三角形网格，三角形网格包括网格顶点以及顶点之间的连接边，网格顶点的连接关系构成所述二维角色的拓扑结构；

(1-2)在角色上放置若干个控制点(1)，计算控制点相对三角形网格顶点的MLS变形影响权值w_ij，拖动控制点(1)，计算任意网格顶点j的最优变形位置地址，实现三角形网格变形：

(1-2-1)用户通过鼠标在角色上设置n个控制点并拖动其中一个或多个控制点移动；

(1-2-2)基于三角形网格的拓扑结构，求解拉普拉斯方程计算出考虑拓扑结构的控制点i相对三角网格中的任意一个顶点j的变形影响权值w_ij，为散度运算符；

(1-2-3)计算机利用公式计算顶点j的最优变形刚性变换M，并得到 $M=\frac{1}{{\mathrm{\μ}}_r}\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\left[\begin{array}{c}{\widehat{\stackrel{\‾}{p}}}_i\\ -{{\widehat{\stackrel{\‾}{p}}}_i}^{\⫬}\end{array}\right]\left[\begin{array}{cc}{p_i}^T& -{\left({p_i}^{\⫬}\right)}^T\end{array}\right],$

其中，为设定的使的二维向量运算符，

${\mathrm{\μ}}_r=\sqrt{{\left(\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{\hat{p}}_i{{\widehat{\stackrel{\‾}{p}}}_i}^T\right)}^2+{\left(\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{\hat{p}}_i{\left({{\widehat{\stackrel{\‾}{p}}}_i}^{\⫬}\right)}^T\right)}^2};$ 其中，T为矩阵转置运算符，||·||为范数运算符；

${\widehat{\stackrel{\‾}{p}}}_i={\stackrel{\‾}{p}}_i-{\stackrel{\‾}{p}}_{*},{\hat{p}}_i=p_i-p_{*},{\stackrel{\‾}{p}}_{*}=\frac{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{\stackrel{\‾}{p}}_i}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}},$ $p_{*}=\frac{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}{p}_i}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{w}_{\mathrm{ij}}},$ 为控制点i的初始位置地址，p_i为控制点i被移动之后的位置地址；

(1-2-4)利用公式计算任意网格顶点j的最优变形位置地址v_j；其中，为顶点j的初始位置地址；当计算得到三角形网格中每个顶点的最优变形位置地址后，计算机利用线性纹理映射法在显示屏中画出变形后的二维角色。

2.根据权利要求1所述的考虑拓扑结构的移动最小二乘二维角色变形方法，其特征是，利用如下步骤代替步骤(1-2-1)：

用户通过鼠标在三角形网格图上设置若干条控制线段(2)，计算机计算控制线段和三角形网格之间的交点(3)，将交点和各条线段的端点作为控制点，控制点为n个；

用户通过鼠标拖动其中一个或多个控制点移动。

3.根据权利要求1所述的考虑拓扑结构的移动最小二乘二维角色变形方法，其特征是，利用下述步骤代替步骤(1-2-2)：

基于三角形网格的拓扑结构，求解拉普拉斯方程Lw_ij＝0，计算出考虑拓扑结构的控制点i相对三角网格中的任意一个顶点j的变形影响权值w_ij，

其中，矩阵L为离散的三角形网格上的Laplace-Beltrami算子矩阵。

4.根据权利要求1所述的考虑拓扑结构的移动最小二乘二维角色变形方法，其特征是，所述二维角色为位图图片或者二维矢量图片。

5.根据权利要求1所述的考虑拓扑结构的移动最小二乘二维角色变形方法，其特征是，控制点为8至100个。

6.根据权利要求1或2或3或4或5所述的考虑拓扑结构的移动最小二乘二维角色变形方法，其特征是，三角形网格包括若干个相互连接的三角形。