research-article

Shortest paths with arbitrary clearance from navigation meshes

Author:

Marcelo KallmannAuthors Info & Claims

SCA '10: Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

Pages 159 - 168

Published: 02 July 2010 Publication History

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.

References

[1]

{BLM08} Berg J., Lin M., Manocha D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In ICRA'08: Proceedings of the International Conference on Robotics and Automation (2008). 2

[2]

{Cha82} Chazelle B.: A theorem on polygon cutting with applications. In SFCS '82: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (1982), IEEE Computer Society, pp. 339--349. 7

Digital Library

[3]

{Che85} Chew L. P.: Planning the shortest path for a disc in o(n²logn) time. In SCG '85: Proceedings of the first annual symposium on computational geometry (1985). 2

Digital Library

[4]

{DBCvK08} De Berg M., Cheong O., van Kreveld M.: Computational geometry: algorithms and applications. Springer, 2008. 2

Digital Library

[5]

{FS98} Fiorini L. P., Shiller Z.: Motion planning in dynamic environments using velocity obstacles. International Journal of Robotics Research 17, 7 (1998), 760--772. 2

[6]

{Ger10} Geraerts R.: Planning short paths with clearance using explicit corridors. In ICRA'10: Proceedings of the IEEE International Conference on Robotics and Automation (2010). 2

[7]

{GO07} Geraerts R., Overmars M. H.: The corridor map method: a general framework for real-time high-quality path planning: Research articles. Computer Animation and Virtual Worlds 18, 2 (2007), 107--119. 2

Digital Library

[8]

{GSA*09} Gayle R., Sud A., Andersen E., Guy S. J., Lin M. C., Manocha D.: Interactive navigation of heterogeneous agents using adaptive roadmaps. IEEE Transactions on Visualization and Computer Graphics 15 (2009), 34--48. 2

Digital Library

[9]

{HCK*00} Hoff III K. E., Culver T., Keyser J., Lin M., Manocha D.: Fast computation of generalized voronoi diagrams using graphics hardware. In Proceedings of the sixteenth annual symposium on computational geometry (2000). 2

Digital Library

[10]

{HNR07} Hart P. E., Nilsson N. J., Raphael B.: A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics, IEEE Transactions on 4, 2 (February 2007), 100--107. 2

[11]

{HS94} Hershberger J., Snoeyink J.: Computing minimum length paths of a given homotopy class. Computational Geometry Theory and Application 4, 2 (1994), 63--97. 3, 7

Digital Library

[12]

{HS97} Hershberger J., Suri S.: An optimal algorithm for euclidean shortest paths in the plane. SIAM Journal on Computing 28 (1997), 2215--2256. 2

Digital Library

[13]

{KBT03} Kallmann M., Bieri H., Thalmann D.: Fully dynamic constrained delaunay triangulations. In Geometric Modeling for Scientific Visualization, Brunnett G., Hamann B., Mueller H., Linsen L., (Eds.). Springer-Verlag, Heidelberg, Germany, 2003, pp. 241--257. ISBN 3-540-40116-4. 2, 3, 4, 6

[14]

{KL99} Kuffner J. J., Latombe J.-C.: Fast synthetic vision, memory, and learning models for virtual humans. In CA'99: Proceedings of Computer Animation (1999), IEEE. 2

Digital Library

[15]

{LA95} Liu Y. H., Arimoto S.: Finding the shortest path of a disk among polygonal obstacles using a radius-independent graph. IEEE Transactions on Robotics and Automation 11, 5 (1995), 682--691. 2

[16]

{Lat90} Latombe J.-C.: Robot Motion Planning. Kluwer Academic Publisher, December 1990. 2

Digital Library

[17]

{LaV06} LaValle S. M.: Planning Algorithms. Cambridge University Press (available on-line), 2006. 2

Digital Library

[18]

{LD04} Lamarche F., Donikian S.: Crowd of virtual humans: a new approach for real time navigation in complex and structured environments. Computer Graphics Forum 23, 3 (2004), 509--518. 2

[19]

{LP84} Lee D. T., Preparata F. P.: Euclidean shortest paths in the presence of rectilinear barriers. Networks 3, 14 (1984), 393--410. 7

[20]

{LPW79} Lozano-Pérez T., Wesley M. A.: An algorithm for planning collision-free paths among polyhedral obstacles. Communications of ACM 22, 10 (1979), 560--570. 2

Digital Library

[21]

{MH03} Metoyer R. A., Hodgins J. K.: Reactive pedestrian path following from examples. In CASA '03: Proceedings of the 16th International Conference on Computer Animation and Social Agents (2003), IEEE Computer Society. 1, 2

Digital Library

[22]

{Mit93} Mitchell J. S. B.: Shortest paths among obstacles in the plane. In SCG '93: Proceedings of the ninth annual symposium on computational geometry (New York, NY, USA, 1993), ACM, pp. 308--317. 2, 7

Digital Library

[23]

{NT95} Noser H., Thalmann D.: Synthetic vision and audition for digital actors. In Proc. of Eurographics (1995). 2

[24]

{OW88} Overmars M. H., Welzl E.: New methods for computing visibility graphs. In SCG '88: Proceedings of the fourth annual symposium on Computational geometry (1988), ACM, pp. 164--171. 2

Digital Library

[25]

{Rey99} Reynolds C.: Steering behaviors for autonomous characters. In GDC'99: Game Developers Conference (1999). 1, 2

[26]

{SAC*08} Sud A., Andersen E., Curtis S., Lin M. C., Manocha D.: Real-time path planning in dynamic virtual environments using multiagent navigation graphs. IEEE Transactions on Visualization and Computer Graphics 14 (2008), 526--538. 2

