Invertible finite elements for robust simulation of large deformation

Large Growth Deformations of Thin Tissue Using Solid-Shells

Simulating large scale expansion of thin structures, such as in growing leaves, is challenging. Solid-shells have a number of potential advantages over conventional thin-shell methods, but have thus far only been investigated for small plastic deformation cases. In response, we present a new general-purpose FEM growth framework for handling a wide range of challenging growth scenarios using the solid-shell element. Solid-shells are a middle-ground between traditional volume and thin-shell elements where volumetric characteristics are retained while being treatable as a 2D manifold much like thin-shells. These elements are adaptable to accommodate the many techniques that are required for simulating large and intricate plastic deformations, including morphogen diffusion, plastic embedding, strain-aware adaptive remeshing, and collision handling. We demonstrate the capabilities of growing solid-shells in reproducing buckling, rippling, curling, and collision deformations, relevant towards animating growing leaves, flowers, and other thin structures. Solid-shells are compared side-by-side with thin-shells to examine their bending behavior and runtime performance. The experiments demonstrate that solid-shells are a viable alternative to thin-shells for simulating large and intricate growth deformations.

ERGOBOSS: Ergonomic Optimization of Body-Supporting Surfaces

Humans routinely sit or lean against supporting surfaces and it is important to shape these surfaces to be comfortable and ergonomic. We give a method to design the geometric shape of rigid supporting surfaces to maximize the ergonomics of physically based contact between the surface and a deformable human. We model the soft deformable human using a layer of FEM deformable tissue surrounding a rigid core, with measured realistic elastic material properties, and large-deformation nonlinear analysis. We define a novel cost function to measure the ergonomics of contact between the human and the supporting surface. We give a stable and computationally efficient contact model that is differentiable with respect to the supporting surface shape. This makes it possible to optimize our ergonomic cost function using gradient-based optimizers. Our optimizer produces supporting surfaces superior to prior work on ergonomic shape design. Our examples include furniture, apparel and tools. We also validate our results by scanning a real human subject's foot and optimizing a shoe sole shape to maximize foot contact ergonomics. We 3D-print the optimized shoe sole, measure contact pressure using pressure sensors, and demonstrate that the real unoptimized and optimized pressure distributions qualitatively match those predicted by our simulation.

Manipulating deformable objects by interleaving prediction, planning, and control

We present a framework for deformable object manipulation that interleaves planning and control, enabling complex manipulation tasks without relying on high-fidelity modeling or simulation. The key question we address is when should we use planning and when should we use control to achieve the task? Planners are designed to find paths through complex configuration spaces, but for highly underactuated systems, such as deformable objects, achieving a specific configuration is very difficult even with high-fidelity models. Conversely, controllers can be designed to achieve specific configurations, but they can be trapped in undesirable local minima owing to obstacles. Our approach consists of three components: (1) a global motion planner to generate gross motion of the deformable object; (2) a local controller for refinement of the configuration of the deformable object; and (3) a novel deadlock prediction algorithm to determine when to use planning versus control. By separating planning from control we are able to use different representations of the deformable object, reducing overall complexity and enabling efficient computation of motion. We provide a detailed proof of probabilistic completeness for our planner, which is valid despite the fact that our system is underactuated and we do not have a steering function. We then demonstrate that our framework is able to successfully perform several manipulation tasks with rope and cloth in simulation, which cannot be performed using either our controller or planner alone. These experiments suggest that our planner can generate paths efficiently, taking under a second on average to find a feasible path in three out of four scenarios. We also show that our framework is effective on a 16-degree-of-freedom physical robot, where reachability and dual-arm constraints make the planning more difficult.

NNWarp: Neural Network-Based Nonlinear Deformation

