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.
 
 

Motivation

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

• Accurate within a user-defined tolerance: Given a boundary representation of solid geometry and user-specified deformation, the algorithm preserves the total volume of embedded solid geometry within a given tolerance. This is achieved by tessellating boundary surfaces into a triangle mesh fine enough to allow the algorithm to obtain the desired accuracy.

• Frame-indifferent: The internal elastic energy of a dynamical system should not depend on the frame in which the deformation is observed. This property is known as "frame-indifference" in mechanics. Our algorithm computes the new node positions of the deformation lattice using augmented Lagrangian methods. It minimizes the elastic energy function based on a spring network to simulate frame-invariant elastic behavior subject to the volume-preserving constraint, as opposed to simple quadratic approximations. Frame-indifference is especially important for large deformation.

• Efficient: During each iteration, the optimizer computes the volume deviation and its derivatives based on a approximation method that requires a finely tessellated mesh to achieve the desired accuracy. To reduce the computational cost, we exploit the multi-level-of-detail representations of the boundary surfaces to provide progressive refinement, while the user interactively manipulates the object and views the changes.

• Versatile: This technique is capable of handling not only polyhedra but also most of other B-rep solids, by using successive levels of detail of the models to accelerate convergence of the non-linear optimizer.

  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 (http://gamma.cs.unc.edu/ffd). 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.

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 (N_Tri³ 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. T₁ and T₂ are the total CPU time (msec) of without and with Multi Level Optimization respectively. D V/V_org is the final relative volume deviation after Multi-Level Optimization. N_Tri is the number at the terminal level.
 

Example	T1	T2	T1/T2	NTri	DV/Vorg
Torus   Compression	21000	1760	12	4096	0.05%
Torus Stretch	677400	11080	61	65536	0.08%
Club Partial  Compressioin	40990	3530	12	16384	0.07%
Cow Bending	15810	2240	7	5804	0.07%

 
  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 k^th level of approximation with N_Tti 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. N_step is the total number of internal minimization steps at each level. T is CPU time (in msec) spent for the minimization of the k^th level. T_c is cumulative CPU time.
 

k	NTri	Before minimization.	After minimization	D X	Nstep	T	Tc
0	16			25%	90	120	120
1	64			7.9%	15	60	180
2	256			3.3%	19	290	470
3	1024			0.4%	13	700	1170
4	4096			0.01%	3	590	1760

 
 

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.