# Fast Implicit Surface Reconstruction for the Radial Basis Functions Interpolant
## 1 Introduction  
The reconstruction of implicit surfaces is commonly used in computer graphics, scientific data visualization, geometry processing, reverse engineering, etc. The reconstruction efficiency has always been a difficult problem that hinders the wide application of implicit surface (e.g., real-time shape editing). This work tries to extract the isosurface from the zero level set of an implicit function efficiently.  
As an important interpolation method, the radial basis functions (RBFs) interpolant [1; 2; 3] is widely used in different applications. In numerical analysis, the RBF interpolant plays a key role in solving partial differential equations (PDEs) [4]. In nonlinear time series analysis, it is used for the approximation of the flow in the phase space [5; 6]. In spatial interpolation, it is used to interpolate different geological data [7] (e.g., grade, fault and formation).  
In implicit modeling, given a set of unorganized points with normals (Hermite data), the implicit surface reconstruction methods interpolate the unknown surface using an implicit function. Based on the idea of signed distance field interpolation [8], the radial basis functions interpolant can be used to implicitly represent the implicit surface satisfying the Hermite data. The unorganized points are used to construct on-surface constraints, and the offset points generated by projecting along the normals are used to construct off-surface constraints.  
The implicit surface reconstruction involves two main processes, namely evaluation and reconstruction. As a classical method of surface reconstruction, the marching cubes (MC) method [9; 10]extracts the isosurface by triangulating the cubes in the discretized space. The method evaluates the implicit function values of all points sampled on the regular voxel points. It takes too much time to evaluate the invalid voxels that do not intersect the isosurface. The improved surface following method [11; 12] minimizes the number of evaluation points by tracking voxels intersecting the isosurface.  
For the RBF interpolant with large numbers of constraints, both the evaluation and reconstruction processes should be combined to accelerate the reconstruction of the implicit surface. The fast multipole method (FMM) [13; 14] is performed to efficiently calculate the sums of pairwise interactions between source points. However, different from the marching cubes method, the evaluation points are determined dynamically by tracking seed voxels for the surface following method. Therefore, on the one hand, the original FMM should be improved to efficiently evaluate the points one by one. On the other hand, to avoid the repeat computation of the coefficients of the FMM, the evaluation points in the same leaf cell of the FMM tree should be evaluated first in the reconstruction process.  
According to the above analysis, the minimum evaluation points and the optimization of single point evaluation should be combined to improve the efficiency of implicit surface reconstruction. In this paper, we improve an efficient implicit surface reconstruction method for the RBF interpolant. The method balances the reconstruction efficiency and the evaluation efficiency in the process of surface following. The goal is to ensure that one point evaluation of the method obtains a similar efficiency to the original FMM, so that it can be efficiently applied to the voxel growing method. To efficiently evaluate the field points one by one in reconstruction, we improve the FMM procedures for single point evaluation. The numerical results of several data sets showed the reliability and performance of the efficient implicit surface reconstruction method.