 Speculative Parallel Asynchronous Contact Mechanics Samantha Ainsley, Etienne Vouga, Eitan Grinspun, and Rasmus Tamstorf, ACM Transactions on Graphics (SIGGRAPH Asia), pp.8, 2012.
Abstract: We extend the Asynchronous Contact Mechanics algorithm and improve its performance by two orders of magnitude, using only optimizations that do not compromise ACM’s three guarantees of safety, progress, and correctness. The key to this speedup is replacing ACM’s timid, forwardlooking mechanism for detecting collisions—locating and rescheduling separating plane kinetic data structures—with an optimistic speculative method inspired by Mirtich’s rigid body Time Warp algorithm [2000]. Time warp allows us to perform collision detection over a window of time containing many of ACM’s asynchronous trajectory changes; in this way we cull away large intervals as being collision free. Moreover, by replacing force processing intermingled with KDS rescheduling by windows of pure processing followed by collision detection, we tranform an algorithm that is very difficult to parallelize into one that is embarrassingly parallel. [PDF] [bib] [Project] [Video]   Asynchronous Contact Mechanics (CACM Research Highlights) David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, and Eitan Grinspun, Communications of the ACM, pp.102109, 2012. [PDF] [bib]   Technical Perspective: Building Robust Dynamical Simulation Systems Dinesh Manocha, Communications of the ACM, pp.101, 2012. [PDF] [bib]   Reflections on Simultaneous Impact Breannan Smith, Danny M. Kaufman, Etienne Vouga, Rasmus Tamstorf, Eitan Grinspun, SIGGRAPH ( ACM Transactions on Graphics), pp.106:1106:12, 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: pairwise 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 breakaway. 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 timeintegration of largescale 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.
[PDF] [bib] [Project] [Video]   Interactive Editing of Deformable Simulations Jernej Barbič, Fun Shing Sin, Eitan Grinspun, SIGGRAPH, 2012.
Abstract: We present an interactive animation editor for complex deformable object animations. Given an existing animation, the artist directly manipulates the deformable body at any time frame, and the sur rounding animation immediately adjusts in response. The auto matic adjustments are designed to respect physics, preserve detail in both the input motion and geometry, respect prescribed bilateral contact constraints, and controllably and smoothly decay in space time. While the utility of interactive editing for rigid body and ar ticulated figure animations is widely recognized, a corresponding approach to deformable bodies has not been technically feasible be fore. We achieve interactive rates by combining spacetime model reduction, rotationstrain coordinate warping, linearized elasticity, and direct manipulation. This direct editing tool can serve the final stages of animation production, which often call for detailed, direct adjustments that are otherwise tedious to realize by resimulation or framebyframe editing. [PDF] [bib] [Project] [Video]   Discrete Viscous Sheets Christopher Batty, Andres Uribe, Basile Audoly, Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), pp.113:1113:7, 2012.
Abstract: We present the first reduceddimensional technique to simulate the dynamics of thin sheets of viscous incompressible liquid in three dimensions. Beginning from a discrete Lagrangian model for elastic thin shells, we apply the StokesRayleigh analogy to derive a simple yet consistent model for viscous forces. We incorporate nonlinear surface tension forces with a formulation based on minimizing discrete surface area, and preserve the quality of triangular mesh elements through local remeshing operations. Simultaneously, we track and evolve the thickness of each triangle to exactly conserve liquid volume. This approach enables the simulation of extremely thin sheets of viscous liquids, which are difficult to animate with existing volumetric approaches. We demonstrate our method with examples of several characteristic viscous sheet behaviors, including stretching, buckling, sagging, and wrinkling. [PDF] [bib] [Project] [Video]   Diamonds From the Rough: Improving Drawing, Painting, and Singing via Crowdsourcing Yotam Gingold, Etienne Vouga, Eitan Grinspun, Haym Hirsh, Human Computation Workshop (HCOMP), 2012.
Abstract: It is well established that in certain domains, noisy inputs can be reliably combined to obtain a better answer than any individual. It is now possible to consider the crowdsourcing of physical actions, commonly used for creative expressions such as drawing, shading, and singing. We provide algorithms for converting lowquality input obtained from the physical actions of a crowd into highquality output. The inputs take the form of line drawings, shaded images, and songs. We investigate singleindividual crowds (multiple inputs from a single human) and multipleindividual crowds. [PDF] [bib] [Project]   Asynchronous Variational Contact Mechanics E. Vouga, D. Harmon, R. Tamstorf, and E. Grinspun, Computer Methods in Applied Mechanics and Engineering, pp.21812194, 2011.
Abstract: An asynchronous, variational method for simulating elastica in complex contact and impact scenarios is developed. Asynchronous Variational Integrators (AVIs) are extended to handle contact forces by associating different time steps to forces instead of to spatial elements. By discretizing a barrier potential by an infinite sum of nested quadratic potentials, these extended AVIs are used to resolve contact while obeying momentum and energyconservation laws. A series of two and threedimensional examples illustrate the robustness and good energy behavior of the method. [PDF] [bib] [Project]   ExampleBased Elastic Materials S. Martin, B. Thomaszewski, E. Grinspun, M. Gross, SIGGRAPH (ACM Transactions on Graphics), pp.72:172:8, 2011.
Abstract: We propose an examplebased approach for simulating complex elastic material behavior. Supplied with a few poses that characterize a given object, our system starts by constructing a space of prefered deformations by means of interpolation. During simulation, this example manifold then acts as an additional elastic attractor that guides the object towards its space of prefered shapes. Added on top of existing solid simulation codes, this example potential effectively allows us to implement inhomogeneous and anisotropic materials in a direct and intuitive way. Due to its examplebased interface, our method promotes an artdirected approach to solid simulation, which we exemplify on a set of practical examples.
[PDF] [bib] [Project] [Video]   Sensitive Couture for Interactive Garment Editing and Modeling Nobuyuki Umetani, Danny M. Kaufman, Takeo Igarashi, Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), 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 highfidelity 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 pat tern designs and immediately obtain stable accurate feedback on line, thus enabling rapid prototyping and an intuitive understanding of complex drape form. [PDF] [bib] [Project] [Video]   Discrete Viscous Threads Miklós Bergou, Basile Audoly, Etienne Vouga, Max Wardetzky, Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), 2010.
Abstract: We present a continuumbased discrete model for thin threads of viscous fluid based on the Rayleigh analogy to elastic rods, demonstrating canonical coiling, folding, and breakup in dynamic simulations. Our derivation emphasizes spacetime symmetry, which ultimately sheds light on the role of timeparallel transport in eliminating—without approximation—all but an O(n) band of entries of the physical system’s force Jacobian. The result is a fast, unified, implicit treatment of viscous threads and elastic rods that closely reproduces a variety of fascinating physical phenomena, including hysteretic transitions between coiling regimes, competition between surface tension and gravity, and the first numerical fluidmechanical sewing machine. The novel implicit treatment also yields an order of magnitude speedup in our elastic rod dynamics. [PDF] [bib] [Project] [Video]   Unified Simulation of Elastic Rods, Shells, and Solids Sebastian Martin, Peter Kaufmann, Mario Botsch, Eitan Grinspun, Markus Gross, SIGGRAPH (ACM Transactions on Graphics), 2010.
Abstract: We develop an accurate, unified treatment of elastica. Following the method of resultantbased formulation to its logical extreme, we derive a higherorder integration rule, or elaston, measuring stretching, shearing, bending, and twisting along any axis. The theory and accompanying implementation do not distinguish between forms of different dimension (solids, shells, rods), nor between manifold regions and nonmanifold junctions. Consequently, a single code accurately models a diverse range of elastoplastic behaviors, including buckling, writhing, cutting and merging. Emphasis on convergence to the continuum sets us apart from early unification efforts. [PDF] [bib] [Video]   Synthesizing Structured Image Hybrids Eric Risser, Charles Han, Rozenn Dahyot, Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), 2010.
Abstract: Examplebased texture synthesis algorithms generate novel texture images from example data. A popular hierarchical pixelbased approach uses spatial jitter to introduce diversity, at the risk of breaking coarse structure beyond repair. We propose a multiscale descriptor that enables appearancespace jitter, which retains structure. This idea enables repurposing of existing texture synthesis implementations for a qualitatively different problem statement and class of inputs: generating hybrids of structured images. [PDF] [bib] [Project]   Higherorder extended finite elements with harmonic enrichment functions for complex crack problems S. E. Mousavi, E. Grinspun, N. Sukumar, International Journal for Numerical Methods in Engineering, pp.560574, 2010.
Abstract: We analyze complex crack problems in elastic media using harmonic enrichment functions in a higherorder extended finite element implementation. The numerically computed enrichment function of a crack is the solution of the Laplace equation with discontinuous Dirichlet boundary condition along the crack, and its interaction with branches or other cracks is realized by imposing vanishing Neumann boundary conditions along those cracks. The classical finite element displacement approximation is enriched by adding the enrichment function of a crack through the framework of partition of unity. A nested subgrid mesh is used in the Laplace solve with a rasterized approximation of a crack, which simplifies the numerical integration—no partitioning of finite elements is required. Harmonic enrichment functions readily permit the extension to handle multiple interacting and branched cracks without any special treatment around the junction points. Several numerical examples are presented that affirm the accuracy and effectiveness of the method when applied to complex crack configurations under mixedmode loading conditions. [PDF] [bib]   Harmonic enrichment functions: A unified treatment of multiple, intersecting and branched cracks in the extended finite element method S. E. Mousavi, E. Grinspun, N. Sukumar, International Journal for Numerical Methods in Engineering, pp.13061322, 2010.
Abstract: A unifying procedure to numerically compute enrichment functions for elastic fracture problems with the extended finite element method is presented. Within each element that is intersected by a crack, the enrichment function for the crack is obtained via the solution of the Laplace equation with Dirichlet and vanishing Neumann boundary conditions. A single algorithm emanates for the enrichment field for multiple cracks as well as intersecting and branched cracks, without recourse to special cases, which provides flexibility over existing approaches in which each case is treated separately. Numerical integration is rendered to be simple—there is no need for partitioning of the finite elements into conforming subdivisions for the integration of discontinuous or weakly singular kernels. Stress intensity factor computations for different crack configurations are presented to demonstrate the accuracy and versatility of the proposed technique. [PDF] [bib]   Asynchronous Contact Mechanics David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), 2009.
Abstract: We develop a method for reliable simulation of elastica in complex contact scenarios. Our focus is on firmly establishing three parameterindependent guarantees: that simulations of wellposed problems (a) have no interpenetrations, (b) obey causality, momentum and energyconservation laws, and (c) complete in finite time. We achieve these guarantees through a novel synthesis of asynchronous variational integrators, kinetic data structures, and a discretization of the contact barrier potential by an infinite sum of nested quadratic potentials. In a series of two and three dimensional examples, we illustrate that this method more easily handles challenging problems involving complex contact geometries, sharp features, and sliding during extremely tight contact. [PDF] [bib] [Project] [Video]   Enrichment Textures for Detailed Cutting of Shells Peter Kaufmann, Sebastian Martin, Mario Botsch, Eitan Grinspun, Markus Gross, SIGGRAPH (ACM Transactions on Graphics), 2009.
Abstract: We present a method for simulating highly detailed cutting and fracturing of thin shells using lowresolution simulation meshes. Instead of refining or remeshing the underlying simulation domain to resolve complex cut paths, we adapt the extended finite element method (XFEM) and enrich our approximation by custom designed basis functions, while keeping the simulation mesh unchanged. The enrichment functions are stored in enrichment textures, which allows for fracture and cutting discontinuities at a resolution much finer than the underlying mesh, similar to image textures for increased visual resolution. Furthermore, we propose harmonic enrichment functions to handle multiple, intersecting, arbitrarily shaped, progressive cuts per element in a simple and unified framework. Our underlying shell simulation is based on discontinuous Galerkin (DG) FEM, which relaxes the restrictive requirement of C^{1} continuous basis functions and thus allows for simpler, C^{0} continuous XFEM enrichment functions. [PDF] [bib] [Video]   Semantic Deformation Transfer Ilya Baran, Daniel Vlasic, Eitan Grinspun, Jovan Popovic, SIGGRAPH (ACM Transactions on Graphics), 2009.
Abstract: Transferring existing mesh deformation from one character to another is a simple way to accelerate the laborious process of mesh animation. In many cases, it is useful to preserve the semantic characteristics of the motion instead of its literal deformation. For example, when applying the walking motion of a human to a flamingo, the knees should bend in the opposite direction. Semantic deformation transfer accomplishes this task with a shape space that enables interpolation and projection with standard linear algebra. Given several example mesh pairs, semantic deformation transfer infers a correspondence between the shape spaces of the two characters. This enables automatic transfer of new poses and animations. [PDF] [bib] [Video]   ImplicitExplicit Variational Integration of Highly Oscillatory Problems Ari Stern, Eitan Grinspun, SIAM Multiscale Modeling and Simulation, pp.17791794, 2009.
Abstract: We derive a variational integrator for certain highly oscillatory problems in mechanics. To do this, we take a new approach to the splitting of fast and slow potential forces: rather than splitting these forces at the level of the diﬀerential equations or the Hamiltonian, we split the two potentials with respect to the Lagrangian action integral. By using a diﬀerent quadrature rule
to approximate the contribution of each potential to the action, we arrive at a geometric integrator that is implicit in the fast force and explicit in the slow force. This can allow for signiﬁcantly longer time steps to be taken (compared to standard explicit methods, such as Störmer/Verlet) at the cost of only a linear solve rather than a full nonlinear solve. We also analyze the stability of this method, in particular proving that it eliminates the linear resonance instabilities that can arise with explicit multipletimestepping methods. Next, we perform some numerical experiments, studying the behavior of this integrator for two test problems: a system of coupled linear oscillators, for which we compare against the resonance behavior of the rRESPA method; and slow energy exchange in the Fermi–Pasta–Ulam problem, which couples fast linear oscillators with slow nonlinear oscillators. Finally, we prove that this integrator accurately preserves the slow energy exchange between the fast oscillatory components, which explains the numerical behavior observed for the Fermi–Pasta–Ulam problem.
[PDF] [bib]   Discrete Elastic Rods Miklós Bergou, Max Wardetzky, Stephen Robinson, Basile Audoly, Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), pp.112, 2008.
Abstract: We present a discrete treatment of adapted framed curves, parallel transport, and holonomy, thus establishing the language for a discrete geometric model of thin flexible rods with arbitrary cross section and undeformed configuration. Our approach differs from existing simulation techniques in the graphics and mechanics literature both in the kinematic description — we represent the material frame by its angular deviation from the natural Bishop frame — as well as in the dynamical treatment — we treat the centerline as dynamic and the material frame as quasistatic. Additionally, we describe a manifold projection method for coupling rods to rigidbodies and simultaneously enforcing rod inextensibility. The use of quasistatics and constraints provides an efficient treatment for stiff twisting and stretching modes; at the same time, we retain the dynamic bending of the centerline and accurately reproduce the coupling between bending and twisting modes. We validate the discrete rod model via quantitative buckling, stability, and coupledmode experiments, and via qualitative knottying comparisons. [PDF] [bib] [Project] [Video]   Multiscale Texture Synthesis Charles Han, Eric Risser, Ravi Ramamoorthi, Eitan Grinspun, SIGGRAPH ( ACM Transactions on Graphics), pp.51, 2008.
Abstract: Examplebased texture synthesis algorithms have gained widespread popularity for their ability to take a single input image and create a perceptually similar nonperiodic texture. However, previous methods rely on single input exemplars that can capture only a limited band of spatial scales. For example, synthesizing a continentlike appearance at a variety of zoom levels would require an impractically high input resolution. In this paper, we develop a multiscale texture synthesis algorithm. We propose a novel examplebased representation, which we call an exemplar graph, that simply requires a few lowresolution input exemplars at different scales. Moreover, by allowing loops in the graph, we can create inﬁnite zooms and inﬁnitely detailed textures that are impossible with current examplebased methods. We also introduce a technique that ameliorates inconsistencies in the user’s input, and show that the application of this method yields improved interscale coherence and higher visual quality. We demonstrate optimizations for both CPU and GPU implementations of our method, and use them to produce animations with zooming and panning at multiple scales, as well as static gigapixelsized images with features spanning many spatial scales. [PDF] [bib] [Project] [Video]   Robust Treatment of Simultaneous Collisions David Harmon, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), pp.14, 2008.
Abstract: Robust treatment of complex collisions is a challenging problem in cloth simulation. Some state of the art methods resolve collisions iteratively, invoking a failsafe when a bound on iteration count is exceeded. The bestknown failsafe rigidifies the contact region, causing simulation artifacts. We present a failsafe that cancels impact but not sliding motion, considerably reducing artificial dissipation. We equip the proposed failsafe with an approximation of Coulomb friction, allowing finer control of sliding dissipation. [PDF] [bib] [Project] [Video]   Discrete Laplace operators: No free lunch Max Wardetzky, Saurabh Mathur, Felix Kälberer and Eitan Grinspun, Symposium on Geometry Processing, pp.3337, 2007.
Abstract: Discrete Laplace operators are ubiquitous in applications spanning geometric modeling to simulation. For robustness and efficiency, many applications require discrete operators that retain key structural properties inherent to the continuous setting. Building on the smooth setting, we present a set of natural properties for discrete Laplace operators for triangular surface meshes. We prove an important theoretical limitation: discrete Laplacians cannot satisfy all natural properties; retroactively, this explains the diversity of existing discrete Laplace operators. Finally, we present a family of operators that includes and extends wellknown and widelyused operators. [PDF] [bib]   Compressive Structured Light for Recovering Inhomogeneous Participating Media Jinwei Gu, Shree Nayar, Eitan Grinspun, Peter Belhumeur, Ravi Ramamoorthi, Europian Conference on Computer Vision (ECCV), 2008.
Abstract: We propose a new method named compressive structured light for recovering inhomogeneous participating media. Whereas conventional structured light methods emit coded light patterns onto the surface of an opaque object to establish correspondence for triangulation, compressive structured light projects patterns into a volume of participating medium to produce images which are integral measurements of the volume density along the line of sight. For a typical participating medium encountered in the real world, the integral nature of the acquired images enables the use of compressive sensing techniques that can recover the entire volume density from only a few measurements. This makes the acquisition process more efficient and enables reconstruction of dynamic volumetric phenomena. Moreover, our method requires the projection of multiplexed coded illumination, which has the added advantage of increasing the signaltonoise ratio of the acquisition. Finally, we propose an iterative algorithm to correct for the attenuation of the participating medium during the reconstruction process. We show the eﬀectiveness of our method with simulations as well as experiments on the volumetric recovery of multiple translucent layers, 3D point clouds etched in glass, and the dynamic process of milk drops dissolving in water.
[PDF] [bib] [Project]   TRACKS: Toward Directable Thin Shells Miklós Bergou, Saurabh Mathur, Max Wardetzky, and Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), pp.50, 2007.
Abstract: We combine the often opposing forces of artistic freedom and mathematical
determinism to enrich a given animation or simulation of a surface with physically based detail. We present a process called tracking, which takes as input a rough animation or simulation and enhances it with physically simulated detail. Building on the foundation of constrained Lagrangian mechanics, we propose weakform constraints for tracking the input motion. This method allows the artist to choose where to add details such as characteristic wrinkles and folds of various thin shell materials and dynamical effects of physical forces. We demonstrate multiple applications
ranging from enhancing an artist’s animated character to guiding a simulated inanimate object. [PDF] [bib] [Project] [Video]   Efficient Simulation of Inextensible Cloth Rony Goldenthal, David Harmon, Raanan Fattal, Michel Bercovier, Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), 2007.
Abstract: Many textiles do not noticeably stretch under their own weight. Unfortunately, for better performance many cloth solvers disregard this fact. We propose a method to obtain very low strain along the warp and weft direction using Constrained Lagrangian Mechanics and a novel fast projection method. The resulting algorithm acts as a velocity filter that easily integrates into existing simulation code. [PDF] [bib] [Project] [Video]   Frequency Domain Normal Map Filtering Charles Han, Bo Sun, Ravi Ramamoorthi, and Eitan Grinspun, SIGGRAPH (ACM Transactions on Graphics), pp.28, 2007.
Abstract: Filtering is critical for representing imagebased detail, such as textures or normal maps, across a variety of scales. While mipmapping textures is commonplace, accurate normal map filtering remains a challenging problem because of nonlinearities in shading¡ªwe cannot simply average nearby surface normals. In this paper, we show analytically that normal map filtering can be formalized as a spherical convolution of the normal distribution function (NDF) and the BRDF, for a large class of common BRDFs such as Lambertian, microfacet and factored measurements. This theoretical result explains many previous filtering techniques as special cases, and leads to a generalization to a broader class of measured and analytic BRDFs. Our practical algorithms leverage a significant body of previous work that has studied lightingBRDF convolution. We show how spherical harmonics can be used to filter the NDF for Lambertian and lowfrequency specular BRDFs, while spherical von MisesFisher distributions can be used for highfrequency materials. [PDF] [bib] [Project] [Video]   Cubic Shells Akash Garg, Eitan Grinspun, Max Wardetzky, Denis Zorin, Symposium on Computer Animation, pp.9198, 2007.
Abstract: Hingebased bending models are widely used in the physicallybased animation of cloth, thin plates and shells. We propose a hingebased model that is simpler to implement, more efficient to compute, and offers a greater number of effective material parameters than existing models. Our formulation builds on two mathematical observations: (a) the bending energy of curved flexible surfaces can be expressed as a cubic polynomial if the surface does not stretch; (b) a general class of anisotropic materials—those that are orthotropic—is captured by appropriate choice of a single stiffness per hinge. Our contribution impacts a general range of surface animation applications, from isotropic cloth and thin plates to orthotropic fracturing thin shells. [PDF] [bib] [Video]   Discrete Quadratic Curvature Energies [CAGD Most Cited Paper Award for 2010] Max Wardetzky, Miklós Bergou, David Harmon, Denis Zorin, and Eitan Grinspun, Computer Aided Geometric Design, pp.499518, 2007.
Abstract: [This is preprintnot a final copy.] We present a family of discrete isometric bending models (IBMs) for triangulated surfaces in 3space. These models are derived from an axiomatic treatment of discrete Laplace operators, using these operators to obtain linear models for discrete mean curvature from which bending energies are assembled. Under the assumption of isometric surface deformations we show that these energies are quadratic in surface positions. The corresponding linear energy gradients and constant energy Hessians constitute an efficient model for computing bending forces and their derivatives, enabling fast timeintegration of cloth dynamics with a two to threefold net speedup over existing nonlinear methods, and nearinteractive rates for Willmore smoothing of large meshes.
[PDF] [bib] [Project] [Video]   Computing discrete shape operators on general meshes [Eurographics 2006 Best Paper, 3rd Place] Eitan Grinspun, Yotam Gingold, Jason Reisman, Denis Zorin, Eurographics (Computer Graphics Forum), pp.547556, 2006.
Abstract: Discrete curvature and shape operators, which capture complete information about directional curvatures at a point, are essential in a variety of applications: simulation of deformable twodimensional objects, variational modeling and geometric data processing. In many of these applications, objects are represented by meshes. Currently, a spectrum of approaches for formulating curvature operators for meshes exists, ranging from highly accurate but computationally expensive methods used in engineering applications to efficient but less accurate techniques popular in simulation for computer graphics. We propose a simple and efficient formulation for the shape operator for variational problems on general meshes, using degrees of freedom associated with normals. On the one hand, it is similar in its simplicity to some of the discrete curvature operators commonly used in graphics; on the other hand, it passes a number of important convergence tests and produces consistent results for different types of meshes and mesh refinement.
[PDF] [bib] 

