Computer Graphics and Animation applications require mathematical models and simulation software that captures the qualitative, characteristic behavior of a physical system, even at very coarse discretizations. Our research group develops such numerical tools by using ideas from discrete differential geometry and discrete geometric mechanics. We attempt to build a discrete picture from the ground up, mimicking the axioms, structures, and symmetries of the smooth setting. The result is a discrete (hence immediately computable) model of the system, and in particular one that preserves important symmetries and conservation laws.
I will briefly survey our work in this domain, and focus on two specific recent examples: a discrete model of elastic rods with a natural extension to viscous threads, and a computational treatment of mechanical systems under contact and multi-impact (e.g., crumpling thin shells, granular media). Even at coarse discretizations, the resulting simulations capture desirable phenomena such as good long-time energy conservation, energy exchange between coupled modes, and characteristic instabilities.
In this talk, we will introduce Hodge-optimized triangulations, a family of well-shaped primal-dual pairs of complexes designed for fast and accurate computations in computer graphics. These triangulations are obtained via a variational optimization procedure based on a family of functionals on pairs of complexes that we derive from bounds on the errors induced by diagonal Hodge stars, commonly used in discrete computations. The minimizers of these functionals are shown to be generalizations of Centroidal Voronoi Tesselations and Optimal Delaunay Triangulations, and to provide increased accuracy and flexibility for a variety of computational purposes. This is a joint work with Patrick Mullen, Fernando de Goes and Mathieu Desbrun.
Under what conditions does a given collection of data describe a valid piece of geometry? This question is the question of integrability. Integrability is a powerful geometric tool because it often leads to changes of variables that greatly reduce the cost of computation. In this talk I will investigate conditions on curvature that make it easy to compute length-preserving motions of curves and angle-preserving motions of surfaces. The main outcome is a new algorithm for Willmore flow that permits extraordinarily large time steps and does not require remeshing over the course of the flow.
We present a fast, scalable algorithm to generate high-quality blue noise point distributions of arbitrary density functions. At its core is a novel formulation of the recently-introduced concept of capacity-constrained Voronoi tessellation as an optimal transport problem. This insight leads to a continuous formulation able to enforce the capacity constraints exactly, unlike previous work. We exploit the variational nature of this formulation to design an efficient optimization technique of point distributions via constrained minimization in the space of power diagrams. Our mathematical, algorithmic, and practical contributions lead to point sets with improved spectral and visual behavior, at a fraction of the computational costs of previous approaches to high-quality blue noise generation.
Self-supporting masonry is one of the most ancient and elegant techniques for building curved shapes. Because of the very geometric nature of their failure, analyzing and modeling such structures is more a geometry processing problem than one of classical continuum mechanics. We present an iterative nonlinear optimization algorithm based on thrust network analysis to efficiently approximate freeform shapes by self-supporting ones. The rich geometry of thrust networks leads us to close connections between diverse topics in discrete differential geometry, such as a finite-element discretization of the Airy stress potential, perfect graph Laplacians, and computing admissible loads via curvatures of polyhedral surfaces. This geometric viewpoint allows us, in particular, to remesh self-supporting shapes by self-supporting quad meshes with planar faces.
We present a linear algorithm to Reconstruct the vertex coordinates for a surface mesh given its edge lengths and dihedral angles, unique up to rotation and translation. A local integrability condition for the existence of an immersion of the mesh in 3D Euclidean space is provided, mirroring the fundamental theorem of surfaces in the continuous setting (i.e., Gauss's equation and the Mainardi-Codazzi equations) if we regard edge lengths as the discrete first fundamental form and dihedral angles as the discrete second fundamental form. The resulting sparse linear system to solve for the immersion is derived from the convex optimization of a quadratic energy based on a lift from the immersion in the 3D Euclidean space to the 6D rigid motion space. This discrete representation and linear reconstruction can benefit a wide range of geometry processing tasks such as surface deformation and shape analysis. A rotation-invariant surface deformation through point and orientation constraints is demonstrated as well.