Navmesh Generation
It's always recast
The navigation mesh can be generated automatically from the geometry in the game.
Surface Merging
Take all the surfaces that is walkable and simplify them as far as possible by merging them with each other to convex polygons. Cull away the really small nodes and then take all things that block out the navmesh. Subdivide all polygons it covers, remove the ones below them and then merge the navmesh polygons again.
Generating 2D Navmeshes - 2014
Fredrik Farnstrom, Improving on Near-Optimality: More Techniques for Building Navigation Meshes. AIGPW3 p113-p128. - 2006.
Paul Tozour, Building a near-optimal navigation mesh, AIGPW1 p171-p185. - 2002.
Voxelization
This system takes all the walkable and blocking surfaces and sample them to voxels. Then these voxels are used to calculate walkable areas and turn them into navmesh polygons. One common lib for this is Recast and a description of how it works can be found at the NMGen Study homepage.
Reference
Unreal 3: Navigation Mesh Reference
Automatic Navigation Mesh Generation in Configuration Space - 2013
Improving on Near-Optimality: More Techniques for Building Navigation Meshes, AIGPW3 p112-128. - 2006.