| dc.description.abstract | This thesis investigates computer algorithms and user interfaces which assist in the process of deforming raster images, vector graphics, geometric models and animated characters in real time. Many recent works have focused on deformation quality, but often at the sacrifice of interactive performance. A goal of this thesis is to approach such high quality but at a fraction of the cost. This is achieved by leveraging the geometric information implicitly contained in the input shape and the semantic information derived from user constraints. Existing methods also often require or assume a particular interface between their algorithm and the user. Another goal of this thesis is to design user interfaces that are not only ancillary to real-time deformation applications, but also endowing to the user, freeing maximal creativity and expressiveness. This thesis first deals with discretizing continuous Laplacian-based energies and equivalent partial differential equations. We approximate solutions to higher-order polyharmonic equations with piecewise-linear triangle meshes in a way that supports a variety of boundary conditions. This mathematical foundation permeates the subsequent chapters. We aim this energy-minimization framework at skinning weight computation for deforming shapes in real-time using linear blend skinning (LBS). We add additional constraints that explicitly enforce boundedness and later, monotonicity. We show that these properties and others are mandatory for intuitive response. Through the boundary conditions of our energy optimization and tetrahedral volume meshes we can support all popular types of user control structures in 2D and 3D. We then consider the skeleton control structure specifically, and show that with small changes to LBS we can expand the space of deformations allowing individual bones to stretch and twist without artifacts. We also allow the user to specify only a subset of the degrees of freedom of LBS, automatically choosing the rest by optimizing nonlinear, elasticity energies within the LBS subspace. We carefully manage the complexity of this optimization so that real-time rates are undisturbed. In fact, we achieve unprecedented rates for nonlinear deformation. This optimization invites new control structures, too: shape-aware inverse kinematics and disconnected skeletons. All our algorithms in 3D work best on volume representations of solid shapes. To ensure their practical relevancy, we design a method to segment inside from outside given a shape represented by a triangle surface mesh with artifacts such as open boundaries, non-manifold edges, multiple connected components and self-intersections. This brings a new level of robustness to the field of volumetric tetrahedral meshing. The resulting quiver of algorithms and interfaces will be useful in a wide range of applications including interactive 3D modeling, 2D cartoon keyframing, detailed image editing, and animations for video games and crowd simulation. | en_US |
