An Algorithm for Computing the Exact Configuration Space of a Rotating Object in 3-space


In this paper we present and test an algorithm for constructing SO(3) configuration spaces. It is capable of handling polyhedral scenes (triangulated) as well as ball-only scenes (sphere-trees). Without loss of generality we consider objects rotating around the zero point. In a scene, consisting of $n$ triangular faces (or balls) of obstacles and $m$ triangular faces (or balls) of a rotating object, the complexity of the presented algorithm is $O(n^3m^3log(nm))$. The algorithm is output-sensitive, which means that it discards all unnecessary geometry and takes only a minimum number of geometry needed to obtain a correct final configuration space. Configuration spaces are represented as graphs of intersections on the border of free configuration space. This algorithm is a generalization of a few previous related works: the case of a rotating and translating polygon on a plane and the case of a rotating and translating segment (or a cigar-like object) in 3-space.

In IAENG International Journal of Computer Science