NNWarp is a highly re-usable and efficient neural network (NN) based nonlinear deformable simulation framework. Unlike other machine learning applications such as image recognition, where different inputs have a uniform and consistent format (e.g., an array of all the pixels in an image), the input for deformable simulation is quite variable, high-dimensional, and parametrization-unfriendly. Consequently, even though the neural network is known for its rich expressivity of nonlinear functions, directly using an NN to reconstruct the force-displacement relation for general deformable simulation is nearly impossible. NNWarp obviates this difficulty by partially restoring the force-displacement relation via warping the nodal displacement simulated using a simplistic constitutive model-the linear elasticity. In other words, NNWarp yields an incremental displacement fix per mesh node based on a simplified (therefore incorrect) simulation result other than synthesizing the unknown displacement directly. We introduce a compact yet effective feature vector including geodesic, potential and digression to sort training pairs of per-node linear and nonlinear displacement. NNWarp is robust under different model shapes and tessellations. With the assistance of deformation substructuring, one NN training is able to handle a wide range of 3D models of various geometries. Thanks to the linear elasticity and its constant system matrix, the underlying simulator only needs to perform one pre-factorized matrix solve at each time step, which allows NNWarp to simulate large models in real time.

Physics-Based Quadratic Deformation Using Elastic Weighting

This paper presents a spatial reduction framework for simulating nonlinear deformable objects interactively. This reduced model is built using a small number of overlapping quadratic domains as we notice that incorporating high-order degrees of freedom (DOFs) is important for the simulation quality. Departing from existing multi-domain methods in graphics, our method interprets deformed shapes as blended quadratic transformations from nearby domains. Doing so avoids expensive safeguards against the domain coupling and improves the numerical robustness under large deformations. We present an algorithm that efficiently computes weight functions for reduced DOFs in a physics-aware manner. Inspired by the well-known multi-weight enveloping technique, our framework also allows subspace tweaking based on a few representative deformation poses. Such elastic weighting mechanism significantly extends the expressivity of the reduced model with light-weight computational efforts. Our simulator is versatile and can be well interfaced with many existing techniques. It also supports local DOF adaption to incorporate novel deformations (i.e., induced by the collision). The proposed algorithm complements state-of-the-art model reduction and domain decomposition methods by seeking for good trade-offs among animation quality, numerical robustness, pre-computation complexity, and simulation efficiency from an alternative perspective.

Projective Peridynamics for Modeling Versatile Elastoplastic Materials

Unified simulation of versatile elastoplastic materials and different dimensions offers many advantages in animation production, contact handling, and hardware acceleration. The unstructured particle representation is particularly suitable for this task, thanks to its simplicity. However, previous meshless techniques either need too much computational cost for addressing stability issues, or lack physical meanings and fail to generate interesting deformation behaviors, such as the Poisson effect. In this paper, we study the development of an elastoplastic model under the state-based peridynamics framework, which uses integrals rather than partial derivatives in its formulation. To model elasticity, we propose a unique constitutive model and an efficient iterative simulator solved in a projective dynamics way. To handle plastic behaviors, we incorporate our simulator with the Drucker-Prager yield criterion and a reference position update scheme, both of which are implemented under peridynamics. Finally, we show how to strengthen the simulator by position-based constraints and spatially varying stiffness models, to achieve incompressibility, particle redistribution, cohesion, and friction effects in viscoelastic and granular flows. Our experiments demonstrate that our unified, meshless simulator is flexible, efficient, robust, and friendly with parallel computing.

Dynamic anticrack propagation in snow

Continuum numerical modeling of dynamic crack propagation has been a great challenge over the past decade. This is particularly the case for anticracks in porous materials, as reported in sedimentary rocks, deep earthquakes, landslides, and snow avalanches, as material inter-penetration further complicates the problem. Here, on the basis of a new elastoplasticity model for porous cohesive materials and a large strain hybrid Eulerian–Lagrangian numerical method, we accurately reproduced the onset and propagation dynamics of anticracks observed in snow fracture experiments. The key ingredient consists of a modified strain-softening plastic flow rule that captures the complexity of porous materials under mixed-mode loading accounting for the interplay between cohesion loss and volumetric collapse. Our unified model represents a significant step forward as it simulates solid-fluid phase transitions in geomaterials which is of paramount importance to mitigate and forecast gravitational hazards.

Anticrack propagation in snow results from the mixed-mode failure and collapse of a buried weak layer and can lead to slab avalanches. Here, authors reproduce the complex dynamics of anticrack propagation observed in field experiments using a Material Point Method with large strain elastoplasticity.

