From Engine Parts to Monuments, Mathematics-based Software Conjures Accurate 3D Models

By Michelle Sipics

SIAM News, September 24, 2007

3D model of an automotive oil
pump after segmentation by
Geomagic software.

In January of 2006, the reverse-engineering specialists at Advanced Design Concepts had a problem. Wegner Motorsports, the manufacturer of engines for numerous NASCAR and Busch Grand National championship cars, needed a way to precisely duplicate their carefully designed cylinder heads, including the air and fuel ports. Up to that point, engineers had done the task either painstakingly by hand, or with duplication systems that could produce only approximate surfaces.

ADC had some experience in this area, having done similar reverse engineering for clients ranging from Harley-Davidson to the Cleveland Clinic's Total Artificial Heart Group. In the work for that highly varied group of clients, there was one constant: Geomagic Studio. The main product of Geomagic, a company formed in the mid-90s by then-University of Illinois researcher Ping Fu and mathematics professor Herbert Edelsbrunner, Geomagic Studio gave ADC the capability to turn scanned surface point data into three-dimensional models.

"We use their software for anything from sculptures, to race cars, to human bones," says Greg Groth, reverse-engineering manager at ADC. "It allows us to quickly turn our scan data into highly detailed machine-ready surfaces. We can have projects complete within hours and amazing accuracy, compared to [projects] modeled in a traditional CAD package."

All thanks to a mathematician and a researcher-turned-entrepreneur who came together at just the right time---and, they are quick to add, to all the people who have joined Geomagic.

Bridging the Physical and Digital Worlds
A little more than a decade ago, a decidedly entrepreneurial spirit was in the air at the National Center for Supercomputing Applications at the University of Illinois. The Netscape browser had just made its spectacular debut, and scientists and researchers were eager to build on its success.

"[The university] brought in venture capitalists, corporate attorneys, and business consultants," recalls Ping Fu, then a researcher at NCSA. Everyone was "in search of the next killer application that would change the world."

At the time, says Fu, she dismissed the idea that she might be an entrepreneur at heart. But as she conducted her research, in geometry and scientific visualization, she was interested in applying her discoveries to improve the world. Fu foresaw her own revolution: one in which the transformations in one- and two-dimensional computing would find counterparts in three-dimensional space.

"In one dimension, the transformation from analog to digital signal sampling and processing greatly expanded the capacity of the phone, music, and other forms of communication," she says. "In two dimensions, the leap from the typewriter and manual typesetting to digital image sampling and processing forever changed the publishing industry and how information is expressed and disseminated," she continues. In 1996, Fu predicted that the third dimension would follow suit, and she wanted to be part of the action.

And she has been. At Geomagic, the company she founded more than a decade ago with Edelsbrunner (who is now at Duke University), Fu has served as chairman, president, and CEO; Edelsbrunner, the co-founder and a member of the board of directors, is a well-known researcher in digital shape sampling and processing (DSSP). For Fu, DSSP is the embodiment of the revolution she predicted a decade ago.

DSSP provides the ability to digitize physical objects, creating 3D point clouds from scanned surface and location data. In essence, it captures real objects in digital form and allows for comparison between the objects as designed, via original design models, and as manufactured, via the captured point clouds.

"It enables designers, engineers, inspectors and manufacturers to move easily between the physical and digital worlds," Fu says.

Not Technology for Technology's Sake
DSSP requires three-dimensional scanning, which can be done in a number of ways. Some techniques are destructive, cutting the structure to be scanned into layers. In photogrammetry, targets are placed on the object to be scanned, and 3D coordinates of the targets are computed from images. Time-of-flight techniques are based on the emission of laser radiation toward the target, with the time between emission and detection of the reflected radiation used to provide a range measurement. Such scan data are the basis for Geomagic Studio.

Geomagic got its start with Edelsbrunner's solution to the surface-reconstruction problem; his "wrap algorithm," a combination of alpha shapes and Morse theory, was hailed as possibly the first surface-reconstruction algorithm based on discrete methods, but inspired by continuous mathematical concepts. Along with surface simplification, tiling into quadrangles, and conversion to NURBS (nonuniform rational B-splines), the algorithm is the mathematical heart of Geomagic Studio.

In addition to the ADC reverse-engineering challenge mentioned earlier, many clients have employed Geomagic Studio to regenerate "legacy" components. The technology has also been used to verify the safety of spacecraft components for NASA flights, and to create a digital reconstruction of the Statue of Liberty so that the data would be available if the statue needed repair. In Fu's opinion, though, Geomagic's greatest potential lies in mass customization.

"DSSP shifts manufacturing of goods from mass production where consumers are forced to choose what the vendor has available to mass customization, where goods are made in the same efficiency . . . but the customer has the power to order goods made to his or her exact specifications or tastes," she says. "It's not technology for technology's sake, but technology that can change our lives for the better."

Mass customization may sound like a staggering challenge, but Fu and Edelsbrunner are ready to take it on. The pair has often cited their complementary talents as a factor in their success, with Fu primarily handling applications and implementations and Edelsbrunner dealing with mathematics and theory. (Their collaboration goes beyond business: The two married in 1991, several years before they started Geomagic.)

