Detri: Robust 3D Delaunay triangulations

These are the sources to the latest version of Detri [M98]. The code constructs the 3D Delaunay triangulation of a given point set using a variant of the randomized incremental-flip algorithm [J91], [ES96], and [M93]. Detri employs a fast randomized point-location scheme without preprocessing [MSZ96] and achieves robustness by using the SoS symbolic perturbation method [EM90]. Valid input data consists of point sets in arbitrary position, given either in integer or fix-point coordinates.

The distribution includes:

• the author's very own collection of macros and utility functions which helped him to keep his sanity while programming in C,
• the Lia Package: a pretty fast long-integer package, performing +, -, and *, under the assumption that the maximum size of any long-integer number occurring during the computations, is known in advance, and
• the SoS Library: an implementation of a set of relevant SoS primitives.

        tar -zxf detri_2.9www.tar
        cd detri_2.9www/
        make detri_new [CC="gcc [-ansi]"]
        cd ../

The ANSI C sources are known to compile as they are on the following platforms: SGI Irix, SUN Solaris, DEC Alpha OSF1, and Windows 95/NT (under Developer Studio). They are also reported to compile on a Macintosh (under CodeWarrior) as well as on a Linux PC (GNU's gcc).

The distribution also contains a sample project file for the Developer Studio to get you started under Windows.

There is some documentation in form of README* files in each of the subdirectories.

Questions?