Keywords: Delaunay triangulation, Voronoï diagram, co-volume integration schemes.

Yee's scheme, for the solution of the Maxwell equations [1], is an example of a co-volume solution technique that is staggered in both space and time. It exhibits a high degree of computationally efficiency, in terms of both CPU and memory requirements compared to, for example, a finite element time domain method (FETD). Initially proposed for structured grids, Yee's scheme can be generalized for unstructured meshes and this will enable its application to industrially complex geometries [2]. However, despite the fact that real progress has been achieved in unstructured mesh generation methods over the last two decades, such schemes have not generally proved to be effective for simulations involving domains of complex shape. This is a result of the difficulties encountered when attempting to generate high quality meshes, satisfying the requirements necessary for use of co-volume schemes.

As it is staggered in space, Yee's scheme needs two mutually orthogonal meshes for the electric and magnetic fields and the dual Delaunay-Voronoï diagram is the obvious choice. The time step limitation of Yee's algorithm is proportional to the shortest edge in both meshes, so it is critical that the Voronoï diagram is as well behaved as the Delaunay triangulation. In addition, from view point of accuracy, the Delaunay mesh should not contain bad elements, where an element is defined as bad in this context if its circumcentre is located outside the element, or, at least, the number of bad elements should be minimized. Using present meshing methods, it is possible to build a smoothly varying Delaunay triangulation, with a high quality index. However, the corresponding Voronoï diagram is often highly irregular, with some very short Voronoï edges. This increases the total number of required time steps and, hence, reduces the practicality of the method. In the three dimensional case, standard mesh generation methods, like the advancing front technique can produce meshes, with about 30% bad elements, which are unsuitable for use with a co-volume method. In this paper, this difficulty will be addressed and non-standard mesh generation procedures studied. In the two dimensional case, the problem can be solved by use of a stitching method [3] or by the centroidal Voronoï tesselation (CVT) method [4], supplemented by constrained smoothing [5]. In the stitching approach, the problem of triangulation is split into a set of relatively simple problems of local triangulation. Firstly, in the vicinity of boundaries, body fitted local meshes are built with properties close to those regarded as being ideal. An ideal mesh is employed, away from boundaries, in the major portion of the domain. The mesh fragments are then combined, to form a consistent mesh, with the outer layer of the near boundary elements stitched to a region of ideal mesh by a special procedure, in which the high compliance of mesh fragments is used. The work of generalising the stitching method to the three dimensional case is currently in progress. The CVT method is easier to generalise to three dimensions. It produces meshes with around 3-5% bad elements and, as these elements are located near boundaries, the essential part of the work in both methods is the near boundary triangulation.

1

K.S. Yee, "Numerical solution of initial boundary value problem involving Maxwell's equation in isotropic media", IEEE Trans. Antennas and Propagation, 14, 302-307, 1966. doi:10.1109/TAP.1966.1138693

2

K. Morgan, O. Hassan, J. Peraire, "A time domain unstructured grid approach to the simulation of electromagnetic scattering in piecewise homogeneous media", Computer Methods in Applied Mechanics and Engineering, 134, 17-36, 1996. doi:10.1016/0045-7825(95)00958-2

3

I. Sazonov, D. Wang, O. Hassan , K. Morgan, N.P. Weatherill, "A stitching method for the generation of unstructured meshes for use with co-volume solution techniques", Computer Methods in Applied Mechanics and Engineering, 195/13-16, 1826-1845, 2006. doi:10.1016/j.cma.2005.05.037

4

Q. Du, and D. Wang, "Tetrahedral mesh generation and optimization based on Centroidal Voronoï Tessellations", International Journal of Numerical Methods in Engineering, 56, 1355-1373, 2003. doi:10.1002/nme.616

5

D. Wang, I. Sazonov, O. Hassan, K. Morgan and N.P. Weatherill, "Unstructured mesh generation for co-volume numerical schemes based on constrained smoothing", FEF05 IACM Special Interest Conference supported by ECCOMAS, April 4-6, 2005, Swansea, Wales, UK.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £105 +P&P)