From Engine Parts to Monuments, Mathematics-based Software Conjures Accurate 3D Models
By Michelle Sipics
SIAM News, September 24, 2007
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
"[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
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
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
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"
"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.