Edelsbrunner recalls some of the mathematical challenges Geomagic has faced in developing Geomagic Studio and the company's automated inspection software, Geomagic Qualify. "Tiling and conversion to NURBS . . . turned out to be the most challenging step," he says, but "alignment and comparison defies a 100% solution in principle, so everybody works in purgatory mode: improving what we have forever."

Efficient, Accurate Modeling
ADC purchased Geomagic Studio in 1999, when the software was in its infancy, and has been using it ever since. Greg Groth is especially proud of the company's use of Geomagic Studio for Wegner Motorsports.

To use the software, Groth says, ADC first needed to collect scan data for the cylinders' outer and inner surfaces---not an easy feat, thanks to the intricate sculpting on the inside of the cylinders. They used laser scanners and hard probes to obtain detailed surface and location data sets, and then let the software work its magic---producing a polygon model that would be edited and converted to a NURBS surface model. The NURBS model is used to generate a computer-aided manufacturing file, which is sent for milling---and the duplication process is complete.

"It was a year or two before we developed an efficient, accurate method of duplicating cylinder head ports," Groth says. "Without Geomagic, that would not have been possible."

New Segmentation Algorithm
Fu and Edelsbrunner probably wouldn't describe their company as working entirely in "purgatory mode," but they do hope to continue to move in new directions. Geomagic's focus on creating concrete and accurate geometric shapes, as opposed to visualizing such shapes, differentiates it from companies that focus on volume-heavy areas like medical imaging, Edelsbrunner says. The company now deals with volume data to some extent, he adds, and may extend those efforts in the future.

Although lacking a broad suite of volume-specific software, "we do extract surfaces from volume data," Edelsbrunner says. "We have developed a new segmentation algorithm for 3D data which might form another nucleus for interesting things to come."

The strength of that algorithm, which Edelsbrunner developed with John Harer, a colleague at Duke, relies on methods from differential and algebraic topology. One key element of their improvements to segmentation is "topological persistence," which Edelsbrunner describes in terms of births and deaths of topological features, giving the example of a height function on the surface of the Earth.

"A sublevel set is the subset of a space where the function value is less than or equal to some threshold, t," he says. "On the Earth, for t = 0 you might think of sea level, so the sublevel set for t = 0 is the underwater surface." (He also points to exceptions---low-lying areas of Israel and other places have exposed surfaces that are actually below sea level.)

"Now, imagine you slowly increase t," he continues, "like in the ancient flood, with Noah sailing on water, and keep track of what the sublevel set is at every moment. The sublevel set slowly grows until, eventually, it consists of the entire topological space.

"The object of interest is the sequence of sublevel sets. The sequence is nested . . . you can imagine the process like a movie, watching the sublevel set as it changes."

Those changes are important because eventually, the set's topology is affected. "When the threshold passes so-called critical values, the sublevel set changes its topology," Edelsbrunner explains. "For example, the water might reach a local minimum and start a lake, [which is] a birth of a component of the sublevel set. [Or, if] the water reaches a saddle point and connects two lakes that were disconnected before, you have a death, since we go from two lakes to only one lake."

What persistence provides, he explains, is a way to associate a particular birth to a particular death, and thus measure lifetime---the moment of death minus the moment of birth.

"This is what you read on gravestones, although the convention is to write it backwards---1950–1981, so you get the negative persistence," Edelsbrunner jokes. Even backwards, the comparison is apt.

"The lifetime can now be interpreted as the interval of scale-levels at which a particular topological feature is relevant," he explains. "In a nutshell, persistence gives a way to measure scale---a big deal, because we have lots of methods to manipulate scale, but now we can be more quantitative and evaluate how well we are doing."

The improvement gives Geomagic a big advantage, Edelsbrunner says, because noise can cause the segmentation algorithm to over-segment. With persistence, a rational decision can be made as to when to simplify segmentation, based on a measurement of an object's features. The redeveloped "watershed algorithm" for segmentation, he adds, also works on three-dimensional density data, where simplification requires a birth–death cancellation that does not exist in the two-dimensional case.

"There is a case in between starting and merging a lake and forming a loop and closing it, namely the case in which we cancel an index-1 with an index-2 critical point," he says. "This is the most difficult one in the three-dimensional case, [and] has not been considered in the past within segmentation algorithms. We think that doing this right will lead to a significant advantage."

Industrial Problems---"Almost Always Harder to Solve"
The research interests of the company have expanded and varied since its creation more than a decade ago, Fu says, but Geomagic's focus has remained the same.

"We've always concentrated on discrete geometric and topological computation and the transformation between discrete and continuous methods," she says, adding that they plan to keep that focus in the future. "There are many unsolved theoretical problems in applied mathematics that impact [the primary industries] we serve at this time: automotive, aerospace, turbine machinery, and dental and medical reconstruction and devices."

Fu lists the handling, viewing, and manipulation of large datasets; the merging of 2D and 3D data; real-time alignment and visualization of 3D scan data; and the mapping of points, curves, triangles, and parametric surfaces as theoretical areas in which Geomagic is interested. As a company, she points out, Geomagic's approach to such problems, necessarily dictated by its customers' needs, is more specialized than that of its academic counterparts.

"Industrial problems are not as pure," says Fu, "but they are almost always harder to solve."

Michelle Sipics is a contributing editor at SIAM News.