Shortest Paths with Arbitrary Clearance from Navigation Meshes

Loading...
Thumbnail Image
Date
2010
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
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.
Description

        
@inproceedings{
10.2312:SCA/SCA10/159-168
, booktitle = {
Eurographics/ ACM SIGGRAPH Symposium on Computer Animation
}, editor = {
MZoran Popovic and Miguel Otaduy
}, title = {{
Shortest Paths with Arbitrary Clearance from Navigation Meshes
}}, author = {
Kallmann, Marcelo
}, year = {
2010
}, publisher = {
The Eurographics Association
}, ISSN = {
1727-5288
}, ISBN = {
978-3-905674-27-9
}, DOI = {
10.2312/SCA/SCA10/159-168
} }
Citation