# A marching cube algorithm based on edge growth

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

Keywords： 3D reconstruction ; Marching cube ; Edge growth

Content

^{[1]}. A volume-rendering algorithm directly maps the input data into a 3D figure on the screen without passing through the intermediate geometric primitives. The algorithm proposed in this paper belongs to the class of surface rendering algorithms. Generally speaking, compared with the execution of a volume rendering algorithm, that of a surface rendering algorithm requires less memory and leads to better performance in terms of the details of the reconstruction model.

^{[2-5]}. Among these algorithms is the MC algorithm proposed by Lorensen and Cline in 1987. Because of its good 3D reconstruction effect, fast reconstruction speed, and simple algorithm principle, the MC algorithm has gained the recognition of the majority of image developers in practical applications. Currently, the MC algorithm has become a classical algorithm in the field of 3D reconstruction. From the results of in-depth research studies and practical applications, we found that the MC algorithm has the following shortcomings. The first shortcoming is ambiguity, which means that the topological configuration between adjacent cubes does not match, and the final reconstructed 3D model contains holes. The second one is that a certain amount of time is wasted in the calculation of empty voxels. An empty voxel refers to a cube that does not intersect with the isosurface, generally accounting for more than 95% of all cubes

^{[6]}. Because the MC algorithm processes all cube voxels in a traversal-based manner, part of the time is wasted in the calculation of empty voxels. The third shortcoming is that the MC algorithm generates a large number of triangles, which is not conducive to the rendering and storage of the model.

^{[7]}. They found that the MC algorithm has some basic configurations that can be replaced by a variety of other topological configurations and that it is impossible to determine which topology to use during reconstruction.

^{[8]}, which is one of the earliest surface rendering algorithms to solve the ambiguity issue, is based on the MC algorithm. The MT algorithm subdivides each cube voxel into multiple four-side voxels and then extracts isosurfaces from each tetrahedron for reconstruction. However, this algorithm also has ambiguity when the cube is divided into tetrahedrons. Owing to the ambiguity of the segmentation, the reconstructed model may still have holes. In addition, the reconstruction time of the MT algorithm is much longer than that of the MC algorithm. In 1991, Nielson and Hamann proposed the asymptotic decider

^{[9]}. This method can better judge the ambiguity of a cube surface. According to the criterion of judgment, the ambiguity of the cube surface can be resolved; however, the method still cannot resolve the ambiguity of the cube. Regarding the ambiguity of the MC algorithm body, the current main judgment methods include the saddle point method, critical point method, and generalized asymptotic method. For these judgment methods, although the ambiguity is resolved to a certain extent, it also increases the reconstruction time. In 1990, Van Gelder and Wilhelms proposed that only 3% of the topological structures are ambiguous in practical applications

^{[10]}. Because of the low frequency of ambiguity, Van Gelder and Wilhelms proposed an extended lookup table method that extends the main ambiguous topological structures and where the judgment of the topological configuration is mainly based on the grayscale and threshold values of the cube vertices. This type of method is of special research value because it not only reconstructs quickly but also reconstructs well under the premise of solving the holes in the model. In 1994, Zhou et al. further improved this method

^{[11]}. In 2013, Masala et al. expanded the 15 topological configurations of the MC algorithm to 21 on the basis of the extended lookup table method. This method can effectively solve the ambiguity problem, and it exhibits good performance in terms of the speed of reconstruction and the quality of the 3D model. At present, some software applications have applied this method

^{[12,13]}.

^{[14]}. Montani and Scateni proposed the use of a midpoint to replace the linear interpolation point in the MC algorithm. This method reduces many floating-point operations and is a commonly used acceleration method for the current MC algorithm

^{[15] }. Using Montani and Scateni's idea, some scholars also used golden ratio points and multisegment points to replace linear interpolation points. When the input data are large, the MC algorithm generates a large number of triangular meshes. The main solution is to simplify the reconstructed 3D mesh model

^{[16]}. In 2011, Vignoles and Donias proposed the simplified marching cubes (SMC) algorithm, which uses the vertex of the cube instead of interpolating the intersection point between the isosurface and the cube. This method can effectively avoid the ambiguity of the MC algorithm and generates fewer triangles than those generated by the latter. However, the precision of the SMC algorithm is not as good as that of the MC algorithm

^{[17]}.

Name | Parameter |
---|---|

Operating system | Windows 10 (64 bit) |

CPU | Intel Core i5-8400 |

Memory | 8 GB |

Development environment | Visual Studio 2015 |

Platform | VTK |

Algorithm | Time (s) | Triangular faces |
---|---|---|

Masala’s | 0.219711 | 79,728 |

Ours | 0.212538 | 71,472 |

Data No. | Algorithm | Time (s) | Triangular faces |
---|---|---|---|

1 | Masala’s | 40.1304 | 10,706,161 |

Ours | 36.9829 | 6,633,879 | |

2 | Masala’s | 33.3153 | 6,885,207 |

Ours | 36.463 | 5,973,771 | |

3 | Masala’s | 3.9786 | 1,519,788 |

Ours | 3.9027 | 1,276,479 | |

4 | Masala’s | 3.5484 | 845,165 |

Ours | 3.4459 | 686,160 |

Reference

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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