Calculating the medial axis of a CAD model by multi-CPU based parallel computation

Computational efficiency is still a great challenge for the generation of the Medial Axis (MA) for complicated CAD models. Current research mainly focuses on CPU-based MA generation methods. However, most of the methods emphasize using a single CPU. The highly-efficient methods based on parallel computing are still missing. In this study, a parallel method based on multi-CPU is proposed for the efficient MA generation of CAD models using distance dilation. By dividing the whole model into several parts for which MAs are calculated in parallel and then combined, computational efficiency can be greatly improved in theory and the computation time can be reduced nearly K times if K CPUs are used. Firstly, an adaptive division method is proposed to divide the voxelized model into blocks which have nearly the same number of voxels to balance the computational burden. Secondly, the local Euclidean Distance Transform (EDT) is calculated for each block based on the existing distance dilation method. Thirdly, the complete inter-dilation method is proposed to compute the influence between different blocks to get a global EDT for each block. Finally, each block generates a sub-MA separately and then all the generated MAs are combined to obtain the final MA. The last three processes can be efficiently conducted in parallel by using multiple CPUs. Several groups of experiments are conducted which demonstrate the good performance of the proposed methods in terms of efficiency.