The new method partitions the surface
into regions (coloured) and then produces
a mesh of polygons, one face representing
each region.

Shrek and his animators will be happy to hear about a new method to help him, or his data files at least, lose weight. A research team led by Mathieu Desbrun from the University of Southern California, has developed a new way to compress the files representing 3D objects used in computer graphics.

The advantage of computer animation of characters, like Shrek, is that animators can spin him inside the computer, viewing him from the side, above or below instantly without having to redraw the view each time. This is possible as Shrek is stored inside the computer as a whole 3D object. And the same technology is being used by virtual museum exhibitions and online shopping sites to allow people to explore 3D objects online.

Although methods for accurately compressing sound and image files are now routine, those for efficiently turning 3D objects into digital files are not so well developed. Developing similarly effective methods of compressing 3D objects is vital for future advances in computer graphics.

The surface of a 3D object is usually stored in a computer as a mesh of triangles, perhaps produced by a 3D scanner or graphics modelling software. However these initial meshes are often highly inefficient, with far more elements in the mesh than are needed. "Even if a region is completely flat it may be scanned into a bunch of uneven triangles, adding unnecessary complexity," Desbrun said.

Producing an "optimal" mesh, that is, one as simple and as accurate as possible, has been shown in general to be NP-hard and thought to be computationally impossible (read more about NP-hard problems in How maths can make you rich and famous from Issue 24 of Plus). Instead the challenge has been to develop methods that simplify the mesh representing an object to provide a good approximation of the surface.

Most of the previous work in the area used greedy algorithms which decide how to merge or remove triangles from the initial mesh based on the shape of the surface in the immediate vicinity. In contrast, with each step in the method developed by Desbrun and his colleagues, how the change will effect the approximation over the entire surface is considered.

Their method alternately reduces the initial mesh by clustering the triangles together into regions taking into account the global error, and then produces a new approximation where each mesh element represents an "average" of the triangles in a cluster. And unlike other compression methods where the mesh elements in the final approximation are all triangular, this new method produces a mesh consisting of polygons with three, four, five or possibly more sides.

The process, which Desbrun will present at the SIGGRAPH 2004 conference in August in Los Angeles, quickly produces a mesh that more accurately and more efficiently represents the original object than those produced by previous methods.

"We believe this approach to geometry approximation offers both solid foundations and unprecedented results," said Desbrun. "Combined with the other recent advances of our research lab on mesh compression, it is a significant step to facilitate use of 3D geometry in many areas." Perhaps soon, along with downloading the trailer and soundtrack of the film, we will get a virtual 3D Shrek to play with too.