From: mucke@cs.uiuc.edu (Ernst Mucke)
Subject: Alvis 1.0 (3D Alpha-Shape Visualizer)
Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
Date: Thu, 10 Sep 1992 16:36:17 GMT

I'm happy to announce the 1.0 release of Alvis, a 3D alpha-shape visualizer.
This version is a slightly improved version of what we showed at SIGGRAPH'92.
It is ready for anonymous ftp from

        ftp.ncsa.uiuc.edu (141.142.20.50),

file:

        SGI/Alpha-shape/Alvis-1.0.tar.Z

Ftp it using binary mode and do a

        uncompress Alvis-1.0.tar.Z
        tar  xvfp  Alvis-1.0.tar

which will create a directory Alvis-1.0 with the SGI executables
of the 1.0 release, including README files and some sample data.

System requirements:

        o SGI workstation running Irix 4.0 or later.
        o 32 MB memory advisable.
        o Alvis-1.0 release needs less than 2 MB disk space.

Contact address:

        alpha@ncsa.uiuc.edu

Find attached excerpts from the README file shortly discribing the
concept of three-dimensional alpha shapes.

Enjoy, and remember...

 This is a new kind of SHAREWARE.  You share your science and experiences
 with us, and we attain the resources necessary to share more software like
 Alvis with YOU.

--Ernst.

------------------------ snip ------------ snip ----------------------------
Copyright (c) 1991, 1992 The Board of Trustees of the University of Illinois

...

Three-dimensional Alpha Shapes

Frequently, data in scientific computing is in its abstract form a finite
point set in space, and it is sometimes useful or required to compute what one
might call the "shape" of the set.  For that purpose, we introduced the formal
notion of the family of alpha shapes of a finite point set in 3D space, R^3;
see [1].  Each shape is a polytope, derived from the Delaunay triangulation of
the point set, with a parameter alpha controlling the desired level of detail.
The employed algorithms construct the entire family of shapes for a given set
of size n in worst-case time O(n^2).

Conceptually, alpha shapes are a generalization of the convex hull of a point
set.  Let S be a finite set in R^3 and alpha a non-negative real number.  The
alpha shape of S is a polytope that is neither necessarily convex nor
connected.  For alpha = infinity, the alpha shape is identical to the convex
hull of S.  However, as alpha decreases, the shape shrinks by gradually
developing cavities.  These cavities may join to form tunnels, and even holes
may appear

Intuitively, a piece of the polytope disappears when alpha becomes small
enough so that a sphere with radius alpha, or several such spheres, 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 more solid material, such as rock.  Now
imagine a spherical eraser with radius alpha.  It is omnipresent in the sense
that it carves out Styrofoam at all positions where it does not enclose any of
the sprinkled rocks, that is, points of S.  The resulting object is called
the alpha hull.  To make things more feasible, we straighten the object's
surface by substituting straight edges for the circular ones and triangles for
the 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.

Refer to [1] for the formal definitons.

...

REFERENCES

The alpha shape programs are based on the theory of alpha shapes, Delaunay 
triangulations, and simulated perturbation.  There are three main papers 
that had a significant influence on the program development.

[1] Herbert Edelsbrunner and Ernst Mucke. Three-dimensional alpha shapes.
    To appear in Computer Graphics. Proceedings to the Boston Volume
    Visualization Workshop, 1992.

[2] Barry Joe.  Construction of three-dimensional Delaunay triangulations
    using local transformations.  Computer Aided Geometric Design, volume 8,
    number 2, pages 123-142, 1991.

[3] Herbert Edelsbrunner and Ernst Mucke.  Simulation of Simplicity:
    a technique to cope with degenerate cases in geometric algorithms.
    ACM Transactions on Graphics, volume 9, number 1, pages 66-104, 1990.

--
--        
Ernst Mucke,   Dept of Computer Science,  U of Illinois at Urbana-Champaign
mucke@uiuc.edu  {convex,uunet}!uiucdcs!mucke  mucke%uiuc.edu@uiucvmd.bitnet
Newsgroups: comp.graphics.visualization