
           THREE-DIMENSIONAL ALPHA-SHAPE SOFTWARE TUTORIAL

                             Version 0.95


Let us assume that you have a hardcopy of this file on your desk, next
to your Silicon Graphics workstation.  Furthermore, you have the
executables "detri", "mkalf", and "alvis", plus the data file "torus"
in your working directory.  The "torus" data consists of points
generated in a rather regular fashion on the surface of a torus.  This
will serves us as demo data.  Typing `alvis -help' will give you the
version of the "alvis" code, including the available command-line
options.  The same is true for the other programs.


1. "detri" (DElaunay TRIangulation)

To start the tour through the software, run `detri torus' and see what
happens.  This will compute the 3D Delaunay triangulation for the
"torus" data.  The format of the data file is simple: line i contains
the integer coordinates, "<x> <y> <z>", of point i.  Note that detri
will only work if you DO NOT have any "duplicates" in your point set,
ie, 2 or more points with same coordinates.  (You can take care of
this by using the Unix "sort" utility or the "vsort" code that comes
with this distribution, eg, `vsort <unsorted file> <sorted file>'.)
Also, we are talking INTEGER coordinates here, that means, you will
have to convert your data such that the coordinates are integers whose
absolute value is less than 2^31 = 2147483648.

The code employs the incremental-flip algorithm by Barry Joe
\cite{joe:flip2}.  During execution you will see lines of the form

        "v[%d]... %d %d %d..."

indicating that the points v[%d] ... v[%d+10] are added, using %d, %d,
%d,... flip operations.  The algorithm takes O(n^2) time in worst
case, which is optimal.  However, the program is usually a lot faster
depending on the point set; more like O(n*log(n)).  (Data with 10K
points will take approximately 0.5h on a 4D/35 with 32MB memory.)
Upon completion, `detri torus' will produce two files, "torus.dtc" and
"torus.INF".  The "*.dtc" file stores the Delaunay triangulation, and
"*.INF" is an ASCII file containing some statistical information.


2. "mkalf" (MaKe ALpha-shape Family structure)

Now type `mkalf torus' which takes "torus" and "torus.dtc" and
produces "torus.alf", the support structure for the whole family of
(positive) alpha shapes.  This file essentiallystores the alpha-
interval for each face of the triangulation.  (This takes again around
0.5h for 10K points, on a 4D/35 with 32MB memory.  Right now, this
process is indeed rather memory intensive and systems with less than
32MB will trash for point sets in the range of n = 10K.  Sorry. :-)


3. "alvis" (ALpha-shape VIewing Software)

Now the fun starts!  Run `alvis torus' and your Iris will pop up a
graphics window and a panel for the user interface.  It is best to do
this in such that the shell window out of which "alvis" got executed
is still visible.  The program will produce some protocol output which
might sometimes be quite helpful.

(What follows now, is a bit hard to explain in writing, but I will try
anyway... :-)

The program comes up displaying the convex hull of the data, viewed
from the positive z-axis.  You can rotate the scene by pressing the
left mouse button which simulates a track ball.

        (FOOTNOTE: Due to some bug, you will have to move the mouse OUT
         of the window, and then BACK IN, before it works. Beats me!)

You can give the object a "spin" which can be stopped by a double
click.  Of course, you can always move the graphics window around on
the screen; however, you can not resize it.  Still, there is a
possibility to specify the window geometry at startup time; see
'alvis -help' or README file.

So now you are rotating the object... I presume.  Click the "vertices"
button in the middle of the panel.  This gives you the vertices of the
point set.  Clicking the "alpha-shape" button, gives you the same
picture because the default value for alpha is 0, and the 0-shape is
indeed identical to the point set itself.  To select a different
alpha-value go to the vertical slider on the left side of the panel.
The currently selected value is indicated by a blue triangle.  It
should now be at the lower border of the slider.  The blue bars inside
the slider rectangle show the so-called alpha-thresholds, values which
would yield to different shapes. Any two alpha-values within the same
interval will give you the same shape.

Select now a value at the upper border of the slider, and press the
"alpha-shape" button to render the new shape.  This will take a second
(O(m) time, m the number of triangles in the Delaunay triangulation)
and will result in the convex hull.  Select a new value below the
second threshold from the top.  (This is near to the "center" button
of the "alpha ZOOM" menu.)  Recompute the shape by clicking the
"alpha-shape" button.  You will see a slight concavity, but it is
still far from looking like a torus.  (If necessary, drag the shape
into a convenient position using the mouse.)

Threshold-values tend to cluster.  For the "torus" data there are
several clusters close to zero, ie, on the lower end of the slider.
The "alpha-zoom" menu to zoom in and out and take a closer look at
clustered thresholds.

Move the slider triangle back to the bottom edge of the slider and
click the "in 2" button of the "alpha ZOOM" menu 4 times.  (Notice the
longer tick at the lower end of the slider; this represents 0.)  Now,
select an alpha value approximately at the height of the "alpha ZOOM"
menu; eg, alpha = 1.8e+06.  Recompute the shape. You will get a nice
torus.  This is the "optimal" alpha value for this data set.

Now click the "misc" button.  A 1-line window pops up for text input.
Type `option -B "0 0 0.75"' (notice the quotes!), hit <ENTER>, and see
a ball appearing at (x,y,z) = (0,0,0.75), with radius rho = alpha.

        (FOOTNOTE: There is some bug in the implementation of this
         input window.  You type characters, but it DOES NOT display
         them!  It usually works when you type something, use <BACKSPACE>
         to move the cursor back to the beginning of the input line, and
         start typing again.  I know, this is horrible.  Sorry.)

This is the intuition behind alpha-shapes!  Imagine the convex hull of
the point set to be made out of Styrofoam; the points themselves,
however, are made out of granite.  The ball acts as an eraser which
can move anywhere and erase Styrofoam, but it cannot penetrate
granite, ie, the points.  The resulting object, "linearized" to a
polytope, is the alpha shape. Refer to \cite{edels:3d-alpha} for a
more rigorous definition.

Click "misc" again.  Use the <BACKSPACE> key to get rid of the old
command and type `do -a 1.02e6' to get the shape with alpha = 1.02e6.
Press the "multi-colored" button in the "alpha-DISPLAY" menu.  The
yellow triangles form the so-called "regular boundary" enclosing the
"interior" of the shape.  This is where you indeed have some three-
dimensional (what else?) volume.  The mangenta part shows the
"singular boundary" of the shape, consisting of singular triangles,
ie, triangles that do not bound any volume of the shape.  This happens
because the data at hand is really "hollow", but the density at the
inside radius of the torus is higher...  So the thing you see is
really hollow.

Now, unclick the "f1" button in the "alpha-DISPLAY" menu.  Oops, what
happened?...  You disabled the drawing of the singular triangles; so
all you see is the regular interior of the shape.  But what are these
weird paddles where the shading screwed up?  Well, that is actually a
long story. It has to do with the symbolic perturbation (SoS)
performed during the computation of the Delaunay triangulation
\cite{edels:sos}.  Anyway, these paddles are "infinitely" flat parts
of the regular interior.  Since these tetrahedra are totally flat,
they should not be drawn as tetrahedra in the first place, but they
still are, and the hardware Z-buffer of the Silicon Graphics chokes
because it does not know how to shade them properly.  (You call it a
bug; I call it a feature. :-)

Now click "f1" again.  The "1" corresponds to "singular boundary" and
the "f" stands for triangles (triangular Facets).  By the same
pattern, the "f0" button enables/disables the display of the triangles
bounding the regular interior.  Now disable "f0" and you will see
even more paddles, but now they are isolated patches pointing
inside...  A funny shape indeed!

Now, select an alpha of approximately 4.5e5, and you will get a shape
which contains even singular edges. In the meantime, you know how to
disable/enable their display, right?  Good.  Notice the column of
integers to the right of the "f0", "f1", "e1", "v1" buttons; they
count the number of the corresponding faces.  Also observe the
floating-point numbers at the lower end of the panel, which show the
volume, area, and length of the regular interior, singular triangles,
and singular edges, respectively.

Okay, now get rid of the eraser by pressing "misc" and issuing the
command `option -B off'.  Stop or reduce the spin (with the "slowdown"
button of the "TRACKBALL") and click "misc" again.  Then, enter the
following cryptic string: `do 1000 -U -d foo.NL' and see what happens.
(Welcome to the movies! :-) You just saw a sample of alpha-shapes,
starting at the convex hull and shrinking towards the shape consisting
only of original vertices.  Additionally, it filed certain information
about each shape in the "foo.NL" file.

Now it would be a good time to finish reading the README file giving
some more information on the "misc" commands and several file formats.

What more can I say?  I realize that the software still needs dramatic
improvements, esp, with respect to the user interface and speed; but I
think I had something else to do.  What was it again?  Oh yeah, I
still need to write my dissertation.


REFERENCES

@unpublished { edels:3d-alpha,
author = "Edelsbrunner, H and M{\"u}cke, E P",
title = "Three-dimensional Alpha Shapes",
year = "1992",
note = "Unpublished manuscript",
}

@article { edels:sos,
author = "Edelsbrunner, H and M{\"u}cke, E P",
title = "Simulation of Simplicity: A Technique to Cope with Degenerate \
         Cases in Geometric Algorithms",
journal = "ACM Transactions on Graphics",
volume = "9",
number = "1",
pages = "66--104",
}

@article { joe:flip2,
author = "Joe, B",
title = "Construction of Three-Dimensional {Delaunay} Triangulations \
         Using Local Transformations",
journal = "Computer Aided Geometric Design",
volume = "8",
number = "2",
pages = "123--142",
year = "1991",
}


Contact:  Ping Fu 	pfu@ncsa.uiuc.edu
	  Ernst Mucke	muche@cs.uiuc.edu
