Abstract Existing approaches to frictional contact dynamics typically either modify the Coulomb law to improve numerical robustness or solve the exact law in a fully coupled monolithic form. However, in its reduced form, exact Coulomb friction can be written as a cone complementarity problem with an augmented velocity, which reveals a natural split between a cone‐constrained linear response and a scalar non‐associated coupling induced by tangential velocity. We exploit this structure in the solver design. Our method uses an outer iteration to update the non‐associated coupling explicitly, and an inner solve for a strongly convex cone‐constrained quadratic program. This separation also makes the inner solver modular, so different numerical schemes can be used without changing the outer iteration. We evaluate the method on rigid‐body benchmarks with stick‐slip transitions and frictional stacking, and show that it reproduces exact Coulomb complementarity without smoothing or relaxing the friction law.

Dynamics simulation with frictional contacts is important for a wide range of applications, from cloth simulation to object manipulation. Recent methods using smoothed lagged friction forces have enabled robust and differentiable simulation of elastodynamics with friction. However, the resulting frictional behavior can be inaccurate and may not converge to analytic solutions. Here we evaluate the accuracy of lagged friction models in comparison with implicit frictional contact systems. We show that major inaccuracies near the stick-slip threshold in such systems are caused by lagging of friction forces rather than by smoothing the Coulomb friction curve. Furthermore, we demonstrate how systems involving implicit or lagged friction can be correctly used with higher-order time integration and highlight limitations in earlier attempts. We demonstrate how to exploit forward-mode automatic differentiation to simplify and, in some cases, improve the performance of the inexact Newton method. Finally, we show that other complex phenomena can also be simulated effectively while maintaining smoothness of the entire system. We extend our method to exhibit stick-slip frictional behavior and preserve volume on compressible and nearly-incompressible media using soft constraints.

Physics-based simulation methods for deformable objects suffer limitations due to the conflicting requirements that are placed on them. The work horse semi-implicit (SI) backward Euler method is very stable and inexpensive, but it is also a blunt instrument. It applies heavy damping, which depends on the timestep, to all solution modes and not just to high-frequency ones. As such, it makes simulations less lively, potentially missing important animation details. At the other end of the scale, exponential methods (exponential Rosenbrock Euler (ERE)) are known to deliver good approximations to all modes, but they get prohibitively expensive and less stable for very stiff material. In this article, we devise a hybrid, semi-implicit method called SIERE that allows the previous methods SI and ERE to each perform what they are good at. To do this, we employ at each timestep a partial spectral decomposition, which picks the lower, leading modes, applying ERE in the corresponding subspace. The rest is handled (i.e., effectively damped out) by SI. No solution of nonlinear algebraic equations is required throughout the algorithm. We show that the resulting method produces simulations that are visually as good as those of the exponential method at a computational price that does not increase with stiffness, while displaying stability and damping with respect to the high-frequency modes. Furthermore, the phenomenon of occasional divergence of SI is avoided.

Abstract Commonly used linear and nonlinear constitutive material models in deformation simulation contain many simplifications and only cover a tiny part of possible material behavior. In this work we propose a framework for learning customized models of deformable materials from example surface trajectories. The key idea is to iteratively improve a correction to a nominal model of the elastic and damping properties of the object, which allows new forward simulations with the learned correction to more accurately predict the behavior of a given soft object. Space‐time optimization is employed to identify gentle control forces with which we extract necessary data for model inference and to finally encapsulate the material correction into a compact parametric form. Furthermore, a patch based position constraint is proposed to tackle the challenge of handling incomplete and noisy observations arising in real‐world examples. We demonstrate the effectiveness of our method with a set of synthetic examples, as well with data captured from real world homogeneous elastic objects.

High quality simulations of the dynamics of soft flexible objects can be rather costly, because the assembly of internal forces through an often nonlinear stiffness at each time step is expensive. Many standard implicit integrators introduce significant, time-step dependent artificial damping. Here we propose and demonstrate the effectiveness of an exponential Rosenbrock-Euler (ERE) method which avoids discretization-dependent artificial damping. The method is relatively inexpensive and works well with the large time steps used in computer graphics. It retains correct qualitative behaviour even in challenging circumstances involving non-convex elastic energies. Our integrator is designed to handle and perform well even in the important cases where the symmetric stiffness matrix is not positive definite at all times. Thus we are able to address a wider range of practical situations than other related solvers. We show that our system performs efficiently for a wide range of soft materials.

