TET_MESH_REFINE
Simple Refinement of a Tet Mesh

TET_MESH_REFINE is a C++ program which refines every tetrahedron in a tet mesh, replacing each tetrahedron by 8 subtetrahedrons.

In particular, TET_MESH_REFINE reads two files, one listing the coordinates of nodes, the other the indices of nodes forming tetrahedrons. From this information, it determines a refinement of the mesh, and writes out new node and tetrahedron files corresponding to this refinement.

The refinement of a single tetrahedron is easy. Every pair of nodes generates a new node whose location is the average of the locations of the original two nodes. The problem is that many tetrahedrons may share the same edge. The new node needs to be generated exactly once, and assigned a unique index, which all the tetrahedrons will share. The tricky part of this calculation is thus figuring out whether it is time to generate a new node, or whether the node has already been generated, in which case the appropriate index must be retrieved.

The current version of the code can only refine a tet mesh of order 4. There's no real reason why it could not also handle meshes of order 10, except that the programming is a bit more complex. For the moment, a mesh of order 10 could be handled by using the sequence of programs:

        TET_MESH_Q2L --> TET_MESH_REFINE --> TET_MESH_L2Q
      

Usage:

tet_mesh_refine prefix

• prefix_nodes.txt, the node coordinates;
• prefix_elements.txt, the element definitions.
• prefix_ref_nodes.txt, the refined node coordinates;
• prefix_ref_elements.txt, the refined element definitions.

The element definition file will list node indices. In C++, it may be more natural to use 0-based indices. This program will accept an element definition file that is 0-based or 1-based, and will convert a 1-based input file so that it becomes 0-based internal to the program. The detection of 1-based data is determined by the absence of the use of a 0 index, and the use of an index equal to the number of nodes. This is an implicit and fallible, but reasonable, way to handle this problem.

The input and output files use the simple TABLE format; comment lines begin with a "#" character. Otherwise, each line of the file contains one set of information, either the coordinates of a node (for a node file), or the indices of nodes that make up a tetrahedron, (for a tetrahedron file).

The input file nodes.txt contains the coordinate information for the tet mesh. Each data line contains the X and Y coordinates of a single node.

The input file tetras.txt contains the tetrahedron information for the tet mesh. Each data line contains the indices of the nodes that form a tetrahedron.

The output files have the same format.

Licensing:

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

Languages:

TET_MESH_REFINE is available in a C++ version and a FORTRAN90 version and a MATLAB version.

Related Programs:

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

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, a C++ library which includes a variety of routines for working with tetrahedral meshes.

TET_MESH_BOUNDARY, a C++ program which returns the nodes and faces of the boundary of a tetrahedral mesh, which themselves form a 3D triangular mesh or "TRI_SURFACE".

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 C++ program which takes a 4-node tet mesh and makes a 10-node tet mesh by adding nodes.

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

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

TET_MESH_Q2L, a C++ program which takes a 10-node tet mesh and makes a 4-node tet mesh.

TET_MESH_QUALITY, a C++ program which takes a 4-node tet mesh and computes the "quality" of the mesh.

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

TET_MESH_TET_NEIGHBORS, a C++ program which computes the tetrahedral adjacency information.

TET_MESH_VOLUMES, a C++ program which computes the volume of each tetrahedron in a tet mesh;

Reference:

1. Herbert Edelsbrunner,
   Geometry and Topology for Mesh Generation,
   Cambridge, 2001,
   ISBN: 0-521-79309-2,
   LC: QA377.E36.
2. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, Number 5, 1991, pages 325-331.
3. Anwei Liu, Barry Joe,
   Quality Local Refinement of Tetrahedral Meshes Based on 8-Subtetrahedron Subdivision,
   Mathematics of Computation,
   Volume 65, Number 215, July 1996, pages 1183-1200.
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:

• tet_mesh_refine.cpp, the source code.

Examples and Tests:

CUBE_ORDER4 defines an order 4 test mesh on a cube:

• cube_nodes.txt, the nodes for the 4-node tet mesh.
• cube_elements.txt, the tetras for the 4-node tet mesh.
• cube_ref_nodes.txt, the nodes for the refined tet mesh.
• cube_ref_elements.txt, the tetras for the refined tet mesh.
• cube_output.txt, the output file.

List of Routines:

• MAIN is the main program for TET_MESH_REFINE.
• CH_CAP capitalizes a single character.
• CH_EQI is true if two characters are equal, disregarding case.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• FILE_COLUMN_COUNT counts the columns in the first line of a file.
• FILE_EXIST reports whether a file exists.
• FILE_ROW_COUNT counts the number of row records in a file.
• I4_MAX returns the maximum of two I4's.
• I4_MIN returns the minimum of two I4's.
• I4_SWAP switches two I4's.
• I4COL_COMPARE compares columns I and J of an I4COL.
• I4COL_SORT_A ascending sorts the columns of an I4COL.
• I4COL_SORT2_A ascending sorts the elements of each column of an I4COL.
• I4COL_SORTED_UNIQUE_COUNT counts unique elements in an I4COL.
• I4COL_SWAP swaps two columns of an I4COL.
• I4I4_SORT_A ascending sorts a pair of I4's.
• I4MAT_DATA_READ reads data from an I4MAT file.
• I4MAT_HEADER_READ reads the header from an I4MAT file.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of an I4MAT, transposed.
• I4MAT_WRITE writes an I4MAT file with no header.
• R8MAT_DATA_READ reads the 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.
• R8MAT_WRITE writes an R8MAT file with no header.
• S_LEN_TRIM returns the length of a string to the last nonblank.
• S_TO_I4 reads an I4 from a string.
• S_TO_I4VEC reads an I4VEC from a string.
• 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.
• SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
• TET_MESH_BASE_ZERO ensures that the element definition is zero-based.
• TET_MESH_ORDER4_REFINE_COMPUTE computes a refined order 4 tet mesh
• TET_MESH_ORDER4_REFINE_SIZE sizes a refined order 4 tet mesh.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.