Graphics & Geometry Group

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 physically-inspired energies subject to user-controlled 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.

Figure 1: Physically-plausible deformations are achieved by a constrained minimization of stretching (center) or bending (right) energies [3,10].
Figure 2: Stretching the car's hood using multiple handle regions allows the wheel houses to be kept circular. Precomputed response function enable real-time deformation of this 250k triangles model [6].

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 [3]. These so-called multiple right-hand side problems can be solved efficiently using sparse Cholesky factorization [4]. Precomputing deformation response functions, which can then be evaluated instead of solving the linear system, even allows for real-time mesh editing [3]. Fine-scale geometric details are intuitively preserved through so-called multi-resolution or multi-scale deformations [1,2,3,6], which first separate the global shape from the fine-scale details, then deforms the global shape, and finally adds back the fine-scale details (Figure 3).

Figure 3: A multiresolution deformation framework decomposes the input geometry S into a smooth base surface B and fine-scale details D. The global shape is deformed to B', on top of which the details D are added back to finally get the deformed detailed surface S' [10].

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 [5,8] we represent the space deformation by triharmonic radial basis functions, which provides smoothness guarantees similar to surface-based 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 real-time shape editing of complex models at a rate of 30M vertices/sec (Figure 4).

Figure 4: Our variational space deformation allows for local fine-scale edit (center) as well as global deformations (right) of the complex head model (left, 660k triangles) in real-time [2].

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 [10]. 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.

Figure 5: A detailed analysis and comparison of several linear deformation approaches reveals their respective advantages and drawbacks, and also demonstrates the general limitations of linear methods in case of large deformations [10].

In [7] 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 non-linear, 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 multi-grid solver [7] or by an adaptive space deformation approach [9]. For the latter, the object is embedded into an adaptively refined octree-like 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 sample-based representations, such as meshes, triangle soups, or point clouds (Figure 11).

Figure 6: The nonlinear energy, which glues the rigid cells together, measures the amount of deformation, such as stretching and bending, as indicated in red.
Figure 7: A user-defined force tries to lift the car's front. The center and right image show results for the same force on a rather stiff and a more flexible surface material, respectively.
Figure 8: The Goblin was posed by prescribing position and orientation for its head and right hand. For the left hand and foot positions were constrained only, thus enabling the automatic optimization of their orientations. The natural bending of joints was easily achieved by reducing the surface stiffness in these regions.
Figure 9: Deformations on a very large model. The user deforms the shape using a reduced model during interaction shown on the left. When satisfied with the results, the final space deformation is applied offline to the high-resolution model on the right consisting of more than seven million triangles.
Figure 10: The cut-away views show how the initial adaptive discretization is dynamically refined in regions of strong deformation, i.e., stretching and bending.
Figure 11: The space embedding allows to deform objects that are not clean, two-manifold surfaces. In this example, a tree represented by a triangle soup of 14k connected components, with leaves modeled as alpha-textured triangles, is deformed. On the right the stiffness was decreased toward the top of the trunk and for the leaves, further demonstrating the flexibility of the approach.
[1]
Multiresolution Surface Representation Based on Displacement Volumes
Mario Botsch, Leif Kobbelt
Computer Graphics Forum 22(3), Proc. Eurographics 2003, pp. 483-491.
[PDF]  [Video]  
[2]
A Remeshing Approach to Multiresolution Modeling
Mario Botsch, Leif Kobbelt
Eurographics Symp. on Geometry Processing 2004, pp. 189-196.
[3]
An Intuitive Framework for Real-Time Freeform Modeling
Mario Botsch, Leif Kobbelt
ACM Transactions on Graphics 23(3), SIGGRAPH 2004, pp. 630-634.
[4]
Efficient Linear System Solvers for Mesh Processing
Mario Botsch, David Bommes, Leif Kobbelt
Invited paper at IMA Mathematics of Surfaces XI, Lecture Notes in Computer Science, Vol 3604, 2005, pp. 62-83.
[PDF]  
[5]
Real-Time Shape Editing using Radial Basis Functions
Mario Botsch, Leif Kobbelt
Computer Graphics Forum 24(3), Proc. Eurographics 2005, pp. 611-621.
[6]
Deformation Transfer for Detail-Preserving Surface Editing
Mario Botsch, Robert Sumner, Mark Pauly, Markus Gross
Vision, Modeling & Visualization 2006, pp. 357-364.
[7]
PriMo: Coupled Prisms for Intuitive Surface Modeling
Mario Botsch, Mark Pauly, Markus Gross, Leif Kobbelt
Eurographics Symp. on Geometry Processing 2006, pp. 11-20 (Best Paper Award).
[8]
GPU-Based Multiresolution Deformation Using Approximate Normal Field Reconstruction
Martin Marinov, Mario Botsch, Leif Kobbelt
Journal of Graphics Tools 12(1), 2007, pp. 27-46.
[PDF]  [Video]  
[9]
Adaptive Space Deformations Based on Rigid Cells
Mario Botsch, Mark Pauly, Martin Wicke, Markus Gross
Computer Graphics Forum 26(3), Proc. Eurographics 2007, pp. 339-347.
[10]
On Linear Variational Surface Deformation Methods
Mario Botsch, Olga Sorkine
IEEE Transactions on Visualization and Computer Graphics, 14(1), 2008, pp. 213-230.
[11]
Interactive Shape Modeling and Deformation
Olga Sorkine, Mario Botsch
Eurographics 2009 Course Notes
[12]
Example-Driven Deformations Based on Discrete Shells
Stefan Fröhlich, Mario Botsch
Computer Graphics Forum 30(8), 2011, pp. 2246-2257.
[13]
A Comprehensive Comparison of Shape Deformation Methods in Evolutionary Design Optimization
Daniel Sieger, Stefan Menzel, Mario Botsch
Proceedings of International Conference on Engineering Optimization, 2012
[14]
High Quality Mesh Morphing Using Triharmonic Radial Basis Functions
Daniel Sieger, Stefan Menzel, Mario Botsch
Proceedings of the 21st International Meshing Roundtable, 2012, pp. 1-15
[15]
RBF Morphing Techniques for Simulation-based Design Optimization
Daniel Sieger, Stefan Menzel, Mario Botsch
Engineering with Computers, 30(2), 2014, pp. 161-174
[16]
Constrained Space Deformation for Design Optimization
Daniel Sieger, Stefan Menzel, Mario Botsch
Proceedia Engineering 82 (Proc. International Meshing Roundtable), 2014, pp. 114-126 (Best Paper Award).
[PDF]  
[17]
On Shape Deformation Techniques for Simulation-based Design Optimization
Daniel Sieger, Stefan Menzel, Mario Botsch
New Challenges in Grid Generation and Adaptivity for Scientific Computing, SEMA SIMAI Springer Series, 2015, pp. 281-303.
[PDF]  
[18]
Constrained Space Deformation Techniques for Design Optimization
Daniel Sieger, Sergius Gaulik, Jascha Achenbach, Stefan Menzel, Mario Botsch
Computer Aided Design 72, 2016, pp. 40-51.
[PDF]