A parallel generator for sparse unstructured meshes to solve the eikonal equation

摘要

Mesh generation is the first step in a wide range of applications including navigation for robots or virtual agents in pedestrian simulations. To find the shortest travel time to a target, a common technique is to solve the eikonal equation on a mesh. We propose EikMesh, an extension of the DistMesh algorithm. EikMesh is a fast parallel mesh generator that reduces the number of mesh points, and thus the computation time, while maintaining precision of numerical solvers on the mesh. It automatically refines where desired, in our case, where the eikonal equation undergoes changes, e.g. near obstacles. The first crucial step is the generation of a sophisticated initial mesh which reduces the number of smoothing steps. In addition, EikMesh avoids expensive Delaunay-re-triangulations. Space filling curves manage storage space in a cache-friendly manner. EikMesh scales better than the parallelized traditional DistMesh and significantly outperforms it for a number of test cases. (C) 2018 Elsevier B.V. All rights reserved.