How to generate a navmesh from a set of 3D meshes from scratch

I’ve found a great article on how to build a constrained delaunay triangulation that can be used to create a simple navmesh from cutout geometry. However, this does not seem sufficient to generate a high quality navmesh from any arbitrary set of level geometry from scratch.

One of the problems is that it only deals with triangles in XZ space. But how should I handle situations where an arbitrary 3D mesh is intersecting another arbitrary 3D mesh? Within their intersection, each triangle would need to retriangulated in some way.