Document Open Access Logo

The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation

Authors Wouter van Toll, Atlas F. Cook IV, Marc van Kreveld, Roland Geraerts



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.70.pdf
  • Filesize: 0.57 MB
  • 5 pages

Document Identifiers

Author Details

Wouter van Toll
Atlas F. Cook IV
Marc van Kreveld
Roland Geraerts

Cite AsGet BibTex

Wouter van Toll, Atlas F. Cook IV, Marc van Kreveld, and Roland Geraerts. The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 70:1-70:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.70

Abstract

We describe and demonstrate the Explicit Corridor Map (ECM), a navigation mesh for path planning and crowd simulation in virtual environments. For a bounded 2D environment with polygonal obstacles, the ECM is the medial axis of the free space annotated with nearest-obstacle information. It can be used to compute short and smooth paths for disk-shaped characters of any radius. It is also well-defined for multi-layered 3D environments that consist of connected planar layers. We highlight various operations on the ECM, such as dynamic updates, visibility queries, and the computation of paths (indicative routes). We have implemented the ECM as the basis of a real-time crowd simulation framework with path following and collision avoidance. Our implementation has been successfully used to simulate real-life events involving large crowds of heterogeneous characters. The enclosed demo application displays various features of our software.
Keywords
  • Medial axis
  • Navigation mesh
  • Path planning
  • Crowd simulation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. R. Geraerts. Planning short paths with clearance using Explicit Corridors. In Proceedings of the IEEE International Conference on Robotics and Automation, pages 1997-2004, 2010. Google Scholar
  2. P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968. Google Scholar
  3. M. Held. VRONI and ArcVRONI: Software for and applications of Voronoi diagrams in science and engineering. In Proceedings of the 8th International Symposium on Voronoi Diagrams in Science and Engineering, pages 3-12, 2011. Google Scholar
  4. K.E. Hoff III, T. Culver, J. Keyser, M. Lin, and D. Manocha. Fast computation of generalized Voronoi diagrams using graphics hardware. International Conference on Computer Graphics and Interactive Techniques, pages 277-286, 1999. Google Scholar
  5. D.T. Lee and R.L. Drysdale III. Generalization of Voronoi diagrams in the plane. SIAM Journal on Computing, 10(1):73-87, 1981. Google Scholar
  6. F. Preparata. The medial axis of a simple polygon. In Mathematical Foundations of Computer Science, volume 53, pages 443-450. Springer, 1977. Google Scholar
  7. W. van Toll, N. Jaklin, and R. Geraerts. Towards believable crowds: A generic multi-level framework for agent navigation. In ASCI.OPEN, 2015. Google Scholar
  8. W.G. van Toll, A.F. Cook IV, and R. Geraerts. Navigation meshes for realistic multi-layered environments. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3526-3532, 2011. Google Scholar
  9. W.G. van Toll, A.F. Cook IV, and R. Geraerts. A navigation mesh for dynamic environments. Computer Animation and Virtual Worlds, 23(6):535-546, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail