Insider Presentation

Building and Traversing Navigation Meshes with Recast and Detour (Project Video)

Alex J. Champandard on May 12, 2009

Over the past couple years, Mikko Mononen has been working on a personal R&D project for automatically generating navigation meshes based on a polygon soup. Mikko worked on Crysis as a Lead AI Programmer and recently started in the same role at Recoil Games, although he has a demomaking background and experience with independent games too. His project was born out of a need for better data for pathfinding; navigation meshes can never be good enough!

Mikko experimented with a variety of different techniques based on rasterization and voxelization, which treat space as a discrete grid and post-process these voxels to retrieve polygons on the output. This approach is one of the most promising for generating robust and reliable navigation meshes, and research projects and commercial solutions are increasingly relying on this approach too. (See the 11 references below, including papers, books and articles available publicly.)

In the following 11:30 minute HD video, you'll get a guided tour of the navigation generation (known as Recast) as well as a demo of the runtime pathfinding and navigation queries (called Detour). You'll get an idea of how this kind of technology works, as well as a demonstration of how it works on a variety of indoor and outdoor levels.

Video Screencast

IMPORTANT: You can get immediate access to the code and executable by joining here as a Premium Member. You have until Tomorrow (Wednesday 13th) for the launch week bonuses.

Mikko is one of the "Founding Experts" (as we call them) that help make Premium what it is today, and since his project reached version 1.0 recently he make it available to our Members. The project is called Recast and since then, version 1.1 is out, which includes pathfinding and navigation queries with Detour (also available to Premium Members).


The following references were collected by Mikko Mononen for his masterclass he held on the subject earlier this year.
Conservative Voxelization
Long Zhang, Wei Chen, David S. Ebert, Qunsheng Peng
Download PDF
Real-time Voxelization for Complex Polygonal Models
Zhao Dong, Wei Chen, Hujun Bao, Hongxin Zhang, Qunsheng Peng
Download PDF
Single-pass GPU Solid Voxelization and Applications
Elmar Eisemann, Xavier Décoret
Download PDF
GPU Gems 2: Flow Simulation with Complex Boundaries
Wei Li, Zhe Fan, Xiaoming Wei, Arie Kaufman
Download here 
GPU Gems 3: Real-Time Simulation and
Rendering of 3D Fluids
Keenan Crane, Ignacio Llamas, Sarah Tariq
Download PDF
Way-Finder: guided tours through complex walkthrough models
C. Andújar, P. Vázquez, M. Fairén
Download PDF
Volumetric Cell-and-Portal Generation
Denis Haumont, Olivier Debeir, François Sillion
Download here 
Skeleton Extraction of 3D Objects with Visible Repulsive Force
Fu-Che Wu, Wan-Chun Ma, Ping-Chou Liou, Rung-Huei Liang, Ming Ouhyoung
Download here 
Automated Static and Dynamic Obstacle Avoidance in Arbitrary 3D Polygonal Worlds
Edited by Xing-Jian Jing
Download here 
A Navigation Graph for Real-time Crowd Animation on Multilayered and Uneven Terrain
Julien Pettré, Jean-Paul Laumond, Daniel Thalmann
Download PDF
Pedestrian Reactive Navigation for Crowd Simulation: a Predictive Approach
Sébastien Paris, Julien Pettré, Stéphane Donikian
Download PDF

Discussion 0 Comments

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!