 | Discrete Elastic Rods
Miklós Bergou, Max Wardetzky, Stephen Robinson, Basile Audoly, Eitan Grinspun,
SIGGRAPH ( ACM Transactions on Graphics), 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 rigid-bodies 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 coupled-mode experiments, and via qualitative knot-tying 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:
Example-based texture synthesis algorithms have gained widespread popularity for their ability to take a single input image and create a perceptually similar non-periodic texture. However, previous methods rely on single input exemplars that can capture only a limited band of spatial scales. For example, synthesizing a continent-like 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 example-based representation, which we call an exemplar graph, that simply requires a few low-resolution input exemplars at different scales. Moreover, by allowing loops in the graph, we can create infinite zooms and infinitely detailed textures that are impossible with current example-based 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 gigapixel-sized 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), 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 fail-safe when a bound on iteration count is exceeded. The best-known fail-safe rigidifies the contact region, causing simulation artifacts. We present a fail-safe that cancels impact but not sliding motion, considerably reducing artificial dissipation. We equip the proposed fail-safe 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.33-37, 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 well-known and widely-used operators.
[PDF] [bib] |
 | TRACKS: Toward Directable Thin Shells
Miklós Bergou, Saurabh Mathur, Max Wardetzky, and Eitan Grinspun,
SIGGRAPH (ACM Transactions on Graphics), 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 weak-form 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 image-based 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 lighting-BRDF convolution. We show how spherical harmonics can be used to filter the NDF for Lambertian and low-frequency specular BRDFs, while spherical von Mises-Fisher distributions can be used for high-frequency materials.
[PDF] [bib] [Project] [Video] |
 | Cubic Shells
Akash Garg, Eitan Grinspun, Max Wardetzky, Denis Zorin,
Symposium on Computer Animation, pp.91-98, 2007.
Abstract:
Hinge-based bending models are widely used in the physically-based animation of cloth, thin plates and shells. We propose a hinge-based 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
Max Wardetzky, Miklós Bergou, David Harmon, Denis Zorin, and Eitan Grinspun,
Computer Aided Geometric Design, 2007.
Abstract:
[This is preprint--not a final copy.] We present a family of discrete isometric bending models (IBMs) for triangulated surfaces in 3-space. 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 time-integration of cloth dynamics with a two- to three-fold net speedup over existing nonlinear methods, and near-interactive rates for Willmore smoothing of large meshes.
[PDF] [bib] [Project] |
 | 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.547-556, 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 two-dimensional 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 triangle-centered quadratic interpolation.
|
 | A note on the triangle-centered 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 edge-adjacent 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] |
 | Sim-X: Parallel System Software for Interactive Multi-Experiment Computational Studies
Siu-Man Yau, Eitan Grinspun, Vijay Karamcheti, and Denis Zorin,
International Parallel & Distributed Processing Symposium , 2006.
Abstract:
Advances in high-performance 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 high-level 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 high-level 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.227-230, 2006.
Abstract:
Efficient computation of curvature-based 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 curvature-based 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.180-187, 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 All-Frequency Relighting
Ryan Overbeck, Aner Ben-Artzi, 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 3x-4x over conventional PRT with minimal implementation effort, and can trivially be added to almost any existing PRT algorithm.
[PDF] [bib] [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, egg-shells 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.62-67, 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
Eitan Grinspun, Jeff Bolz, Ian Farmer, and Peter Schröder,
SIGGRAPH ( ACM Transactions on Graphics), pp.917-924, 2003.
Abstract:
Many computer graphics applications require high-intensity 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 floating-point performance. We implemented two basic, broadly useful, computational kernels: a sparse matrix conjugate gradient solver and a regular-grid 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] [Video] |
 | CHARMS: A Simple Framework for Adaptive Simulation
Eitan Grinspun, Petr Krysl and Peter Schröder,
SIGGRAPH ( ACM Transactions on Graphics), pp.281-290, 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 B-splines, 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 thin-shell 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 Subdivision-Surface Interference Detection
Eitan Grinspun, Peter Schröder,
IEEE VIS '01: Proceedings of the conference on Visualization '01, pp.333-340, 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 thin-shell 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 self-interference. The normal bounds are also useful for CAD and rendering
[PDF] [bib] |
 | Non-Linear 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 so-called thin-shell equations. We present a concise treatment of thin-shell equations including dynamic behavior, scalable material models, and the treatment of collisions (detection as well as response). The resulting energy minimization problem is non-linear 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] |
|
. I also teach Computer Animation, Physical Simulation, and Discrete Differential Geometry.