home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / graphics / visualiz / 1324 < prev    next >
Encoding:
Text File  |  1992-09-10  |  4.8 KB  |  116 lines

  1. Newsgroups: comp.graphics.visualization
  2. 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
  3. From: mucke@cs.uiuc.edu (Ernst Mucke)
  4. Subject: Alvis 1.0 (3D Alpha-Shape Visualizer)
  5. Message-ID: <mucke.716142977@espresso.cs.uiuc.edu>
  6. Sender: news@m.cs.uiuc.edu (News Database (admin-Mike Schwager))
  7. Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
  8. Date: Thu, 10 Sep 1992 16:36:17 GMT
  9. Lines: 105
  10.  
  11. I'm happy to announce the 1.0 release of Alvis, a 3D alpha-shape visualizer.
  12. This version is a slightly improved version of what we showed at SIGGRAPH'92.
  13. It is ready for anonymous ftp from
  14.  
  15.         ftp.ncsa.uiuc.edu (141.142.20.50),
  16.  
  17. file:
  18.  
  19.         SGI/Alpha-shape/Alvis-1.0.tar.Z
  20.  
  21. Ftp it using binary mode and do a
  22.  
  23.         uncompress Alvis-1.0.tar.Z
  24.         tar  xvfp  Alvis-1.0.tar
  25.  
  26. which will create a directory Alvis-1.0 with the SGI executables
  27. of the 1.0 release, including README files and some sample data.
  28.  
  29. System requirements:
  30.  
  31.         o SGI workstation running Irix 4.0 or later.
  32.         o 32 MB memory advisable.
  33.         o Alvis-1.0 release needs less than 2 MB disk space.
  34.  
  35. Contact address:
  36.  
  37.         alpha@ncsa.uiuc.edu
  38.  
  39. Find attached excerpts from the README file shortly discribing the
  40. concept of three-dimensional alpha shapes.
  41.  
  42. Enjoy, and remember...
  43.  
  44.  This is a new kind of SHAREWARE.  You share your science and experiences
  45.  with us, and we attain the resources necessary to share more software like
  46.  Alvis with YOU.
  47.  
  48. --Ernst.
  49.  
  50. ------------------------ snip ------------ snip ----------------------------
  51. Copyright (c) 1991, 1992 The Board of Trustees of the University of Illinois
  52.  
  53. ...
  54.  
  55. Three-dimensional Alpha Shapes
  56.  
  57. Frequently, data in scientific computing is in its abstract form a finite
  58. point set in space, and it is sometimes useful or required to compute what one
  59. might call the "shape" of the set.  For that purpose, we introduced the formal
  60. notion of the family of alpha shapes of a finite point set in 3D space, R^3;
  61. see [1].  Each shape is a polytope, derived from the Delaunay triangulation of
  62. the point set, with a parameter alpha controlling the desired level of detail.
  63. The employed algorithms construct the entire family of shapes for a given set
  64. of size n in worst-case time O(n^2).
  65.  
  66. Conceptually, alpha shapes are a generalization of the convex hull of a point
  67. set.  Let S be a finite set in R^3 and alpha a non-negative real number.  The
  68. alpha shape of S is a polytope that is neither necessarily convex nor
  69. connected.  For alpha = infinity, the alpha shape is identical to the convex
  70. hull of S.  However, as alpha decreases, the shape shrinks by gradually
  71. developing cavities.  These cavities may join to form tunnels, and even holes
  72. may appear
  73.  
  74. Intuitively, a piece of the polytope disappears when alpha becomes small
  75. enough so that a sphere with radius alpha, or several such spheres, can occupy
  76. its space without enclosing any of the points of S.  Think of R^3 filled with
  77. Styrofoam and the points of S made of more solid material, such as rock.  Now
  78. imagine a spherical eraser with radius alpha.  It is omnipresent in the sense
  79. that it carves out Styrofoam at all positions where it does not enclose any of
  80. the sprinkled rocks, that is, points of S.  The resulting object is called
  81. the alpha hull.  To make things more feasible, we straighten the object's
  82. surface by substituting straight edges for the circular ones and triangles for
  83. the spherical caps.  The thus obtained object is the alpha shape of S.  It is
  84. a polytope in a fairly general sense: it can be concave and even disconnected,
  85. it can contain two-dimensional patches of triangles and one-dimensional
  86. strings of edges, and its components can be as small as single points.  The
  87. parameter alpha controls the maximum ``curvature'' of any cavity of the
  88. polytope.
  89.  
  90. Refer to [1] for the formal definitons.
  91.  
  92. ...
  93.  
  94. REFERENCES
  95.  
  96. The alpha shape programs are based on the theory of alpha shapes, Delaunay 
  97. triangulations, and simulated perturbation.  There are three main papers 
  98. that had a significant influence on the program development.
  99.  
  100. [1] Herbert Edelsbrunner and Ernst Mucke. Three-dimensional alpha shapes.
  101.     To appear in Computer Graphics. Proceedings to the Boston Volume
  102.     Visualization Workshop, 1992.
  103.  
  104. [2] Barry Joe.  Construction of three-dimensional Delaunay triangulations
  105.     using local transformations.  Computer Aided Geometric Design, volume 8,
  106.     number 2, pages 123-142, 1991.
  107.  
  108. [3] Herbert Edelsbrunner and Ernst Mucke.  Simulation of Simplicity:
  109.     a technique to cope with degenerate cases in geometric algorithms.
  110.     ACM Transactions on Graphics, volume 9, number 1, pages 66-104, 1990.
  111.  
  112. --
  113. --        
  114. Ernst Mucke,   Dept of Computer Science,  U of Illinois at Urbana-Champaign
  115. mucke@uiuc.edu  {convex,uunet}!uiucdcs!mucke  mucke%uiuc.edu@uiucvmd.bitnet
  116.