Fabrice Lamarche
email: fabrice.lamarche@irisa.fr

TopoPlan: a topological path planner for real time human navigation under floor and ceiling constraints

TopoPlan: a topological path planner for real time human navigation under floor and ceiling constraints

Introduction

One of the goal of behavioral animation is to automate the process of populating a virtual environment with autonomous virtual humans. Models used to describe humanoid behavior have to combine long term planning and reactivity to enable local adaptation to different environmental constraints. One of the most important behaviors is the ability to navigate inside a virtual environment. Like humans, humanoids should be able to walk upstairs or downstairs, avoid beams and adapt their posture to avoid collisions with an irregular ceiling. This natural behavior actually needs a huge effort to be mimicked.

Virtual environments are provided as 3D triangular meshes modeled by designers (architects, graphics designers...). In order to endow a virtual human with a navigation process, this 3D triangular mesh needs to be analyzed in order to produce efficient structures enabling fast and accurate path planning inside constrained environments. On the other hand, humanoid motion should be adapted to match constraints imposed by the environment (beam avoidance, stair climbing...). To the best of our knowledge, few models propose to solve all those problems in a unified architecture and none is capable of generating such motions for several dozens of humanoids in real time.

In this paper, we address the problem of path planning and motion adaptation in complex 3D environments. We propose an architecture handling spatial analysis, accurate path planning and motion adaptation to environmental constraints. Proposed algorithms make a compromise between exact environment representation and performance. Environment representation is based on an exact spatial subdivision which is analyzed in order to extract environment topology and generate a concise and accurate roadmap. Based on this representation, several runtime algorithms are proposed: optimized path generation, accurate footprint placement and posture adaptation to floor and ceiling constraints. Those algorithms have been designed to match behavioral animation requirements: performance and reactivity.

This paper is organized as follows. In the next section, previous works centered on environment representation, path planning and motion adaptation during locomotion are presented. The following sections detail the environment representation and proposed mo-1 tion control processes. Finally, results and performance analysis are discussed.

Related works

Path planning and environment representation have been widely studied in the field of robotics where navigation is a necessary task to achieve [START_REF] Latombe | Robot Motion Planning[END_REF][START_REF] Lavalle | Planning Algorithms[END_REF]. The aim of the proposed methods is to represent the environment free space. Three general approaches, differing in their representation of free space, can be distinguished: roadmaps, cell decomposition and potential fields. The roadmap approach captures the connectivity of the free space by using a network of standardized paths (lines, curves). Different approaches can be used to compute roadmaps. The visibility graph [START_REF] Arikan | Efficient multi-agent path planning[END_REF] connects together vertices of the environment geometry if and only if they see each other. This approach ensures finding the shortest path between two configuration but can be memory consuming in open environments with sparse obstacles. An alternative is to compute the generalized Voronoi diagram [HIKL * 99] inside the free space [SGA * 07]. The property of such a method is to generate paths maximizing clearance with obstacles. The probabilistic roadmap consists of generating non colliding configurations by randomly sampling the free space and linking those configurations if a collision-free linear path connects them. Such method has been used to plan paths inside 2D virtual environments [START_REF] Bayazit | Roadmap-based flocking for complex environments[END_REF] or huge 3D environments [START_REF] Salomon | Interactive navigation in complex environments using path planning[END_REF] and has demonstrated its capacity to deal with relatively high dimensional problems [START_REF] Kavraki | Probabilistic roadmaps for path planning in highdimensional cončguration spaces[END_REF]. A combination of random sampling and Voronoi diagrams have also been used in the AERO system to compute adaptative roadmaps in order to interactively plan paths inside dynamic environments [SAC * 07]. The Rapidly exploring Random Trees (RRT) [KL00] is a single query method which tries to cover free space with a tree of random configurations. The root of the tree is the initial configuration whereas leaves converge to the goal. The cell decomposition method consists of decomposing free spaces into cells. Two general methods can be distinguished: the approximate cell decomposition and the exact cell decomposition. The approximate cell decomposition consists of using predefined cell shapes, whose union is strictly included in the free space (uniform grids, quadtrees, circles) [BT98, Kuf98, SYN01, PLT06, ST06]. The exact cell decomposition consists of computing cells such that their union is exactly the free space (constrained Delaunay triangulation, convex polygons, trapezoidal) [START_REF] Kallmann | Fully dynamic constrained delaunay triangulations[END_REF][START_REF] Lamarche | Crowd of virtual humans: a new approach for real time navigation in complex and structured environments[END_REF]. The representation complexity of the latter method is directly dependent on the input geometry complexity. Finally, the potential field method consists of computing an artificial potential function in order to guide the entity to its goal by using gradient methods. The main problem of this technique is that it is subject to the local minimum problem and does not necessary reach the goal. This problem can be partially solved by providing good potential functions or by executing random moves [START_REF] Kavraki | Analysis of probabilistic roadmaps for path planning[END_REF].

