Free-Form Deform Deformations

J. Alexander Clarke
Term project CS799r (CS779-F2002)

January 27th, 2003

Overview

Free-form deformation (FFD) is a sophisticated technique for creating complex geometric models. It involves using trivariate parametric volumes to map "regular" space to some distorted space. Generally FFDs are a awkward to use. This is because the modelling is achieved by moving control points that are not attached to the object being manipulated. However, they remain popoular because they work well on Modern programs that perform FFD use Direct Manipulation (DM) techniques to help make the modelling process more natural. My project implements two slightly different DM interfaces for a 20x20x20 B-Splines FFD applied to a sphere.

Work Stages

polish B-Spline code
develop 3D point manipulation code
write a B-Spline surface editor based on the pyrimid algorithms presented in the course to prove my code can be worked up to 3D
abandon the dynamic programming technique in favor of an explicit method
implement a second point manipulation technique (thanks for the help Tibi)
implement simple FFD editor without DM
allow user to change mesh density on sphere
fix normals so they look right under most deformations
implement DM for single point
develop and compare two multipoint techniques:

cumulative control point displacement with averaging
cumulative control point displacement without averaging

B-Spline Editor

I only mention this because it was done in addition to the Bezier Surface renderer I wrote for class.

My middle initial embossed.

3D Point Manipulation

In order to to realtime FFD I needed to implement some kind of point editing. The first method I used was simple translation along the axes of the WCS. I later implemented viewer oriented planar translation to keep me from going crazy when I edited things from a different angle. I wish I had implemented a view angle based depth altering function.

Simple FFD Editor (No FFD)

B-Spline FFDs allow the construction of complex objects, but they need a large number of control points to do it. The following image illustrates just how bewildering the interface gets at the point where things start getting useful.

My eyes hurt

Here's an example of some editing using a simpler grid (10x10x10)

Before

step1

I won't admit how much time I wasted on this.

FFD with Direct Manipulation

There are many different schemes for doing direct manipulation. All of them share one thing: the ability to edit the position of points that are part of the mesh rather than free floating spline control points. The two schemes I implemented are actually variants of the same one. It is taken from the paper by Hagenlocker and Fujimura and is based on the seminal DM paper by Hsu and Kaufman. Basically it uses least squares to try to get the tricubic curve that a point lies in to move the point where you want it to go. It is really quite elegant. Both papers suggest that when two moved points share a control point they should play nice and blend their influences over it. This, however seems to lead to points fighting over control points and which point wins is not always clear. To get around this I simply let the newet point move the already displaced control point however it saw fit. I like the feel of the latter approach.

The DM interface for FFD is much cleaner than the alternative.

Cleaner then control point manipulation!

Both Direct manipulation techniques have their disadvantages. They are nearly useless without group selection which I did not choose to implement. With the first scheme deformations slowed down noticeably as large numbers of points were displaced. The second scheme does not suffer from slow down, but it tends to allow points to get too close together causing ridges and interpenetration.

Discussion

Using B-Splines to do Free-form deformations has several advantages. Foremost among them is that they guaranee continuity between one region of deformaton and another. They are also fast and allow for local rather than global control of the deformation. This power comes with a price. Using too fine a grid results in deformations that are hard to control.

References

Thomas W. Sederberg and Scott R. Parry, Free-Form Deformations of Solid Geometric Models Computer Graphics, 20 (August 1986) 151-159
Hsu, William M., Hughes, John F., and Kaufman, Henry, Direct Manipulation of Free-form Deformations, ACM SIGGRAPH (July 1992) 177-184
Hagenlocker, Michael and Kikuo Fujimura, CFFD: a tool for designing flexible shapes, The Visual Computer, 14 (1998) 271-287