Lisa Durbeck

Part 1. Unstructured Meshes in Entertainment and Engineering

Tomb Raider

If you have played just about any modern Nintendo(tm) or Playstation (tm) computer game, then you have encountered meshes. Many games make heavy use of what are called polygonal surface meshes, or surfaces built up out of polygons. They are used in the models of many of the people and cars and other 3D things within the game. Polygonal models are a good way for the game designers to get what they want out of the hardware inside the computer or whatever you are using to play the game. I'll explain what a mesh actually is, how it is constructed, and how engineers use meshes to solve problems.

Luke O'Donnell Academy of Interactive Entertainment Canberra, Australia	David Rindner

Picture one of those 14 inch tall wooden mannequins that artists sometimes pose and draw. Now picture one of those with a grid drawn all over it. That's basically the idea, although a lot of the art of it comes down to perfecting the grid, which generally means using different sized and shaped elements to make the model realistic but not overblown. The more complex and detailed the mesh is, the smaller the patches and the more realistic the end result you see in the game looks.



Similar meshes are used by engineers when they want to test a design for a new part, tool, or product. The figure above shows a mesh model of a Pontiac Fiero car done by Aerosoft, Inc. A couple of examples helps to make it clearer why meshes are needed and what they are good for.

For instance, before a prototype of a car is built, engineers create a mesh model of the design and put it through rigorous simulations and tests. One thing they want to know about the car body design is how aerodynamic it is. During aerodynamics tests the designers can modify the shape of the mesh and compare results: does this altered design make the car more fuel-efficient, or keep the tail of the car down better at high speeds?

Tracy Welterlen et al. Lockheed Martin Tactical Aircraft Systems Fort Worth, Texas	Mike Malone Northrop Grumman Corporation Los Angeles, California

Accurate simulations of the aerodynamics of a car or an aircraft require good polygonal surface meshes of the design. They also require good models of the flow of the air around the vehicle. Meshes can be used in that area too. Instead of representing a surface, they are used to capture the essential features of the airflow as the air travels from one mesh region to the next.

So how does someone construct the mesh he or she needs to represent an object, or a phenomenon such as air flow? In computer games and engineering alike, people try to use the simplest mesh that they can get away with. This is for the simple and unavoidable reason that the more complicated the mesh is, the slower any computer software using that mesh will run.

The designers of a character such as Lara Croft in the game Tomb Raider can start with a crude model and keep dividing it up into smaller, more accurate regions until the character looks real, or real enough. Making a decent-looking patch of grass might take a single 2D texture patch. Making a human arm might take fifteen polygons, and making a human face might take a lot more polygons, since there are a lot of small and complicated features on the face: look again at the image near the top with a mesh head on the left and the final result on the right. The more contours you are trying to represent, the more individual flat pieces you need to get something that looks curved. (foot image by David Rinder)

Scientists and engineers can use a similar process to construct the meshes they use: start off with something crude, then increase the resolution of the mesh in areas with interesting features, high curvature, or rapidly changing phenomena, until they have a mesh that gives them a good enough representation to solve the problem they are trying to solve.


Tomb Raider

What is a good enough mesh? In games, it should look realistic and not run too slowly. In engineering, it should accurately represent the problem and not run too slowly: some computations can take weeks to complete. It is currently difficult to construct good meshes for new, complex problems. We have done some research toward making it easier to assess a mesh and refine the techniques used to generate it as described in Part 2 of this article.

The engineering meshes shown here are from the Gridgen Gallery at Pointwise, Inc's site. The human character models came from the online publication “Mastering 3D Graphics”. If you think you might be interested in making your own character, check out David Rindner's article “Character Modeling in form Z” which describes the basic steps involved in creating a character model. The Lara Croft images came from the TombRaider Web Site.

Part 2. Probing Complex Meshes

Like a “connect the dots” puzzle, a mesh is a collection of points and the edges connecting nearby points. One difference is that meshes can be 2 dimensional or 3 dimensional. We have been working with 3 dimensional unstructured tetrahedral meshes. An unstructured mesh is a mesh in which the points need not be equidistant from each other, as they are in a “regular” or “structured” mesh. In a tetrahedral mesh, points in the interior of the mesh form 3 dimensional, four-sided elements with triangular faces called tetrahedra. A tetrahedron is a special kind of pyramid. You'll learn more about what meshes are and how they are used in computer games science in Part 1 of this article.

