# A Two-Step Surface Reconstruction Method Using Signed Marching Cubes
## 2 Method
### Signed Fast Multipole Method  
To recover the interpolated surface of an implicit function, it is necessary to sample the geometry space and evaluate the function values of the sampled points. The efficiency of the surface reconstruction mainly depends on the process of evaluation. The direct evaluation of a radial basis function with \(N\) constraint points requires \(O(N)\) operations. To accelerate the speed of evaluation, the fast multipole method can be utilized to approximate the function values of radial basis functions within a given precision. Given a set of target points (evaluation points) \(\{\mathbf{x}\}\) and source points (interpolation points) \(\{\mathbf{y}\}\), the basic idea of the fast multipole method is to represent the RBF kernel using a finite series [35]. \[\Phi(\mathbf{x},\mathbf{y})=\sum_{n=1}^{p}\phi_{n}(\mathbf{x})\phi_{n}(\mathbf{y})+R_{p}(\mathbf{x },\mathbf{y}) \tag{7}\]  
where \(p\) is the expansion order of the series \(\phi_{n}\) and \(\psi_{n}\). \(R_{p}(\mathbf{x},\mathbf{y})\) is a residual that satisfies \(R_{p}(\mathbf{x},\mathbf{y})\to 0\) for \(\parallel\mathbf{x}-\mathbf{y}\parallel_{2}\rightarrow\infty\) and/or \(p\rightarrow\infty\). Then, the summation of RBF kernels can be evaluated at the evaluation points \(\{\mathbf{x}\}\) via the following formula  
\[f(\mathbf{x})=s_{p}(\mathbf{x})+\varepsilon_{p} \tag{8}\]  
where  
\[s_{p}(\mathbf{x})=\sum_{j=1}^{N}\omega_{j}\Phi\Big{(}\mathbf{x},\mathbf{y}_{j}\Big{)}=\sum _{n=1}^{p}\phi_{n}(\mathbf{x})\left[\sum_{j=1}^{N}\omega_{j}\psi_{n}\Big{(}\mathbf{y}_ {j}\Big{)}\right]=\sum_{n=1}^{p}\Psi_{n}(\mathbf{y})\phi_{n}(\mathbf{x}) \tag{9}\]The moments \(\Psi_{n}(\mathbf{y})\) can be pre-computed firstly. The evaluation error \(\varepsilon_{p}\) satisfies  
\[\varepsilon_{p}=\sum_{j=1}^{N}\omega_{j}R_{p}(\mathbf{x},\mathbf{y})>0 \tag{10}\]  
Note that the evaluation points should be far away from the source points to ensure the expansion order is small enough. Therefore, the multilevel fast multipole method [36] is developed to construct the finite series using several fast multipole method operations, including P2M, M2M, M2L, L2L, L2P, and P2P. In this paper, the kernel independent fast multipole method (black-box fast multipole method [37]), is utilized to evaluate the function values of the radial basis functions efficiently. In general, the higher the expansion order \(p\) of a series is, the smaller the approximate residual will be. That is, a higher expansion order corresponds to a higher accuracy of the evaluated kernel function value and a smaller evaluation error \(\varepsilon_{p}\). However, sometimes it is not necessary to spend too much time to compute the accurate function value, but only to determine the sign of the function value. In this case, we can utilize a lower expansion order to determine the sign of the function value. Therefore, how to determine the positive and negative sign of the function value is a key problem. The relationship between the expansion order \(p\) and the evaluation error \(\varepsilon_{p}\) can be defined as  
\[f(\mathbf{x})=s_{p}(\mathbf{x})+\varepsilon_{p}=\left\{ \begin{array}{ll}>0,&\text{ if }s_{p}(\mathbf{x})>0\;\;\text{and}\;\;s_{p}(\mathbf{x})-\varepsilon_{p}>0\\ <0,&\text{if }s_{p}(\mathbf{x})<0\;\;\text{and}\;\;s_{p}(\mathbf{x})+\varepsilon_{p}<0 \end{array} \right. \tag{11}\]  
Considering that the absolute function values of the points that are far away from the target isosurface are greater than the evaluation error \(\varepsilon_{p}\), it is possible to evaluate the sign of the function values using a lower expansion order at these points. In other words, we can select a lower expansion order in the process of evaluation to filter the non-boundary voxels that are far away from the target isosurface. To distinguish different kinds of voxels, the evaluation voxels are divided into two kinds: the non-boundary voxels (including the exterior voxels and the interior voxels) and the boundary voxels.