Algorithms For Automatic Generation Of Triangular Meshes

Triangulation is a fundamental step in the process of computer geometric modeling and plays an essential role in computer graphics. It is of a great interest for many CAD/CAM applications such as surface modeling, surface rendering, finite element analysis, fundamental geometric calculations, science visualizations and so on. It, as a basic step in many algorithms, is also an important part in computational geometry. The problem of triangulation is to generate triangular finite element meshes over a given 2-D domain, a given surface, or a given 3-D domain, and to make them as optimal as possible under some specific conditions. This thesis deals with three aspects of triangulation: triangulation with a given boundary over a 2-D domain; triangulation of scattered points over a 2-D domain; triangulation of NURBS surface under a given error tolerance. Triangulation over a convex 2-D domain is implemented by advancing front technique and circumcircle optimizing method, while the triangulation over an arbitrary 2-D domain needs more restriction of the visibility between points. Triangulation of a set of scattered points on a plane is obtained by a novel algorithm, which generates the convex hull of it in the process of triangulation according to the property that the boundary of triangulation meshes coincides with the convex hull of the set of points. Triangulation of NURBS surface under a given error tolerance is achieved by several steps. Firstly, recursively bisecting the surface until the given error tolerance is satisfied. Secondly, based on the discretized surface, generating boundary points. Finally, dynamically generating interior points on the surface and triangular meshes according to the density of points and mutual exclusive coefficients between them. Experiments demonstrate triangular meshes generated in this thesis appear to be in good form and precision. The generation is also efficient and capable of satisfying need of applications.