Shortest Paths with Arbitrary Clearance from Navigation Meshes


Abstract:

This paper addresses the problem of efficiently computing optimal paths of arbitrary clearance from a polygonal representation of a given virtual environment. Key to the proposed method is a new type of triangulated navigation mesh, called a Local Clearance Triangulation, which enables the efficient and correct determination if a disc of arbitrary size can pass through any narrow passages of the mesh. The proposed approach uniquely balances speed of computation and optimality of paths by first computing high-quality locally shortest paths efficiently in optimal time. Only in case global optimality is needed, an extended search will gradually improve the current path (if not already the global optimal) until the globally shortest one is determined. The presented method represents the first solution correctly extracting shortest paths of arbitrary clearance directly from a triangulated environment.

Paper:

Shortest Paths with Arbitrary Clearance from Navigation Meshes
Marcelo Kallmann
Eurographics / SIGGRAPH Symposium on Computer Animation (SCA)
Madrid, Spain, 2010


Errata 1: In an attempt to simplify the text, it is mentioned that the proposed locally shortest paths are computed in optimal time. This statement is however not accurate sometimes as it does not distinguish the precomputation time from the query time. For instance the channel search procedure (Section 5) can be easilly modified to run in O(n) time using available linear time planar graph search techniques.

Errata 2: The disturbance definition in the paper is incomplete as it does not account for possible cases where v is not connected to c.

An extended version of this paper including new features, adding missing citations, and addressing the issues above is still under preparation...

Video:



(43.6 MB .mov)

Code:

The LCT implementation is now included in the tripath toolkit available here

Bibtex: 
  @inproceedings { kallmann10sca,
    author    = { Marcelo Kallmann },
    title     = { Shortest Paths with Arbitrary Clearance from Navigation Meshes },
    booktitle = { Proceedings of the Eurographics / SIGGRAPH Symposium on Computer Animation (SCA) },
    year      = { 2010 },
    location  = { Madrid, Spain }
  }


(for information on other projects, see our research and publications pages)