Usually a navigation mesh will be a different mesh from the geometry that is used to render the ground. There are a couple of reasons. First, the idea is that the nav mesh would be simpler, e.g., fewer vertices and triangles, so that operations that use it, such as ray tracing to find the ground height and path finding operations, can run much faster than if you used a ground mesh that had more detail. It won't be the case for every game that the ground mesh needs more detail, but it can be. Another reason for having a separate navigation mesh is that you may not want the character to be able to walk everywhere on the ground. By making a different navigation mesh, you can limit the walkable area, to keep the character within the main gameplay areas.

As for cutting a navigation mesh...it can be tricky to automatically generate navigation meshes. The techniques for doing this include polygon clipping and Boolean set operations. It can be done with BSP trees or other approaches. I would say that in a typical game production pipeline, navigation meshes are probably usually custom built by an artist. An artist might use the ground mesh as a starting point, making a copy to be the nav mesh, then use tools inside a digital content creation (DCC) tool such as 3ds max or Maya to trim the nav mesh copy appropriately.

Note that if you do automatically generate your nav meshes by trimming a ground mesh against a wall, now you have the possibility that your character can walk directly into a wall (unless you have another collision response operation also), while if you manually created the nav mesh you could trim it somewhat away from the wall to prevent the character from walking into the wall without doing a separate character/wall collision response procedure.

I hope that helps!

You should also note that depending on how your navmesh code is written, there may be other limitations to the mesh that dictate a custom drawn mesh, or even several seperate meshes that overlap where they connect.
Since some navmesh stuff is just a lookup table with n^2 entries for n triangles, you need to keep your meshes small or else have a huge memory footprint. And the way that table is created means that you can't have any internal verticies in the mesh.

I think one of the earlier AI Wisdom books may have had more coverage of navigation meshes. If I recall correctly, the first book may have had a fairly comprehensive example, though I can't vouch for the quality of the technique or code.

Actually, it was Greg Snook's article on navigation meshes in the original Game Programming Gems that I was thinking about, not the earlier AI Wisdom books.

If you have a separate mesh for your ground geometry, then here is an approach I would suggest might be workable:

*** Part 1 - Find contours of world geometry ***

for each item in the world other than the ground plane{  // Project points into xy plane, creating a 2D point  // cloud.  add each vertex into an array of 2D points, setting Z = 0  // determine a convex shape that approximates the item's  // projection shape on the ground  find convex contour of the 2D point cloud using any  convenient technique  // cleanup contour and add to array of contours  weld points together to make sure the contour is a single  closed loop of line segments  // optionally increase size of the contours to push  // nav mesh away from geometry. here's an easy way.  find centroid of all points that make up the contour.  scale all the points about the centroid by some uniform  scale factor x that is greater than 1.0.}

*** Part 2 - Cut holes in the ground mesh ***

make a copy of the ground mesh, but disconnect the triangles
so you have 3 unique vertices per triangle....this "triangle
soup" approach is not fully optimal for performance or memory
but can make things quite a bit easier to code.

for each contour above{  Mark all the triangles as unvisited, e.g., assign a flag = false  on a per triangle basis.  For each triangle in the ground mesh copy  {    if visited = true, skip the triangle,    else    {      if the triangle doesn't overlap the contour      {        mark the triangle as visited = true      }      else      {        clip the triangle against the convex contour using        (for example) the Sutherland-Hodgeman algorithm. But        remember that you want to keep the part that is        outside the contour, not inside... The result        may not be a triangle, and in fact a given triangle        could be completely clipped away or could be cut into        two independent pieces.        When you do the clip, you'll compute the clip points        in 2D (xy plane), but when inserting new vertices        remember to compute the z coordinate as well, since        you'll need the z point in your final clipped nav        ground mesh.        triangulate the clipped result, marking each        new triangle visited = true, and adding all        new triangles into the copied mesh        delete the original, unclipped triangle from        the list      }    }  }}Once you've clipped the copied mesh against all contours,change the connectivity of the mesh so that all coincidentvertices are welded together, e.g., rebuild the indexedmesh out of triangle soup. And you're done!

Now, you could do something fancier...instead of making
a triangle soup and then rebuilding an indexed mesh in the
end, use a winged-edge data structure (WEDS) to cut holes
directly in the indexed mesh. But coding that will be
quite a bit more difficult.

If you have multiple ground geometries that overlap, you'll
have to deal with that somehow, and you could do it by
adding logic to handle locomotion transitions from one nav
mesh to another, or by clipping one against the other and
welding them together into one....anyway, something to
consider.

Hope this helps!