Better 3D Meshes Using The Nash Embedding Theorem
Written by Mike James
Wednesday, 04 December 2013

Researchers at UT Dallas have found a really clever way of solving the anisotropic mesh problem - do it in higher dimensions and then map it back to 3D. The result is faster and more accurate meshes.

Most 3D models make use of a mesh of simple triangles. In many cases the triangles are all the same size but you can get a better representation by varying the size of the triangle.  The idea is that where the curvature of the surface is large you need more triangles and where it is approaches flat you need far fewer.

The resulting mesh is generally referred to as Non-uniform Isotropic because it uses the same shape of triangle. The next level of improvement comes from dividing up the surface using different shapes and sizes of triangle - a so called Anisotropic mesh.  An anisotropic mesh can represent a surface more accurately with fewer triangles making rendering faster but creating such a mesh is difficult. The same idea can make accurate simulations such as fluid dynamics faster. For such applications we would need to fit a mesh according to other physical conditions not just curvature.

It can be shown that the anisotropy of the triangles should depend on the ratio of the curvature in two directions. The problem can be thought of as trying to best fit the mesh to a curved surface but it is the curvature that makes the problem difficult. You have to work with a curvature tensor and minimize the error within the curved space.

This is where the Nash embedding theorem comes in. John Forbes Nash, the same mathematician responsible for the Nash Equilibrium and who featured in the movie "A Beautiful Mind" worked out that if you could always embed a curved space, i.e. a Riemann manifold, in a perfectly flat, i.e. Euclidean, space. This is great because it means that you can do all the work in the simple flat space. The problem is that the flat space might have to have more dimensions than the original space to allow it to take up the curvature.

For example, if you live on the surface of a 2D sphere then you have to measure distance using the appropriate metric, e.g. the distance between two points isn't the straight-line distance but the great circle distance. However the 2D curved surface can be embedded in a flat 3D space - that is you can step back from the sphere in 3D and see it as a curved surface in a flat space.

A team at UT Dallas lead by Dr. Xiaohu Guo has used the Nash embedding theorem to convert the problem of finding an anisotropic mesh as an isotropic mesh in a flat space. Once you have the isotropic mesh you can map it back to the original lower dimensional space where it becomes anisotropic. For example, in the diagram taken from the research paper, you can see that the 2D anisotropic mesh corresponds to a projection of the isotropic mesh to the right:

Of course in real cases the more than three dimensions are needed.

Is all this extra work worth it?

It seems that moving to an anisotropic mesh produces smoother objects and speeds things up by a factor of better than 100. For example 155 seconds to create a circular image versus 19,500 seconds for a standard mesh to the same quality.

The objective of the work is to create accurate 3D models of human organs as imaged by medical scanners by extending the work to cover volume representations.

Particle-Based Anisotropic Surface Meshing

#### Related Articles

WebGL 3D Sculpture Demo

Computer Simulated Knitting

Kintinuous - Kinect Creates Full 3D Models

Open Source Volume Rendering

New face animation algorithm

Easy 3D