DIANA PHILLIPS MAHONEY
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 do main, 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.
 |
| The Power Crust algorithm partitions laser scan data into sets of polyhedral cells comprising weighted "balls." Boundaries are extracted from the union of the cells to create a polygonal output surface. At left, a rough offset model has been computed from |
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."
 |
| If a "good" sample is obtained, the Power Crust algorithm can generate a topologically correct, convergent model of complex objects, such as this shell. |
In the Power Crust implementation, Amenta explains, "two balloons touching each other form a flat surface as they expand, and when a balloon hits an input sample, it stops expanding in that direction." Finally, she continues, "if the inside balloons and the outside balloons are put into the box together, a flat piece forms where the two sets of balloons touch each other. That's the power crust."
The technique is unique among most surface-reconstruction tools in that it relies on information about the interior of the dataset rather than only information about the boundary of the dataset. Because of this, it provides good results on "difficult" inputs, including models with sharp corners, unevenly distributed point samples, and holes. For example, at a hole, inner polar balls can bulge out of the object, and outer polar balls can bulge into the interior. The deeply intersecting pair of polar balls will fill in the hole in the surface.
Among the advantages of this technique are its ability to generate a "watertight" model in which the output surface is always the boundary of a 3D solid. "Existing commercial tools sometimes require user intervention to get the topology right," says Amenta, "or they may output models that have holes in them, which then requires the use of a hole-filling algorithm to get a watertight solid model." In contrast, given a "good sample" from a smooth surface, the Power Crust output is guaranteed to be topologically correct and convergent.
 |
| Objects defined by sharp corners with no nearby features can be reconstructed without any samples on the edges themselves using the Power Crust approach. |
Watertight models are critical for such applications as mesh construction for finite element analysis of an object or when creating an STL model for layered manufacturing /rapid prototyping.
The Power Crust technique can also be used to build crude offset surfaces, says Amenta, "by shrinking the inside balloons and expanding the outside ones in the same amount." While the resultant offsets may be too crude for many CAD applications, she notes, "they may be useful for making a solid object into a thin shell for manufacturing."
On the downside, the current Power Crust implementation is slow "and a real memory hog," says Amenta. "Using it on inputs of more than about 100k points takes a long time." The bottleneck, she says, is the Voronoi diagram computation. "We're hoping that new Voronoi diagram codes under development, which are supposed to be an order of magnitude faster, will help."
Another drawback is its inability to handle "noisy" point sets. In such cases, says Amenta, "getting a surface that passes through the points, like the Power Crust tries to do, is not really important." What's more important in such situations, she says, is the ability to successfully average the noisy points together, which is beyond the scope of the Power Crust.
 |
| The inner polar balls calculated for this foot using Power Crust will be combined with the outer polar balls to generate a smooth surface. |
Currently, the researchers are developing enhancements to the Power Crust technique. For example, says Amenta, "we are working on computing pieces of the Power Crust when we only have sample points from part of the surface. Also, we want to speed up the Voronoi diagram computation."
In the meantime, the Power Crust code in its current guise is available as Open Source (GPL) software at http://www.cs.utexas.edu/users/amenta/powercrust.
In terms of commercial potential, says Amenta, "once the Voronoi diagram computation is faster, the Power Crust algorithm should be quite useful for automatically building object models from laser range data."