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

摘要

We present a novel method to approximate me dial axis points given a set of points sampled from a surfac and the normal vectors to the surface at those points. Fo each sample point, we find its maximal tangent ball contain ing no other sample points, by iteratively reducing its radiu using nearest neighbor queries. We prove that the center o the ball constructed by our algorithm converges to a tru medial axis point as the sampling density increases to in finity. We also propose a simple heuristic to handle nois; samples. By simple extensions, our method is applied t medial axis point simplification, local feature size estima tion and feature-sensitive point decimation. Our algorithn is simple, easy to implement, and suitable for parallel com putation using GPU because the iteration process for eacl sample point runs independently. Experimental results sho that our method is efficient both in time and in space.