Home  Issues  About JGAA  Instructions for Authors 
Selected Papers from the 1998 Dagstuhl Seminar on Graph Algorithms and Applications
DOI: 10.7155/jgaa.00040
Shelling Hexahedral Complexes for Mesh Generation
Vol. 5, no. 5, pp. 5991, 2001. Regular paper.
Abstract We present a new approach for the generation of hexahedral finite element meshes for solid bodies in computeraided design. The key idea is to use a purely combinatorial method, namely a shelling process, to decompose a topological ball with a prescribed surface mesh into combinatorial cubes, socalled hexahedra. The shelling corresponds to a series of graph transformations on the surface mesh which is guided by the cycle structure of the combinatorial dual. Our method transforms the graph of the surface mesh iteratively by changing the dual cycle structure until we get the surface mesh of a single hexahedron. Starting with a single hexahedron and reversing the order of the graph transformations, each transformation step can be interpreted as adding one or more hexahedra to the so far created hex complex. Given an arbitrary solid body, we first decompose it into simpler subdomains equivalent to topological balls by adding virtual 2manifolds. Second, we determine a compatible quadrilateral surface mesh for all created subdomains. Then, in the main part we can use the shelling of topological balls to build up a hex complex for each subdomain independently. Finally, the combinatorial mesh(es) are embedded into the given solids and smoothed to improve quality.

Submitted: January 1999.
Revised: August 2000.
Revised: July 2001.

Journal Supporters
