On-Line Computer Graphics Notes
FREE-FORM DEFORMATIONS

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 ${\bf P}$ in the following form
  $${\bf P} = {\bf O} + u {\vec u} + v {\vec v} + w {\vec w}$$

  The $(u,v,w)$ coordinates of any point ${\bf P}$ can be found by solving the above system of equations or by direct calculation

  $$u = \frac{ ( {\vec v} \times {\vec w} ) \cdot ( {\bf P} - {\bf O} ) }{ ( {\vec v} \times {\vec w} ) \cdot {\vec u} }$$

  $$v = \frac{ ( {\vec u} \times {\vec w} ) \cdot ( {\bf P} - {\bf O} ) }{ ( {\vec u} \times {\vec w} ) \cdot {\vec v} }$$

  $$w = \frac{ ( {\vec u} \times {\vec v} ) \cdot ( {\bf P} - {\bf O} ) }{ ( {\vec u} \times {\vec v} ) \cdot {\vec w} }$$

  
  

• Impose a grid of control points

  $$\left\{ {\bf F} _{i,j,k}^{pp} : 0 \leq i \leq l, \: 0 \leq j \leq m, \: 0 \leq k \leq n \right\}$$

  
  
  on the parallelpiped such that

  $${\bf F} _{i,j,k}^{pp} = {\bf O} + \frac{i}{l} {\vec u} + \frac{j}{m} {\vec v} + \frac{k}{n} {\vec w}$$

  
  

• Deform the control points ${\bf F} _{i,j,k}^{pp}$ on the parallelpiped into new points ${\bf F} _{i,j,k}$
• Reconstruct any point ${\bf P}$ in three-dimensional space by first calculating its $(u,v,w)$ coordinates, and then plugging these coordinates into the trivariate Bézier function

  $${\bf F} (u,v,w) = \sum_{i=0}^{l} \sum_{j=0}^{m} \sum_{k=0}^{n} {\bf F} _{i,j,k} B_{i}^{l}(u) B_{j}^{m}(v) B_{k}^{n}(w)$$

  
  
  The point ${\bf F} (u,v,w)$, is the deformation of ${\bf P}$.

In general, an object can be deformed by deforming all the points that are contained in the object. Usually this is an impossible task and thus we normally strive to determine a finite set of points that can be deformed (the B-rep model) and then attempt to reconstruct the deformed B-rep from the finite set of deformed points. In general, the accepted method to utilize Sederberg/Parry deformations is to take an object and tesselate it into small polygons. The vertices of these polygons are then deformed and the resulting polygons are drawn on a graphics device. Utilizing small polygons limits the possible distortion that this method can generate (Consider that this method can take planar polygons into non-planar surfaces, so utilizing the vertices of large polygons may not work so well).

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).

It is this third method that we address in this paper.

Extensions of Sederberg/Parry Deformation Methods

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 $(u,v,w)$ 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 $(u,v,w)$ 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 $(u,v,w)$ 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 $(u,v,w)$ 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

$${\bf F} (u,v,w) = \sum_{i=0}^{l} \sum_{j=0}^{m} \sum_{k=0}^{n} {\bf F} _{i,j,k} B_{i}^{l}(u) B_{j}^{m}(v) B_{k}^{n}(w)$$

where ${\bf F} _{i,j,k}$ are the deformed control points.

Thus, the EFFD method recognized that it was the calculation of the $(u,v,w)$ 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 $\cal O$ be an object that is to be deformed and let $\cal A$ be an axis. Attach each vertex ${\bf V}$ of $\cal O$ to a point ${\bf A} _ {\bf V}$ on the axis $\cal A$. Calculate the local coordinates $(u,v,w)$ of ${\bf V}$ in the local coordinate system of $\cal A$. The deformed vertex is obtained by computing the associated local coordinate system at ${\bf A} _ {\bf V} '$ (which is the deformed point analygous to ${\bf A} _ {\bf V}$) and transforming the $(u,v,w)$ 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 $\cal A$. The deformation of these frames then allows the reconstruction of the transformation to get the $(u,v,w)$ points back into world space.

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

$${\bf P} (t) = \sum_{i=0}^{n} {\bf P} _i B_{i}^{n} ( t )$$

and define the frame at each point by the parametric functions

$${\bf U} (t) = \sum_{i=0}^{n} {\bf U} _i B_{i}^{n} ( t )$$

$${\bf V} (t) = \sum_{i=0}^{n} {\bf V} _i B_{i}^{n} ( t )$$

$${\bf W} (t) = \sum_{i=0}^{n} {\bf W} _i B_{i}^{n} ( t )$$

Given a point ${\bf P} = (x,y,z)$ in 3-dimensional space, find the point $t_ {\bf P}$ (probably by numerical techniques) such that ${\bf P} (t_ {\bf P} )$ is the point on the axial curve associated with ${\bf P}$. Determine values $(u,v,w)$ so that

$${\bf P} = {\bf P} (t_ {\bf P} ) + u {\bf U} (t_ {\bf P} ) + v {\bf V} (t_ {\bf P} ) + w {\bf W} (t_ {\bf P} )$$

Let ${\bf P} _i'$, ${\bf U} _i'$, ${\bf V} _i'$, ${\bf W} _i'$ be the deformed points and frame respectively. Then the deformed point ${\bf P} '$ is given by

$${\bf P} ' = {\bf P} '(t_ {\bf P} ) + u {\bf U} '(t_ {\bf P} ) + v {\bf V} '(t_ {\bf P} ) + w {\bf W} '(t_ {\bf P} )$$

where

$${\bf P} '(t) = \sum_{i=0}^{n} {\bf P} _i' B_{i}^{n} ( t ),$$

$${\bf U} '(t) = \sum_{i=0}^{n} {\bf U} _i' B_{i}^{n} ( t ),$$

$${\bf V} '(t) = \sum_{i=0}^{n} {\bf V} _i' B_{i}^{n} ( t ), \: {\rm and}$$

$${\bf W} '(t) = \sum_{i=0}^{n} {\bf W} _i' B_{i}^{n} ( t )$$

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 $(u,v,w)$

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

Mail us your comments

All contents copyright (c) 1996, 1997, 1998, 1999
Computer Science Department
University of California, Davis

All rights reserved.