Accesses:  |
| Maverick Development for Agile development |
Inbetweening Using a Physically Based Model
and Nonlinear Path Interpolation
A Thesis
Presented to the
Department of Computer Science
Brigham Young University
In Partial Fulfillment
of the Requirements for the Degree
Master of Science
by
Geoffrey Slinker
October 1992
This thesis, by Geoffrey Slinker is accepted in its present form by the Department of Computer Science of Brigham Young University as satisfying the thesis requirement for the degree of Master of Science.
________________________________________
Robert P. Burton, Committee Chairman
________________________________________
Thomas W. Sederberg, Committee Member
_____________ ________________________________________ ________________ ________________________________________ ________________
Date David W. Embley, Graduate Coordinator
Acknowledgments
I express my sincere appreciation to Dr. Robert P. Burton. Without his encouragement, his expression of confidence in my skills and his unique approach to the graduate experience, I would not have continued my education and received this Master of Science degree.
Also, I thank Dr. Thomas W. Sederberg for his kindness and the many meaningful insights and ideas.
I thank my parents, Durwood and Emma Slinker. Without their financial support and understanding, it would have been impossible to continue my education.
Finally, and most importantly I thank my wife Shannon. Without her support and understanding I would not have been able to finish this degree. There are many “all nighters” that are necessary to complete a Masters Degree and I hope the time away from my family will prove to be worth it.
Table of Contents
Chapter 1 ..................................................................................................... 1
1.1 Introduction................................................................................. 1
Chapter 2 ..................................................................................................... 5
2.1 Thesis Statement....................................................................... 5
2.2 Physical Model........................................................................... 5
2.3 Nonlinear Interpolation............................................................... 5
Chapter 3 ..................................................................................................... 9
3.1 Purpose of Physical Model....................................................... 9
3.2 Description of Physical Model.................................................. 9
3.3 Results of Physical Model......................................................... 11
Chapter 4 ..................................................................................................... 16
4.1 Rigid Body Motion..................................................................... 16
4.2 Q-Curves..................................................................................... 16
4.3 New Attribute of Q-Curves........................................................ 20
Chapter 5 ..................................................................................................... 23
5.1 Nonlinear Interpolation............................................................... 23
5.2 Problem of Linear Interpolation................................................ 23
5.3 Path Equation Candidates....................................................... 24
5.4 Bézier Curve for Nonlinear Paths............................................. 27
Chapter 6 ..................................................................................................... 38
6.1 Results of Nonlinear Interpolation............................................. 38
Chapter 7 ..................................................................................................... 49
7.1 Comparison to Hand Drawn Inbetweens................................ 49
7.2 Joints........................................................................................... 49
7.3 Results of Joints......................................................................... 50
Chapter 8 ..................................................................................................... 58
8.1 Conclusions................................................................................ 58
8.2 Further Work............................................................................... 59
Bibliography ................................................................................................... 60
List of Figures
Figure 2.1 Linear Inbetweening............................................................... 7
Figure 2.2 Nonlinear Inbetweening.......................................................... 7
Figure 3.1 Concord to Volkswagen......................................................... 11
Figure 3.2 Bird with Shrinking Feet......................................................... 12
Figure 3.3 Bird with Changing Tail Feathers.......................................... 12
Figure 3.4 C with Spike............................................................................ 12
Figure 3.5 E to F........................................................................................ 13
Figure 3.6 Twelve Vertices to Six Vertices............................................ 13
Figure 3.7 Eight Vertices to Three Vertices........................................... 13
Figure 3.8 Left Brace - Right Brace........................................................ 14
Figure 3.9 Pentagon to Triangle.............................................................. 14
Figure 3.10 Five Vertices to Three Vertices............................................ 15
Figure 4.1 Angles used by Q-Curves...................................................... 16
Figure 4.2 Angles used by the Q-Curve and the Plotted
Q-Curve.................................................................................... 18
Figure 4.3 Polygons for Q-Curve Analysis.............................................. 19
Figure 4.4 Q-Curves for Figure 4.3......................................................... 19
Figure 4.5 Zoom Showing Straight Line Q-Curve
of Figure 4.4........................................................................... 20
Figure 4.6 Two Triangles for Representing
Q-Curve Attribute.................................................................... 21
Figure 4.7 Q-Curves of Triangles in Figure 4.6...................................... 22
Figure 4.8 Zoom of Figure 4.7................................................................. 22
Figure 5.1 Rigid Body Rotation............................................................... 23
Figure 5.2 Rigid Body Motion - Linear Path........................................... 24
Figure 5.3 Parametric Cycloids............................................................... 26
Figure 5.4 Brachistochrone Problem...................................................... 26
Figure 5.5 Linear Interpolation at t = 0.5................................................. 28
Figure 5.6 Reshaped Interpolated Keyframe......................................... 29
Figure 5.7 Reshaped Vertex.................................................................... 30
Figure 5.8 Values Needed to Find P1.................................................... 31
Figure 5.9 The value of P1....................................................................... 32
Figure 5.10 Bézier Control Polygon and Curve........................................ 33
Figure 5.11 Ratios of Linear Interpolation................................................. 34
Figure 5.12 Setup of Linear Interpolation.................................................. 35
Figure 5.13 Lengths of Line Segments..................................................... 36
Figure 6.1.a Linear Interpolation of Square............................................... 40
Figure 6.1.b Nonlinear Interpolation of Square.......................................... 41
Figure 6.1.c Linear and Nonlinear Interpolation of Square...................... 42
Figure 6.2.a Linear Interpolation of Rectangle with Paths........................ 43
Figure 6.2.b Linear Interpolation of Rectangle.......................................... 44
Figure 6.2.c Nonlinear Interpolation of Rectangle
with Paths................................................................................ 45
Figure 6.2.d Nonlinear Interpolation of Rectangle..................................... 46
Figure 6.2.e Linear and Nonlinear Interpolation
of Rectangle............................................................................ 47
Figure 7.1 Joint Method............................................................................ 51
Figure 7.2 Jointed Box with Pointed Top................................................ 53
Figure 7.3a Linear Interpolation of Walk................................................... 54
Figure 7.3b Nonlinear Interpolation of Walk.............................................. 54
Figure 7.3c Nonlinear Jointed Interpolation of Walk................................ 55
Figure 7.4a Linear Interpolation of Walk................................................... 56
Figure 7.4b Nonlinear Interpolation of Walk.............................................. 56
Figure 7.4c Nonlinear Jointed Interpolation of Walk................................ 56
Figure 7.4d Hand Drawn Interpolation....................................................... 57
Chapter 1
1.1 Introduction
Computer assisted animation is the general topic of the thesis. Precisely, the thesis deals with the problem of inbetweening in the animation paradigm.
Inbetweening refers to the laborious task of drawing the images of an animation, such as a cartoon, that fall inbetween the keyframes. Keyframes are images showing important instances in the animation. For example, an animator draws a picture of a baseball player about to swing the bat. Then the animator draws another picture of the player after he completes the swing. These drawings are “keyframes.” Keyframes indicate important events or junctions. To complete the animation someone must draw all the inbetween frames of the player’s swing. The number of inbetween frames depends on the length of the animation sequence, and the rate of display needed to create the illusion of smooth motion.
The perception of smooth, continuous motion from the rapid display of static images occurs because the human visual system maintains each image momentarily after the image passes. This phenomenon is known as “persistence of vision” [1]. The speed necessary to achieve this illusion is approximately 24 frames per second. For a 30 minute cartoon, 43,200 images are drawn. With this in mind, the task of making a full-length animated motion picture seems overwhelming.
Computer Assisted Animation (CAA) largely relieves the animator of the task of drawing this enormous amount of frames. The computer is a natural candidate for doing this highly repetitive and somewhat mundane task. The recent rebirth of full length animated features has provoked a renewed interest in CAA, specifically in increasing the quality and the speed at which the computer is able to generate these images.
CAA has long challenged computer scientists and engineers. Catmull [2] discusses several problems in CAA, noting that the rigidity of the then existing systems was cumbersome for the animators to use. Keyframes were constrained to have the same number of curves, and in proper order for the system to compute the inbetween frames. Reeves [3] suggests using surface patches networked together to provide continuity between frames. These patch networks are constructed from Coons patches using a bilinear interpolation scheme along the patch boundaries.
A method known as Animated Free-Form Deformation is proposed in [5]. This technique relies on the Free Form Deformation (FFD) technique developed by Sederberg in [4]. The 2-D technique gives impressive results that are useful in CAA and CAD.
In 1992 an innovative technique for inbetweening was developed by Sederberg and Greenwood [6]. Sederberg describes the method as follows:
[1]This technique treats corresponding polygons in the two keyframes as if they were made of wire and determines how to bend and stretch one keyframe into the other using the least amount of work.
These bending and stretching equations are complex. This precludes their use with slower personal computing systems when turnaround time is important. The complexity of the algorithm is the result of the many arithmetic functions that are used. The equation for stretching wire requires two exponentiations, three multiplications, two divisions, and two additions. The equation for bending requires one absolute value, two multiplications, one addition, one subtraction, and one division.
[6] is able to produce images with exceptional quality, demonstrating, what seems to be, intuition in the algorithm in associating the beginning and ending keyframes. [6] presents a new application of Bernstein based polynomials termed “Q-Curves.” Through the use of Q-Curves, calculation of the angles formed at vertices for the entire inbetween are done without calculating the interpolation. The algorithm penalizes angles that go through a zero degree change or that do not increase monitonically. It does not consider nonlinear interpolation as an option in the inbetweening algorithm.
Chapter 2
2.1 Thesis Statement
The thesis is based on the system proposed in [6]. The topics of this thesis are: 1) a new physically based model which gives work equations of less mathematical complexity (in terms of the number and type of operations) than the work equations of the proposed system found in [6] and provides a new basis for studying the interpolation problem, and 2) the avoidance of undesired foreshortening by using nonlinear path interpolation. These two aspects of the thesis are now expounded.
2.2 Physical Model
The first aspect improves performance over [6] by identifying a new physically based model which requires less complex equations, allowing for faster computation of the keyframes. Less complex means fewer arithmetic functions are used for the computation. This method is not as robust as the method in [6]. However and most importantly, the model itself is the basis which provides the equations for nonlinear path interpolation.
2.3 Nonlinear Interpolation
The second aspect focuses on the use of linear path interpolation as the only means of interpolation found in [6]. The nonlinear interpolation uses quadratic paths for each vertex of the polygons. Current techniques that find path equations for each vertex use linear interpolation. Other techniques use interpolation schemes that are not linear. However, these are not considered simple vertex path methods. [3] uses a constraint model that is not a simple path model that uses curves that are specified by the animator with a surface patch scheme.
Q-Curves are used by [6] to identify the bending angles through the entire inbetween, and are not used for interpolation curves. These curves give more information than just the angles over the interpolation. Through analyses of the control polygon of the Q-curve, rigid body motions can be identified. Certain types of rigid body motion are best interpolated using a nonlinear interpolation scheme. Consider figure 2.1. The beginning line segment labeled “A” and ending line segment “B” are the same length. The intermediate line segments generated by linear interpolation are shorter than the original and final line segments. [6] uses only linear interpolation and produces inbetweens of these types. This problem is an undesired shortening of objects over time where a rigid body motion is desired.
Figure 2.1 Linear Inbetweening
Through analyses of the Q-curve, insights are gained as when to use linear and nonlinear interpolation. These insights are applied to the undesired foreshortening problem of the linear inbetweening. Figure 2.2 shows nonlinear interpolation that maintains the lengths of the line segments through the entire scene.
Figure 2.2 Nonlinear Inbetweening
The thesis builds on the work of [6]. The current capabilities of [6] do not include nonlinear interpolation. Through the use of Q-Curves, a new, computer performed, analysis of inbetween generation is developed. Also, the work equations of [6] have apparent confounding factors. That is, some of the parameters of the work equations are held constant in [6], indicating that their use may not be necessary. A new physically based model is developed, resulting in less complex (in terms of the number and type of operations) work equations.
The controlling factor of the nonlinear interpolation is the maintenance of rigidity during rigid body motion. This is evaluated using measurements of the perimeter of the beginning and ending keyframes compared to the generated inbetween frames. This is a measurement of rigid body movement and is the accepted controlling factor of the thesis.
Chapter 3
3.1 Purpose of Physical Model
The purpose of the physical model is to provide a new method of thinking about polygonal data. The concept of mass associated with the vertices provides a new way of thinking about polygonal data that makes the nonlinear path interpolation technique possible.
A second purpose of the physical model is to reduce to complexity of the work equations and still balance polygons with different numbers of vertices. The equations of the new physical model are less complex than the equations presented in [6]. However, this model does not give the robustness of [6]. The speed up of computation allows for more inbetweening throughput which allows for more examples to be tested for nonlinear interpolation in the second part of this thesis.
3.2 Description of Physical Model
The model used in this thesis assumes the vertices of the polygons defining the keyframes to be points in space with a mass of one unit. Transforming the location of a point in one keyframe to its corresponding point in another keyframe is analogous to taking the point and finding the work necessary to move it to the new location. This concept of physical characteristics results in very concise and easily understood equations for determining the work for the transformation, and provide the basis for finding nonlinear paths for interpolation.
The work equations are based on moving a point through space with a constant force. Since the force is constant, only the distance needs to be computed.
Each vertex is compared to all other vertices and the work needed to move the one vertex to the other is calculated. The values resulting from the work calculations are stored in a two-dimensional array for further analysis. The analysis of the array results in the identification of the locations to insert vertices such that the beginning and ending polygons have the same number of vertices.
Once the work matrix as been identified, the analysis is a summation of values providing a minimal work solution for balancing the polygons which is described in [6].
This work equation is less complex than the equations used in [6]. This less complex equation does not come without a price. Since the model uses the vertex that is closest to the vertex under consideration, associations may be ones that are not desired. In the following section are figures that show results that are not considered as pleasing inbetweens.
3.3 Results of Physical Model
Figure 3.1, shows the inbetween of a Concord airplane and a Volkswagen Bug. Any solution could be correct. However, desired "blends" between polygons exist. In animation the beginning and ending polygons are usually similar. The algorithm in this thesis tries to identify the similarities of the polygons and give a "pleasing" blend between them. If the results are unsatisfactory, additional points in the smallest polygon can resolve this problem. Consider figures 3.1 through 3.7.
Figure 3.1 Concord to Volkswagen
Figure 3.2 Bird with Shrinking Feet
Figure 3.3 Bird with Changing Tail Feathers
Figure 3.4 C with Spike
Figure 3.5 E to F
Figure 3.6 Twelve Vertices to Six Vertices
Figure 3.7 Eight Vertices to Three Vertices
Figures 3.8 through 3.10 show some results that are not considered as good blends, a result of the work equation used that is less robust than the equations used in [6].
Figure 3.8 Left Brace - Right Brace
Figure 3.9 Pentagon to Triangle
Figure 3.10 Five Vertices to Three Vertices
Chapter 4
4.1 Rigid Body Motion
Rigid body motion is a special type of transformation. Rigid body motion consists only of translations and rotations, but no scaling or shearing.
4.2 Q-Curves
[6] develops a method known as the Q-Curve for following the angle formed by three vertices in an inbetweening scenario. Consider the two angles shown in figure 4.1. Each angle is defined by three vertices, a subpart of two entire polygons making up two keyframes.
Figure 4.1 Angles used by Q-Curves
The angle µ is approximately 90°. The angle ø is approximately 45°. Interpolation of the Q-Curve at t = 0.5 results in an angle of 67.5°. For a situation not so intuitive, the Q-Curve is evaluated at any t value, ranging from zero to one, resulting in the angle of the vertices at that t value.
The Q-Curve is a quadratic Bézier curve whose control polygon is defined by the angle of consideration on the two keyframes. The derivation of the Q-Curve is found in [6]. The equations for finding the Q-Curve for any given pair of angles follows.
Figure 4.2 Angles used by the Q-Curve and the Plotted Q-Curve
If the angle does not change between the two keyframes, then the control polygon for the Q-Curve is made of three coincident points. By studying when Q-Curves are reduced to a point, rigid body motion analysis can occur. Consider the following polygon keyframes in figure 4.3 and the Q-Curves for each angle on the polygons in figure 4.4. Figure 4.5 is a zoom of figure 4.4.
Figure 4.3 Polygons for Q-Curve Analysis
Figure 4.4 Q-Curves for Figure 4.3
Figure 4.5 Zoom Showing Straight Line Q-Curve of Figure 4.4
By analysis of the Q-Curves one angle is maintained because one of the Q-Curves is a straight line. Since the result is a line and not three coincident points, some length change of the vectors making the angle has been identified.
4.3 New Attribute of Q-Curves
An interesting attribute of Q-Curves was observed after substantial study. If the polygons are triangles, then the control points of the Q-Curves lie on straight lines. That is, the P0’s for all three vertices lie on a line, as do the P1’s, and P2’s. This experimental observation was reported to [2]Wang who proved it to be true.
Figure 4.6 Two Triangles for Representing Q-Curve Attribute
Figure 4.6 shows two triangles. Figure 4.7 shows the Q-Curves for the three angles defined by the triangles. Figure 4.8 shows a close-up of the three Q-Curves. The control points that make up the control polygons, with respect to their counterpart in the other control polygons, lie on a line.
Figure 4.7 Q-Curves of Triangles in Figure 4.6
Figure 4.8 Zoom of Figure 4.7
Chapter 5
5.1 Nonlinear Interpolation
Vertices of a polygon undergoing rigid body motion follow a linear path if the polygon is subjected only to translation. If the polygonal body undergoes rotation, then the vertices of the polygon follow a nonlinear path.
Figure 5.1 Rigid Body Rotation
5.2 Problem of Linear Interpolation
Figure 5.1 shows a square undergoing rotation. The paths of the vertices are along a circular path defined by the distance r , where r is the distance from the center of the square to one of the vertices. Linear paths for the vertices do not maintain the rigidity of the body, as shown in figure 5.2.
Figure 5.2 Rigid Body Motion - Linear Path
Figure 5.2 clearly shows that q < r. This indicates that the interpolated squares all are smaller than the original square and the rigidity of the object is not maintained.
5.3 Path Equation Candidates
Any rigid body undergoing rotational transformation has vertices that follow only circular paths. Therefore any candidate for a nonlinear path should be able to represent circular paths, or provide a reasonable approximation.
With a circular path constraint on the candidates for the nonlinear path equations, possible candidates can now be considered. Some candidates that may meet the needs of the nonlinear interpolation are Bézier curves, B-Spline curves, and parametric cycloids.
Quadratic rational Bézier curves can represent circular paths exactly. Nonrational quadratic Bézier curves can give good approximations of circular paths with less computational expense.
B-Spline curves can represent circular paths, and can be reduced to Bézier curve segments since Bézier curves can be used to represent any B-Spline curve.
Parametric cycloids are generated by rigid body rotation and translation. If a wheel rolls along a straight line without slipping, then a point on the rim of the wheel traces a curve called a cycloid [7]. The cycloid provides the solution to two famous mathematical problems: the brachistochrone problem and the tautochrone problem. The characteristics of these two problems bring cycloids into consideration as a possible path candidate. The brachistochrone problem is the “shortest time” problem, and the tautochrone problem is the “equal time” problem.
Figure 5.3 Parametric Cycloids
The brachistochrone problem was proposed by Johann Bernoulli in 1696. The problem was to find the shape of a wire such that if a bead was dropped down the wire it would travel from point A to point B in the shortest time. The problem was constrained by the fact that point B could not be directly below point A.
Figure 5.4 Brachistochrone Problem
Half of one arc of an inverted cycloid is the answer to the brachistochrone problem.
The tautochrone problem is to find the shape of a piece of wire such that if two beads are dropped down the wire from different positions along the wire they will arrive at point B at the same time. Once again, half of an arc of a cycloid is the answer to the problem.
These interesting characteristics of a cycloid are considered because of their unique timing qualities. The physical properties of vertices can be modeled as beads, and gravity can be modeled about any arbitrary axis. This would provide confidence that any points starting along their respective paths would arrive at their destinations at the same time if their paths were identical cycloids. The path of a cycloid is not circular. In many cases it may approximate a circular path sufficiently. However, it is not as flexible as the Bézier curve.
5.4 Bézier Curve for Nonlinear Paths
The quadratic Bézier curve meets all the requirements for representing paths for rigid body motion. Cycloids are not general enough to give the desired results. Bézier curves also allow a reparameterization of the weights of the control polygon that could allow for different speeds along the interpolation. Also, there are well-defined conditions for continuity between Bézier curves, which is an important aspect of inbetweening. A quadratic Bézier curve has a control polygon that is composed of three points.
To find the control polygon for each vertex path curve a frame is calculated at t = 0.5 using linear interpolation. For example, consider the vertex path for point V in figure 5.5.
Figure 5.5 Linear Interpolation at t = 0.5
First compute the center of mass of each keyframe (C0 and C1) and the interpolated frame (C.5). Compute next the distances of each vertex from the center of mass.
If the keyframe polygons represent a rigid body transformation then d0=d1. In rigid body motion the center of mass moves along a straight line if no outside forces act on the polygonal bodies. Further, interpolated frame’s vertices lay the same distance from its center of mass as those from the keyframes. Therefore the interpolated frame is reshaped such that its vertices are the correct distance from the center of mass as shown in figure 5.6. With the correct position of the vertices at t = 0.5 known, an appropriate curve to interpolate that location at t = 0.5 can be found.
Figure 5.6 Reshaped Interpolated Keyframe
Three vertices must be found for the control polygon of the quadratic Bézier curve. These vertices are referred to as P0, P1, and P2. Since Bézier curves interpolate their end points, P0 and P2 are known; they are the corresponding vertices in the two keyframes. P1 is the only point that has not been found. P1 must be positioned such that when the Bézier curve is evaluated, the results at t = 0.5 are the same as the reshaped linearly interpolated keyframe just described.
Figure 5.7 Reshaped Vertex
The control points P0 and P2 are known because the Bézier curve always interpolates the end points. Therefore, P0 is the vertex under consideration in the first keyframe and P2 is the vertex of the second keyframe. Also, the baseline of the Bézier control polygon is the line between P0 and P2. Figure 5.8 shows the values needed to find P1. The following equations find the point P1.
Figure 5.8 Values Needed to Find P1
Point a is the midpoint of the baseline. Pr is the value of the reshaped intermediate polygon. With these two values, and the parametric equations for a line, the value of Pr can be obtained from a parameter value of 2.0.
Figure 5.9 The value of P1
Figure 5.10 shows the computer generated results of figure 5.9.
Figure 5.10 Bézier Control Polygon and Curve
5.5 Angle Preservation by Linear Interpolation
The reshaping method depends on the assumption that the interpolated frame at t = 0.5 has the same angles between vertices as the keyframes.
The interpolated keyframe is smaller than the original keyframes if the keyframes represent any rotation. For the angles to be maintained by the interpolated keyframe, the scaling of each vertex must be uniform for the entire polygon, and must be dependent on the angle of rotation.
Experimentally it was observed that the ratio of the lengths of the line segments of the interpolated frame to the keyframes was uniform.
Figure 5.11 Ratios of Linear Interpolation
Figure 5.11 shows an arbitrary line segment from a polygon and the center of mass for the polygon. ||A|| is the length of the line segment. ||C1|| is the distance from the center of mass to one end point of the line segment and ||C2|| is the distance from the center of mass to the other end point. The corresponding lengths of the interpolated frame are shown as ||At||, ||C1t||, and ||C2t||. For angles to be maintained the following must be true:
Figure 5.12 Setup of Linear Interpolation
Figure 5.12 shows the line segment C1, the line from the center of mass to an arbitrary vertex.
Figure 5.13 Lengths of Line Segments
Figure 5.13 shows that the length of the interpolated line segment from the center of mass to any vertex is:
The ratio of the lengths represent the cosine of half the angle of rotation that the rigid body experiences. Since the ratio is dependent on the angle of rotation, the ratio represents a uniform scaling of the line segments from the center of mass to the vertices at t = 0.5 and therefore the angles formed by the vertices to the center of mass are the same in the interpolated keyframe as the original keyframes. Since the angles are preserved, the interpolated frame is congruent to the keyframes, and the reshaping of the polygon at t = 0.5 to its proper size gives an interpolation that exactly represents the keyframes at t = 0.5.
Chapter 6
6.1 Results of Nonlinear Interpolation
In a visual paradigm like this, the ends justify the heuristic. The method, whether simple or complex, is useless unless the viewer is satisfied with the results of the method. One method of showing that this method tends to maintain shape in tasks of rigid body motion is to show that the perimeter of the polygon is maintained.
Following are several figures and statistics concerning the perimeter lengths of the frames. The comparison of perimeter values is as follows:
The keyframe’s perimeter lengths are calculated and averaged together.
Using nonlinear interpolation, a frame is generated at t = 0.5, the average of the two keyframes.
The perimeter of the interpolated frame is compared to the average of the two keyframes, and a ratio is reported. The ratio is the interpolated frame’s perimeter divided by the perimeter of the average of the two keyframes.
Each set of figures shows the linear and nonlinear interpolations, with and without plotted interpolation paths. An examination of the perimeter values follows the figures.
Figure 6.1 shows a square that has undergone translation and rotation. The rotation is 90°. The linear interpolation is obviously unsatisfactory in that the square undergoes deformations, first shrinking in size and then growing in size. The nonlinear interpolation provides results that seem more natural candidates for inbetweens and maintains the rigidity of the object as is expected.
Figure 6.1.a Linear Interpolation of Square
Figure 6.1.b Nonlinear Interpolation of Square
Figure 6.1.c Linear and Nonlinear Interpolation of Square
LINEAR METHOD
Perimeter of Left Polygon = 8.00000
Perimeter of Right Polygon = 8.00000
Perimeter of Interpolated Polygon = 5.65685
Average of Keyframes = 8.00000
Ratio of Inbetween to Average = 0.70711
NONLINEAR METHOD
Perimeter of Left Polygon = 8.00000
Perimeter of Right Polygon = 8.00000
Perimeter of Interpolated Polygon = 8.00000
Average of Keyframes = 8.00000
Ratio of Inbetween to Average = 1.00000
The figures in 6.2 show a translating and rotating rectangle. Again the linear interpolation deforms the intermediate frames while the nonlinear interpolation maintains the size and shape of the rectangle.
Figure 6.2.a Linear Interpolation of Rectangle with Paths
Figure 6.2.b Linear Interpolation of Rectangle
Figure 6.2.c Nonlinear Interpolation of Rectangle with Paths
Figure 6.2.d Nonlinear Interpolation of Rectangle
Figure 6.2.e Linear and Nonlinear Interpolation of Rectangle
LINEAR METHOD
Perimeter of Left Polygon = 14.00000
Perimeter of Right Polygon = 14.00000
Perimeter of Interpolated Polygon = 9.89950
Average of Keyframes = 14.00000
Ratio of Inbetween to Average = 0.70711
NONLINEAR METHOD
Perimeter of Left Polygon = 14.00000
Perimeter of Right Polygon = 14.00000
Perimeter of Interpolated Polygon = 14.00000
Average of Keyframes = 14.00000
Ratio of Inbetween to Average = 1.00000
The new nonlinear method of interpolation obviously works well for rigid body motion. The maintenance of the perimeter length of the keyframes is the goal of this thesis; the method presented in this thesis succeeds.
Chapter 7
7.1 Comparison to Hand Drawn Inbetweens
The purpose of this thesis is avoidance of undesired foreshortening of objects due to linear interpolation. A comparison of this new technique to hand drawn inbetweens can be used for evaluating this new method. However, since the method deals only with rigid body motion, the comparison to rigid body movement of hand drawn animation is somewhat uninteresting. Imagine a picture of a cartoon character rotating and translating through some inbetween frames. It is nothing more than a stiff lifeless character spinning during the animation, much as a pipe or some other rigid dead object being hurled along a path. Living objects move at joints, with local rigidity of limbs, not an overall rigidity like a stiff dead object.
An extension to the newly developed method presented in this thesis is appropriate. This extension allows for rigid body motion between joints.
7.2 Joints
Rigid body motion between joints means the limbs move rotationally about joints without experiencing gross deformations. Consider an arm and the elbow joint. When the arm is bent, the forearm moves about a joint of rotation defined by the elbow. However the forearm does not deform during the motion. It does not shrink along a linear path. It is a rigid body in its own right constrained by the elbow.
With this model of joints and rigid body segments between joints, the method described in this thesis is extended to handle jointing of the keyframes.
During the initial phases of the extension of the method, an algorithm to define joints was tried. It soon became an overwhelming problem. There is no standard way in which a jointed body moves. One segment may move first, dragging the other segments along with it. All may move simultaneously, with the segments consisting of larger masses controlling the movement of the other segments. The user of the animation tool can identify the joints quickly and much more efficiently than an existing algorithm.
In most figures, the number of joints is easily definable and relatively small. Consider a human character for animation. The importance joints are the neck, shoulders, elbows, wrists, hips, knees, and ankles, or thirteen joints in all.
7.3 Results of Joints
Following are several sets of figures showing some simple polygonal bodies with obvious joints. Figures 7.1 through 7.3 show these examples. The inbetweens in these figures show interpolations using linear, nonlinear, and jointed-nonlinear methods.
Figure 7.1 Joint Method
The joint in figure 7.1 is defined by the two vertices labeled Pa and Pb. The jointed method gives a more intuitive interpolation. The nonlinear method alone fails since it is not a total rigid body motion. In the nonlinear method, the center of mass of the entire polygonal body is used to define the position of the interpolated points. In the jointed nonlinear interpolation, the local center of mass of the jointed body is used to define the paths for the nonlinear interpolation.
The jointing of the polygons in figure 7.1 is similar to dividing the body into two separate polygons per body. The triangle becomes a polygon and the remaining vertices define another polygon. These polygonal divisions are termed local bodies. The center of mass of these local bodies then is used in the original nonlinear method.
Figure 7.2 shows keyframes that represent a body with a rectangular bottom and a triangular point on top. The rectangular part rotates 90° and the triangular part points almost in a constant direction.
Figure 7.2 Jointed Box with Pointed Top
In figure 7.2 the nonlinear jointed method maintains the bottom rectangular part more consistently than the linear and nonlinear methods.
Figure 7.3 shows a cartoon figure’s feet walking. These are digitized from [8] .
Figure 7.3a Linear Interpolation of Walk
Figure 7.3b Nonlinear Interpolation of Walk
Figure 7.3c Nonlinear Jointed Interpolation of Walk
In figure 7.3a the linear interpolation deforms the ankle; and the forward foot is smaller than in either of the keyframes.
In figure 7.3b, using the nonlinear interpolation, the ankle of the lifted foot deforms drastically. This is because the centers of mass of the two keyframes are different enough that the method fails.
Figure 7.3c shows nonlinear jointed interpolation. The ankle does not deform and the foot maintains its size. This interpolation is visually more natural than the previous interpolation.
Figure 7.4a Linear Interpolation of Walk
Figure 7.4b Nonlinear Interpolation of Walk
Figure 7.4c Nonlinear Jointed Interpolation of Walk
Figure 7.4d Hand Drawn Interpolation
Figures 7.4a through 7.4d show the nonlinear jointed interpolation maintains the ankle and foot better than the other methods. Compared to the hand drawn interpolation, the leg does not rise as high. The jointed nonlinear method seems slightly lazy in that the leg moves about the shortest path possible through the interpolation while the hand drawn method gives the character some “energy” to the character’s step. This is precisely why it is difficult to compare to the hand drawn animation. The animator can add such things as “bounce,” “energy,” and other life-like characteristics to the animation more intuitively than can an algorithm. Given more frames to user for interpolation, the life-like characteristics can be achieved by the nonlinear jointed method.
Chapter 8
8.1 Conclusions
This thesis presents two topics which are of value in Computer Assisted Animation (CAA): 1) a physical model for representing polygons as keyframes and 2) a nonlinear interpolation for rigid body motion.
The physical model represents the vertices of the polygons as points with mass. This mass model allowed for the conception of the ideas that lead to the nonlinear path interpolation technique. The equations for work with a constant force are used to balance the polygons. The model is less complex than the model presented in [6] where wire is modeled, and bending and stretching equations are used. The results of the physical model described in this thesis are presented and give adequate results only when the keyframes are more similar than those required by [6]. This is the loss of robustness that is described earlier in this thesis. The equations used in the model are less complex than those in [6], which is a partial goal of this thesis.
Nonlinear interpolation successfully represents rigid body motion. The use of Bézier curves as interpolation paths give good results in an easy to understand manner. For rigid body motion, the method maintains the perimeter length of the interpolated polygons where linear interpolation fails. However, the nonlinear method alone does not satisfy the problem of joints and limbs.
An extension to the nonlinear method proves useful. The user can identify joints interactively. A new application of the nonlinear technique shows that movement about joints gives improved results over the nonlinear method alone.
Comparison to hand drawn inbetweens shows that the types of movement that an animator gives a character is extremely complex. The nonlinear jointed method gives good inbetweens that do not deform or shorten. However, it can not anticipate the type of path the animator may desire.
8.2 Further Work
Further development may include a more in-depth study of joints. An understanding of how motion occurs about a joint could improve the quality of inbetweening. A new method for balancing polygons that contain joints would be useful. This new method could balance the limbs of the polygons, which would improve the use of the center of mass as a reference point for motion.
Bibliography
[1] Glassner, Andrew S. “3D Computer Graphics A User’s Guide for Artists and Designers” Second Edition, Design Press New York, NY., 1989
[2] Catmull, Edwin. “The problems of computer-assisted animation” Computer Graphics , 12(3):348-353 1978
[3] Reeves, William T. “Inbetweening for Computer Animation Utilizing Moving Point Constraints” Computer Graphics , 15(3):263-269 1981
[4] Sederberg, T. W., and Parry, S. R. “Free-Form Deformation: A Sculpturing Tool for 3D Geometric Modeling” ACM Siggraph , 20:151-160 1986
[5] Coquillart, Sabine., and Jancéne Pierre. “Animated Free-Form Deformation: An Interactive Animation Technique” Computer Graphics , 25(4):23-26 1991
[6] Sederberg, T. W., and Greenwood, Eugene. “A Physically Based Approach to 2-D Shape Blending” Computer Graphics , 26(2):25-34 1992
[7] Anton, Howard. “Calculus with Analytic Geometry Second Edition” John Wiley & Sons, New York. 726-727 1984
[8] White, Tony. “The Animator’s Workbook” Watson-Guptill, New York. 46-51 1986
[1]Description of Shape Blending was given by Sederberg during a private conversation on September 17, 1992.
[2]Guo-Jin Wang is an Associate Professor of Applied Mathematics at the Zhejiang University, Hangzhou, China. Currently he is at Brigham Young University as a guest of the Civil Engineering Department.