Danny Kaufman

Senior 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


Minchen Li, Danny M. Kaufman, Vladimir G. Kim, Justin Solomon, and Alla Sheffer
OptCuts: Joint Optimization of Surface Cuts and Parameterization,
to appear ACM Transactions on Graphics (SIGGRAPH Asia 2018).

ABSTRACT:  Low-distortion mapping of three-dimensional surfaces to the plane is a critical problem in geometry processing. The intrinsic distortion introduced by these UV mappings is highly dependent on the choice of surface cuts that form seamlines which break mapping continuity. Parameterization applications typically require UV maps with an application-specific upper bound on distortion to avoid mapping artifacts; at the same time they seek to reduce cut lengths to minimize discontinuity artifacts. We propose OptCuts, an algorithm that jointly optimizes the parameterization and cutting of a three-dimensional mesh. OptCuts starts from an arbitrary initial embedding and a user-requested distortion bound. It requires no parameter setting and automatically seeks to minimize seam lengths subject to satisfying the distortion bound of the mapping computed using these seams. OptCuts alternates between topology and geometry update steps that consistently decrease distortion and seam length, producing a UV map with compact boundaries that strictly satisfies the distortion bound. OptCuts automatically produces high-quality, globally bijective UV maps without user intervention. While OptCuts can thus be a highly effective tool to create new mappings from scratch, we also show how it can be employed to improve pre-existing embeddings. Additionally, when semantic or other priors on seam placement are desired, OptCuts can be extended to respect these user preferences as constraints during optimization of the parameterization. We demonstrate the scalable performance of OptCuts on a wide range of challenging benchmark parameterization examples, as well as in comparisons with state-of-the-art UV methods and commercial tools.

Project Page

Yufeng Zhu, Robert Bridson, and Danny M. Kaufman,
Blended Cured Quasi-Newton for Distortion Optimization,
ACM Transactions on Graphics (SIGGRAPH 2018).

ABSTRACT:  Optimizing distortion energies over a mesh, in two or three dimensions, is a common and critical problem in physical simulation and geometry processing. We present three new improvements to the state of the art: a barrier-aware line-search filter that cures blocked descent steps due to element barrier terms and so enables rapid progress; an energy proxy model that adaptively blends the Sobolev (inverse-Laplacian-processed) gradient and L-BFGS descent to gain the advantages of both, while avoiding L-BFGS's current limitations in distortion optimization tasks; and a characteristic gradient norm providing a robust and largely mesh- and energy-independent convergence criterion that avoids wrongful termination when algorithms temporarily slow their progress. Together these improvements form the basis for Blended Cured Quasi-Newton (BCQN), a new distortion optimization algorithm. Over a wide range of problems over all scales we show that BCQN is generally the fastest and most robust method available, making some previously intractable problems practical while offering up to an order of magnitude improvement in others.

Project Page

Michal Piovarci, David I.W. Levin, Danny M. Kaufman, and Piotr Didyk,
Perception-Aware Modeling and Fabrication of Digital Drawing Tools,
ACM Transactions on Graphics (SIGGRAPH 2018).

ABSTRACT:  Digital drawing is becoming a favorite technique for many artists. It allows for quick swaps between different materials, reverting changes, and applying selective modifications to finished artwork. These features enable artists to be more efficient and creative. A significant disadvantage of digital drawing is poor haptic feedback. Artists are usually limited to one surface and a few different stylus nibs, and while they try to find a combination that suits their needs, this is typically challenging. In this work, we address this problem and propose a method for designing, evaluating, and optimizing different stylus designs. We begin with collecting a representative set of traditional drawing tools. We measure their physical properties and conduct a user experiment to build a perceptual space that encodes perceptually-relevant attributes of drawing materials. The space is optimized to both explain our experimental data and correlate it with measurable physical properties. To embed new drawing tool designs into the space without conducting additional experiments and measurements, we propose a new, data-driven simulation technique for characterizing stylus-surface interaction.We finally leverage the perceptual space, our simulation, and recent advancements in multi-material 3D printing to demonstrate the application of our system in the design of new digital drawing tools that mimic traditional drawing materials.

Project Page

