Method and apparatus for inserting external transformations into computer animations

[0002] This invention relates to the field of computer graphics, and more specifically, to modeling and/or simulating the behavior and motion of real-world articulated objects such as humans, animals and birds in real-time 3-dimensional video games and other interactive contexts. Still more particularly, this invention relates to a unique solution to the problem of efficiently inserting external matrix transformations (e.g., generated in real time) to computer-modeled animations and/or changing animation sequences at an arbitrary point.

[0003] Computers and video games have revolutionized animation—the process of showing a sequence of images in rapid succession to create the illusion of motion.

[0004] In the past, animations were created by a human artist drawing each of the many still frames required (e.g., over 1000 frames for each minute of animation). Now computers can do most of this work.

[0005] For example, computers are commonly used to automatically generate an arbitrarily-long sequence of successive incremental frames between two “key frames” specified by the animation artist or captured by an image sensing device. Using this technique, a first frame and a last frame of an animation sequence are specified, along with the duration of the sequence. Based on this information, the computer automatically generates the many intermediate frames between the first and last frames using a process called interpolation. FIG. 1 illustrates this well known technique. In the FIG. 1 example, the animation artist specifies a first key frame 10 in which the arm of character 11 is lowered, and a second key frame 12 in which character 11's arm is raised. The computer interpolates to automatically generate intermediate frames 14(1), 14(2), 14(3), . . . , 14(N), showing character 11's arm in the various intermediate positions between the lowered and raised positions.

[0006] Pre-storing each still picture in its entirety would take up too much space. Therefore, the computer uses a sequence of mathematical transformations to specify incremental changes between the successive frames of the animation. These mathematical transformations can be conveniently represented by a mathematical construct called a transformation matrix (“M”) that specifies the amount of translation, rotation and scaling in each of the three possible axes (x, y, z) of three-dimensional space. Such transformation matrices are commonly used in computer graphics to represent changes in position, orientation and/or size between successive images.

[0007] FIG. 1 shows how a first transformation matrix M 16(1) transforms the beginning key frame 10 to a first intermediate frame 14(1); a second transformation matrix M 16(2) transforms the first intermediate frame 14(1) to a second intermediate frame 14(2); and so on, with a last transformation matrix M 16(N) transforming the last interpolated intermediate frame 14(N−1) to the second key frame 12.

[0008] In this example, the computer models character 11 just as real humans or animals are constructed—out of different parts (e.g., legs, arms and a torso) interconnected by articulated joints. See FIG. 1A. This modelling technique allows the computer to break up the animation problem into more easily handled parts (for example, how the character's right arm moves relative to the character's torso; and how the character's torso moves relative to the character's surroundings). Dividing a character 11 up into different articulated portions allows the computer to use different transformation matrices to move parts of the character relative to other parts of the character. For example, one transformation matrix may be applicable to the entire character (e.g., to move the entire character relative to a common three-dimensional “world” space). Other matrices may apply to various body parts of the character. Such articulated portions are sometimes represented in a hierarchical structure an example of which shown in FIG. 1B. To move a part of the character relative to the rest of the character (e.g., to cause the character to raise its arm), a transformation matrix is applied to that part of the character relative to the rest of the character.

[0009] Because the animation must run at high speed (i.e., over a thousand pictures a minute) to create the illusion of fluid motion, it is desirable to pre-compute and pre-store the necessary animation transformation matrices when the animation sequence is authored. Then, during video game play or other presentation of the animation, the computer reads these pre-stored matrices and applies them to achieve a desired visual animation effect.

