Particle host cell determination in unstructured grids

An algorithm has been developed to efficiently determine the correct particle host cell for unstructured grids with multiple element types (e.g. tetrahedrons, prisms, hexahedrons, etc.) and large particle movements (e.g. movement across single or multiple cells). The algorithm utilizes a dot product searching technique where a direction vector connecting a face centroid and the particle location is dotted with an outwardly-positive face normal to facilitate the host cell search. The algorithm is investigated for particles moving a distance of one or several cell lengths on a variety of two-dimensional (2-D) and three-dimensional (3-D) meshes. Two variations of this approach are introduced and tested, each focusing on different strategies (cell-searching vs. face-searching minimization) to optimize the use of computational resources. Finally, in order to increase the efficiency of each algorithm in the case of large problems where the previous host cell is not known, a coarse-grain search is introduced, whereby a small sampling of the total cells are inspected, after which the adjoining-faces search is completed in the host sub-domain. (C) 2008 Elsevier Ltd. All rights reserved.