TABLE_TET_MESH
A Tet Mesh of Points in 3D

TABLE_TET_MESH is a FORTRAN90 program which computes the Delaunay tetrahedral mesh ("tet mesh") of a set of points in 3D.

Specifically, TABLE_TET_MESH reads a data file containing the coordinates of a set of points in 3D, computes the Delaunay tet mesh, and writes out a file of sets of four node indices that form a mesh of tetrahedrons.

The input node coordinate data file and the output tetrahedron node index file are in the simple TABLE file format, one set of node coordinates or one set of four node indices, respectively, on each line.

A tet mesh of 3d points is the analog of the triangularization of points in 2d. In other words, it is a maximal organization of the points into nonintersecting tetrahedrons. Since it is a Delaunay tet mesh, it has the additional property that, of all maximal tet meshes, this one has the largest minimum angle.

Usage:

table_tet_mesh nodes.txt

reads the node coordinates in nodes.txt, computes the tetrahedron information, and writes it to the file nodes.tetras.txt.

Licensing:

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

Languages:

TABLE_TET_MESH is available in a FORTRAN90 version.

Related Programs:

CVT_TET_MESH, a FORTRAN90 program which uses CVT methods to compute a tet mesh in a region.

GEOMPACK3, a FORTRAN90 library which computes Delaunay meshes and Voronoi diagrams in 3D, by Barry Joe.

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_BARPLOT_PPMA, a FORTRAN90 program which reads a table file and creates a PPMA bargraph of the data.

TABLE_BORDER, a FORTRAN90 program which can be used to add a border (of zero values) to a table file.

TABLE_COLUMNS, a FORTRAN90 program which can extract specific columns of data from a table file.

TABLE_COLUMNS_PERMUTE, a FORTRAN90 program which permutes the columns of a table file.

TABLE_DELAUNAY, a FORTRAN90 program which computes the Delaunay triangulation of a set of points.

TABLE_HISTOGRAM, a FORTRAN90 program which can make a histogram of a set of points stored in a table file.

TABLE_IO, a FORTRAN90 library which supplies the routines used to read the TABLE file.

TABLE_LATINIZE, a FORTRAN90 program which reads a file of points and creates a "latinized" version by adjusting the data.

TABLE_MERGE, a FORTRAN90 program which reads a file of points, and removes duplicates, and points that are close to each other.

TABLE_ORTHONORMALIZE, a FORTRAN90 program which reads a file of points and orthonormalizes the columns.

TABLE_QUALITY, a FORTRAN90 program which reads a file of points and computes the quality of dispersion.

TABLE_RECORD_MATCH, a FORTRAN90 program which can be used to find close records in a table file.

TABLE_SCALE, a FORTRAN90 program which can be used to multiply the entries of a table file by a scale vector.

TABLE_SHIFT, a FORTRAN90 program which can be used to shift the entries of a table file by a shift vector.

TABLE_STATS, a FORTRAN90 program which can read a table file and compute certain statistics.

TABLE_TOP, a FORTRAN90 program which can read a table file of M-dimensional data and make a table of plots of all pairs of coordinates.

TABLE_UNBORDER, a FORTRAN90 program which can be used to remove the border from a table file.

TABLE_UNIFORM_NOISE, a FORTRAN90 program which can be used to add a uniform noise term to the data in a table file.

TABLE_VORONOI, a FORTRAN90 program which can be used to compute information about the Voronoi diagram of the 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 can read in the node and tetra files defining a 4-node tet mesh and write out files for a 10-node tet mesh by adding midside nodes.

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. Herbert Edelsbrunner,
   Geometry and Topology for Mesh Generation,
   Cambridge, 2001,
   QA377.E36,
   ISBN 0-521-79309-2.
2. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, pages 325-331, 1991.
3. Per-Olof Persson, Gilbert Strang,
   A Simple Mesh Generator in MATLAB,
   SIAM Review,
   Volume 46, Number 2, pages 329-345, June 2004.

Source Code:

• table_tet_mesh.f90, the source code.

Examples and Tests:

CUBE is a simple dataset of 8 nodes:

• cube_nodes.txt, the coordinates of 8 nodes that form the vertices of a cube.
• cube_nodes_tetras.txt, the tetrahedron file.

P01_00050 is a dataset of 50 nodes in a 3x1x1 channel.

• p01_00050_nodes.txt, the coordinates of 50 nodes.
• p01_00050_tetras.txt, the tetrahedron file.
• p01_00050_output.txt, the output file.

P01_00400 is a dataset of 400 nodes in a 3x1x1 channel.

• p01_00400_nodes.txt, the coordinates of 400 nodes.
• p01_00400_tetras.txt, the tetrahedron file.
• p01_00400_output.txt, the output file.

P01_03200 is a dataset of 3200 nodes in a 3x1x1 channel.

• p01_03200_nodes.txt, the coordinates of 3200 nodes.
• p01_03200_tetras.txt, the tetrahedron file.
• p01_03200_output.txt, the output file.

List of routines:

• MAIN is the main program for TABLE_TET_MESH.
• AVAILF returns the index of the next available record in the FC array.
• BARYTH computes barycentric coordinates of a point in 3D.
• CCSPH finds the circumsphere through the vertices of a tetrahedron.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• DHPSRT sorts a list of double precision points in KD.
• DLESS determines the lexicographically lesser of two double precision values.
• DSFTDW does one step of the heap sort algorithm for double precision data.
• DTRIS3 constructs a Delaunay triangulation of vertices in 3D.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_NAME_EXT_GET determines the "extension" of a file name.
• FILE_NAME_EXT_SWAP replaces the current "extension" of a file name.
• FILE_ROW_COUNT counts the number of row records in a file.
• FRSTET shifts vertices so the first 4 vertices are in general position in 3D.
• GET_UNIT returns a free FORTRAN unit number.
• HTDEL deletes a record from the hash table.
• HTINS inserts a record into the hash table.
• HTSRC searches for a record in the hash table.
• I4_MODP returns the nonnegative remainder of integer division.
• I4_SWAP swaps two I4's.
• I4_WRAP forces an integer to lie between given limits by wrapping.
• I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of the transpose of an I4MAT.
• I4MAT_WRITE writes an I4MAT file.
• NWTHOU creates new tetrahedra outside the current convex hull.
• OPSIDE tests if points are on opposite sides of a triangular face.
• ORDER3 reorders 3 integers into ascending order.
• R8MAT_DATA_READ reads data from an R8MAT file.
• R8MAT_HEADER_READ reads the header from an R8MAT file.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
• S_INDEX_LAST finds the LAST occurrence of a given substring.
• S_TO_R8 reads an R8 from a string.
• S_TO_R8VEC reads an R8VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• SWAPES swaps faces in a 3D triangulation.
• TETLST constructs a list of tetrahedra from the FC array.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• UPDATF updates a record in FC after a local transformation.
• VBFAC determines the boundary faces of a 3D triangulation.

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