D-Plan: Efficient Collision-Free Path Computation For Part Removal and Disassembly


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

University of  North Carolina at Chapel Hill


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, 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.

International CAD Conference (CAD'08), 2008;
Best Paper Award
Journal of Computer-Aided Design and Applications;
Paper: PDF , BIB


Alpha Puzzle Benchmark: the goal is to separate the two intertwined models. This is a very difficult benchmark for motion planning due to the underlying "narrow passage". Our planner can efficiently solve this benchmark (less than 20 minutes).


Interestingly, our planner finds two different solutions. This matches the underlying symmetry in the models and the benchmark.

Video for solution 1

Video for solution 2




Pipe (Video)


Wiper (Video)


Car seat benchmark: The problem is to remove a seat outside of a car body. It is a difficult benchmark for motion planning approaches due to the cluttered environment and complex geometric representation of the models.

Car Seat (Video)

Related Links

Retraction-based Motion Planning

Generalized Penetration Depth Computation

Complete Motion Planning