# Fast Implicit Surface Reconstruction for the Radial Basis Functions Interpolant
## 4 Fast Evaluation
### Single Point FMM  
The original FMM evaluates the sums of matrix-vector products. For the surface following method, the evaluation points are determined via the tracking process step by step. To efficiently evaluate the  
Figure 1: Quadtree decomposition of the multilevel FMM method. (**a**) In the second level of quadtree, the near field of the green box is composed by the white boxes and the green box itself (neighbor list). (**b**) The far field of the green box is composed by the gray boxes (interaction list). field points one by one, the tree-based procedures of the multilevel approach should be improved for single point evaluation. For a leaf cell T in the FMM tree (e.g., quad-tree in 2D, octree in 3D), the evaluation of any target point \(x_{i}\) in T is decomposed into three steps based on the black-box FMM operations [23; 33]. 1. Set up (P2M and M2M). The P2M and M2M operations have no connection with the evaluation points and can be computed first. For any leaf cell \(T\), the multipole moments of \(T\) are interpolated from the source points inside \(T\) at the Chebyshev nodes \(\overline{y}_{m}^{T}\)  
\[M_{m}^{T}=\sum_{y_{j}\in T}\omega_{j}S_{p}\Big{(}\overline{y}_{m}^{T},y_{j} \Big{)},\ m=1,2,\ldots,p \tag{5}\]  
For any non-leaf cell \(T\), the multipole moments of \(T\) are computed by gathering the child cells' multipole expansions interpolated at the Chebyshev nodes \(\overline{y}_{m}^{T}\)  
\[M_{m}^{T}=\sum_{T^{\prime}}\sum_{m^{\prime}}M_{m^{\prime}}^{T^{\prime}}S_{p} \big{(}\overline{y}_{m^{\prime}}^{T},\overline{y}_{m^{\prime}}^{T^{\prime}} \big{)},\ m=1,2,\ldots,p \tag{6}\]  
where \(T^{\prime}\) are the child cells of \(T\) and \(m^{\prime}\) is associated with \(T^{\prime}\). 2. Translation (M2L and L2L). The translation of far field expansions to near field expansions depends on the evaluation points. For the cells \(T\) containing \(x_{i}\) in different octree levels, the local expansions of far field are computed by translating the multipole moments interpolated at the Chebyshev nodes \(\overline{x}_{n}^{T}\)  
\[L_{n}^{T,J}=\sum_{J}\sum_{m}M_{m}^{I}K(\overline{x}_{n}^{T},\overline{y}_{m}^ {J}),\ n=1,2,\ldots,p \tag{7}\]  
where \(J\) are the cells in the interaction list of \(T\). The M2L operation of the computed cell is marked as true to avoid repeated calculation. For the cells \(T\) containing \(x_{i}\) in different octree levels, the local expansions of \(T\) are computed by adding the far field interactions and translating the parent cell's local expansions interpolated at the Chebyshev nodes \(\overline{x}_{n}^{T}\)  
\[L_{n}^{T}=L_{n}^{T,J}+\sum_{n^{\prime}}L_{n^{\prime}}^{T^{\prime}}S_{p}\Big{(} \overline{x}_{n}^{T},\overline{x}_{n^{\prime}}^{T^{\prime}}\Big{)},\ n=1,2, \ldots,p \tag{8}\]  
where \(T^{\prime}\) is the parent cell of \(T\) and \(n^{\prime}\) is associated with \(T^{\prime}\). The L2L operation of the computed cell is marked as true to avoid repeated calculation. 3. Evaluation (L2P and P2P). Once the setup and translation steps have been completed, the evaluation for a single point can be computed as the sum of the far field and near field by  
\[f_{K}(x_{i})\approx f_{K}^{far}(x_{i})+f_{K}^{near}(x_{i}) \tag{9}\]  
For any target point \(x_{i}\) in leaf cell \(T\), the interactions of far field are computed by  
\[f_{K}^{far}(x_{i})=\sum_{n}L_{n}^{T}S_{p}\Big{(}\overline{x}_{n}^{T},x_{i} \Big{)} \tag{10}\]  
For any target point \(x_{i}\) in leaf cell \(T\), the interactions of near field are directly computed by  
\[f_{K}^{near}(x_{i})=\sum_{I^{\prime}}\sum_{y_{j}\in I^{\prime}}\omega_{j}K \Big{(}x_{i},y_{j}\Big{)} \tag{11}\]  
where \(J^{\prime}\) are the cells in the neighbor list of \(T\). The setup step computes the multipole moments of the cells in each level via the source points. It is only executed once before the evaluation process without considering the evaluation points. The other two steps are computed based on the evaluation points. The translation step computes the conversion of multipole moments and local expansions to the target leaf cell.