We have developed a new method for the recovery of an explicit representation of a surface from an implicit surface definition. Specifically, we construct a polygonal mesh from a 3D Euclidean distance transform, which specifies the signed distance (negative inside) to the nearest surface from every point on a 3D grid.

In the first step, we use ENO interpolation to determine where the surface intersects the lines of the 3D grid. This allows us to find multiple intersection points below the level of resolution; these cannot be generated by traditional interpolation techniques. Second, we connect the ENO anchor points into a polygonal mesh using a wave propagation scheme. The advantage of this method over current approaches like marching cubes is that when two distinct surfaces exist between two sample points, each surface can be recovered accurately.

Simple examples where our algorithm has obvious success over marching cubes can be generated synthetically, like this pair of spheres. The result of marching cubes is on the top, and our result is on the bottom. To see an animation of ouralgorithm acting on this data set, click here.

Another good synthetic example is this pair of tori. To see an animation of our algorithm acting on this data set, click here.

This algorithm is also useful for the visualization and accurate measurement of surfaces which arise in medical imaging where surfaces are closer to each other than the image resolution, such as branching or curving structures like the bronchial airway and carotid arteries, and folding structures like the gyri and sulci of the brain. The results on a carotid arteries data set are below.

The two are nearly indistinguishable when viewed at this resolution, especially if they are rendered with smooth Gourand shading. However, when viewed up close, you can see a significant difference in the way polygons were formed. Our alrogithm appears to generate a more rounded surface and also eliminates some topological artifacts which marching cubes introduces, such as the bridge on the left-hand side of the images below (marching cubes is left, ours is right).

** UPDATE: 8/15/01 2:45pm **

We have now obtained results on data set for the left hemisphere of the brain, shown below. This distance transform was produced from a polygonal mesh by Frederic F. Leymarie's 3D-CADT algorithm. The polygonal mesh was provided by Dr. Jean-Francois Mangin at the Service Hospitalier Frederic Joliot of the Commissariat `a l'Energie Atomique in Orsay, France.

Again, the marching cubes result is on top and our result is on the bottom for each pair of images. To see an animation of our algorithm acting on this data set click here.

In this data set, our algorithm has a clear advantage over marching cubes, correctly resolving most (but not all) of the artifacts which are generated when two surfaces get close together.

Go Back to Mike Rodehorst's Web Page at LEMS

Go Back to Topics in Vision Research at Brown