A marching cube algorithm based on edge growth

Xin WANG ¹ , Su GAO ² , Monan WANG ¹ , Zhenghua DUAN ¹

1. Key Laboratory of Medical Biomechanics and Materials of Heilongjiang Province, Harbin University of Science and Technology, Harbin 15000, China

2. Beijing Normal University Hospital, Beijing 100875, China

Abstract

The marching cube algorithm is currently one of the most popular three-dimensional (3D) reconstruction surface rendering algorithms. It forms cube voxels based on an input image and then uses 15 basic topological configurations to extract isosurfaces from the voxels. The algorithm processes each cube voxel in a traversal-based manner, but it does not consider the relationship between the isosurfaces in adjacent cubes. Owing to ambiguity, the final reconstructed model may have holes. In this paper, we propose a marching cube algorithm based on edge growth. The algorithm first extracts seed triangles, grows these seed triangles, and then reconstructs the entire 3D model. According to the position of the growth edge, we propose 17 topological configurations with isosurfaces. The reconstruction results showed that the algorithm can reconstruct the 3D model well. When only the main contour of the 3D model is required, the algorithm performs well. In addition, when there are multiple scattered parts in the data, the algorithm can extract only the 3D contours of the parts connected to the seed by setting the region selected based on the seed.

Keyword

3D reconstruction ; Marching cube ; Edge growth

Cite this article

Xin WANG, Su GAO, Monan WANG, Zhenghua DUAN. A marching cube algorithm based on edge growth. Virtual Reality & Intelligent Hardware, 2021, 3(4): 336-349 DOI:10.1016/j.vrih.2021.08.006

References

1. Newman T S, Yi H. A survey of the marching cubes algorithm. Computers & Graphics, 2006, 30(5): 854–879 DOI:10.1016/j.cag.2006.07.021

2. Keppel E. Approximating complex surfaces by triangulation of contour lines. IBM Journal of Research and Development, 1975, 19(1): 2–11 DOI:10.1147/rd.191.0002

3. Herman G T, Liu H K. Three-dimensional display of human organs from computed tomograms. Computer Graphics and Image Processing, 1979, 9(1): 1–21 DOI:10.1016/0146-664x(79)90079-0

4. Cline H E, Lorensen W E, Ludke S, Crawford C R, Teeter B C. Two algorithms for the three-dimensional reconstruction of tomograms. Medical Physics, 1988, 15(3): 320–327 DOI:10.1118/1.596225

5. Lorensen W E, Cline H E. Marching cubes: a high resolution 3D surface construction algorithm. ACM SIGGRAPH Computer Graphics, 1987, 21(4): 163–169 DOI:10.1145/37402.37422

6. Jin J, Wang Q, Shen Y, Hao J S. An improved marching cubes method for surface reconstruction of volume data. In: 2006 6th World Congress on Intelligent Control and Automation. Dalian, China, IEEE, 2006, 10454–10457 DOI:10.1109/wcica.2006.1714052

7. Dürst M J. Re: Additional reference to marching cubes. ACM SIGGRAPH Computer Graphics, 1988, 22(5): 243 DOI:10.1145/378267.378271

8. Shirley P, Tuchman A. A polygonal approximation to direct scalar volume rendering. ACM SIGGRAPH Computer Graphics, 1990, 24(5): 63–70 DOI:10.1145/99308.99322

9. Nielson G M, Hamann B. The asymptotic decider: resolving the ambiguity in marching cubes. Proceeding Visualization'91, 1991, 83–91 DOI:10.1109/visual.1991.175782

10. van Gelder A, Wilhelms J. Topological considerations in isosurface generation. ACM Transactions on Graphics, 1994, 13(4): 337–375 DOI:10.1145/195826.195828

11. Zhou C, Shu R B, Kankanhalli M S. Handling small features in isosurface generation using Marching Cubes. Computers & Graphics, 1994, 18(6): 845–848 DOI:10.1016/0097-8493(94)90011-6

12. Masala G L, Golosio B, Oliva P. An improved Marching Cube algorithm for 3D data segmentation. Computer Physics Communications, 2013, 184(3): 777–782 DOI:10.1016/j.cpc.2012.09.030

13. Cercos-Pita J L, Cal I R, Duque D, de Moreta G S. NASAL-Geom, a free upper respiratory tract 3D model reconstruction software. Computer Physics Communications, 2018, 223: 55–68 DOI:10.1016/j.cpc.2017.10.008

14. Wilhelms J, van Gelder A. Octrees for faster isosurface generation. ACM Transactions on Graphics, 1992, 11(3): 201–227 DOI:10.1145/130881.130882

15. Montani C, Scateni R, Scopigno R. Decreasing isosurface complexity via discrete fitting. Computer Aided Geometric Design, 2000, 17(3): 207–232 DOI:10.1016/s0167-8396(99)00049-7

16. Lakshmipathy J, Nowinski W L, Wernert E A. A novel approach to extract triangle strips for iso-surfaces in volumes. VRCAI '04: Proceedings of the 2004 ACM SIGGRAPH International Conference on Virtual Reality Continuum and Its Applications in Industry. 2004: 239–245 DOI:10.1145/1044588.1044639

17. Vignoles G L, Donias M, Mulat C, Germain C, Delesse J F. Simplified marching cubes: an efficient discretization scheme for simulations of deposition/ablation in complex media. Computational Materials Science, 2011, 50(3): 893–902 DOI:10.1016/j.commatsci.2010.10.027

1. Pingbo HU, Bisheng YANG, Visual perception driven 3D building structure representa-tion from airborne laser scanning point cloud Virtual Reality & Intelligent Hardware 2020, 2(3): 261-275

Full Text

3 PDF

739 HTML

EXPORT

EndNote ProCite Reference Manager BibTex RefWorks

SHARE ON

ARTICLES BY AUTHORS

VRIH

BAIDU SCHOLAR

WANFANG DATA

CNKI