The 3D marching lines algorithm

This paper presents a general purpose tool designed to extract characteristic curves from 3D images. Our algorithm, called the Marching Lines, is inspired by isointensity techniques, such as the Marching Cubes. Marching Lines extracts, with subpixel accuracy, the 3D lines corresponding to the intersection of two isosurfaces in a 3D grid. The algorithm ensures that each reconstructed curve is formed of a connected set of segments, is closed if the curve is entirely contained in the grid, does not intersect itself, and is oriented. The main idea is to define isosurfaces as interfaces (f greater than or equal to 0, f < 0) instead of implicit equation solutions (f = 0). The singularities are solved with an offset technique. Results are presented for synthetic data and for 3D medical image applications. (C) 1996 Academic Press, Inc.