Mapping the configuration space of polygons using reduced convolution

Configuration space (C-space) plays an important role not only in motion planning but also in geometric modeling, shape and kinematic reasoning, and is fundamental to several basic geometric operations, such as continuous collision detection and generalized penetration depth estimation, that also find their applications in motion planning, animation and simulation. In this paper, we developed a new method for constructing the boundary of the C-space obstacles (C-obst) of polygons. This method is simpler to implement and is theoretically more efficient than the existing techniques. Our main idea is to devote the computation on the discontinuity in temporal and spatial coherence where the structure of the C-obst changes. We also developed a method for estimating the generalized penetration depth by computing the distance between the query point and the C-obst surface.