Enriching Triangle Mesh Animations with Physically Based Simulation

We present a system to combine arbitrary triangle mesh animations with physically based Finite Element Method (FEM) simulation, enabling control over the combination both in space and time. The input is a triangle mesh animation obtained using any method, such as keyframed animation, character rigging, 3D scanning, or geometric shape modeling. The input may be non-physical, crude or even incomplete. The user provides weights, specified using a minimal user interface, for how much physically based simulation should be allowed to modify the animation in any region of the model, and in time. Our system then computes a physically-based animation that is constrained to the input animation to the amount prescribed by these weights. This permits smoothly turning physics on and off over space and time, making it possible for the output to strictly follow the input, to evolve purely based on physically based simulation, and anything in between. Achieving such results requires a careful combination of several system components. We propose and analyze these components, including proper automatic creation of simulation meshes (even for non-manifold and self-colliding undeformed triangle meshes), converting triangle mesh animations into animations of the simulation mesh, and resolving collisions and self-collisions while following the input.

ADMM ⊇ Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints

We apply the alternating direction method of multipliers (ADMM) optimization algorithm to implicit time integration of elastic bodies, and show that the resulting method closely relates to the recently proposed projective dynamics algorithm. However, as ADMM is a general purpose optimization algorithm applicable to a broad range of objective functions, it permits the use of nonlinear constitutive models and hard constraints while retaining the speed, parallelizability, and robustness of projective dynamics. We further extend the algorithm to improve the handling of dynamically changing constraints such as sliding and contact, while maintaining the benefits of a constant, prefactored system matrix. We demonstrate the benefits of our algorithm on several examples that include cloth, collisions, and volumetric deformable bodies with nonlinear elasticity and skin sliding effects.

Optimization Integrator for Large Time Steps

Practical time steps in today's state-of-the-art simulators typically rely on Newton's method to solve large systems of nonlinear equations. In practice, this works well for small time steps but is unreliable at large time steps at or near the frame rate, particularly for difficult or stiff simulations. We show that recasting backward Euler as a minimization problem allows Newton's method to be stabilized by standard optimization techniques with some novel improvements of our own. The resulting solver is capable of solving even the toughest simulations at the [Formula: see text] frame rate and beyond. We show how simple collisions can be incorporated directly into the solver through constrained minimization without sacrificing efficiency. We also present novel penalty collision formulations for self collisions and collisions against scripted bodies designed for the unique demands of this solver. Finally, we show that these techniques improve the behavior of Material Point Method (MPM) simulations by recasting it as an optimization problem.

Stable Anisotropic Materials

The Finite Element Method (FEM) is commonly used to simulate isotropic deformable objects in computer graphics. Several applications (wood, plants, muscles) require modeling the directional dependence of the material elastic properties in three orthogonal directions. We investigate linear orthotropic materials, a special class of linear anisotropic materials where the shear stresses are decoupled from normal stresses, as well as general linear (non-orthotropic) anisotropic materials. Orthotropic materials generalize transversely isotropic materials, by exhibiting different stiffness in three orthogonal directions. Orthotropic materials are, however, parameterized by nine values that are difficult to tune in practice, as poorly adjusted settings easily lead to simulation instabilities. We present a user-friendly approach to setting these parameters that is guaranteed to be stable. Our approach is intuitive as it extends the familiar intuition known from isotropic materials. Similarly to linear orthotropic materials, we also derive a stability condition for a subset of general linear anisotropic materials, and give intuitive approaches to tuning them. In order to simulate large deformations, we augment linear corotational FEM simulations with our orthotropic and general anisotropic materials.

Aggregate Constraints for Virtual Manipulation with Soft Fingers

Interactive dexterous manipulation of virtual objects remains a complex challenge that requires both appropriate hand models and accurate physically-based simulation of interactions. In this paper, we propose an approach based on novel aggregate constraints for simulating dexterous grasping using soft fingers. Our approach aims at improving the computation of contact mechanics when many contact points are involved, by aggregating the multiple contact constraints into a minimal set of constraints. We also introduce a method for non-uniform pressure distribution over the contact surface, to adapt the response when touching sharp edges. We use the Coulomb-Contensou friction model to efficiently simulate tangential and torsional friction. We show through different use cases that our aggregate constraint formulation is well-suited for simulating interactively dexterous manipulation of virtual objects through soft fingers, and efficiently reduces the computation time of constraint solving.

