Open problem

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:

  • W. Thurston (wpt@math.berkeley.edu) has proved existence of a solution (posting to sci.math., 25. Oct. 1993).

  • In his paper Scott Mitchell gives another existence proof.

  • David Eppstein gave an algorithm for linear complexity hexahedral mesh generation.

  • Carlos Carbonera of SDRC has found a solution that is not combinatorically valid (it has elements sharing more than one face). It can be transformed into a valid one by using Scott Mitchell's ideas.

  • 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.


    Robert Schneiders