Curve and surface smoothing without shrinkage

TitleCurve and surface smoothing without shrinkage
Publication TypeConference Paper
Year of Publication1995
AuthorsTaubin, G.
PublisherIEEE Computer Society
Keywordsapproximation algorithms boundary-following algorithms computational complexity computational geometry computer vision curve fitting curve smoothing data visualisation edges faces faceting high curvature variations image registration iso-surface construct
Abstract

For a number of computational purposes, including visualization of scientific data and registration of multimodal medical data, smooth curves must be approximated by polygonal curves, and surfaces by polyhedral surfaces. An inherent problem of these approximation algorithms is that the resulting curves and surfaces appear faceted. Boundary-following and iso-surface construction algorithms are typical examples. To reduce the apparent faceting, smoothing methods are used. In this paper, we introduce a new method for smoothing piecewise linear shapes of arbitrary dimension and topology. This new method is in fact a linear low-pass filter that removes high-curvature variations, and does not produce shrinkage. Its computational complexity is linear in the number of edges or faces of the shape, and the required storage is linear in the number of vertices.