|Floraine Berthouzoz, Akash Garg, Danny M. Kaufman, Eitan Grinspun, and Maneesh Agrawala,
Parsing Sewing Patterns into 3D Garment Models, to appear ACM Transactions on Graphics (SIGGRAPH 2013), July 2013.
|Danny M. Kaufman and Dinesh K. Pai,
Geometric Numerical Integration of Inequality Constrained Nonsmooth
Hamiltonian Systems, SIAM Journal on Scientific Computing, 34(5), October 2012.
ABSTRACT: We consider the geometric numerical integration of Hamiltonian systems subject to both equality and "hard" inequality constraints. As in the standard geometric integration setting, we target long-term structure preservation. Additionally, however, we also consider invariant preservation over persistent, simultaneous, and/or frequent boundary interactions. Appropriately formulating geometric methods for these cases has long remained challenging due the inherent nonsmoothness and one-sided conditions that they impose. To resolve these issues we thus focus both on symplectic-momentum preserving behavior and the preservation of additional structures, unique to the inequality constrained setting. Toward these goals we introduce, for the first time, a fully nonsmooth, discrete Hamilton's principle and obtain an associated framework for composing geometric numerical integration methods for inequality-equality--constrained systems. Applying this framework, we formulate a new family of geometric numerical integration methods that, by construction, preserve momentum and equality constraints and are observed to retain good long-term energy behavior. Along with these standard geometric properties, the derived methods also enforce multiple simultaneous inequality constraints, obtain smooth unilateral motion along constraint boundaries, and allow for both nonsmooth and smooth boundary approach and exit trajectories. Numerical experiments are presented to illustrate the behavior of these methods on difficult test examples where both smooth and nonsmooth active constraint modes persist with high frequency.
Supplemental material: Structure Preserving Integration of Inequality Constrained Dynamics, Oberwolfach Report No. 16/2011
|Breannan Smith, Danny
M. Kaufman, Etienne Vouga,
Rasmus Tamstorf, and Eitan
Grinspun, Reflections on Simultaneous Impact, ACM Transactions
on Graphics (SIGGRAPH 2012), 31(4), August 2012.
ABSTRACT: Resolving simultaneous impacts is an open and significant problem in collision response modeling. Existing algorithms in this domain fail to fulfill at least one of five physical desiderata. To address this we present a simple generalized impact model motivated by both the successes and pitfalls of two popular approaches: pair-wise propagation and linear complementarity models. Our algorithm is the first to satisfy all identified desiderata, including simultaneously guaranteeing symmetry preservation, kinetic energy conservation, and allowing break-away. Furthermore, we address the associated problem of inelastic collapse, proposing a complementary generalized restitution model that eliminates this source of nontermination. We then consider the application of our models to the synchronous time-integration of large-scale assemblies of impacting rigid bodies. To enable such simulations we formulate a consistent frictional impact model that continues to satisfy the desiderata. Finally, we validate our proposed algorithm by correctly capturing the observed characteristics of physical experiments including the phenomenon of extended patterns in vertically oscillated granular materials.
M. Kaufman, Takeo
Igarashi, and Eitan
Grinspun, Sensitive Couture for
Interactive Garment Editing and Modeling, ACM Transactions
on Graphics (SIGGRAPH 2011), 30(4), August 2011.
ABSTRACT: We present a novel interactive tool for garment design that enables, for the first time, interactive bidirectional editing between 2D patterns and 3D high-fidelity simulated draped forms. This provides a continuous, interactive, and natural design modality in which 2D and 3D representations are simultaneously visible and seamlessly maintain correspondence. Artists can now interactively edit 2D pattern designs and immediately obtain stable accurate feedback online, thus enabling rapid prototyping and an intuitive understanding of complex drape form.
|Danny M. Kaufman, Coupled Principles For Computational Frictional Contact
ABSTRACT: Methods for simulating frictional contact response are in high demand in robotics, graphics, biomechanics, structural engineering, and many other fields where the accurate modeling of interactions between solids are required. While techniques for accurately simulating structures and continua have advanced rapidly, methods for simulating contact between solids have lagged behind. This thesis considers the difficulties encountered in designing robust, accurate, and efficient computational methods for simulating frictional contact dynamics. We focus on understanding the fundamental sources of difficulty in frictional contact modeling, elucidating existing structures that can be leveraged to minimize them, and designing robust, accurate and efficient algorithms to simulate challenging frictional contact problems. In this thesis a Coupled Principles formulation of discrete, time-continuous frictional contact is developed. This is then applied as the basis for deriving novel, time-discrete, variational integrators that pose the discrete frictional contact problem as a system of coupled minimizations. Solutions to these resulting systems are given by points that are simultaneously optimal for both minimizations and avoid some known issues present in existing variational integration approaches for frictional contact. We then consider a specific two-step variant of these variational schemes that generalizes the popular Stewart-Trinkle model for frictional contact simulation. This is taken as a starting point for investigating encountered sources of difficulties found in solving numerical problems posed by these models. We show that many existing algorithms, that have generally been presumed suitable for solving the resulting contact-related numerical optimization problems, fail entirely for many important examples of frictional contact, and then address these limitations with our Staggered Projections algorithm. Applying a fixed-point scheme, derived from the Coupled Principles Formulation, we show that Staggered Projections efficiently obtains accurate solutions to the optimizations problems for many frictional contact problems that were previously impractical to solve. Finally, we also offer convergence analysis of the Staggered Projections algorithm, as well as simulations and instrumented examples that capture frictional contact behaviors for both rigid and large deformation models.
|Danny M. Kaufman,
James, and Dinesh K. Pai, Staggered Projections for
Frictional Contact in Multibody Systems, ACM Transactions
on Graphics (SIGGRAPH Asia 2008), 27(5), December
2008, pp. 164:1-164:11.
ABSTRACT: We present a new discrete velocity-level formulation of frictional contact dynamics that reduces to a pair of coupled projections and introduce a simple fixed-point property of this coupled system. This allows us to construct a novel algorithm for accurate frictional contact resolution based on a simple staggered sequence of projections. The algorithm accelerates performance using warm starts to leverage the potentially high temporal coherence between contact states and provides users with direct control over frictional accuracy. Applying this algorithm to rigid and deformable systems, we obtain robust and accurate simulations of frictional contact behavior not previously possible, at rates suitable for interactive haptic simulations, as well as large-scale animations. By construction, the proposed algorithm guarantees exact, velocity-level contact constraint enforcement and obtains long-term stable and robust integration. Examples are given to illustrate the performance, plausibility and accuracy of the obtained solutions.
|Danny M. Kaufman,
and Dinesh K. Pai,
Contact Trees: Adaptive Contact Sampling for
Technical Sketches, SIGGRAPH 2007.
ABSTRACT: Algorithms for rigid body dynamics with contact are well known, but challenging to implement due to the interplay between large time steps, general purpose collision detection packages and pragmatic approximations of the underlying inequality constrained contact problems. While research on rigid body simulation has focused heavily both on contact resolution and collision detection, contact generation has largely been ignored. Most contact resolution algorithms presume that an ideal set of contacts, fully characterizing system constraints, are available, while collision detection methods generally presume that their task is finished once a set of intersecting primitives has been identified. Bridging the gap between these domains, by generating representative contact samples, contact point locations and their associated normals, is crucial for the accuracy, robustness and speed of simulation. We address these issues by developing an adaptive contact generation approach that tightly integrates hierarchical collision detection with the generation of well sampled contact constraints.
|Danny M. Kaufman and
Dinesh K. Pai,
Randomized Quadratic Programming with Applications to
Rigid Body Contact, Technical Report, UBC, 2006.
ABSTRACT: Motivated by applications in rigid body contact simulation we develop a numerically robust, randomized Quadratic Programming algorithm. We show that the resulting solver remains robust under highly constrained and redundant conditions, while also detecting infeasibility conditions. Its expected complexity is linear in the number constraints imposed and our experiments show that it performs well in practice for low-dimensional examples.
|Danny M. Kaufman, Timothy Edmunds and Dinesh K. Pai,
Fast Frictional Dynamics for Rigid Bodies, ACM Transactions on
Graphics (SIGGRAPH 2005), 24(3), August 2005, pp. 946-956.
ABSTRACT: We describe an efficient algorithm for the simulation of large sets of non-convex rigid bodies. The algorithm finds a simultaneous solution for a multi-body system that is linear in the total number of contacts detected in each iteration. We employ a novel contact model that uses mass, location, and velocity information from all contacts, at the moment of maximum compression, to constrain rigid body velocities. We also develop a new friction model in the configuration space of rigid bodies. These models are used to compute the feasible velocity and the frictional response of each body. Implementation is simple and leads to a fast rigid body simulator that computes steps on the order of seconds for simulations involving over one thousand non-convex objects in high contact configurations.
|Danny M. Kaufman and
Dinesh K. Pai,
Rapid Collision Dynamics for Multiple Contacts with
Friction, in Multi-Point Physical Interaction
with Real and Virtual Objects, Springer Tracts on
Advanced Robotics,18, Springer-Verlag, 2005, pp. 3-19.
ABSTRACT: We examine the interaction of complex two-dimensional rigid bodies with friction. Given their idealized description, many different feasible solutions for frictional contact and collision are possible. The usual assumptions of noninterpenetration and negligible deformation at the global scale constrain contact behaviors, while incomplete descriptions of material properties at the local scale allow for a large amount of latitude in solution methods. We propose a method that generalizes Moreau's impact law to formulate a simple but complete contact law in which both multiple constraints and multiple contacts are possible.