袁田琛 赵俭辉
摘要： 运动物体碰撞变形动画在电脑动画领域中有着重要作用。模拟物体的碰撞变形方法主要有基于几何模型法和基于物理模型法。随着多媒体和电脑动画技术的发展，对于物体变形动画模拟的真实性要求越来越高，采用物理模型法能得到更加逼真的模拟效果。针对运动物体的碰撞变形动画，采用模态分析法将复杂的非线性系统转换为能单独求解的线型方程组，从而提高了变形动画模拟的求解速度。结果表明，所述方法能获得变形动画模拟的实时性和视觉效果的逼真性。
关键词： 模态分析；电脑动画；碰撞变形；模态分解；碰撞检测
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2014）14-3388-03
Abstract： Moving object collision deformation animation plays very important role in the area of computer animation. Simulating collision deformation of objects is mainly based on geometric modeling approach and based on physical modeling approach. As the development of multimedia and computer animation technology， the authenticity of object deformation animation requires higher and higher， the physically based model can generate more realistic simulating effects. Aiming at the collision deformation animation of moving objects， using modal analysis method translates complicated nonlinear system into linear system of equations which can be solved separately to improve solution speed with regard to deformation animation simulation. The experimental results show that the presented method has real-time and realistic simulating effects in the deformation animation.
Key words： modal analysis； computer animation； collision deformation； modal decomposition； collision detection
电脑动画模拟是多媒体和虚拟现实技术中一个迅速发展的领域，它涉及物理学、数学、生物学、人工智能、多媒体技术等多门学科，广泛应用于专业动画制作、广告电影特技、教学演示、训练模拟、电子游戏等诸多领域。而变形动画模拟是视觉模拟系统中的一个关键的部件，动画变形模拟必须具备模拟的实时性和视觉效果的逼真性，如何构建出一种动画变形模拟系统能同时满足这两个基本要求仍然是当前活跃的研究应用领域之一[1]。目前已有一些模拟物体变形的模拟方法，如基于广义元球的约束变形动画[2]、有限差分法与欧拉-拉格朗日法结合模拟物体变形动画等[3]。近年来的趋势是基于物理的变形动画模拟方法占主导地位，其中模态分析法是一种重要的物理物理方法。
模态分析是研究结构动力特性一种近代方法，是系统辨别方法在工程振动领域中的应用。模态是机械结构的固有振动特性，每一个模态具有特定的固有频率、阻尼比和模态振型。这些模态参数可以由计算或试验分析获得，这种计算或试验分析过程称为模态分析。如果该分析过程是由有限元计算方法取得的，则称为计算模态分析；如果通过试验将采集的系统输入与输出信号经过参数识别获得模态参数，称为试验模态分析。1989年，Pentland等首次将模态分析作为一种针对近似变形动画的快速方法引入到图形社区[4]。2005年，Min Gyu Choi等在线性模态分析框架的基础上实现了一种实时大变形模拟[5]，2012年，ShaoJun Hu等采用模态分析实现了一种交互式树的模拟[6]等。
本文采用模态分析法对运动物体间的碰撞进行动力学分析并将其运用于变形动画过程的模拟。首先介绍模态分析模型，然后运用模态分析技术对物体变形动画过程进行模拟，给出相关的实验结果。
1 模态分析模型
真实物体受力变形模拟涉及到集成一系列的非线性的方程，通常采用数值计算方法求解这些复杂的方程。典型的数值计算方法分为直接法和迭代法。直接法中有高斯消去法、矩阵分解法；迭代法有Jacobi迭代法、超松弛迭代法和共轭梯度法等[7]。对于复杂的物体变形，采用这些数值计算方法往往计算量大，不能保证变形动画模拟的实时性。
模态分析是一种现实非线性描述的线性近似，它将复杂的非线性系统转换为可单独求解的线型方程组。丢掉一些不相关的或是可以忽略的系统参数，使得能直接对方程进行分析求解。其优点是极大地了减少计算量，在不影响精度的情况下能获得实时的变形动画处理效果。
1.1 模态分解
通常采用如下方程描述物理系统的模型：
[KU+CU′+MU″=F] （1）
其中[K]、[C]和[M]分别代表系统的刚度矩阵、阻尼矩阵和质量矩阵，[U]和[F]分别为广义位移向量和外力向量，[U′]和[U″]分别为[U]对时间的一阶导数和二阶导数。
这里，模态分解主要是指将（1）式进行对角化。我们使用瑞利阻尼，即矩阵[C]是[K]和[M]的线性组合，满足如下等式：
解耦后的系统方程不是对原线性系统的近似，而是能得到与原有线性系统相同的结果。虽然线性系统是对初始非线性系统的一个近似，但是通过求解方程（6）能在系统规定的时间内得出计算结果。得到模态坐标[z]后再根据（4）式得到物体各节点新的位置[U]并对物体重新渲染。
1.2碰撞检测
对于碰撞检测，该文采用基于轴向包围盒的碰撞检测算法[8]。采用自顶向下的方式建立包围盒层次树，首先建立物体的包围盒，作为包围盒的根节点，然后将模型细分为4份，建立每个部分的包围盒和相应节点，再递归的分裂每个节点对应的模型来建立层次包围盒树。碰撞检测过程就是两个物体间的包围盒树相交测试过程。从根节点开始，相互进行相交测试：对于包围盒树M和N，若树M的根节点的包围盒与树N内部节点的包围盒不相交，则停止向下遍历；若遍历到树N的叶子节点，则再反过来用该叶子节点遍历树M的内部节点；若两个包围盒树的叶子节点的包围盒相交，则再进行基元测试，当两个基元相交时表明两物体相交。
三维物体一般由三角形网格组成，因而基元碰撞检测一般是基于三角形的。三角形之间的相交测试包括“点-三角形面”、“边-边”、“边-三角形面”等测试，通过基元碰撞检测可获得更精确的碰撞信息。
1.3 动态模拟
这里，我们模拟球体在封闭的立方体网格或球体网格中因受到初始作用力而在网格内来回自由碰撞的过程。
在三维空间中，假设一平面[p]可表示为一个法向量[normal]（方向为坐标原点指向平面）和坐标原点到平面的距离[dir]；球体的包围盒树从根节点到叶子节点依次编号为0～n，每个节点的包围盒记为[Bi]。包围盒[Bi]由两个三维向量组成：[bmin]和[bmax]，其分量分别表示包围盒在坐标轴上投影的最大值和最小值。
由于立方体网格和球体网格都是由多个三角形构成的，每个三角形确定一个平面，那幺对于球体与立方体网格或者球体网格的碰撞，则是循环对网格的每个三角形面进行上述碰撞检测过程。
2 实验结果
表1罗列了本文实验所采用的球体对象模型和另外两种较复杂的对象模型的变形动画模拟结果，从结果数据可以看出，即使对于像大脑等较复杂的对象模型，采用模态分析法也能获得较快的和逼真的变形动画模拟效果。
3 结束语
在基于物理的变形动画模拟中，模态分析方法是其中的一种重要数学物理方法。在小形变模拟中，采用模态分析法将非线性系统进行线性逼近，以保持在较高真实性的前提下获得较快的模拟效果。实验结果表明，在小形变动画过程的碰撞模拟中，即使对于一些复杂的物体，采用本文所述模态分析法也能获得很好的变形动画模拟效果。
参考文献：
[1] 袁志勇，尹乾，冯仕堃，等. 基于改进质点-弹簧模型的图像变形仿真方法[J]. 华中科技大学学报自然科学版， 2009， 37（1）： 35-37.
[2] 金小刚，彭群生. 基于广义元球的一般约束变形[J]. 软件学报， 1998， 9（9）： 677-682.
[3] David Baraff， Andrew Witkin. Large Steps in Cloth Simulation[C]. Proceedings of SIGGRAPH 98， 1998： 43-54.
[4] Alex Pentland， John Williams. Good Vibrations： Modal Dynamics for Graphics and Animation[C]. Proceedings of SIGGRAPH 89， 1989： 215–222.
[5] Min Gyu Choi， Hyeong-Seok Ko. Modal Warping： Real-time Simulation of Large Rotational Deformation and Manipulation[J]. IEEE Transactions on Visualization and Computer Graphics， 2005， 11（1）： 91-101.
[6] ShaoJun Hu， Norishige Chiba， Dongjian He. Realistic Animation of Interactive Trees[J]. The Visual Computer， 2012， 28（6-8）： 859-868.
[7] 吕同富，康兆敏，方秀男. 数值计算方法[M]. 北京：清华大学出版社， 2008： 47-99.
[8] 唐勇，冯立颖，吕梦雅. 基于轴向包围盒碰撞检测算法的改进[J].系统仿真学报，2009， 21（1）： 157-160.
这里，模态分解主要是指将（1）式进行对角化。我们使用瑞利阻尼，即矩阵[C]是[K]和[M]的线性组合，满足如下等式：
解耦后的系统方程不是对原线性系统的近似，而是能得到与原有线性系统相同的结果。虽然线性系统是对初始非线性系统的一个近似，但是通过求解方程（6）能在系统规定的时间内得出计算结果。得到模态坐标[z]后再根据（4）式得到物体各节点新的位置[U]并对物体重新渲染。
1.2碰撞检测
对于碰撞检测，该文采用基于轴向包围盒的碰撞检测算法[8]。采用自顶向下的方式建立包围盒层次树，首先建立物体的包围盒，作为包围盒的根节点，然后将模型细分为4份，建立每个部分的包围盒和相应节点，再递归的分裂每个节点对应的模型来建立层次包围盒树。碰撞检测过程就是两个物体间的包围盒树相交测试过程。从根节点开始，相互进行相交测试：对于包围盒树M和N，若树M的根节点的包围盒与树N内部节点的包围盒不相交，则停止向下遍历；若遍历到树N的叶子节点，则再反过来用该叶子节点遍历树M的内部节点；若两个包围盒树的叶子节点的包围盒相交，则再进行基元测试，当两个基元相交时表明两物体相交。
三维物体一般由三角形网格组成，因而基元碰撞检测一般是基于三角形的。三角形之间的相交测试包括“点-三角形面”、“边-边”、“边-三角形面”等测试，通过基元碰撞检测可获得更精确的碰撞信息。
1.3 动态模拟
这里，我们模拟球体在封闭的立方体网格或球体网格中因受到初始作用力而在网格内来回自由碰撞的过程。
在三维空间中，假设一平面[p]可表示为一个法向量[normal]（方向为坐标原点指向平面）和坐标原点到平面的距离[dir]；球体的包围盒树从根节点到叶子节点依次编号为0～n，每个节点的包围盒记为[Bi]。包围盒[Bi]由两个三维向量组成：[bmin]和[bmax]，其分量分别表示包围盒在坐标轴上投影的最大值和最小值。
由于立方体网格和球体网格都是由多个三角形构成的，每个三角形确定一个平面，那幺对于球体与立方体网格或者球体网格的碰撞，则是循环对网格的每个三角形面进行上述碰撞检测过程。
2 实验结果
表1罗列了本文实验所采用的球体对象模型和另外两种较复杂的对象模型的变形动画模拟结果，从结果数据可以看出，即使对于像大脑等较复杂的对象模型，采用模态分析法也能获得较快的和逼真的变形动画模拟效果。
3 结束语
在基于物理的变形动画模拟中，模态分析方法是其中的一种重要数学物理方法。在小形变模拟中，采用模态分析法将非线性系统进行线性逼近，以保持在较高真实性的前提下获得较快的模拟效果。实验结果表明，在小形变动画过程的碰撞模拟中，即使对于一些复杂的物体，采用本文所述模态分析法也能获得很好的变形动画模拟效果。
参考文献：
[1] 袁志勇，尹乾，冯仕堃，等. 基于改进质点-弹簧模型的图像变形仿真方法[J]. 华中科技大学学报自然科学版， 2009， 37（1）： 35-37.
[2] 金小刚，彭群生. 基于广义元球的一般约束变形[J]. 软件学报， 1998， 9（9）： 677-682.
[3] David Baraff， Andrew Witkin. Large Steps in Cloth Simulation[C]. Proceedings of SIGGRAPH 98， 1998： 43-54.
[4] Alex Pentland， John Williams. Good Vibrations： Modal Dynamics for Graphics and Animation[C]. Proceedings of SIGGRAPH 89， 1989： 215–222.
[5] Min Gyu Choi， Hyeong-Seok Ko. Modal Warping： Real-time Simulation of Large Rotational Deformation and Manipulation[J]. IEEE Transactions on Visualization and Computer Graphics， 2005， 11（1）： 91-101.
[6] ShaoJun Hu， Norishige Chiba， Dongjian He. Realistic Animation of Interactive Trees[J]. The Visual Computer， 2012， 28（6-8）： 859-868.
[7] 吕同富，康兆敏，方秀男. 数值计算方法[M]. 北京：清华大学出版社， 2008： 47-99.
[8] 唐勇，冯立颖，吕梦雅. 基于轴向包围盒碰撞检测算法的改进[J].系统仿真学报，2009， 21（1）： 157-160.
这里，模态分解主要是指将（1）式进行对角化。我们使用瑞利阻尼，即矩阵[C]是[K]和[M]的线性组合，满足如下等式：
解耦后的系统方程不是对原线性系统的近似，而是能得到与原有线性系统相同的结果。虽然线性系统是对初始非线性系统的一个近似，但是通过求解方程（6）能在系统规定的时间内得出计算结果。得到模态坐标[z]后再根据（4）式得到物体各节点新的位置[U]并对物体重新渲染。
1.2碰撞检测
对于碰撞检测，该文采用基于轴向包围盒的碰撞检测算法[8]。采用自顶向下的方式建立包围盒层次树，首先建立物体的包围盒，作为包围盒的根节点，然后将模型细分为4份，建立每个部分的包围盒和相应节点，再递归的分裂每个节点对应的模型来建立层次包围盒树。碰撞检测过程就是两个物体间的包围盒树相交测试过程。从根节点开始，相互进行相交测试：对于包围盒树M和N，若树M的根节点的包围盒与树N内部节点的包围盒不相交，则停止向下遍历；若遍历到树N的叶子节点，则再反过来用该叶子节点遍历树M的内部节点；若两个包围盒树的叶子节点的包围盒相交，则再进行基元测试，当两个基元相交时表明两物体相交。
三维物体一般由三角形网格组成，因而基元碰撞检测一般是基于三角形的。三角形之间的相交测试包括“点-三角形面”、“边-边”、“边-三角形面”等测试，通过基元碰撞检测可获得更精确的碰撞信息。
1.3 动态模拟
这里，我们模拟球体在封闭的立方体网格或球体网格中因受到初始作用力而在网格内来回自由碰撞的过程。
在三维空间中，假设一平面[p]可表示为一个法向量[normal]（方向为坐标原点指向平面）和坐标原点到平面的距离[dir]；球体的包围盒树从根节点到叶子节点依次编号为0～n，每个节点的包围盒记为[Bi]。包围盒[Bi]由两个三维向量组成：[bmin]和[bmax]，其分量分别表示包围盒在坐标轴上投影的最大值和最小值。
由于立方体网格和球体网格都是由多个三角形构成的，每个三角形确定一个平面，那幺对于球体与立方体网格或者球体网格的碰撞，则是循环对网格的每个三角形面进行上述碰撞检测过程。
2 实验结果
表1罗列了本文实验所采用的球体对象模型和另外两种较复杂的对象模型的变形动画模拟结果，从结果数据可以看出，即使对于像大脑等较复杂的对象模型，采用模态分析法也能获得较快的和逼真的变形动画模拟效果。
3 结束语
在基于物理的变形动画模拟中，模态分析方法是其中的一种重要数学物理方法。在小形变模拟中，采用模态分析法将非线性系统进行线性逼近，以保持在较高真实性的前提下获得较快的模拟效果。实验结果表明，在小形变动画过程的碰撞模拟中，即使对于一些复杂的物体，采用本文所述模态分析法也能获得很好的变形动画模拟效果。
参考文献：
[1] 袁志勇，尹乾，冯仕堃，等. 基于改进质点-弹簧模型的图像变形仿真方法[J]. 华中科技大学学报自然科学版， 2009， 37（1）： 35-37.
[2] 金小刚，彭群生. 基于广义元球的一般约束变形[J]. 软件学报， 1998， 9（9）： 677-682.
[3] David Baraff， Andrew Witkin. Large Steps in Cloth Simulation[C]. Proceedings of SIGGRAPH 98， 1998： 43-54.
[4] Alex Pentland， John Williams. Good Vibrations： Modal Dynamics for Graphics and Animation[C]. Proceedings of SIGGRAPH 89， 1989： 215–222.
[5] Min Gyu Choi， Hyeong-Seok Ko. Modal Warping： Real-time Simulation of Large Rotational Deformation and Manipulation[J]. IEEE Transactions on Visualization and Computer Graphics， 2005， 11（1）： 91-101.
[6] ShaoJun Hu， Norishige Chiba， Dongjian He. Realistic Animation of Interactive Trees[J]. The Visual Computer， 2012， 28（6-8）： 859-868.
[7] 吕同富，康兆敏，方秀男. 数值计算方法[M]. 北京：清华大学出版社， 2008： 47-99.
[8] 唐勇，冯立颖，吕梦雅. 基于轴向包围盒碰撞检测算法的改进[J].系统仿真学报，2009， 21（1）： 157-160.
