Title:

``Quadrilateral Mesh Generation in Computer-Aided Design''

Author:

Date:

Source:

Abstract:

For many years the finite element method has been a fundamental numerical analysis technique in the engineering community. In the field of computer-aided design (CAD), engineers often model their workpieces first in form of a coarse mesh of convex polygons, so-called macro elements, in three-dimensional space which approximates the object's surface. However, in order to make a numerical analysis applicable, a suitable refinement of the coarse mesh is necessary.

A large amount of research has been done in the area of mesh refinement into triangles. However, we concentrate in this thesis on mesh refinement into quadrilaterals, as quadrilaterals are more appropriate in many applications for numerical reasons.

It has been a challenging, and also fascinating task to bring together knowledge, ideas, and experience from very different disciplines, namely from computer-aided design and numerical and structural analysis on the one hand, and from computational geometry, combinatorial optimization, algorithmic graph theory, and complexity theory on the other hand. The main objective of this thesis is to solve - as far as possible - the mesh refinement problem in theory and practice.

Originating from a concrete application, we describe the difficult modeling process, analyze the computational complexity of the mesh refinement problem in various forms, and develop a new algorithmic approach. For the first time, network flow and matching techniques are applied to a mesh refinement problem. Our experiments show that this approach usually leads to meshes with a very good quality.

Previous approaches have suffered from restrictions imposed by so-called templates, which are patterns to decompose single macro elements. By a generalization of the set of templates we succeed in overcoming these difficulties.

Furthermore, we study the problem of decomposing a convex polygon into the minimum number of strictly convex quadrilaterals. We give a characterization of the structure of minimal decompositions and develop from it a linear-time algorithm for this problem. This research has been motivated by the problem to refine a mesh into the minimum number of quadrilaterals. The latter problem, however, turns out to be NP-hard. Therefore, we design a couple of approximation algorithms and prove their performance guarantees. The best known performance guarantee has a factor of 1.867 for meshes without branchings and has been achieved by us with matching techniques, as well.

University | Department | Group | FTP
Last modified: Fri Apr 4 17:04:47 MEST 2003
Matthias Müller-Hannemann <mhannema@math.TU-Berlin.DE>