Computing Exact Arbitrary Clearance for Navigation Meshes


Character navigation in virtual environments is mostly handled by a combination of path planning with local movement algorithms. Clearance should be taken into consideration when choosing a path, but also when deciding the location of way points within portals. Previous work has considered clearance for path planning, but it is ignored when assigning way points within portals. Paths with clearance, do not necessarily guarantee that characters can walk through collision-free way points in portals. In this work we present a method for calculating clearance in navigation meshes (NavMeshes) consisting of convex cells of any type, as well as a novel method to calculate portals with clearance. We also introduce a new method to dynamically locate attractors over portals based on current trajectory, destination, and clearance.


Computing Exact Arbitrary Clearance for Navigation Meshes from Ramon Oliva on Vimeo.