[0010] However, in an interactive situation like a video game, how a character moves and how a scene changes may depend in part on events occurring in real time (for example, a game player's operation of joysticks, buttons or other controls). This means that the real time interactive animation or simulation cannot rely entirely on pre-computed animation matrices, but must instead provide some way for the animation to also be affected by real world inputs. For example, while a character's arm and leg motion may be characteristic of the particular character and may be essentially the same irrespective of the direction in which the character walks, the direction in which the character walks may be controlled by operation of a keyboard, handheld controller or joystick.

[0011] While it would be desirable to use the same pre-computed animation (matrix) sequences for any arbitrary walking direction, this has sometimes been difficult to achieve in the past because of the way the animation transformation matrices are typically pre-computed as representing the incremental change(s) (Δ) between successive frames of the animation. This has in some cases meant that the animation artist at authoring time must anticipate each of the various directions the character will be required to walk, and pre-compute a different animation sequence for each different direction. For example, one technique pre-computes a walking animation sequence for each 10 degrees of the compass—allowing a character to walk in any selectable one of thirty-six different directions. Storing all of these various pre-computed sequences takes up a lot of space in memory, and also does not actually cover every possible walking direction (for example, in this scenario, the video game player cannot control the character to walk in a direction of 245 degrees, but is limited to 240 degrees or 250 degrees). It would be desirable to easily and efficiently insert, into a pre-computed animation sequence, an arbitrary external transformation generated in real time response to user interaction in order to, for example, control the character's orientation and/or translation direction and speed.

[0012] Another problem relating to pre-constructed animation matrices for real time interactive animations is how to handle a transition from one animation sequence to another. Past techniques defining each incremental frame of an animation sequence relative to the last frame of the sequence can lead to unnatural-looking transitions between different animation sequences. Suppose for example that during an interactive game, the game player operates a hand controller to cause character 11 to walk for a time and then suddenly pushes a button to cause the character to run. In many prior systems, it was necessary to finish the walking animation sequence before starting the running animation sequence. This is why some prior games noticeably delay transitions between different animation sequences. One approach to solving this problem is to make each animation sequence very short so the player won't notice any significant delay. In contrast, however, a real world person or animal can immediately change direction or orientation without waiting for a prior motion to complete. It would be desirable to simulate such fluid continuity by allowing an immediate transition from any arbitrary frame of an animation sequence to another animation sequence.

[0013] The present invention solves these problems by providing a unique framework for allowing an externally-supplied transformation matrix to further transform an ongoing animation, and for smoothly concatenating animations together seamlessly and arbitrarily. The algorithm can be built in a game-authoring environment that allows artists, musicians and developers to maximize their creative freedom and reduce engineering costs. Techniques provided in accordance with the present invention can be used in the context of a hierarchical articulated system, to efficiently provide lifelike and natural motion of a variety a complex humanoid, animal and other simulated animated objects.

[0014] In accordance with one aspect of this invention, a reference object is defined as the root of the articulated system. Transformation matrices describing the motion of this reference object are constrained to translations. This means the matrices can be easily inverted. The ability to easily invert theses matrices avoids the cost of computing, at run time, a “relative” matrix representing change relative to the last transformation.

[0015] In accordance with another aspect of this invention, a sequence of transformation matrices defines an animation sequence for an articulated part of the reference object. This sequence of transformation matrices is constructed as absolute transformations. That is, the translations described by the transformation matrices are not relative to the previous position of the articulated system, but instead are defined with respect to the origin of the object's coordinate system. Because each animation step references the origin (as opposed to a “last” position), each step is essentially self-contained—and can thus serve as the departure point for any other arbitrary transformation (e.g., the first step of a different animation sequence).

[0016] In accordance with a further aspect of the invention, a connection matrix is saved at each animation step to represent the current transformation status of the animated object. This connection matrix embodies the result of the entire history of all previous transformations on the object. This connection matrix is obtained at each animation step by continuously concatenating an external matrix, if any, with the transformation matrix for the animation step. The historical information the connection matrix stores is used to further transform the animation, and is also stored for use in the next successive animation step(s).

[0017] Although the transformations performed in accordance with the present invention can be implemented by multiplying the various matrices together to achieve a single transformation matrix which is then applied to the object, one way to think about the transformation process in accordance with one embodiment of the present invention is as follows:

[0018] the object is transformed by the inverse translation of the current animation step;

[0019] the external transformation (if any) is inserted (e.g., based on real time input);

[0020] the object is (re)translated based on the current animation step's translation matrix;

[0021] the connection matrix saved from the last animation step is used to concatenate with above transformation with matrix; and

[0022] the next animation step's transformation matrix is applied to obtain the object's new location and orientation.

[0023] Because these techniques relate the object back to its reference coordinate system origin, they can be efficiently used at any arbitrary point in an animation sequence. This allows any arbitrary frame of an animation sequence to be a departure point for a different animation sequence. Furthermore, because the transformation matrices are defined as absolute translations, the transformation calculations are very efficient (for example, perhaps ten times faster than otherwise in some contexts); and provide a very high degree of natural realism and fluid motion. As one dramatic example, a character that is animated in accordance with the present invention can efficiently and rapidly shift from doing backward handstands to doing forward handstands in a very realistic and fluid manner without interruptions. Furthermore, the calculations provided by the present invention are very inexpensive from a computational standpoint, and are therefore particularly suited for high-speed execution on restricted- resource graphics platforms such as 3D home video game consoles. Such efficiencies also help provide quick prototyping of newly authored animations.

[0024] The present invention thus allows an artist to choose a single translation direction (e.g., the most convenient one to model) relative to a reference origin, for authoring a particular animation. The direction of translation and the orientation of the object being animated can be easily and efficiently changed at run-time to any arbitrary orientation and/or translation direction, based on insertion of an external transformation matrix. Furthermore, a connection matrix continuously concatenated with the animation sequence animation matrices can be used to supply a different object location (e.g., based on the object's prior history in the 3D universe). Still further, the artist may author an animation sequence having any arbitrary duration, since the sequence can be efficiently interrupted at any time in the real-time animation process to bridge into a different animation sequence. These added flexibilities make it possible for a graphics artist without much or any programming experience to easily author extremely realistic and fluid animations.

[0025] These and other features and advantages of the present invention will be better and more completely understood by referring to the following detailed description of presently preferred example embodiments in conjunction with the drawings, of which:

[0026] FIG. 1 shows an example prior art “key frame” animation technique;

[0027] FIG. 1A shows an example prior art hierarchical articulated character model;

[0028] FIG. 1B is a schematic illustration of an example prior art database representation of the FIG. 1A hierarchical model;

[0029] FIG. 1C is an example 3D graphics display system the preferred embodiment of the present invention can use to present animations on;

[0030] FIG. 2 schematically illustrates a reference object in accordance with the present invention;

[0031] FIG. 2A schematically shows successive transformations of the FIG. 2 reference object for sequential animation frames;

[0032] FIGS. 2B and 2C illustrate examples of how any arbitrary animation frame can be a departure for a new animation sequence;

[0033] FIG. 3 schematically illustrates an example animation process in accordance with the present invention;

[0034] FIG. 3A schematically shows insertion of an external transformation between frames k and k+1 of an example animation sequence;

[0035] FIG. 4 shows an example transformation technique for inserting an external rotation between the k and k+1 steps of an animation sequence;

[0036] FIGS. 4A-4D schematically illustrate a step-by-step explanation of the FIG. 4 process;

[0037] FIG. 5 is a flowchart of an example process performed in accordance with the invention; and

[0038] FIGS. 6A and 6B together show an example hierarchical object model provided by the present invention.

[0039] FIG. 1C shows an example 3-D real time computer animation system 50 that may be used to provide realistic interactive real time 3D simulation and animation in accordance with the present invention. The FIG. 1 example system 50 includes a NINTENDO 64® 3-D video game console 52 and associated hand controllers 54a, 54b. A cartridge 56, optical disk or other storage medium storing a software animation (video game) program is operatively connected to console 52. The console 52 is connected to a display device 58 such as a conventional home color television set or computer monitor. Console 52 includes a 3D graphics engine that can render 3D animation on display 58 in real time response to user manipulation of controllers 54a, 54b. The software within cartridge 56 controls console 52 to display a sequence of animated video frames on display 58. These animated video frames can serve to animate an arbitrary three-dimensional character 11 such as the character schematically shown in FIG. 2.

[0040] FIG. 2 shows definition of a reference object 50 with respect to arbitrary three-dimensional character 11. The reference object 50 (which may be a cube) is defined at the root of the hierarchical articulated system used to represent character 11 (see FIGS. 1B, 6A & 6B for example).

[0041] In accordance with one aspect of the present invention, all transformation matrices describing the motion of reference object 50 are constrained to translations only. Thus, these various translations will result in translating the reference object 50 along a piecewise-linear path. Those skilled in the art will recognize that this form of transformation matrix is relatively easy to invert (e.g., using only three additions)—making the inversion process computationally inexpensive and very efficient.

[0042] In accordance with another aspect provided by the invention, the transformation matrices defining animations are constructed as absolute transformations. That is, the transformations described by the transformation matrices are not relative to the previous position of the articulated system (e.g., a “Δ” between successive displayed frames), but instead are defined with respect to the origin of the object's coordinate system. Because these matrices are defined with respect to the origin of modeling space for the object, the transformation matrices applied to each animation step all relate back to a common reference origin. One implication of this technique is that any arbitrary animation transformation can follow any other animation transformation. This gives the animation system a much more lifelike and realistic appearance, allowing characters for example to change from a walk to a run or vice versa within the time of a single animation frame.

[0043] FIGS. 2A, 2B and 2C illustrate some the advantages provided by using such absolute transformation matrices. FIG. 2A shows an example animation sequence comprising animation step transformations 20(0), 20(1), 20(2), 20(3), 20(4), relative to the modeling coordinate system origin 22. For purposes of simplified illustration, FIGS. 2A and 2B show the modeling coordinate system as two-dimensional, but those skilled in the art will understand that in a 3-D graphics system this coordinate system will have another axis to make it be three-dimensional rather than two-dimensional.

[0044] Each of the various translation transformations of FIG. 2A independently relates back to and references the modeling coordinate system origin 24. The corollary of this construct is that each transformation describes the current position of the reference object 50 without reference to any prior transformation. This powerful construct allows any transformation to be a departure point for any other transformation (e.g., to change to direction of character motion, or even to being a completely different animation sequence).

[0045] FIG. 2C graphically illustrates this. Suppose axis 26 of FIG. 2C represents, in linear form, an animation path defined by the first few frames 20(0), 20(1), . . . of an example “walk” animation sequence. FIG. 2C shows that any of these frames can be a departure point for an entirely different animation sequence (e.g., a “run” animation sequence). Because each of the transformations in the FIG. 2C “walk” animation sequence is absolute (i.e. in accordance with present invention, each change in position (Δ) relative to the last animation frame is represented relative to the object's reference coordinate system origin instead of with respect to the last frame position), it becomes very easy and efficient to “interrupt” one animation sequence at any point in the sequence to begin a different animation sequence.

[0046] FIG. 3 shows the overall steps system 50 may perform to provide animation in accordance with a preferred example embodiment of the present invention. An initial step 30 defines the root of an articulated system (e.g., the FIG. 1A character) as a reference object (see FIG. 2), and constrains transformation matrices describing motion of the reference object to translations only. A second step 32 defines a sequence of transformation matrices M₁. . . , M_n−1and M_nrepresenting an animation sequence of the object or an articulated portion of the object, where each matrix is defined with respect to the origin of the object's coordinate system origin. A further step 34 performed at each animation step transforms the object or articulated portion thereof, based on the transformation matrix for the current animation step and an external transformation matrix (if any).

[0047] At any arbitrary step k of the animation, such an external rotation matrix Me (e.g., reflecting real time interactive inputs from a human game player) may be inserted between steps k and k+1 so the sequence would be changed to reflect the influence of this external transformation. The external rotation matrix may be a 4×4 matrix defining rotation, translation and/or scaling in any of the x, y and z directions. The transformation(s) defined by the external matrix may be supplied in whole or in part in response to interactive realtime input from a human player via a user input device; or they may be supplied by other events (e.g., operation of a concurrently running program). Step 34 concatenates this transformation with the last animation step results to obtain the current location and orientation of the object. Step 34 also saves, at each step in the animation, a connection matrix to represent the current transformation status of the animated object for use in such concatenation—and for use in carrying forward to succeeding animation steps, the cumulative distilled history of the orientation, size and position of the object or articulated portion thereof.

[0048] FIG. 3A graphically illustrates the transformation procedure of block 34. In the FIG. 3A graphical depiction:

[0049] <OX, OY> shows the position and orientation of an arbitrary object after a last animation step k;

[0050] <OX′, OY′> shows the consequence after k+1 steps without the interference of the external rotation; and

[0051] <OX″, OY″> is the result with the external rotation inserted for the k+1 step.

[0052] FIG. 3A uses the following notations:

[0053] M_kand M_k+1are “absolute” transformation matrices of animation step k and k+1, which are defined with respect to the origin of the object's coordinate system;

[0054] M_k+1=ΔM_k+1M_kwhere ΔM_k+1is the k+1 step transformation matrix defined with respect to the previous transformation M_k; and

[0055] M_eis the external transformation matrix containing only rotations.

[0056] An intuitive method might be to push the external transformation matrix Me onto the stack after pushing the current transformation M_k, then adding the “relative” transformation matrix M_k+1on top of that. This can be described by equation:

[0057] M″_k+1=ΔM_k+1M_e^rM_k

[0058] In practice, since all matrices are stored as the “absolute” transformations, it would be expensive to compute the relative transformation ΔM_k+1at runtime. Our approach instead uses the formula:

[0059] M″_k+1=M_k+1(−M_k^t)M_e^rM_k^tM_k

[0060] As a practical matter, this calculation can be performed by multiplying all of the various transformation matrices together to produce a resultant matrix that is then used to transform the object or articulated segment of the object.

[0061] FIG. 4 shows a more detailed sequence of computer-performed steps that may be used to efficiently implement the FIG. 3A transformation, and FIGS. 4A-4D graphically illustrate these various steps. In each of FIGS. 4A-4D, <OX, OY > represents the object location and orientation before the transformation operation, while <OX′, OY′> indicates that after the transformation. The first step is to invert the matrix M_kfor the current animation step, and to transform the object by the resulting inverse transformation (translation) of matrix M_kfor the current animation step (block 40) (see FIG. 4B). Next, an external transformation matrix M_eis inserted if one is being used (block 42) (see FIG. 4C). This external transformation matrix commonly may include orientation transformations based on real-time user inputs such as operation of a joystick or the like, but may also or alternatively include other transformations such as translation and/or scaling.

[0062] The object is then re-translated with the current step's animation translation matrix M_k(block 44) (see FIG. 4D)—thus “undoing” the FIG. 4B transformation by the inverse matrix. The result is concatenated with a connection matrix saved from the last animation step (block 46). The next animation step's transformation matrix M_k+1is applied to the concatenated result (see FIG. 4A—which operation may be performed at the beginning or at the end of the concatenation process as desired) to obtain the object's location and orientation. It is easy to observe that the final result of the transformation shown in FIG. 4D coincides with the one shown in FIG. 3A.

[0063] FIG. 5 is a flowchart of an example process performed by the FIG. 1C system to animate character 11. In this example, system 50 initially uses an identity matrix as the connection transformation matrix (block 102), and pushes the connection transformation matrix onto a system transformation matrix stack (block 104). System 50 then determines whether there is an external transformation (e.g., supplied based on operation of controller(s) 54 by a human user) (block 106). If there is an external transformation (“yes” exit to decision block 106), system 50 pushes the current translation matrix onto the stack (block 108); then pushes external transformation matrix onto the stack (block 110); and finally, pushes the inverse of the current translation matrix onto the stack (block 112). Thus, the external transformation matrix is effectively concatenated with the current transformation matrix and the inverse of the current transformation matrix (see FIGS. 4B-4D).

[0064] Whether or not there is an external transformation, system 50 pushes the transformation matrix for the next animation step onto the stack (block 114), multiplies all matrices onto the stack to produce a current connection matrix (block 116), and saves the result (block 118). This resulting current connection matrix is used to generate display of the k+1th animation frame, and is also pushed onto the stack for use in the k+2d animation step (block 104). As will be understood by those skilled in the art, further conventional transformations (e.g., from object space into world space and/or camera space) may be applied before the animation-transformed object is displayed on display device 58.

[0065] FIGS. 6A-6B show an example hierarchical data structure 200 that can be used to represent an arbitrary object 11 in accordance with the present invention. Data structure 200 is conventional except for its transformation table shown in FIG. 2B—which in this example stores sequences of transformation matrices of the type discussed above. In one example, each articulated joint of the 3D object will be separately defined in hierarchical data structure 200, and will have its own respective sequence of animation transformation matrices for each of N different animations (e.g., running, walking, doing handstands, falling, etc.) The matrices represented in transformation table 202 may be 4×4 matrices to allow translation, rotation and scaling factors to be represented in the same matrix. The transformation matrix sequences shown in FIG. 6B are used to perform the animation processes described herein.

[0066] While the invention has been described in connection with what is presently considered to be the most practical and preferred embodiments, it is to be understood that the invention is not to be limited to the disclosed embodiments, but on the contrary, is intended to cover various modifications and equivalent arrangements included within the scope of the appended claims.