P27
Interior Point Methods and Impact Zone Optimization
✅ 发现碰撞的pairs后如何处理。
P28
Two Continuous Collision Response Approaches
✅ 这是两个大的套路，不是具体的方法。
Given the calculated next state \(\mathbf{x} ^{[1]}\), we want to update it into \(\bar{\mathbf{x} } ^{[1]}\), such that the path from \(\mathbf{x} ^{[0]}\) to \(\bar{\mathbf{x} } ^{[1]}\) is intersection-free.
内点法：
| 内点法 | Impact Zone 法 | ||
|---|---|---|---|
 |  | ✅ 蓝色区域为安全区域 | |
| ✅ 从\(\mathbf{x}^{[0]}\)出来，朝\(\mathbf{x}^{[1]}\)走，并永远保证只在安全区域走，直到不能走为止。 | ✅ 从\(\mathbf{x}^{[1]}\)出发，反复优化结果（投影），直到回到安全区域为止。 | ||
| 优点 | Always succeed | Fast. 1. Close to solution. 2. Only vertices in collision (impact zones). 3. Can take large step sizes. | ✅ Impact Zone：\(\mathbf{x}^{[1]}\)通常离安全区域不太远，且优化时只针对 Impact Zone 优化，因此快。 |
| 局限性 | Slow. 1. Far from solution. 2. All of the vertices. 3. Cautiously by small step sizes. | May not succeed. | ✅ 内点：为保证每一步安全，步长不能太大，因此慢、哪怕\(\mathbf{\bar{x}}^{[1]}\)最终没有到最佳位置，但能保证一定在安全区域，因此一定成功。\(\mathbf{x}^{[0]}\)和\(\mathbf{x}^{[1]}\)可能比较远，也导致慢。 ✅ 内点法慢的原因2没有解释。 |
P30
Log-Barrier Interior Point Methods
算法过程
For simplicity, let’s consider the Log-barrier repulsion between two vertices.
$$E(\mathbf{x} )=−\rho \text{ log} ||\mathbf{x} _{ij}||$$
$$ \mathbf{f} _i(\mathbf{x} )=−∇_iE=ρ\frac{\mathbf{x} _ {ij}}{||\mathbf{x} _ {ij}||^2} \\ \mathbf{f} _j(\mathbf{x} )=−∇_jE=−ρ\frac{\mathbf{x} _ {ij}}{||\mathbf{x} _{ij}||^2} $$
✅ 用 Log 定义能量、前面某一节课讲过。距离 → 能量 → 斥力
✅ 不需要互斥力一直存在，因此做了一个截断（IPC）
P31
算法实现
We can then formulate the problem as:
$$ \bar{\mathbf{x} }^ {[1]}\longleftarrow \mathrm{argmin} _\mathbf{x} (\frac{1}{2} ||\mathbf{x} −\mathbf{x} ^{[1]}||^2−ρ\sum \mathrm{log} ||\mathbf{x} _{ij}||) $$
✅ 优化目标：点的位置与目标位置（穿模）尽量接近，然后优化。
Gradient Descent:
\(\mathbf{x} ^{(0)}\longleftarrow \mathbf{x} ^{[0]}\)
For \(k=0…K\)
$$\mathbf{x} ^{(k+1)}\longleftarrow \mathbf{x} ^{(k)}+α(\mathbf{x} ^{[1]}−\mathbf{x} ^{(k)}+ρ\sum \frac{\mathbf{x} _{ij}}{||\mathbf{x} _{ij}||^2})$$ \(\bar{\mathbf{x} }^ {[1]}\longleftarrow \mathbf{x} ^{(k+1)}\)
The step size \({\color{Red} α}\) must be adjusted to ensure that no collision happens on the way. To find \({\color{Red} α}\), we need collision tests.
✅ 绿色是来自\(\mathbf{x}^{[1]}\)的引力，黄色是来自边界的斥力、关键是步长\(\alpha \)， 每走一小步都需要反复的碰撞检测。
P32
Impact Zone Optimization
The goal of impact zone optimization is to optimize \(\mathbf{x}^{[1]}\) until it becomes intersection-free. (This potentially suffers from the tunneling issue, but it’s uncommon.)
$$ \bar{\mathbf{x} }^{[1]}\longleftarrow \mathrm{argmin} _\mathbf{x} \frac{1}{2} ||\bar{\mathbf{x} }-\mathbf{x}^{[1]}||^2 $$
$$ \text{such that} \begin{cases} C(\mathbf{x} )=−(\mathbf{x} _3−b_0\mathbf{x} _0−b_1\mathbf{x} _1−b_2\mathbf{x} _1)\cdot \mathbf{N} ≤0 & \text{ For each detected vertex-triangle pair } \\ C(\mathbf{x} )=−(b_2\mathbf{x} _2+b_3\mathbf{x} _3−b_0\mathbf{x} _0−b_1\mathbf{x} _1)\cdot \mathbf{N}≤0 & \text{ For each detected edge-edge pair } \end{cases} $$
✅ 利用 constrain（不是能量）转化成优化问题，具体没讲。
P33
Geometric Impulse
The goal of impact zone optimization is to optimize \(\mathbf{x}^{[1]}\) until it becomes intersection-free. (This potentially suffers from the tunneling issue, but it’s uncommon.)
Every pair gives new positions to the involved vertices. We can combine them together in a Jacobi, or Gauss-Seidel fashion, just like position-based dynamics.
P34
After-Class Reading (Cont.)
Bridson et al. 2002. Robust Treatment of Collisions, Contact and Friction for Cloth Animation. TOG (SIGGRAPH).
Relative simple explicit integration of cloth dynamics
P35
Augmented Lagrangian
$$ \bar{\mathbf{x} }^{[1]}\longleftarrow \text{argmin} _\mathbf{x} \frac{1}{2} ||{\mathbf{x} }-\mathbf{x}^{[1]}||^2 $$
$$ \text{such that} \begin{cases} C(\mathbf{x} )=−(\mathbf{x} _3−b_0\mathbf{x} _0−b_1\mathbf{x} _1−b_2\mathbf{x} _1)\cdot \mathbf{N} ≤0 & \text{ For each detected vertex-triangle pair } \\ C(\mathbf{x} )=−(b_2\mathbf{x} _2+b_3\mathbf{x} _3−b_0\mathbf{x} _0−b_1\mathbf{x} _1)\cdot \mathbf{N}≤0 & \text{ For each detected edge-edge pair } \end{cases} $$
P36
Augmented Lagrangian
We can then convert it into an unconstrained form:
$$\bar{\mathbf{x} } {[1]}\longleftarrow \text{argmin}_{x,λ}(\frac{1}{2} ||\mathbf{x} −\mathbf{x} ^{[1]}||^2+\frac{ρ}{2} ||\text{max}(\tilde{C} (\mathbf{x} ))||^2−\frac{1}{2ρ}||\mathbf{λ} ||^2) $$
$$ \tilde{C} (\mathbf{x})= \text{max}(\mathbf{C} (\mathbf{x} )+\mathbf{λ} /ρ) $$
Augmented Lagrangian:
\(\mathbf{x} ^{(0)} \longleftarrow \mathbf{x} ^{[0]}\)
\(\mathbf{λ \longleftarrow 0} \)
For \(k=0…K\)
$$\mathbf{x} ^{(k+1)} \longleftarrow \mathbf{x} ^{(k)}−α∇(\frac{1}{2} ||\mathbf{x} −\mathbf{x} ^{[1]}||^2+\frac{ρ}{2} ||\text{max}(\tilde{C} (\mathbf{x} ))||^2−\frac{1}{2ρ}||\mathbf{λ} ||^2)$$
\(λ\longleftarrow ρ\tilde{C} (\mathbf{x} )\)
\(\bar{\mathbf{x} } ^{[1]}\longleftarrow \mathbf{x} ^{(k+1)}\)
Tang et al. 2018. I-Cloth: Incremental Collision Handling for GPU-Based Interactive Cloth Simulation. TOG. (SIGGRAPH Asia)
P37
About Impact Zone Optimization
-
Fast per iteration
- Only have to deal with vertices in collision.
-
Convergence sensitive to \(||\mathbf{x} ^{[0]}−\mathbf{x} ^{[1]}||^2\), or the time step \(∆t\)
- Can take many iterations to, or never achieve intersection-free.
- Easy solution is to reduce \(∆t\), but that increases total costs.
P38
Rigid Impact Zones
The rigid impact zone method simply freezes vertices in collision from moving in their pre-collision state. It’s simple and safe, but has noticeable artifacts.
✅ 检测到碰撞，则把这个区域退回到上一帧。
P39
A Practical System
✅ 有碰撞，先做 Impact Zone. 因为这个快、不能解决再用后面方法、计算量不允许则选择 Rigid Impact.
本文出自CaterpillarStudyGroup，转载请注明出处。
https://caterpillarstudygroup.github.io/GAMES103_mdbook/