Appeared In ACM SOLID MODELING '99 Paper Session
Complete versions are available in PDF and MSWord
Fast Volume-Preserving Free Form Deformation
Using Multi-Level Optimization
Gentaro Hirota, Renee Maheshwari and Ming C. Lin


Department of Computer Science
University of North Carolina at Chapel Hill

We present an efficient algorithm for preserving the total volume of free-form solids undergoing deformation using discrete level-of-detail representations. Given the boundary representation of a solid and user-specified deformation, the algorithm utilizes augmented Lagrangian methods to compute the new node positions of the deformation lattice, while minimizing the elastic energy subject to the volume-preserving criterion. During each iteration, the non-linear optimizer computes the volume deviation and its derivatives based on a triangular approximation method, which requires a finely tessellated mesh to achieve desirable accuracy. To reduce the computational cost, we exploit the multi-level representations of the boundary surfaces to greatly accelerate the performance of the non-linear optimizer. This technique also provides interactive response to the users. Furthermore, it is generally applicable to lattice-based free-form deformation and its variants. Our implementation has been applied to several complex solids. We have been able to achieve an order of magnitude performance improvement over the traditional methods on our test models.


Engineering design and shape styling often require the capability to manipulate flexible objects, including bending, twisting, compressing or stretching parts of the model or its entire geometry. Several modeling techniques and design methodologies have been proposed to provide intuitive manipulation and interactive deformation of flexible objects. One of the most versatile and powerful tools for representing and modeling flexible objects is free-form deformation (FFD) or space deformation introduced by Sederberg and Parry. FFD unifies both the free-form surfaces and solid modeling into a common framework for deforming solid geometry in a free-form manner. Furthermore, it can also sculpt surfaces and polygonal models. A more general extension to FFD (EFFD) was later presented by Coquillart.

  However, none of these methods associates any physical constraints with geometric deformation of solids. Recently, the integration of geometric design and physically-based modeling techniques has emerged to be an attractive alternative, as a natural and systematic approach to constraint-based design, shape blending and a variety of solid modeling problems by several researchers. Principles of physics govern the dynamic behaviors of objects in the physical world. Direct manipulation and interactive sculpturing of geometric models should also be compliant with the law of physics to give designers and stylists an intuitive grasp of the object. One of the important governing laws of Newtonian physics is the conservation of mass. When the density of a given material is constant, this implies the preservation of volume.

  A volume-preservation constraint allows designers to keep the required relative proportionality of object sizes (in terms of their volumes) in the design of a complex assembly consisting of multiple parts. Another example is the design of a container whose capacity is given a priori. The volume inside should be preserved when the designer modifies the shape of the container. Volume-preserving free-form deformation is not only a useful tool for modeling, but can also be a powerful visual aid in engineering animation and virtual prototyping as well. This technique can also be used to automatically create the standard squash and stretch effects in computer animation and help bring life to the animated characters.

Main Contribution

We present a new approach for volume-preserving free-form deformation using multi-level-of-detail representations. Our method is

  To the best of our knowledge, none of the previous methods on volume-preserving FFD have achieved these goals simultaneously.

  Although our implementation is based on the trivariate Bernstein basis FFD, the proposed technique is generally applicable to other lattice-based free-form deformations and their variants. Our implementation allows the designer to interactively manipulate the free-form solids and to view the model changes due to deformation in real-time, while simulating the physical behaviors of the solids subject to the volume-preserving constraint. We have been able to achieve an order of magnitude speedup over the conventional optimization methods.

Implementation & Results

We have implemented our algorithm in C++. The image generation and the user interface are developed using the OpenGL and GLUT library. All timing data were obtained on an SGI Onyx2 with 195MHz R10000 MIPS processors.

