Communications of the ACM
Home/Magazine Archive/April 2014 (Vol. 57, No. 4)/Technical Perspective: A 'Reasonable' Solution to.../Full Text
Research highlights
Technical Perspective: A 'Reasonable' Solution to Deformation Methods
Geometry plays a key role in the world of modern computing. In science and engineering, mathematical models of geometry are crucial for applications like simulation and manufacturing. In the arts and entertainment, mathematical models of geometry are ubiquitous in applications like games and movies, and are useful even for image editing. Developing new variants of these models that are both intuitive and computationally efficient remains an area of intense research in computer graphics.
One classical problem in this area is that of deformable modeling; that is, deforming a given shape into a target shape via some type of mathematical method (ideally an interactive one). Solutions to this problem lie at the core of most current computer animation systems. One standard approach for these methods is to view the shape as being comprised of a deformable material and having a collection of embedded shape handles. Typically, these shape handles are either points or piecewise linear shapes connecting these points that a user may manipulate interactively. In this framework, the deformation method computes a "reasonable" deformation of the shape based on some simple physical model.
One interesting question here is what corresponds to a "reasonable" deformation. Historically, the simplest mathematical models for deformations have been piecewise polynomials. In the one-dimensional case, these models (such as B-splines) are simple, intuitive, and expressive. For two-dimensional shapes, piecewise linear deformations are again simple and intuitive. However, higher-order piecewise polynomial models lack the smoothness and flexibility needed in many applications. Since univariate polynomials are the solutions to simple differential equations, many modern deformation schemes model smooth deformations as the solutions to a partial differential equation (PDE). Most deformation methods based on PDEs typically focus on either harmonic functions (solutions to Laplace's equation) or, more recently, biharmonic functions (solutions to the iterated Laplace's equation).
In this vein, Jacobson et al. construct a deformation method that allows a wide range of handle types (points, line segments, open and closed polygons) and produces deformations that are biharmonic functions. In this framework, the positions of the handles are treated as boundary conditions for the associated PDE. An important fact to note is that the use of biharmonic functions in place of the harmonic functions is due to the inclusion of isolated handles. Harmonic functions are typically used to model the idealized deformation of thin elastic membranes while biharmonic functions are typically used to model deformations of thin elastic plates. Interpolating an isolated handle with a thin membrane (harmonic) will lead to non-smooth deformations that often fold back on themselves. Interpolating an isolated handle with a thin plate (biharmonic) normally yields a smooth deformation with no fold back.
Jacobson et al.'s main technical innovation is the addition of linear inequality constraints to their model to ensure the resulting solutions to the harmomic equation are bounded. Most modeling methods based on partial differential equations restrict themselves to linear constraints to ensure the solution process is interactive. The drawback with these purely linear methods is that the solution to a problem with non-negative boundary values may occasionally have a solution that is not strictly non-negative everywhere. In practice, this issue makes modeling a desired deformation as a combination of deformations formed by perturbing one shape handle at time less intuitive.
The mathematical solution to this problem is to use a combination of linear equality and inequality constraints to ensure the resulting solutions to the PDE are non-negative. Using the authors' formulation of these constraints, the resulting problem is both bounded and convex and, as a result, can be solved efficiently using a standard sparse quadratic programming solver. In practice, the method discretizes the shape and pre-computes independent deformations for each individual handle. This main solution process is done as a pre-computation and takes on the order of, at most, seconds for most examples. Since the problem is linear, the desired deformation corresponding to a specific set of handle locations can be computed interactively by taking linear combinations of the pre-computed deformations for each individual handle. Locality and convexity ensure the resulting deformations follow the boundary conditions in an intuitive manner.
The method is an excellent example of the state of the art in deformation methods. The method combines the use of the biharmonic equation to achieve smooth local deformations while restricting these deformations to be non-negative and have no local minima through the use of linear inequality constraints. Since the deformation is computed as a solution to the PDE only over the shape, the resulting deformations depend only on the positions of the handles that are nearby in terms of distance inside the shape. More generally, the paper points in the direction for interesting future work on the use of advanced mathematical methods for representing complex deformations and the use of sophisticated numerical solvers to compute these deformations in practice.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.
No entries found