Since its first release in 1992, Alpha Shapes has been quietly shaking up people's ideas of scientific visualization. One reason is that its images are almost skeletal -- nothing like the textural images common to many scientific animations and visualizations. Another reason it is perturbing the world of scientific visualization is that it embodies a new approach to modeling scientific data.
A modeling tool, Alpha Shapes can transform points of data into objects whose shapes may or may not be known, such as the microscopic pockets on the surfaces of proteins. For example, NCSA structural biologists are using it to calculate the bizarre configurations of proteins' binding sites, which is essential to understanding how proteins interact. Others are observing how membranes change over time as part of their investigation of fluid flow in the brain.
Ping Fu, NCSA Technical Program Manager
Biologists are currently the largest users of Alpha Shapes; however, any discipline that involves geometry will find uses for it, says Ping Fu, a technical program manager at NCSA and the software's developer. Alpha Shapes is about constructing and discovering shapes.
For most of the past three years, Fu and a team of graduate research assistants have been refining the program so that it is accurate and expandable. With two releases last year and another within twelve months , it is now ready for other scientists to explore its possibilities.
On the other hand, Alpha Shapes computes shapes from exact points in space (data) based upon mathematical formulations. To draw a group of overlapping spheres, for instance, Alpha Shapes takes only the centers of the balls and their radii to identify where the spheres intersect as well as to clip away mass within the spheres. As long as the spatial point data and the formula for calculating the shapes are correct, Alpha Shapes can rapidly reconstruct any shape from these coordinates. Because Alpha Shapes is based on mathematical information about a shape, a researcher can compute other properties -- volume and area, for example.
According to Fu, Alpha Shapes provides a quantitative and rigorous method for describing and computing shapes at many levels of detail in 3D space. "An alpha shape is a concrete geometric object that is uniquely defined. . . . If you agree with the criteria for construction," states Fu, "you can construct a system. Even if it is unknown."
Alpha Shapes has its underpinnings in mathematical concepts from combinatoric and computational topology, both narrow disciplines within computational geometry. Few scientists outside of computer science and mathematics know of combinatoric and computational topology because they work with continuous mathematics, in which formulas define functions and space is infinitely divisible.
Combinatoric topology falls within discrete mathematics where everything consists of pieces -- perhaps thousands, but still finite. Combinatorics is about counting these finite pieces. Its algorithms determine whether a particular arrangement of objects is possible, and if so, how many different ways they can be arranged. On the other hand, topology indicates the shape of objects by disclosing their placement and relationship in space with points of data. Some people refer to topology as "rubber sheet geometry" because if you were to paint dots on a piece of rubber and stretch it, the relationship among the dots would not change although their distances might. Using combinatoric topology, researchers can compute the size, number, and shape of objects. By adding algebraic "weights" to data points, special characteristics can be singled out from an enormous number of unspecified data points.
Because so few scientists know much about combinatoric topology, only a few of its concepts have found their way into other disciplines. Fu's own acquaintance with combinatoric topology might have remained glancing if her mathematician husband, Herbert Edelsbrunner, had not happened to be among the world's leading practitioners in this field. (In 1991, at the age of 33, Edelsbrunner won the prestigious Waterman Award for his pioneering work in computational geometry.)
One of the ways in which Edelsbrunner uses combinatoric topology is in dreaming up new geometric shapes, which he then figures out how to compute. To some that might sound like an unusual occupation until one starts to look at shapes in the environment. People construct objects that are primarily rectangular -- buildings, furniture, and books to name a few. In nature, objects take on shapes of limitless variety. As a consequence, formulas for calculating the area of a rectangle are wholly inadequate to the task of computing the shapes of proteins.
Through Alpha Shapes, a new field of mathematics is being opened to other sciences, according to Jean Ponce, professor of computer science at UIUC's Beckman Institute. "This in itself is important because ideas from computational geometry often stay on the pencil and paper side of things rather than being exploited for practical applications."
Fu became a bridge between a mathematical theory and its application in science. Whereas Edelsbrunner takes concepts and makes them concrete as theories and algorithms, she transforms them into software. This meshing of skills by Fu and Edelsbrunner makes them a powerful team, says Joseph Hardin, associate director of NCSA's SDG. "It is one thing to prove an idea within a mathematical framework; it's another to take what has been proven and make it of practical value."
Edelsbrunner describes his collaboration with Fu as a chain of development. Through the two of them, he says, theory is transferred into practice and knowledge about its relevance flows back to theory. Through implementation, an algorithm is proved correct.
The two-way flow along this chain is evident in the latest releases of Alpha Shapes, which are nothing like the first version. Whereas the initial release sprang from Edelsbrunner and his student Ernst Mucke's work on 3D alpha theory, the later versions bear Fu's imprint. Communication with other scientists have led to capabilities such as weighted points. The latest version made it possible to construct a shape that represents different levels of detail. It takes into account more natural variability (such as the 16-fold difference in size between hydrogen and oxygen atoms). A recent paper on protein recognition with Alpha Shapes by Edelsbrunner, Fu, Mike Facello (SDG), and Jie Liang (Apps) was selected as the best paper for 1995 by the Institute of Electrical and Electronics Engineers.
By next spring she will add flesh to Alpha Shapes' boney images by releasing a version of the software that will produce smooth, nontriangulated imagery. The representations will be striking, Fu assures; and their underlying structure will be mathematically sound.
"If it is beautiful now, it is because it is a new technique to make things that are beautiful," says Fu. "The next step will be to impress those not in science -- those in visualization, in graphics, and business."
Ping Fu set up a "mini-NCSA" in Hong Kong in early 1995.
Return to the Table of Contents.