博客园的Markdown支持太差，想要看完美排版的请点击这个链接.
Introduction
读这篇论文的机缘巧合很有趣，我在Unity3D的Asset Store上看到一个叫做Dyanmic Bones的项目，使用物理动画真实地模拟了角色的躯干动作，20$还是个不小的数目，就发了封邮件给项目作者Will Hong，作者很热心地回答该项目并没有使用Unity3D的物理引擎，而是根据Advanced Character Physics这篇论文的思想复现而成的。本着对当今工业界黑科技的膜拜之情，我读了一下这篇文章。
这篇论文并不是一篇学术论文，应该可以说是一篇关于工业界实现技巧的Gems类专著，论文中的技巧被用于实现Hitman: Codename 47这个游戏的物理交互系统（包括刚体和软体，甚至是连接体），读完全文的直接感受就是：艹，为了实现起来简单并达到实时交互级，原来还可以这么搞。
Verlet integration
一般做物理模拟是经常使用到如下的两个运动学公式来进行运动信息的更新：
\[x^\prime=x+v\cdot{\bigtriangleup{t}}\]\[v^\prime=v+a\cdot{\bigtriangleup{t}}\]
论文指出可以使用一种排除速度因素的模式来做运动信息更新：
\[x^\prime=2x-x^\star+a\cdot{t^2}\]\[x^\star=x\]
其中\(x^\star\)是上一个时间点的位置信息，\(x\)是当前时间点的位置信息，每隔固定的时间步对运动信息进行更新。
这是一种叫做Verlet integration的方案，对应上面的Euler integration。公式的正确性由\(2x-x^\star=x+(x-x^\star)\)及\(x-x^\star\)作为当前的速度估计值易得。
Collision and contact handling by projection
论文中为了处理避免Penalty method带来的stiffness问题，使用了一种看起来非常简陋的方法来处理碰撞。
如图所示为一个Box中的一些粒子，可以认为Box的四壁都是无弹性的刚体，粒子碰撞到墙壁后立刻失去墙壁法线方向上的距离。具体的理解可以看下面的代码：
// Implements particles in a box
void ParticleSystem::SatisfyConstraints()
{for (int i = 0; i < NUM_PARTICLES; ++i){ // For all particlesVector3& x = m_x[i];x = vmin(vmax(x, Vector3(0,0,0)),Vector3(1000,1000,1000));}
}这实际上是给粒子的位置加上了一个约束$x_i\ge0,x_i\le1000 \(，同样的思想可以用在处理一根刚性的连杆将两个粒子相连的情况,即给两个粒子加上一个\)\lvert{x_2-x_1}\rvert=100$的位置约束，具体如下：
// Pseudo-code to satisfy (C2)
delta = x2-x1;
deltalength = sqrt(delta*delta);
diff = (deltalength-restlength) / deltalength;
x1 += delta*0.5*diff;
x2 -= delta*0.5*diff;Relaxation Method for solving several concurrent constraints
对于连杆碰撞问题中可能会出现两个约束互相冲突的情况，作者使用了一种非常简单的思想，在一个时间步对这两个约束条件串行地进行多次迭代：
// Implements simulation of a stick in a box
void ParticleSystem::SatisfyConstraints()
{for (int j = 0; j < NUM_ITERATIONS; ++j){// First satisfy (C1)for (int i = 0; i < NUM_PARTICLES; ++i) { // For all particlesVector3& x = m_x[i];x = vmin(vmax(x, Vector3(0,0,0)),Vector3(1000,1000,1000));}// Then satisfy (C2)Vector3& x1 = m_x[0];Vector3& x2 = m_x[1];Vector3 delta = x2-x1;float deltalength = sqrt(delta*delta);float diff = (deltalength-restlength) / deltalength;x1 += delta*0.5*diff;x2 -= delta*0.5*diff;}
}这种处理方法就是松弛法（或者叫做雅可比或高斯塞德尔迭代法），作者声称对于一般的约束需要的松弛次数非常少，在实时游戏环境中甚至可以一次迭代就达到理想的效果。
使用这两个约束就可以对布料等软体建模了，在实现中认为布料的网格就是连杆，首先用Verlet迭代更新顶点位置，再利用松弛法对每根连杆的约束进行满足。
对于刚体，也可以使用粒子-连杆法进行建模，如下图：
可认为正方体刚体中嵌套了一个用粒子-连杆建模的四面体。这样做的好处是更新刚体的信息时不用考虑整体的复杂动力学信息（转动惯量等），直接通过更新粒子的运动让刚体随动即可，处理起来很简单并且可信度足够，适合于实时游戏。
Miscellaneous
论文中还讲到了一些有价值的gems，如上图中墙壁的几何特征并不是直线时的碰撞处理，以及使用粒子-连杆法对骨骼连接体进行建模（构建新的约束而不违反人体运动的自由度规律，如\((x_2-x_0)\cdot{(x_1-x_0)}<\alpha\)表示关节角极限等），想要详细了解可以从本文开头的链接处获取论文自行研究。
虽然本文的方法比较简陋，而且随着硬件的发展计算机已经可以更快速的处理更复杂的物理模拟，但本文中提出的方法应用于简单的手机2D游戏是非常合适的，有较强的借鉴意义。
Rudy Snow
2014.05.10
于斛兵塘
