High quality quadrilateral surface meshing without template restrictions: A new approach based on network flow techniques

We investigate a purely combinatorial approach to the following mesh refine ment problem: Given a coarse mesh of polygons in three-dimensional space, f ind a decomposition into well-shaped quadrilaterals such that the resulting mesh is conforming and satisfies prescribed local density constraints. We present a new approach based on network flow techniques. In particular, we show that this problem can efficiently be solved by a reduction to a min imum cost bidirected flow problem, if the mesh does not contain branching e dges, that is, edges incident to more than two polygons. This approach hand les optimization criteria such as density, angles and regularity. In our mo del we get rid of restrictions on the set of feasible solutions imposed by templates. On the other hand, we still use advantages of general templates with respect to mesh quality for the individual refinement of the mesh poly gons. For meshes with branchings, the problem is feasible if and only if a certai n 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 whic h first decomposes the whole mesh into components without branchings, and t hen uses minimum cost bidirected Rows on the components in a second phase. We report on our computational results which indicate that this approach us ually leads to a very high mesh quality.