The present invention relates to a system, method and computer program for generating computer images, primarily for use in a computer game environment.

Background of the Invention Realism in computer games and animation is a goal that is constantly driving the development and uptake of new technologies in software and hardware. Previously, realism was achieved by using complex graphical environments as backdrops for characters to move within. However, realism requires more than just an accumulation of detail. Objects in the world that the user or animated character is interacting with should react as their real- world counterparts would. This applies to objects reacting in a physically plausible way, for example falling over when pushed, and should also be applied to the characters in the world, so that they appear to inhabit it and walk on its surfaces in a plausible way.

Currently in games and general animation packages, characters are defined by skeletons that are made up of bones and joints that are animated using keyframing techniques. This involves specifying joint rotations over time. In games, these animations are produced in an offline process, which does not take into account the variation of terrain, but covers some general actions, for example walking on a flat surface, climbing stairs, etc. These animations are typically stored as animation loops that can be called on to cause the character to effect a particular walking type until a command is received to change. For example, a walking animation sequence would typically be stored for presenting an image of the character walking on a flat surface, and a stair climbing animation sequence would be stored for presenting the character climbing stairs etc.

An advantage of using off-line subroutines for causing movement of characters is that the skilled artist can instil an animation with life that a procedurally animated character might lack. For example, by calling the flat surface animation, the character can be caused to walk on a flat surface and by subsequently calling on the climb animation, the character can be caused to climb a set of stairs. A problem is, however, that the set of offline animations is used for all variations of terrain in the game or animation, so the character is animated as if walking on a flat surface even if it is actually walking over undulating terrain. This produces visual anomalies, such as the feet penetrating the landscape, floating above it and appearing to slide. As well as appearing unrealistic, this can detract from the immersive qualities of the game, so that the player may feel less affinity with the character or less involved in the game. A further problem is that the memory requirements are relatively high, because a suitable animation sequence has to be stored for every walking style of every character. For games with more than one character and indeed more than one player, this becomes particularly problematic.

A solution to this problem is to create or modify the animation to fit the environment. Much research has been applied to the generation of walking gaits for characters. Current techniques have focused on offline animation creation (i.e. complex physical simulation of walking) or more tightly controlled mechanisms for real-time animation (i.e. for characters whose motion path is known before-hand). Whilst these techniques can be suitable for non-interactive characters in games, they would not be suitable for player-controlled characters, because players expect more control and are consequently less predictable.

Summary of the Invention According to one aspect of the present invention, there is provided a method for generating an animation of a character having one or more feet and being able to move in a computer generated landscape in response to user inputs, the method comprising: analysing the landscape that is to be traversed by the character; determining a location in the landscape that is sufficient to accommodate a foot of the character, thereby to identify a next location for that foot; analysing the terrain between the start and the next location for the foot to produce a convex path that extends over any obstructions in the terrain; using the convex path to determine a path for the foot to follow; identifying a height difference between the start and next positions of the foot; determining an end position for a pre-determined part of the character's body, for example the pelvis, based on the swinging foot height difference and causing the said character to move in such a manner that the foot follows the convex path and the pre-determined part of the body is moved to the determined end position.

By dynamically analysing the terrain in the immediate vicinity of the character during play, it is possible to cause the character to move and interact with the environment in a realistic manner based on real-time calculations and assessments of the terrain in which the character is moving. This is particularly advantageous for interactive games, because it means that the number of image frames that have to be stored can be greatly reduced. Indeed, in a preferred embodiment of the invention only a single animation is stored and used to dynamically generate all character images, whether walking on a flat surface or going up-hill etc. This results in significant memory saving.

In the event that the height different indicates that the immediate landscape is up-hill, the method may involve moving the pelvis up by an amount corresponding substantially to the determined height difference by the middle of the step, and maintaining the pelvis at that new height until the next step is taken. Moving the pelvis up may involve using an ease-in-ease-out curve and/or a bezier curve.

In the event that the height different indicates that the immediate landscape is lower than the start landscape, the method may involve moving the pelvis down by an amount corresponding substantially to the determined height difference by the middle of the step, and maintaining the pelvis at that new height until the next step is taken. Moving the pelvis down may involve using an ease-in-ease-out curve and/or a bezier curve.

The method may use a damp spring function to vary a degree of bounce in the character's walk/gait. This can be used to convey personality and/or emotional state of the character.

The method may involve setting a pre-determined limit on the height difference that is allowed. In this way, the step size taken by the character can be kept within a physically realistic range, so that the character is not caused to step up or down by an unfeasibly high amount. In the event that the predetermined limit is exceeded, the method may involve identifying another foot placement location.