Volume Preserved Mass-Spring Model with Novel Constraints for Soft Tissue Deformation

An interactive surgical simulation system needs to meet three main requirements, speed, accuracy, and stability. In this paper, we present a stable and accurate method for animating mass-spring systems in real time. An integration scheme derived from explicit integration is used to obtain interactive realistic animation for a multiobject environment. We explore a predictor-corrector approach by correcting the estimation of the explicit integration in a poststep process. We introduce novel constraints on positions into the mass-spring model (MSM) to model the nonlinearity and preserve volume for the realistic simulation of the incompressibility. We verify the proposed MSM by comparing its deformations with the reference deformations of the nonlinear finite-element method. Moreover, experiments on porcine organs are designed for the evaluation of the multiobject deformation. Using a pair of freshly harvested porcine liver and gallbladder, the real organ deformations are acquired by computed tomography and used as the reference ground truth. Compared to the porcine model, our model achieves a 1.502 mm mean absolute error measured at landmark locations for cases with small deformation (the largest deformation is 49.109 mm) and a 3.639 mm mean absolute error for cases with large deformation (the largest deformation is 83.137 mm). The changes of volume for the two deformations are limited to 0.030% and 0.057%, respectively. Finally, an implementation in a virtual reality environment for laparoscopic cholecystectomy demonstrates that our model is capable to simulate large deformation and preserve volume in real-time calculations.

Estimation of Soft Tissue Mechanical Parameters from Robotic Manipulation Data

Robotic motion planning algorithms used for task automation in robotic surgical systems rely on availability of accurate models of target soft tissue's deformation. Relying on generic tissue parameters in constructing the tissue deformation models is problematic because, biological tissues are known to have very large (inter- and intra-subject) variability. A priori mechanical characterization (e.g., uniaxial bench test) of the target tissues before a surgical procedure is also not usually practical. In this paper, a method for estimating mechanical parameters of soft tissue from sensory data collected during robotic surgical manipulation is presented. The method uses force data collected from a multiaxial force sensor mounted on the robotic manipulator, and tissue deformation data collected from a stereo camera system. The tissue parameters are then estimated using an inverse finite element method. The effects of measurement and modeling uncertainties on the proposed method are analyzed in simulation. The results of experimental evaluation of the method are also presented.

Energy Conservation for the Simulation of Deformable Bodies

We propose a novel technique that allows one to conserve energy using the time integration scheme of one's choice. Traditionally, the time integration methods that deal with energy conservation, such as symplectic, geometric, and variational integrators, have aimed to include damping in a manner independent of the size of the time step, stating that this gives more control over the look and feel of the simulation. Generally speaking, damping adds to the overall aesthetics and appeal of a numerical simulation, especially since it damps out the high frequency oscillations that occur on the level of the discretization mesh. We propose an alternative technique that allows one to use damping as a material parameter to obtain the desired look and feel of a numerical simulation, while still exactly conserving the total energy-in stark contrast to previous methods in which adding damping effects necessarily removes energy from the mesh. This allows, for example, a deformable bouncing ball with aesthetically pleasing damping (and even undergoing collision) to collide with the ground and return to its original height exactly conserving energy, as shown in Fig. 2. Furthermore, since our method works with any time integration scheme, the user can choose their favorite time integration method with regards to aesthetics and simply apply our method as a postprocess to conserve all or as much of the energy as desired.

Estimation of Soft Tissue Mechanical Parameters from Robotic Manipulation Data

Robotic motion planning algorithms used for task automation in robotic surgical systems rely on availability of accurate models of target soft tissue's deformation. Relying on generic tissue parameters in constructing the tissue deformation models is problematic; because, biological tissues are known to have very large (inter- and intra-subject) variability. A priori mechanical characterization (e.g., uniaxial bench test) of the target tissues before a surgical procedure is also not usually practical. In this paper, a method for estimating mechanical parameters of soft tissue from sensory data collected during robotic surgical manipulation is presented. The method uses force data collected from a multiaxial force sensor mounted on the robotic manipulator, and tissue deformation data collected from a stereo camera system. The tissue parameters are then estimated using an inverse finite element method. The effects of measurement and modeling uncertainties on the proposed method are analyzed in simulation. The results of experimental evaluation of the method are also presented.

