Software squeezes 3-D data

By Eric Smalley, Technology Research News

Data compression algorithms -- the mathematical formulas that shrink digitized video and still images into packages small enough to travel over the Internet -- have arrived in the world of 3-D graphics.

Researchers at the California Institute of Technology and Lucent Technologies' Bell Labs have adapted an image compression algorithm to handle the complex geometries of virtual three-dimensional objects. The 3-D compression algorithm can be used to transmit Computer-Aided Design (CAD) files and digitized scans of real-life objects over ordinary Internet connections.

The technology could allow consumers to download 3-D renditions of things like furniture and appliances and suppliers to host 3-D catalogs of mechanical parts on the Web, said Wim Sweldens, a research staff member at Bell Labs.

The 3-D compression algorithm is based on wavelets, which are mathematical formulas that analyze electrical signals. Wavelets analyze the frequencies of a signal at different time intervals.

"We generalized the idea of wavelets [to] make it work on more complicated geometry," Sweldens said. "Most of the standard wavelet technology is really suited for very simple geometries. An image is essentially a square or a rectangle. The image may be very complex but the geometry is very simple."

The Caltech-Bell Labs algorithm is 12 times more efficient for compressing 3-D graphics than MPEG4 compression, which is designed to compress video, Sweldens said.

Eve Riskin, an associate professor at the University of Washington and codirector of the university's Data Compression Laboratory called a new algorithm "a neat piece of work," noting that the upcoming JPEG 2000 standard for still image compression is also based on wavelets.

The 3-D compression algorithm both shrinks the number of bits needed to represent a 3-D object and orders the bits so that only the first portion of the post-compression file is needed to provide a low-resolution version of the object. The more bits that come through, the sharper the image becomes. In one example, the form of a 3-D object is recognizable after 956 bytes, which is less than four percent of the total compressed data. Much of the detail is recognizable after 4,806 bytes, or just over 18 percent of the data. (See image.)

This also allows one 3-D data file to be transmitted to computers that have different 3-D graphics capabilities, Sweldens said.

This is possible because 3-D objects are actually made up of many tiny polygons, usually triangles, of various sizes and shapes. "It doesn't exactly matter where these triangles are as long as their shape overall represents the original piece of geometry. One very crucial aspect of our algorithm is that we take [near] optimal advantage of that degree of freedom."

This type of compression also improves the algorithm's performance.

"Compression technology invariably uses some type of prediction," said Sweldens. The algorithm optimizes the layout of the triangles to make their locations easy to predict. "The more accurate the prediction method the less information actually has to be transmitted," he said.

The algorithm is ready for widespread use, Sweldens said. "There's nothing much holding it back technologically," he said. The team is working on extending the algorithm to work with 3-D geometry combined with textual data, and animation. The team's work was funded by Lucent Technologies, the National Science Foundation, the David and Lucile Packard Foundation and the Alias Wavefront subsidiary of Selected Graphics, Inc.

Timeline:   Now
Funding:   Government, Corporate, Private
TRN Categories:   Data Structures and Algorithms
Story Type:   News
Related Elements:   Graphic


September 6, 2000

Page One

Nano-scale jets possible

Software squeezes 3-D data

DNA strands form nano-machine

Scaled links make nets navigable

Magnetic interface photographed


Research News Roundup
Research Watch blog

View from the High Ground Q&A
How It Works

RSS Feeds:
News  | Blog  | Books 

Ad links:
Buy an ad link


Ad links: Clear History

Buy an ad link

Home     Archive     Resources    Feeds     Offline Publications     Glossary
TRN Finder     Research Dir.    Events Dir.      Researchers     Bookshelf
   Contribute      Under Development     T-shirts etc.     Classifieds
Forum    Comments    Feedback     About TRN

© Copyright Technology Research News, LLC 2000-2006. All rights reserved.