BU GRS CS 680
Graduate Introduction to Computer Graphics

Readings for February 5, 1997

Participants

• Alia Atlas
  
• Timothy Frangioso
  
• Scott Harrison
  
• Leslie Kuczynski
  
• Shih-Jie Lin
  
• Geoffry Meek
  
• Romer Rosales
  
• Lavanya Viswanathan
  

Commentary

Tim Frangioso

Commentary 3

Date: 2/5/97

"Free-Form Deformation of Solid Geometric Models" By Thomas W. Sederberg and Scott R. Parry

This paper talks about the technique of deforming geometric objects in a free form manner. That is talking about a modeling process that is akin to sculpting and molding a lump of clay. Through the process described one is ale to shape and deform solid geometric objects and there parametric surface patches.

To describe the FFD think of a parallelepiped block of plastic. It is this plastic block that we will be shaping and molded. The FFD is defined in terms of a tensor product trivariate Bernstein polynomial. "We begin by imposing a local coordinate system on a parallelepiped region." In this region there are three planes that are created one in the S direction one in the T direction and one in the U direction. When values are given to the control points on these planes a lattice structure is created. The actual deformation is accomplished by moving these P control points from there original positions.

There are three points to keep in mind the displaced point X the deformed position Xd and the control point P. The (s,t,u) coordinates are found by using the three given equations. Then the Bernstein Polynomial is solved using the (s,t,u) values and the P values to get the vector Xd.

The strength of this modeling technique is by far its simplicity and easy of use. The implementation of this technique is straight forward and not only easy to apply but easy to modify to more specific uses with other types of geometric models. The authors claim that this can be applied to any geometric model. The author also demonstrates how the FFD can be used to create local deformations on small pieces of the object being deformed. Another very useful result is that there are volume preserving and volume controlling FFD's that allow for direct control over the change in volume that goes on when the deformations take place. The combination of these different element creates a versatile tool for designing by and deforming objects. Its applications could be strongly used in throughout engineering and manufacturing or any area that needed to model a object before actual building it.

"Extended Free Form Deformation: A Sculpturing Tool for 3D Geometric Modeling" by Savine Coquillart

This paper describes a technique for creating a 3D modeling system that is able to deform objects arbitrarily. It is an extension of the Free Form Deformations that allows for the creation of arbitrarily shaped bumps and surfaces to be created.

The major extension of the FFD's is that the deformations are not created by simple moving control points. In the EFFD the deformations are controlled by the lattice structure itself. The EFFD solves a number of problems with the FFD. Namely, the number of control points affected and how they are effected is that proportional to the changes in shape. Also the shape of the region is controlled by the actual boundary that the lattice structure and the isoparametric lines and the neighboring control points. The major disadvantage on the FFD was that it was restricted to parallelepipedical objects because the shape of the lattice was restricting it. The EFFD allows for non-parallelepipedical lattices. This allows for all kinds of bending to be accomplished.

Sederberg and Parry, "Free-Form Deformation of Solid Geometric Models":

I have heard of Bezier curves and surface patches in passing before, and was able to sort of intuit their uses from this paper, but I really don't have a clear picture of what these objects are; some discussion of them would be useful. The technique Sederberg and Parry describe sounds extremely versatile, and there are lots of really neat effects one could produce with it. At the same time, however, the picture they present sounds almost too glowing; they only briefly gloss over some of their problems and shortcomings at the very end of the paper, problems that may seriously effect how successful FFDs really are as computational models. (For example, the very last item mentioned in the paper is the high computational cost of calculating some of the equations used to define FFDs. Just how serious is this cost problem?)

Coquillart, "Extended Free-Form Deformation: A Sculpturing Tool for 3E Geometric Modeling":

Coquillart proposes some interesting modifications to Sederberg's FFD technique. (Perhaps some of the problems I noted in the previous article were not as serious as I thought, given that Sederberg's system still appears to be in use.) Coquillart provides a good analysis of the problems with graphic styles involving control point manipuation. It is also interesting to speculate what other types of deformations might be possible with different lattice structures; although they might be difficult to work with, I can think of several lattice types (hexagonal, tetragonal, and so forth) that might be interesting to experiment with.

