# A Fast Particle-Locating Method for the Arbitrary Polyhedral Mesh
## 2 PLUG Method
### Mapping Relation Between Background Cells and Computational Cells
#### 2.2.1 Creating the _Cell2 cube_ List  
In this part, we describe the procedure to create the _cell2 cube_ list. An illustration of a such list is shown in Figure 2.  
In existing auxiliary grid methods, a minimum cuboid (bound box) encapsulating a computational cell is used to construct the mapping relation. As shown in Figure 3, the bound box of computational cell \(a\) is marked in grey. Using the boundary box, the cubes related to a cell are those which intersect with its boundary box. Since the background cubes are much smaller than the computational cells in the present study, boundary box method would introduce many useless cubes. For example, cube \(A\) in Figure 3 intersects with the boundary box of cell \(a\), whereas it doesn't intersect with cell \(a\). To improve the computational efficiency, a new method based on characteristic points is developed in this study. Figure 1: An illustration of different background grid configurations. (a) large-spacing grid; (b)small-spacing grid. The characteristic point method is developed to check the intersection of a tetrahedron and a cube. We first apply the tetrahedral decomposition on all polyhedral computational cells [15]. Then we use the characteristic point method to find all background cubes which are fully or partially covered by a certain tetrahedron. To create the _cell2 cube_ list, each component corresponding to \(C_{J}\) will be a union set of indices of background cubes fully or partially covered by several tetrahedrons decomposed from \(C_{J}\). Therefore, the procedure described hereafter can be applied on the arbitrary polyhedral mesh. In order to find all the background cubes covered by a given tetrahedron, several characteristic points are defined for the tetrahedron. As shown Figure 4, two types of the characteristic points are adopted in this study, i.e., the interior points shown in panel (a) and the boundary points shown in panel (b). Within each tetrahedron (panel (a) of Figure 4), the characteristic points are the centroid (point \(O\)) and the centers of lines \(\overline{OA}\), \(\overline{OB}\), \(\overline{OC}\), and \(\overline{OD}\). On each boundary surface (triangle \(ABC\) in panel (b) of Figure 2), the characteristic points are the centroid (point \(O^{\prime}\)), the centers of edges \(\overline{AB}\), \(\overline{BC}\), and \(\overline{CA}\), and the centers of the lines \(\overline{O^{\prime}A}\), \(\overline{O^{\prime}B}\), and \(\overline{O^{\prime}C}\). Figure 3: Overlap relation determination in existing auxiliary grid method. Figure 2: An illustration of the _cell2 cube_ list. In this study, we adopt the background cubes containing the characteristic points and their neighbors as the background cubes fully or partially covered by the tetrahedron. The neighbors of a given background cube are defined as those background cubes that share at least one vertex with it. Apparently, if a tetrahedron is small enough compared with the background cube, the background cubes found using this rule will completely cover this tetrahedron. For a tetrahedron far larger than the background cube, a subdivision will be applied, as shown in Figure 5. Panel (a) shows the original tetrahedron, and panel (b) shows the initial subdivision. The black points in the figure are the centers of the boundary edges. It should be noted that, after initial subdivision, four tetrahedrons and an octahedron are formed. The octahedron is given in panel (c). This octahedron is further decomposed into four tetrahedrons through a line passing through its two opposite vertices, as shown in panel (d). After a subdivision, the above searching scheme will be conducted again to find the background cubes fully or partially covered by the computational cells. For a certain computational cell, searching is completed if no new background cube is found. Otherwise, the subdivision will continue until no new background cube is found to have intersection with corresponding computational cells.