README
----------------------------------------------------------------
1.1 (09 May 2000) (beta)    Lutz Kettner
Requires CGAL 2.1.

Two demo programs and one (stupid) sample object (a sphere ;-)
Includes also a CGAL makefile, a version file, and this README file.

crust_3d.C
----------
    CGAL demo: Surface reconstruction in 3D of an unorganized sequence 
    of input points using the crust algorithm of N. Amenta, S. Choi, 
    T. Dey, N. Leekha: A Simple Algorithm for Homeomorphic Surface 
    Reconstruction. In Proc. 16th Annu. ACM Sympos. Comput. Geom., 2000.

    This program reads points from an input file (or stdin) in the OFF
    or SKEL format known from Geomview. The lines or facets are ignored
    in the input. Geomview is used to visualize the output. The original
    input points, their poles, and the candidate triangles are shown.
    The full algorithm as described in the paper has been implemented
    except the very last step of extracting the outer manifold. The angle
    parameter for the co-cone and definition of sharp edges can be 
    adjusted at the commandline. The algorithm is currently set to use
    an exact number type of CGAL. This can be easily changed to double,
    see the typedef right before the main program. However, even crossed
    fingers might not help and you might get garbage from the
    triangulation.

    See http://www.geom.umn.edu/software/download/geomview.html for Geomview.

    The documentation of the various functions is still sketchy.

    Playing with my program, I come to one of the following conclusions:

       1. I have bugs in my code (please find and report them ;-)
          Actually not too unlikely, since I did this program pretty fast.
          (I did _some_ tests though, honestly)

       2. I just don't have the nice point clouds to see it work
          (send me some if you have).

       3. Crust in 3d is plain useless in practice.

    Why that? My program does not even reconstruct the simplest point
    set, except spheres, which makes me at least a bit confident that 
    I have not gotten the signs wrong. The killer is usually that there 
    is a hole in the surface and that all triangles get removed during 
    the (important) cleanup step starting at the hole. You might want to
    play with the two angle parameters: -sharp -1 does switch off the
    cleanup step completely, and -sharp 0 reduces cleanup to boundary
    edges only. Still, the cleanup usually eats up the real surface
    leaving a bunch of slivers. And without cleanup big triangles 
    of the convex hull clutter the view and many small triangles
    are attached to the real surface.

    There is one detail missing in the paper. The Voronoi edge is used
    in selecting candidate edges, however, there is no Voronoi vertex for
    infinite cells and the edge is actually a ray. The paper doesn't say
    explicitly what to do here. With a bit more time I'll ask Nina
    what they did. I just did a simple hack, I reflected the Voronoi
    vertex of the finite cell at the facet into the infinite cell,
    and scaled its distance up. Now the "Voronoi" edge for this facet 
    gives something reasonable, but maybe way too short compared to 
    the ray ;-)

    Looking for real point cloudes? http://www.cyberware.com/ offers
    samples in PLY format, and also a bunch of converters for PLY. In
    the CGAL distribution under examples/Polyhedron_IO are a couple of
    file convertes around OFF. Raindrop Geomagic offers also a few
    samples at http://www.geomagic.com/ . See also the Stanford
    repository at http://www-graphics.stanford.edu/data/3Dscanrep/ .


sample_points.C
---------------
    CGAL demo: Sample points at random or uniform from a polyhedral 
    surface. Reads an arbitrary OFF file. Writes points in SKEL format,
    which is suitable for crust_3d.C and can also be viewed in Geomview
    showing the individual vertices.

sphere?.off
-----------
    A sphere in various resolutions. Resampling it with the above 
    program actually works also.


---
end