Addendum:
The associated addendum, below, describes a shape operator discretization based on trianglecentered quadratic interpolation.

 A note on the trianglecentered quadratic interpolation discretization of the shape operator Jason Reisman, Eitan Grinspun, Denis Zorin, Technical Report, Department of Computer Science, Columbia University and New York University, 2007.
Abstract: In this note we consider a simple shape operator discretization for general meshes, based on computing an interpolating quadratic function passing through vertices of a triangle and its edgeadjacent neighbors. This approximation is computationally simple and consistent for a broad class of meshes. However, its convergence properties in the context of mesh optimization problems are not as good as some of the previously proposed techniques and it suffers from instabilities for certain point configurations.
[PDF] [bib]   SimX: Parallel System Software for Interactive MultiExperiment Computational Studies SiuMan Yau, Eitan Grinspun, Vijay Karamcheti, and Denis Zorin, International Parallel & Distributed Processing Symposium, 2006.
Abstract: Advances in highperformance computing have led to the broad use of computational studies in everyday engineering and scientific applications. A single study may require thousands of computational experiments, each corresponding to individual runs of simulation software with different parameter settings; in complex studies, the pattern of parameter changes is complex and may have to be adjusted by the user based on partial simulation results. Unfortunately, existing tools have limited highlevel support for managing large ensembles of simultaneous computational experiments. In this paper, we present a system architecture for interactive computational studies targeting two goals. The first is to provide a framework for highlevel user interaction with computational studies, rather than individual experiments; the second is to maximize the size of the studies that can be performed at close to interactive rates. We describe a prototype implementation of the system and demonstrate performance improvements obtained using our approach for a simple model problem. [PDF] [bib]   A Quadratic Bending Model for Inextensible Surfaces Miklós Bergou, Max Wardetzky, David Harmon, Denis Zorin, and Eitan Grinspun, Fourth Eurographics Symposium on Geometry Processing, pp.227230, 2006.
Abstract: Efficient computation of curvaturebased energies is important for practical implementations of geometric modeling and physical simulation applications. Building on a simple geometric observation, we provide a version of a curvaturebased energy expressed in terms of the Laplace operator acting on the embedding of the surface. The corresponding energy, being quadratic in positions, gives rise to a constant Hessian in the context of isometric deformations. The resulting isometric bending model is shown to significantly speed up common cloth solvers, and when applied to geometric modeling situations built on Willmore flow to provide runtimes which are close to interactive rates. [PDF] [bib] [Project] [Video]   Discrete Shells Origami Robert Burgoon, Eitan Grinspun, Zoë Wood, Proceedings of Computers And Their Applications, pp.180187, 2006.
Abstract: We introduce a way of simulating the creation of simple Origami (paper folding). The Origami is created in a thin shell simulation that realistically models the behavior and physical properties of paper. We demonstrate how to fold and crease the simulated paper wherever the user desires. [PDF] [bib]   Exploiting Temporal Coherence for Incremental AllFrequency Relighting Ryan Overbeck, Aner BenArtzi, Ravi Ramamoorthi and Eitan Grinspun, Eurographics Symposium on Rendering, 2006.
Abstract: Current PRT methods exploit spatial coherence of the lighting (such as with wavelets) and of light transport (such as with CPCA). We consider a significant, yet unexplored form of coherence, temporal coherence of the lighting from frame to frame. We achieve speedups of 3x4x over conventional PRT with minimal implementation effort, and can trivially be added to almost any existing PRT algorithm. [PDF] [bib] [Project] [Video]   A Discrete Model for Inelastic Deformation of Thin Shells Yotam Gingold, Adrian Secord, Jefferson Y. Han, Eitan Grinspun, Denis Zorin, Technical Report, Courant Institute of Mathematical Sciences, New York University, 2004.
Abstract: We introduce a method for simulating the inelastic deformation of thin shells: we model plasticity and fracture of curved, deformable objects such as light bulbs, eggshells and bowls. Our novel approach uses triangle meshes yet evolves fracture lines unrestricted to mesh edges. We present a novel measure of bending strain expressed in terms of surface invariants such as lengths and angles. We also demonstrate simple techniques to improve the robustness of standard timestepping as well as collision response algorithms. [PDF] [bib] [Project]   Discrete Shells Eitan Grinspun, Anil Hirani, Mathieu Desbrun and Peter Schröder, ACM SIGGRAPH / Eurographics Symposium on Computer Animation, pp.6267, 2003.
Abstract: In this paper we introduce a discrete shell model describing the behavior of thin flexible structures, such as hats, leaves, and aluminum cans, which are characterized by a curved undeformed configuration. Previously such models required complex continuum mechanics formulations and correspondingly complex algorithms. We show that a simple shell model can be derived geometrically for triangle meshes and implemented quickly by modifying a standard cloth simulator. Our technique convincingly simulates a variety of curved objects with materials ranging from paper to metal, as we demonstrate with several examples including a comparison of a real and simulated falling hat [PDF] [bib]   Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid Jeff Bolz, Ian Farmer, Eitan Grinspun, and Peter Schröder, SIGGRAPH (ACM Transactions on Graphics), pp.917924, 2003.
Abstract: Many computer graphics applications require highintensity numerical simulation. We show that such computations can be performed efficiently on the GPU, which we regard as a full function streaming processor with high floatingpoint performance. We implemented two basic, broadly useful, computational kernels: a sparse matrix conjugate gradient solver and a regulargrid multigrid solver. Realtime applications ranging from mesh smoothing and parameterization to fluid solvers and solid mechanics can greatly benefit from these, evidence our example applications of geometric flow and fluid simulation running on NVIDIA\\\'s GeForce FX using geometric flow (cube smoothing movie, 3D photography scan denoising movie) and fluid simulation (particle advection movie) as application examples. [PDF] [bib]   CHARMS: A Simple Framework for Adaptive Simulation Eitan Grinspun, Petr Krysl and Peter Schröder, SIGGRAPH (ACM Transactions on Graphics), pp.281290, 2002.
Abstract: Finite element solvers are a basic component of simulation applications; they are common in computer graphics, engineering, and medical simulations. Although adaptive solvers can be of great value in reducing the often high computational cost of simulations they are not employed broadly. Indeed, building adaptive solvers can be a daunting task especially for 3D finite elements. In this paper we are introducing a new approach to produce conforming, hierarchical, adaptive refinement methods (CHARMS). The basic principle of our approach is to refine basis functions, not elements. This removes a number of implementation headaches associated with other approaches and is a general technique independent of domain dimension (here 2D and 3D), element type (eg, triangle, quad, tetrahedron, hexahedron), and basis function order (piecewise linear, higher order Bsplines, Loop subdivision, etc.). The (un)refinement algorithms are simple and require little in terms of data structure support. We demonstrate the versatility of our new approach through 2D and 3D examples, including medical applications and thinshell animations. [PDF] [bib]   Natural Hierarchical Refinement for Finite Element Methods Petr Krysl, Eitan Grinspun, and Peter Schröder, International Journal for Numerical Methods in Engineering, pp.1109–1124, 2003.
Abstract: Current formulations of adaptive finite element mesh refinement seem simple enough, but their implementations prove to be a formidable task. We offer an alternative approach called CHARMS: Conforming Hierarchical Adaptive Refinement Methods. Our method yields equivalent adapted approximation spaces wherever the traditional mesh refinement is applicable, but proves to be significantly simpler to implement. At the same time it is much more powerful in that it is general (no special tricks are required for different types of finite elements), and applicable for some newer approximations where traditional mesh refinement concepts are not of much help, for instance on subdivision surfaces. [PDF] [bib]   Normal Bounds for SubdivisionSurface Interference Detection Eitan Grinspun and Peter Schröder, IEEE VIS \'01: Proceedings of the conference on Visualization \'01, pp.333340, 2001.
Abstract: Interference detection is vital for simulation and animation. Our interest was born of a larger project: using the Subdivision Element Method and the thinshell equations we produce realistic animations of crushing, crumpling, and wrinkling. In this paper we derive normal bounds for subdivision surfaces and use these to develop an efficient algorithm for collision detection with specific optimizations for selfinterference. The normal bounds are also useful for CAD and rendering [PDF] [bib]   NonLinear Mechanics and Collisions for Subdivision Surfaces Eitan Grinspun, Fehmi Cirak, Peter Schröder, and Michael Ortiz, Technical Report, 1999.
Abstract: Numerically accurate simulation of the mechanical behavior of thin flexible structures is important in application areas ranging from engineering design to animation special effects. Subdivision surfaces provide a unique opportunity to integrate geometric modeling with concurrent finite element analysis of thin flexible structures. Their mechanics are governed by the socalled thinshell equations. We present a concise treatment of thinshell equations including dynamic behavior, scalable material models, and the treatment of collisions (detection as well as response). The resulting energy minimization problem is nonlinear and in turn able to capture effects of far more realism than linear models. We demonstrate these claims with a number of simulations which exhibit characteristic effects of real world experiments [PDF] [bib]   The Basis Refinement Method Eitan Grinspun, PhD Thesis, Caltech, 2003.
Abstract: Finite element solvers are critical in computer graphics, engineering, medical and biological application areas. For large problems, the use of adaptive refinement methods can tame otherwise intractable computational costs. Current formulations of adaptive finite element mesh refinement seem straightforward, but their implementations prove to be a formidable task. We offer an alternative point of departure which yields equivalent adapted approximation spaces wherever the traditional mesh refinement is applicable, but proves to be significantly simpler to implement. At the same time it is much more powerful in that it is general (no special tricks are required for different types of finite elements), and applicable to novel discretizations where traditional mesh refinement concepts are not of much help, for instance on subdivision surfaces. [PDF] [bib]  