We have tested our system on various models undergoing deformation. The color images are also available at our web site ( We analyze its performance using four examples here.

  1. Torus compression (Plate 1): This example is already described in section 4 and Table 2. A torus (the left image) is deformed by a 3´ 3´ 3 lattice. The upper and lower 3´ 3 nodes in red are vertically moved toward the center, compressing the torus (the middle image) and then fixed in their places. The algorithm finds the new positions of the central nodes to regain the original volume (the right image). The multi-level meshes are generated by uniformly sampling the parameter space.
  2. Torus stretch (Plate 2): The same torus is now stretched by using a 5´ 2´ 2 lattice (the middle image). The upper and lower 2´ 2´ 2 nodes in red are fixed to enforce strong stretching to both ends. After the optimization process, the central 2´ 2 nodes have moved all the way across to the diagonal sides to produce lateral contraction.
  3. Rounded Club Partial Compression (Plate 3): A club with rounded ends (the left image) is deformed by 5´ 2´ 2 lattice. The left side of the club is compressed (the middle image) and the right side swells to compensate the lost volume by the compression. The club is modeled as a sphere deformed by FFD. The multi-level meshes are generated by a polygonal simplification algorithm [GH97] on a densely sampled sphere. The number of triangles at each level is approximately the same as the torus in previous example.
  4. Cow Bending (Plate 4): A cow model is bent by 5´ 2´ 2 lattice. The rather unnatural looking of the user-deformed cow (the middle image) is "improved" by our algorithm (the right image). The cow model has 5804 triangles and multi-level meshes are generated in the same way as the rounded club.
Figures 5,6,7, and 8 illustrate the convergence of the multi-level optimization. The x-axis is cumulative CPU time, and the y-axis is the maximum error of node positions estimated as the distance deviation between the nodes before and after the optimization. The distance is normalized by the size of the object. In all our examples the node points converge to the approximately correct positions in a fraction of a second. These results demonstrate that our method can be used for interactive applications. In our implementation, the intermediate states of nodes and objects are rendered during the unconstrained minimization iterations to provide even faster feedback to the user.

Table 1 shows the performance improvement of the multi-level optimization over the usual optimization method. We have consistently achieved about an order of magnitude speedup using the multi-level optimization. The torus stretch example has an interesting property that is worth mentioning. If we start the algorithm from a fine mesh (NTri³ 4096), the shape converges to a different configuration than if we start with a coarse mesh (Plate 6). This is not surprising because there are often multiple local minimum states in many near symmetric constraints. Our method seeks only the local minimum, therefore the result may not be consistent for different starting levels. Plate 7 is an example of very large deformation. The rounded club is bent significantly. Our algorithm handles these situations without any numerical problem. In Plate 5, The bottom half of a water pitcher model (6176 triangles) is compressed by the user. As a result of optimization, the upper part is expanded.

Figure 5: Convergence Curve. Torus compression.

Figure 6: Convergence Curve. Stretched Torus.

Figure 7: Convergence Curve. Rounded Club Partial Compression.

Figure 8: Convergence Curve. Bending Cow.


Table 1: Performance Improvement by Multi Level Optimization. T1 and T2 are the total CPU time (msec) of without and with Multi Level Optimization respectively. D V/Vorg is the final relative volume deviation after Multi-Level Optimization. NTri is the number at the terminal level.


Torus Stretch
Club Partial 


Cow Bending
Plate 1: Torus Compression Example
Plate 2: Stretched Torus Example. The triangle mesh at the convergence is 16 times denser than the mesh shown here.
Plate 3: Rounded Club with Partial Compression Example
Plate 4: Bending Cow Example
Plate 5: Water Pitcher Bottom Compression Example

Plate 6: A Different Equilibrium State
Plate 7: Large Deformation. The club in plate 3 is bent by a user (left) resulting in the right one.

 Table 2: Performance chart of multi-level optimization for a compressed torus example (Plate 1). The level k corresponds to the minimization at the kth level of approximation with NTti triangles. Red and blue cubes denote fixed and free nodes respectively. Node points X(k), penalty factor s (k), and Lagrange multiplier l (k) are inherited from one level to the next. D X is the maximum change in the coordinates of node points X relative to the size (the maximum extent) of the object. Nstep is the total number of internal minimization steps at each level. T is CPU time (in msec) spent for the minimization of the kth level. Tc is cumulative CPU time.
Before minimization.
After minimization

Copyright 1998. Permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the authors.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In all cases, these works may not be reposted without the explicit permission of the copyright holder.

 For more information, contact Gentaro Hirota <> or Ming C. Lin <>
Last Content Update: March 12, 1999
Last Content Review: July 18, 1999