Interactive Shape Deformation
Interactive deformation is an important aspect of geometry processing, used for instance in CAGD and the movie industry. In our work, shape manipulation is driven by a variational optimization, which guarantees high quality deformations by minimizing physicallyinspired energies subject to usercontrolled constraints (Figures 1,2). We distinguish between linear and nonlinear approaches, depending on whether the energy minimization leads to the solution of a linear or nonlinear problem.
Using simplified quadratic energies leads to a linear system to be solved for the deformed surface each time the user changes the constraints or drags some surface points [1]. These socalled multiple righthand side problems can be solved efficiently using sparse Cholesky factorization [2]. Precomputing deformation response functions, which can then be evaluated instead of solving the linear system, even allows for realtime mesh editing [1]. Finescale geometric details are intuitively preserved through socalled multiresolution or multiscale deformations [1,3,4,5], which first separate the global shape from the finescale details, then deforms the global shape, and finally adds back the finescale details (Figure 3).
Space deformations warp the whole embedding space of an object, instead of computing the deformation on the surface mesh only. As a consequence, the complexity and stability of the deformation is decoupled from the object's mesh representation, such that on the one hand very complex models, and on the other hand also point clouds or irregular triangle soups can be processed. In [6,7] we represent the space deformation by triharmonic radial basis functions, which provides smoothness guarantees similar to surfacebased deformations. Since each mesh vertex is now transformed individually, the involved computations can be delegated to the programmable shaders of recent graphics hardware, which enables realtime shape editing of complex models at a rate of 30M vertices/sec (Figure 4).
While linear deformation approaches are extremely efficient, the involved linearizations can lead to artifacts under large deformations, in particular for large rotations (Figure 5), as we analyzed in our survey [8]. In such cases, nonlinear deformation techniques have to be employed. However, since then a nonlinear constrained minimization problem is to be solved for each step of an interactive deformation, particular attention has to be paid to computational efficiency and numerical robustness.
In [9] we developed a new nonlinear method for 3D surface deformation that achieves intuitive and robust deformations by emulating physically plausible surface behavior inspired by thin shells. The surface mesh is embedded in a layer of volumetric rigid cells, which are coupled through nonlinear, elastic forces (Figure 6). To deform the mesh, cells are rigidly transformed to satisfy user constraints while minimizing the nonlinear elastic energy. The nonlinearity allows for intuitive results even under large scale deformations. The rigidity of the prisms prevents degeneration even under extreme deformations, making the method numerically stable. Our modeling framework allows for the specification of various geometrically intuitive parameters that provide control over the physical surface behavior (Figures 7, 8). Interactive performance is achieved by a hierarchical multigrid solver [9] or by an adaptive space deformation approach [10]. For the latter, the object is embedded into an adaptively refined octreelike voxelization (Figure 9), which can even be dynamically refinement during object deformation (Figure 10). Thanks to the space embedding, the approach is applicable to arbitrary samplebased representations, such as meshes, triangle soups, or point clouds (Figure 11).
Related Publications
[1] 
An Intuitive Framework for RealTime Freeform Modeling
ACM Transactions on Graphics 23(3), SIGGRAPH 2004, pp. 630634.


[2] 
Efficient Linear System Solvers for Mesh Processing
Invited paper at IMA Mathematics of Surfaces XI, Lecture Notes in Computer Science, Vol 3604, 2005, pp. 6283.


[3] 
Multiresolution Surface Representation Based on Displacement Volumes
Computer Graphics Forum 22(3), Proc. Eurographics 2003, pp. 483491.


[4] 
Deformation Transfer for DetailPreserving Surface Editing
Vision, Modeling & Visualization 2006, pp. 357364.


[5] 
A Remeshing Approach to Multiresolution Modeling
Eurographics Symp. on Geometry Processing 2004, pp. 189196.


[6] 
RealTime Shape Editing using Radial Basis Functions
Computer Graphics Forum 24(3), Proc. Eurographics 2005, pp. 611621.


[7] 
GPUBased Multiresolution Deformation Using Approximate Normal Field Reconstruction
Journal of Graphics Tools 12(1), 2007, pp. 2746.


[8] 
On Linear Variational Surface Deformation Methods
IEEE Transactions on Visualization and Computer Graphics, 14(1), 2008, pp. 213230.


[9] 
PriMo: Coupled Prisms for Intuitive Surface Modeling
Eurographics Symp. on Geometry Processing 2006, pp. 1120 (Best Paper Award).


[10] 
Adaptive Space Deformations Based on Rigid Cells
Computer Graphics Forum 26(3), Proc. Eurographics 2007, pp. 339347.
