Matt Pharoah
Overview
My project implements freeform deformation with cubic B-spline patches. Evaluation is performed using the de Boor algorithm. I used cubic B-splines with full knot multiplicity at the edges so that the B-Spline is defined over the entire lattice.In addition to freeform deformation using the lattice of control points, I also implemented direct manipulation.
Core Project Objectives
(More detailed discussion on interesting objectives farther down)- Arbitrary Polygon Support
The program supports models made of any kind of polygons, including non-planar ones. - Triangular Bézier Patch Support
Triangular Bézier patches can be loaded as well, and can be tesselated to different degrees of precision. - Selection and Translation
Single control points and groups of control points can be selected and moved. - Smooth Translation
When moving control points, you have the option to pull other control points near your selection as well at a fraction of the distance of the selected points. This allows for smoother deformations, and can be used to stretch parts of the model. - Twist, Bend, and Scew
I implemented the twist, bend, and scew tools which work on the selected control points to create meaningful deformations. - Save and Load
The program can read .s3d files, including support for Bézier patches, and save in .s3d format.
Extra Objectives
- Direct Manipulation
I added support for direct manipulation using the least squares solution to minimize the change in control points. - Advanced Direct Manipulation
I improved my direct manipulation tool to give more control over how the surface is deformed. (Details below) - Save/Load Transformations
In addition to saving and loading in .s3d format, FFD transformations- independant of the model- can be saved into .ffd files (just binary data compressed with gzip) allowing a transformation to be applied to different models - Undo/Redo The application maintains an undo stack in a temporary file, and holds a redo stack in memory.
Discussion
Knot Multiplicity
Since I am using a cubic B-spline with full knot multiplicity at the edges, I need to invert the transformation for the initial lattice for points near the edges of the lattice. I used Maple to expand and simplify the transformation, then solved the resulting cubic equations for spline segments including knots with multiplicity higher than 1. For every point in the lattice, there is one real solution, and it can be solved exactly.Normals
My initial idea for computing the normals of deformed surfaces was to perform a change of basis to store the vertex normals with respect to the polygon's normal computed using the cross product, then reverting the basis after the transformation. This didn't work very well because the polygon shape is irrelevant to the normal at one particular vertex: the way the model is deformed at one edge of a triangle may be very different from how it is deformed at another vertex.I then realized that a much better approach would be to approximate the deformation at each vertex as an affine transformation. (Actually, just a linear combination since translation doesn't affect normals) To do this, I take 3 points very close to the vertex- each one being epsilon units along one axis. I then deform these points (and the original vertex) and define the linear transformation by the positions of the deformed points relative to the deformed vertex. I can then take the inverse transpose of this linear transformation to get the normal transformation. It ended up working very well, giving good results in most cases, keeping sharp edges sharp and smooth curves smooth.
Advanced Direct Manipulation
There are many free parameters involved in direct manipulation. To give more control over how the surface is deformed, I added "brush attributes" to the direct manipulation tool. The size of the brush determines how many control points should be changed, and the brush pressure determines how much the control points should move relative to each other.To solve the direct manipulation with these constraints, I simply multiply the blending functions at each control point by a value determined by its distance from the control point that most affects the point on the curve being manipulated and the brush pressure attribute. I then solve for that control point's new position, and all other control points within the brush size are moved by some multiple of this change, again determined by the pressure attribute and the control point's distance from the control point with the greatest effect on the surface point.
Screenshots
The twist tool in action
The bend tool
And shear as well
The translation tool with the pull option creating a smooth deformation (Transparency feature used here to see the control point lattice better)
The effect of different brush sizes for direct manipulation
Transformations can be combined together
They can be done at low quality for a more responsive program...
...then the quality can be increased afterwards
A transformation being applied to a cube
And the same transformation applied to a sphere
Room for Improvement
Some features that I didn't get around to implementing:- Support for more surfaces
Since freeform deformation applies a transformation from one volume to another, any type of model can be transformed. A possible extension could be to implement simple implicit surfaces such as cylinders, spheres, and cones. - Subdivide Polygons
As transformations are applied to a polygon mesh, the polygons can become large in areas where the deformation changes quickly. It would be usefull to be able to detect this and subdivide large polygons into smaller ones for better quality. - Improved Controls
Currently, it is awkward to move points towards and away from the camera as it requires the scroll wheel or rotating the view, which causes the points being dragged to move with the rotation. Instead of always rotating around (0,0,0), it would be better to rotate around the point being dragged by the mouse so that it is not moved when the user rotates. - Composite Deformations on Bézier Patches
Currently, when a deformation is applied and the lattice reset to an evenly spaced one, all Bézier patches are converted into a triangular mesh so it's tesselation value can no longer be changed. This can be worked around by saving and loading the transformation, which restores the ability to adjust the tesselation value, but it would be better to not tesselate when applying multiple deformations.
Bugs
- Sometimes, loading a composite deformation from an .ffd file results in a different transformation than it should.
Controls
Left click selects and moves control points.Middle click and drag rotates the camera, and the scroll wheel zooms in and out
Right click and drag pans the camera
Acknowledgements
A Gestural Interface to Free-Form Deformation, Geoffrey M. Draper and Parris Egbert, in Graphics Interface 2003, 2003, pages 113--120.Direct Manipulation of Free-Form Deformations (Hsu, 1992)
Thomas Sederberg and Scott Parry. "Free-Form Deformation of Solid Geometric Models": SIGGRAPH '86
wxWidgets