Solving inverse configuration space problems by adaptive sampling


Event Symposium on Solid and Physical Modeling (SPM 2012)


Saigopal Nelaturi
Technical Publications
October 29th 2012
Given two shapes in relative motion, an important class of inverse configuration problems is solved by determining relative configurations that maintain set-inclusion relationships (non-interference, containment, or contact) between the shapes. This class of inverse problems includes the well-known problem of constructing a configuration space obstacle, as well as many other problems in computational design such as sweep decomposition, accessibility analysis, and dynamic packaging. We show that solutions to such problems may be efficiently approximated directly in the 6D configuration space SE(3) of relative motions by adaptive sampling. The proposed method relies on a well-known fact that the manifold of the group SE(3) is a Cartesian product of two manifold subgroups: the group of rotations SO(3) and the group of translations R3. This property allows generating desired configurations by combining samples that are generated in these subgroups independently and adaptively. We demonstrate the effectiveness of the proposed approach on several inverse problems including the problem of sweep decomposition that arises in reverse engineering applications.


Nelaturi, S.; Shapiro, V. Solving inverse configuration space problems by adaptive sampling. Symposium on Solid and Physical Modeling; 2012 October 29-31; Dijon, France. In Computer-Aided Design; 2013 February; 45 (2): 373-382.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for¬†Commercialization.


Our scientists and staffers are active members and contributors to the science and technology communities.