The landscape that is to be analysed may be that part of the landscape that is within two steps of the character's current position in the direction of travel. The step length may be a pre-determined amount. A range of pre-determined step lengths may be stored, each being usable for a different movement style. For example, the stored step length for use when the character is running may be greater than that for use when the character is walking. According to another aspect of the invention, there is provided a system or device for generating an animation of a character having one or more feet and being able to move in a computer generated landscape in response to user inputs, the system or device comprising: means for analysing the landscape that is to be traversed by the character; means for determining a location in the landscape that is sufficient to accommodate a foot of the character, thereby to identify a next location for that foot; means for analysing the terrain between the start and the next location for the foot to produce a convex path that extends over any obstructions in the terrain; means for using the convex path to determine a path for the foot to follow; means for identifying a height difference between the start and next positions of the foot; means for determining an end position for a pre¬ determined part of the character's body, for example the pelvis, based on the said height difference and means for causing the said character to move in such a manner that the foot follows the convex path and the pre-determined part of the body is moved to the determined end position.

According to yet another aspect of the invention, there is provided a computer program, preferably on a data carrier or computer readable medium, for generating an animation of a character having one or more feet and being able to move in a computer generated landscape in response to user inputs, the computer program having code or instructions for analysing the landscape to be traversed by the character; determining a location in the landscape that is sufficient to accommodate a foot of the character, thereby to identify a next location for that foot; analysing the terrain between the start and the next location for the foot to produce a convex path that extends over any obstructions in the terrain; using the convex path to determine a path for the foot to follow; identifying a height difference between the start and next positions of the foot; determining an end position for a pre-determined part of the character's body, for example the pelvis, based on the foot height difference and causing the said character to move in such a manner that the foot follows the convex path and the pre-determined part of the character's body is moved to the determined end position.

Brief Description of the Drawings Various aspects of the present invention will now be described by way of example only and with reference to the accompanying drawings, of which: Figure 1 is a representation of a character walking on a flat surface; Figure 2 is a diagrammatic representation of a trajectory of the pelvis and moving foot of the character of Figure 1; Figure 3 is a diagrammatic representation of the trajectory of the pelvis and the foot of a character walking over a discrete obstruction; Figure 4 is a representation of a character walking uphill; Figure 5 is a representation of a character walking downhill; Figure 6 is a representation of a character walking on an uneven surface, and Figure 7 is a diagrammatic representation of the trajectory of the pelvis and the foot of a character that is walking over an uneven surface.

Detailed description of a Specific Embodiment The present invention provides a skeletal animation system for interactive games and a unique algorithm that modifies the animation to allow bipedal characters to walk over arbitrary terrain in a visually plausible fashion in response to interactive user inputs. To implement this, a skeletal animation blending system is provided. This allows multiple animations to be blended and applied to a skeleton using a series of masks and weights consecutively in what is termed an animation blend chain. This produces a series of joint rotations and translations, which can be applied to a skinned character in a game or animation. The blending system takes the output from skeleton controllers, which are the orientations and positions of the joints in the skeleton. These controllers can be anything from a basic animation controller (playing an existing animation), a physics controller or a user-defined controller. The weight determines how much the skeleton pose is blended with the result of the previous stage in the chain and the mask determines which joints this blend is applied to. For example, two walk cycles can be blended to produce a hybrid which is only applied to the character's legs, while a third animation can be applied to the upper body, with inverse kinematics applied to an arm holding a weapon. Animation blending schemes are well known in the art and so will not be described in detail.

To allow a skeletally animated character to walk in a realistic fashion over any type of terrain, a biped algorithm is provided within the main animation application. This algorithm uses only a single animation sequence to generate solutions over varying terrains and is operable to cause movement of the character in response to user inputs. The biped algorithm is operable to maintain the height of the pelvis above the supporting foot as the character walks over uneven terrain. This works on the assumption that the pelvis should be at the same height above the supporting foot by the middle of a step as the character were it walking on a flat surface. This mid-step position is known in animation as the passing position. This is necessary so that there is enough space between the pelvis and the ground to allow the swinging foot to pass under the character. This is also usually the point when the pelvis reaches its maximum height in the animation, which is referred to as the summit at mid-stance in some gait-generation literature.

The biped algorithm uses inverse kinematics to fix the supporting foot in position to eliminate foot sliding and to adjust the trajectory of the swinging foot to avoid obstacles in the landscape that the foot would otherwise pass through in an unrealistic manner. More specifically, a simple standard analytical inverse kinematics solver is used for two bone chains in the limbs of the animated character. At the beginning of a new step, the landscape immediately in front of the character is analysed in the direction the step will be taken, from the current position of the swinging foot just before it leaves the ground. This produces a cross-section of the landscape for two step-lengths ahead. Using this information the algorithm attempts to predict where the character will place its foot next. From the standard step-length taken from the animation, the algorithm works backwards (towards the character) until it finds a piece of terrain that is big and flat enough to accommodate the foot.

Figure 1 shows a character 10 walking along a flat, unimpeded surface 12. With each step, the biped algorithm checks the terrain that is about to be traversed to find a suitable position for the character to place its foot. Once the application finds a suitable foot position, the intervening terrain between the start and end of the step is analysed. If a foot placement is found and the swinging foot is not obstructed and there is no significant height difference between the start and next foot placement positions, the animation is scaled in the horizontal direction by a factor to achieve the correct contact position, see Figure 2. This is a simple linear scale of the animation purely in the horizontal direction and does not affect the vertical animation at all. If a foot placement is found, but an obstruction 14 is identified, a convex path / hull 16 is determined. This is selected so that it extends over any obstructions 14 that lie in the path of the swinging foot, see Figure 3. The convex hull is then used to determine a trajectory for the swinging foot that is such as to cause the foot to step over the identified obstruction, hi particular, the swinging foot is adjusted vertically using inverse kinematics to ensure that it is the same height above the convex hull 16 as it would have been above a horizontal surface were the obstruction 14 not present. This process is simplified by including the height of the foot above the ground in the animation data. To ensure that the foot swinging motion is realistic, a limit on the height of the convex hull 16 is set, so that the character cannot be caused to step up or down by amounts that are physically unfeasible. Hence, this step can also be used to identify any obstructions 14 in the way of the swinging foot that are too large to be stepped over.

If a suitable foot placement is not found or there is an obstruction 14 that is too large for the swinging foot, the biped algorithm lets the main animation application know, so it can take appropriate action. The biped algorithm does not make decisions that could affect game play, hi the event that the biped algorithm informs the application that it cannot identify a suitable path for the character to follow, the application may then seek input from the game player or initiate a subroutine for causing, for example, the character to jump or change the direction of movement, thereby to overcome or avoid the obstacle.

As well as identifying and stepping over obstructions 14, the biped algorithm is operable to identify whether the character is being directed up a hill or alternatively down a bill within the immediate terrain. To do this, the height difference between the start position of the swinging foot and the predicted end position is compared, hi the event that the character is going up or downhill an appropriate algorithm is selected to adjust the height of the pelvis during the step. This will be described with reference to Figures 4 to 7.

Figure 4 shows an example of a character 10 walking uphill walk. As for the example of Figures 1 to 3, the current position of one of the character's feet is noted and a next position is identified. Then, the height difference between the current and next positions is calculated. In this case, the height difference between the start and end positions of the swinging foot is indicative of an up-hill slope. This causes the biped algorithm to select the uphill algorithm. This is operable to use the height difference to raise the character's torso relative to a pre-determined fixed point, usually the character's pelvis, to the desired position by the middle of the step, after which the character is animated as per the flat animation. The transition in the first half of the step can be achieved in various ways, for example by using a simple ease-in ease-out curve. Alternatively, a bezier curve could be used instead to ensure continuity between the transition curve, the preceding curve and the following curve. Additionally or alternatively a damped spring could be used to add or remove more bounce to the character's walk by adjusting the spring stiffness and damping factors.

Figure 5 shows an example of a character 10 waking down hill. As before, the current position of one of the character's feet is noted and a next position is identified. Then, the height difference between the current and next positions is calculated. In this case, the height difference between the start and end positions of the swinging foot indicates a down-hill slope. This causes the biped algorithm to select the down-hill algorithm. This is operable to use the height difference to lower the character's torso relative to a pre¬ determined fixed point, usually the pelvis, until the middle of the step, after which it moves into a position so that it is at the same height as it would be at the beginning of the step on the flat (above the new supporting foot). As for the uphill algorithm, the downhill algorithm uses a simple ease-in ease-out curve to adjust the height of the pelvis over the "down" section of the step animation.

Figure 6 shows an example of a person walking on uneven terrain. In this case, the terrain is treated like a flat slope as far as the pelvis is concerned, and the swinging foot follows the convex hull 16 of the geometry it is passing over, with the height difference between the start and end of the step determining which of the up-hill or down-hill algorithms to use. The trajectory of the pelvis and moving foot of the character of Figure 6 is shown in Figure 7.

The present invention provides a solution to the problem of how to provide realistic movement of a biped in an interactive computer games environment that can fit into existing production processes without affecting the amount of work required on the part of the programmers or the artists. The invention also provides a technique for eliminating foot sliding, improving character locomotion over arbitrary terrain, as well as providing a standard library to handle general skeletal animation tasks a developer would need for most applications. This can be done using an algorithm that is lightweight enough for even low-powered processors, as it requires a few trigonometry functions that could be handled using look-up tables. This means that a practical implementation can be reduced to a few multiplies and additions per inverse kinematics calculation. This is ideal for legs and arms and could also be applied to the torso and head or any other chains in a skeleton.

A skilled person will appreciate that variations of the disclosed arrangements are possible without departing from the invention. For example, whilst the description and drawings refer to a skeleton that has a substantially human form, it will be understood that the methodology of the invention could be applied to any type of character. In this regard, it will be understood that the term "foot" is intended to cover for example paw, in the event that the character is a bear or other such animal, or hoof, in the event that the character is a horse, etc. Accordingly the above description of the specific embodiment is made by way of example only and not for the purposes of limitation. It will be clear to the skilled person that minor modifications may be made without significant changes to the operation described.