home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.graphics.visualization
- Path: sparky!uunet!haven.umd.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!sdd.hp.com!ux1.cso.uiuc.edu!m.cs.uiuc.edu!mucke
- From: mucke@cs.uiuc.edu (Ernst Mucke)
- Subject: Alvis 1.0 (3D Alpha-Shape Visualizer)
- Message-ID: <mucke.716142977@espresso.cs.uiuc.edu>
- Sender: news@m.cs.uiuc.edu (News Database (admin-Mike Schwager))
- Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
- Date: Thu, 10 Sep 1992 16:36:17 GMT
- Lines: 105
-
- 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
-