An original approach to the partitioning of 3D meshes (typically for the finite element method) is presented. Our technique applies on sub-domains defined by their polyhedrical boundary. It relies on the meshing of interfaces between sub-domains before meshing the domain itself. Since this idea basically trades smoothness, small-size, and regularity of the interfaces for unbalance, we describe a fast, efficient, linear-time evaluation algorithm that corrects this default. Its use is experienced with industrial benchmarks, and compared with other heuristic schemes.