| • June 1998 • |
3D Soft ObjectsSuchit TiwariUniversity of Pune Bachelor of Engineering Computer Science & Engineering 1998-99 Thesis work submitted in partial fulfillment of Engineering Bachelor degree in Computer Science & Engineering Author's Contact: Email: srt@suchit-tiwari.org ©Suchit. This is a brief excerpt from a detailed PDF/DOC report. Complete report is available for download upon request. Just drop me a line. ABSTRACTOne of the major motivations of three-dimensional shape animation is to extend the degrees of freedom of conventional computer animation. Compared with traditional animation, the computer animator is restricted to an environment where the virtual camera can be choreographed and objects can be moved. Great efforts are being made by mathematicians, computer scientists, programmers and computer animators, all over the world, to extract novelty and variety from these somewhat limited aspects. Importing the tricks of traditional animation into computer animation is difficult. One of the most important aspects of Disney-type animation is the ability to give characters pseudopersonality and was not available with three dimensional computer animators. Another attribute of traditional animation is shape distortion (called stretch & squeeze) that is used to highlight dynamic action such as deceleration due to collisions. The artistic domain of three-dimensional animation can be extended by the introduction of shape deformation into the field. Shape animation blurs the traditional distinction made in computer graphics between modeling and animating. In this paper, I am going to address this issue - Soft Object Animation. I will be talking about the general philosophy, mathematical theory, implementation algorithms and applications of Soft Object Animation.Keywords: Bezier Hyperpatch, Bernstein Blending, Free Form Deformation (FFD), EFFD, Curvilinear co-ordinate systems, Tweening, Inbetweening, Twisting, Bending, Tapering, Animation. 1. IntroductionSoft object animation blurs the traditional distinction made in computer graphics between modeling and animating. One can view soft object animation equally as either a modeling process where a different model is created for each frame, or as an animation process where we animate the data that represents the model. The distinction between modeling and animation thus breaks down – the two operations are now intimately linked. Because of this, the methods that are reviewed include work from areas where the original paper may have been a static graphics technique but which exhibited shape animation potential, as well as papers, which explicitly claim a shape animation technique. As it is most basic, the deformation is usually achieved by moving the vertices of a polygonal model or the control points of a parametric one; the animation is achieved by the choreography of this movement. The representational scheme generally places restrictions on the nature and extent of the deformation that is used. There are different methods of deformation of objects – depending upon the format in which the object is represented. They are as follows:Now, let’s take a look at each one of above. Polygonal Object DeformationGenerally, moving some of its vertices deforms a polygonal object. The vertices in a polygon mesh model cannot be treated as a set of independent particles, each possessing their own animation, because they have an implicit connectivity that must be ‘respected’ by any deformation. The deformation applies only to the vertices of the model – the newly deformed model is retrieved from the unaltered connectivity between vertices. Deformational schemes applied to polygonal objects are constrained by these connecting links between vertices. Problems occur if deformations are non-global or if the nature of the transformation is such that, for example, edges between vertices cross over when deformations are applied to the vertices. For example, we cannot twist a cube, represented as six surfaces without limit, and retain a structure suitable for rendering. There is major drawback in the deformation of the polygonal representation, which can generally be thought of as a three-dimensional alias problem. Problems occur when the deformation is too complex with respect to the object representation. The vertices can be thought of as sample points in three-dimensional space and the shape change or deformation as a function that has to be adequately sampled by these vertices. Deformations where the vertices, initially planar, are moved far apart and become non-planar have the effect of reducing the polygonal resolution of the deformed model, giving rise to degradation in silhouette edge alias and so on. The polygonal resolution constrains the nature of the deformation and this can only be overcome by subdividing or increasing the resolution of the polygonal object depending on the ‘severity’ of the deformation.Parametric Object DeformationThe most significant advantage the parametric representation enjoys over the polygonal one lies in the fact that it can handle a deformation of any complexity and still appear smooth. This is because in altering the positions of the control points we are merely changing the coefficients of the basis functions, that is, altering the functional description of the surface. The deformed parametric surface is therefore in no sense less well defined that non-deformed object. Whether or not the deformed object is a faithful representation of the deformation itself is another matter – the point is that whatever the deformation a parametrically deformed surface will be immune to the degradation associated with deformed polygonal objects. The deformation of parametric surfaces is just as prone to three-dimensional alias problem as the polygonal representation in that it may not accurately reflect the deformation we intended to make. Furthermore, this problem is exacerbated in the parametric case since, in general, the control points of a parametric object are more sparsely distributed than the vertices of a polygonal object of comparable curvature. Applying a localized deformation to a parametric object that falls between control points will result in no deformation whatsoever. The work of, mathematicians, Forsey and Bartles is particularly important in this context. It states: It is generally a more difficult problem to represent objects parametrically than polygonal representation. The parametric surface cannot easily represent objects possessing complicated topology. This is because by far the most established type of parametric surface is the rectangular bicubic patch – consequently only objects with a rectilinear topology can be represented. Researches has been conducted into alternative patch shapes, such as the triangular patch, but have so far yielded little success. The restrictions placed upon the type of deformation applicable to the parametric representation arise mainly from the properties of the basis functions used and the need to maintain continuity across adjacent patches. For many practical applications B-splines are preferred over Bezier patches since they give rise to smooth surfaces.Deformation Independent of RepresentationIn this section I will cover two developments in deformation techniques that are particularly useful in that they are independent of representation. In practice, this means they can be applied equally to both the polygonal and the parametric representation. The first represents a generalization of the standard modeling operations facilitating nonlinear global deformations of objects. The second is a unique and powerful approach that deforms objects by deforming the space in which the object is embedded.Nonlinear Global DeformationSuppose we wish to perform a standard modeling operation, such as scaling, on an object. The operation, usually in the form of a transformation matrix, is applied to each of the vertices (or control points) in turn. Throughout this procedure the transformation matrix does not change. The mathematician – Barr has invented this method. The innovation behind Barr’s approach is to alter the transformation while it is being applied to the object. The way in which the transformation is altered becomes a function of the position at which it is applied. It is as if the transformation itself undergoes a transformation before it is applied to the object. Three of Barr’s transformations are tapering, twisting and bending. Barr uses a formula definition for the transformations:(X, Y, Z) = F (x, y, z) Where (x, y, z) is a vertex in an undeformed solid and (X, Y, Z) is the position of the deformed vertex. Using this notation the standard scaling transformation, for example, is: (X, Y, Z) = (sxx, syy, szz) Where (sxx, syy, szz) are the scaling coefficients along the three axes. Tapering is easily developed from scaling. We choose a tapering axis and differentially scale the other two components. If effect we are scaling a scaling transformation. Thus to taper an object along its z-axis, we just scale the scaling along the x- and y-axes as a function of z: (X, Y, Z) = (rx, ry, z) Where: r = f (z) is a linear or nonlinear tapering profile or function. Global axial twisting can be developed as a differential rotation just as tapering is a differential scaling. In effect, all we are doing is scaling the rotation angle of rotation transformation. To rotate an object through an angle Ø about the z-axis we apply: (X, Y, Z) = (xcosØ - ysinØ, xsinØ + ycosØ, z) Now if we allow the amount of rotation to vary as a function of z the object will be twisted. This is done by setting:
Ø = f(z)
where f(z) specifies the rate of twist per unit length along the z-axis.
Finally, a global linear bend along an axis is a composite transformation comprising a bent region and a region outside the bent region where the deformation is a rotation and a translation. Barr defines a bend region along the y-axis
as ymin <= y <= ymax . The radius of curvature of the bend is 1/k and the center of the bend is at
y=y0. The bending angle is:
The deforming transformation is given by:
X = x
Y = -sinØ (z - 1/k) + y0 ymin <= y <= ymax
= -sinØ (z - 1/k) + y0 + cosØ (y - ymin) y < ymin
= -sinØ (z - 1/k) + y0 + cosØ (y - ymax) y > ymax
Z = cosØ (z - 1/k) + 1/k ymin <= y <= ymax
= cosØ (z - 1/k) + 1/k + sinØ (y - ymin) y < ymin
= cosØ (z - 1/k) + 1/k + sinØ (y - ymax) y > ymax
Figure 1 shows an example of each of these three transformations in turn. The deformation on the cube is an intuitive reflection of the effects and the same transformations are applied to the Utah teapot. More general shape change can be achieved by using a combination of these transformations. To summarize, Barr extends the range of modelling transformations by allowing the transformations themselves to be modified according to where they are applied in space. In case of twisting and tapering this modification is achieved by the use of a profile curve F(z) that weights the scaling or rotation angle, respectively. A generalization of this technique, which takes a transformation and modifies it according to when it appears in time, is very useful in that it provides us with a powerful and flexible tool for animating deformations. For illustration here I have taken a kettle and a box. The ‘severity’ of deformation can be realized by looking at the box. The process of deformation was carried out using Barr’s Algorithm. The first pair, from top to bottom, is undeformed object. Second deformation is tapering effect. Third deformation is twisting. Fourth deformation is Bending.
After applying transformations to individual vertices of the objects, the objects are then to be projected in onto 2D-screen space from 3D space. The reconstruction details may vary from person to person. I have used polygonal representation. The order in which the vertices are to be entered is counterclockwise direction. 2. Free Form DeformationThe second representational-independent deformation technique we shall look at is Free Form Deformation (FFD). Where Barr’s deformations are restricted to particular transformations, this technique, developed by Sederberg, is completely general. In this respect it is the most flexible of the two and eminently suitable for soft object animation.The unique aspect of the method is that instead of deforming the object directly, the object is embedded in a space that is then deformed. Sederberg uses the physical analogy of a parallelepiped of clear flexible plastic, in which is embedded one or even a number of objects. The plastic is deformed and the objects change shape in a manner that Sederberg describes as being ‘intuitively consistent’.
As explained earlier, the elastic container with object placed inside it deforms the object. Here we are actually deforming the space around it. Thomas W. Sederberg did the original mathematical work from Brigham Young University. He and Scott R. Pary at the ACM SIGGRAPH Conference presented that in 1986. The method is so important that it was worth a patent (patent #4,821,214 dated April 11, 1989, owned by Viewpoint Datalabs International, Inc.). Another useful analogy of the process is the deformation of two-dimensional space using a bicubic surface patch. Let us represent two-dimensional space as a grid of squares that are mapped onto an initially planar, square surface patch. If we move the control points of this surface patch arbitrarily then the grid of squares and hence two-dimensional space become distorted. Moreover, we can track how a point distorts by substituting its u, v-coordinates into patch definition to find its new position. This process is shown in Figure 3. The formulation, which governs this process, is Bernstein Blending.
where: pij are control points, Bi and Bj are Bernstein Blending functions of the form: B0 (u) = u3 B1 (u) = 3u2(1-u) B2 (u) = 3u(1-u)2 B3 (u) = (1-u)3The process of deformation is carried out using a simple algorithm as:
In Figure 3, the original object is a wheel with spokes (Red in color). It is first enclosed with a grid (Light Gray in color). When that reference grid is deformed, the space around the object is also deformed (Blue in color) resulting in deformed object.
The above discussion can be extended directly to include 3D objects. The change however will be that instead of using bicubic Bezier patches, we have to go for tricubic Bezier Hyperpatches. A single tricubic Bezier Hyperpatch is defined as:
And the object will be in 3D space. Therefore the extents will be three pairs – (Xmin, Xmax), (Ymin, Ymax) and (Zmin, Zmax). With respect to these pairs, all the parametric triplets will be calculated for each of the vertices. Those triplets will be (u, v, w).
Using Tricubic Bezier Hyper Patch Modelling with Free Form Deformation, I have written a program which deforms an object in 3D space. Let us take an example of deforming a bottle. From the animation sequence I have captured four frames for this illustration. (Refer to Figure 4.)
The bottle was created using simple sweep function. Its database was stored in RAW format, which consists of only vertices. Then it was transformed using Bernstein Blending Basis Functions. The curvilinear coordinate systems in three-dimensional space were also formed using the same equations. And finally mapping the vertices from undeformed to deformed coordinate system with projection on the screen plus connectivity produces the deformed object. The animation was implemented in a simple loop with the Bezier HyperSpace around the object being shifted towards left along its both the ends. This procedure gives bending effect. Other effects – like tapering, twisting, etc. can also be implemented as well. Free Form Deformation proves to be a very useful and intuitive tool for Computer Graphics applications. It is powerful yet simple! 3. ApplicationsFFD (Free Form Deformation) can be used to create professional animations and special effects. It is being used widely in advertisements. For example:
Above two incorporated FFD for animations. EFFDIntrinsic parallelepiped shape of the FFD block constrains the shape of the deformation. An EFFD block differs from an FFD block in that it allows such lattices to be a part of itself; the FFD block definition becomes a subset of the EFFD block definition, which can be made up of any type of lattice. To achieve EFFD, we first construct FFD lattice in rectangular fashion. Then it is bent, rotated, scaled to fit the desired shape. After that we can proceed with the deformation process. For EFFD, by definition, we cannot assume a simple connection between the rectilinear space and Bezier space. The calculation proceeds in two steps, for a given point on the object:
What’s Next?At this point, to make things interesting and to explore potential of FFD, I’ll discuss how objects can be animated through the use of FFD. Two easy-to-implement techniques can be developed. The first one takes a sequence of transformation operations – that is scaling, translation, and rotation – and applies them to the 3-D object in small steps, each one creating a ‘frame’ of animation. For Example, let’s say that we wish to rotate one of the Bezier hyperpatches from 0 to 45 degrees. To create the animation, we can break down 45 degrees into 10 steps or 4.5 degrees per frame. Using a simple loop operation, we’ll have a counter that increments the rotation angle by 4.5 degrees. At each frame, the original data is deformed and saved to a file. The second method combines FFD and a technique called ‘tweening’. Let’s take the preceding example and apply FFD and tweening. The first step is to deform the original data by rotating Bezier hyperpatch 45 degrees and saving that object. Now we have two objects: the original, or undeformed, and the deformed one. Now tweening comes into action. Because each point in the undeformed object has a corresponding point in the deformed object, we can apply linear interpolation between both. In other words, for each point in the object, we’ll compute the following:(Point at frame) i = p_original + (p_deformed – p_original) * (i / total number of frames)This operation is computationally inexpensive compared to applying FFD at each frame. Remember that FFD has cubic time complexity. The drawback of FFD/tweening is that the deformed object must be closely similar to the original object; otherwise, the tweening operation will show an object morphing in a rather unnatural manner. In this sense, applying FFD at each frame is more consistent. Refer to Figure 5. It shows a letter E being deformed into letter Z. The intermediate frames have been predicted using inbetweening.
To learn more about the theoretical background, implementation details, and creative use of FFD, reader may refer to the references given on the next page. Check it out for yourself, try it, and HAVE FUN ! References:For intermediate to advanced readers I would recommend following books and articles, which give sophisticated treatment to the subject of FFD. In alphabetical order:
</snipped> ©Suchit. This is a brief excerpt from a detailed PDF/DOC report. Complete report is available for download upon request. Just drop me a line. |
| © Suchit. | |Top| |