ABSTRACT
The design and implementation of new techniques for navigation meshes can play a significant role in the navigation capabilities of agents populating modern virtual worlds. This chapter reviews the main approaches used to compute flexible and efficient navigation meshes for three-dimensional (3D) virtual worlds, and discusses the use of local clearance triangulations (LCTs) as the underlying cell decomposition representing the navigable surfaces in a virtual environment.
