“Marching cubes: A high resolution 3D surface construction algorithm” by Lorensen and Cline

We present a new algorithm, called marching cubes, that creates triangle models of constant density surfaces from 3D medical data. Using a divide-and-conquer approach to generate inter-slice connectivity, we create a case table that defines triangle topology. The algorithm processes the 3D medical data in scan-line order and calculates triangle vertices using linear interpolation. We find the gradient of the original data, normalize it, and use it as a basis for shading the models. The detail in images produced from the generated surface models is the result of maintaining the inter-slice connectivity, surface data, and gradient information present in the original 3D data. Results from computed tomography (CT), magnetic resonance (MR), and single-photon emission computed tomography (SPECT) illustrate the quality and functionality of marching cubes. We also discuss improvements that decrease processing time and add solid modeling capabilities.

1. Artzy, E., Frieder, G., and Herman, G.T. The Theory, Design, Implementation and Evaluation of a Three-Dimensional Surface Detection Algorithm. Comptlter Graphics and Ima~,,e Processinj,, 15, 1 (January 1981), 1-24.
2. Barillot, C., Gibaud, B., Scarabin, J., and Coatrieux, J. 3D Reconstruction of Cerebral Blood Vessels. IEEE Comlmwr Graphk’s attd Applk’ations 5, 12 (December 1985), 13-19.
3. Bates, R. H., Garden, K. L., and Peters, T. M. Overview of Computerized Tomography with Emphasis on Future Developments. Proc. of the IEEE 71, 3 (March 1983), 356-372.
4. Bloch, P. and Udupa, J. K. Application of Computerized Tomography to Radiation Therapy and Surgical Planning. Proc. oi’ the IEEE 71, 3 (March 1983), 351-355.
5. Brewster, L. J., Trivedi, S. S., Tut, H. K., and Udupa, J. K. Interactive Surgical Planning. IEEE Computer Graphics and Applications 4, 3 (March 1984), 31-40.
6. Burk, D. L., Mears, D. C., Kennedy, W. H., Cooperstein, L. A., and Herbert, D. L. Three-Dimensional Computed Tomography of Acetabula Fractures. Radiology 155, 1 (1985), 183-186.
7. Chen, L., Herman, G. T., Reynolds, R. A., and Udupa, J. K. Surface Shading in the Cuberille Environment. IEEE Computer Graphics and Applications 5, 12 (December 1985), 33-43.
8. Christiansen, H. N. and Sederberg, T. W. Conversion of Complex Contour Line Definitions into Polygonal Element Meshes. Computer Graphics 12, 3 (August 1978), 187-192.
9. Cline, H. E., Dumoulin, C. L., Lorensen, W. E., Hart, H. R., and Ludke, S. 3D Reconstruction of the Brain from Magnetic Resonance Images. Magnetic Resonance Imaging (1987, to appear).
10. Cline, H. E., Lorensen, W. E., Ludke, S,, Crawford, C. R., and Teeter, B. C. High-Resolution Three- Dimensional Reconstruction of Tomograms. Medical Physics (1987, to appear).
11. Cook, L. T., Dwyer, S. J., Batnitzky, S., and Lee, K. R. A Three-Dimensional Display System for Diagnostic Imaging Applications. IEEE Computer Graphics and Applications 3, 5 (August 1983), 13-19.
12. Farrell, E. J. Color Display and Interactive Interpretation of Three-Dimensional Data. IBM J. Res. Develop 27, 4 (July 1983), 356-366.
13. Farrell, E. J., Zappulla, R., and Yang, W. C. Color 3D Imaging of Normal and Pathologic Intracranial Structures. IEEE Computer Graphics and Applications 4, 9 (September 1984), 5-17.
14. Fuchs, H., Kedem, Z. M., and Uselton, S. P. Optimal Surface Reconstruction from Planar Contours. Comm. o{‘the ACM 20, 10 (October 1977), 693-702.
15. Gordon, D. and Reynolds, R. A. Image Space Shading of 3-Dimensional Objects. Computer Graphics and Image Processing 29, 3 (March 1985), 361-376.
16. Hale, J. D., Valk, P. E., and Watts, J. C. MR Imaging of Blood Vessels Using Three-Dimensional Reconstruction: Methodology. Radiolo,xv 157, 3 (December 1985), 727-733.
17. Hemmy, D. C., David, D. J., and Herman, G. T. Three-Dimensional Reconstruction of Craniofacial Deformity Using Computed Tomography. Neurosurgery 13, 5 (November 1983), 534-541.
18. Hemmy, D. C. and Tessier, P. L. CT of Dry Skulls with Craniofacial Deformities: Accuracy of Three- Dimensional Reconstruction. Radiology 157, 1 (October 1985), 113-116.
19. Herman, G. T. and Udupa, J. K. Display of 3D Digital Images: Computational Foundations and Medical Applications. IEEE Computer Graphics and Applications 3, 5 (August 1983), 39-46.
20. Hinshaw, W. S. and Lent, A. H. An Introduction to NMR Imaging: From the Bloch Equation to the Imaging Equation. Proc. of the IEEE 71, 3 (March 1983), 338-350.
21. Hoffman, E. A. and Ritman, E. L. Shape and Dimensions of Cardiac Chambers: Importance of CT Section Thickness and Orientation. Radiology 155, 3 (June 1985), 73%744.
22. Hohne, K. H. and Bernstein, R. Shading 3D-Images from CT Using Gray-Level Gradients. IEEE Trans. on Medical Imaging MI-5, 1 (March 1986), 45-47.
23. Keppel, E. Approximating Complex Surfaces by Triangulation of Contour Lines. IBM J. Res. Develop 19, 1 (January 1975), 2-11.
24. Knoll, G. F. Single-Photon Emission Computed Tomography. Proc. of the IEEE 71, 3 (March 1983), 320-329.
25. Meagher, D. J. Geometric Modeling Using Octree Encoding. Computer Graphics and Image Processing 19, 2 (June 1982), 129-147.
26. Robb, R. A., Hoffman, E. A., Sinak, L. J., Harris, L. D., and Ritman, E. L. High-Speed Three-Dimensional X-Ray Computed Tomography: The Dynamic Spatial Reconstructor. Proc. of the IEEE 71, 3 (March 1983), 308-319.
27. Sunguroff, A. and Greenberg, D. Computer Generated Images for Medical Application. Computer Graphics 12, 3 (August 1978), 196-202.
28. Sutherland, I. E. and Hodgman, G. W. Reentrant Polygon Clipping. Comm. of the ACM 17, 1 (January 1974), 32-42.
29. Trivedi, S, S., Herman, G. T., and Udupa, J. K. Segmentation Into Three Classes Using Gradients. 1EEE Trans. on Medical Imaging MI-5, 2 (June 1986), 116-119.
30. Udupa, J. K. Interactive Segmentation and Boundary Surface Formation for 3-D Digital Images. Computer Graphics and Image Processing 18, 3 (March 1982), 213-235.
31. Vannier, M. W., Marsh, J. L., and Warren, J. O. Three Dimensional CT Reconstruction Images for Craniofacial Surgical Planning and Evaluation. Radiology 150, 1 (January 1984), 179-184.
32. Zucker, S. W. and Hummel, R. A. A Three- Dimensional Edge Operator. IEEE Trans. on Pattern Analysis and Machine Intelligence PAMI-3, 3 (May 1981), 324-331.