Scott A. Mitchell, Center for Computing Research
From December 1994 to May 2002 I was a member of the Cubit project. From August 2000 to May 2002 I served as the Cubit technical project leader. I had responsibility for identifying Sandia's mesh generation and model preparation needs, developing short and long term plans to meet those needs, and ensuring that those plans were carried out. Cubit has a large, well functioning team of researchers and developers: about 18 Sandia Staff or contractors and about 35 people total including industry and university collaborators. I frequently interacted with technology suppliers and meshing customers outside of Sandia as well. See the cubit web page for more project information.
My research is in the area of unstructured mesh generation. I've worked on triangulation algorithms, and, since 1995, on hexahedral mesh generation algorithms and control & automation within the CUBIT meshing toolkit. At Sandia I've been funded by some industrial CRADAs, DOE's ASCI initiative, now called the ASC program and MICS. There are many interesting MICS projects at Sandia.
At the 11th International Meshing Roundtable I gave an invited short course on the technical history of hexahedral mesh generation. Creating software for generating good-quality hexahedral meshes for arbitrary geometries is difficult. If the hexes must conform to a prescribed quadrilateral bounding mesh, it often seems impossible. However, people keep trying to find this "Holy Grail", because it would revolutionize the current labor-intensive FEM preparation process. As a community, we've tried a variety of engineering and computer science approaches over the past 10 years. In the short course, I described some of the difficulties and reviewed the approaches we've tried, with a focus on the islands of useful concepts. I also speculated on some of the combinations of things that haven't been tried yet, and how they might solve certain classes of problems. Slides are available here.
In CUBIT, I've been most active with the Whisker Weaving (WW) algorithm for generating all-hex meshes of general geometries, U.S. Patent 5,768,156. Our research is based on the idea that the dual of a hexahedral mesh can be grouped into an arrangement of surfaces which captures features of the global connectivity of the mesh. We call this the "STC" following Peter Murdoch's Ph.D. thesis. Based on the STC, I've written a proof for the existence of topologically well-defined hex meshes, "a characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume" Whisker Weaving is an attempt at a practical algorithm that builds the STC in an advancing front manner. Tim Tautges, Ted Blacker and I have a paper describing the basic algorithm and ideas. In addition, Nate Folwell and I blended the local-rules with a provable curve contraction algorithm to produce a very reliable algorithm for building the initial arrangement if self-intersecting curves dual to the surface mesh are first removed. The algorithm is based on the constructive steps of the existence proof. Once built, however, the arrangement may be too coarse to dualize to a reasonable-connectivity hexahedral mesh, so fix-ups are necessary as described in the existence proof. I've developed a number of fix-up algorithms, some which have application to general meshes not necessarily produced by Whisker Weaving. One type of problem that arises in the existence proof is dealing with two faces sharing two edges. Another example is dealing with knives, hexes with one face collapsed.
Our current status is that while WW can reliably produce topologically well-defined hex meshes, they often exhibit unacceptable quality. During 1998-1999, Patrick Knupp and I worked on improving the quality of an existing all-hex mesh generated by WW, T-HEX, or any other algorithm. We considered a combination of nodal position optimization and local connectivity swapping, as is done with other types of meshes. Our results were mixed. An overview of our MICS plan, and an abstract and a full paper of our LDRD final report for the mesh-improvement project are available.
If you've read the curve-contraction algorithm mentioned above, then this picture will show you how to hex mesh Rober Schneiders's open problem, a 4 sided pyramid with a certain mesh on it. This problem is of practical importance for the following reason. In principle one could mostly fill a volume with hexes starting from the boundary and working inwards. The remaining unmeshed void would be bounded by quadrilaterals. Then you could put attach a four-sided pyramid to each quadrilateral. Then the remaining unmeshed void would be bounded by triangles. Then you could fill that void with tetrahedra compatible with those triangles. Then you could subdivide the original hexes into 8 hexes each, and the original tetrahedra into 4 hexes each. The pyramids then look like Schneiders's open problem. If you could fill those pyramids in with a hex mesh, then you'd have an all-hex mesh of the whole volume, perhaps with exceptional quality elements near the boundary. Such a mesh would be useful for structural analysis.
The picture doesn't provide the hex mesh itself, just instructions on how to generate it. If you have access to an old version of Cubit, you just might be able to actually carry out the steps and see what you get. The caveats are that the pillowing step will probably generate hundreds of hexes, and you'll probably get many hexes with negative Jacobians. But there are some variations of the steps that just might yield a good hex mesh. Does anybody know sufficient conditions on a surface mesh for it to admit a compatible hexahedral mesh of good quality?
I discovered the all-hex geode-template (fixed coordinates) while studying a variation of Schneiders's open problem. Instead of a single pyramid on each quad face bounding the unmeshed void, you place a short brick-shaped template, and require that each template shares four sides with its neighboring templates. Requiring that neighboring templates share sides with one another causes a lot more distortion than in the case of using pyramids, so that for certain voids this method definately won't work.If you can get over that, then the top of the template is split into two triangles, the void is tetmeshed, then the tets are subdivided into 4 hexes. The 26 hexes of the template have good quality depending on the distortion of the template away from being brick-shaped. We've developed a meshing algorithm based on Plastering using this template. In practice, it produces at least a few negative-jacobian hexes most of the time. You can turn the template into the Geode Algorithm.
I've also done some applied research and development in CUBIT on choosing corners for mapped meshing, and a high fidelity scheme for assigning the number of mesh edges on each curve so that each surface may be meshed according to its prescribed algorithm (and corners, if any). Early in 1997 I addressed some CUBIT usability issues and helped create a 7 million element mesh of a complicated 3d model for ASC.
Most of my triangulation algorithms are Computational Geometry /Computer Science type results (Eppstein pages.) That is, I prove that the algorithms always work, and prove bounds on the number of triangles produced and their shape. I've also explored the tradeoff between number of triangles and the smallest triangle angle: If you have a triangulation algorithm and can bound the size and angles of the individual triangles, I have theorems that can bound the number of triangles produced in a competitive sense. I also have a few results (and implementations) that consider the problem of bounding the largest angle apart from the smallest angle under various conditions. I implemented a quadtree-based triangular mesh-generation algorithm, partly at Xerox PARC. Abstracts, papers, and source code for all of the above are available online. Steve Vavasis, my Ph.D. advisor, has implemented an octree-based tetrahedral mesh generator QMG.
The International Meshing Roundtable is a good place to submit papers in unstructured mesh generation Proceedings are available online. I chaired the 5th International Meshing Roundtable (October 1996) and have helped out in various other capacities over the years.
I served on the applied track program committe for the Sixteenth Annual Symposium on Computation Geometry (June 2000).