In this paper we introduce a novel automatic method for generating near optimal navigation meshes from a 3D multi-layered virtual environments. Firstly, a GPU voxelization of the entire scene is calculated in order to identify and extract the different walkable layers. Secondly, a high resolution render is performed with a fragment shader to obtain the 2D floor plan of each layer. Finally, a convex decomposition of each layer is calculated and layers are linked in order to create a Navigation Mesh of the scene. Results show that our method is not only faster than the previous work, but also creates more accurate NavMeshes since it respects the original shape of the static geometry. It also provides a significantly lower number of cells and avoids ill-conditioned cells and T-joints between portals that could to unnatural character navigation.