Coupled with path planning, a second problem arises: how can we generate plausible motions inside complex environments such as environments with stairs, beams or pillars? In order to generate plausible animations, multi stage methods have been proposed. A humanoid is approximated by a bounding volume (generally a cylinder) in order to compute a collision free path inside the environment. Coupled with global path planning strategies, motion controllers [START_REF] Kuffner | Goal-directed navigation for animated characters using realtime path planning and control[END_REF] or local planning methods are used to adapt the humanoid motion to environmental constraints. The approach of Pettré et al. [START_REF] Pettré | 3d collision avoidance for digital actors locomotion[END_REF] consists of using a probabilistic roadmap in order to plan a global path. Once the path is computed, a global motion is generated and body parts colliding with obstacles are identified. Those colliding parts are then modified by using a randomized search in order to avoid obstacles colliding with the upper part of the body. The resulting motion is then warped with the initial motion. In [START_REF] Choi | Planning biped locomotion using motion capture data and probabilistic roadmaps[END_REF], sequences of valid footprints are searched through a probabilistic roadmap augmented with a posture transition graph. Each pair of footprints is then substituted with corresponding motion clips. This approach tends to generate realistic motions and is able to generate locomotion on uneven grounds as well as jumps over holes.The approach of Li consists of representing the free space by using regular multi-layered grids and a cost function optimization to compute footprints [START_REF] Huang P.-Z | Motion planning for humanoid walking in a layered environment[END_REF] even on unconnected surfaces [START_REF] Huang P.-Z | Planning humanoid motions with striding ability in a virtual environment[END_REF]. An inverse kinematics (IK) method is then employed to generate human locomotion. In the work of Shiller et al. [START_REF] Shiller | Planning motion patterns of human figures using a multi-layered grid and the dynamics filter[END_REF], a multi-layer grid is used to represent the configuration space for a humanoid with different locomotion such as walking and crawling. The humanoid is able to change its posture along a global path by using several bounding volumes extracted from the predefined locomotion behavior. The approach proposed in [START_REF] Lau | Behavior planning for character animation[END_REF] uses finite state machines in order to encode possible transitions between motions traducing possible motion / state transitions. This state machine is used by a search technique (A * and variants) in order to provide possible states. The environment is represented by a 2D height field grid map. This map encodes free space, obstacles and their proximity and also contains information about special obstacles the character can crawl under. This environment representation is used to prune the exploration tree. This technique has been extended in [START_REF] Lau | Precomputed search trees: Planning for interactive goaldriven animation[END_REF] by using a precomputed exploration tree to improve the system performance.

Techniques handling motion adaptation during locomotion use a two step process. The first step relies on a specific environment representation on which global path planning is based. The second step uses this representation in conjunction with specific algorithms to select and / or adapt motion to environmental constraints. Most approaches use either probabilistic roadmaps or regular grids to represent the environment. Probabilistic roadmaps enable path planning in high dimensional configuration spaces but raise several problems. The most important one is related to the probability density during sampling. The process may fail to capture the connectivity of a very constrained environment if probability densities are not carefully tuned [START_REF] Kavraki | Analysis of probabilistic roadmaps for path planning[END_REF][START_REF] Saha | Finding narrow passages with probabilistic roadmaps: The small-step retraction method[END_REF]. Moreover, suppose that the environment contains a constrained spiral staircase. Without further environment analysis, it is hard to ensure that each step will be identified. On the other hand, using regular grids may provide better results but this technique is very sensitive to the grid resolution. A precise grid resolution, as well as high probability densities during sampling, generates precise representations. But it also increase memory consumption and decrease planning performance. Techniques used to select / adapt humanoid motions fall into one of the three following categories: search of an adequate motion in order to enforce the quality of the resulting animation [CLS03, LK05, LCL05, SH07]; use of a bounding volume to avoid collision [START_REF] Shiller | Planning motion patterns of human figures using a multi-layered grid and the dynamics filter[END_REF]; use of a randomized search in order to generate collision free motion [START_REF] Pettré | 3d collision avoidance for digital actors locomotion[END_REF][START_REF] Yamane | Synthesizing animations of human manipulation tasks[END_REF]. Processes using motion adaptation are the more general but are generally non realtime for one character and do not scale to the animation of several dozens of characters in real time. Finally some hard navigation problems such as climbing a constrained spiral staircase, walking on a curved ground while avoiding collisions with a curved ceiling or avoiding a beam while climbing a step have not been demonstrated.

