From Point Clouds to Power Crusts.(Technology Information)

A new algorithm reconstructs polygonal surfaces from 3D scan data

The emergence and maturation in recent years of 3D input technologies such as laser scanners, handheld digitizers, and computer vision techniques, have spurred a need for equally sophisticated methods of reconstructing object geometry from raw digital data. This demand is particularly evident in the manufacturing domain, where fast, accurate surface reconstructions of physical objects can be an invaluable design aid. Now, researchers at the University of Texas at Austin have made a promising development in this arena by creating an algorithm that reconstructs polygonal surface models from point clouds.

Called the Power Crust, the new technique is able to extract an approximate skeletal shape, or medial axis transform (MAT), and a surface description of an object based on the collected 3D data--capabilities that could impact a range of solid modeling and manufacturing applications.

The Power Crust technique is based on a structure common in computational geometry called the Voronoi diagram, which uses a space-filling approach to represent proximity information about a set of points or objects.

Typically, Voronoi diagram techniques partition data sampled from the surface of an object into sets of polyhedral cells, and each point of the sampled data is assigned to its nearest cell. The points that share a nearest cell form the Voronoi diagram.

In the Power Crust implementation, the structure is further defined by subsets of weighted poles that lie inside and outside of the object. These sets of poles, like the Voronoi diagram, divide the space into polyhedral cells. The boundary of the union of the interior cells forms the polygonal output surface, or the Power Crust.

Principal researcher Nina Amenta uses a cage analogy to illustrate the concept. "Think of the input points sampled from the surface of an object as being fixed in space and forming a sort of cage around the interior of the object. Then think of blowing up a lot of balloons inside the cage, each as big as possible, so that they fill up the interior and maybe poke out a little between the points."