Abstracts: In this paper, an interactive platform is introduced that users can create dancing animation of models with various topologies, including humans, flowers, animals and etc. Two different physical models, the spring model without mass and elastic joint model are applied into system. In the interaction procedure, the models are set as spring model, which could propagate the force at one joint to the entire skeleton and drive the motion of the whole model correspondingly. And we have taken some measures to make the model stiffer and reduce "super-elongated" springs. In the process of animating, we make good use of elastic joint model to sequence and polish the interpolation. In addition, we have simplified the elastic model to achieve smooth real-time animation. What is more, certain posture bases have been designed for users in advance, which greatly reduces the labor burden of creating individual postures and facilitates operating the system. After users have set proper dancing postures interactively through mouse action and stored these postures, our system will calculate the transition between those postures following dynamic theories, and produce the dancing animation soundly in real time. Moreover, some natural movements can be easily simulated with the system, such as the waving motion of trees in the winds, with the spring model and elastic joint model working together.
Key words: Physically based animation, Interactive, Spring Model, Simulation, Elastic Joint Model, Inverse Kinetics
From Steamboat Willie by Disney in 1928, the first sound cartoon in the world, the cartoon industry has made rapid progress in the past years. Nowadays there are about fifty to sixty cartoons produced each week just in Japan. Generation after generation, both children and adults are impressed by lively characters, interesting stories, various subjects and wonderful pictures of cartoons. However, the traditional key-frame technique to produce cartoon manually is an extremely great burden for animators. With the development of computer science, how to aid animators in producing cartoons with computer is an active and promising research field.
Our approach is also based on the dynamic equations of motion. As physically based animations are preeminent to produce realistic motions, and moreover, motions are created automatically according to the inherent physics theories in such an animation system. That is, in this system, what animator need to do is to regulate some physical parameters and specify the beginning and ending postures, and the system will produce the final animation automatically.
The goal of this work is to create an expressive and recreational animation system. We finally focus on the dancing animation, for dancing is very representative. Furthermore, it generally exhibits repeated patterns in dancing, which facilitate the design of postures. We also want the system to provide an easy-to-use interface, and grant users the power to create motions representing their individualities. We also intend to offer a system for animating universal models, including humanoid biped, quadruped, myriapod insects, plants, and so forth.
As a matter of fact, to generate the animation completely by computers, without any involvement of human intelligence is not possible at present . In this system, users should first choose a dancer from what we have provided in the model base. Because our method is based only on dynamic physics theories and not related with the topology of dancer models, the dancing characters can be various. In producing animation, users may set individual postures directly by dragging the selected joint of the skeleton to the desired position interactively. Subsequently, the individual postures are stored as key frames of the final dancing animation. We also afford users some most ordinary postures in the posture bases of each model to make the creation procedure easier and more standard. At last, we apply the elastic joint model to the dancer, interpolating between the key frames and producing dancing animation in real time. Because our model is a second-order dynamic system, the final animation is smooth and realistic, avoiding some undesirable effects usually caused by direct linear interpolation .
The remainder of this paper is organized as follows. After reviewing the related work in Section 2, we will briefly describe our whole system in Section 3. We introduce the elastic joint model to smooth the dancing animation in Section 4, and the application of spring model as well as the pre-set posture bases in the system to realize the interactive control in Section 5, and. Some resulting animations will be shown in Section 6. We conclude the paper and point out the future work directions at last.
A common technique to create character-dancing animation is motion capture, which can obtain appealing motion sequences directly from real world. For instance, Li and his colleagues  designed a two-level statistical model to characterize the dynamic and stochastic nature of the figure motion. Firstly they created motion texture for synthesizing the dancers' motion. Then under the constraints of the beginning pose and ending pose, the system could find the lowest cost path automatically and smooth all the transitions. But their algorithm did not allow the poses to be edited by users to deviate from the original ones too much. Kim et al. , however, presented a novel scheme to synthesizing new motions from the example motions while preserving their rhythmic pattern. Their scheme first extracted the basic movements and their transitions from example motions, and then constructed a movement transition graph representing the example motions. However captured data are difficult to edit and operate, and motion capture has disadvantages on interactivity and adjustability. 
Oore et al.  introduced local physical model - the DIGITAL MARIONETTE animation system, which could automatically produce some behaviors and let users control the virtual puppetry via a PD-controller. There are also inertia parameter M, stiffness coefficient K, and damping matrix C in their system, but they only developed models for the knees and ankles of an interactively-animated 3D anthropomorphic character. What is more, there were no such poses as leaning or bowing in their final animation, which would lead to the unbalance of the character. In addition, the virtual puppetry could not jump, that is, at least one point of the two feet should be fixed on ground, and in the interactive control, users could only set some limited physical properties of the joints. Such kind of work is also in , and their algorithm is O(N).
On the other hand, many people create some animation system with intelligence, such as . Recently Lu  is engaged in the research of full life cycle computer aided animation generation technique, that is, from the story in natural language to the demonstration of pictures, the whole process is done with the aid of computers. This study is related with artificial intelligence, natural language understanding, and computer graphics. It will greatly reduce the workload of producing animation, however nowadays the process must have people's interference. In the respects of interaction, frameworks for creating and animating the elastically deformable characters interactively have been developed as in [9, 10]. Dontcheva et al.  created an action-based animation system, in which the animator's real-world, expressive motions were mapped into the character's virtual world. Some widgets were used to control the user features, which mapped to character features. Visual feedback are also adopted to maintain a tight coupling between the animator and the character. In J. Popovic's  system, an animator could select bodies at any time and simply dragged them to desired locations. In response, the system computed the required physical parameters and simulated the resulting motion. While in our system, all the physical parameters are initially defined or interactively regulated by users in real time. The system just computes the torque caused by displacement and torsion following the second-order dynamic equations.
All the work in this article is based on our previous system - "DFLORA" . We have completed a system with script-driven function as in , but it is not convenient for users to work out the script and produce animation. In this paper, we offer users the option of interactively controlling the dancing character and automatically producing animation from key frames. Obviously, it is much more intuitionistic to design animation by the friendly interface. Furthermore, we want to do some work to combine animation with music and finally accomplish a system with script-driven and music-driven two functions.
Fig.1 Flow chart for the interactive system
First of all, we should create the character models with the help of some modeling software. In our practice, we just apply the skeletons to the prepared model meshes through MilkShape 3D©. Of course, the skeleton can be designed with more details, which means more accurate control of the character and the more elaborate animation. However it also means more burdens in creating the postures and more computation cost in animation. We should achieve a balance in the dilemma soundly.
The system of this work is divided into two levels: the high level for interactive control and animate actors and the low level for regulating the dynamical motions and physical properties of each joint. Animators can interactively control the characters at the high-level intuitively, with no awareness of the inner potential mechanisms. The system will automatically produce the final animation through the low-level.
As can be seen from Fig.1, we design the system as a linear spring model and a second-order dynamic elastic model. The connected springs can propagate the local deformation throughout the whole skeleton, which is desirable for the interactive control globally. On the other hand, the elastic model is created as a linear dynamic system (LDS) as in . All the transitions are computed locally, in the parent joint coordinates. We also simplify the LDS in order to create the animation in real time while keeping animation realistic at the same time.
Although music-driven module is mentioned in the system, it is our future work. And we will not discuss the techniques of music cognition and music-motion mapping here. Our propose is to introduce a dynamic, interactive and real-time animation system. Nevertheless with our current system, if animators could design the postures according to their understanding of certain music, they will choreograph these postures to music with their own individuality and express their inner preferences as well.
As we all know that the linear interpolation often result in jerky motions in animation. Consequently, we adopt the second-order dynamic equations.
In the elastic joint model, every joint is regarded as rigid link and elastic hinge, and the hinge determines DOF (degree of freedom) of the joint. A joint is considered as a spherical joint, and an angular spring is set in every hinge. When a joint rotates, there will be angular displacement in the joint. The angular spring will produce a torque proportional to the angle to force the joint back to its rest position. In the model, all the computation is localized. As a result, we should translate the absolute coordinates to those in the parent coordinates, and extract the spacial angular displacement from 3D position coordinates, as shown in Fig.2.
Fig.2 From spring model to elastic joint model
As can be seen, <![if !vml]><![endif]>is a vector quantity, indicating the rotation angels in two orientations. <![if !vml]><![endif]> and <![if !vml]><![endif]> are the absolute torsion angel around their respective hinge, and <![if !vml]><![endif]> is a scalar quantity that can be thought as a rotation angel in another orientations. And <![if !vml]><![endif]> is the final angular vector under computation in this system.
First of all, we apply the unconstrained rigid body motion equations to analyze the dynamics of each joint.
In the above two equations, <![if !vml]><![endif]> is the angular velocity, <![if !vml]><![endif]> is the angular momentum, and m is the rotation inertia of bone of the hinge.
is the total torque, the sum of elastic torque, damping torque and external torque.
is the elastic torque which, according to Hooke's principle, is proportional to the negative angular displacement, and k is the elastic coefficient.
is the first-order damping, indicating friction or the energy loss of the system, and c is the damping coefficient.is the external torque, which is the only motivation of the whole system.
From the above analysis, the whole model can be deduced as a second-order linear dynamic system. The equation for the movement of every joint is as follows.
In the practical design, every joint is thought independent on others, including the immediate parent-joint and child-joints in the skeleton. That is, we assume that when computing a joint, other joints are fixed in their present positions, and only the joint currently under consideration is active and can move freely. Therefore, there is no coupling between joints and all the coefficient matrixes in the equations are simplified to cross matrixes as follows:
Here M is the inertial matrix, C is the damping matrix, and K is the stiffness matrix.<![if !vml]><![endif]> is the angular displacement vector, and <![if !vml]><![endif]> is external torque vector.
Such presupposition is not accurate in theory. But because the motion range of every joint is small, relatively with neighbor joints, the velocity of the whole skeleton is not very fast and the simplification highly decrease the computation cost, we ultimately achieve satisfying smooth animations in real time.
4.2. Physical Parameters
As the animation is based on angular springs, and the ultimate motion source is the external torque produced from the displacement in interaction. It is also the only impetus of the whole system. The actor can smoothly change its postures as a response of the second-order dynamic system with different external motivations.
On the other hand, all the physical parameters in the formula can be adjusted by animators in real time, and the system will demonstrate different styles of choreography accordingly. For example, if we increase the inertia coefficient, the actor looks clumsy; while deceasing it, it is brisk. The greater the damp coefficient is, the faster the system loses its energy; in contrast, the less it is, the crazier the character appears is. When stiffness coefficient is enhanced, the motion seems rigid, while it is cut down, the animation is softer.
5.1. Spring Model
"Skeleton animation consists of changing joint angles. In a typical system based on inverse kinematics, animators specify the end positions of some parts of the skeleton, and the system can compute the necessary joint angles of other parts to put the specified parts to the desired position automatically."  Our system also involves inverse kinematics, for users select and drag certain joint to the target position, and system should put the whole character skeleton to the proper position. Our method is to model the skeleton with spring model because connected springs can propagate forces among the entire skeleton, maintaining the minimum energy of the system.
In practice, spring model has been widely adopted to simulate deformable objects, for example the dynamic clothes [15, 16], realistic skin  and expressive face . There are two kinds of spring model, with or without mass. The spring model with mass can be used to create more realistic animation, but it is also time-consuming, which is unsuitable to be utilized in interactive animation. In our system, the prime purpose is to permit users to set and store the appropriate postures as they want in real time. Accordingly we adopt the spring model without mass to alleviate the computation cost.
Fig.3. Energy in a spring system
The original method is to minimize the energy of the whole model. Because the joints in this system are created without mass, there is only potential energy and no kinetic energy here. A case in point is the example of a simple spring system like Fig.3. According to the physical theories of potential energy in a spring system, we should minimize the energy
where <![if !vml]><![endif]> is the current distance between two joints, while <![if !vml]><![endif]> is the rest length of the spring. And the final equations are as follows.
here <![if !vml]><![endif]> and <![if !vml]><![endif]> are the positions of point 1 and 2.
and h is the step coefficient.
From above, we carry out the effect of one neighbor joint on another. But each joint in the system, except the root and leaf joints, is connected with one parent joint and at least one child joint, and the sum of these effects must be taken into consideration. Here we calculate the sum of forces on every joint according to Hooke's law.
We set k=1 to facilitate the computation. As can be seen, F and<![if !vml]><![endif]>are equal in numerical value.
Then the sum of forces on each joint is calculated recursively throughout the whole skeleton, as shown Fig.4. Our method is to compute forces in three coordinate directions, that is<![if !vml]><![endif]>in this system, and figure out the final displacements of every joint of the skeleton. It also produces the forces driving the movements of the entire skeleton, which will be illustrated in the next section.
Initially, we set h=1 directly, because the system energy is kept zero in such a case. But there is unexpected vibration while dragging a joint to move the entire skeleton. It is because the points move so far at a step when h=1, that the system is unstable. Therefore we set h less to slow down the movement of each point.
However as can be expected, an inherent shortcoming of spring model appears-the elongation, which may result in unacceptable deformation in our models. Ultimately we find that h=0.5 is a good setting. It is the critical point. When it is greater, there is vibration while skeleton moving, while if less than that value, there is no such phenomenon. But the less h is, the greater the elongation is. As a result, we finally set h=0.5.
Fig.4. Force on a joint
5.1.1. Making Dancing Models Stiffer
Fig.5. Springs between 2, 4 and 6 joints
Fig.6. Dragging the foot of a human skeleton
(On the left is the skeleton with springs imposed just between the nearest 2 neighbor joints, while on the right is that with springs among 2, 4 and 6 neighbor joints.)
In the beginning experiments, another problem with the spring model also occurred. If we just provide springs between the immediate neighbors, the model looks extremely flexible. Therefore we impose additional springs in the neighbor 4 and 6 joints to make the model stiffer as illustrated in Fig.5. As a matter of fact, to set spring between two joints is to maintain their initial distance constant during the interaction procedure. Accordingly those additional springs can help keep the shape of models unchanged in this process.
In Fig.6, the blue point in foot indicates the joint selected and dragged by the mouse. As it shows, because we have imposed springs between 2, 4 and 6 nearest joints, the leg seems stiff. In contrast, if only the force produced by the springs between the immediate 2 neighbors is calculated, the whole skeleton is particularly flexible and unrealistic.
5.1.2. Fixing Joints in the Skeleton
As illustrated previously, the spring model is universal to model subjects of different topologies, and we regard any joint in the skeleton having 6 DOFs, unattached to each other. But in most cases, this is not true. For example, knees in human body can not bend forward and there are interlinkings between crotch, knee and ankle. Furthermore, many articulations are only of limited ranges of DOF. For instance, we cannot turn our heads for <![if !vml]><![endif]>.
On the other hand, after more springs are added into the system, the skeletons are much stiffer. If the ankle is dragged, the whole leg will follow the motion and it is something like a stick.
In order to control every joint respectively, we grant animators the ability to select and fix some joints. For example, animators can finely adjust the position and orientation of wrist by fixing the joints shoulder and elbow. This function will permit animators to design postures with more accuracy.
5.1.3. Reducing the Elongation
Due to the application of spring model, the displacement of a joint is proportional to the altered distance between its neighbor joints and it. There is also the "super-elongated" phenomenon in our model. But because of the less amount of joints in our system compared to the one finished by Provot , we do not adopt his method of apply a dynamic inverse procedure. In our accomplishment, we set a threshold <![if !vml]><![endif]>, for example <![if !vml]><![endif]>, which means that the length of the springs cannot exceed their rest length by 5% or more. The system will iterate from the springs exceeding this threshold and propagate the force among the whole skeleton.
The criterion to end the iteration is diverse. For instance, the iteration can be stopped when all the springs converge to satisfy that all springs do not exceed their rest length by 5%, or by computing for a certain period time, say 0.1 second. However we choose to predefine the times of iteration N to make our algorism easier. The experiments show that N=10 is an ideal setting. When N is less than 10, the "super-elongated" is also obvious in some cases, while if N is greater, we might achieve more satisfying results, but it is comparatively with more computation cost.
5.2. Postures Bases
Fig.7 Some elemental postures and the combined postures
(From left to right, they are postures right arm raised up, right leg raised up, left knee bent backwards, body bent forwards, and two complicated postures combined from the elemental postures.)
We have pre-set some basic postures for users. These postures are the most common ones as we can imagine, including bending the waist, the elbows, the knees, the wrists, or the ankles, nodding head and raising the arms or the legs. What is more, the postures from bases can be combined into a new complicated posture. Some are shown in Fig.7. We also set them with extent coefficients to demonstrate the similar posture with different exaggeration, exhibited in Fig.8. Hence, users can obtain a group of similar postures by adjusting the extent parameter.
On the other hand, animators could set up their own posture bases by creating individual postures and storing them into the bases. So users need not to design every posture each time, for they can choose the appropriate postures from the posture bases to create their dancing. With the help of these settings, users can produce animations more effectively.
Fig.8 Postures with increasing exaggeration extent
(The postures are the model Human at rest, leaning right with 50% and 100% degree of exaggeration respectively.)
All the animations are achieved on a 1.4G PC with Intel Pentuim 4 CPU, 128M RAM. The interactive control is in real time and the final dancing is smooth. Many objects of various topologies can be animated in this system. For example, Human is a 3D model with 754 faces and 39 joints, while Lily is with 9248 faces and 29 joints. Although there are actually more than 100 joints in a human body, it is unnecessary for us to animate every joint in this system. and more joints also lead to more designing and computing cost.
Some final dancing animations are displayed in Fig.9 and Fig.10.
Furthermore as discussed in the previous sections, although there are spring model and elastic joint model in the system, the two models operate at different time. However, when the two models work together, this system can simulate some natural movements, as Feng et al.  do. Animators can introduce wind into the system, which causes displacement in some joints, just as some are selected and dragged interactively through mouse motions. The spring model is responsible for the effects of wind on the whole skeleton. At the same time, the elastic joint model will be activated by the angular displacement, and produce a force compelling the skeleton to its initial equilibrium. As the elastic joint model is a second-order dynamic system, the simulation is based on physics and the results are realistic. But this kind of simulation is not fine enough, especially for the objects such as flowers that have complicated and detailed petals. However it is good at simulating the models with clear skeletons, such as willows, grass, stems of flowers and branches of trees. The simulation result is exhibited in Fig.11.
Fig.9 Dancing animation sequences of Human
Fig.10 Dancing animation sequences of Rose
Fig.11 Motion sequences of Lily in storm
7. Conclusions and Future Work
In this paper, a system has been described for creating and manipulating articulated character dancing animation. Animators can produce choreography of their own personality, and even design dancing according to music to express their understanding of certain music freely. What is more, this system can achieve diverse types of dancing animations by changing the physical parameters, including stiffness, damping, and inertial coefficients of the joints.
Spring model is widely adopted to animate deformable objects, and "it is easy to implement, is highly parallelizable, and involves few computations."  We apply spring model to interactively control and design postures, and the results are equally effective and satisfying. For the elastic joint model, we make some assumptions to simplify the computation of LDS and achieve the real-time animation while keeping motions realistic.
There are also many problems remaining in this system. The spring model is universal for objects of various topologies, but we also want to add some constrains to the articulated models to grant them their natural characteristics, as M. Naganand and S.Ferguson  have done. For example, all the human-like figures have the specific characters of human to display the required physical similarity that is necessary for a human animation. Then it will be much easier and more effective for animators to create animations through this system.
Spring model and elastic joint model are applied to the system to produce animation in real time, but the two models are generally local models. Consequently, we are also desirous to add some other physical models into our system to realize controlling the whole skeleton globally. A case in point is the introduction of Mode Shape in mechanism, which will greatly facilitate the animation production and simplify the computation to improve the real-time performance.
Furthermore, dancing is the most impressive when performed to music. Animators can create dancing animations to music, but it may take them much time with our current system. As animators must listen to certain music many times to extract the rhythm and pattern by themselves, and then design the postures accordingly and particularly. How to aid animators in creating choreography to music with computers is a promising and arduous task for our future improvement. It involves in extracting rhythm, patterns and even feelings of music by computer automatically, and it is also a significative exploration in music visualization [20, 21]. We plan to use MIDI (Musical Instrument Digital Interface) as the input music because it contains the control information for a musical composition.
This work is supported in part by NSFC(#60121302). We would like to acknowledge Jun Teng for his profound suggestions and technology instruction in implementing the system, and Yujiu Yang for his constructive advices in finishing the paper. The flower and human models shown in our paper is downloaded from the website of Toucan Corporation. (URL: http://www.toucan.co.jp)
 LU R.-Q., AND ZHANG S.-M, From Story to Animation-Full Life Cycle Computer Aided Animation Generation. Chinese Journal of Automation 28, 5, 321-348. (Chinese). 2002
 THALMANN N. M., AND THALMANN D. Computer Animation: Theory and Practice. Springer-Verlag. 1990.
 LI, Y., WANG, T., AND SHUM, H.-Y. Motion texture: A two-level statistical model for character motion synthesis. ACM Trans. Gr. 21, 3, 465-475. (Proc. of SIGGRAPH 2002). 2002.
 KIM, T., PARK, S. I., AND SHIN, S. Y. Rhythmic-motion Synthesis Based on Motion-beat Analysis. ACM Trans. Gr. 22, 3, 392-401. (Proc. of SIGGRAPH 2003). 2003.
 NAKATA, T. Generation of Whole-body Expressive Movement Based on Somatical Theories. In Proc. of the Second International Workshop on Epigemetic Robotics, 105-114. 2002.
 OORE, S., TERZOPOULOS, D., AND HINTO, G. Local Physical Models for Interactive Character Animation. Computer Graphics Forum 21, 3, 337-346. (Proc. of Eurographics 02). 2002.
 MCMILLAN, S., ORIN, D. E., AND MCGHEE, R. B. Efficient Dynamic Simulation of an Underwater Vehicle with a Robotic Manipulator. IEEE Transactions on Systems, Man, and Cybernetics 25, 8, 1194-1206. 1995.
 TU, X.-Y., CHEN, H.-J., AND TU, X.-Y. Methods of Artificial Life - Modeling and Production of Artificial Fish. In Software World, 51-53. (Chinese). 2000.
 CAPELL, S., GREEN, S., CURLESS, B., DUCHAMP, T., AND POPOVI, Z. Interactive Skeleton-driven Dynamic Deformations. ACM Trans. Gr. 21, 3, 586-593. (Proc. of SIGGRAPH 2002). 2002.
 TURNER, R., AND GOBBETTI, E. Interactive Construction and Animation of Layered Elastically Deformable Characters. Computer Graphics Forum 17, 2, 135-152. 1998.
 DONTCHEVA, M., YNGVE, G. D., AND POPOVIC, Z. Layered Acting for Character Animation. ACM Trans. Gr. 22, 3, 409-416. 2003.
 POPOVIC, J., SEITZ, S. M., ERDMANN, M., POPOVIC, Z., AND WITKIN, A. Interactive Manipulation of Rigid Body Simulations. In Proc. of SIGGRAPH 2000, 209-218. 2000.
 LI, C.-Z., HU, B.-G., AND CHEN, C. Dancing Flora: Virtual Plant Dancing Animation System Based on Elastic Model. in Proc. of Chinagraph 04. 2004
 PERLIN, K., AND GOLDBERG, A. Improv: A System for Scripting Interactive Actors in Virtual Worlds. In Proc. of SIGGRAPH 96, 205-216. 1996.
 MEYER, M., DEBUNNE, G., DESBRUN, M., AND BARR, A. H. Interactive Animation of Cloth-like Objects in Virtual Reality. The Journal of Visualization and Computer Animation 12, 1, 1-12. 2001.
 PROVOT, X. Deformation Constraints in a Mass-spring Model to Describe Rigid Cloth Behavior. In Graphics Interface, 47-154. 1995.
 ZHANG, Y., PRAKASH, E.-C., AND SUNG, E. Real-time Facial Expression Animation on an Individualized Face Using Adaptive Simulation Algorithm. In Proc. of GraphiCon 2002, 62-69. 2002.
 FENG, J.-H., CHEN, Y.-Y., YAN, T., AND WU, E.-H. Going with Wind - Physically Based Animation of Trees. Chinese Journal of Computers 21, 9, 769-773. (Chinese). 1998.
 NAGANAND, M., AND FERGUSON, S. Specialized Constraints for an Inverse Kinematics Animation System Applied to Articulated Figures. In Proc. of Eurographics 98, 215-223. 1998.
 KIM, G., AND HWANG, J. Musical Motion: A Medium for Uniting Visualization and Control of Music in the Virtual Environment. In Proc. of VSMM 99. 1999.
 SMITH, S., AND WILLIAMS, G. A Visualization of Music. In Proc. of Conference on Visualization 97, 499-503. 1997.