Alvis 1.0 (3D Alpha-Shape Visualizer)
Ernst Mucke
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:
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
mu...@uiuc.edu {convex,uunet}!uiucdcs!mucke mucke%uiuc...@uiucvmd.bitnet
Ernst Mucke
> Based on your description, it would appear that the alpha shape is
> generally *more complex* than the convex hull. But the intent seems to
> be (?) to have simpler approximations to the shape. I guess I don't
> understand what the alpha shapes are useful for; could you expound
> (preferably by posting)? Thanks.
Garnted, alpha shapes are more complex than the convex hull, but
that's exactly the point. The convex hull is simple, true, but it has
one disadvantage, namely that it's convex. :) Alpha shapes can be
non-convex, or even disconnected... and thus (have the potential to)
capture "shape" far better. Take for example a point set that
resembles a torus, ie, a donut. The convex hull of this set won't
show most of the torus' features, esp, not the tunnel, ie, the donuts
hole. Alpha shapes do... Or for example, consider a point set where
you have several clusters easily visible to the human eye. The convex
hull would just make one big blob out of it. Alpha shapes can be
usesed to seperate the clusters.
For a more formal discription of the concept "alpha shapes" I would
suggest you get the techreport (from the department or from me):
Edelsbrunner, Mucke. Three-dimensional alpha shapes.
Technical report UIUCDCS-R-92-1734. Dept of Computer
Science, UIUC. 1304 W Springfield, Urbana, IL 61801.
March 1992.
For a informal discription it's best to ftp Alvis from
ftp.ncsa.uiuc.edu and play around with it. That's exactly why we
built the tool! We think alpha shapes can have an enormous potetial
for scientific computing. Many people work with three-dimensional
data, and would need some geometric structure in it. Alpha shapes can
do that. There is still a long way to real-life applications, but the
main goal of Alvis was/is to make the new concept known to the
scientific community. You know, a paper doesn't impress anybody, but
if you have a code and can show things to people, that get's attention.