The 3D alpha shapes software consists of four programs

SOFTWARE

The 3D alpha shapes software consists of four programs:

+ Delcx --- 3D (weighted) Delaunay complex,
+ Mkalf --- 3D alpha shape file and data structure,
+ Alvis --- 3D alpha shape visualizer, and
+ Volbl --- Measuring union of balls and voids.

The first two programs, Delcx and Mkalf, pre-process the data, and Alvis
visualizes the results interactively. The fourth program, Volbl, measures
the union of spherical balls dual to the alpha shape; it is aimed at
computational biology applications modeling molecules. Execute any of
these programs without arguments to get a list of available command-line
arguments. The programs are now described in more detail.

_______________________________________________________________________________
SHORT TOUR

Let us assume that you have a hardcopy of this document on your desk, next to
your Silicon Graphics workstation. Now go to the demo directory of the alpha
shape distribution; for example:

% cd /usr/local/alpha/demo

This directory should at least consist of the following files:

% ls -F
alvis@
delcx@
mkalf@
molecule
torus
volbl@

The torus data consists of points generated in a regular fashion on the
surface of a torus; it will serve as demo data.

In case your demo directory already contains the files torus.dt, torus.alf,
and torus.info, you can jump ahead and start Alvis by typing:

% alvis torus

Otherwise, you should follow the instructions step by step.

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.