A University of Southern California computer scientist has created an elegant algorithm to compress the large files that represent 3-D shapes used in animations, video games and other computer graphics applications.
Mathieu Desbrun, assistant professor of computer science at the USC Viterbi School of Engineering, created his ‘Variational Shape Approximation’ scheme with two collaborators.
It produces simplified but highly accurate “meshes” representing 3-D shapes. The meshes are orders of magnitude smaller than those produced by existing ways of handling such files, but remain compatible with all widely used methods to display and use the information.
Desbrun says that the data output from current 3-D scanners consists of a mesh of connected triangles. Unfortunately, many more triangles are needed to represent the shape than are actually necessary. What is more, the data is redundant and costly to process further.
“Even if a region is completely flat,” Desbrun says, “it may be scanned into a bunch of uneven triangles, adding unnecessary complexity.”
Desbrun’s accomplishment was to simplify such a mesh, by combining as many of the triangles as possible into larger elements without compromising the actual shape. Nearly flat regions are efficiently represented by one large, flat mesh element while curved regions require more mesh elements.
The Desbrun team’s novel approach comes from the seemingly unrelated field of machine learning using a technique invented in 1959 called “Lloyd Clustering” named after its inventor Stuart Lloyd.
Desbrun’s algorithm uses it to automatically segment an object into a group of non-overlapping connected regions – an instant draft alternative to the too-numerous triangles of the original scan.
Then the method provides a fast and accurate way to test these alternative larger regions – called proxies – for their fit to the object, and successively optimise them in a small number of iterations.
The process also allows direct manipulation of the results for special purposes by the user – making it a very convenient tool for digital artists in animation studios. The user can select particular areas of a 3-D representation to make them either less or more detailed, or to emphasize them.
“For instance, when approximating a human face with very few proxies, the eyes may not be apparent,” says Desbrun. But a user can adjust the technique to fine-tune the eye region while leaving other areas in rougher form.
The proxy representation, once refined, is then reconverted into a now-optimised mesh – but not necessarily a mesh of triangles. The technique turns them instead into an assortment of polygons – some triangles, but also four, five, six or more sided figures that more efficiently represent the shape.
These in turn feed seamlessly into standard software to represent 3-D shapes on computer screens, or for other uses.