We investigate a purely combinatorial approach to
the following mesh refinement problem: Given a coarse mesh of
polygons in three-dimensional space, find 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 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.
In our
model 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 polygons.
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.
