Voxel-Based General Voronoi Diagram for Complex Data with Application on Motion Planning

Abstract

One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find appropriate disassembly paths for all assembled parts. Such a path places demands on its length and clearance. In the past, it became apparent that planning the disassembly path based on the (approximate) General Voronoi Diagram (GVD) is a good approach to achieve these requirements. But for complex real-world data, every known solution for computing the GVD is either too slow or very memory consuming, even if only approximating the GVD. We present a new approach for computing the approximate GVD and demonstrate its practicability using a representative vehicle data set. We can calculate an approximation of the GVD within minutes and meet the accuracy requirement of some few millimeters for the subsequent path planning. This is achieved by voxelizing the surface with a common errorbounded GPU render approach. We then use an error-bounded wavefront propagation technique and combine it with a novel hash table-based data structure, the so-called Voronoi Voxel History (VVH). On top of the GVD, we present a novel approach for the creation of a General Voronoi Diagram Graph (GVDG) that leads to an extensive roadmap. This roadmap can be used to suggest appropriate disassembly paths for the later task of motion planning.