Digital Library

[27]

{SR94} Storer J. A., Reif J. H.: Shortest paths in the plane with polygonal obstacles. J. ACM 41, 5 (1994), 982--1012. 2

Digital Library

[28]

{ST07} Shao W., Terzopoulos D.: Autonomous pedestrians. Graphical Models 69, 5--6 (2007), 246--274. 1, 2

Digital Library

Cited By

Kallmann MKapadia M(2016)Geometric and discrete path planning for interactive virtual worldsACM SIGGRAPH 2016 Courses10.1145/2897826.2927310(1-29)Online publication date: 24-Jul-2016
https://dl.acm.org/doi/10.1145/2897826.2927310
Berseth GKapadia MFaloutsos P(2016)ACCLMeshComputer Animation and Virtual Worlds10.1002/cav.171027:3-4(195-204)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1002/cav.1710
Berseth GKapadia MFaloutsos P(2015)ACCLMeshProceedings of the 8th ACM SIGGRAPH Conference on Motion in Games10.1145/2822013.2822043(97-102)Online publication date: 16-Nov-2015
https://dl.acm.org/doi/10.1145/2822013.2822043
Show More Cited By

Index Terms

Shortest paths with arbitrary clearance from navigation meshes
1. Computing methodologies
  1. Computer graphics
    1. Animation

Recommendations

On Approximating Shortest Paths in Weighted Triangular Tessellations
WALCOM: Algorithms and Computation
Abstract
We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types ... $_{}$ $_{}$ $_{}$ $\frac{_{}}{_{}}$ $\frac{_{}}{_{}}$ $\frac{_{}}{_{}}$
$\frac{_{}}{_{}} \frac{}{\sqrt{}}$
Progressive compression of arbitrary triangular meshes
VIS '99: Proceedings of the conference on Visualization '99: celebrating ten years

In this paper we present a mesh compression method based on a multiresolution decomposition whose detail coefficients have a compact representation and thus smaller entropy than the original mesh. Given an arbitrary triangular mesh with an irregular ...
Subdivision tree based multiresolution representation of arbitrary triangle meshes

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '10: Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

July 2010

256 pages

Conference Chairs:
François Faure
Grenoble University, INRIA, LJK-CNRS
,
Caroline Larboulette
Universidad Rey Juan Carlos, Madrid
,
Program Chairs:
Zoran Popović
University of Washington
,
Miguel Otaduy
Universidad Rey Juan Carlos, Madrid

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 02 July 2010

Check for updates

Qualifiers

Research-article

Conference

SCA '10

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA '10: The ACM SIGGRAPH / Eurographics Symposium on Computer Animation 2010

July 2 - 4, 2010

Madrid, Spain

Acceptance Rates

SCA '10 Paper Acceptance Rate 24 of 56 submissions, 43%;

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
270
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kallmann MKapadia M(2016)Geometric and discrete path planning for interactive virtual worldsACM SIGGRAPH 2016 Courses10.1145/2897826.2927310(1-29)Online publication date: 24-Jul-2016
https://dl.acm.org/doi/10.1145/2897826.2927310
Berseth GKapadia MFaloutsos P(2016)ACCLMeshComputer Animation and Virtual Worlds10.1002/cav.171027:3-4(195-204)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1002/cav.1710
Berseth GKapadia MFaloutsos P(2015)ACCLMeshProceedings of the 8th ACM SIGGRAPH Conference on Motion in Games10.1145/2822013.2822043(97-102)Online publication date: 16-Nov-2015
https://dl.acm.org/doi/10.1145/2822013.2822043
Jaklin NKremyzas AGeraerts RZhao QThalmann DWu ELin MWang L(2015)Adding sociality to virtual pedestrian groupsProceedings of the 21st ACM Symposium on Virtual Reality Software and Technology10.1145/2821592.2821597(163-172)Online publication date: 13-Nov-2015
https://dl.acm.org/doi/10.1145/2821592.2821597
Bruneau JPettré JBarbič JDeng Z(2015)Energy-efficient mid-term strategies for collision avoidance in crowd simulationProceedings of the 14th ACM SIGGRAPH / Eurographics Symposium on Computer Animation10.1145/2786784.2786804(119-127)Online publication date: 7-Aug-2015
https://dl.acm.org/doi/10.1145/2786784.2786804
Oliva RPelechano N(2015)Clearance for diversity of agents' sizes in navigation meshesComputers and Graphics10.1016/j.cag.2014.11.00447:C(48-58)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1016/j.cag.2014.11.004
Ninomiya KKapadia MShoulson AGarcia FBadler N(2015)Planning approaches to constraint-aware navigation in dynamic environmentsComputer Animation and Virtual Worlds10.1002/cav.162226:2(119-139)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1002/cav.1622
Kallmann MKapadia M(2014)Navigation meshes and real-time dynamic planning for virtual worldsACM SIGGRAPH 2014 Courses10.1145/2614028.2615399(1-81)Online publication date: 27-Jul-2014
https://dl.acm.org/doi/10.1145/2614028.2615399
Kallmann M(2014)Dynamic and Robust Local Clearance TriangulationsACM Transactions on Graphics10.1145/258094733:5(1-17)Online publication date: 23-Sep-2014
https://dl.acm.org/doi/10.1145/2580947
Oliva RPelechano NMcDonnell RSturtevant NZordan V(2013)A Generalized Exact Arbitrary Clearance Technique for Navigation MeshesProceedings of Motion on Games10.1145/2522628.2522900(103-110)Online publication date: 6-Nov-2013
https://dl.acm.org/doi/10.1145/2522628.2522900
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents