A method having application for petroleum exploration or geological storage of generating a mesh of a faulted underground medium, comprising generating a hex-dominant mesh from faults and horizons in a form of a 3D triangulated surfaces. Each 3D triangulated surface is converted to a 2D triangulated surface onto which the faults are projected by an isometric unfolding technique. A regular two-dimensional grid pattern is generated for each 2D triangulated surface. The faults are accounted for by deforming quadrilaterals of the grid pattern intersected by projected faults. The deformed regular grid pattern is then converted to a 3D gridded surface and each quadrilateral which is crossed by a fault is converted into two triangles at a level of a diagonal. Finally, after iterating for all the 3D triangulated surfaces, the mesh is generated by creating links between the nodes of neighboring three-dimensional gridded surfaces with respect to the faults.