In the following, we will show that our approach based on an exact 3D spatial subdivision of a static en-vironment is able to deal with such problems. It generates accurate and concise roadmaps covering all accessible zones and enables the creation of reactive motion control processes handling path optimization, accurate footprint placement and posture adaptation under floor and ceiling constraints in real time.

Environment representation

The aim of the proposed environment representation is to exactly represent the free space of an unstructured 3D database while providing efficient data structures dedicated to environment analysis, environmental queries and path planning. Our representation is defined by several complementary visions of the same environment. Firstly, an exact 3D prismatic spatial subdivision of the 3D database is computed. Based on this 3D spatial subdivision and some humanoid characteristics, a topology identifying interconnected continuous navigable zones is computed. This topology is then summarized in 2D topological maps that accurately identify obstacles and steps borders as well as bottlenecks. Those topological maps enable the reduction of 3D computational problems to simpler 2D problems and are a prerequisite for the computation of lightweight roadmaps which automatically cover all accessible free space. In the following, each component of this environment representation is discussed.

Input geometry and preprocessing

Our spatial subdivision process does not make any assumption on the input geometry. However, some requirement has to be fulfilled before computation. Firstly, the geometry has to be described by a set of unorganized triangles. Secondly, this mesh has to be clean, i.e. it does not contain degenerate triangles and all triangles intersections have to be materialized by a shared vertex or a shared edge. The required cleaning step can be achieved by classical 3D modelers or by using computational geometry libraries such as CGAL 1 . Once a clean mesh is computed, we apply a simplification step consisting in representing the mesh with complex 3D planar polygons instead of triangles. Those polygons are computed by partitioning the set of mesh triangles into sets of coplanar and connected triangles knowing that two triangles are connected if and only if they share a common edge and if this edge is not shared by another triangle of the input geometry.

Prismatic spatial subdivision

The aim of our prismatic spatial subdivision process is to organize a set of 3D polygons in order to capture ground connectivity and identify floor and ceiling constraints. It represents the environment by a set of vertical 3D prisms dividing the 3D database into layers.

In order to explain our algorithm, we will use the example presented Fig. 1. Step (1) presents a simple environment composed of two triangles. The first step of the prismatic spatial subdivision computation consists of projecting the boundaries of each 3D planar polygon on the XY plane (the ground plane). This produces a set of 2D segments (3) on which a constrained Delaunay triangulation [START_REF] Boissonnat | Algorithmic Geometry[END_REF] is applied (4). This triangulation defines a triangle partition T 2 of the convex hull of the environment projected onto the XY plane. An important resulting property is that each 3D polygon of the environment mesh exactly projects itself on the union of one or several triangles of T 2 . The prismatic subdivision is then obtained by associating to each 2D triangle of T 2 , the set of 3D polygons partially projecting on it. Technically, the latter relation can be computed by using ray casting techniques. Once this relation is computed, for each triangle t of T 2 and for each associated polygon p, we compute a triangle (called 3D cell) such as this triangle is supported by the plane supporting p and its projection on XY plane is exactly t. The resulting subdivision is illustrated by step (5) in Fig. 1. Let prism(t) be the relation giving the list of all 3D cells which are exactly projecting on a triangle t of T 2 . The relation prism, coupled with the triangular map T 2 defines the prismatic spatial subdivision. In this spatial subdivision, vertical polygons are not represented as they project on a single segment. Vertical polygons constrain the accessibility between cells, thus they will be taken into account during the topology extraction phase. As shown on the example of Fig. 1, the extracted 3D cells perfectly identify overlapping parts of the environment geometry with cells belonging to the same prisms. Each prism defines several layers of 3D cells, knowing that if a 3D cell is surmounted by another one, the lower cell can be identified as a potential floor whereas the upper one corresponds to its associated ceiling.

