Computing High Resolution Explicit Corridor Maps using Parallel Technologies

Abstract

This work investigates the approximated construction of Explicit Corridor Maps (ECMs). An ECM is a type of Navigation Mesh: a geometrical structure describing the walkable space of an environment that is used to speed-up the path-finding and crowdsimulation operations occurring in the environment. Additional geometrical routines that take advantage of the GPGPU model are presented, which improve the current construction method by increasing the number of computations performed on the GPU and reducing the amount of data transferred back to the CPU. At the same time, a multi-tiled construction approach is presented, which almost frees the geometrical computation from its current main constraint, resolution, allowing high-resolution ECMs to be produced; moreover, we show that this approach can benefit optimally from CPU-parallelism. Both a GPGPU-aided and a CPU-parallel implementation are tested: experiments show that high-resolution ECMs can be computed, and that the new implementations often outperform the original one.