carrier image

Generation of polyhedral Delaunay meshes

Contreras, David and Nancy Hitschfeld-Kahler

23rd International Meshing Roundtable, Elsevier Ltd., October 12-15 2014


23rd International Meshing Roundtable
London, UK
October 12-15,2014

Department of Computer Science, FCFM, University of Chile, Blanco Encalada 2120, Santiago, Chile

A polyhedral mesh fulfills the Delaunay condition if the vertices of each polyhedron are co-spherical and each polyhedron circumsphere is point-free. If Delaunay tessellations are used together with the finite volume method, it is not necessary to partition each polyhedron into tetrahedra; co-spherical elements can be used as final elements. This paper presents a mixed-element mesh generator based on the modified octree approach that has been adapted to generate polyhedral Delaunay meshes. The main di erence with its predecessor is to include a new algorithm to compute Delaunay tessellations for each 1-irregular cuboids (cuboids with at most one Steiner point on their edges) that minimize the number of mesh elements. In particular, we show that when Steiner points are located at edge midpoints, 24 di erent co-spherical elements can appear while tessellating 1-irregular cubes. By inserting internal faces and edges to these new elements, this number can be reduced to 13. When 1-irregular cuboids with aspect ratio equal to sqrt(2) are tessellated, 10 co-spherical elements are required. If 1-irregular cuboids have aspect ratio between 1 and sqrt(2), all the tessellations are adequate for the finite volume method. The proposed algorithm can be applied to any point set to compute the Delaunay tessellation inside the convex hull of the point set. Simple polyhedral Delaunay meshes generated by using the adapted mesh generator are shown.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article