direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 668-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Improving the Surface Cycle Structure for Hexahedral Mesh Generation
appeared in Proceedings of the 16th Annual ACM Symposium on Computational Geometry 2000, Hong Kong, June 12-14, pp. 19-28, 2000
primary: 65M50 Mesh generation and refinement
secondary: 65D18 Computer graphics and computational geometry
hexahedral mesh generation, quadrilateral mesh generation, b-matching, non-selfintersecting cycles, recursive splitting
Several promising approaches for hexahedral mesh generation work as follows: Given a prescribed quadrilateral surface mesh they first build the combinatorial dual of the hexahedral mesh. This dual mesh is converted into the primal hexahedral mesh, and finally embedded and smoothed into the given domain. Two such approaches, the modified Whisker Weaving algorithm by Fowell and Mitchell, as well as a method proposed by the author, rely on an iterative elimination of certain dual cycles in the surface mesh. An intuitive interpretation of the latter method is that cycle eliminations correspond to complete sheets of hexahedra in the volume mesh.
Although these methods can be shown to work in principle, the quality of the generated meshes heavily relies on the dual cycle structure of the given surface mesh. In particular, it seems that difficulties in the hexahedral meshing process and pure mesh qualities are often due to self-intersecting dual cycles. Unfortunately, all previous work on quadrilateral surface mesh generation has focused on quality issues of the surface mesh alone but has disregarded its suitability for a high-quality extension to a three-dimensional mesh.
In this paper, we develop a new method to generate quadrilateral surface meshes without self-intersecting dual cycles. This method reuses previous b-matching problem formulations of the quadrilateral mesh refinement problem. The key insight is that the b-matching solution can be decomposed into a collection of simple cycles and paths of multiplicity two, and that these cycles and paths can be consistently embedded into the dual surface mesh.
A second tool uses recursive splitting of components into simpler subcomponents by insertion of internal two-manifolds. We show that such a two-manifold can be meshed with quadrilaterals such that the induced dual cycle structure of each subcomponent is free of self-intersections if the original component satisfies this property. First experiments indicate that the hexahedral mesh quality can greatly benefit from both methods proposed in this paper.
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe