## 3 Results and Discussion
### Performance of Parallel Cartesian Mesh Generation Algorithm  
In this section, the performance of the parallel Cartesian mesh generation algorithm was analyzed through theory and numerical experiment. Some practical mesh generation tests are listed to compare the performance between the parallel algorithm and the traditional sequential algorithm. The testing environment is summarized below: (a) The program of CPU version was run in a work station with Intel Xeon CPU (2.6 GHz), and the program was written in Microsoft Visual C++; (b) The program of GPU version was run in a work station with Nvidia Quadro K2000. The GPU parallel program was written in Microsoft Visual C++ and Nvidia CUDA [32]. For traditional sequential ray casting algorithm, the total number of iterations was the number of rays, which can be expressed as: \(xynumber=xnumber\times ynumber\), where \(xnumber\) and \(ynumber\) are the number of cells in \(X\) and \(Y\) dimension, respectively. Then, in every iteration, intersection judgement was calculated for each ray. Using the same lattice grid triangle searching method, the time of judgement was the average number of facets in each lattice grid, which can be expressed as  
Figure 9: Result of Cartesian mesh generation for computational domain containing a large number of geometries, (**a**) an aircraft model; (**b**) mesh generation result of the aircraft engine; (**c**) mesh generation result of the aircraft wheel. \(avfacetnumber\). In the property mapping step, the time complexity was \(O(znumber)\), where \(znumber\) is the number of mesh cells in \(Z\) dimension. Therefore, the time complexity of the whole algorithm was \(O(xnumber\times znumber\times avfacetnumber)\). In the parallel Cartesian mesh generation algorithm, all three steps containing ray generation, intersection calculation, and property mapping were completed in a thread on GPU. In a thread, the ray generation step had a time complexity \(O(1)\). In the intersection test and calculation step, the time complexity was \(O(avfacetnumber)\). In the property mapping step, the time complexity was also \(O(znumber)\). The time complexity of the whole algorithm was \(O(znumber\times avfacetnumber)\). Thus, it can be seen that the parallel algorithm was much more efficient than the sequential one. Then, the performance of parallel algorithm in different situation was tested. Four 3D models were built for test containing a Hubble Space Telescope model (model 1), an aircraft model (model 2), a house model (model 3) as shown in Figure 10, and 64-spheres model (model 4) as shown in Figure 11, respectively. Four Cartesian meshes were generated with different cell numbers for the test. Table 1 lists the Cartesian mesh generation time of four models. It can be seen that the traditional sequential mesh generation algorithm spent a lot of time on the property mapping step. The time of mesh line generation step was very small compared with the total time, and could be ignored. By contrast, there was so much calculation occurring in property mapping step containing the intersection test, intersection point calculation, and arrangement with the increasing of the mesh cell number. For the parallel algorithm of GPU version, the total time cost of mesh generation was much less than the traditional sequential algorithm. The average speed-up ratio of the parallel algorithm could reach 15 in average. In addition, for both sequential and parallel algorithm, the time cost was approximately proportional to the number of mesh cells and facets, respectively. The test results are consistent with the theoretical analysis results. In the literature [30], a similar mesh generator is implemented. [PERSON], [PERSON], and [PERSON] implemented an open-source automatic mesh generator for finite-difference time-domain (FDTD) simulation with Matlab code.