Yufeng Zhu, Jovan Popović, Robert Bridson, and Danny M. Kaufman,
Planar Interpolation with Extreme Deformation, Topology Change and Dynamics,
ACM Transactions on Graphics (SIGGRAPH Asia 2017), November 2017.

ABSTRACT:  We present a mesh-based, interpolatory method for interactively creating artist-directed inbetweens from arbitrary sets of 2D drawing shapes without rigging. To enable artistic freedom of expression we remove prior restrictions on the range of possible changes between shapes; we support interpolation with extreme deformation and unrestricted topology change. To do this, we extend discrete variational interpolation by introducing a consistent multimesh structure over drawings, a Comesh Optimization algorithm that optimizes our multimesh for both intra- and inter-mesh quality, and a new shape-space energy that efficiently supports arbitrary changes and can prevent artwork overlap when desired. Our multimesh encodes specified correspondences that guide interpolation paths between shapes. With these correspondences, an efficient local-global minimization of our energy interpolates n-way between drawing shapes to create inbetweens. Our Comesh Optimization enables artifact-free minimization by building consistent meshes across drawings that improve both the quality of per-mesh energy discretization and inter-mesh mapping distortions, while guaranteeing a single, compatible triangulation. We implement our method in a test-bed interpolation system that allows interactive creation and editing of animations from sparse key drawings with arbitrary topology and shape change.

Project Page

Desai Chen, David I.W. Levin, Wojciech Matusik, and Danny M. Kaufman,
Dynamics-Aware Numerical Coarsening For Fabrication Design,
ACM Transactions on Graphics (SIGGRAPH 2017), July 2017.

ABSTRACT:  The realistic simulation of highly-dynamic elastic objects is important for a broad range of applications in computer graphics, engineering and computational fabrication. However, whether simulating flipping toys, jumping robots, prosthetics or quickly moving creatures, performing such simulations in the presence of contact, impact and friction is both time consuming and inaccurate. In this paper we present Dynamics-Aware Coarsening (DAC) and the Boundary Balanced Impact (BBI) model which allow for the accurate simulation of dynamic, elastic objects undergoing both large scale deformation and frictional contact, at rates up to 79 times faster than state-of-the-art methods. DAC and BBI produce simulations that are accurate and fast enough to be used (for the first time) for the computational design of 3D-printable compliant dynamic mechanisms. Thus we demonstrate the efficacy of DAC and BBI by designing and fabricating mechanisms which flip, throw and jump over and onto obstacles as requested.

Project Page

Etienne Vouga, Breannan Smith, Danny M. Kaufman, Rasmus Tamstorf, and Eitan Grinspun,
All's Well That Ends Well: Guaranteed Resolution of Simultaneous Rigid-Body Impact,
ACM Transactions on Graphics (SIGGRAPH 2017), July 2017.

ABSTRACT:  Iterative algorithms are frequently used to resolve simultaneous impacts between rigid bodies in physical simulations. However, these algorithms lack formal guarantees of termination, which is sometimes viewed as potentially dangerous, so failsafes are used in practical codes to prevent infinite loops. We show such steps are unnecessary. In particular, we study the broad class of such algorithms that are conservative and satisfy a minimal set of physical correctness properties, and which encompasses recent methods like Generalized Reflections as well as pairwise schemes. We fully characterize finite termination of these algorithms. The only possible failure cases can be detected, and we describe a procedure for modifying the algorithms to provably ensure termination. We also describe modifications necessary to guarantee termination in the presence of numerical error due to the use of floating-point arithmetic. Finally, we discuss the challenges dissipation introduce for finite termination, and describe how dissipation models can be incorporated while retaining the termination guarantee.

Project Page

JiaXian Yao, Danny M. Kaufman, Yotam Gingold, and Maneesh Agrawala,
Interactive Design and Stability Analysis of Decorative Joinery for Furniture,
ACM Transactions on Graphics (presented at SIGGRAPH 2017), March 2017.

