Compact representation of medial axis transform

Abstract

Shape representation is a fundamental topic in geometric modeling, which is ubiquitous in computer graphics. Compared with the explicit and implicit shape representations, the medial representation possesses many advantages. It provides a comprehensive understanding of the shapes, since it gives direct access to both the boundaries and the interiors of the shapes. Although there are many medial axis computation algorithms which are able to filter noises in the medial axis, introduced by the perturbations on the boundary, and generate stable medial axis transforms of the input shapes, the medial axis transforms are usually represented in a redundant way with numerous primitives, which brings down the flexibility of the medial axis transform and hinders the popularity of the medial axis transform in geometric applications. In this thesis, we propose compact representations of the medial axis transforms for 2D and 3D shapes.

The first part of this thesis proposes a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in the 3D space to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform.

The second part of this thesis discusses improvements on the existing medial axis computation algorithms, and represent the medial axis transform of a 3D shape in a compact way. The CVT remeshing framework is applied on an initial medial axis transform to promote the mesh quality of the medial axis. The simplified medial axis transform is then optimized by minimizing the approximation error of the shape reconstructed from the medial axis transform to the original 3D shape.

Our results on various 2D and 3D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D and 3D shapes.