Three-dimensional scanning technologies give designers and engineers a fast, easy means for digitally representing physical objects. What they typically don't give are smooth surfaces. To digitally re-create a physical object, 3D scanners convert the object's surface to point clouds comprising hundreds of thousands of 3D coordinates. The 3D points must then be connected in some manner to create a mesh from which a surface can be extrapolated. Unfortunately, the resulting mesh can be inaccurate or incomplete-either because the shape is highly complex with details that are difficult for the scanner to capture or because of arbitrary "noise" in the resultant point cloud. Reducing or repairing the surface damage can be a painstaking process, but it's an absolutely necessary one for some applications, particularly manufacturing, which requires smoothly blended, manifold surfaces.
In an effort to take the pain out of the conversion process and to provide better results than those that can be achieved using existing surface-reconstruction techniques, researchers at Applied Research Associates and the University of Canterbury in New Zealand have developed an automated system that not only reconstructs surfaces from 3D point clouds, but also fills holes in 3D meshes and smoothes surface distortions caused by noisy point data.
At the heart of the technique is an implicit-modeling system based on a mathematical concept called Radial Basis Functions (RBFs), which are analytical functions that interpolate between known coordinates. The new RBF-based approach, called FastRBF, models the surface using a function that represents the distance from any point in space to the nearest point on the surface.
 |
| The surface of a scanned turbine blade is rendered with semi-transparency using a new technique that automatically creates smooth surfaces from point cloud data. |
The reliance on RBFs for implicit modeling is significant because they provide the smallest energy value of the known interpolation functions, and thus are considered the smoothest interpolants. After the data interpolation, the system forms triangular faces along the resulting isosurface to create a mesh representation of the surface.
The chief advantage of using RBFs for implicit modeling is that, unlike parametric surfaces or implicit patches, they rely on a single, continuous analytical function to represent the entire surface of an object, the value and gradient of which can be calculated anywhere in space. It has only been recently, however, that mathematics and algorithms have been developed to perform RBF calculations for large or complex objects. "In the past, it has been generally accepted that, although RBFs are the smoothest interpolants, they were computationally impractical for anything more than a few thousand data points," says Bruce McCallum of Applied Research Associates. For example, a 500,000 point object would require 2000gb of RAM.
The new implicit modeling system relies on innovative mathematical methods for RBFs developed by a research team led by Canterbury mathematics professor Rick Beatson. The fast-fitting methods reduce the storage and floating point requirements by an order of magnitude. As such, says McCallum, "RBF methods can now be applied to large data sets using a desktop computer." The Canterbury team uses a 550mhz PIII with 512mb of RAM.
 |
| Automatic mesh repair fills in the gaps of an incomplete surface representation. The RBF-generated mesh (left) is developed using a single analytical function to represent the entire surface of the object. |
Among the additional benefits of the new technology is that RBF-based implicit models are scale-independent, thus a mesh can be generated at any resolution. Similarly, the system can fill holes of any size smoothly and completely, and the resulting mesh is guaranteed to be watertight, which is critical for manufacturing applications, particularly when the data is to be input into stereolithography machines.
The RBF process is completely automatic, requiring no user intervention. While such automation is generally beneficial, there are situations where user input may be required, for example, to avoid filling holes that are actually required. Another obstacle may be computation time. A 500,000-point object, for instance, takes 3-1/2 hours to process on a 550mhz PIII. Lastly, the technique is not well suited to applications that don't rely on polygonal mesh data, such as those using NURBS surfaces, although this is the subject of current work.
On the drawing board for FastRBF enhancements are further speed increases and, says McCallum, "the extension from 3D to 4D, to allow morphing of 3D objects."
At present, the RBF-based surface reconstruction software has been beta tested by numerous users, including researchers at Cornell University who successfully used the tool to reconstruct the surface of the asteroid Eros. Evaluation versions of the software in command-line and Matlab formats are available from FarField Technology (www.farfieldtechnology.com) and a plug-in for the Polhemus Fastscan scanner is available from Polhemus (www.polhemus.com). In addition, a FastRBF plug-in will soon be available for Alias|Wavefront's Maya.
McCallum believes the only roadblocks to widespread application of the FastRBF techniques are conceptual ones. The hurdles, he says, are "educating users that complicated objects can be represented by a single function and that RBF techniques are computationally possible for large problems on desktop computers."
Additional information on FastRBF research can be found on the Web site of Applied Research Associates NZ Ltd. at www.aranz.com.
Diana Phillips Mahoney is chief technology editor of Computer Graphics World.