Space discretization for efficient human navigation

There is a large body of research on motion control of legs in human models. However, they require specification of global paths in which to move. A method for automatically computing a global motion path for a human in a 3D environment of obstacles is presented. Object space is discretized into a 3D grid of uniform cells and an optimal path is generated between two points as a discrete cell path. The grid is treated as graph with orthogonal links of uniform cost. The A* search method is applied for path finding. By considering only the cells on the upper surface of objects on which a human walks, a large portion of the grid is discarded from the search space, thus boosting efficiency. This is expected to be a higher level mechanism for various local foot placement methods in human animation