Due to the properties ensured by the geometry preprocessing (all faces intersections are materialized thanks to a shared vertex or a shared edge) and to the spatial subdivision construction, cells belonging to prism(t) can be ordered along the Z axis. Thus, for each triangle t ∈ T 2 , we sort the list of 3D cells of prism(t) in the increasing order of the average Z coordinates of the vertices of the 3D cells. Let consider a triangle t ∈ T 2 , and two cells (c 1 , c 2 ) belonging to prism(t). If c 2 is after c 1 in prism(t), then c 2 is over c 1 . Moreover, if c 2 is immediately after c 1 in prism(t) then c 2 is the ceiling corresponding to the floor defined by c 1 . The Fig. 3 presents a top view of the prismatic spatial subdivision of our testing environment along with two sample prims identifying floor and ceiling constraints under a beam.

This spatial subdivision has two good properties in terms of topology computation. Firstly, the triangle map T 2 coupled with the prism relation identifies floor and ceiling enclosing each point of the environment. Secondly, the triangle partition T 2 defines a 2D connectivity between prisms of the environment. This property can be used to extract the environment topology by possibly connecting cells belonging to two adjacent prisms.

Topology and 2.5D surfaces

The aim of the topology computation is to characterize navigable zones of the environment with respect to humanoid characteristics. This process determines 3D cells spatial relations and identifies homogeneous and continuous navigable surfaces.

In order to characterize the topology with respect to humanoid characteristics, several parameters have to be defined: the minimal navigable height (H m ), the maximal navigable slope (S m ) and the maximal height of a surmountable step (H s m ). Moreover, several functions related to the cells of the 3D subdivision are also defined. Let S (c) be a function returning the slope of cell c and H (c) be a function returning the minimal height between the floor cell c and its ceiling. Let up(c) be a function returning the ceiling 3D cell associated to 3D cell c and E(c, s) a function returning the segment of the cell c projecting on the 2D segment s.

The topology of a 3D environment is represented by a graph in which nodes are navigable 3D cells and edges represent the accessibility between cells. Thus, two cells c 1 and c 2 belong to the graph and are connected if and only if:

• Cells c 1 and c 2 are navigable, i.e. ∀c ∈ {c 1 , c 2 },

H (c) ≥ H m ∧ S (c) ≤ S m
• The 2D projections of c 1 and c 2 are two triangles of T 2 sharing a common edge S. This property verifies the 2D accessibility between cells.

• The maximal vertical distance between E(c 1 , S) and E(c 2 , S) is less than the maximum surmountable step height H s m . • The minimal vertical distance between E(c 1 , S)

and E(up(c 2 ), S) and between E(up(c 1 ), S) and E(c 2 , S) is greater than the minimal navigable height. This property ensures that the humanoid can pass under the ceiling located on the frontier of the two cells.

• The vertical zone delimited by the upper segment between E(c 1 , S) and E(c 2 , S) noted V s , and segment V s translated along the Z axis with an offset equivalent to the minimal navigable height, do not contain any vertical obstacle. This property compensates the lack of representation of vertical obstacles in the 3D spatial subdivision by verifying if a vertical polygon of the environment mesh is situated on the common boundary of the two cells.

An edge added in the topological graph is then tagged continuous if the maximal distance between E(c 1 , S) and E(c 2 , S) is lesser than a given threshold or step otherwise. Each connected component of the topological graph defines a surface. Let us consider the environment of Fig. 2 containing several stairs (regular, irregular, spiral), beams and narrow passages. Once the topological graph is computed, zones representing homogeneous groups of 3D cells can be extracted. Those zones are defined as groups of cells linked by a continuous relation, i.e. an edge tagged as continuous. Those zones are then grouped into a set of 2.5D surfaces. A 2.5D surface is defined as the union of interconnected zones that do not overlap, i.e. none of the 3D cells belong to the same prism of the spatial subdivision. In case of 3D environments, a connected component of the topological graph will then be represented as a set of layers defining several 2.5D surfaces. This property reduces problem dimensionality and enables some data structure optimization and constraint extraction that will be presented in the following sections. Fig. 4 presents the different zones corresponding to the navigable surface presented in figure 3. Each zone is colored and dark lines represent zones borders. As shown in this example, extracted zones match the different continuous surfaces and identify each step of a stair, each platform of the block maze and continuous surfaces. Moreover, it appears that 2.5D surface and zone computation is a first step toward a drastically

Topological maps

The aim of topological maps is to provide a compact and accurate representation of a 2.5D surface by precisely characterizing obstacle and step borders while improving the environment representation with the computation of bottlenecks, i.e. the most constrained part of the environment. It is a 2D representation of the environment topology enabling to reduce a large part of 3D problems to simpler 2D problems.

As presented in the previous section, a 2.5D surface is composed of several interconnected zones. The definition of the topological map relies on the spatial subdivision of segments defining the boundaries of zones compounding a given 2.5D surface. Zone boundaries represent either a step border if they correspond to an edge linking two cells in the topological graph or an obstacle border otherwise. Let B s be the 2D segments corresponding to the projection of step borders and B o be the 2D segments corresponding to the projection of obstacle borders. Sets B s and B o are simplified by merging collinear segments sharing a common point. This tends to highly reduce the number of segments and reduce the complexity of the topological map. The topological map is then computed by using a constrained Delaunay triangulation computed on the segments belonging to sets B s and B o . In order to conserve step and obstacle border information, the membership of a segment to set B o or B s is kept during computation. Once the triangulation is computed, the algorithm proposed in [START_REF] Lamarche | Crowd of virtual humans: a new approach for real time navigation in complex and structured environments[END_REF] is used to identify bottlenecks. The resulting 2D triangulation defines the topological map. Triangular cells compounding this map are delimited by three types of segments: obstacle, step and f ree segments. It also accurately identify bottlenecks constraining the Figure 5 shows the topological map computed on our testing environment: black segments are obstacle borders, dashed segments are step borders and green segments represent f ree edges, added by the Delaunay triangulation. Compared to the complexity of the surface presented in Fig. 3 we can rapidly conclude that the topological map is drastically simpler (2406 cells vs 7038 original 3D cells). In zones (1) and ( 2), the projection of ceiling constraints and floor irregularities has been removed. Those results are due to the zone border identification combined with aligned segment simplification. Moreover, in zone (3), bottlenecks have been clearly identified.

Due to the analysis of the environment topology, the topological map abstracts the environment spatial subdivision by removing the projection of ceiling constraints, which results in a simpler representation. Furthermore, this map precisely represents the environment and contains all information needed by path planning and footprint generation processes: it identifies steps, obstacles and bottlenecks.

Roadmap

The aim of the roadmap generation process is to limit the number of waypoints and paths while ensuring a precise coverage of the environment. Classically, this process uses two computational steps: the generation of waypoints on the edges of the topological map and the generation of linear paths connecting them.

In order to generate waypoints, each border and free segment of the topological map is sampled in order to compute a histogram H(S, u), where S is the sampled segment, u is the curvilinear abscissa on segment S and H(S, u) is the distance to the nearest obstacle segment. Once the histogram computed, all values of u such as H(S, u) is a local maximum and H(S, u) is greater than the humanoid radius are extracted. A waypoint is then generated for each extracted value of u. Once all waypoints are generated, a linear path connecting two waypoints (w 1 , w 2 ) is generated if and only if the distance between the segment (w 1 ,w 2 ) and obstacle segments is greater than the humanoid radius and if w 1 and w 2 have been generated on two different segments delimiting the same triangular cell of the topological map. This waypoint generation process tends to generate waypoints maximizing clearance with obstacles. The generated roadmap is thus a coarse approximation of the generalized Voronoï diagram computed on the set of obstacle segments. An example of the roadmap generation is presented in fig. 6. On the spiral staircase (on the bottom left of the figure), this example demonstrates the capacity of our algorithm to find paths within narrow passages.

Virtual human navigation

Built upon the representation described in the previous sections, three animation processes will be described: optimized path generation, footprint generation and ceiling obstacle avoidance. Those processes have been designed to respect behavioral animation requirements: reactivity and performance. Optimized path generation and footprint generation have been designed to be compatible with producer / consumer architecture. This makes them compatible with other reactive processes such as, for instance, reactive navigation. The ceiling avoidance algorithm is described through and reactive process endowed with anticipation capabilities. It acts independently by modifying the posture to match environmental constraints.

Path generation and optimization

