Discrete bending forces and their Jacobians

Rasmus Tamstorf, Eitan GrinspunGraph. Model 2013 · DOI

TL;DR

This paper presents a compact and efficient closed-form expression for the Hessian of discrete bending energies, which is crucial for accurate and fast simulations of deformable objects like cloth. By exploiting symmetries and refactoring computations, they achieve up to a 7x speedup over automatic differentiation, making advanced simulation techniques more accessible.

What Problem Does This Paper Address?

Simulating the behavior of deformable objects, such as cloth or thin shells, in computer graphics and physics requires accurately modeling how they bend. A common approach involves defining a "bending energy" based on the angles between adjacent triangles in a mesh. To achieve realistic and stable simulations, especially with methods like implicit time stepping or Newton-based optimization, we need not only the energy and its gradient (which gives the forces) but also the Hessian (which describes how forces change with deformation). While gradients are well-understood, deriving the Hessian is notoriously tedious, error-prone, and computationally expensive. Existing methods either avoid it, use approximations, or rely on computationally heavy techniques like automatic differentiation, hindering the adoption of efficient numerical methods for these energies.

Methods

The core contribution is the derivation of a compact, closed-form expression for the Hessian of discrete bending energies. The authors achieve this by:

  • Exploiting Symmetry: They meticulously analyze the structure of the Hessian and identify symmetries between the contributions of adjacent triangles. This allows them to reuse computations.
  • Refactoring the Hessian: The Hessian is broken down into contributions from "half-hinges" (parts of a hinge associated with a single triangle) and then reassembled at the triangle level. This leads to a more organized and efficient computation.
  • Leveraging Building Blocks: They define several intermediate quantities (like $S(A)$, $w_{ij}$, $M_i$, $N_i$, $P_{ij}$, $Q_j$) that simplify the final expressions for the Hessian subblocks.
  • Conditional Transpose Operator: A novel operator is introduced to handle orientation differences between triangles when assembling the Hessian, ensuring consistency.

Datasets

Not discussed in the paper. The paper focuses on theoretical derivations and experimental evaluation using simulations.

Key Insights and Ideas

  • Hessian Derivation is Hard: The paper emphasizes that deriving the Hessian for discrete bending energies is a significant undertaking, often taking weeks of manual effort and being prone to errors.
  • Symmetry is Key: The significant speedups are achieved by exploiting the inherent symmetries in the Hessian's structure, which were previously underutilized.
  • Refactoring for Efficiency: Reorganizing the computation from a hinge-centric to a triangle-centric approach, while carefully handling orientation, leads to a more efficient implementation.
  • Compactness Matters: The derived closed-form expressions are not only efficient but also more readable and maintainable than those obtained through less structured methods.

Key Results

  • Speedup: The proposed method achieves up to a 7x speedup in evaluating bending forces and their gradients compared to automatic differentiation.
  • Accuracy: The derived Hessians are shown to be highly accurate, with normwise relative errors typically on the order of 1-2 ulps (units in the last place) when compared to existing methods.
  • Efficiency: The formulation leads to a more compact representation and reduces the number of operations required for Hessian assembly, with estimated speedups of 3x-4x over a previously used symbolic derivation.
  • Practical Impact: The paper demonstrates the method's effectiveness in cloth simulations, showing that the Hessian computation can be a significant portion of the total simulation time (4-33% depending on the method and simulation type).

Limitations and Future Work

  • Degeneracies: The paper acknowledges limitations related to degenerate mesh configurations, specifically "edge collapses" and "altitude collapses," which can lead to divisions by zero in the gradient and Hessian. While edge collapses can be handled with special cases, altitude collapses remain an issue.
  • Indefiniteness: The hinge angle Hessian is generally indefinite, meaning it's not positive definite. This prevents the use of certain efficient solvers like conjugate gradient or Cholesky decomposition for solving linear systems, and it also precludes phenomena like buckling.
  • Future Work: The authors suggest that the derived framework can be extended to other discrete differential geometry problems and that the performance gains can be further amplified by parallelization. The paper also hints at the potential for more advanced constitutive models and the need for robust handling of degeneracies.

Summary updated

BibTeX
@article{tamstorf2013discrete,
  author = {Rasmus Tamstorf and Eitan Grinspun},
  title = {{Discrete bending forces and their Jacobians}},
  journal = {Graph. Model},
  year = {2013},
  doi = {10.1016/j.gmod.2013.07.001},
}

Loading related content...

Figure