CVT_TET_MESH
Centroidal Voronoi Tessellation
for 3D Regions

CVT_TET_MESH is a FORTRAN90 program which applies CVT methods to produce a tet mesh of various test regions in 3D.

Note that, when using this program, we begin with a region, which is to be filled up with a number of (unspecified) points and then organized into tetrahedrons.

Other programs, such as TABLE_TET_MESH, are available for the case where the points are already given, and only the tetrahedrons need to be determined.

The CVT points are written to files in the TABLE format.

Licensing:

The computer code and data files made available on this web page are distributed under the GNU LGPL license.

Languages:

CVT_TET_MESH is available in a FORTRAN90 version.

Related Programs:

CVT_TRIANGULATION, a FORTRAN90 library which applies CVT methods to produce a triangle mesh of various test regions in 2D.

GEOMPACK, a FORTRAN90 library which contains a routine DTRIS3 that can compute the tet mesh for a set of 3D points, as well as the adjacency information.

KEAST, a FORTRAN90 library which defines a number of quadrature rules for a tetrahedron.

MESH_BANDWIDTH, a FORTRAN90 program which returns the geometric bandwidth associated with a mesh of elements of any order and in a space of arbitrary dimension.

TABLE_TET_MESH, a FORTRAN90 program which can compute the tet mesh for a given set of points.

TEST_TET_MESH, a FORTRAN90 library which defines a few test regions for the generation of a tet mesh.

TET_MESH_DISPLAY, a MATLAB program which can read in the node and tetra files defining a tet mesh and display a wireframe image.

TET_MESH_DISPLAY_OPENGL, a C++ program which reads a tet mesh and displays the nodes and edges using OpenGL.

TET_MESH_L2Q, a FORTRAN90 program which converts a linear to quadratic tet mesh.

TET_MESH_ORDER4, a data directory which contains a description and examples of a tet mesh using order 4 elements.

TET_MESH_ORDER10, a data directory which contains a description and examples of a tet mesh using order 10 elements.

TET_MESH_Q2L, a FORTRAN90 program which converts a quadratic to linear tet mesh.

TET_MESH_QUALITY, a FORTRAN90 program which computes the quality of a tet mesh.

TET_MESH_RCM, a FORTRAN90 program which takes a tet mesh and relabels the nodes to reduce the bandwidth of the corresponding adjacency matrix.

TET_MESH_TET_NEIGHBORS, a FORTRAN90 program which computes the tetrahedral adjacency information.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, pages 345-405, September 1991.
2. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review, Volume 41, 1999, pages 637-676.
3. Lili Ju, Qiang Du, Max Gunzburger,
   Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
   Parallel Computing,
   Volume 28, 2002, pages 1477-1500.
4. Per-Olof Persson, Gilbert Strang,
   A Simple Mesh Generator in MATLAB,
   SIAM Review,
   Volume 46, Number 2, June 2004, pages 329-345.

Source Code:

• cvt_tet_mesh.f90, the source code.
• cvt_tet_mesh.sh, commands to compile, link and run the source code.
• cvt_tet_mesh.txt, the output file.

Examples and Tests:

P01 is the 3x1x1 channel. Test files you may copy include:

• cvt_p01_test01.txt, the dataset of 400 points created by test #1 on test region #1: a standard CVT dataset.
• cvt_p01_test02.txt, the dataset of 400 points created by test #2 on test region #1: a CVT dataset modified so that some points are forced to lie on the boundary.
• cvt_p01_test03.txt, the dataset of 400 points created by test #3 on test region #1: a CVT dataset modified so that some points are forced to lie on the boundary, and some points are specified by the user.
• cvt_p01_test03.png, a PNG image of the dataset, created by MATLAB.

We also ran problem P01 with several sizes, using the test #3 code (some points are forced to lie on the boundary, and some points are specified by the user.) These three sets of points where then used in other calculations, the first of which is TABLE_TETRA, which computes a "tetrahedronalization" of the points.

• p01_00050_nodes.txt, the dataset of 50 points created by test #3 on test region #1.
• p01_00400_nodes.txt, the dataset of 400 points created by test #3 on test region #1.
• p01_03200_nodes.txt, the dataset of 3200 points created by test #3 on test region #1.

P02 is the vertical cylinder. Test files you may copy include:

• cvt_p02_test03.txt, the dataset of 400 points created by test #3 on test region #2: a CVT dataset modified so that some points are forced to lie on the boundary.
• cvt_p02_test03.png, a PNG image of the dataset, created by MATLAB.

List of Routines:

• MAIN is the main program for CVT_TET_MESH.
• TEST01 uses CVT techniques on a given test problem.
• TEST02 uses CVT techniques on a given test problem.
• TEST03 uses CVT techniques on a given test problem.
• CVT_WRITE writes a CVT dataset to a file.
• FIND_CLOSEST finds the closest point to each sample.
• GET_UNIT returns a free FORTRAN unit number.
• TIMESTRING writes the current YMDHMS date into a string.

You can go up one level to the FORTRAN90 source codes.