The medial axis transform (or MAT) is a representation of an object as an i
nfinite union of balls. We consider approximating the MAT of a three-dimens
ional object, and its complement, with a finite union of balls. Using this
approximate MAT we define a new piecewise-linear approximation to the objec
t surface, which we call the power crust.
We assume that we are given as input a sufficiently dense sample of points
from the object surface. We select a subset of the Voronoi balls of the sam
ple, the polar balls, as the union of balls representation. We bound the ge
ometric error of the union, and of the corresponding power crust, and show
that both representations are topologically correct as well. Thus, our resu
lts provide a new algorithm for surface reconstruction from sample points.
By construction, the power crust is always the boundary of a polyhedral sol
id, so we avoid the polygonization, hole-filling or manifold extraction ste
ps used in previous algorithms.
The union of balls representation and the power crust have corresponding pi
ecewise-linear dual representations, which in some sense approximate the me
dial axis. We show a geometric relationship between these duals and the med
ial axis by proving that, as the sampling density goes to infinity, the set
of poles, the centers of the polar balls, converges to the medial axis. (C
) 2001 Elsevier Science B.V All rights reserved.