THREE-DIMENSIONAL ALPHA SHAPES

This is a brief and informal tutorial for the alpha shapes software. For the
time being, this document together with the README files serve as substitutes
for a user's manual, which may be available sometime in the future.

This text gives a brief description of three-dimensional alpha shapes,
followed by a short tour through the programs, especially, the graphics user
interface of Alvis. The list of relevant references can be found in the file
REFERENCES.

_______________________________________________________________________________
THREE-DIMENSIONAL ALPHA SHAPES

The concept of alpha shapes formalizes the intuitive notion of ``shape'' for
spatial point set data, which occurs frequently in the computational sciences.
An alpha shape is a concrete geometric object that is uniquely defined. It
thus stands in sharp contrast to many common concepts in computer graphics,
such as isosurfaces, which are approximate by definition and the exact form
depends on the algorithm used to construct them.

Alpha shapes are generalizations of the convex hull. Given a finite point
set S and a real parameter alpha, the alpha shape of S is a polytope which
is neither necessarily convex nor necessarily connected. The set of all real
numbers alpha leads to a family of shapes capturing the intuitive notion of
``crude'' versus ``fine'' shape of a point set. For sufficiently large alpha,
the alpha shape is identical to the convex hull of S. As alpha decreases,
the shape shrinks and gradually develops cavities. These cavities may join
to form tunnels and voids. For sufficiently small alpha, the alpha shape
is empty.

In the original (unweighted) definition, a piece of the polytope disappears
when alpha becomes small enough so that a ball with radius alpha, or several
such balls, can occupy its space without enclosing any of the points of S.
Think of R^3 filled with styrofoam and the points of S made of solid rock.
Now imagine an eraser in the form of a ball with radius alpha. It is
omnipresent in the sense that it carves out styrofoam at all positions where
it does not contain any of the sprinkled rocks, that is, points of S. The
resulting object is called the alpha hull. For good reasons we straighten
the surface by substituting straight edges for circular arcs and triangles
for spherical caps. The thus obtained object is the alpha shape of S. It
is a polytope in a fairly general sense: it can be concave and even
disconnected, it can contain two-dimensional patches of triangles and
one-dimensional strings of edges, and its components can be as small as
single points. The parameter alpha controls the maximum ``curvature'' of
any cavity of the polytope.

A question that was repeatedly asked in the past is whether it is possible
to construct a shape that represents different levels of detail or different
``curvature'' in different parts of space. This is indeed possible by
assigning a weight to each point. Intuitively, a large weight favors and
a small weight discourages connections to neighboring points. We refer to
the resulting concept as the weighted alpha shape. If all weights are zero
it is the same as the original, unweighted alpha shape. This software is
general enough to handle weights, and this document makes no distinction
between weighted and unweighted alpha shapes, unless such a distinction is
important. Refer to Edelsbrunner and Mucke [3] for the formal definition
of unweighted alpha shapes and to [7, 11] for the extension including weights.