The surface of a hexahedral element mesh is a mesh of quadrilateral faces; it is an easy task to derive this mesh from a hex mesh. This does not hold for the inverse problem: given a mesh of quadrilateral faces (polyhedron), does there exist a mesh of hexahedral elements whose surface matches the prespecified surface exactly?
The next picture shows an example for which it is very difficult to find a hex mesh:
Recently the problem has found some attention:
The mesh given by Carlos Carbonera has degenerated elements, and the problem whether one can always find a mesh of non-degenerated elements that matches a given quadrilateral surface mesh is still open.
Can one give an algorithm that constructs a valid mesh from a surface discretization? The solution of this problem would have enormous impact; the CUBIT team is working in this direction.
Scott Mitchell's presentation on the technical history of hexahedral mesh generation includes a good review of the problem and it's various solutions.