Just as triangles can take on more shapes than rectangles do, tetrahedra can have many different shapes. This is because there is a lot of freedom as to the positions of the four points relative to each other in space. Some of the more common varieties even have names: a regular tetrahedron is one in which all the sides are the same length and all the interior angles are the same, a wedge and a sliver are two shapes that arise when one point is far from the other three. In a mesh, the position of a tetrahedron in space -- that is, where it exists in the mesh -- also matters, and these fixed positions plus the tetrahedron's asymmetrical shape also give the tetrahedron an orientation in space: an attitude and a rotation, for example, with respect to a coordinate system imposed on the mesh (x,y,z). You can also calculate the volume of a tetrahedron based on the metric distance between its vertices, and compare its volume to other tetrahedra in the mesh.

This flexibility in shape, orientation, and size/volume makes the tetrahedron a good building block for meshes used in applied math to solve problems. Unstructured triangular (2D) and tetrahedral (3D) meshes are used extensively in mechanical engineering, fluid dynamics, and scientific computing for solving problems via finite element and finite volume methods. They allow a researcher to approximate a complex, continuous mathematical function, or series of equations, by representing it with a set of piecewise linear functions that are easy to calculate. If you take Calculus in high school or college math, you encounter a similar idea with Riemann sums: the integral can be thought of as the area under a curve, and it can be approximated by the sum of the areas of a set of rectangles drawn underneath the curve, and the more slender the rectangles you use, the closer you get to the “right” answer.

As with any approximation, the answer you get is not quite as good as the “right” answer. It's obviously a waste of time to get a completely wrong answer, but it is useful to get a somewhat right answer, one that is “pretty good” and that gives researchers some insight that might lead to a more accurate model of the problem. The basic question researchers have to ask themselves is: Is this answer I just obtained as good an answer as I can get with the computing resources I have and the mathematical techniques available to me at this point in human and computer evolution? As it turns out, there are several fairly untapped areas of research implied simply by trying to ask that question! And in recent years, as the demand for finite element and finite volume methods of problem-solving increases, researchers have been working toward good techniques for evaluating the quality of the meshes they generate, as well as studying the effect of mesh quality on solution quality. University of Leeds professor Martin Berzins and I have done work in this area to make the questions about mesh quality easier to pose, and to try to answer some of them on a case-by-case basis.

We have investigated several meshes used in simulations by Tomlin and her colleagues and by Speares and Berzins, to see how the shape, volume, position, and orientation of the tetrahedra relate to the local and overall quality of the meshes. A poor quality region of a mesh is one that, for reasons we wanted to discover, represents a poor discretization of the space, and one for which the simplifying assumptions (such as piecewise linearity) introduce errors into the solution. Currently this problem is solved by finding and then remeshing the bad areas, but at some point in the future, the goal is to be able to generate meshes without having to go in and fix areas afterwards.


I built an interactive environment to analyze these meshes, and with it we were able to find all the poorly-meshed regions. We also could pull apart the worst areas of the mesh to look at everything that might affect the quality there: the tetrahedra's shapes, volumes, and orientations; local solution values; and any sharp increases in solution value from one tetrahedron to the next across a shared face. By comparing bad regions and bad tetrahedra to good ones, we were able to determine that, for these particular meshes, it was generally the size and orientation of one or two faces of a single tetrahedron that caused the regional problems. This experiment gives us direct answers on how to fix these two meshes. It also gives us potentially useful insight into how to change the software algorithms used in generating these meshes so that we can successfully avoid the formation of these few critical faces in regions of the mesh where a fairly fine-grained resolution is required.


Here at the SCI Institute, finite element meshes are utilized to develop improved solutions to:

• Inverse electroencephalography (EEG) problems
• Forward and inverse magnetoencephalography (MEG) problems
• Inverse electrocardiography (ECG) problems

Institute researchers have also been involved in mesh generation research, such as the development of adaptive methods and adaptive mesh generators, and in mesh quality analysis.



For more information:

L. Durbeck. Evaporation: A Technique for Visualizing Mesh Quality. 8th International Meshing Roundtable, 11 - 14 October 1999, Lake Tahoe. Sandia National Laboratories. 259-265.Versions Available: [ Gzip'd PostScript | Postscript | PDF | results as zipped AVI ]

---

M. Berzins and L. Durbeck. Unstructured Mesh Methods Applied to Hyperbolic PDEs with Source Terms: Error Estimates and Mesh Quality. Godunov Methods: Theory and Applications Conference and Short Course, 18 - 22 October 1999, Oxford. numeritek Ltd.Versions Available: [ Gzip Compressed PostScript | Postscript | PDF ]

---

M.Berzins, L. Durbeck, P.K.Jimack and M.Walkley. Mesh Quality and Moving and Meshes for 2D and 3D Unstructured Mesh Solvers. Von Karman Institute for Fluid Mechanics 31st Lecture Series on Computational Fluid Mechanics, March 2000. Von Karman Institute for Fluid Mechanics.Versions Available: [ Gzip Compressed PostScript | PostScript ]