Scott A. Mitchell, Center for Computing Research
Link to Scott A. Mitchell's current home page

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 goodquality 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 laborintensive 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 allhex 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 welldefined 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 localrules with a provable curve contraction algorithm to produce a very reliable algorithm for building the initial arrangement if selfintersecting 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 reasonableconnectivity hexahedral mesh, so fixups are necessary as described in the existence proof. I've developed a number of fixup 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 welldefined hex meshes, they often exhibit unacceptable quality. During 19981999, Patrick Knupp and I worked on improving the quality of an existing allhex mesh generated by WW, THEX, 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 meshimprovement project are available.
If you've read the curvecontraction 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 foursided 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 allhex 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 allhex geodetemplate (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 brickshaped 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 brickshaped. We've developed a meshing algorithm based on Plastering using this template. In practice, it produces at least a few negativejacobian 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 quadtreebased triangular meshgeneration 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 octreebased 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).