We present a data-driven method for deformation capture and modeling of general soft objects. We adopt an iterative framework that consists of one component for physics-based deformation tracking and another for spacetime optimization of deformation parameters. Low cost depth sensors are used for the deformation capture, and we do not require any force-displacement measurements, thus making the data capture a cheap and convenient process. We augment a state-of-the-art probabilistic tracking method to robustly handle noise, occlusions, fast movements and large deformations. The spacetime optimization aims to match the simulated trajectories with the tracked ones. The optimized deformation model is then used to boost the accuracy of the tracking results, which can in turn improve the deformation parameter estimation itself in later iterations. Numerical experiments demonstrate that the tracking and parameter optimization components complement each other nicely. Our spacetime optimization of the deformation model includes not only the material elasticity parameters and dynamic damping coefficients, but also the reference shape which can differ significantly from the static shape for soft objects. The resulting optimization problem is highly nonlinear in high dimensions, and challenging to solve with previous methods. We propose a novel splitting algorithm that alternates between reference shape optimization and deformation parameter estimation, and thus enables tailoring the optimization of each subproblem more efficiently and robustly. Our system enables realistic motion reconstruction as well as synthesis of virtual soft objects in response to user stimulation. Validation experiments show that our method not only is accurate, but also compares favorably to existing techniques. We also showcase the ability of our system with high quality animations generated from optimized deformation parameters for a variety of soft objects, such as live plants and fabricated models.

Points acquired by laser scanners are not intrinsically equipped with normals, which are essential to surface reconstruction and point set rendering using surfels. Normal estimation is notoriously sensitive to noise. Near sharp features, the computation of noise-free normals becomes even more challenging due to the inherent undersampling problem at edge singularities. As a result, common edge-aware consolidation techniques such as bilateral smoothing may still produce erroneous normals near the edges. We propose a resampling approach to process a noisy and possibly outlier-ridden point set in an edge-aware manner. Our key idea is to first resample away from the edges so that reliable normals can be computed at the samples, and then based on reliable data, we progressively resample the point set while approaching the edge singularities. We demonstrate that our Edge-Aware Resampling (EAR) algorithm is capable of producing consolidated point sets with noise-free normals and clean preservation of sharp features. We also show that EAR leads to improved performance of edge-aware reconstruction methods and point set rendering techniques.

Concocting a plausible composition from several non-overlapping image pieces, whose relative positions are not fixed in advance and without having the benefit of priors, can be a daunting task. Here we propose such a method, starting with a set of sloppily pasted image pieces with gaps between them. We first extract salient curves that approach the gaps from non-tangential directions, and use likely correspondences between pairs of such curves to guide a novel tele-registration method that simultaneously aligns all the pieces together. A structure-driven image completion technique is then proposed to fill the gaps, allowing the subsequent employment of standard in-painting tools to finish the job.

We consolidate an unorganized point cloud with noise, outliers, non-uniformities, and in particular interference between close-by surface sheets as a preprocess to surface generation, focusing on reliable normal estimation. Our algorithm includes two new developments. First, a weighted locally optimal projection operator produces a set of denoised, outlier-free and evenly distributed particles over the original dense point cloud, so as to improve the reliability of local PCA for initial estimate of normals. Next, an iterative framework for robust normal estimation is introduced, where a priority-driven normal propagation scheme based on a new priority measure and an orientation-aware PCA work complementarily and iteratively to consolidate particle normals. The priority setting is reinforced with front stopping at thin surface features and normal flipping to enable robust handling of the close-by surface sheet problem. We demonstrate how a point cloud that is well-consolidated by our method steers conventional surface generation schemes towards a proper interpretation of the input data.

