IPC Notes

Note of the paper Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection- and Inversion-free, Large-Deformation Dynamics. ACM Trans. Graph. 39, 4, Article 49 (July 2020), 20 pages. https: //doi.org/10.1145/3386569.3392425

Introduction

Incremental potential contact (IPC) is a recent milestone of contaction and friction simulation in computer graphics. IPC remarkably enhanced the robustness of large deformation dynamics.

Physical Model

Let us begin with the action functional. \(S[x] = \int_{t_0}^{t_1}\left(\frac{1}{2} \dot{x}^T M \dot{x} - \Psi(x) + x^T(f_e + f_d) \right) dt\)

In IPC paper, the functional is “extended-value action”, which means that the value can be $\infty$.

Here, $f_e$ are external forces and $f_d$ are dissipative frictional forces. From the perspective of analyical mechanics, we will find the trajectory that minimizing the action. However, the admissible trajectories of shape deformation should be properly defined.

Admissible trajectories

Definition of “intersection free”

We say a trajectory is “intersection free”, if for all moments $t$, the distance $d(p, q)$ between any two distinct points $p$ and $q$ on the boundaries of objects is positive.

The intersection-free trajectories forms a open set $\mathcal{A}_I$ in the space of trajectories. The set of admissible trajectories is defined as the closure of $\mathcal{A}_I$, denoted as $\mathcal{A}$.

A natural question is how to describe the admissible trajectories. And here comes a key observation of IPC, which can greatly reduce the computation:

The distance between any pair of primitives is bounded from below by the distance for triangle-vertex and edge-edge pairs, if there are no intersections.

Hence, it is sufficient to enforce constraints $d_k (x(t)) > 0$ continuously in time, for all $k \in C \subset B$ where $B$ contains all primitive pairs and $C$ contains all non-incident point-triangle and all non-adjacent edge-edge pairs in the surface mesh. We also let $\mathcal{T}$ denote the set of all primitives.

Incremental Potential

What is incremental potential(IP)? In short, the incremental potential is the variational form of the time step updating methods. For example, for implicit Euler, given positions and velocities at time $t$, the incremental potential is

where $h$ is the time step size and $\hat{x} = x^t + h v^t + h^2 M^{-1}f_e$.

With the constraints of contaction, the minimization of IP is restricted to the admissible trajectories:

where $x^{\tau}$, $\tau \in [t, t+1]$, is the linear trajectory between $x^t$ and $x^{t + 1}$.

Trajectory accuracies

IPC Method

Barrier-augmented Incremental Potential

To enforce $d_k(t) > 0$ for all $k \in C$ and $t$, we construct a continuous barrier energy $b$ affecting motion only when primitives are close to collision, and vanishing if primitives are a small userspecified distance apart.

$\kappa$ > 0 an adaptive conditioning parameter automatically controlling the barrier stiffness

What is barrier stiffness

The observation above allows us compute only $\vert C \vert$ distance value, not $O(\vert \mathcal{T} \vert^2)$.

Barrier Function

IPC choose a $C^2$ function as the barrier function

Newton-type Barrier Solver Details

The barrier solvers follow the project Newton style.

• Project Hessian to positively semi-definite. Following Teran [2005], project per-element elasticity Hessians to PSD
• Terminate when $\frac{1}{h}\Vert p \Vert < \epsilon_d$
• Adaptive update barrier sniffness $\kappa$.

Intersection-aware Line Search

Barrier energy and standard line search is not enough for avoiding penetrations. IPC applies a CCD to conservatively compute a large feasible step size and then applies the line search.