Free-Form Deformation of Solid Geometric Models -- Sederberg and Parry

Extended Free-Form Deformation: A Sculpturing Tool for 3D Geometric Modeling -- S.Coquillart

Authors Sederberg and Parry present an approach to free-form solid modeling. They strive to solve the problem of defining a solid geometric model of an object bounded by free-form surfaces. Their claim is that their method, free-form deformation (FFD) can deform surface primitives of any type (planes, quadratics, parametric surface patches, etc..), can be applied globally or locally and can deform solid models such that the volume is preserved.

Basically what they do is encase the solid(s) to be deformed inside a lattice structure which I think of as sort of a cage that has bars on the inside. If the cage had joints at all intersecting bars, then you could imaging being able to bend the cage. The joints I refer to are what are referred to as control points in the paper. Additionally, if you could pull or push on the cage joints, you could again change its shape although this time the effect would be different from merely bending it (this and the above are global deformation). Now, if you had more than one cage, you could image joining them together at some of the joints and as long as you somehow fixed those joints from moving you could move any of the cages while the other ones stayed in place (this is local deformation).

As the shape of the lattice structure changes so does the shape of the encased solids. Since the lattice and the solids are mathematical models, the actual changes in the positions of the encased solids needs to be computed. That is, a mapping from the original location to the newly deformed location must occur. This is accomplished by first computing the 3-D position of the point before deformation and then substituting these points into the deformation function which is defined by a trivariate tensor product Bernstein polynomial. The values returned, the Cartesian coordinates of points after deformation, are computed such that they are dependent upon where the control points, or cage joints, have been moved to.

An important question to ask, and one addressed by Coquillart, is, "how is the method proposed by Sederberg and Perry restrictive?". How close, or for that matter, how far away, is FFD to realizing its main objective which seems to be the desire to "sculpt" or "model as if with clay". Coquillart focuses on the restriction imposed by using a parallelepipedical lattice (my cage). He introduces his idea of extended free-form deformations (EFFD) where he extends the lattice structure to be non-parallelepipedical. He talks about the use of elementary prismatic lattices such as cylinders and the use of composite lattices, which are just elementary prismatic lattices welded together. Additionally he describes the use of non prismatic lattices such as spheres. The claim is, arbitrarily shaped deformations can be achieved including such things as random size bump formation. By varying the shape of the lattice, more control is given to the "sculptor", where the strictly parallelepipdical lattice imposes constraints on the shape, size and position of the retion to be deformed.

I did not see much difference in what Coquillart did in 1990 compared to Sederberg and Perry in 1986 besides the building of a more user friendly environment for solid modeling and the use of different shaped lattices. I would be surprised to hear that Sederberg and Perry did not experiment with lattice shapes other than parallelepipdical.

Free-Form Deformation of Solid Geometric Models

The authors describe a very interesting method of deforming a solid model. The interesting part to me is the fact that if the model is parametric, it will continue to be parametric after deformation. This seems pretty powerful when there is a need to design something that can be described mathematically at every step of the deformation (and be quickly computed). My other favorite topic was the volume preserving free-form deformations, the authors didnt seem to have a use for this, but I think it could be very useful in the design of containers or simply to preserve realism in a deformation of a more rigid model. Another caveat is the authors design system, which they describe as easy to use. This makes it appealing to users that normally might not consider computer aided design. (Artists, too!)

Extended Free-Form Deformation: A Sculpturing Tool for 3D Geometric Modeling

This paper is a logical extension of the previous paper. The authors method just about fully generalizes the Free-Form Deformation described by Parry and Sederberg. The author has four criteria that a deformation tool should fulfill. The first two, position and size of the deformed region are adequately fulfilled by Parry and Sederbergs model. She is aiming to preserve shape of the boundary and interior regions. My favorite is the generalization of the 3D lattice used to control the deformation. The author implements a user-defined, editable 3D lattice that yield a wide-range of deformations. After the lattice is edited to the users specification. Then it is associated with the surface to deform. The deformations can be nearly arbitrary thanks to the fact that the lattices can be associated with pieces of the surface, preserving the locality of the deformation by the properties of the lattice. In most cases, the continuity of the surface is also preserved.

