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.
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 AiGameDev.com 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).
ReferencesThe following references were collected by Mikko Mononen for his AiGameDev.com 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