CS679 Project: Direct Manipulation of Free-Form Deformations

Overview:

GUI Features:

• (L)oad and (S)ave facility supporting a subset of Wavefront's OBJ format.
• (R)eset orientation of the model.
• Wireframe (1), Flat (2) shaded, and Gouraud (3) shaded display modes.
• Switches to cull (B)ackfacing polygons and to display polygon (N)ormals.
• Parallelpiped lattice with user definable subdivisions in the U, V, and W directions.
• (F)reezing the lattice to start deformations. FFDs can only be performed on a frozen lattice. Un(F)reezing the lattice will result in a new lattice being created for additional deformations.
• Deformation modes: lattice (C)ontrol point (CP) manipulation and (D)irect manipulation of surface points. Currently, only vertices of the surface are selectable for manipulation.
• Miscellanous: (H)ide lattice, Undo (CTRL-Z), and (U)nselect all selected points. Undo buffers update everytime a mouse is clicked.
• Mouse (Orientation):
  • Button-1: Screen space X-Y translation.
  • Button-2: Screen space Z translation.
  • Button-3: Trackball rotation.
• Mouse (Unfrozen lattice):
  • Ctrl-Button-1: Expand lattice in U direction.
  • Ctrl-Button-2: Expand lattice in V direction.
  • Ctrl-Button-3: Expand lattice in W direction.
• Mouse (Frozen lattice):
  • Button 1: Addint and removing single CPs.
  • Shift-Button-1 + Drag: Adding and removing multiple CPs.
  • Ctrl-Button-1: Model space X-Y translation.
  • Ctrl-Button-2: Model space Z translation.
• Mouse (Frozen lattice with (T)ranslate w.r.t. Screen modifier):
  • Ctrl-Button-1: Screen space X-Y translation.
  • Ctrl-Button-2: Screen space Z translation.

Implementation:

• File format: Only triangular data in OBJ format currently supported. Face normals are calculated from the data.
• Lattice:
  • Model coordinates converted to local hyperpatch coordinates as described in presentation.
  • Arbitrary degree tensor product Bezier volume as lattice.
  • Arbitrarily limited degree in each dimension to 5 (for interactivity reasons in direct manipulation).
• Evaluator: Implemented Mann-DeRose evaluation scheme. Trilinear interpolation not possible with arbitrary degree in each dimension. Did not want the overhead in recursive subdivision evaluation. Evaluated fully instead of stopping one step short as I didn't need normals for the point in the volume (which is different from the normals for the point the the polygon). More efficient (see paper for 2D case analysis).
• Point Selection:
  • Uses OpenGL selection buffer.
  • Direct manipulation selects model vertices. Other options. I tried reversing the OpenGL transformations (commented out) but had problems reading from depth buffer. Once this is done, integration is trivial.
  • Multiple selection of lattice CPs can be improved by selecting area first, then defining a plane parallel to screen and allowing the user to select control points in depth order. Out of time.
• Lattice FFD (Sederberg, Parry):
  • Deformed model coordinates are obtained by evaluating tensor product volume equation using the displaced CPs.
  • Optimized code to avoid unnecessary evaluations (due to order of user actions).
• Direct Manipulation FFD (Hsu, Hughes, Kaufman):
  • Chose this scheme over Bartels and Beatty because less variables to experimentally determine. Also, least squares for an underdetermined system gives solution that movies the CPs the least amount. Also, we don't have the problems described at the end of the Bartels and Beatty paper.
  • Moore-Penrose generalized inverse computed. Simplified computation using SVD by hand (since B is a row matrix). (Wrong interpretation of the paper before--which was why I didn't get their method to work).
  • Separate code to compute Bezier basis functions. If speed is an issue, we can compute these functions in the Mann-DeRose evaluation but it will take an obscene amount of memory because we have to store all the basis functions for all vertices the last deformation in memory.
  • Only single point constraint implemented.
  • Control lattice displayed on deformation.
• Screen space translations:
  • Computed using inverse of OpenGL matrix transformations.
  • Retained model space translations: in some cases it is easier to manipulate model by translating this way.
  • Extension using Marryat's manipulation mapping not completed. However, the same effect has been achived with my screen space translation.

Results:

• Fairly interactive rates. With a 5x5x5 lattice and 5000 polygon model, direct manipulation of one vertex requires approx 1-2 seconds. One lattice CP manipulation takes < 1 second.
• See presentation for images.

Time blackholes:

• Making the user-interface usable.
• Picking of exact surface point in the volume using OpenGL depth buffer.
• Stuff partially implemented mentioned above.

Analysis:

• Easy method to manipulate models and fairly intuitive.
• See presentation.

Possible Extensions:

• Adaptive refinement of mesh after deformation to smooth model (Griessmair, Purgathofer, Gain, Dodgson).
• Extended FFDs (Coquillart).
• Multiple lattices and enforcement of continuity conditions between them (plus loading and saving features).
• B-Spline tensor product volumes: Mann-DeRose evaluator and B-spline basis function evaluator already done. Can do lattice CP deformation but direct manipulation not completed. Need to introduce extra constraints on borders of lattice to preserve full multiplicity (Hsu et. al paper).
• Multiple point constraint for direct manipulation.
• Enchance OBJ format importer.
• Complete Marryat's screen space translation.
• Complete screen space point selection.
• Complete plane selection method.
• Addition of cube, cylinder, sphere, and plane primitives with user-definable resolution controls.
• Addition of Bezier or B-spline surface primitives (Mann-DeRose already gives evaluation and tesselation is trivial).

References:

• My project presentation.

• Barr: Global and Local Deformations of Solid Primitives.
• Sederberg and Parry: Free-form Deformation of Solid Geometric Models.
• Coquillart: Extended Free-form Deformation: A Sculpturing Tool for 3D Geometric Modellng.

• Bartels and Beatty: A Technique for the Direct Manipulation of Spline Curves.
• Hsu, Hughes, and Kaufman: Direct Manipulation of Free-form Deformations.

• Mann and DeRose: Computing Values and Derivatives of Bezier and B-spline Tensor Products.
• Chang and Rockwood: A Generalized de Casteljau Approach to 3D Free-form Deformation.
• GriessMair and Purgathofer: Deformation of Solids with Trivariate B-Splines.
• Gain and Dodgson: Adaptive Refinement and Decimation under Free-form Deformation.
• Marryat Ma: Masters Thesis (in progress).
• Thanks to Steve Mann for guidance.
• Public domain models from Avalon and Viewpoint Datalabs.