Mary-Anne K. Posenau
Penn State York
York, PA 17403
717-771-4186
ABSTRACT
Many applications require a discretization of space before a computational solution can be obtained. The creation of these discretizations, called grids or meshes, often requires a great deal of human intervention in developing grids around complex configurations. Many techniques have been employed to create meshes of triangular (or hexahedral) elements, although other subdivisions of convex cells may be used. In aerodynamic problems, the existence of large gradients in the solution may be exploited to reduce the computational effort by using high aspect ratio elements in high gradient regions. However, the majority of mesh generation methods currently available do not adequately address this need for high aspect ratio unstructured grids.
This research proposes the use of the Voronoi diagram as the basis for a contoured framework that is then used to develop a Steiner point triangulation, with the goal of producing high aspect ratio triangulations.
Keywords
Delaunay triangulation, Steiner triangulation, Voronoi diagram, grid generation, mesh generation.
BACKGROUND
The field of computational fluid dynamics deals with the mathematical modeling of physical phenomena. Closely related to it is the subject of grid generation, which has been studied for several decades [5][6]. The grid provides a framework for the storage and manipulation of physical data. Grids (or meshes, as they are sometimes called) have been used extensively in fields such as computational fluid dynamics (CFD), finite element analysis, computer graphics, medical applications such as the modeling and visualization of tomographic results, cartography, and interpolation.
The research described focuses on computational geometry considerations in grid generation for computational fluid dynamics, or CFD, problems; specifically, algorithms for the generation of meshes with irregular connectivities for aerodynamic problems will be studied. Such meshes are called unstructured grids. The CFD area provides additional requirements and restrictions not often encountered in other problem areas, and therefore provides a rich problem area for computational geometry. A requirement unique to CFD is the need for grids with high aspect ratio elements. The aspect ratio is defined as the ratio s/h, where s is the length of the longest side of the element and h is the distance to the opposite side (in quadrilateral elements) or vertex (in triangular elements). Computational efficiency dictates the need for high aspect ratio elements in regions of high solution gradients.
The problem addressed in this research is how to provide suitable unstructured meshes with high aspect ratio triangular elements for CFD problems using computational geometry techniques.
DESIGN OVERVIEW
Many techniques have been adopted to produce grids. Surveys by Bern and Eppstein [2] and Barth [1] survey the field from computational geometry and CFD viewpoints, respectively. Many of the algorithms rely on heuristic methods for their point generation phases.
The design adopted herein is based on the Voronoi diagram of a set of point and line segment sites corresponding to an initial collection of object boundaries. The Voronoi diagram results in a partitioning of space into neighborhoods where every point within a neighborhood is closest to its generating site. Each neighborhood boundary is then, by definition, equidistant from its two neighbors. By first determining the Voronoi diagram of the initial configuration, the Voronoi diagram may then be used to further partition the region into a series of discrete contours of a controlled density about the objects. This then forms the basis for a Steiner triangulation of the contoured regions, which produces a series of points that are subsequently triangulated non-obtusely along the contour strips.
Due to the nature of the objects at the heart of the discretization, very often inputs may be close to degenerate, with nearly co-linear and co-circular sites. The Voronoi diagram must be robust enough to handle such input, and must result in topologically sound diagrams.
Line Segment Voronoi Diagram
The foundation of this process is a robust mechanism for the generation of the Voronoi diagram of the initial sites, which is a combination of line segments and their endpoints, and a data structure for the diagram. Where some approaches attempt to deal with degeneracy by using exact computations [3], the approach taken here is to develop a diagram that is "good enough" - one that yields results close enough to the exact Voronoi diagram within the numerical accuracy of the computation, yet remains topologically sound.
To date, although algorithms for creation of the line segment Voronoi diagram have appeared in the literature, the approaches taken usually do not exploit the duality to the Delaunay triangulation. In this approach, much of the work may be accomplished in the Delaunay dual - in this paper, the algorithm is described in terms of the Voronoi diagram.
The general construction consists of an initial phase in which an infinitesimally small (but topologically sound) neighborhood for a new site is introduced into the diagram, followed by a series of local tests that expand the new region to its final configuration. Because the criteria for expansion is done locally, each local expansion remains topologically consistent.
The algorithm is based on an algorithm due to Guibas and Stolfi [4], which uses a quad-edge data structure which allows both the Voronoi diagram, and its dual graph (the Delaunay triangulation) to be computed at the same time.
The algorithm proceeds in two phases. First, all point sites (including endpoints) are introduced into the Voronoi diagram. Then each line segment is introduced into the diagram. The same general construction process is used in both. There are three primary differences between point site and line segment site insertion: (1) Whereas the initial creation of a point site neighborhood affects a single Voronoi cell, the initial creation of a line segment neighborhood may often affect several existing cells, which need to be modified before the new neighborhood may be added. (2) Line segments are treated as two sites, whose neighborhoods potentially encompass disjoint halves of the plane. (3) The local tests (incircle computations, to determine whether or not a site violates the circle defined by three other sites) are more involved, dealing with various combinations of point and line segment sites.
Triangulation
Once the Voronoi diagram is constructed, it is used to generate a set of contours at preset levels. The contours between neighborhood boundaries must then be triangulated. Points are introduced using a greedy algorithm to produce a non-obtuse triangulation of each contour section.
CURRENT STATUS
A line segment Voronoi diagram algorithm has been developed and implemented, and is currently being tested. An interpretation and visualization of the dual graph of the line segment Voronoi diagram has been developed. Algorithms for Steiner triangulations in simple contours have been studied in the preliminary work on this topic.
ACKNOWLEDGMENTS
This paper represents work done as a doctoral candidate in the Computer Science Department at the University of Maryland, College Park.
REFERENCES