During FMX 2008 conference, Deutsch Telekom organized the first session of the Deutsh Telekom awards. This award rewards authors of innovative projects in three categories: « Best new technologies in effects and animation », « Young Talents award », « Best Interactive Design & Usability ». Fabrice Lamarche (University of Rennes 1, INRIA project Bunraku) and Richard Kulpa (University of Rennes 2, M2S – Bunraku) were awarded of the second prize in « Best new technologies » category for their work on TopoPlan, MKM and their combination. This price have been issued by a jury composed of Neil Trevett (Vice President Embedded Content, NVIDIA), Eric Tabellion (Animation Technology, PDI – Dreamworks), Remi Arnaud (COLLADA contributor and promoter member, The Khronos Group) and Akiko Maeta (NetPeople Lead Producer, Inago).

Bunraku project, in collaboration with M2S on biomechanical aspects, have been working for several years on behavioural animation. The aim of this work is to provide models and tools enabling the creation of autonomous virtual humans endowed with credible behaviours. Models and tools awarded by the Deutsch Telekom awards are part of this research. The first tool, MKM (Manageable Kinematic Motions), is dedicated to real time virtual human animation. The second tool, TopoPlan (Topological Planner), performs automatic 3D database analysis in order to extract 3D topology of a virtual environment and computes optimized data structures dedicated to path planning and reactive navigation. The combination of both models handles, in real time, the navigation of several dozens of virtual humans planning their path inside complex environments while adapting their postures to environmental constraints.

Manageable Kinematic Motions (MKM).

MKM is a tool dedicated to real time virtual human animation. This engine uses motion captures to generate complex and realistic animations and proposes the following features:

• Motion blending. Several motions can be blended using intuitive priorities. Internal weights are then calculated for each body part in order to ensure animation continuity. For example, it allows the blending of walks and grasping motions in order to generate a movement such as grasping while walking.

• Motion synchronization. The synchronisation model ensures that two motions are compatible for blending and enforce animation realism. It uses an algebraic operator and a time warping method to automatically synchronize motions. For example, when blending two locomotion movements, motions are synchronized on support phases in order to enforce resulting motion realism. Stances are automatically extracted from the original motion capture.

• Morphological adaptation. MKM uses a morphology-independent representation of the motion. In real time, motions are retargeted on different morphologies. (cf. Figure 3: morphological adaptation).

• Motion adaptation to geometric constraints. An inverse kinematics algorithm is proposed in order to handle external constraints. Based on an iterative method, this algorithm allows adapting the motion of dozens of characters in real time. The constraints can be placed on any point of the character such as on the skin for example. As the constraints are verified in real time, they can be defined relatively to other postures 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.

Figure 3: morphological adaptation

Topological Planner (TopoPlan

is a software performing 3D environment analysis in order to extract its topology. From the topology, different structures dedicated to path planning, environmental queries and posture adaptation are computed.  Those structures are used in real time to control the virtual human animation while navigating inside a 3D environment. It is composed of two processes: an offline 3D database analysis and an online path planning and query process. This tool proposes the following functionalities:

• 3D spatial subdivision. A 3D spatial subdivision of the environment is computed using a 3D database. This spatial subdivision is exact and has been designed to qualify floor and ceiling constraints for each point (or zone) of the environment without any assumption on its geometry. This process is fully automated and does 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 identifies 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 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 a compact path planning graph ensuring optimal environment coverage while minimising the number of generated way points.

• Path planning and trajectory optimisation. Based on the path planning graph and the environment topology, the path planning process is able to compute paths and optimizes trajectories in real-time.

• Footprints generation. The aim of this process is to correctly handle footprints generation on stairs by putting a foot on each step when climbing a stair and to limit the turn angle used between two 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.

MKM and TopoPlan have been combined in order to propose a unique system handling the animation of several dozens of virtual humans adapting their motion to environmental constraints in real time (collision avoidance with ceiling or stair climbing for example). The quality of the combination is based on two properties: the capacity of TopoPlan to extract, in real time, environmental constraints and the capacity of MKM to apply constraints in real time. The combination of those models currently proposes 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 postural adaptations based on the height of the virtual environment. This process is fully reactive. When this process is started, all motions are automatically adapted without any user intervention or supplementary programming.
• Stairs climbing. Based on the path planning process and footprints 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 and 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 (cf. Figure 4: posture adaptation in constrained environments).   

Figure 4: posture adaptation in constrained environments

The complete system automatically allows the virtual character to navigate in highly constrained environments by using few intuitive parameters such as minimal height allowing navigation or maximal surmountable step height for example. Moreover, the complex parameterization enabling motion adaptation to environmental constraints and morphology are done automatically by MKM and its combination with TopoPlan. Only the step creating environmental data is done offline. Path planning and motion adaptation to environmental constraints are done in real time and performances of the system are compatible with the animation of several dozens of characters in real time. Future works will focus on animation control during reactive navigation while keeping all good properties of current algorithms (precise footprint handling, motion adaptation) and will generalize motion adaptation to environmental constraints.

Download Videos

Contacts: Fabrice Lamarche [TopoPlan]            Richard Kulpa [MKM]