We present a novel approach to compute a collision-free path for part disassembly simulation and virtual prototyping of part removal. Our algorithm is based on sample-based motion planning that connects collision-free samples in the configuration space using local planning. In order to effectively handle the tight-fitting scenarios, we describe techniques to generate samples in narrow passages and efficient local planning algorithms to connect them with collision-free paths. Our approach is general and makes no assumption about model connectivity or object topology, and can handle polygon soup models that frequently arise in CAD applications. We highlight the performance on many challenging benchmarks including the Alpha puzzle, maintainability of the windscreen wiper motion, and disassembly of a seat from the interior of a car body.
Bibliographical noteFunding Information:
This research was supported in part by ARO Contracts DAAD19-02-1-0390 and W911NF-04-1-0088, NSF awards 0400134, 0429583 and 0404088, DARPA/RDECOM Contract N61339-04-C-0043 and Intel. Young J. Kim was supported in part by the Korea Research Foundation Grant funded by the Korean Government (KRF-2007-331-D00400) and the IT R&D program of MKE/IITA (2008-F-033-01, Development of Real-time Physics Simulation Engine for e-Entertainment). We thank E. Ferre from Kineo CAM and J.P. Laumond from LAAS-CNRS for providing benchmarks in Figs. 11 and 12.
- Motion planning
- Part disassembly planning
- Virtual prototyping