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. His project was born out of a need for better data for pathfinding; navigation meshes can never be good enough! Previously, 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.
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 references below in the article.)
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.