Free-Form Deformation of Solid Geometric Models

Article Review

This paper present a technique for modeling 3D objects bounded by a free-form surface. Some of the approaches to this problem include combining existing free-form surface and solid modeling methods, trivariate parametric hyperpatch, modeling with algebra ic (implicit) surfaces, etc.

It uses a mapping R3->R3 through a trivariate tensor product Benstein polynomial. FFD is defined in terms of a tensor product. It is like defining a local coordinate system on a parallelpiped region, such that any point's coordinate can be found. A grid o f control points is imposed on the parallelpiped. The deformation is described by a movement of the control points. The control points represent the coefficient of the polynomial, the deformation can be (until certain degree) represented by the control po ints.

This model is valid when trying to perform local deformations, it is possible to maintain cross-boundary derivative continuity. In this case, it works by keeping some control points unmoved or to have a undeformed lattice at some points.

Volume change issues are also discussed, we can use the determinant of the Jacobian matrix over the region of deformation as a indicator of the volume change.

This technique can take objects with really basic geometry and mold them in such a way that they get a free-form surface. This transformation and representation of the result using a free-form solid model seems to be quite simple when implemented and at the same time to be inexpensive. An object can be then transformed a number of times, but I think that if we want to get meaningful or useful forms, we have to know how to modify the grid, and this might not be done so easily or in only one interaction.

I think that in general this technique can be more helpful as a design method than as a representation of free-form solids. It may be because the representation is imposed by the design method an it is not very efficient or portable.

Extended Free-Form Deformation: A Sculpturing Tool for 3D Geometric Modeling

Article Review

This deformation technique is independent of the geometric model. It uses the sculpturing metaphor for geometric models in order to deform an initally simple object.

In general this technique changes the shape of an existing surface by adding arbitrarily shaped bumps to it, of course it have to have the model of the bump, or by bending it along an arbitrary curve.

Free-form deformations consists of embedding the geometric model that has to be deformed into a parallelepipedical 3D lattice regularly subdivided. When the lattice is deformed, the model gets those deformations, this is done basically by a matching process and then moving the control points of the lattice.

The reason why an extended FFD was developed was because it is too restrictive to allow real sculpturing of surfaces. This restriction is due to the shape of the lattice. Size and position can be solved using FFD but not shape(*), also a circular bump on a surface is not possible.

EFFD is based on the use of non-parallelepipedical lattices, in this way we can achieve arbitrarily shaped deformations. Basically its implementation can be resumed in: editing an EFFD lattice, associating it with the surface, freezing an EFFD lattice and deforming the surface.

These EFFD lattices can be defined independently of the surface, and can be defined according to the user needs as toolboxes, for example.

In order to design EFFD lattices, this paper discusses prismatic lattices a the way it redefines the surface geometry (which is hidden from the user in the implementation). The prismatic lattice should be positioned in such a way that the surface passes t hrough the lattice. Deformations on the lattice will be transfered to deformations to the surface, the result will be that all surface point inside the EFFD will be deformed.

Two kind of prismatic laticces are discussed, elementary and composite, elementary are sometimes not enough, composite ones must be introduced to allow the design of some unconnected shapes. It is possible also to use non-prismatic lattices, such as spherical lattices. Lattices that are too complex seem to lead to unpredictable results.

Lattices can be defined by moving their control points. We can also create 3D lattices by using 2D ones or by merging already defined lattices, but we have to be careful if we want to preserve tangent continuity at the point where they are merged (some ca ses cannot be solved automatically). Some continuity vs complexity issues are discussed in the paper.

The association of the lattices with the surface should consider where we want the deformation of the model. When the lattice is freezed then the points on the surface are calculated with respect to the lattice space. When the lattice is deformed then all the transformations are applied to the surface.

Physical methods can model in a better way some objects, but they are too expensive. According to the authors, it is very efficient to deform a surface using th EFFD technique.

