Stellar
A Tetrahedral Mesh Improvement Program
Bryan Matthew Klingner
and
Jonathan Richard Shewchuk
Department of Electrical Engineering and Computer Sciences
University of California, Berkeley
About
Stellar improves tetrahedral meshes so that their worst tetrahedra have high quality, making them more suitable for finite element analysis. Stellar employs a broad selection of improvement operations, including vertex smoothing by nonsmooth optimization, stellar flips and other topological transformations, vertex insertion, and edge contraction. If the domain shape has no small angles, Stellar routinely improves meshes so that the smallest dihedral angle is larger than 30 degrees and the largest dihedral angle is smaller than 140 degrees.
Features include a choice of several quality measures (both as objective functions and for mesh statistics), control of tetrahedron sizes, and transformations that improve the boundary of the mesh. The last give you a choice between flat surfaces (in which vertices are constrained to lie, so the surface is improved without changing the domain shape) and curved surfaces (where we optionally permit small changes of the domain shape if they give big wins in mesh quality).
Stellar is written entirely in ANSI C, and relies only on standard C libraries. It should compile on any POSIX-compliant system, and is known to compile on Linux, Mac OS X, and Microsoft Windows. Stellar's internal mesh data structure is an implementation of Blandford, Blelloch, Cardoze, and Clemens' Compact Representations of Simplicial Meshes in Two and Three Dimensions. For geometric computations, it relies on Jonathan's fast robust predicates code. It is available under the terms of the Berkeley Source Distribution (BSD) license. It is accompanied by a (slightly unfinished) visualization program called Show Me, which runs only under X Windows.
Download
Stellar 1.0 (5 July 2009): Stellar_1.0.tar.gz or Stellar_1.0.zip
Documentation
Compiling Stellar
Stellar comes with a makefile that should work out-of-the-box on Mac OS X and Linux. It links only to standard C libraries. To compile on Mac OS X, type
makemake linux-fast on Mac OS X, -O3 on Linux) and without debugging symbols. To disable optimization and add debugging symbols, type
make macdebugmake linuxdebugIf you are running X Windows, you can compile the visualization program Show Me by typing
make macshowmemake linuxshowmemeshconvert.py script to convert meshes to NETGEN format, then use their visualizer.
Using Stellar
Stellar has a sensible default configuration that should do a good job of improving most meshes. A typical invocation of Stellar would be
Stellar mymeshmymesh is the mesh you'd like to improve. Stellar will read the mesh from mymesh.node and mymesh.ele, and write the improved mesh to mymesh.1.node and mymesh.1.ele. The number “1” is called an iteration number, which is convenient for improving or refining a mesh multiple times. If Stellar reads and improves mymesh.1 (likely with a different configuration file), the output is named mymesh.2, which can subsequently be improved to mymesh.3, and so on.
The Stellar distribution includes a mesh example called house2, so you can try it now. More sample meshes are available below.
Configuration File
You can change Stellar's default behavior by specifying a configuration file with the -s switch. The distribution includes a sample configuration file with an enumeration of all of Stellar's options. Read it for instructions on how to change it.
Stellar -s EXAMPLE_CONFIG mymeshCommand Line Switches
Although most of Stellar's behavior can only be controlled through the configuration file, there are a few command line arguments provided for convenience.
-s [configfilename]- Specifies the configuration file. If this option is omitted, Stellar will use the same defaults described in the example configuration file.
-L [verbosity]- Specifies the
verbosityconfiguration parameter, which can also be set in the configuration file. If the-Lswitch comes after the-sswitch, this verbosity will override the setting in the configuration file. -F- When this switch is specified, Stellar will output quality information of the input mesh and quit, without performing any mesh improvement. This switch corresponds to the
outputandquitoption in the configuration file. If the-Foption is specified after the-soption, it will override the setting in the configuration file. This option is useful if you want to analyze the quality of an existing mesh without altering it.
File Formats
Stellar's tetrahedral mesh inputs and outputs come as two files: a .node file that stores the geometric positions of the vertices, and an .ele file that stores the tetrahedra, indexed by their vertex numbers.
.node Files
First line: [# of points] [dimension (must be 3)] [# of attributes] [# of boundary markers (0 or 1)]
Remaining lines: [point #] [x] [y] [z] [optional attributes] [optional boundary marker]
Blank lines and comments prefixed by ‘#’ may be placed anywhere. Points must be numbered consecutively, starting from one or zero. Floating-point attributes and boundary markers may be present in the file, and Stellar will copy them to the output. However, Stellar does not currently support assigning attributes and boundary markers to vertices created during mesh improvement. Here's an example .node file:
# my node file 295 3 0 1 1 3.69 1.19 -3.35 0 2 2.79 2.43 -3.35 0 3 1.64 2.39 -5.13 1 ... 294 1.43 5.32 4.21 0 295 4.32 3.21 5.02 0
.ele Files
First line: [# of tetrahedra] [points per tetrahedron (must be 4)] [# of attributes (must be 0)]
Remaining lines: [tetrahedron #] [point] [point] [point] [point]
Blank lines and comments prefixed by ‘#’ may be placed anywhere. Tetrahedra must be numbered consecutively, starting from one or zero. Points are indices into the corresponding .node file. The four points are the corners of the tetrahedron, and are listed in a right-handed orientation: a tetrahedron with vertices ordered (1, 2, 3, 4) implies that the vertices 2, 3, 4 occur in counterclockwise order as seen from vertex 1. If you curl the fingers of your right hand to follow the vertices 2, 3, 4, then your thumb points toward vertex 1. Here's an example .ele file:
# my ele file 1184 4 0 1 1 11 2 15 2 4 14 15 28 3 6 13 28 34 ... 1183 35 11 34 2 1184 54 15 35 28
Mesh Quality Files (.minsine, .minang, .maxang, .vlrms, .nrr)
Stellar optionally outputs files that list the quality of each tetrahedron in the mesh. .minsine files list the minimum sine among each tetrahedron's six dihedral angles. .minang and .maxang files list the minimum and maximum dihedral angle in degrees for each tetrahedron. .vlrms files list the volume-length ratio, which is the ratio of each tetrahedron's volume to the cube of its root-mean-squared edge length, normalized so that an equilateral tetrahedron has a ratio of 1.0. .nrr files list the radius ratio, the ratio of the radii of the inscribed and circumscribing spheres of each tetrahedron, normalized so that an equilateral tetrahedron has a ratio of 1.0. For more information about these quality measures, refer to Chapter 2 of Bryan's dissertation. Here's an example of a .minsine file:
First line: [# of tetrahedra] [points per tetrahedron (must be 4)] [# of attributes (must be 0)]
Remaining lines: [1 if boundary tetrahedron, 0 otherwise] [quality]
# my .minsine file 1184 4 0 0 0.833605 0 0.803108 0 0.698183 ... 1 0.672113 0 0.697132A tetrahedron is labeled a “boundary tetrahedron” if it has at least one triangular face on the boundary of the mesh.
.stats Files
When it terminates, Stellar writes out a .stats file that details the improvement process. The .stats file includes a listing of improvement options, final mesh quality, and running times and success rates for various improvement operations. You can view an example .stats file here.
Visualization with Show Me
The distribution includes an interactive program called Show Me for visualizing the input and output meshes, both on the screen and as PostScript output. Unlike Stellar, Show Me requires X Windows to compile and run. Show Me isn't completely finished yet, though it's still useful. An alternative (especially if you don't run X Windows) is the visualization program that comes with the mesh generator NETGEN. You can convert our mesh format to NETGEN's format with the meshconvert.py script below.
A typical invocation of Show Me is
showme mymesh.1mymesh.1.node and mymesh.1.ele contain the mesh you'd like to view. If you want to view the mesh vertices only, you can append the suffix .node. For example, to view the vertices of the input mesh (iteration number zero), type
showme mymesh.nodeShow Me has interactive control buttons, many of whose purposes will become clear if you try them. Here are some of the less obvious ones.
- Clicking the left mouse button on the mesh zooms in slightly, and places the point where you clicked at the center of the window. Clicking the right mouse button un-zooms, and also places the point where you clicked at the center of the window.
- The top row of buttons reads an improved mesh, and the second row reads the previous iteration. You can click on the numbered buttons on the right end of these rows to increase or decrease the iteration number, to help you examine a sequence of iterations of the mesh.
- Each
nodebutton displays just the mesh vertices, whereas theelebutton displays the elements (tetrahedra) too. The remaining buttons in the first two rows display file formats associated with the 2D mesh generator Triangle, but not with Stellar. - The
Cut<button and the three buttons to its right allow you to cut away a portion of the mesh so you can see inside. Press one of these buttons, then click a location on the mesh. All tetrahedra whose centroids are to the left of / to the right of / above / below the cursor will disappear. - The
PSandEPSwrite the screen image in PostScript and encapsulated PostScript formats, respectively. - Ignore the
Q,Amt, andPerspbuttons, which don't work yet.
The meshconvert.py script
The distribution includes a mesh conversion script, meshconvert.py, that can read and write several tetrahedral and surface mesh formats. You can use it to import meshes produced by other meshing programs to Stellar's .node/.ele format, and to export the improved meshes to some of those formats. The script requires Python 2.4 or higher. Here is the script's usage information:
meshconvert.py [-s scale] input_file output_file
input_file the input tetrahedral (or trianglar surface) mesh file.
This file must be in one of the following formats:
.node - Our node file format. A .node file must be accompanied
by an .ele file that contains tetrahedra.
.mesh - NETGEN's tetrahedral mesh format.
.vmesh - GRUMMP's tetrahedral mesh format.
.tet - AIM@SHAPE repository's tetrahedral mesh format.
.off - A common surface mesh format. Only boundary triangles
will be available for output.
.surf - NETGEN's triangle surface mesh format. Only boundary
triangles will be available for output.
output_file the output tetrahedral (or triangular surface) mesh file.
This file must be in one of the following formats:
.node - Our node file format. An .ele file
containing tetrahedra will also be produced.
.mesh - NETGEN's tetrahedral mesh format.
.obj - A common surface mesh format. Only mesh
boundary triangles will be written.
.off - A common surface mesh format. Only mesh
boundary triangles will be written.
.surf - NETGEN's triangle surface mesh format. Only
mesh boundary triangles will be written.
-s scale optional vertex scale argument. All vertex coordinates
will be multiplied by scale in the output file.
NOTE: As part of the conversion process, all tetrahedra are adjusted to have a
consistent, right-handed orientation: that is, for a tetrahedron with vertices
ordered (1, 2, 3, 4), the vertices 2, 3, 4 occur in counterclockwise order as
seen from vertex 1. If you curl the fingers of your right hand to follow the
vertices 2, 3, 4, then your thumb points toward vertex 1.
Animations and Meshes
|
 |
| Animation of Mesh Improvement | Download Example Meshes |
Publications
[PDF, 211 MB] [PDF with reduced image quality, 57 MB]
I present a tetrahedral mesh improvement method that creates meshes whose worst tetrahedra have a level of quality substantially better than those produced by any previous method for tetrahedral mesh generation or “mesh clean-up.” Mesh optimization methods often get stuck in bad local optima (poor-quality meshes) because their repertoire of mesh transformations is weak. In contrast, my mesh improvement software employs a broader palette of operations than any other. Alongside the best traditional topological and smoothing operations, I introduce a topological transformation that inserts a new vertex, as well as methods for smoothing vertices on the boundary of the mesh. My implementation routinely improves meshes so that all the dihedral angles lie between 34 and 131 degrees. It also allows a user to locally control the sizes and grading of the tetrahedra, and to generate anisotropic meshes with local control of the orientations and eccentricities of the tetrahedra. With the same operations, I develop a dynamic mesh improvement method for simulations of deforming materials that updates a mesh at each timestep to maintain the quality of its tetrahedra. The dynamic mesher strikes a balance between maintaining high element quality and minimizing the error introduced through artificial diffusion.
[PDF, 27 MB] [BibTeX]
This paper is a concise summary of our work on improving tetrahedral meshes. It discusses mesh improvement operations (especially vertex insertion), tetrahedron quality measures, an effective schedule for mesh improvement, and the high mesh quality that a sufficiently aggressive approach makes possible—though we've improved the quality since we wrote this paper. See Bryan's dissertation for an updated discussion of the techniques implemented in Stellar, plus subjects not covered in this paper such as tetrahedron size control, anisotropic mesh generation, and dynamic meshing.