Computer graphics processing and selective visual display system – Computer graphics processing – Animation
Reexamination Certificate
1999-10-08
2003-09-30
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Animation
C345S427000, C345S619000
Reexamination Certificate
active
06628286
ABSTRACT:
FIELD OF THE INVENTION
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.
BACKGROUND AND SUMMARY OF THE INVENTION
Computers and video games have revolutionized animation—the process of showing a sequence of images in rapid succession to create the illusion of motion.
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.
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.
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.
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
.
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.
1
A. 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.
1
B. 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.
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.
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.
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) (&Dgr;) 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.
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
Comair Claude
Fam Sun Tjen
Ghali Prasanna
Li Xin
Samra Samir Abou
Nguyen Kimbinh T.
Nintendo Software Technology Corporation
Zimmerman Mark
LandOfFree
Method and apparatus for inserting external transformations... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for inserting external transformations..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for inserting external transformations... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3072072