Also, a remark: it is not possible an exact representation of somal lattices such as the ciliyndrical lattice.

1) T. W. Sederberg and S. R. Parry. Free-form deformation of solid geometric models. In Proc. ACM SIGGRAPH, volume 20, 151-160, 1996.

This paper proposes a method of deformation of solid geometric models called Free Form Deformation (FFD). This model can be used on both parametric surface patches and solid geometric models. Parametric representations of surface are especially useful because they can be "sculptured" as easily as clay. Solid geometric models, however, lack this property but are useful in determining whether a given point lies within or outside a bounding surface. FFD can be applied to solid models as well as surfaces or polygonal data and, hence, it is a highly versatile tool.

Another very useful property of FFDs is that they can be applied locally to a particular patch of the given surface while all other parts of the surface are kept intact. This makes FFD a more desirable technique than refinement techniques that are non-local and cause regions that are far from the region of interest to be refined as well. The authors show a very interesting example of the local deformation of one end of a metal rod to the mouthpiece of a telephone to illustrate this advantage of FFD.

Free-form surfaces used in engineering design fall into four categories: (a) aesthetic surfaces where the visual apperance of the final object is the primary goal, (b) fairings or duct surfaces where one has to compute a surface transition between two other surfaces of different cross-section, (c) blends and fillets which require the smooth intersection of two other surfaces, and (d) functional or fitted surfaces, where high geometric constraint is imposed on the designed object to cater to a given functional requirement. The authors claim that FFD can be used to create aesthetic surfaces and fairings. Some blends and functional surfaces may also be possible.

The algorithm proposed by the authors seems very straightforward. The authors use a tensor product trivariate Bernstein polynomial for the transformation but other polynomials, such as the B-spline or the surface Bezier polynomials, may also be used for this purpose. The algorithm involves defining a set of equally distant control points on the surface of a parallelopiped and locally transforming these points and the regions between them to get the final shape. The authors also describe various ways of controlling the continuity of two adjacent surfaces to the kth derivative. Methods for local deformations and for volume deformations with or without maintaining constant volume are also described. Several interesting examples are also shown to illustrate the possibilities of using the algorithm.

The authors also mention some disadvantages of FFD. It cannot perform blending, filleting or create functional surfaces. Although local deformations are possible, it is not possible to control the shape of the boundary between the deformed and undeformed portions of the objects. This boundary is made planar and complex shapes require highly complicated procedures. Finally the use of trivariate Bernstein polynomials increase the computational time significantly.

2) S. Coquillart. Extended free-form deformation. In Proc. ACM SIGGRAPH, 187-196, 1990.

This paper proposes an extension of the FFD algorithm suggested by Sederberg and Parry and this new algorithm is called EFFD (Extended FFD). This is an interactive technique independent of the geometric model. The author begins by discussing certain problems faced by existing techniques. First, the designing of large bumps on the surface of an object would require that the user move several control points while it may even be impossible to design small bumps; in other words, the number of control points that the user has to move depends on the size of the deformed region rather than on its shape. Second, the shape of the deformed region is constrained to be specified by the position of neighboring control points; this makes it almost impossible to design a bump with a circular boundary. Third, the position of the deformed region is imposed by the position of the control points since only the control points can be moved.

The FFD algorithm proposed by Sederberg and Parry used a parallelpiped of control points. Coquillart extends this algorithm so that the control points lie on a non-parallelpiped lattice so that the user has the flexibility of specifying where the control points are. This gives the user the ability to create arbitrarily shaped boundaries for deformed regions. The EFFD technique consists of four steps: (a) editing an EFFD lattice, (b) associating an EFFD lattice with the surface, (c) "freezing" an EFFD lattice, and (d) deforming the surface.

The algorithm proposed by Coquillart looks simple to implement. The suthor acknowledges the fact that the results obtained are not as natural as those obtained using physical methods but it is computationally less expensive than physical methods and this may sometimes be useful. Coquillart claims that "only a few minutes" were needed to implement the examples shown in the paper.

Stan Sclaroff

Created:  Jan 21, 1997

Last Modified: Jan 30, 1997