Compression algorithm opens the door to 3-D applications

Computer scientists from Bell Labs, the research and development arm of Lucent Technologies, and the California Institute of Technology have developed the first technique that makes it practical to transmit detailed three-dimensional data on the Internet and to work with this kind of data on personal computers.

At the Siggraph 2000 Conference, the researchers are announcing a new algorithm for what is called ‘digital geometry compression.’ The breakthrough could have an impact in fields as diverse as manufacturing, entertainment, medicine, education and retail sales.

Geometry in this sense refers to geometric representations of objects – anything from aircraft parts to cartoon characters – detailed information about size and shape with which 3-D virtual objects can be displayed, measured and manipulated. Digital geometric data is typically acquired by 3-D laser scanning and represents objects using dense meshes of millions or even billions of triangles.

The compression challenge is to use the fewest possible bits to store and transmit these huge, complex data sets, which do not yield to the kinds of processing techniques that have made digital audio, image and video applications commonplace. Efficient geometry compression – delivering the same quality with fewer bits or higher quality with the same bit budget – could supercharge 3-D applications found today at the high end of manufacturing and film making. It also could unlock the potential of high-end 3-D on consumer systems.

The researchers – led by Wim Sweldens of Bell Labs’ Mathematical Sciences Research Center and Professor Peter Schröder of Caltech’s Computer Science Department, who is currently on leave at Bell Labs – report that their technique for geometry compression is 12 times more efficient than the method standardised in MPEG4 and six times more efficient than the best previously published method.

Several aspects of the Bell Labs / Caltech approach set it apart from other research in digital geometry processing. One is the team’s original use of wavelet transformation, ‘wavelets’ for short, a mathematical technique that has solved a surprising variety of practical problems since its emergence in the early 1980s. Wavelet transformation is complementary to Fourier transforms, long-established techniques for processing signals and analysing physical data.

‘Geometry is poised to become the fourth wave of digital multimedia communication,’ Sweldens said. ‘The first three waves – sound in the 1970s, images in the ’80s, and video in the ’90s – were enabled by signal processing based on Fourier transforms. This kind of signal processing simply cannot handle geometry. Wavelets can.’

In fact, the first generation of wavelets, which were built on Fourier transforms, did not handle the geometry of curved surfaces well. One of Sweldens’s earlier fundamental contributions was the development of a technique called ‘lifting,’ an efficient way to generate wavelets without Fourier transforms. (Although developed with geometry in mind, lifting proved to be effective in other areas as well; it was recently incorporated into the JPEG 2000 standard for image compression.)

Producers of animated films and video games are expected to be among the early adopters of wavelet-based geometry compression. ‘Imagine a multiplayer, Internet-based video game that looks as good as Toy Story,’ Schröder said. But the potential applications go far beyond entertainment.

‘Manufacturing companies that can justify a huge investment in systems for 3-D scanning and digital geometry processing have already begun using this technology to create virtual parts catalogues,’ Schröder said. ‘They can use geometric representations when they put out requests for parts, use geometry to guide fabrication equipment, and compare scans of newly made parts to the original designs. ‘

‘Now, if you drastically reduce the cost of this technology while improving the quality of applications, geometry processing is likely to be used in many more parts of the manufacturer’s enterprise, from design to sales and order fulfilment. Also, the technology becomes something that small manufacturers, potentially every manufacturer, can and will use.’

Mass customisation is another likely application. For example, a clothing company might take 3-D scans of customers, transmit the geometric representations to a factory, and ship tailored goods to the customers’ homes.

Though tools for working with geometry are being developed first by and for manufacturers, film makers and other high-end users, consumer applications may not lag far behind. ‘Think of real estate,’ Sweldens said. ‘Today someone selling a house puts pictures of all the rooms on the Web. Soon the seller may be putting a video walkthrough of the house on the Web. When geometry processing reaches the desktop – in software like today’s digital photo and video editors – you’ll not only be able to see any view of any room in the house, but you’ll also be able to see how it will look after you knock out a wall, repaint the rooms, and drop in new furniture from a 3-D catalogue.’

Improvements in digital geometry compression, which are measured in terms of the number of bits per vertex needed to describe a mesh of triangles within a given margin of error, can be exploited in the same ways as gains in other kinds of compression.

Application designers, and ultimately end users, will be able to trade off bits or bandwidth for the quality of 3-D representations. Tested against other approaches, the Bell Labs /Caltech method proved to be superior across the board and especially effective in enabling high-quality reproduction with relatively few bits.

This is the sixth year running that the extremely competitive technical program of the annual SIGGRAPH conference has featured papers by Sweldens, Schröder, and their collaborators. The results published this week augment an increasingly complete toolbox for digital geometry processing that the team has been developing since 1994.

The researchers’ latest breakthrough in compression was built on their earlier achievements, including the generalisation of wavelets to represent spherical data and arbitrary geometries. It also exploited their research on meshes, particularly their insight that two of three types of coordinates used to describe a mesh consume a large fraction of the bit budget but contribute very little to quality. Another key element was the collaborators’ original contribution to ‘subdivision,’ a novel way of building smooth surfaces.

Like other areas of wavelet research – which is known for bringing together mathematicians and computer scientists, theorists and engineers – digital geometry processing has inspired collaboration across boundaries that sometimes separate disciplines and institutions. Collaboration between Sweldens and Professor Ingrid Daubechies of Princeton University has focused primarily on the theoretical side of wavelets, yet has had an impact on the applied side as well.

In addition to Sweldens and Schröder, collaborators who have contributed to the current work are: Andrei Khodakovsky and Igor Guskov at Caltech; Kiril Vidimce at Mississippi State University; David Dobkin and Aaron Lee at Princeton; and Lawrence Cowsar at Bell Labs, Lucent Technologies.

More information on the annual SIGGRAPH conference can be found at http://www.siggraph.org.

The papers ‘Progressive Geometry Compression’ and ‘Normal Meshes’ are available at: http://cm.bell-labs.com/who/wim/papers/compression and http://cm.bell-labs.com/who/wim/papers/normalmesh.