Optimal Path Maps on the GPU

We introduce a new method for computing optimal path maps on the GPU using OpenGL shaders. Our method explores GPU rasterization as a way to propagate optimal costs on a polygonal 2D environment, producing optimal path maps which can efficiently be queried at run-time. Our method is implemented entirely with GPU shaders, does not require pre-computation, addresses optimal path maps with multiple points and line segments as sources, and introduces a new optimal path map concept not addressed before: maps with weights at vertices representing possible changes in traversal speed. The produced maps offer new capabilities not explored by previous navigation representations and at the same time address paths with global optimality, a characteristic which has been mostly neglected in animated virtual environments. The proposed path maps partition the input environment into the regions sharing a same parent point along the shortest path to the closest source, taking into account possible speed changes at vertices. The proposed approach is particularly suitable for the animation of multiple agents moving toward the entrances or exits of a virtual environment, a situation which is efficiently represented with the proposed path maps.