## Free-Form Deformation

Cherry Zhang
David R. Cheriton School of Computer Science

[Homepage] [Project Page]

### Motivations

• Apply concepts of multi-variate tensor product of Bernstein polynomials from 2D Bézier curve to 3D geometry.
• Develop a simple tool for animating OBJ models.
• Explore the effectiveness of using control points in manipulating models.

### Background

• The Free-Form Deformation (FFD) used in this project was introduced by Sederberg and Parry [1]. In FFD, a geometric model is enclosed within a parallelepiped lattice of control points. The parallelepiped lattice is called the control polygon. The control polygon defines a local coordinate system. Any point on the geometric model has world coordinates of (x,y,z) also has local coordinates of (s,t,u). When the control points are displaced, the local coordinates of the model are re-evaluated using tensor product of trivariate Bernstein polynomials. The local coordinates are then converted to world coordinates. This technique provides an indirect yet effective way to deform geometric models.

### User Interface

• Feature 0: Model Transformations
The model can be translated and rotated along all x- ,y- and z-axis. It can also be scaled.
• Feature 1: Mode Switching
The application supports two modes: model transformation and control point manipulation. In both modes, model can be transformed. However in control point manipulation mode, control points can also be selected and transformed.
• Feature 2: Show/Hide Control Points/Axes
Control points and axes can be hidden after model manipulation.
• Feature 3: Select/Deselect Multiple Control Points
- x,y,z-axis: automatically select all the control points that are along the same x,y or z-axis as the selected control point.
- x,y,z-plane: automatically select all the control points that are on the same x,y or z-plane as the selected control points.
- deselect all: deselect all control points.
• Feature 4: Bend X/Y/Z
Only one bend operation can be selected at a time. Slider is used to control the degree of bending.
• Feature 5: Double Twist X/Y/Z
Control points are twisted in opposite directions about the center plane of the control polygon. Slider is used to control the degree of twisting.
• Feature 6: Single Twist X/Y/Z
Control points are twisted in the same direction about one side plane of the control polygon. Slider is used to control the degree of twisting
• Feature 7: Reset Control Points and Transformations
Reset model orientation and/or control point positions.
• Feature 8: Dynamic Manual and Mode Display
A message box is implemented to dynamically provide users with instructions.
• Feature 9: Adjustable Number of Control Points
Users are given the freedom to adjust the number of control points along each axis. The minimum number of control points is 1 and maximum is 10.

### Implementation Details

• Objective 0: User Interface Setup and Model Manipulation
FLTK/OpenGL is used to implement the graphical user interface. Standard OpenGL rotation and translation matrices are used to implement model transformations.
• Objective 1: Import OBJ and MTL Files
Implemented a function to parse standard OBJ and MTL files.
• Objective 2: Find Control Polygon and Compute Local Coordinates of the Model
The control polygon is a "bounding box" for the model. Figure 1 shows a control polygon with local coordinate system. X0 is the local origin and vectors S, T and U are the local axes. Each point on the model will have a local coordinate (s,t,u) with respect to the local axes. The control points are evenly distributed along each S-, T- and U-axis.
• Objective 3: Control Point Manipulation
Standard OpenGL "picking" technique is used to determine which control points are selected.
• Objective 4: Support Quick Multiple Control Points Selection
Control points with the same local x-,y- or z-axis/planes can be selected by pressing a button. Control points are stored in a 3D array so they are naturally grouped together, by the same s, t or u values.
• Objective 5: Implement Model Deformation Algorithm
Each vertex of the OBJ model will have local coordinates (s,t,u). The deformation function is defined by a tensor product of trivariate Bernstein polynomials. The position of a deformed vertex is evaluated by the following:

• Figure 1: Evaluation of deformed vertex using tensor product of trivariate Bernstein polynomials.

where Pijk are the control points. All the coordinates are with respect to the local axes. The local coordinates are converted to world coordinates using a local-to-world transformation matrix.
• Objective 6: Implement Bending Operation
Bending operations are implemented in a similar way along x-, y- and z-axis. Bending is simulated by rotating planes of control points around local x-, y- or z-axis. A "zero-rotation" plane is defined to be one side of the control polygon. The angle of rotation increases as the plane of control points gets further away from the zero-rotation plan.
• Objective 7: Implement Double Twisting Operation
In terms of implementation, double twisting is similar to bending. The zero-rotation plane is defined to be the middle plane of the control polygon. Planes above and below the zero-rotation plane are rotated around the axis in a different direction.
• Objective 8: Implement Single Twisting Operation
Single twisting is similar to bending as well, except that control points/planes are rotated around a different axis.
• Objective 9: Support Change in Number of Control Points
When the number of control points changes, control polygon is re-computed, vertices of model are re-evaluated and the scene is re-rendered.

Figure 1: Control polygon and local coordinate system

### Extras

