For a virtual human, it is one of the most fundamental activities to walk from one location to another while avoiding collision with obstacles. The walking trajectory planning, that is composed of the path planning in 2D and the footprint generation, is very important in providing a virtual human with such an activity. Beside the collision avoidance, the characteristics of the human behavior should be reflected to give realistic movements in the path planning. In the footprint generation, a sequence of footprints, from which a realistic walking motion can be readily obtained, should be sought.
In this thesis, we present an efficient walking trajectory planning algorithm for virtual humans. We first decompose the workspace into sparse and dense regions, and introduce the hybrid roadmap that combines the tangent visibility graph of sparse regions and the Voronoi skeleton of dense regions to reflect the responsive behavior of an actual human. The roadmap is used to efficiently obtain a center-site path of the polygonal mover that is the projection of the articulated human figure. In order to generate a sequence of footprints following the obtained path, we introduce a characteristic volume that stores the model-dependent relation between two legs and determines omni-directional step positions efficiently. Using a characteristic volume and the bisection technique, we keep the stance foot from blocking the swing foot, the swing foot from colliding with obstacles, and two feet from intersecting each other to obtain footprints from which a walking motion can be readily generated.