_______________________________________________________________________________ ____________________________ Alvis 4.0 Tutorial _____________________________ 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. _______________________________________________________________________________ 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. _______________________________________________________________________________ Delcx (DELaunay CompleX) To start the tour, run % delcx torus This will compute the 3D Delaunay complex for the torus data. Upon completion, the files torus.dt and torus.info will have been created. The *.dt file stores the Delaunay complex, and *.info is an ASCII file containing statistical information. Both files will be needed for further computations. Refer to README.input for a specification of the data file format. It is sometimes useful to extract lists of simplices from the binary *.dt files. Delcx has an ``ABC mode'' (All But Computation) for this. For example, it allows you to print a list of all Delaunay simplices to an ASCII file. See README.delcx for more information. _______________________________________________________________________________ Mkalf (MaKe ALpha shape File and data structure) Now type % mkalf torus which takes the files torus and torus.dt to produce the file torus.alf. The latter is the support structure for the family of alpha shapes. This file essentially stores the alpha interval for each simplex of the Delaunay complex. `Simplex' is a general term that can mean vertex, edge, triangle, or tetrahedron. (Right now, this process is rather memory intensive and systems with less than 32MB might run out of memory for point sets in the range of 10K or higher. Sorry. ;-) Mkalf also has an ``ABC mode.'' With this, you can produce ASCII simplex lists from specific alpha shapes. Type % mkalf torus -C "help" for a list of available options. _______________________________________________________________________________ Alvis (3D ALpha shape VISualizer) Now the fun starts! Run Alvis by typing % alvis torus which will open a main viewing window, a scene panel, and a signature panel. There is also an optional pocket panel that can be opened using the `Gizmos' pull-down manu of the viewing window. This will be discussed later. It is best to start Alvis so the shell window in which Alvis is executed is still visible. The program produces protocol output which is sometimes helpful. The window comes up displaying the convex hull of the data, viewed from the positive z-axis. You can ROTATE the scene by moving the mouse over the main viewing window and pressing the left mouse button; this simulates a track ball. If press the shift key at the same time with the left mouse button you can MOVE the scene sideways in the viewing window. You can also ZOOM by pressing the middle mouse button, and sliding the mouse up (zoom out) or down (zoom in). A permanent SPIN of the shape is induced by pressing the left mouse button, sliding the mouse quickly, and then releasing the button before the mouse comes to a rest. Spin can be stopped by a click. The windows can be moved and resized. The default size is the NTSC standard (640x480). So now the shape rotates ... so far pretty boring, but this will soon change. Look at the SIGNATURE panel. You see three colorful curves in the drawing area, and a set of six labeled buttons. To the left of each such button there is a small square toggle button whose color matches one of the curves. Click on these toggle buttons and see what happens. Now click your left mouse button anywhere in the drawing area ... a vertical line appears, the alpha rank cursor. The curves are what we call ``signatures'' or ``signature graphs.'' Remember that we computed a representation of the entire family of alpha shapes, ranging from the empty shape (for alpha = -infinity) to the convex hull (for alpha = +infinity). Each signature represents a certain property (eg, volume, area, number of singular edges, etc.) over the entire family of shapes. Each shape has an assigned index, called its ALPHA RANK. The vertical line of the alpha rank cursor is used to select ranks. Press the left mouse button, and move your mouse left or right. You see the line follows the mouse. Now place the cursor at the peak of the `area' signature (green curve), and click the `alpha shape' button in the scene panel. An almost perfect torus should appear in the main viewing window. As an exercise, select a few shapes by first moving the alpha rank line and then clicking the `alpha shape' button. Usually, alpha rank lines positioned at peaks or valleys of signature graphs give interesting shapes. Below the signature drawing area, there are buttons labeled `<<', `<', `||', `>', and `>>'. These aid in the selection of alpha ranks when the number of different alpha ranks exceeds the number of pixel columns in the window. The `<' and `>' buttons decrease and increase the rank by 1, and the `<<' and `>>' buttons decrease and increase it by the number of ranks represented by a single pixel column. An animation of the entire family of alpha shapes can be started by pressing the right mouse button continuously in the signature window moving the rank cursor to the right of its initial position. Shapes in the sequence will be displayed in fast succession once you release the button. The top edge of the viewing window offers several pull-down menus. For example, in the `Props' menu you can select `Alpha Eraser', which results in a ball that appears in the lower right corner of the viewing window. Its radius is equal to alpha selected for the current shape. This is the intuition behind alpha shapes for points without weights described earlier. For points with weights the meaning of alpha is more complicated and we refer to [11] for a formal and detailed description. Now we return to the MATRIX on the right hand side in the scene panel. It has an entry or button for each type of simplex. Rows distinguish dimensions and columns distinguish between singular (sg), regular (rg), and interior (in) simplices. To explain this choose rank 173. The default selection shows regular triangles and all singular simplices. The regular and singular simplices make up the boundary of the shape. Regular edges and vertices are graphically redundant and therefore not part of the default drawing. By selecting (interior) tetrahedra and deselecting regular triangles you can see the tetrahedra behind the boundary. The different color indicates you see something behind the surface. To make the difference more obvious explode the shape by pushing the up-arrow. You see the tetrahedra flying apart. If you now select regular triangles again you see both, the tetrahedra and the gold regular triangles detached from the tetrahedra by explosion. For rank 173 there are no singular simplices at all, so let us change to rank 91. Do not forget to push the alpha shape button in the scene panel to execute the rank selection graphically. Select the default simplices (singular vertices, singular edges, singular triangles, regular triangles) together with (interior) tetrahedra. Also implode the shape so triangles fit together again without forming gaps. By deselecting and again selecting singular triangles you find out where they are. They disappear without trace so you see there are no tetrahedra behind them. If you deselect regular triangles the hidden tetrahedra appear in different color. This is precisely the definition: singular simplices are not face of any other higher-dimensional simplices in the shape, and regular simplices are. A piece of advice and warning. Alpha shapes for large data sets and high rank tend to have many interior simplices. Drawing these simplices is in general not advised because it slows down the graphics, and in most cases it is not effective because they are hidden behind the boundary. There are some more options in the viewing window. For example, there is the pull-down menu `File'. With `Save Simplex List' you can save simplices of the currently displayed shape in a file, and with `Save Alvis Screen' and `Save Signature Screen' you can save images in SGI default rgb format. (Consult README for the format of these files.) Here you also find an `Exit' button, but you can also hit the `Esc' key to quit. By using the pull-down menu `Props', you can select different materials for the boundary (singular and regular) and interior triangles, edges, and vertices. You can also change the background color. If you have a preferred setting, you may set them at start up time using command line options. In the pull-down menu `Help' you find explanations for key bindings, current parameter settings, and signatures. A continuous EXPLOSION is triggered by selecting the up-arrow button to the left of the word `Explosion' in the scene panel. As long as the button is touched with the mouse the explosion continues. The separation between the simplices admits a visual inspection of the way they fit together. Selecting the down-arrow to the right of `Explosion' reverses the explosion until the simplices fit together without gaps. Let us now display objects or shapes which we call VOIDS, POCKETS, and DIFFERENCE SHAPES. These are open or partially open shapes, that is, the entire boundary or part of the boundary is missing. The different color of interior tetrahedra indicates where boundary is missing. It would be rather confusing if interior tetrahedra would not be drawn, so whenever you click on `Voids', `Pockets', or `Difference' the interior tetrahedra button in the simplex matrix is turned on automatically. To try specific examples move the rank cursor to 163 and select voids. You see a cycle of 32 voids; you know there are 32 from the voids signature. Some of the voids seem to share simplices but the do not since each void is an open set. You can find out which tetrahedra belong to the same void and which do not by selecting interior triangles in the simplex matrix and observing where they glue tetrahedra and where they are missing. A good rank for viewing pockets is 101. The alpha shape is a torus with openings all around its outside. By pushing `pockets' the ``inside'' of the torus is filled with tetrahedra all the way to the openings, which are closed by what we call mouth triangles. For a definition of pockets refer to reference [12]. Finally, select `Difference' for rank 196, maybe. The result is the set of simplices that belong to the Delaunay complex and not to the alpha shape of rank 196. We will see shortly how the Delaunay complex can be replaced by another alpha complex, of rank 196 or higher. We believe that pockets and voids are important new concepts that warrant a specialized panel, the POCKET PANEL. It can be opened using the `Gizmos' pull-down menu. Click on `Pocket Panel' and a 4th window below the signature panel appears. It contains its own signature display and a few extra buttons that can be used to control the selection and display primarily of pockets, although some of the functions also apply to voids and difference shapes. The pocket signature window has two rank cursors: one is a copy of the rank cursor in the signature panel (it is always at the same position), the other can be changed using the left mouse button to the `<' and `>' buttons that allow finer control. Suppose the chosen ranks are 101 and 170. Pushing `Difference' in the scene panel now constructs the set of simplices in the alpha shape of rank 170 that are not in the alpha shape of rank 101. For pockets the effect of the second rank cursor is more difficult to explain. Intuitively, 170 is an upper bound on the size of pocket tetrahedra: if a tetrahedron is not the alpha shape of rank 170 then it cannot be part of any pocket between 101 and 170. This explanation is over-simplification because the omission of this tetrahedron may cause other tetrahedra to be removed from the pockets, etc. In this specific example, there are 8 pockets, each with 4 mouths or more. By moving the second cursor to 172 the pockets merge and form a single pocket filling the inside of the torus. The second rank has no influence on computing voids. The pockets panel has quite a few other features which are worthwhile exploring. The pocket signatures can be selected and displayed the same way as the signatures of alpha shapes. However, the collection of signatures is somewhat different as they apply to pockets rather than alpha shapes. For example, take the #pockets signature. It starts at the first rank, 101, and ends at the last possible rank, 218, which corresponds to the Delaunay complex. The signature indicates the number of pockets for this fixed first rank and for varying choices of the second rank. If the first rank is changed in the signature panel, then all pocket signatures are recomputed when `Pockets' is pushed in the scene panel. Changing the second rank does not affect the signatures. Another feature in the pocket panel is the shapewire toggle button. It complements the displayed pockets or voids with the wireframe of the alpha shape of the first rank, 101. This way it is easy to see where a pocket or void is located relative to the alpha shape. The up-arrow and down-arrow buttons in the lower right corner of the pocket panel allow you to step through the list of pockets. The sequence starts with all pockets shown at once and then progresses through a sequence of the pockets. Rather than looking at all pockets, you can also limit the collection to all pockets with no mouth, or all pockets with 1 mouth, or all pockets with 2 mouths, or all pockets with at least 3 mouths. It should be mentioned that it is sometimes difficult to count the number of mouths of a pocket graphically by looking at the yellow mouth triangles. Take pocket 8, for example, which you get by pushing the down-arrow of the step through function once. It seems there are 3 mouths, 2 on the ends of the drum-like pocket and 1 along the outside of the torus. However, the 8 mouth triangles on the outside of the torus are not glued by mouth edges and really form 8 individual mouths. _______________________________________________________________________________ Volbl (VOLume of BaLl union -- measuring the union of spherical balls) A molecule is often modeled as the union of balls in three-dimensional Euclidean space. Each ball represents an atom, and its size is determined by the van der Waals radius of the atom. The union is commonly referred to as the space filling diagram of the molecule. This program, Volbl, can be used to measure the union of balls, ie, compute its volume, surface area, total arc length, and number of corners. It can also compute the contributions to the surface of individual atoms or balls. A void is defined as a region of space completely surrounded by balls. Volbl also measures the voids of a ball union. Volbl can be called only after the input file has been processed by Delcx and Mkalf. Assuming that you have the files molecule, molecule.{dt,alf,info} in your working directory, you can start the program by issuing the following command: % volbl molecule First, you are asked to enter an alpha rank, that is the rank of the desired shape you selected, using Alvis or otherwise. Then you need to enter an alpha value consistent with this rank; to be lazy enter any inconsistent value and the program will selects its own consistent value for alpha. Now you are prompted with 5 selections: ENTER a switch: 0 for voids 1 for space filling (or union) 2 for envelope 3 for outside fringe 4 for checking Select the one you want. The program will generate self-explanatory output listing the various measures computed. Enjoy ;-) For more user information, see README.volbl. For more technical details regarding the implementation refer to [6], regarding different models of molecules refer to [9], and regarding the proofs of the formulas underlying the software refer to [7]. _______________________________________________________________________________ FINALE Now is a good time for you to explore our tool on your own. We hope you find it useful. Please note the copyright information that comes with this distribution. What more can we say? We realize that the software still needs work and improvements. Check back with us for new releases. (Alvis lives! ;-)