Shrinking sphere: A parallel algorithm for computing the thickness of 3D objects. Issue 2 (3rd March 2016) - Inui, Masatomo
Abstract: An interactive system is required to enable machine designers to precisely visualize the thickness of a machine part. The thickness of a 3D object at a surface point is given by the diameter of the maximum inscribed sphere (MIS) touching that point. In this paper, we propose a novel iterative algorithm, namely, the shrinking sphere algorithm, for computing the MIS at a specific surface point. The convergence speed of the proposed algorithm is very high, and several iterations are usually sufficient for obtaining the MIS. The parallel execution of the algorithm with a graphics processing unit (GPU) is presented for further improving the computation speed. On the basis of the proposed algorithm, an experimental thickness visualization system is implemented using Compute Unified Device Architecture (CUDA). This system can visualize the thickness of a complex object with nearly two million polygons in several minutes using a PC (Core i7 CPU, 32GB memory and GTX-980 GPU), which is sufficiently fast for practical purposes. GRAPHICAL ABSTRACT: