3D medial axis point approximation using nearest neighbors and the normal field

Abstract

We present a novel method to approximate medial axis points given a set of points sampled from a surface and the normal vectors to the surface at those points. For each sample point, we find its maximal tangent ball containing no other sample points, by iteratively reducing its radius using nearest neighbor queries. We prove that the center of the ball constructed by our algorithm converges to a true medial axis point as the sampling density increases to infinity. We also propose a simple heuristic to handle noisy samples. By simple extensions, our method is applied to medial axis point simplification, local feature size estimation and feature-sensitive point decimation. Our algorithm is simple, easy to implement, and suitable for parallel computation using GPU because the iteration process for each sample point runs independently. Experimental results show that our method is efficient both in time and in space.