F. Lamarche (2009). TopoPlan: a topological path planner for real time human navigation under floor and ceiling constraints . Computer Graphics Forum (Proc of Eurographics 2009) 2(28).

Abstract: In this article we present TopoPlan, a topological planner dedicated to real-time humanoid path-planning and motion adaptation to ?oor and ceiling constraints inside complex static environments. This planner analyzes unstructured 3D triangular meshes in order to automatically determine their topology. The analysis is based on a prismatic spatial subdivision which is analyzed, taking into account humanoid characteristics, in order to extract navigable surfaces and precisely identify environmental constraints such as ?oors, ceilings, walls, steps and bottlenecks. The technique also provides a lightweight roadmap computation covering all accessible free space. We demonstrate the properties of our topological planner within the context of two reactive motion control processes: an on-the-?y trajectory optimization and footprint generation process that correctly handles climbing of complex staircases, and a reactive ceiling adaptation process that handles beam avoidance and motion adaptation to irregular ?oors and ceilings. We further show that the computation cost of these processes is compatible with the real time animation of several dozens of virtual humans.

Download article.