ABSTRACT:  High-quality hand-made furniture often employs intrinsic joints that geometrically interlock along mating surfaces. Such joints increase the structural integrity of the furniture and add to its visual appeal. We present an interactive tool for designing such intrinsic joints. Users draw the visual appearance of the joints on the surface of an input furniture model as groups of 2D regions that must belong to the same part. Our tool automatically partitions the furniture model into a set of solid 3D parts that conform to the user-specified 2D regions and assemble into the furniture. If the input does not merit assemblable solid 3D parts, our tool reports the failure and suggests options for redesigning the 2D surface regions so that they are assemblable. Similarly, if any parts in the resulting assembly are unstable, our tool suggests where additional 2D regions should be drawn to better interlock the parts and improve stability. To perform this stability analysis, we introduce a novel variational static analysis method that addresses shortcomings of the equilibrium method for our task. Specifically, our method correctly detects sliding instabilities and reports the locations and directions of sliding and hinging failures. We show that our tool can be used to generate over 100 joints inspired by traditional woodworking and Japanese joinery. We also design and fabricate 9 complete furniture assemblies that are stable and connected using only the intrinsic joints produced by our tool.

Project Page

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

ABSTRACT:  Animation artists enjoy the benefits of simulation but do not want to be held back by its constraints. Artist-directed dynamics seeks to resolve this need with a unified method that combines simulation with classical keyframing techniques. The combination of these approaches improves upon both extremes: simulation becomes more customizable and keyframing becomes more automatic. Examining our system in the context of the twelve fundamental animation principles reveals that it stands out for its treatment of exaggeration and appeal. Our system accommodates abrupt jumps, large plastic deformations, and makes it easy to reuse carefully crafted animations.

Project Page

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

ABSTRACT:  Designers frequently reuse existing designs as a starting point for creating new garments. In order to apply garment modifications, which the designer envisions in 3D, existing tools require meticulous manual editing of 2D patterns. These 2D edits need to account both for the envisioned geometric changes in the 3D shape, as well as for various physical factors that affect the look of the draped garment. We propose a new framework that allows designers to directly apply the changes they envision in 3D space; and creates the 2D patterns that replicate this envisioned target geometry when lifted into 3D via a physical draping simulation. Our framework removes the need for laborious and knowledge-intensive manual 2D edits and allows users to effortlessly mix existing garment designs as well as adjust for garment length and fit. Following each user specified editing operation we first compute a target 3D garment shape, one that maximally preserves the input garment's style - its proportions, fit and shape - subject to the modifications specified by the user. We then automatically compute 2D patterns that recreate the target garment shape when draped around the input mannequin within a user-selected simulation environment. To generate these patterns, we propose a fixed-point optimization scheme that compensates for the deformation due to the physical forces affecting the drape and is independent of the underlying simulation tool used. Our experiments show that this method quickly and reliably converges to patterns that, under simulation, form the desired target look, and works well with different black-box physical simulators. We demonstrate a range of edited and resimulated garments, and further validate our approach via expert and amateur critique, and comparisons to alternative solutions.

Project Page

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

ABSTRACT:  With existing programming tools, writing high-performance simulation code is labor intensive and requires sacrificing readability and portability. The alternative is to prototype simulations in a high-level language like Matlab, thereby sacrificing performance. The Matlab programming model naturally describes the behavior of an entire physical system using the language of linear algebra. However, simulations also manipulate individual geometric elements, which are best represented using linked data structures like meshes. Translating between the linked data structures and linear algebra comes at significant cost, both to the programmer and to the machine. High-performance implementations avoid the cost by rephrasing the computation in terms of linked or index data structures, leaving the code complicated and monolithic, often increasing its size by an order of magnitude. In this article, we present Simit, a new language for physical simulations that lets the programmer view the system both as a linked data structure in the form of a hypergraph and as a set of global vectors, matrices, and tensors depending on what is convenient at any given time. Simit provides a novel assembly construct that makes it conceptually easy and computationally efficient to move between the two abstractions. Using the information provided by the assembly construct, the compiler generates efficient in-place computation on the graph. We demonstrate that Simit is easy to use: a Simit program is typically shorter than a Matlab program; that it is high performance: a Simit program running sequentially on a CPU performs comparably to hand-optimized simulations; and that it is portable: Simit programs can be compiled for GPUs with no change to the program, delivering 4 to 20X speedups over our optimized CPU code.

Project Page

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.