carrier image

High Quality Quadrilateral Surface Meshing Without Template Restrictions: A New Approach Based on Network Flow Techniques

Muller-Hannemann, Matthias

Proceedings, 6th International Meshing Roundtable, Sandia National Laboratories, pp.293-307, October 1997


Technische Universitat Berlin

We investigate the following mesh refinement problem: Given a mesh of polygons in three-dimensional space, find a decomposition into strictly convex quadrilaterals such that the resulting mesh is conforming and satisfies prescribed local density constraints.

We show that this problem can efficiently be solved by a reduction to a minimum cost bidirected flow problem, if the mesh does not contain branching edges, that is, edges incident to more than two polygons. This approach handles optimization criteria such as density, angles and regularity, too. For meshes with branchings, the problem is feasible if and only if a certain system of linear equations over GF(2) has a solution. To enhance the mesh quality for meshes with branchings, we introduce a two-stage approach which first decomposes the whole mesh into components without branchings, and then uses minimum cost bidirected flows on the components in a second phase. We report on our computational results which indicate that this approach usually leads to a very high mesh quality.

Download Full Paper (PDF)

Contact author(s) or publisher for availability and copyright information on above referenced article