Cs679 - Free-Form Deformations

Overview

Direct manipulation is an attempt to make deformations of objects more user-friendly. The user selects point on the surface of the object and moves the point to a new location. The program automatically determines adjustments to the control points that effect this change.

What I did

My program has the following main interface features (See Figure 1):

• Ability to import OBJ (mesh) models.
• Save deformed (mesh) model to OBJ format file.
• Render the model in face, line or point mode.
• Toggle the normal direction on models that don't provide normals.
• Toggle culling for backfacing polygons.
• Adjust the size of the control grid (lattice) in the X, Y and Z directions.
• Toggle display of the lattice.
• Pick through the model, if in line or point mode.
• Perform group selections of lattice control points when in lattice deformation mode.
• Select and move multiple lattice points or model vertices.
• Deform the model using either the lattice control points or the model vertices.
• Mark the current lattice configuration, Undo and Redo between previous marked configurations.
• Change the background colour and the colour the model is displayed in.

Figure 1: User-Interface for the Free-Form Deformation Program

Implementation Details

• Polygonal mesh read in from selected OBJ file.
• A bounding box is created around the model.
• Local coordinate system is imposed on the model.
• The local (s,t,u) coordinates of the model vertices are computed.
• The control points for the lattice are computed based on the current number of regions specified.
• The deformed position of a point in the model is computed by evaluating the trivariate Berstein polynomial at the local (s,t,u) coordinates relative to the current location of the control points.
• In Free-Form Deformation mode:
  • Single or multiple grid control points are selected and moved.
  • The deformed positions of the model points are recomputed relative to the new control point locations.
• In Direct Manipulation mode:
  • Single or multiple points (vertices) on the model are selected and moved.
  • New positions for the control points are computed by using the generalized inverse to find the best least-squares solution for the new control points given the new locations of surface point(s) and the matrix of Bernstein blending functions at the selected point.
  • The deformed positions of all other model points are computed relative to the new control point locations.
• Any combination of free-form deformations and direct manipulations can be used to achieve the desired effect.
• Deformed model mesh written to OBJ file.

What I learned

In more detail...

• advantages and disadvantages to different types of deformation techniques (free-form deformations, extended free-form deformations, direct manipulation)
• how to evaluate and implement tri-variate Bezier volumes
• how to generate Bernstein coordinates from a polygonal mesh
• Tri-variate Bezier volumes are probably not the best evaluation technique to use for free-from deformations or for direct manipulation. One major draw-back is that the control points do not have a local area of influence. While it is true that they have more influence on surface points that are closer, they still do have influence on all object points. This greatly increases the amount of computation that must be done when a fine lattice is used. In particular if one control point changes, the deformation for the entire model must be recomputed. Another evaluation technique such as B-splines that has a local area of influence would be much more efficent, and would provide a greater degree of control when manipulating the object.
• how to use the singular value decomposition to compute the generalized inverse (pseudoinverse) for a non-square and possibly singular matrix.
• OpenGL and Tcl/Tk (rinse, lather and repeat).
• Obj files

What I deserve marks for

Basic Project

• Implementing interactive free-from deformations using tri-variate Bezier's.
• Manipulation of single control points.
• Direct manipulation of a single target point.

Extras

• Selection and manipulation of multiple control points simultaneously.
• Direct manipulation of multiple target points.
• Ability to combine types of deformations.
• Importing/Exporting OBJ models
• Mark/Undo/Redo of selected configurations.
• Enhanced user-interface.

Pictures

Figure 1 Beethoven Model before deformation with 4x6x5 lattice	Figure 2 Beethoven after a few iterations of FFD	Figure 3 Beethoven with multiple points selected for DM
Figure 4 Final Lattice after a several more DM steps	Figure 5 Final Beethoven model after several rounds of FFD and DM	Figure 6 ATC model before deformation
Figure 7 ATC after several DM steps with multiple target points	Figure 8 Lattice after DM on ATC	Figure 9 ATC deformed by several DM steps
Figure 10 FFD using an X cross section selection on ATC	Figure 11 Deathstar model	Figure 12 Deathstar model with 4x4x4 lattice in line mode to facilitate point selection
Figure 13 Deathstar partially deformed using FFD	Figure 14 The DeathEgg!	Figure 15 Triceratop Model
Figure 16 Triceratop model showing lattice after a number of DM steps	Figure 17 Triceratop after deformation by DM	Figure 18 Tie Interceptor Model
Figure 19 FFD Deformation with 4x4x3 lattice	Figure 20 Resulting model... Beware those hi-G turns!

References

• T.W. Sederberg, S.R.Parry. Free-Form Deformation of Solid Geometric Models. SIGGRAPH 1986 Vol. 20. No. 4.
• W.H. Hsu, J.F. Hughes and H. Kaufman. Direct Manipulation of Free-Form Deformations. SIGGRAPH 1992 Vol. 26. No. 2.
• W.H. Press et.al. Numerical Recipes in C, Second Edition. Cambridge University Press. 1992.