Given a topological map, the aim of our path generation process is to generate a pseudo optimal trajectory linking a source and a destination point. The path planning process starts by localizing the source and destination points inside the topological map, i.e. finding the cells containing them. Those points are then connected to the way points generated on the segments delimiting their respective cells. The path is then computed using an A * algorithm [?]. The resulting path is a list of waypoints which is transformed in a parameterized poly-line P(u) with u varying in the interval [0; L]; L being the path length.

Given the position of the virtual human inside the environment, the aim of this algorithm is to find the furthest accessible position belonging to the planned path P(u). Let t be the curvilinear abscissa of the current target on the path (with t = 0 when initializing the algorithm). In order to find the furthest accessible target along the path P(u), we use a dichotomy to maximize the parameter α ∈ [0; 1] such as P(t + α(Lt)) is accessible. Then t is given the value t + α(Lt) and the new target becomes P(t). The notion of accessibility is defined as follow: a target position is accessible from a source position (generally the humanoid position) if the distance between the segment (source, target) and obstacles is greater than the humanoid radius (this property is verified within the topological map). This ensures that the virtual human can move along a straight line toward the target without colliding with obstacles. Given a new position of the humanoid, a new optimization starting with the current value of t can be called in order to generate a new target.

The performance of this algorithm is limited by the cost of the accessibility query. This spatial query is efficiently implemented by locating a point of the segment inside the topological map and by using a flood fill algorithm to search for obstacles. This algorithm starts from the triangle containing the selected position and explores triangles lying in a zone situated at the given distance from the segment.

Footprint generation

Footprint generation aims at correctly handling footprint placement over steps while following the optimized trajectory. It uses the topological map to extract environmental constraints and correct footprint position. This process uses two parameters that can be automatically computed knowing the humanoid morphology and the motion capture in use: the preferred step length S l and the preferred step width S w . During the following explanation, the reader is invited to refer to Fig. 7 which presents the computation of an adapted footprint. The first step of the algorithm is to compute the new target P(t) using the trajectory optimization process, using F p as the humanoid position. Once the target computed, a maximal step length S l is defined such as S l = min(|F p -P(t)|, S l ). Let D be the normalized vector defining the movement direction between F p and P(t). The next potential position P F is then defined as P F = F p + S l D. Within the topological map, all border edges intersecting segment (F p , P F ) are selected. If the number of intersections is greater or equal to 2, there exists a step between F p and P F . In that case, intersection points p 1 and p 2 minimizing the distance to F p are computed and P F (noted P ′ F in Fig. 7) is defined as the middle point of the segment (p 1 , p 2 ). This position is thus located on the step. The final footprint position is then defined as P F ± S * D × R(π/2) where R(π/2) is a rotation matrix and S is the minimum value between the preferred step width S w and the distance to the nearest border edge minus the foot width.

Virtual ceiling

The ceiling avoidance algorithm is based on the definition of a virtual ceiling whose role is to smooth transitions between ceiling obstacles. This smoothing process spatially extends ceiling constraints and thus solves anticipation problems during ceiling collision avoidance.

The height of the virtual ceiling is evaluated by a local function taking into account ceiling obstacles situated within a given volume. Let H h be the humanoid height, P a point of the environment, r a radius and D A an anticipation distance. Let H (c) be a function re-

H(P, r) = min c∈ o max( 2 (P, c) -r, 0) D A * (H h -H (c))+ H (c)
(1) Let consider the example presented in Fig. 8. On the left, an environment composed of a flat floor with a rectangular step surmounted by several ceiling obstacles is presented. The previous equation uses the projection of 3D cells compounding the 2.5D surface and the height between the floor and ceiling. During the computation, the algorithm reduces the problem to a flatten floor with an associated ceiling deformation such as presented on the right of figure 8. Finally, equation 1 creates a virtual ceiling smoothing constraints using a linear height interpolation around constrained zones of the environment. Figure 9 presents the virtual ceiling and its section, computed on the basis of the environment of fig.

8.

Given the position of a body part of a humanoid, the corresponding height of the virtual ceiling can be rapidly computed. By applying constraints on this body part, a motion anticipating and avoiding collision with the ceiling can be generated. Finally, as the height of the virtual ceiling is computed by using the height between floor and ceiling, uneven surfaces surmounted by irregular ceilings are automatically handled and do not need specific computation.

Virtual human animation

To animate our virtual human, we use MKM [START_REF] Kulpa R | Fast inverse kinematics and kinetics solver for human-like figures[END_REF][START_REF] Kulpa R | Morphology-independent representation of motions for interactive human-like animation[END_REF]. This system proposes several functionalities such as motion blending, real time motion retargeting, fast IK solver and ground adaptation. Coupled with MKM, two control processes are used. The first process handles locomotion and footprint generation while the second one handles ceiling avoidance. The structure of the animation pipeline is presented Fig. 10.

Locomotion. When a moving request is received, the global path is computed. Then, the trajectory optimization and the footprint generation processes are started. A cyclic locomotion motion is played and the trajectory optimization and the footprint generation processes are activated when a new footprint is required.

Ceiling collision avoidance. The ceiling collision avoidance process combines two techniques: the control of blending between locomotion and crouching locomotion and a procedural control of the humanoid head position. If the head position resulting from the last blending is under the virtual ceiling, the weight of the crouching locomotion is decreased otherwise the weight of the crouching locomotion is increased. This computation tends to smoothly adapt the humanoid animation to ceiling constraints. As a result, the head can collide the virtual ceiling. In such a case, we generate a new head position in front of the humanoid. Let D H (p) be a function returning the distance between a 3D point p and its projection on the floor. Let P H be the head position and r H be the radius of a sphere approximating the head shape. The distance between the top of the head and the virtual ceiling is given by the following equation:

∆ H (P H , r H ) = |H(P H , r H ) -D H (P H ) -r H | (2)
Let δ = ∆ H (P H , r H ) be the distance after blending between the head and the virtual ceiling. Let f be the normalized front vector of the humanoid and Z be the normalized Z-up vector. The head position is computed as follow:

P ′ H = P H + δ f -∆ H (P H + 1 2 δ f , 1 2 δ + r H )Z (3)
In this equation, two virtual ceiling height queries are used. The first one δ = ∆ H (P H , r H ) select minimal ceiling height over the head of the humanoid. The second one ∆ H (P H + 1 2 δ f , 1 2 δ + r H ) uses a selection over a cylinder centered on the middle of the original head position and the translated head position with a radius covering all the zone possibly occupied by the head between those two positions. This ensures that the head cannot collide the ceiling. An IK on spine and head is then used to modify the posture of the virtual humanoid.

The Fig. 11 presents some results of motion adaptation to floor and ceilings constraints. One important characteristic of the presented motion control techniques is that they automatically adapt to new motions and character morphologies. This enables to use the same algorithm on a wide variety of humanoids and motions without any pre-computation. The other important characteristic is their reactivity. Computation is achieved online and do not require long term anticipation nor planning. Footprint generation only requires a target which can be computed by the proposed trajectory optimization process but also by an external reactive navigation model for example. Ceiling adaptation does not use randomized search nor motion bounding boxes and do not need a fully planned path to adapt postures. It uses a mix between motion blending and procedural animation which accelerates computation and increase model reactivity.

Results and performance analysis

We tested our algorithm on two environments. The first environment is the platform presented Fig. 2. It is compounded of 7952 triangles and contains several test cases: a regular staircase, an irregular staircase (with varying step length), a spiral staircase, a block maze, several beams and a tunnel with a curved floor surmounted by a curved ceiling. The second environment is a house with two floors and a tunnel, several staircases and several rooms with furniture (Cf. right images of Fig. 11). The geometry is compounded of 120160 triangles. Tables 1 and2 respectively present the size of the data structures generated during environment analysis and the time taken to generate each representation (prismatic spatial subdivision, topology, topological maps and roadmaps). Computation time as well as representation complexity increase with the size of the input mesh and the number of floors. In the worst case, the number of generated prisms is a polynomial function of the number of overlapping triangles (two overlapping triangles can generate up to height prisms). This is a drawback of our approach. However, our preprocessing phase tends to reduce the complexity of the input geometry, and in most cases, complex geometries which do not influence navigation can be removed or simplified before environment processing. Figure 11 presents some result concerning motion adaptation: climbing a slope while avoiding beams, walking on an curved floor under an curved ceiling, avoiding beams along a curved trajectory and climbing several types of staircases. Our reactive avoidance process, due to the use of the virtual ceiling, is endowed with anticipation capabilities. Humanoids can anticipate collision on uneven floor surmounted by an irregular ceiling without any specific computation such as presented fig. 11. Moreover, the footprint generation process is able to generate climbing motions even in very constrained stairs such as in the narrow spiral staircase for example. This demonstrates the generic aspect of our approach. In terms of performance, the average path planning time using an A * algorithm is about 1.2 ms. Our animation control processes are coupled with the approach proposed in [KM05,KMA05] to compute the virtual human animation. The humanoid animation only takes about 0.5 ms per time step with the following distribution:

• Motion blending: 0.041 ms per time step.

• Path optimization: 0.21 ms per footprint.

• Footprint correction: 0.05 ms per footprint.

• Floor height evaluation and ground adaptation (inverse kinematics on legs, root position correction): 0.012 ms per time step.

• Virtual ceiling computation and head position computation 0.236 ms per time step.

• IK on spine and head: 0.217 ms per time step.

Those results are compatible with the real time animation of several dozens of characters adapting their motion to ceiling constraints.

Discussion

We have presented TopoPlan, our topological planner. The proposed approach uses the 3D environment description to automatically generate an accurate spatial representation. It makes no assumption on the input geometry and proposes an exact 3D spatial subdivision (the prismatic subdivision) from which environment topology is extracted. Free space and navigable zones are thus exactly identified. The 2D representation provided by the topological map is compact and contains all required topological information such as obstacles, steps but also bottlenecks. It provides a suitable structure enabling to reduce some 3D problems to 2D problems and improves performance. Finally, the generated roadmap automatically captures the environment connectivity even in very constrained zones and is described by a small number of waypoints and paths.

Based upon this representation, two motion adaptation algorithms have been proposed: a footprint generation process and posture adaptation to floor and ceiling constraints. Footprints are generated on demand by using a process compatible with reactive navigation algorithms. Posture adaptation is handled by a separate and independent process and can be used in several contexts and not only navigation. Those algorithms rapidly adapt to different humanoid morphologies by using high level parameters and do not require any complex collision checking. Finally, those algorithms have been designed to respect behavioral animation requirements: reactivity and performance. Future works will focus on several aspects. Firstly, we will use TopoPlan properties to provide a new reactive navigation process taking into account constraints imposed by the environment. Secondly, we will focus on the generalization of our approach on posture adaptation within dynamic environments. Finally, we will explore the link between environment information and topology determination in order to feed high level decision processes with abstract topological information automatically extracted from an informed environment geometry.

Figure 1 :

 1 Figure 1: Different steps of the 3D subdivision process.

Figure 2 :

 2 Figure 2: Views of our testing environment.

Figure 3 :

 3 Figure 3: Projection of the 3D cells compounding the 2.5D surface extracted from the environment of fig. 2 along with two sample prisms of the prismatic subdivision.

Figure 4 :

 4 Figure 4: Example of zones computed on the navigable part of our testing environment.

Figure 5 :

 5 Figure 5: Computed topological map. navigation on even or uneven floors.Figure5shows the topological map computed on our testing environment: black segments are obstacle borders, dashed segments are step borders and green segments represent f ree edges, added by the Delaunay triangulation. Compared to the complexity of the surface presented in Fig.3we can rapidly conclude that the topological map is drastically simpler (2406 cells vs 7038 original 3D cells). In zones (1) and (2), the projection of ceiling constraints and floor irregularities has been removed. Those results are due to the zone border identification combined with aligned segment simplification. Moreover, in zone (3), bottlenecks have been clearly identified.Due to the analysis of the environment topology, the topological map abstracts the environment spatial subdivision by removing the projection of ceiling constraints, which results in a simpler representation. Furthermore, this map precisely represents the environment and contains all information needed by path planning and footprint generation processes: it identifies steps, obstacles and bottlenecks.

Figure 6 :

 6 Figure 6: Topological map with associated roadmap.

Figure 7 :

 7 Figure 7: Footprint computation on a regular stair.

Figure 8 :

 8 Figure 8: 3D view of the environment (left). Flatten floor and morphed ceiling (right).

Figure 9 :

 9 Figure 9: Computed virtual ceiling from morphed environment of fig. 8(b) and associated section.

Figure 10 :

 10 Figure 10: MKM (blue) and TopoPlan (yellow) processes in animation pipeline. Red arrows correspond to posture communication between processes.

http://www.cgal.org