CS 779 -Free Form Deformation, 1999
Botros Gerges
My project consists of Free-Form-Deformation surface
editor. The goal of the editor is to allow the user to create different
models by manipulating a flat surface. However, there is no restriction
of starting from a flat surface. The algorithm is able to handle
an initial surface of any shape. Once the initial surface is known
(in the editor, it is always flat), a lattice is generated around the surface.
The lattice is tri-variate Bezier volume that maps the points of the surface
to its local coordinates.
Features
I implemented two methods of deformations, the common form of FFD which
allows the user to move the lattice control points, and Direct FFD (DFFD).
-
The first method is the easier of the two. The user is allowed to
pick any of the lattice's control points and move them in 3-space.
The left mouse button moves the point in the X-Z plane while the right
move it only in the Y-axis. This method is implemented in most modeling
applications. The drawback of FFD is that it not very intuitive how
the effect of moving one point will have on the surface.
-
DFFD is similar to FFD in that the user also picks points and moves them
in the same manner. With DFFD the user should be able to pick any
point on the surface. However, to simplify implementation, I allow
the user to only pick the tessellated points of the surface.
-
I also allow the user to load and save the surfaces that they create.
Algorithms/Implementation
I chose to make the lattice a tri-quartic Bezier volume, because Bezier
evaluations are faster than B-Spline evaluations. I chose quartic
because cubic does not provide a very flexible deformation.
However, I did not choose a degree higher than 4 because 4 has 64 control
points, while 5 has 125 (almost double). This means that degree 5
takes 64 extra affine combinations per evaluation (80 compared to 26).
This is a significant performance reduction.
-
FFD
I simply do an evaluation of the Bezier volume each time a point is
moved. I only evaluate the volume at the points of the surface.
-
DFFD
I used the algorithm describe in the Direct Manipulation of FFD paper.
I calculate the local coordinates of the picked point, then I calculate
the calculate the pseudo-inverse matrix B+ that is mentioned
in the HSU paper. This involves calculating the value of three basis
functions Bni(u) for i=0..n and u,v,w coordinate
of the picked point. Then I multiply them to get a multiple for the
each of the control points of the lattice. I use this matrix to calculate
the deltas for all the control points of the lattice and update the lattice.
Finally, I re-evaluate the volume at the points of the surface.
Surface/Volume Evaluation
For both the bi-variate surface and the tri-variate volume, I wrote
a Mann-DeRose evaluation. I also implemented my own tesselator for
the surface.
Limitations/Improvements
-
The u and v degrees of the initial patch must be equal, i.e.. the patch
must be bicubic, biquartic, etc. (currently bicubic)
-
The u, v, and w degrees of the tri-variate Bezier volume must be equal.
i.e.. tri-cubic, tri-quartic, etc. (currently tri-quartic)
-
Allow the user to pick any point on the surface, not just the tessellated
points.
-
Make the volume a tri-variate B-Spline volume. This will provide a
better locality of deformation.
-
Allow multiple points to be picked at the same time.
References
-
William M Hsu, Direct Manipulation of Free-Form Deformations, Proceedings
of SIGGRAPH'92, In Computer Graphics, 26,2, pages 177-184.
-
T.W. Sederberg, S.R. Parry, Free-Form Deformation of Solid Geometric
Models, Proceedings of SIGGRAPH'86, In Computer Graphics, 20, 4, pages
151-160.