Home About the Journal Latest Work Current Issue Archive Special Issues Editorial Board

2021,  3 (4):   336 - 349

Published Date：2021-8-20 DOI: 10.1016/j.vrih.2021.08.006

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.

Content

1 Introduction
Three-dimensional (3D) reconstruction algorithms are mainly divided into volume rendering and surface rendering algorithms. A surface rendering algorithm first extracts features from two-dimensional (2D) tomographic images, and then it uses intermediate geometric primitives such as quadrilaterals, triangles, hexahedrons, cones, and tetrahedrons to fit the 3D surface contour of the model to be reconstructed[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.
Currently, the main algorithms for surface rendering include the triangulation of contour lines, cuberille, dividing cubes, and marching cubes[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.
The ambiguity of the MC algorithm was first reported by Dürst in 1988[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.
The irrational selection of the topological configuration may lead to a lack of connection between the isosurfaces in the adjacent voxels, eventually resulting in holes in the generated isosurfaces.
The marching tetrahedra (MT) algorithm proposed in 1990[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].
The current methods for the optimization of the reconstruction time of the MC algorithm include parallel computation and octree. The octree method can avoid the calculation of some empty voxels to some extent by block processing the input data, which was proposed by Wilhelms and Van Gelder[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].
In this paper, a surface rendering algorithm based on edge growth is proposed to solve the problems of topology ambiguity and slow reconstruction time of the MC algorithm. In the proposed algorithm, seed triangles are selected and then the edges of these triangles are added to achieve the goal of 3D reconstruction.
2 Algorithm description
2.1 Method and process
In the 3D reconstruction process of the MC algorithm, the isosurface of each cube is interpolated according to its 15 basic topologies, as shown in Figure 1.
The ambiguity of the MC algorithm means that the topological configuration of the cube is not unique when selected, and the corresponding topological configurations can be replaced by other topological configurations. Owing to the existence of ambiguity and to the fact that the MC algorithm processes each cube separately in the reconstruction process, it does not consider the relationship between adjacent cubes. When there is uncertainty as to which topology to use, the reconstructed model will occasionally have holes, as shown in Figure 2.
It is well known that the outer contour of an object is a continuous surface. In 3D reconstruction, the isosurface of an object is also continuous. Therefore, the isosurfaces left by passing through adjacent cubes do not exist independently, but are connected to each other, as shown in Figure 3.
As can be seen in Figure 3, when an isosurface passes through a pair of adjacent cubes, it leaves a line of intersection on the common surface of the adjacent cubes, and this line of intersection is the common edge of the isosurface in the two cubes, acting as a connection between the two isosurfaces. On the basis of the characteristics of the intersecting lines, this paper proposes an edge-growing MC algorithm. The core concept of the algorithm is to use the existing isosurface to generate the isosurface in the adjacent cube. As shown in Figure 3, if the isosurface in the left cube has been generated, but that in the right one does not yet exist, then the isosurface in the right cube can be generated through the common edge of the isosurface in the two cubes, which is called the growth edge.
The algorithm presented in this paper has a growth queue and two labeled arrays to ensure that the entire reconstruction process runs smoothly. The queue stores the growth edge information, and the tag arrays record how each cube is processed and how the growth of the cube is put into the growth queue. The growing edge information includes the 3D coordinates of the two ends, the gradient values of the two ends, and the cube coordinates where the growing edge is to be grown. The algorithm is divided into the following steps:
Step 1: Select the seed triangles and put the growth edge formed by the seed triangles into the growth queue.
Step 2: Remove the growth edge from the growth queue, interpolate the intersection points of the isosurface and the cube edge according to the topology configuration, and connect the intersection points to form a triangular mesh.
Step 3: Make the new edge where the isosurface generated in Step 2 intersects with the surface of the adjacent cube as a growth edge and put it into the growth queue.
Step 4: Repeat Steps 2 and 3 until the queue is empty.
The algorithm flowchart is shown in Figure 4.
2.2 Seed triangle selection
As can be seen in Figure 1, the isosurface corresponding to topology configuration 1 of the MC algorithm is a triangle. In view of the simplicity of topological configuration 1, three sets of data are used for the 3D reconstruction. The results of the 3D reconstruction are shown in Figure 5. Figure 5(a)-(c) shows the results of the 3D reconstruction of data 1, 2, and 3, respectively, using the MC algorithm, whereas Figures 5(d)-(f) show the effect of the 3D reconstruction of data 1, 2, and 3, respectively, when only the cube of topological configuration 1 is reconstructed. From the comparison of the results of the same data reconstruction, Figure 5(d)-(f) can basically reflect the approximate outline of the object, except for the small number of triangular patches in the model, and the independent triangular patches are evenly distributed on each cross section. From the reconstruction results, we can see that topological configuration 1 has a high proportion in the 3D reconstruction of these models.
Owing to the simplicity and high proportion of topological configuration 1, the triangle of topological configuration 1 is used as the seed triangle and then the edge of the seed triangle is used as the growth edge for growth reconstruction.
In practical applications, the number of selected seed triangles must be reasonable: having too few triangles may not yield the desired effect of reconstruction because of noise, whereas having too many will consume more time in the selection of the seed triangles. In most of the experiments in this study, all the triangles generated from one layer of topology 1 were selected as the seed triangles. This method is simple and easy to implement, and it can achieve a good reconstruction effect. For the selection of the number of layers, we need to select the layer whose curvature changes because the content of topological configuration 1 in this layer is greater and the middle layer can usually meet the requirement of seed selection. For the seed triangle, it is not limited to a layer of cubes, but can be selected manually or in a designated 3D area. The core of this algorithm is 3D reconstruction based on edge growth. The purpose of selecting the seed triangle is to obtain the growing edge, which can also be obtained from other topologies.
2.3 Three-dimensional reconstruction based on edge growth
2.3.1 Interpolation
In this algorithm, a three-segment interpolation method is proposed for interpolation reconstruction. The three-segment interpolation method entails an interpolation between the linear interpolation and the midpoint selection.
Assume that
$p 1$
and
$p 2$
are the 3D coordinates of two vertices on one side of the cube,
$h u 1$
and
$h u 2$
are the grayscale values of the two vertices, and the threshold of the isosurface is
$Y$
. When this edge and the isosurface have an intersection point, the intersection point coordinates are calculated using the following formula:
$p = p 1 + ( p 2 - p 1 ) ( Y - h u 1 ) / ( h u 2 - h u 1 )$
If the
$( Y - h u 1 ) / ( h u 2 - h u 1 )$
part in the formula is called the interpolation ratio
$k$
, then
$p = p 1 + k ( p 2 - p 1 )$
The selection of the
$k$
value in the expression is a special feature of the three-segment interpolation method in this study. First, the lower limit
$m$
, upper limit
$n$
, lower value
$q$
, and upper value
$p$
should be set, in which
$0 < q < m < n < p < 1$
and
$q + p = 1$
are required. Then, the absolute value of
$k$
is compared with
$m$
and
$n$
. When the absolute value of
$k$
is less than
$m$
, its absolute value is
$q$
. When the absolute value of
$k$
is greater than
$n$
, its absolute value is
$p$
. In other cases, the absolute value of
$k$
is 0.5. In the three-segment interpolation method, the positive and negative requirements of
$k$
are always the same as before and only its absolute value is normalized. In the practical application of this study,
is 0.25,
$m$
is 0.3,
$n$
is 0.7, and
$p$
is 0.75.
2.3.2 Topological configurations
Because this study adopted the three-segment interpolation method in the interpolation criterion, the intersection points of the interpolation will only be between two endpoints on each side.
The growth edge can be divided into two types according to the position of the two endpoints. In the first type, the two ends of the growing edge are on the two adjacent edges and the growing edge intersects the two sides to form a triangle, as shown on the left-hand side of Figure 6. In the second type, the two ends of the growing side are on opposite sides and the growing side divides the surface of the cube into two quadrangles, as shown on the right-hand side of Figure 6. In this paper, the former growth edge is called the triangle edge and the latter growth edge is called the quadrangle edge.
Because the position of the growth edge is uncertain, we name the vertices of the cube on the basis of the two end points
$I$
and
$I I$
of the growth edge and of the plane where the growth edge is located, which is conducive to the extraction of the isosurface. Figure 7 shows the names of the vertices of the cube when the triangle edges grow. The naming rule is as follows. The names of all vertices on the surface where the growth edge is located begin with
$S S$
, the surface where the growth edge is located is called the
$S S$
surface, the names of the vertices opposite to the
$S S$
all begin with
$S _ S$
, and the surface they are on is called the
$S _ S$
surface. The vertices that simply form a triangle on the
$S S$
surface and the growing edge are directly named
$S S$
, and the two vertices adjacent to the point
$S S$
on the
$S S$
surface are named
$S S _ I$
and
$S S _ I I$
, respectively. The diagonal point opposite to the
$S S$
point on the
$S S$
surface is named
$S S _ I _ I I$
. The name of each point on the
$S _ S$
surface mainly refers to the name of the point on the adjacent
$S S$
surface. The names of the adjacent points on the two surfaces are the same in the suffix.
When using the triangular edge for growth 3D reconstruction, we take the point
$S S$
as the reference point and compare its grayscale value
$H u s s$
with the reconstruction threshold
$Y$
. If
$H u s s$
is greater than threshold
$Y$
, the vertex with a grayscale value greater than threshold
$Y$
is said to meet the requirements, and the remaining points do not meet the requirements. If
$H u s s$
is not greater than threshold
$Y$
, then the vertex with a grayscale value not greater than
$Y$
is called the point that meets the requirements, and the remaining are points that do not meet the requirements. As shown in Figure 7, the vertices that meet the requirements are marked with a large dot and those that do not meet the requirements are marked with a small dot. In the subsequent figures, large and small points are also used to mark each vertex. Some unmarked points in some topological configurations are called irrelevant points, and they do not participate in the specific isosurface generation. In addition, because the proposed algorithm starts from the growing edge, only the isosurfaces that are connected to the growing edge are extracted from the cube body, and, therefore, all the points that meet the requirements are connected to each other when extracting the isosurface.
According to the position of the cube surface where the growth edge is located and to the relationship between the grayscale value of each vertex of the cube and the threshold value, 11 topological configurations when the triangle edge is used for growth are summarized, as shown in Figure 8.
When growing with four corners, we need to first compare the grayscale values of the eight vertices of the cube with the threshold
$Y$
. Then, the vertex is divided into two parts: in the first part, the grayscale value is greater than the threshold, whereas in the other part the grayscale value is not greater than the threshold. A smaller number of points are selected as the reference point, that is, the points that meet the requirements, and the number of points that meet the requirements will be in the closed interval of 1 and 4. As with the growth of triangular edges, when the four corners are used for growth, the vertices of the cube also need to be named. The naming rule is as follows. All the vertices on the surface where the growth edge is located begin with
$S S$
, and the surface where the growth edge is located is called the
$S S$
face. The face of the
$S S$
face to face is the
$S _ S$
face, and the names of the vertices on this face start with
$S _ S$
. In the
$S S$
face, the vertex that meets the requirements that is adjacent to vertex
$I$
of the growth edge is called the
$S S _ I$
point and the adjacent points that do not meet the requirements are called
$S S _ U P _ I$
. The vertex that meets the requirements that is adjacent to vertex
$I I$
of the growth edge is called point
$S S _ I I$
, and the adjacent points that do not meet the requirements are called
$S S _ U P _ I I$
. The vertices on the side
$S _ S$
have the same suffix as that of the vertices on the side
$S S$
. Figure 9 shows the specific names of each vertex.
According to the position of the cube surface where the growing edges are located, six topological configurations are obtained when growth with a quadrangle edge is used for reconstruction, as shown in Figure 10.
The proposed algorithm extracts the isosurfaces from the cube according to the 17 proposed topological configurations. After interpolating the isosurface in the cube according to the topological configuration, we also need to determine whether the intersection of the isosurface and the surface of the cube can become a new growth edge and continue to grow. The basis for the judgment is that this edge is a new growth edge, and neither the processing label value nor the growth label value of adjacent cubes that share the side is 4.
2.3.3 Cube marks
When a cube is processed, its processing needs to be recorded, and only when the processing mark value reaches a certain requirement does further processing of the cube stop. Each cube has two markers: one is the processing marker, which records how the cube is processed according to the growth criteria, and the other one is the growth marker, which records how the growth information of the cube is put into the growth queue. There are also five levels for these marks, which are represented by the numbers 0, 1, 2, 3, and 4, respectively. Level 0 is the lowest, indicating that the cube has not been processed. Level 4 is the highest, indicating that the cube has been processed and no further processing is required. Other numbers indicate that the cube has been processed but may need further processing. The previous 17 topologies show only one growing edge; however, in practice, it is possible to have separate isosurfaces in a cube, and, therefore, there is substantial work to be done in the case of such a cube.
The specific marker assignment criteria are as follows. Extract the cube corresponding to the seed triangle, and directly set all the tags of the corresponding cube to 4 after the seed triangle is extracted. After the growth edge information is put into the growth queue, add 1 to the value of the cube growth marker to be processed. When the corresponding topological configurations of the cube are 4, 5, 7, 8, 10, 11, 13, 15, and 17, after the cube is processed, set the processing tag value to 4. When the corresponding topological configurations of the cube are 2, 3, 6, 9, 12, 14, and 16, after the cube is processed, set the processing flag value to 3. When the topological configuration of the cube is 1, after the cube is processed, increment the processing mark value by 1.
When the processing tag value of a cube is 4, there is no need for any subsequent processing of the cube. When the growth tag value of the cube is 4, there is no need to put the growth information regarding the cube into the growth queue. In addition, when the processing label of a cube is greater than 1 and less than 4, only the isosurface of topological configuration 1 is extracted from the cube.
3 Results and discussion
3.1 Ambiguous hole detection result
In the proposed algorithm, the primary problem is to solve the ambiguity of the topology configuration. Because of the ambiguity, the generated 3D model will have holes in some details, which greatly reduces the overall quality of the model. Aiming at the hole problem, Masala proposed the current simplest solution. Masala's improved MC algorithm deleted one of the original 15 topological configurations of the MC algorithm, added 7 more, and, finally, set the topological configuration to 21 types.
To determine whether the model generated by the 3D reconstruction has holes, this study used Masala's data, which Masala called the MC example and whose size is
$10 × 10 × 10$
; that is, there are 10 layers of data and each layer is of size
$10 × 10$
. Except for the fifth, sixth, and seventh layers, the data values of the other layers are all 0. The data of the fifth, sixth, and seventh layers are shown in Figure 11. The data for the sixth and seventh layers are the same.
Figure 12 shows the reconstruction results of the standard MC algorithm, Masala's improved MC algorithm, and the proposed algorithm when using the set of data of the MC example for reconstruction. As can be seen in the figure, the reconstruction results of the standard MC algorithm have obvious holes. The reconstruction results of the proposed algorithm are the same as those of the improved MC algorithm of Masala, and the generated 3D model has no holes. Figure 13 shows the mesh display results of each model in Figure 12. As can be seen in the figure, the mesh model of the standard MC algorithm has obvious jaggedness on the left-hand side. Because of the lack of some triangles on these saw teeth, the final generated model was incomplete and there were some holes. The mesh model corresponding to Masala's improved MC algorithm is roughly the same as that corresponding to the proposed algorithm, and all generated models are closed mesh models.
3.2 Quality and time analysis of the reconstruction model
Masala's improved MC algorithm mainly improves the topology configuration of the original MC algorithm, which has the problem of ambiguity. To evaluate the performance of our algorithm, we conducted two sets of experiments to determine the reconstruction effect. Table 1 shows the environment configuration of the entire experiment.
Environment configuration of the experiment
Name Parameter
Operating system Windows 10 (64 bit)
CPU Intel Core i5-8400
Memory 8 GB
Development environment Visual Studio 2015
Platform VTK
The first set of experimental data was a set of segmented medical image data, which consisted of 145 two-dimensional tomographic images with a size of
$125 × 105$
. The 3D reconstruction models of Masala's improved MC algorithm and of the proposed algorithm are shown in Figure 14. The seed triangle of the proposed algorithm was obtained from all the cube voxels in the middle layer. As can be seen in the figure, the two algorithms have the same grid on the overall 3D external contour of the 3D image; however, from the inside of the model, Masala's improved MC algorithm has many more internal grids than those of the model reconstructed by the proposed algorithm. In practical applications, these internal grids do not participate in the display of the model. These internal grids are mainly caused by incomplete segmentation. In the case where only a complete external 3D contour mesh model is needed, the proposed algorithm is better than Masala's improved MC algorithm in terms of the quality of the reconstructed model.
Under the same environment configuration, the time spent and the number of triangles generated on the first set of data for the 3D reconstruction by the two algorithms are listed in Table 2. As can be seen in the table, the proposed algorithm generated fewer triangles in the reconstruction model than those generated by Masala's improved MC algorithm. In terms of reconstruction time, there is little difference between the two algorithms, with the reconstruction time of the proposed algorithm being slightly shorter than that of Masala's improved MC algorithm.
Three-dimensional reconstruction information of the first set of experiments
Algorithm Time (s) Triangular faces
Masala’s 0.219711 79,728
Ours 0.212538 71,472
In the second experiment, four sets of data were reconstructed and the same reconstruction threshold was used for these four sets of data. These four sets of data are labeled as data Nos. 1, 2, 3, and 4, respectively. At the same time, 3D reconstruction was carried out using Masala's improved MC algorithm and the proposed algorithm. The reconstruction result is shown in Figure 15, where the seed triangle of the proposed algorithm was obtained from all the cube voxels in the middle layer.
Figure 15 (a)-(d) showsthe 3D models reconstructed by Masala's improved MC algorithm under data Nos. 1, 2, 3, and 4, respectively; Figure 15(e)-(h) shows the 3D models reconstructed by the proposed algorithm under data Nos. 1, 2, 3, and 4, respectively.As can be seen in the figure, the 3D reconstruction result of Masala's improved MC algorithm is similar to that of the proposed algorithm.Figure 16 shows a partial enlargement of the chest using the second set of data for the3D reconstruction.As can be seen in the figure,the model of Masala's improved MC algorithm has many scattered small fragments compared with that of the proposed algorithm, which is somewhat similar to the noise in the two-dimensional (2D) image. These fragments reduced the overall display effect of the model.Therefore, when some fragments that are not connected to the main contour are not needed, the reconstruction quality of the proposed algorithm is better than that of Masala's improved MC algorithm.
Table 3 shows the time spent by the two algorithms in the reconstruction process of the second set of experiments and the number of triangles generated in the mesh model. As can be seen in the table, under the same reconstruction parameters, the number of triangles in the reconstruction model of the proposed algorithm is lower than that of Masala's improved MC algorithm. In terms of reconstruction time, the proposed algorithm took longer to reconstruct data No.2. The reconstruction times of the proposed algorithm for the other three sets of data were shorter than those of Masala's improved MC algorithm.
Comparison of the 3D reconstruction results of the four sets of data in the second set of experiment
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
In the experiments, Masala's improved MC algorithm was compared with the proposed algorithm, and it was found that both algorithms can effectively avoid holes on the surface of the 3D reconstruction model. In the proposed algorithm, among the five sets of data in the experiments, only one set of data entailed a longer time for 3D reconstruction, whereas the remaining four sets of data required a shorter time. In addition, the number of triangles generated in the reconstruction model of the proposed algorithm was lower than that of Masala's improved MC algorithm. In terms of the details of the 2D data that did not require 3D reconstruction, the proposed algorithm performed better than Masala's improved MC algorithm.
3.3 Effect of seed region selection on the reconstruction model
To facilitate the use of the proposed algorithm for the 3D reconstruction of medical images, we developed a simple 3D reconstruction system. The system can set the selected area of the seed triangle to reconstruct a 3D model connected to the seed triangle. We selected a set of human brain data to test this system. The data consisted of 320 two-dimensional images. The results of the 3D reconstruction are shown in Figure 17, where Figure 17a is a model obtained via the reconstruction of the entire data using the MC algorithm. The model is the entire skull corresponding to the data, and each bone is scattered in each area. Figure 17b shows the reconstruction result of the system when the seed region is
and its corresponding 3D model is the maxilla. Figure 17c shows the reconstruction result of the system when the seed selection area is
and its corresponding 3D model is the mandible. As can be seen in the figure, when the system selects different seed regions, the reconstructed model is also different. Owing to this reconstruction effect, for multiple scattered tissues, the proposed algorithm can be used to set the seed area to perform 3D reconstruction of the designated part of the image.
4 Conclusion
This paper proposes a marching cube algorithm based on edge growth for 3D reconstruction. First, the 3D model reconstructed by this algorithm does not contain holes caused by ambiguity. Second, from the perspective of overall reconstruction quality, its appearance is consistent with that of the model reconstructed by Masala's improved MC algorithm; however, when only the main contour of the model is needed, the reconstruction effect of the proposed algorithm is better. Because the proposed algorithm, MC algorithm, and Masala's improved MC algorithm are all based on cube voxel interpolation for 3D reconstruction, their reconstruction accuracies are the same. In the application of the proposed algorithm, when the tissues in the data entail multiple scattered parts, the 3D contour of a specified part can be extracted by setting the region of the selected seed.
The main limitations of the proposed algorithm are as follows. It uses a queue to store the growth side information. Compared with other types of algorithms, it requires more memory space and is not suitable for large-scale reconstruction on a small machine. The proposed algorithm generates a mesh model based on seeds and is not suitable for reconstructing multiple scattered objects, such as broken bones. It is necessary to artificially set the seeds for each scattered part or to expand the area of seed selection.
In subsequent development, multithreading can be used to accelerate the reconstruction speed of the algorithm. It can also be combined with volume rendering. First, the area to be reconstructed is determined according to the display results of the volume rendering, the seed area and the reconstruction threshold are set, and then the surface rendering algorithm proposed in this paper is used to accurately reconstruct the tissue of the specified part.

Reference

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