• Extra 0: Multiple Control Point Selection
Support for multiple control point selection is implemented because sometimes it is too slow to move one control point at a time. Also, chaning a single control point may not have a significant effect on the model.
• Extra 1: Separation of Single and Double Twist
The double twist operation was implemented based on the algorithms specified in [2]. Single twist was implemented by changing the "zero-rotation" plane in double twist from center of the control polygon to one side of the control polygon.
• Extra 2: Open OBJ models From File
This extra feature allows user to load their own models.
• Extra 3: User Control of Number of Control Points
This feature was implemented for studying the effects of control point movement on models. The details of the study is in Discussions
• Extra 4: Creation of Demo Videos
A few demo clips were created to show the features of the application.

### What I Have Learned

• Knowledge 0: Import OBJ and MTL files to FLTK/OpenGL application. (Objective 1)
• Knowledge 1: How to Implement algorithms to evaluate tensor product of trivariate Bernstein Polynomials. (Objective 5)
• Knowledge 2: Efficiently convert models from world-coordinate system to local-coordinate system and vice versa. (Objective 2)
• Knowledge 3: Implement various UI features using FLTK (Objective 0)
• Knowledge 4: How to define and simulate Bend and Twist operations on control polygons. (Objective 6,7,8)
• Knowledge 5: The difficulties in implementing direct manipulation features. (Discussions)
• Knowledge 6: The effects of global control points and the number of global points on the model. (Objective 9 and Discussions)

### Results/Demos

This text will be replaced

### Discussions

• Effect of Number of Control Points
Observation: The effect of control point movement on the model reduces as the more control points increases.
Explanation: The control points are global control points. As a result, all of them will have some impact on the model when they are moved. The amount of impact can be thought of as the "weight" of the control point. As the number of control points increases, the "weights" are more widely distributed. That is, the "weight" on each control point decreases. Therefore the effect of a single control point on the model reduces.
Screenshot: The left picture has 3 layers of control points in the Y direction. The middle picture has 5 and the right picture has 4. The control points in all the pictures were displaced a few units in the positive Y direction. It is obvious that the effect of the model (bird) is reduced when the number of control points increases.

Figure 2: Effect of control points on the same model.

• Challenges in Implementing Direct Manipulation
The current animating tool only allow users to manipulate models through control points. From time to time, users may want to modify points on the models directly. In addition, complex deformation operations often require a large number of control points resulting in screen clutter [3]. One solution to improve the usability of the deformation tool is to move control points in groups, which was implemented as an extra feature in this project. Another more challenging solution is to implement direct manipulation. Direct manipulation would allow users to "move this point on the model to that point". In order to implement direct manipulation, the following changes need to be done to the existing application:

- Instead of using Bernstein Polynomials, use B-Spline basis to gain local control properties.
- Some phantom control points (or knots) might be needed in the implementation.
- Define which vertices of the models can be used in direct manipulation. It is nearly impossible to allow ALL points on the model to be able to move. A new function must be implemented to find which vertex is chosen by the user.
- Control and interpret point movement. It is very challenging for the user to move a point in 3D space on a 2D screen. One possible solution is to implement multiple cameras/views to assist user in moving the point in 3D space. It is also very difficult to interpret user's intentions on moving a point. We could interpret the motion as "some translation along x-, y- or z-axis", or "some translation along the surface normal of the point".
- Re-evaluate model. We must implement functions to calculate which control points are affected by the direct manipulation. The algorithms will be similar to the direct manipulation of B-Spline curves. [3] provides with some details about the math and implementation.

Due to time constraints, direct manipulation is not implemented in this project.
• Assessment of the Application
Speed: The application can achieve excellent interactive rate even when the OBJ model consists of hundreds of vertices. The control points are drawn with an OpenGL display list as spheres with 5 quads. There is no noticeable delays in any transformations and manipulations.
Usability: The application is very simple to use. All the transformations can be performed with intuitive mouse controls. In addition, the dynamic manual box provides users with a quick reference to keyboard and mouse shortcuts.
Screenshot: Animation of a flying bird. Created using single-twist-z operation.

Figure 3: Animation of model. Simulated by single-twist along z-axis.

### Acknowledgement

I would like to acknowledge Professor Stephen Mann for all his generous help throughout the term. Professor Mann offered many insights and advice in designing of this project as well as algorithm implementation. Special thanks to my friend Calvin Ho, for providing me with his wonderful OBJ models. Calvin also helped me implement the mesh import/load functions. I would also like to thank Elodie Fourquet, for encouraging me to take this course, and providing valuable opinions on the design of this project.

### References

[1] Sederberg, Thomas W. and Parry, Scott R. Free-Form Deformation of Solid Geometric Models. In Proceedings of SIGGRAPH'86, In Computer Graphics20,4,pages 151-160, August 1986.
[2] Draper, Geoffrey M. and Egbert, Parris K. A Gestural Interface to Free-Form Deformation. In Proceedings of Graphics Interface, pages 113-120, 2003.
[3] Hsu, William M., Hughes, John F. and Kaufman, Henry. Direct Manipulation of Free-Form Deformations. In Computer Graphics, pages 177-184, 1992.
[4] http://seriss.com/people/erco/fltk/
[5] http://www.fltk.org/doc-1.0/toc.html