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.
Stellar 1.0 (5 July 2009): Stellar_1.0.tar.gz or Stellar_1.0.zip
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
from within the base directory of the uncompressed tarball. To compile on Linux, type
By default, Stellar is built with optimization (
-faston Mac OS X,
-O3on Linux) and without debugging symbols. To disable optimization and add debugging symbols, type
on Mac OS X or
on Linux. Stellar has also been successfully compiled on Windows, but we provide no build environment for Windows. (If you want to contribute one, we will add it to the distribution.)
If you are running X Windows, you can compile the visualization program Show Me by typing
from the base directory. We do not have a visualization program for Microsoft Windows, but you can use the
meshconvert.pyscript to convert meshes to NETGEN format, then use their visualizer.
Stellar has a sensible default configuration that should do a good job of improving most meshes. A typical invocation of Stellar would be
mymeshis the mesh you'd like to improve. Stellar will read the mesh from
mymesh.ele, and write the improved mesh to
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.
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 mymesh
Although most of Stellar's behavior can only be controlled through the configuration file, there are a few command line arguments provided for convenience.
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.
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.
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.
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
# 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
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
# 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
.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.
.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.
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.
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
mymesh.1.elecontain 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
Show Me has interactive control buttons, many of whose purposes will become clear if you try them. Here are some of the less obvious ones.
nodebutton displays just the mesh vertices, whereas the
elebutton 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.
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.
EPSwrite the screen image in PostScript and encapsulated PostScript formats, respectively.
Perspbuttons, which don't work yet.
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
scalein 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.
|Animation of Mesh Improvement||Download Example Meshes|
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.
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.