P22

Projective Dynamics

原理

Instead of blending projections in a Jacobi or Gauss-Seidel fashion as in PBD, projective dynamics uses projection to define a quadratic energy.

✅ PBD方法直接拿约束来修复顶点位置，没有物理含义。而本页方法把projection方法跟物拟模拟结合起来，主要体现在用约束来做什么。

能量和力

$E(\mathbf{x} ) = {\textstyle \sum_{e = (i,j)}}\frac{1}{2} ||(\mathbf{x} _i−\mathbf{x} _j)−(\mathbf{x} _{e,i}^{\mathrm{new} }−\mathbf{x} _{e,j}^{\mathrm{new} })||^2$

{$\mathbf{x} _{e,i}^{\mathrm{new} },\mathbf{x} _{e,j}^{\mathrm{new} }$} = $\mathrm{Projection} _e(\mathbf{x}_i,\mathbf{x}_j)$ for every edge $e$

✅ 本文基于约束定义能量。{$\mathbf{x} _{e,i}^{\mathrm{new} },\mathbf{x} _{e,j}^{\mathrm{new} }$}为期望的顶点位置。不直接把顶点从当前位置移到期望位置。而是把当前位置和期望位置的距离转化为能量，通过能量推动顶点从当前位置移到目标位置。

$$E(\mathbf{x})=\sum _{e=(i,j)}\frac{k}{2}(||\mathbf{x}_i-\mathbf{x}_j||-L_e)^2$$

$$\mathbf{f} _i=−\nabla_iE(\mathbf{x} )=−{\textstyle \sum _{e:i\in e}}(\mathbf{x} _i−\mathbf{x} _j)−(\mathbf{x} _{e,i}^{\mathrm{new}} −\mathbf{x} _{e,j}^{\mathrm{new} })$$

✅ 基于 $E(\mathbf{x})、\mathbf{x}_i^{\mathrm{new} } 、\mathbf{x}_j^{\mathrm{new} }$ 计算力，此时假设$\mathbf{x}_i^{\mathrm{new} }$和 $\mathbf{x}_j^{\mathrm{new} }$都是定值，$\mathbf{x}_i$和 $\mathbf{x}_j$是变量。
✅ 本文基于约束定义能量和力，得到的结果与基于弹簧能量计算的能量和力相同。
✅ 既然 $E$ 和 $F$ 是一样的，何必多此一举? 答：H不同。

P23

Hessian 矩阵

Instead of blending projections in a Jacobi or Gauss-Seidel fashion as in PBD, projective dynamics uses projection to define a quadratic energy.

✅ 同一个顶点在三个不同边上的投影是不同的。
✅ 可以直接根据Mesh的拓扑关系构造H矩阵。
✅ 为什么能简化$\mathbf{H}$的计算？答：在计算某一个端点时，假设另一个端点不动（常量），那么能量就是只关于这个端点的二次函数

P24

Shape Matching

Shape matching is also projective dynamics, if we view rotation as projection:

|

The 2D Space	The 3D Space

Assuming that $\mathbf{{\color{Orange} R} }$ is constant,
$$\begin{matrix} \mathbf{f} _0=−\nabla_0E(\mathbf{x} )\\ \mathbf{f} _1=−\nabla_1E(\mathbf{x} ) \\ \mathbf{f} _2=−\nabla_2E(\mathbf{x} )\\ \mathbf{H} =\frac{∂E^2(\mathbf{x} )}{∂x^2} \quad \text{is a constant !} \end{matrix}$$

P25

Simulation by Projective Dynamics

• According to implicit integration and Newton’s method, a projective dynamics simulator looks as follows, with matrix $\mathbf{A} =\frac{1}{∆t^2}\mathbf{M+}\mathbf{H}$ being constant.

• We can use a direct solver with only one factorization of A.

✅ 解线性系统的主要耗时在LU分解，而这个算法中$\mathrm{H}$是常数矩阵，只需要做一次LU分解，简化了对$\mathrm{H}$分解的计算量。

Initialize $\mathbf{x} ^{(0)}$, often as$\mathbf{x} ^{[0]}$or $\mathbf{x} ^{[0]} +∆t\mathbf{v} ^{[0]}$

For $k=0\dots K$
$\quad$ Recalculate projection

✅ 对于弹簧系统，Recaculate projection 这一步实际上不需要，因为直接用弹簧系统的公式算力，得到的$f$是一样的。
✅ 如果是做 shape matching, 还是需要这一步，用于算 $f$

$\quad$ Solve $(\frac{1}{∆t^2}\mathbf{M} +\mathbf{H} )∆\mathbf{x} =−\frac{1}{∆t^2}\mathbf{M} (\mathbf{x} ^{(k)}−\mathbf{x} ^{[0]}−∆t\mathbf{v} ^{[0]})+\mathbf{f} (\mathbf{x} ^{(k)})$

$\quad$ $\mathbf{x} ^{(k+1)}\longleftarrow \mathbf{x} ^{(k)}+∆\mathbf{x}$

$\quad$ If $||∆\mathbf{x}||$ is small $\quad$ then break

$\mathbf{x} ^{[1]}\longleftarrow \mathbf{x} ^{(k+1)}$

$\mathbf{v} ^{[1]}\longleftarrow (\mathbf{x} ^{[1]}-\mathbf{x} ^{[0]})/∆t$

“Newton’s Method”

$$\quad$$

P26

Preconditioned Steepest Descent

• Mathematically, this approach is preconditioned steepest descent, in which:

$$F(\mathbf{x} )=\frac{1}{2∆t^2} ||\mathbf{x} −\mathbf{x} ^{[0]}−∆t\mathbf{v} ^{[0]}||_\mathbf{M} ^2+E(\mathbf{x} )$$

The performance depends on how well $\mathbf{{\color{Orange} H} }$ approximates the real Hessian.

✅$\mathrm{H}$不需要很精确，一个近似的正定的矩阵，就能让结果收敛。

P27

Pros and Cons of Projective Dynamics

• By building constraints into energy, the simulation now has a theoretical solution with physical meaning.
• Fast on CPUs with a direct solver. No more factorization!

✅ Fast on CPU,因为它只作一次$\mathbf{LU}$分解。

• Fast convergence in the first few iterations.
• Slow on GPUs. (GPUs don’t support direct solver wells.)

✅ Slow on GPU，因为$\mathbf{LU}$分解不适用于 $\mathbf{GPU}$

• Slow convergence over time, as it fails to consider Hessian caused by projection.
  • Still suffering from high stiffness
• Cannot easily handle constraint changes.

✅ constraint changes: 网格关系改变导至弹簧结构改变，原来的$\mathbf{H}$将不再适用。
- Contacts
- Remeshing due to fracture, etc.

✅ 课后答疑：
能量优化的方法很少用于刚体，主要是有限元、弹性体、衣服模拟。

P28

After-Class Reading

Bouaziz et al. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. TOG (SIGGRAPH).

本文出自CaterpillarStudyGroup，转载请注明出处。

https://caterpillarstudygroup.github.io/GAMES103_mdbook/