HOW ARE BSP TREES USEFUL FOR ROBOT MOTION PLANNING?
Overview BSP trees are useful for building an “exact cell decomposition”. A cell is any region which is used as a node in a planning graph. An exact cell decomposition is one in which every cell is entirely occupied, or entirely empty. The alternative is an “approximate cell decomposition”, in which cells may also be partially occupied. A regular grid on a complex scene is an example of an “approximate cell decomposition”. Example Consider a game which uses randomly oriented blocks for obstacles in an enclosed arena. For purposes of path planning, we are interested in the decomposition of the ground plane. We can get this by building a BSP tree containing all of the blocks, and pass a polygon which represents the ground into the tree. The splitting routine should be modified to maintain connectivity information when splitting polygons. Using a technique similar to boolean modelling, we can reduce the tree to contain only those polygons which are the regions of the ground plane not cont
