A finite set of points in 3D space and a real parameter alpha uniquely define a simplicial complex, also called the alpha complex of the points. An alpha shape is the geometric object defined as the union of the elements in the complex. In 1983, a mathematically rigorous definition of alpha shapes was first introduced by Waterman Award winning Professor of Computer Science Herbert Edelsbrunner, UIUC. The first notion of alpha shapes is the 2D analog of the spatial notion described below.
Alpha shapes formalize the intuitive notion of shape. For varying parameter alpha, it ranges from crude to fine in complexity. The most crude shape is a convex hull, which is obtained for very large values of alpha. As alpha decreases, the shape shrinks and develops cavities that may join to form tunnels and voids.
A related notion is the space filling diagram, which is used in biology and chemistry to represent molecular structures. The space filling diagram is the union of balls centered at the points, and it has a geometrically dual alpha complex.
Alpha Shapes Version 2.0 software--from NCSA's Software Development Group (SDG)--is used in several demonstrations in NCSA's CAVE called Stepping into Alpha Shapes. It provides three utilities to visualize a 3D simplicial complex, such as a Delaunay triangulation. Named for the Russian Geometer Boris Delaunay, the triangulation "is uniquely defined for a given point set, and it maximizes minimum angles," says SDG Research Programmer Ping Fu, who adds that it is used often in grid generation, modeling, and graphics.
First, by choosing different values of alpha, different subcomplexes are seen providing insight into the detailed structure of the complex. Second, the simulation of a continuous explosion separates the vertices, edges, triangles, and tetrahedra and thus permits visual inspection of the way these pieces fit together. Third, a directed wave can be propagated through the complex to highlight how it is connected and where the holes are. The wave is a 2D front that advances through the entire complex.
An auditory experience of the complex is made possible through real-time sound synthesis based on the advancing wave. Different features of the wave are mapped to different sound parameters. The goal is to explore the complex with meaningful auditory and visual cues.
The virtual reality environment of the CAVE and the geometric structure provided by the alpha shape software complement each other. The software constructs an object with detailed features on the outside and inside. The CAVE allows an immersive visual and auditory inspection of the features of the object that is difficult to achieve on a 2D computer screen. With the VR environment interface, a biologist can enter hidden regions (voids) within a protein and explore their detailed structures. This is relevant to the study of inaccessible voids and protein folding.
Cosmologists say that as the universe expands, galaxies are clustered into sheet-like structures, surrounding large voids. To explore this global cosmological structure, alpha shapes are an exciting new tool when coupled to numerical simulation and virtual reality visualization. The full spectrum of alpha shapes promises to be useful in this study.
Alpha Shapes Version 2.0 software for SGI workstations is available on the NCSA anonymous FTP server (see inside back cover). The CAVE demonstration using the software was developed by Ping Fu and Gilles Bourhis (SDG), and Robin Bargar, (VEG), NCSA; Herbert Edelsbrunner and Ulrike Axen, UIUC Department of Computer Science; and Insook Choi, UIUC School of Music and Department of Computer Science.
NOTE: Ping Fu contributed to this article.
