Parallelization of skeleton extraction from 3D models and point clouds

Nikolas Hamran

Supervisor(s): Martin Madaras

Slovak Technical University

Abstract: We present a GPU accelerated algorithm for skeleton extraction from 3D meshes and point clouds. Our method performs skeletonization in a pipeline, where each stage ensures an optimal transformation of the input data to achieve a satisfactory result. The input vertices are converted to the medial surface of the mesh with the shrinking spheres method for improved accuracy of the final skeleton. Vertices are then sampled from the medial surface and contracted to a thin shape with the L1 method. These steps are done in parallel. The final stages include skeleton reconstruction and post processing on the CPU. We introduced modifications to the original CPU based algorithms for them to be suitable for parallel execution. These modifications include speedups for algorithm convergence and data dependency removal during computation. An advantage of our method is that it does not require connectivity information between vertices, as opposed to Laplacian based mesh contraction methods. Experimental results show near real time performance of our algorithm. The implementation uses the CUDA API for efficient utilization of the GPU resources.
Keywords: Computational Geometry, Geometry Processing, Point-based Graphics
Full text:
Year: 2020