D-plan: Efficient collision-free path computation for part removal and disassembly

Liangjun Zhang, Xin Huang, Young J. Kim, Dinesh Manocha

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


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.

Original languageEnglish
Pages (from-to)774-786
Number of pages13
JournalComputer-Aided Design and Applications
Issue number6
StatePublished - 2008

Bibliographical note

Funding 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


Dive into the research topics of 'D-plan: Efficient collision-free path computation for part removal and disassembly'. Together they form a unique fingerprint.

Cite this