# Fast Implicit Surface Reconstruction for the Radial Basis Functions Interpolant
## 5 Fast Reconstruction
### Leaf Growing  
In the voxel growing queue, the numerical results show that assigning different priorities to the pending voxels leads to a different evaluation efficiency. It is because the order of voxel growing affects the single point evaluation efficiency. Compared with the original FMM, the third step of the single point FMM computes the L2P coefficients many times for the evaluation points in the same leaf cell. For the evaluation points in the same leaf cell, the L2P operation interpolates at the same Chebyshev nodes, and the same coefficients can be precomputed by expanding the Chebyshev polynomials. To avoid a mass of redundant computation, we present the leaf growing method based on the improved voxel growing method. The main difference is that the growing process considers both the evaluation cell of FMM and the reconstruction cell of MC. The evaluation cell of FMM refers to leaf cell, the finest level of octree. The reconstruction cell of MC refers to the voxel or cube. An available approach is to track the implicit surface leaf by leaf instead of voxel by voxel, and then to evaluate all the voxels in the same leaf. To reduce the number of evaluation points, the improved growing strategy is to track the implicit surface leaf by leaf in global, and voxel by voxel in local. In addition, the voxels in the growing queue are specified a priority via the position in the leaf. There are three positional relationships between the leaf and the voxel, namely interior, intersection and exterior, as shown in Figure 4. In the voxel growing process, a leaf \(T\) with the precomputed L2P coefficients is viewed as a current leaf. The precomputed L2P coefficients of \(T\) will be stored until there are no voxels inside or intersecting \(T\) in the voxel growing queue. To save the memory storage, for the voxels in the growing queue, the voxels inside the current leaf should be evaluated first. Then the voxels intersecting the current leaf will be evaluated and a new current leaf will be obtained. Given a radial basis functions interpolant \(f(x)\), and a desired reconstruction accuracy \(\epsilon\), based on the above analysis, a simplified procedure of the fast implicit surface reconstruction method for the RBF interpolant is given below. Step 1: Space division. Compute the minimum bounding box via the constraint points and divide the space into regular voxels (cubes) via the desired reconstruction accuracy \(\epsilon\). Scale the minimum bounding box in a certain ratio. Step 2: Construct the initial seed voxels. Select the points of the domain constraints with zero values (\(f(x_{i})=0\)) as the seed points and construct an initial seed voxel set \(S\) via the positions of the seed points. Step 3: Execute the setup step. Compute the multipole moments based on the source points \(\left\{\boldsymbol{y}_{j}\right\}\). The source points are the interpolation centers for the RBF interpolant \(f(\boldsymbol{x})\). Step 4: Traverse the initial seed voxel set \(S\). Construct a voxel growing queue \(G\) and add an initial seed voxel to \(G\). Step 5: Traversing the voxel growing queue \(G\), take out a voxel \(V\) with the highest priority. Evaluate the points of the voxel \(V\) by executing the translation and evaluation steps. Obtain the current leaf cell of the FMM according to the L2P operation. Store the evaluated points and the evaluated voxels to avoid the repeated evaluation. Step 6: According to the lookup table of the marching cubes method, triangulate the voxel \(V\) via the eight evaluated values. Optionally, some additional strategies can be implemented to resolve the ambiguities. Step 7: Determine the new growing voxels for tracking. Among the six adjacent voxels of \(V\), append the un-evaluated voxels that are intersected the isosurface to the voxel growing queue \(G\). Step 8: Specify a priority for the new growing voxels via the corresponding position in the current leaf cell of the FMM.