# A Two-Step Surface Reconstruction Method Using Signed Marching Cubes
## 1 Introduction  
Reconstructing a surface from a series of geological sampling points is a well-studied problem in geological modeling, computer graphics, and reverse engineering, etc. In geological modeling, the implicit modeling method [1; 2; 3; 4] interpolates the geological sampling points to obtain an implicit function representing the best fitting geological surface. To visualize the interpolated implicit function, the implicit surface reconstruction method [5; 6; 7] should be used to extract the target isosurface of the interpolated implicit function. What is proposed in this paper is the tracing of a surface (two-manifold) in 3D, but similar concepts have been investigated in other cases (e.g., polynomial systems [8; 9]). There are many implicit surfaces reconstruction methods used to extract isosurfaces, including the marching cubes (MC) methods [10; 11; 12; 13; 14; 15; 16], the marching tetrahedra (MT) methods [17; 18], and the Delaunay triangulation methods [19; 20; 21]. The marching cubes method is widely used for its efficiency and robustness. Based on the given implicit function, the basic idea of the marching cubes method is to triangulate the sampling points by evaluating the corresponding function values. The evaluation points are sampled regularly by a specified voxel size in the modeling space. Then, the target isosurface is extracted by triangulating the sampling points to approximate the target isosurface based on the eight vertices of each cube and a predefined lookup table. For the quality of the triangular mesh, [PERSON] et al. [22] presented an edge transformation method for improving the mesh quality of the marching cubes to reduce degenerate triangles. [PERSON] et al. [23] extended the lookup table, which differentiates scalar values equal to the isovalue from scalar valuesgreater than the isovalue, in order to improve the quality of reconstructed mesh. For the correctness of the mesh topology, there are several methods [24] presented to resolve the ambiguity of the isosurface for any cube configuration. The motivation of this paper is to reconstruct an implicit surface from a given implicit function efficiently by improving the evaluation process of the classical marching cubes method. The performance of implicit surface reconstruction involves the space complexity and the time complexity [25]. An important limitation of the classical marching cubes method is that it takes too much time to evaluate the points of invalid voxels that do not intersect with the target isosurface. To deal with this problem, a common approach is to track the valid voxels that intersect with the target isosurface using the surface following strategy [26]. However, the surface following method depends on the initial seed voxels to reconstruct the target isosurface. In addition, the method may fail to recover the complete isosurface if the initial seed seeds are not sufficient. Therefore, in this work, to accelerate the evaluation process, we try to develop a two-step reconstruction method, including a coarse evaluation step and a refine evaluation process. The key idea of the two-step reconstruction method is based on the fact that, for the radial basis functions (RBF) method [27; 28; 29], the target zero isosurface can be evaluated by the sign of the implicit function using different expansion orders according to different evaluation precisions. The fast multipole method (FMM) [30; 31; 32; 33; 34] is used to accelerate the evaluation of RBF-based implicit functions. A higher expansion order of the fast multipole method obtains a more accurate function value, but it consumes more time than a lower expansion order. [PERSON] et al. [11] proposed a marching cubes hierarchical adaptive algorithm for fast polygonization of variational implicit surfaces. As mentioned earlier, the surface following method improves the traditional marching cubes method by tracking the adjacent target voxels to recover the isosurface via some given seed voxels that intersect with the target isosurface.