Physics-based character skinning using multidomain subspace deformations

In this extended version of our Symposium on Computer Animation paper, we describe a domain-decomposition method to simulate articulated deformable characters entirely within a subspace framework. We have added a parallelization and eigendecomposition performance analysis, and several additional examples to the original symposium version. The method supports quasistatic and dynamic deformations, nonlinear kinematics and materials, and can achieve interactive time-stepping rates. To avoid artificial rigidity, or “locking,” associated with coupling low-rank domain models together with hard constraints, we employ penaltybased coupling forces. The multidomain subspace integrator can simulate deformations efficiently, and exploits efficient subspace-only evaluation of constraint forces between rotated domains using a novel Fast Sandwich Transform (FST). Examples are presented for articulated characters with quasistatic and dynamic deformations, and interactive performance with hundreds of fully coupled modes. Using our method, we have observed speedups of between 3 and 4 orders of magnitude over full-rank, unreduced simulations.

Maintaining large time steps in explicit finite element simulations using shape matching

We present a novel hybrid method to allow large time steps in explicit integrations for the simulation of deformable objects. In explicit integration schemes, the time step is typically limited by the size and the shape of the discretization elements as well as by the material parameters. We propose a two-step strategy to enable large time steps for meshes with elements potentially destabilizing the integration. First, the necessary time step for a stable computation is identified per element using modal analysis. This allows determining which elements have to be handled specially given a desired simulation time step. The identified critical elements are treated by a geometric deformation model, while the remaining ones are simulated with a standard deformation model (in our case, a corotational linear Finite Element Method). In order to achieve a valid deformation behavior, we propose a strategy to determine appropriate parameters for the geometric model. Our hybrid method allows taking much larger time steps than using an explicit Finite Element Method alone. The total computational costs per second are significantly lowered. The proposed scheme is especially useful for simulations requiring interactive mesh updates, such as for instance cutting in surgical simulations.

Surgical Retraction of Non-Uniform Deformable Layers of Tissue: 2D Robot Grasping and Path Planning

Robotic surgical assistants (RSAs) have the potential to facilitate surgeries and reduce human fatigue. In this paper we focus on surgical retraction, the common surgical primitive of grasping and lifting a thin layer of tissue to expose an underlying area. Given a 2D cross-sectional model of heterogeneous tissue with embedded structures (such as veins) and a desired underlying exposure region, we present an algorithm that computes a set of stable and secure grasp-and-retract trajectories, and runs a 3D finite element (FEM) simulation to certify the quality of each trajectory. To choose secure candidate grasp locations, we introduce the continuous spring method and combine it with the Deformation Space (D-Space) approach to grasping deformable objects with a linearized potential energy model based on the locations of embedded bodies. Experiments show that this method produces many of the same grasps as an exhaustive computation with an FEM mesh, but is orders of magnitude cheaper: our method runs in O(υ log υ) time, when υ is the number of veins, while the FEM computation takes O(pn 3) time, where n is the number of nodes in the FEM mesh and p is the number of nodes on its perimeter. Furthermore, we present a constant tissue curvature (CTC) retraction trajectory that distributes strain uniformly around the medial axis of the tissue, by moving the gripper such that the tissue follows a constant-curvature, constant-length arc. 3D FEM simulations show that the CTC achieves retractions with lower tissue strain than circular and linear trajectories. Overall, our algorithm computes and certifies a high-quality retraction in about one minute on a PC.

Robust high-resolution cloth using parallelism, history-based collisions, and accurate friction

In this paper we simulate high resolution cloth consisting of up to 2 million triangles which allows us to achieve highly detailed folds and wrinkles. Since the level of detail is also influenced by object collision and self collision, we propose a more accurate model for cloth-object friction. We also propose a robust history-based repulsion/collision framework where repulsions are treated accurately and efficiently on a per time step basis. Distributed memory parallelism is used for both time evolution and collisions and we specifically address Gauss-Seidel ordering of repulsion/collision response. This algorithm is demonstrated by several high resolution and high-fidelity simulations.