We present a numerical scheme for the real-time solution of the discretized one-dimensional linearized acoustics equation (Webster's equation) augmented with dissipative terms, in a tube with a spatially and temporally varying cross section. The resulting algorithm produces similar results as the Kelly–Lochbaum model but has several advantages over it: the tube length can change continuously, the area function can change in time and can be governed by a dynamical model itself, the scheme is of second-order accuracy, and the spatial and temporal discretization does not need to be uniform. We show how the model can be used to build a realistic real-time audio synthesis method for articulatory speech synthesis by coupling it to a lip radiation model, a dynamical wall model, and a glottal excitation model.

We describe a framework for derivation of several forward dynamics algorithms used in robotics. The framework is based on formulating an augmented system and performing block matrix elimination on this system. Several popular algorithms such as the O(N) articulated body method, and the composite rigid body method can be easily derived. We also derive an algorithm for simulation of contact between smooth bodies of arbitrary shape, in contact coordinates. Finally, we discuss some potential numerical difficulties that could arise and their solution.

The method of programmed constraints has recently been proposed as an executable specification language for robot programming. The mathematical structures behind such problems are viability problems for control systems described by ordinary differential equations (ODE) subject to user-defined inequality constraints. This paper describes a method for the numerical solution of such problems, improving and extending some of our previous results. The algorithm presented is composed of three parts: delay-free discretization, local control, and local planning. Delay-free discretizations are consistent discretizations of control systems described by ODEs with discontinuous inputs. The local control is based on the minimization of an artificial, logarithmic barrier potential function. Local planning is a computationally inexpensive way to increase the robustness of the solution procedure, making it a refinement to a strategy based on viability alone. Simulations of a mobile robot are used to demonstrate the proposed strategy. Some complementarity is shown between the programmed-constraints approach to robot programming and optimal control. Moreover, we demonstrate the relative efficiency of our algorithm compared to optimal control: Typically, our method is able to find a solution on the order of 100 times faster than an optimal-control solver.

The authors identify an important phenomenon they call "formulation stiffness" in the numerical simulation of tree-structured multibody systems such as robot manipulators. The numerical simulation problem is usually treated as two separate problems: (i) the forward dynamics problem for computing system accelerations, and (ii) the numerical integration problem far advancing the state in time. The authors show that the interaction of these two problems leads to new conclusions about the overall efficiency of multibody simulation algorithms; in particular the fastest forward dynamics methods are not necessarily best when considered in conjunction with the popular adaptive stepsize integration methods. Specifically, the authors show that the articulated-body method is better suited to deal with certain types of numerical problems than the composite rigid body method. The authors present examples of simulations and discuss the practical implications of these results.

Recently, new robot programming approaches have proposed the use of programmed constraints as an executable specification language for the desired behavior of a robot. The constraint-based approaches are intermediate level languages, promising a higher, more declarative level of programming than trajectory-based approaches, while being more tractable computationally than motion planning. This paper considers a numerical algorithm for solution of differential systems subject to algebraic inequality constraints. These are the mathematical structures behind the constraint-based approach. Our approach is based on a principle of 'least constraint', consisting of a dynamic integration of the equations of motion coupled with invocation of a control mechanism to ensure that the robot trajectory avoids all constraint boundaries. This is achieved by minimization of a barrier function defined using buffer zones near the constraint boundaries. Determination of the buffer zones is done dynamically, corresponding to a local planning strategy.

The authors describe a nonlinear optimization model for the placement of rectangular blocks with some wire connections among them in the Euclidean plane, so that the total wire length is minimized. Such a placement algorithm is useful as a CAD tool for VLSI and printed-circuit-board layout designs. The model ensures that the blocks will not overlap and minimizes the sum of the distances of the interconnections of the blocks with respect to their orientation as well as their position. Mechanisms are presented for solving more restrictive placement problems, including one in which there is a set of equally spaced, discrete angles to be used in the placement. The mathematical model is based on the Lennard-Jones 6-12 potential equation, on a sine-wave-shaped penalty function, and on minimizing the sum of the squares of the Euclidean distances of the block interconnections. Experimental results are presented to show that good placements are achieved with these techniques.>

The use of a general-purpose code, COLSYS, is described.The code is capable of solving mixed-order systems of boundary-value problems in ordinary differential equations.The method of spline collocation at Gaussian points is implemented using a B-spline basis.Approximate solutions are computed on a sequence of automatically selected meshes until a user-specified set of tolerances is satisfied.A damped Newton's method is used for the nonlinear iteration.The code has been found to be particularly effective for difficult problems.It is intended that a user be able to use COLSYS easily after reading its algorithm description.The use of the code is then illustrated by examples demonstrating its effectiveness and capabilities.

This package is a complement to [1] where its usage is described and demonstrated.COLSYS uses the following non-American National Standard FORTRAN conventions:(1) No run-time subscript range checking.(2) Simple expressions used as subscripts.(3) Specifications of array values in DATA statements (used in subroutine CONSTS) by referring to the array name only.