DREI Workshop on Computational Geometry in Aerodynamics
July 1-3, 1996

Organizer: Tim Baker

Decomposing Simply Connected Domains into Subdomains

Marshall Bern
Xerox PARC

Consider a simple polygonal domain P. We would like to partition P into a tree of "nice" subdomains. We will discuss what makes a subdomain "nice", and give algorithms and bad examples for this problem.

Surface Gridding from Discrete Data

Juan Raul Cebral
Institute for Computational Sciences and Informatics
George Mason University

An advancing front surface gridding technique that operates on discretely defined surfaces (i.e. triangulations) is presented. Different aspects that are required to make the procedure reliable for complex geometries are discussed. Notable among these are:

Post-generation surface recovery or repositioning techniques are discussed. Several examples ranging from academic to industrial demonstrate the utility of the proposed procedure for `ab initio' surface meshing from discrete data, such as those encountered when the surface description is already given as discrete, the improvement of existing surface triangulations, as well as remeshing applications during runs exhibiting significant change of domain.

Guaranteed Quality Delaunay Meshing
in 3D

Paul Chew
Cornell University

In 2D, techniques for producing unstructured meshes are generally based on either Delaunay triangulations or quadtrees. Both types of algorithms can lead to mesh generators that produce meshes of guaranteed quality: the resulting mesh is mathematically guaranteed to satisfy a number of desirable properties.

In 3D, techniques for producing meshes of guaranteed quality have been based on octrees. Existing Delaunay-based techniques, while often effective in practice, can potentially produce slivers, tetrahedra with nicely shaped faces, but with near-zero volume.

I will describe a new technique that can be used to ensure that no slivers are produced during 3D Delaunay meshing. The procedure for generating Steiner points for the mesh uses randomness, but the expected time to generate each new point is constant.

Five Reasons Why Mesh Generation in 3D Will Never Be Automatic

Jeff Cordova
Visual Computing

A fairly broad talk on issues plaguing 3D mesh generation including: NP-Completeness, CAD interfaces, Solver interfaces, Mesh quality, and User bias.

Automatic Generation of Block Structures -- Progress and Challenges

John F. Dannenhoffer, III
United Technologies Research Center

Recent advances toward the automatic generation of block structures for complex three-dimensional configurations are described. As an illustration of recent advances, a blocking technique which is based upon the concept of an abstraction, or squared-up representation, of the configuration and the associated grid is detailed. By allowing the user to describe blocking requirements in natural terms (such as ``wrap a grid around this leading edge'' or ``make all grid lines emanating from this wall orthogonal to it''), users can quickly generate complex grids around complex configurations, while still maintaining a high level of control where desired. An added advantage of the abstraction concept is that once a blocking is defined for a class of configurations, it can be automatically applied to other configurations of the same class, making the new technique particularly well suited for the parametric variations which typically occur during design processes.

Grids have been generated for a variety of real-world, two- and three-dimensional configurations. In all cases, the time required to generate the grid, given just an electronic form of the configuration, was at most a few days. Hence with this new technique, the generation of a block-structured grid is only slightly more expensive than the generation of an unstructured grid for the same configuration.

This talk will conclude with a discussion of the challenges which still preclude a truly automatic (hands-off) system.

Level Sets, Topology and Multiblock Grids

Peter Eiseman
Program Development Corporation

Level sets can be effectively used to create geometric models that can be directly used for grid generation. We will discuss methods for the formulation and assembly of level set elements. A major advantage of the level set approach is the generality in terms of surface topology provided that all actions are global in nature. Once the geometric model is given, grid generation proceeds. For multiblock grid generation, the first item to consider is the grid topology which , unlike the topology of the surface itself, is not unique. This comes from the fact that the various cycles in a grid can be chosen at will while that for surfaces must be oriented to flow about the surface features so that in the end you can separate surfaces such as toruses and spheres into different classes. In fact the non-uniqueness can be used to considerable advantage. This is readily illustrated by use of compact enrichment. The multiblock grid generator, GridPro(TM)/az3000, will take level surface definitions directly and will allow a user to interactively generate a grid topology. We will describe the topology generation process and the use of level surfaces.

Applications of Voronoi Diagrams to the
Generation of Surfaces

Gerald Farin
Arizona State University

The talk will focus on applications of Voronoi diagrams to the generation of surfaces. I will outline the basic properties of an interpolant due to R. Sibson. This interpolant is not very well-known and deserves better, in my opinion. It is a valid alternative to piecewise linear interpolation over triangles.

I will then describe how to apply this interpolant to transfinite data, in a sense a generalization of Coons patches. These surfaces make heavy use of the medial axis transform. As Sibson's basic interpolant is dimension independent, so is this generalization.

Numerically Reliable Implementation of Geometric Algorithms

Steven Fortune
Bell Laboratories

Geometric algorithms are usually described using real numbers, with unit-cost exact arithmetic operations. Implementors often naively substitute floating-point arithmetic for real arithmetic. An unreliable program may result, since geometric predicates depend upon sign evaluation, which is unreliable if expression evaluation is approximate.

Geometric programs are numerically reliable if geometric predicates are evaluated exactly. Exact evaluation is appropriate if each geometric predicate is relatively simple, that is, if each predicate can be expressed as the sign-evaluation of a low-degree polynomial. Adaptive-precision arithmetic, which evaluates an expression to just enough precision to determine its sign, is effective at reducing the cost of predicate evaluation.

This talk will survey research results using exact evaluation. The approach has been demonstrated with several geometric programs involving points and lines in dimensions two and three (Delaunay triangulations, line segment intersection, polyhedral modeling). The programs are numerically completely reliable (at least in principle) and have performance comparable to floating-point implementations.

Anisotropic Adaptive Mesh Generation for CFD

M. J. Castro-Díaz, H. Borouchaki, P.L. George, F. Hecht
and B. Mohammadi
INRIA Rocquencourt

Unstructured mesh generation methods such as Delaunay make the construction of meshes within complex geometries possible. Anisotropic features as well as adaptive mesh generation can be introduced in such a way that while the number of elements is reduced, the accuracy of the solution is better in the case where the simulated phenomena are strongly directional, for instance when shocks and limit layers exist in a fluid flows problem. Nevertheless, two major difficulties remain. Firstly, as mesh adaption is usually based on a change of the local metric based on the interpolation error of some quantity, the extension to systems is not so clear; this is the case when phenomena of different nature interact (for instance in shock-boundary layer interactions). Secondly, boundary layers are usually not correctly resolved and wall coefficients (such as the friction coefficient) obtained over adapted meshes are usually not exploitable as the distance of the first layer points to the wall is not uniform. In this paper, we aim to present two ideas to overpass the above difficulties.

The first idea is based on the intersection of the different metrics obtained for the different variables of the P.D.E. under consideration which are in our case the conservation variables. This remove also the difficulty we had until now for selecting the 'right' variable for defining the metric from its interpolation error. Indeed, we used to choose the pressure or the density for Euler computations and the local Mach number or the entropy for viscous computations. Obviously, this is a dead-end way as none of these choices could be plenty satisfactory because one variable can not encapsulate all the physics of the whole system.

The second idea is motivated by two requirements coming from structured meshes which are known to be more suitable near the walls as orthogonality can be obtained near the body and as uniform distance can be specified near the wall. Thus, we want to construct meshes as orthogonal as possible near the body, and such that each layer node is located at a uniform distance from the wall.

To achieve this, the idea consists in modifying the local metric near the wall. Thus, to enforce the orthogonality of the mesh in this area the eigenvectors of our metric are changed (they are set to be the tangent and the normal directions with respect to the wall). In the normal direction, mesh size can be specified by the user to obtain a mesh adequate by the boundary. These ideas can be easily extended to three dimensions. The proposed mesh generation procedure is quite fast, generating large grids in few minutes on reasonably fast workstations (an average of 200,000 triangles by minute can be obtained on a HP735/99Mhz workstation).

In this paper we will present an anisotropic mesh generation method, then we will show the way in which it can be incorporated in an adaptive loop of CFD by specifying how to define the local metrics associated with the physical behavior of the problem.

Medial-Axis Approach to Mesh Generation

Christoph M. Hoffmann
Computer Science Department
Purdue University

We describe a geometric approach to mesh generation based on the medial-axis transform (MAT). The approach is due to several researchers, including Armstrong (Belfast), Patrikalakis (MIT) and Srinivasan (IBM). The MAT provides synthetic information of the volume to be meshed. Roughly speaking, the MAT is used to subdivide the volume into smaller regions. By analyzing the interaction of adjacent elements across regions, a hexahedral or tetrahedral meshing strategy can be realized.

Construction of 3-D Improved-Quality Triangulations Using Combinations of Flips

Barry Joe
University of Alberta

We present an algorithm for constructing improved-quality triangulations with respect to a tetrahedron shape measure. This algorithm uses combinations of two or more flips (local transformations) to improve a given triangulation towards an optimal triangulation. Experimental results on tetrahedral finite element meshes show that this algorithm is quite effective at removing slivers from Delaunay triangulations and producing nearly optimal triangulations. We conclude by discussing open problems on optimal triangulations and their construction using flips.

Interfacing an Unstructured Mesh Generator with a Geometry Modeler

Jaime Peraire

A method for generating directionally refined unstructured tetrahedral meshes will be presented. The motivation is the need to efficiently mesh the complex computational domains which are frequently encountered in aerospace applications. In this context, the method is applicable to the construction of meshes suitable for the simulation of inviscid and viscous aerodynamic flows. Minimum user intervention is required and the user specified stretching distribution is achieved by locally modifying an existing mesh. The interfacing of the mesh generation procedure with available geometry modellers will be discussed. The ability to modify the geometry model into a form suitable for mesh generation will be discussed. Certain implementation issues regarding the accuracy and robustness of the generation process will also be addressed. Examples will be presented to illustrate the problems discussed.

Numerical Grid Generation in
a Boundary-Representation Solid
Modeling Environment

Renato Perucchio
University of Rochester

We discuss automatic grid generation for Boundary-Representation (B-Rep) solid models based on the numerical solution of three-dimensional elliptic PDEs. In support of nonlinear finite element analysis of geometrically complex three-dimensional domains, we have developed a series of interactive procedures for decomposing a B-Rep solid model into a valid hexahedral finite element mesh.

The automatic meshing algorithm at the core of the interactive procedure operates on "simple" (i.e., mappable) solids. In order to apply numerical grid generation, the boundary surfaces of the solid is reparameterized and an initial set of surface and volume grid points is defined using an algebraic grid generation algorithm. This grid becomes the initial step of the numerical grid generation algorithm based on elliptic PDEs. This approach yields non-overlapping, boundary conforming grids - even for domains that are untractable with a purely algebraic approach - at a reasonable computational cost.

Parallel Algorithms for Adaptive Refinement and Quality Improvement of
Unstructured Meshes

Paul Plassmann
Mathematics and Computer Science Division
Argonne National Laboratory

Unstructured meshes are a powerful computational tool used in the numerical modeling of physical phenomena on complex, irregular domains. Instead of requiring a uniform distribution of grid points, unstructured meshes allow grid points to be strategically placed in the computational domain. Thus, these meshes are particularly effective in modeling irregular boundaries, multiscale geometries, and rapidly changing solutions.

In this talk, we present parallel algorithms for adaptive mesh refinement, geometric smoothing, and edge (face) swapping. We discuss the performance of the 2-D and 3-D versions of these algorithms from the point of view of computational efficiency and mesh quality. Finally, we consider the effectiveness of these algorithms relative to other problem aspects such as the dynamic partitioning of the mesh and linear system solution

Mesh Generation Directly Interacting With Solid Models: Advantages and Costs

M.S. Shephard, S. Dey, H.L. de Cougny, R. Garimella and R.M. O'Bara
Scientific Computation Research Center
Rensselaer Polytechnic Institute, Troy, NY 12180-3590

This presentation with first briefly review a methodology to automatically mesh general non-manifold geometric domains in which all geometric interactions are with the solid modeling system through direct interrogations. Simple arguments will be given which demonstrate the ability of this approach to ensure consistency in the geometric operations, properly account for the hierarchy of tolerances used by solid modelers, deal with periodic model entities, etc.

eliminate the adverse affects of the small model features often introduced by the modeler, supporting curvature based refinement, the need to use modeler surface derivative information in the integration of the stiffnesses of high order finite elements, etc.

The last part of the presentation will initiation a discussion of the downside of the direct use of the geometric modeler interrogations, which is the computational cost. Some comments will be made on efforts to minimize the number of these interrogations required while still retaining the reliability of the overall mesh generation algorithm.

Experiments with Anisotropic Mesh Generation using Chew and Rivara Refinement

Bruce Simpson
Depts of Computer Science and Applied Mathematics
University of Waterloo, Waterloo, Ontario, Canada

An experimental study of the efficiency of using these two refinement schemes for planar meshes in conjunction with anisotropic mesh metrics will be discussed. When these schemes are used with the usual Euclidean distance measure, both have mesh quality guarantees, i.e. limits on the degradation of the shapes of the generated triangles, in the sense of limiting the sizes of small angles. In practice, they both generally show shape improvement in the generated triangles, relative to the initial mesh Such shape modification is important for realizing the efficiencies in error control sought from anisotropic meshes. The efficiency goal referred to here is the reduction of the number of vertices between these two refinement techniques and with meshes that are optimally efficient for piecewise linear interpolation.

Wavelet Transforms on Irregular Triangulations

Wim Sweldens
Bell Laboratories, Lucent Technologies

Wavelets have shown to form a powerful basis for many applications in signal processing and numerical analysis. Because of the time-frequency localization of wavelets, many functions can be approximated well with only a small number of basis functions. This is the key to applications such as data compression and fast numerical solvers. One of the drawbacks of classical wavelets is that they only provide a basis for functions defined on Euclidean spaces (lines, planes, 3-space) and only allow to transform regularly sampled data. We present Second Generation Wavelets, which allow wavelet transform on non-Euclidean spaces (curves, surfaces, volumes) and can be adjusted to irregularly or adaptively sampled data. Second Generation Wavelets share all the powerful properties of classical wavelets such as time-frequency localization, good approximation, and fast transforms. We first focus on the case of semi-irregular triangulations, i.e. triangulations obtained from subdividing an original, topologically irregular coarse mesh. As an example, we show how to build spherical wavelet transforms. Finally, we show how this can be generalized to a fully topologically irregular case.

Computational Geometry, Grid Generation and Algorithm Developments
Related to Computational Fluid Dynamics within the Aircraft Industry

John Vassberg
Douglas Aircraft

Abstract: A brief historical review of computational techniques associated with problems in fluids will be provided. During this tour through time, examples will be used which depict the application of the solution techniques that have been under use for the past 35 years. Furthermore, impact of algorithm advancements which have facilitated the variety of flow solution techniques will be injected throughout the talk. This will include recent advancements in the very mature field of surface panel methods.

An example of applying the conservation laws typified by CFD to a non-fluids problem will also be given. In particular, this problem is the simulation of the dynamics of a hose-drouge geometry during an in-flight refueling exercise.

And for those not interested in the above, a rather simple computational geometry problem will be posed at the beginning of the presentation. Solution of this brain teaser will of course be given at the conclusion of the address.

Introduction: Numerical methods for problems in fluids have been in continuous development since the advent of the modern day computer. Beginning in the late 50's, development of surface panel techniques were initiated. These solve linear flow problems. Through application of Green's Theorem, these methods reduce the 3D volumetric problem to one which is restricted to the surfaces that bound the flow field. A characteristic of problems addressed by these methods is that the geometry can be arbitrarily complex.

During the 1970's, full-potential methods were under development which solved the non-linear flow about simple geometries. Initially, field methods of these types were restricted to simple geometries because the discretized equations of flow were tightly coupled to the conformal transformations which defined the background grid system.

In the early 1980's, the finite-volume method was developed to allow the decoupling of the grid generation and flow solution processes. In conjunction with grid generation techniques based on elliptic equations, these CFD methods could address slightly more complex shapes such as wing/fuselage combinations.

QMG: An Algorithm for Unstructured 3D Volumetric Mesh Generation

Stephen A. Vavasis
Cornell University

QMG is an algorithm for unstructured mesh generation for very general 3D polyhedral regions, possibly with internal boundaries. The algorithm was designed by S. Mitchell and S. Vavasis and has been implemented (and made available on the web) by S. Vavasis. QMG is the only known algorithm for general 3D mesh generation with a provable bound on the aspect ratio of elements. QMG also has a mathematical guarantee not to overrefine the domain. This presentation will cover some of the foundational ideas underlying QMG.