Danny Kaufman

Research Scientist
Creative Technologies Lab
Adobe Systems

danny.kaufman.cs at gmail.com

    The harmony of the world is made
    manifest in form and number...
                                                            D'arcy Thompson


Yunfei Bai, Danny M. Kaufman, C. Karen Liu, and Jovan Popović,
Artist-Directed Dynamics for 2D Animation, to appear ACM Transactions on Graphics (SIGGRAPH 2016), August 2016.

Aric Bartle, Alla Sheffer, Vladimir G. Kim, Danny M. Kaufman, Nicholas Vining, Floraine Berthouzoz,
Physics-driven Pattern Adjustment for Direct 3D Garment Editing, to appear ACM Transactions on Graphics (SIGGRAPH 2016), August 2016.

Fredrik Kjølstad, Shoaib Kamil, Jonathan Ragan-Kelley, David Levin, Shinjiro Sueda, Desai Chen, Etienne Vouga, Danny M. Kaufman, Gurtej Kanwar, Wojciech Matusik, Saman Amarasinghe,
Simit: a Language for Physical Simulation,
ACM Transactions on Graphics (to appear at SIGGRAPH 2016), April 2016.

Danny M. Kaufman, Rasmus Tamstorf, Breannan Smith, Jean-Marie Aubry, and Eitan Grinspun, Adaptive Nonlinearity for Collisions in Complex Rod Assemblies, ACM Transactions on Graphics (SIGGRAPH 2014), August 2014.

ABSTRACT:  We develop an algorithm for the efficient and stable simulation of large-scale elastic rod assemblies. We observe that the time-integration step is severely restricted by a strong nonlinearity in the response of stretching modes to transversal impact, the degree of this nonlinearity varying greatly with the shape of the rod. Building on these observations, we propose the ADONIS collision response algorithm that adapts the degree of nonlinearity in impact solves. We illustrate the advantages of the ADONIS algorithm by analyzing simulations involving elastic rod assemblies of varying density and scale, with up to 1.7 million individual contacts per time step.

Project Page

Floraine Berthouzoz, Akash Garg, Danny M. Kaufman, Eitan Grinspun, and Maneesh Agrawala, Parsing Sewing Patterns into 3D Garment Models, ACM Transactions on Graphics (SIGGRAPH 2013), July 2013.

ABSTRACT:  We present techniques for automatically parsing existing sewing patterns and converting them into 3D garment models. Our parser takes a sewing pattern in PDF format as input and starts by extracting the set of panels and styling elements (e.g. darts, pleats and hemlines) contained in the pattern. It then applies a combination of machine learning and integer programming to infer how the panels must be stitched together to form the garment. Our system includes an interactive garment simulator that takes the parsed result and generates the corresponding 3D model. Our fully automatic approach correctly parses 68% of the sewing patterns in our collection. Most of the remaining patterns contain only a few errors that can be quickly corrected within the garment simulator. Finally we present two applications that take advantage of our collection of parsed sewing patterns. Our garment hybrids application lets users smoothly interpolate multiple garments in the 2D space of patterns. Our sketch-based search application allows users to navigate the pattern collection by drawing the shape of panels.

Project Page

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

SC Breannan Smith, Danny M. Kaufman, Etienne Vouga,  Rasmus Tamstorf, and Eitan GrinspunReflections 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.

Project Page

SC Nobuyuki Umetani, Danny M. Kaufman, Takeo Igarashi, and Eitan GrinspunSensitive 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.

Project Page

Danny M. Kaufman, Coupled Principles For Computational Frictional Contact Mechanics, 2009, Dissertation.

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,  Shinjiro Sueda, Doug L. James, and Dinesh K. PaiStaggered 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.

Project Page

Danny M. Kaufman, Shinjiro Sueda, and Dinesh K. PaiContact Trees: Adaptive Contact Sampling for  Robust Dynamics, 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.

Technical Sketch

Danny M. Kaufman and Dinesh K. PaiRandomized 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.

Technical Report

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.

Project Page

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.