Curve and Surface Smoothing without Shrinkage

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. Current smoothing methods have one or more of the following problems: They do not apply to general polygonal curves and polyhedral surfaces, are computationally expensive, require large amounts of storage, or produce shrinkage. In this paper we introduce a new method for smoothing piece-wise 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.