Adaptive and Quality Quadrilateral/Hexahedral Meshing from Volumetric Data

Yongjie Zhang, Chandrajit Bajaj


The Center for Computational Visualization (CCV)
Institute for Computational Engineering and Sciences & Dept. of Computer Sciences
The University of Texas at Austin

This paper describes an algorithm to extract adaptive and quality quadrilateral/hexahedral meshes directly from volumetric data. First, a bottom-up surface topology preserving octree-based algorithm is applied to select a starting octree level. Then the dual contouring method is used to extract a preliminary uniform quad/hex mesh, which is decomposed into finer quads/hexes adaptively without introducing any hanging nodes. The positions of all boundary vertices are recalculated to approximate the boundary surface more accurately. Mesh adaptivity can be controlled by a feature sensitive error function, the regions that users are interested in, or finite element calculation results. Finally, a relaxation based technique is deployed to improve mesh quality. Several demonstration examples are provided from a wide variety of application domains. Some extracted meshes have been extensively used in finite element simulations.

Paper Download

Adaptive and Quality Quadrilateral/Hexahedral Meshing from Volumetric Data (pdf) (ps), Proceedings of 13th International Meshing Roundtable, pp. 365-376. Willamsburg, VA. September 19-22, 2004.

A journal version of this paper (pdf) has been accepted in Computer Methods in Applied Mechanics and Engineering (CMAME), 2005.

Related Links

  • Tetrahedral Mesh Generation


    Results

    (Each image is linked to a higher resolution image.)

    1. Adaptive quadrilateral and hexahedral meshes of a biomolecule mAChE.


    (a) - the quadrilateral mesh of the molecular surface; (b) - the wireframe of the adaptive quadrilateral mesh of the molecular surface; (c) - the adaptive hexahedral mesh of the interior volume; (d) - the adaptive hexahedral mesh of the exterior volume between the molecular surface and an outer sphere. Finer meshes are generated in the region of the cavity, while coarser meshes are kept in other areas. The cavity is shown in the red boxes.


    2. Quadrilateral and hexahedral meshes of the human head.


    (a) - an adaptive quadrilateral mesh; (b) - the uniform hexahedral mesh at a chosen starting level; (c) - an adaptive interior hexahedral mesh controlled by the feature sensitive error function; (d) - an adaptive exterior hexahedral mesh controlled by the feature sensitive error function.


    3. Quadrilateral and hexahedral meshes of the knee.


    (a) - an adaptive quadrilateral mesh; (b) - the uniform hexahedral mesh at a chosen starting level; (c) - an adaptive hex mesh controlled by the feature sensitive error function; (d) - all the hexahedral elements are refined.


    4. Quadrilateral and hexahedral meshes are extracted from a CT-scanned volumetric data (UNC head).


    (a) - the quadrilateral mesh of the skin; (b) - the hexahedral mesh of the volume inside the skin; (c) - the quadrilateral mesh of the skull isosurface; (d) - the hexahedral mesh of the skull.


    5. Quadrilateral meshes of a bubble model.


    (a) - the uniform mesh at a chosen starting level; (b) - an adaptive mesh controlled by finite element solutions (deformation); (c) - a mesh generated by refining all the boundary elements.


    6. Sharp features are preserved.


    From left to right: an adaptive quad mesh of a mechanical part; an adaptive hex mesh of a mechanical part; an adaptive quad mesh of a fandisk, an adaptive hex mesh of a fandisk.