Accelerated Complex-Step Finite Difference for Expedient Deformable Simulation

Abstract: In deformable simulation, an important computing task is to calculate the gradient and derivative of the strain energy function in order to infer the corresponding internal force and tangent stiffness matrix. The standard numerical routine is the finite difference method, which evaluates the target function multiple times under a small real-valued perturbation. Unfortunately, the subtractive cancellation prevents us from setting this perturbation sufficiently small, and the regular finite difference is doomed for computing problems requiring a high-accuracy derivative evaluation. In this paper, we graft a new finite difference scheme, namely the complex-step finite difference (CSFD), with physics-based animation. CSFD is based on the complex Taylor series expansion, which avoids subtractions in first-order derivative approximation. As a result, one can use a very small perturbation to calculate the numerical derivative that is as accurate as its analytic counterpart. We accelerate the original CSFD method so that it is also as efficient as the analytic derivative. This is achieved by discarding high-order error terms, decoupling real and imaginary calculations, replacing costly functions based on the theory of equivalent infinitesimal, and isolating the propagation of the perturbation in composite/nesting functions. CSFD can be further augmented with multicomplex Taylor expansion and Cauchy-Riemann formula to handle higher-order derivatives and tensor-valued functions. We demonstrate the accuracy, convenience, and efficiency of this new numerical routine in the context of deformable simulation -- one can easily deploy a robust simulator for general hyperelastic materials, including user-crafted ones to cater specific needs in different applications. Higher-order derivatives of the energy can be readily computed to construct modal derivative bases for reduced real-time simulation. Inverse simulation problems can also be conveniently solved using gradient/Hessian-based optimization procedures.

Authors/Presenter(s): Hongyi Xu, Google, Switzerland
Yin Yang, University of New Mexico, United States of America
Ran Luo, University of New Mexico, United States of America
Weiwei Xu, State Key Lab of CAD & CG, State Key Laboratory of CAD & CG, Zhejiang University, China
Tianjia Shao, University of Leeds, United Kingdom

Material-adapted Refinable Basis Functions for Elasticity Simulation

Abstract: In this paper, we introduce a hierarchical construction of material-adapted refinable basis functions and associated wavelets to offer efficient coarse-graining of linear elastic objects. While spectral methods rely on global basis functions to restrict the number of degrees of freedom, our basis functions are locally supported; yet, unlike typical polynomial basis functions, they are adapted to the material inhomogeneity of the elastic object to better capture its physical properties and behavior. In particular, they share spectral approximation properties with eigenfunctions, offering a good compromise between computational complexity and accuracy. Their construction involves only linear algebra and follows a fine-to-coarse approach, leading to a block-diagonalization of the stiffness matrix where each block corresponds to an intermediate scale space of the elastic object. Once this hierarchy has been precomputed, we can simulate an object at runtime on very coarse resolution grids and still capture the correct physical behavior, with orders of magnitude speedup compared to a fine simulation. We show on a variety of heterogeneous materials that our approach outperforms all previous coarse-graining methods for elasticity.

Authors/Presenter(s): Jiong Chen, State Key Laboratory of CAD & CG, Zhejiang University, China
Max Budninskiy, true[X], United States of America
Houman Owhadi, California Institute of Technology, United States of America
Hujun Bao, State Key Laboratory of CAD & CG, Zhejiang University, China
Jin Huang, State Key Laboratory of CAD & CG, Zhejiang University, China
Mathieu Desbrun, California Institute of Technology, United States of America

A Scalable Galerkin Multigrid Method for Real-time Simulation of Deformable Objects

Abstract: We propose a simple yet efficient multigrid scheme to simulate high-resolution deformable objects in their full spaces at interactive frame rates. The point of departure of our method is the Galerkin projection which is simple to construct. However, a naïve Galerkin multigrid does not scale well for large and irregular grids because it trades-off matrix sparsity for smaller sized linear systems which eventually stops improving the performance. Given that observation, we design our special projection criterion which is based on skinning space coordinates with piecewise constant weights, to make our Galerkin multigrid method scale for high-resolution meshes without suffering from dense linear solves. The usage of skinning space coordinates enables us to reduce the resolution of grids more aggressively, and our piecewise constant weights further ensure us to always deal with reasonably-sparse linear solves. Our projection matrices also help us to manage multi-level linear systems efficiently. Therefore, our method can be applied to different optimization schemes such as Newton's method and Projective Dynamics, pushing the resolution of a real-time simulation to orders of magnitudes higher. Our final GPU implementation outperforms the other state-of-the-art GPU deformable body simulators, enabling us to simulate large deformable objects with hundred thousands of degrees of freedom in real-time.

Authors/Presenter(s): Zangyueyang Xian, Shanghai Jiao Tong University, Microsoft Research Asia, China
Xin Tong, Microsoft Research Asia, China
Tiantian Liu, Microsoft Research Asia, China

Accelerating ADMM for Efficient Simulation and Optimization

Abstract: The alternating direction method of multipliers (ADMM) is a popular method for solving optimization problems that are potentially non-smooth and with hard constraints. It has been applied to various computer graphics applications including physics simulation, geometry processing, and image processing. However, ADMM can take a long time to converge to a solution of high accuracy. Moreover, many computer graphics tasks involve non-convex optimization problems, and there is often no convergence guarantee for ADMM on such problems since it was originally designed for convex optimization. In this paper, we propose a method to speed up ADMM using Anderson acceleration, which is an established technique to accelerate a fixed-point iteration. We show that in the general case, ADMM is a fixed-point iteration of the second primal variable and the dual variable, and Anderson acceleration can be directly applied. Additionally, when the problem has a separable target function and satisfies certain conditions, ADMM becomes a fixed-point iteration of only one variable, which further reduces the computational overhead of Anderson acceleration. Moreover, we analyze a particular non-convex problem structure that is commonly used in computer graphics, and prove the convergence of ADMM on such problem under mild assumptions. We apply our acceleration technique on a variety of optimization problems in computer graphics, with notable improvement on their convergence speed.

Authors/Presenter(s): Juyong Zhang, University of Science and Technology of China, China
Yue Peng, University of Science and Technology of China, China
Wenqing Ouyang, University of Science and Technology of China, China
Bailin Deng, Cardiff University, United Kingdom

Schur Complement-based Substructuring of Stiff Multibody Systems with Contact

Abstract: Substructuring permits parallelization of physics simulation on multi-core CPUs. We present a new substructuring approach for solving stiff multibody systems containing both bilateral and unilateral constraints. Our approach is based on non-overlapping domain decomposition with the Schur complement method, which we extend to systems involving contact formulated as a mixed bounds linear complementarity problem. At each time step, we alternate between solving the subsystem and interface constraint impulses, which leads to the identification of the active constraints. By using the active constraints to compute the effective mass of subsystems within the interface solve, we obtain an exact solution. We demonstrate that our simulations have preferable behavior compared to standard iterative solvers and substructuring techniques based on the exchange of forces at interface bodies. We observe considerable speedups for structured simulations where a user-defined partitioning can be applied, and moderate speedups for unstructured simulations, such as piles of bodies. In the latter case, we propose an automatic partitioning strategy based on the degree of bodies in the constraint graph. Because our method makes use of direct solvers, we are able to achieve interactive and real-time frame rates for a number of challenging scenarios involving large mass ratios, redundant constraints, and ill-conditioned systems.

Authors/Presenter(s): Albert Peiret, McGill University, Canada
Sheldon Andrews, École de technologie supérieure, Canada
Jozsef Kovecses, McGill University, Canada
Paul Kry, McGill University, Canada
Marek Teichmann, CM Labs Simulations, Canada