In order to build a navigation mesh, all Recast needs are the triangles that form the meshes that compose the map. So, to build the navmesh for terrain meshes, I had to triangulate the terrain. This was done using the iTerrainSystem mesh interface. Meshes of this type have a collection of cells (iTerrainCell objects), which are further divided into a finer grid. These cells have a method for querying the height of the grid at a specific point (iTerrainCell::GetHeight()).
Once I had the grid size and a way to query the height, triangulating the terrain was trivial. The only thing that may cause some confusion are the triangle indices, since the terrain cells don't use the default coordinate system.
Here are a few screenshots of the navigation meshes built for the terrainf map, from CrystalSpace:
|<< <||Current||> >>|