To reduce execution time for large problems with shading, a grid tracing shading algorithm may be implemented. The geometry is divided into a series of grid cells, resulting in rectangles and rectangular parallelepipeds for the 2-D and 3-D geometries, respectively. The particle is traced from grid cell to grid cell, and the search is done within each grid cell over only those surfaces which exist either wholly or partly within that cell. The situation is depicted in Figure 6 for a 2-D geometry. This algorithm has resulted in reductions in execution time for 2-D Cartesian enclosures of factors of 2 to factors of 20, with factors of 5 to 7 being typical. For 3-D enclosures, due to the higher overhead incurred in tracing through a 3-D grid, reductions in execution time of factors of 2 to factors of 4 are typical.
We have stated in section 2.4 that the surface search loop, which consumes the majority of the execution time, scales as . However, implementing grid tracing causes the surface search loop to scale as , thereby enabling much larger problems to be simulated. The optimum grid differs from problem to problem, and must be empirically determined by the user. However, good starting guesses are about 100 total grid cells (about in two dimensions and in three dimensions).
Figure 6: Illustration of the Grid Shading Algorithm.
The grid must be regular (i.e., all vertices must match up), but it need not be uniform. Our implementations have also required that the grid divisions be at constant X, Y or Z. If the surfaces of the geometry are concentrated in one region of space, then one can define a higher concentration of grids in that region. Note that, we have not vectorized this approach, as there are a variable number of surfaces within each grid, which renders the structure of the algorithm a bit more difficult to handle, as some particles will be absorbed, others will require to be moved to other cells, while still others will have surfaces in their cells remaining to be searched. However, this should be able to be well modelled on an MIMD architecture.