PIECEWISE-LINEAR INTERPOLATION BETWEEN POLYGONAL SLICES

In this paper we present a new technique for piecewise-linear surface reconstruction from a series of parallel polygonal cross sections, Thi s is an important problem in medical imaging, surface reconstruction f rom topographic data, and other applications. We reduce the problem, a s in most previous works, to a series of problems of piecewise-linear interpolation between each pair of successive slices. Our algorithm us es a partial curve matching technique for matching parts of the contou rs, an optimal triangulation of 3-D polygons for resolving the unmatch ed parts, and a minimum spanning tree heuristic for interpolating betw een nonsimply connected regions. Unlike previous attempts at solving t his problem, our algorithm seems to handle successfully in practice an y kind of data, It allows multiple contours in each slice, with any hi erarchy of contour nesting, and avoids the introduction of counterintu itive bridges between contours, proposed in some earlier papers to han dle interpolation between multiply connected regions, Experimental res ults on various complex examples, involving actual medical imaging dat a, are presented and show the good and robust performance of our algor ithm. (C) 1996 Academic Press, Inc.