Free Form Deformation(FFD):

By B4506024李天行

The unique aspect of this deformation is instead of deforming the object directly, we embed the object in a space, which is to be deformed and the object will be deformed accordingly.

The space we choose is called a FFD block, or Bezier volume, which consists of one or a number of Bezier hyperpatches. Each hyperpatch is a 4×4×4 space.(4 stands for 4 control points; in other words, there exist 64 control points for each such space) Each single tricubic Bezier hyperpatch is defined as :

equ.1

where are Bernstein polynomial of degree 3.The hyperpatch is specified by a three-dimensional grid of 64 control points and defines a volume of space parametrized by the three parameters u, v, and w where u, v, w  [0,1].

The undeformed FFD block consists of a rectangular lattice of control points arranged along three mutually perpendicular axes. Let the three sides be represented by the vectors (S,T,U). We defined the FFD block to be an array of (3l + 1)×(3m +1) ×( 3n +1) control points. Or, equivalently, a stack of l×m×n hyperpatches. The steps involved in deforming an object embedded in this FFD block proceed as follows:

  1. Determine the positions of the vertices in lattice space:

We set up a local parametric coordinate system of the FFD block, termed ‘lattice space’, given by:

P(s, t, u) = + sS + tT + uUequ.2

Whereis the origin of the local coordinate system(a corner of the FFD block) and S, T, and U lies along the edges of the volume. Since the magnitudes of these vectors reflect the dimensions of the volume, it follows that any point interior to the volume has lattice space coordinates (s,t,u) where s,t,u  [0,1]. We assign each vertex of a triangle in such space its own (s,t,u) triple, which stay with them unchanged throughout the deformation process. For vertexes not in the FFD block, they will not be assigned such a triple; therefore they will not be affected by the deformation.

  1. Deform the FFD block:

This is achieved by moving the control points from their undisplaced, lattice positions. As in the case of Bezier curve and surface patches there are meaningful relationships between the deformation and the placement of control points. The lattice space coordinates of a point now record only its parametric position within the FFD block. Varying u, say, now moves us along a Bezier curve (whereas undeformed we could have moved along a straight line) and similarly varying, say s and t move along the surface of a Bezier patch (whereas undeformedewe could have moved along a plane).

  1. Determine the deformed positions of the vertices:

After the deformation, the object space and lattice space are obviously different. Now we have to calculate the new position of each affected vertex due to the change of lattice space. First if there are more than one hyperpatch, we have to figure within which hyperpatch the vertex is and transform its original (s,t,u) triple into a new, say (u, v, w) triple where u,v,w  [0,1], which represent the local coordinate within only that hyperpatch. Then we feed the (u, v, w) into the equ.1 to get the deformed position of the vertex. (u, v, w) can be calculated as follows:

(u, v, w) = (l×s – index_s, m×t – index_t, n×u – index_u)equ.3

where (index_s, index_t, index_u ) is the index to the hyperpatch.

About our Deformation Editor:

When you press the button with scissors on it, you’ll get a new tool bar at the bottom of the window. Immediately before that, you’ll first be asked to input some details about the FFD block for operation. We describe the functionality of each button as follows:

  1. Fix FFD Block Position:

You have to fix the FFD block position before any attempt to start the deformation. When this button is not pressed, only translation and rotation can be done and can only be applied to the FFD block. So at this stage, you have to set the FFD block at the intended position. If you want to see from different angles to check if the block position is right, you have to fix the block position, that is to say to wrap the part of object intended with the FFD block. And then all previous actions (translation, rotation, view rotation camera rotation...) done to the object can be re-operated. Every time you fix the FFD block position, the local lattice coordinate, (s, t, u) triples mentioned above, will be assigned to each vertex of the triangles.

<Implementation>:

The assignment of the (s, t, u) triples has to be achieved by means of the knowledge of linear transformation between different coordinate spaces. Here we have are the global coordinate of each vertex of triangles and the S, T, U, which are the three perpendicular axes of the local lattice in global coordinate representation. How do we solve the (s,t ,u) triples? We make use of inverse of the matrix M, the columns of which are S, T, U. The multiplication of the inverse of M and the coordinate of the vertexes will reveal the local coordinate we need. Yet, since s, t, u  [0,1], we’ll further normalize the coordinate we derived to conform to the constraint. There are times that not all the vertexes are wrapped in the FFD block. In such situation, those vertexes not in the FFD block will be excluded from participating in the deformation process.

  1. Select One Control Point:

Select control points you want to drag one at a time; when you want to deselect it, just select it again.

<Implementation>:

I simply just mark those control points if the position of a mouse click falls in a predefined range to their projective (x, y).

Select All Control Points of A Hyperpatch:

Select control points as a group of one hyperpatch.

<Implementation>:

As long as one control point of a hyperpatch is selected, I just mark all the other control points in the same hyperpatch. Yet one more thing we have to take into consideration. If there are connected hyperpatches constituting a FFD block, there will be control points sharing. So those control points shared must also be selected in the nearby hyperpatches.

  1. Deselect All Control Points of A Hyperpatch:

Deselect control points as a group of one hyperpatch.

<Implementation>:

Just do the same thing as 2. with an opposite purpose.

  1. Deselect All Selected Control Points of All Hyperpatches:

Deselect all control points on the screen.

<Implementation>:

Traverse through all control points in the FFD block, and unmark them all.

  1. Drag Selected Control Points:

Drag the selected control points, by means of translation and rotation, to the intended position.

<Implementation>:

We apply the translation and rotation operations only to the control points.

  1. Deform:

The object will be deformed according to the position of the control points.

<Implementation>:

The detail is elaborated.

  1. Real Time Deform:

When this button is pressed, Deform button will be disabled, and the deformation will be done at real time; in other words, the object is to be deformed at the time you drag the control points.

<Implementation>:

The only difference between Deform and Real Time Deform is what they tell literally. For Deform, you have to press the Deform button to get the deformed object. For Real Time Deform, you can view the result while you are dragging the control points, the same as saying deforming the FFD block.

  1. Show/Hide FFD Block:

Show or hide the FFD block.

<Implementation>:

Not rendering the FFD block.

10. Record Deformation:

Record the current deformation. The timestamp will increase by 1.

<Implementation>:

Actually, considering a single triangle, there is a doubly linked list recording all the results of that triangle through the deformation process, including the original one; this is so because undo is allowed. There are of course a lot of unwanted results between the previous accepted one and the last satisfactory one. So when users decide to record the deformation, we will flush all the unwanted results of the deformation in the list and keep only the satisfactory ones.

11. Preview:

Play the current work so far.

<Implementation>:

Before previewing, the unwanted results in the doubly linked lists of all triangles will be flushed away. So the users will be able to viewing only the satisfactory ones.

12. Clip Setting:

Finish the deformation and start to fill other settings for the clip.

<Implementation>:

When all the deformation work is done, we can then edit the movement of the object. When this stage is reached, you can no longer continue deforming the object. This button will trigger a new dialog box, in which you can input the translation, rotation, view rotation, and camera rotation of each timestamp. You have to input these values with reference to the increasing order of the timestamp. In other words, you always start from timestamp 0 to the last timestamp. The ‘OK’ button of this dialog box will save the change and trigger the playback of the object up to the current timestamp you’re setting. When you are satisfied with the current setting, you press ‘Next One’ button to proceed to the next timestamp setting, and ‘Next One’ will only be enabled when ‘OK’ is ever pressed, and the change is saved. Repeat such process until all the settings are done, and you’ll be able to save the clip you’ve just created as a file.