Triangular springs for modeling nonlinear membranes

This paper provides a formal connexion between springs and continuum mechanics in the context of one-dimensional and two-dimensional elasticity. In a first stage, the equivalence between tensile springs and the finite element discretization of stretching energy on planar curves is established. Furthermore, when considering a quadratic strain function of stretch, we introduce a new type of springs called tensile biquadratic springs. In a second stage, we extend this equivalence to non-linear membranes (St Venant-Kirchhoff materials) on triangular meshes leading to triangular biquadratic and quadratic springs. Those tensile and angular springs produce isotropic deformations parameterized by Young modulus and Poisson ratios on unstructured meshes in an efficient and simple way. For a specific choice of the Poisson ratio, 0.3, we show that regular spring-mass models may be used realistically to simulate a membrane behavior. Finally, the different spring formulations are tested in pure traction and cloth simulation experiments.

Melting and burning solids into liquids and gases

We propose a novel technique for melting and burning solid materials, including the simulation of the resulting liquid and gas. The solid is simulated with traditional mesh-based techniques (triangles or tetrahedra) which enable robust handling of both deformable and rigid objects, collision and self-collision, rolling, friction, stacking, etc. The subsequently created liquid or gas is simulated with modern grid-based techniques, including vorticity confinement and the particle level set method. The main advantage of our method is that state-of-the-art techniques are used for both the solid and the fluid without compromising simulation quality when coupling them together or converting one into the other. For example, we avoid modeling solids as Eulerian grid-based fluids with high viscosity or viscoelasticity, which would preclude the handling of thin shells, self-collision, rolling, etc. Thus, our method allows one to achieve new effects while still using their favorite algorithms (and implementations) for simulating both solids and fluids, whereas other coupling algorithms require major algorithm and implementation overhauls and still fail to produce rich coupling effects (e.g., melting and burning solids).

Realistic haptic rendering of interacting deformable objects in virtual environments

A new computer haptics algorithm to be used in general interactive manipulations of deformable virtual objects is presented. In multimodal interactive simulations, haptic feedback computation often comes from contact forces. Subsequently, the fidelity of haptic rendering depends significantly on contact space modeling. Contact and friction laws between deformable models are often simplified in up to date methods. They do not allow a "realistic" rendering of the subtleties of contact space physical phenomena (such as slip and stick effects due to friction or mechanical coupling between contacts). In this paper, we use Signorini's contact law and Coulomb's friction law as a computer haptics basis. Real-time performance is made possible thanks to a linearization of the behavior in the contact space, formulated as the so-called Delassus operator, and iteratively solved by a Gauss-Seidel type algorithm. Dynamic deformation uses corotational global formulation to obtain the Delassus operator in which the mass and stiffness ratio are dissociated from the simulation time step. This last point is crucial to keep stable haptic feedback. This global approach has been packaged, implemented, and tested. Stable and realistic 6D haptic feedback is demonstrated through a clipping task experiment.

Creating and simulating skeletal muscle from the visible human data set

Simulation of the musculoskeletal system has important applications in biomechanics, biomedical engineering, surgery simulation, and computer graphics. The accuracy of the muscle, bone, and tendon geometry as well as the accuracy of muscle and tendon dynamic deformation are of paramount importance in all these applications. We present a framework for extracting and simulating high resolution musculoskeletal geometry from the segmented visible human data set. We simulate 30 contact/collision coupled muscles in the upper limb and describe a computationally tractable implementation using an embedded mesh framework. Muscle geometry is embedded in a nonmanifold, connectivity preserving simulation mesh molded out of a lower resolution BCC lattice containing identical, well-shaped elements, leading to a relaxed time step restriction for stability and, thus, reduced computational cost. The muscles are endowed with a transversely isotropic, quasi-incompressible constitutive model that incorporates muscle fiber fields as well as passive and active components. The simulation takes advantage of a new robust finite element technique that handles both degenerate and inverted tetrahedra.