Efficient host-element determination in convex polyhedral meshes using an adaptive patch-search algorithm

Abstract

Locating particles in dense, unstructured polyhedral meshes remains a critical performance bottleneck in high-fidelity physics simulations, including computational fluid dynamics and Monte Carlo neutron transport. To address this, we extend the Patch-Search method—originally limited to tetrahedral topologies—to enable efficient host-element determination in arbitrary convex polyhedral mesh geometries. We introduce an adaptive, multi-layered grid structure to drastically reduce the prohibitive memory requirements of the original algorithm, thereby eliminating the need for a uniform grid resolution constrained by the domain’s smallest geometric features. Performance comparisons against an optimised linear octree baseline are conducted by locating one billion points on unit-cell geometries typical of nuclear engineering applications with varying mesh element types and densities. Results demonstrate that the proposed method consistently accelerates host-element determination by 32–55%. Compared to the original Patch-Search implementation, our adaptive multi-layered approach achieves initialisation time and memory savings of 82% to 99% across all mesh cases tested, making it a robust and efficient alternative to tree-based acceleration structures for particle-tracking applications.

The authors' abstract, as published at the source. Journal of Computational Physics, 2026 · DOI ↗