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. We also suggest an algorithm to extract kinematic skeletons for articulated models as an application of our medial axis points.
본 논문에서는 주어진 3차원 물체의 표면을 샘플링한 점집합과 법선장을 이용하여 중심축 상의 점을 근사하는 새로운 방법을 제시하였다. 이는 최근린 검색을 이용하여 중심축점에 대응되는 중심구의 크기를 반복적으로 줄여가는 방식을 바탕으로 한다. 본 논문은 주어진 점집합의 밀도가 무한대로 접근할 때 그에 대응되는 근사 중심축점 역시 실제 중심축으로 수렴함을 증명하였으며, 이 결과는 중심축 단순화, 국지적 크기 추정, 점집합 단순화 등의 문제에 응용될 수 있다. 본 논문이 제시하는 알고리즘은 간단하고 효율적일 뿐만 아니라 병렬화하기에 용이하다는 강점을 가지고 있으며, 실험을 통해 그 효율성을 입증하였다. 마지막으로, 이렇게 얻은 중심축점을 이용하여, 본 논문에서는 주어진 관절체 모델의 운동학적 골격을 추출하는 직관적이며 효율적인 방법을 제안하였다.
