Richard Kulpa and Fabrice Lamarche received the second price of the Deutch Telekom awards in the category "new technologies" for the coupling of MKM (Manageable kinematic motion) and TopoPlan (Topological Planner).

Real-time animation of virtual humans in complex environments

Introduction

The goal of behavioural animation is to automate the process of populating a virtual environment with autonomous virtual humans. Nowadays, the animation of virtual characters is used in various fields such as virtual reality, games, crowd simulations or numerical plant simulations for example. A large part of these application fields needs a realistic virtual human with natural gestures and credible behaviours. A virtual human behaviour is usually described through several skills. One of the most important is the ability to navigate inside a virtual environment as that skill is part of a large number of behaviours. Like humans, humanoids should be able to step upstairs or downstairs, avoid beams, adapt their posture to avoid collisions with an irregular ceiling... This natural human behaviour actually needs a huge effort to be mimicked.

Our solution tackles the problem of real-time virtual human animation, path planning and posture adaptation inside complex 3D environments (beam avoidance, putting a foot on each step of a spiral stair...). Our system proposes a fully automated process starting from an unconstrained 3D database which is able to animate several dozens of virtual humans in real-time while navigating inside the environment.

System overview

To reach such an ambitious goal, we have developed an animation engine for the motion adaptation of the characters and a topological planner to find the trajectory of the character and also to automatically extract the environmental constraints. The result of the combination of these two modules allows real-time navigation in complex environments such as spiral stairs or highly constrained environments.

MKM: Real time human animation

This animation engine offers several features that allow the adaptation of captured motions:

• Motion blending: several motions can be blended using intuitive priorities. Internal weights are then calculated for each body part in order to ensure continuity. A notion of negligible motions is also introduced to avoid the unexpected influence of motions with low priority compared to others. It allows the blending of walks and grasping motions in order to generate a movement such as grasping while walking for example.
• Motion synchronization: the synchronisation module ensures that two motions are compatible for blending. Using an algebraic operator and a time warping method, it ensures for example that at a time a motion with the left foot on the ground is not blended with another one with a right support. It is based on the stances that are automatically extracted from the motion using two thresholds: the maximum height of the foot and its maximum speed.
• Morphological adaptation: based on a morphology-independent representation of the motion, a same movement can be shared by any virtual humanoid (cf. Figure 1). This representation ensures that if the morphology is exactly the same then there is no loss of data.

Motion adaptation to geometric constraints: an inverse kinematics algorithm is proposed in order to handle external constraints. Based on an iterative method, it allows to adapt the motion of dozens of characters in real-time. The constraints can be placed to any point of the character, on the skin for example, not only on its skeleton. Since the constraints are verified in real-time, they can be defined relatively to other current posture or to other constraints.
Motion adaptation to ensure balance: in order to take the balance into account, a novel inverse kinetics algorithm is proposed and has been integrated with the inverse kinematics solver. This complex solver can consequently verify geometric constraints as well as a constraint on the centre of mass at the same time. The combination of these two algorithms allows the motion adaptation of dozens of characters in real-time.

TopoPlan: Topology and path planning

TopoPlan is composed of two processes: an offline 3D database analysis and an online path planning process. The offline process computes several useful structures:

• 3D spatial subdivision: a 3D spatial subdivision of the environment is computed on the basis of a 3D database describing the environment. This spatial subdivision is exact and has been designed to qualify floor and ceiling constraints for each point of the environment without any assumption on its geometry. This process is fully automated and do not require any user input.
• Topology extraction: topology relates to the characterization of homogeneous navigable zones and their connectivity. On the basis of the 3D spatial subdivision, the environment topology is computed. This process automatically identify each level of an environment, each step of a stair, computes bottlenecks and generates compact and optimal maps which can be used for several real time processes such as path optimisation, reactive navigation, spatial selectors? Parameters used to compute the topology are intuitive: the maximal navigable slope, the maximal surmountable height, the radius of a virtual human and the minimal height allowing navigation.
• Path planning graph: based on the environment topology, we generate compact a path planning graph ensuring optimal environment coverage while minimising the number of generated way points.

The online processes use the previous data structures to provide various efficient features such as:

• Path planning and trajectory optimisation: based on the path planning graph and the environment topology, the path planning process is able to compute paths an optimize trajectories in real time.
• Footprint generation: the aim of the footprint generation process is to correctly handle footprint generation on stairs by putting a foot on each step when climbing a stair and to limit the turn angle between to humanoid steps. This process generates realistic footprints by taking into account the environment topology and geometry.
• Environmental constraints extraction: based on the 3D subdivision and the topology, TopoPlan provides an efficient spatial requests scheme. Spatial selectors can be used to extract height constraints (distance between floor and ceiling) and to select steps / zones / obstacles lying in an arbitrary shape. The spatial request system has been carefully designed in order to enable an intensive use of such request inside various algorithms such as path optimisation, footprint placement optimisation, posture adaptation, reactive navigation...

Combination of MKM and TopoPlan

These two previous tools are combined in order to take the advantages of each of them. TopoPlan is used for the pre-processing of the environment and after in real-time for the path planning and the generation of the footprints. These information are at last used to constrain MKM in order to produce the final motion. This combination actually provides the following functionalities:

• Motion adaptation to floor and ceiling constraints. By using TopoPlan properties, a virtual human is able to avoid collision with beams by performing posture adaptations based on the height of the virtual environment. This process is full reactive. When this process is started all motions are automatically adapted without any user intervention or supplementary programming.
• Stair climbing. Based on the path planning process and footprint generator, the virtual human is able to correctly climb stairs by putting a foot on each step while climbing for example. Each type of stair is handled: regular, irregular, spiral for example.
• Navigation in highly constrained environments. Thanks to the bottlenecks computation and the optimal roadmap generation, if a path exists from one place to another, the virtual human will find it. A virtual human can navigate in real time inside very narrow passages while avoiding collisions with beams.

The complete system can then automatically make the virtual character navigate in highly constrained environments such as stairs (regular, irregular and spiral) but also in environment with complex floors and ceilings (cf. Figure 2).

Figure 2: walking in constrained environments

Results

The complete system composed of MKM and TopoPlan allows the navigation in complex environments simply using some intuitive parameters such as the minimal height under which the character does not want to walk or the maximal surmountable step for example. Indeed, all the complex parameterizations of the character such as the adaptation of the motion to its morphology are done automatically. Only the two steps that create the environment (spatial subdivision and extraction of the topology) are done offline. All the planning and the motion adaptations are calculated in real-time for dozens of characters. The navigation can simply be ordered choosing the destination of the character.