Sederberg and Parry introduced the concept of a free-form deformation in [#!Sederberg86!#]. This technique defines a free-form deformation of space by specifying a trivariate Bézier solid, which acts on a parallelpiped region of space. The deformation procedure proceeds as follows:

- Impose a local coordinate system on a parallelpiped region of space
by specifying any point
in the following form
The coordinates of any point can be found by solving the above system of equations or by direct calculation

- Impose a grid of control points

on the parallelpiped such that

- Deform the control points on the parallelpiped into new points
- Reconstruct any point
in three-dimensional space by first
calculating its
coordinates, and then plugging these
coordinates into the trivariate Bézier function

The point , is the deformation of .

In the case that the object is defined by Bézier or B-spline solids, three methods are possible to represent the deformed object. (We note that any B-spline object can be refined into a set of Bézier objects, and will henceforth assume that we are only dealing with Bézier objects.)

- 1.
- Tesselate the Bézier object into small polygons and deform the object as was described above.
- 2.
- Deform the control points of the Bézier object. Use the deformed
control points create a new Bézier object.
This is not a correct solution to the problem and could exhibit artifacts that are worse than those possible in the first method. In fact, the deformation process forces a composition of the two defining functions and the resulting deformed object is of higher degree that the original object. Thus this method approximates a deformed Bézier object by another of lower degree - not the best solution.

- 3.
- Recognize that the deformation operation actually composes two Bézier operations and explicitly calculate the new control points of the composed object (which is of higher degree).

The Sederberg-Parry deformation method has had wide use in the computer graphics/modeling/animation fields (see [#!Chadwick89!#]). The simplicity of the method is that it utilizes parallelepipedidal regions of 3-dimensional space, resulting in a simple calculation for the coordinate of any point and a direct substitution into a trivariate Bézier function.

It was recognized by Coquillart [#!Coquillart90!#] that it was the calculation of the coordinate that was the primary difficulty in the algorithm and if one wanted to sacrifice additional time in solving for these coordinates, one could consider non-parallelepipedidal regions. This method, called the extended free-form deformation (or EFFD) method, utilized non-parallelepipedical lattices and calculated the coordinate by utilizing numerical methods (in this case, Newton's method).

For example, a cylindrical lattice can be formed by expanding the control points of a standard lattice representing a cube to approximate the sides by Bézier representations of a circle. The figure below illustrates this process

figures/cylindrical-lattice

The
coordinates cannot now be calculated by direct means,
but must be approximated (numerical iteration is the most common
method). The control points of the cylindrical lattice can then be
displaced and any point can be reconstructed by
where are the deformed control points.

Thus, the EFFD method recognized that it was the calculation of the coordinates that is the fundamental part of the deformation process. Sederberg/Parry utilized a parallelepipedical lattice which allows easy calculation of the coordinates. The calculation is more difficult with other lattice structures, but not so much to make it impossible.

Coquillart also discusses the piecing together of the lattice structures to make much more complex deformations. For example, one could define a toroidal deformation by piecing together four EFFDs that were based upon the Bézier definition of a quarter-section of a torus.

Coquillart and Jancéne's subsequent paper [#!Coquillart91!#] discusses the animation of the deformation lattices. Two lattices, the initial and final lattices, are defined and the animation proceeds by interpolating the corresponding lattice points between the initial and final lattices.

Lazarus, et al. [#!Lazarus!#] discusses axial deformations. This is similar to the EFFD method except that the final deformation function is not defined as a trivariate Bézier function.

The axial deformation process is done as follows. Let be an object that is to be deformed and let be an axis. Attach each vertex of to a point on the axis . Calculate the local coordinates of in the local coordinate system of . The deformed vertex is obtained by computing the associated local coordinate system at (which is the deformed point analygous to ) and transforming the points from this coordinate system back to the world coordinate system.

Most of the applications of this technique define a local coordinate frame, or frames on the axis . The deformation of these frames then allows the reconstruction of the transformation to get the points back into world space.

For example, let the axial curve be the Bézier curve,

Given a point in 3-dimensional space, find the point (probably by numerical techniques) such that is the point on the axial curve associated with . Determine values so that

Let , , , be the deformed points and frame respectively. Then the deformed point is given by

Where we have done this with parametric curves, the same methods can be applied to arbitrary curves and frames - and the basic problem is still the same, calculation of the local coordinates

Griessmair and Purgathofer [#!Griessmair89!#] discuss the Sederberg/Parry deformation of B-spline curves and patches. They do not treat this problem any differently that others, but give a set of criteria to utilize in tesselation of a surface in order to minimize the distortion in the deformation process (Remember that a polygon can be nonplanar under deformation, which implies that it must be approximated by many polygons before the deformation takes place in order to get an accurate model of the deformed surface.).

** References**

- Sederberg, T.W. and S.R. Parry,
``Free-form deformation of solid geometric models,''
*Proceedings of SIGGRAPH '86*(Dallas, Tex., Aug. 18-22, 1986). In*Computer Graphics, 20*, 4 (Aug. 1986), 151-160. - Chadwick, John E., David R. Haumann and Richard E. Parent,
``Layered Construction for Deformable Animated Characters,''
*Proceedings of SIGGRAPH '89*(Boston, MA, July 31 - Aug. 4, 1989). In*Computer Graphics, 23*, 3 (Aug. 1989), 243-252. - Coquillart, S.,
``Extended Free-Form Deformation : A Sculpturing Tool for 3D Geometric
Modeling,''
*Proceedings of SIGGRAPH '90*(Dallas, Tex., Aug. 6-10, 1990). In*Computer Graphics, 24*, 4 (Aug. 1990), 187-196. - Coquillart, S. and P. Jancéne,
``Animated Free-Form Deformation : An Interactive Animation
Technique,''
*Proceedings of SIGGRAPH '91*(Las Vegas, Nev., July 28- August 2, 1991). In*Computer Graphics, 25*, 4 (July 1991), 23-26. - Griessmair, J. and W. Purgathofer,
``Deformation of Solids with Trivariate B-Splines,''
in Hanmann, W., F.R.A Hopgood and W. Strasser (eds.),
*EUROGRAPHICS '89*, Elsevier Science Publishers (North Holland), 1989, 137-148. - Lazarus, F., S. Coquillart and P. Jancéne, ``Interactive Axial Deformations,'' 242-254.

**Return to
the Graphics Notes Home Page**

**Return
to the Geometric Modeling Notes Home Page**

**Return
to the UC Davis Visualization and Graphics Group Home Page**

**This document maintained by Ken
Joy**

All contents copyright (c) 1996, 1997, 1998,
1999

Computer Science Department

University of California, Davis

All rights reserved.

1999-12-06