DeWall 1.0


    NAME

	DeWall: a program for generating 3d Delaunay triangulations

    SYNOPSYS

	dewall [-s[1|2]] [-u nnn] [-p] [-c] [-t] filein [fileout]

    where:

	-s	Turn on statistic informations (descriptive format)
	-s1	Turn on statistic informations (numerical only format)
	-s2	Turn on statistic informations 
		(numerical+descriptive line format)
	-u nnn	Set Uniform Grid size (nnn = no. of cells)
	-p	print the number of tetrahedra built while processing
	-c	Check every tetrahedron is a Delaunay one
	-t	Check for double creating Tetrahedra (caused by num. errors)

	filein	file of points to be triangulated
	fileout triangulation output file


    NOTES

       This program builds the 3D Delaunay triangulation of a set of point
       adopting the DeWall algorithm described in:

       P. Cignoni, C. Montani, R. Scopigno		d
       "A Merge-First Divide and Conquer Algorithm for E
       Delaunay Triangulation"
       CNUCE Internal Report C92/16 Oct 1992
       A PostScript file containing a printable copy of this Internal Report
       is included in this distribution pack. 
  
   INPUT FILE FORMAT

       The point set to be triangulate has the following format:

       n
       x1 y1 z1
       x2 y2 z2
       ...
       xi yi zi
       ...
       xn yn zn

       where n is the number of points in the set, and xi yi zi are their
       cartesian coordinates.

   OUTPUT FILE FORMAT

       The triangulated set is returned with the following format:

       m
       a1 b1 c1 d1
       a2 b2 c2 d2
       ...
       ai bi ci di
       ...
       am bm cm dm

       where m is the number of tetrahedra built, and ai bi ci di are the
       vertex indices of the i-th tetrahedron; such indices are relative
       to the point file.

   OPTIONS
   
   A more detailed description of options follows.

  -s[1|2] Turn on statistic informations; at the end of the run the
	program shows the following report:

   +----- Statistical Informations ----------------------------------------+
   |Points     |Time (sec.)|Tetras     |Faces      |CH Faces   |TetraRadius|
   |  10000    |185.700    |  66445    | 133021    |    262    |  7.849    |
   |UGMakeTetra|Empty Box  | 2nd Box   |Useful 2nd |PntPerFace |CellPerFace|
   |  53019    |    234    |  35027    |   5039    |  10.71    |  22.27    |

 	Most of these Statistical informations have been deviced in order to 
 	debug and evaluate the program, but some of them can be explained more
	accurately in order to show  the good behaviour of Uniform Grid (UG) 
	techniques in Computational Geometry.
	The algorithm use the UG to speed up an incremental construction
	technique that whould have needed an O(n) point scanning for each
	face of the triangulation. Using the UG we reduce the ideal bound
 	to the average value indicated in PntPerFace field.
	Similarly the CellPerFace field says the average number of cells of
	the UG we analyze for each face.

	The -s1 and -s2 options print the same Statistical information
	in a format more easily readable from spreadsheet and statistical
	packages.

  -u nnn    By default the UG size, i.e. the number of cells, is proportional
	to dataset size; this option override that and set UG size to a be nnn

  -p	Print the current number of tetrahedra built while processing. 
	It does not slow down the algorithm appreciabily (in UNIX output
	is buffered).

  -f	These options force the program to do additional internal testing
  	for avoiding that numerical errors cause endless loop of the program.
	They slow down dewall of a 10-20%.

  -c	Tests that each built tetrahedra is a Delaunay one checking that each
	point of the dataset is out of the circumsphere of that tetrahedron. 
	It makes dewall a quadratic algoritm. This option is nearly useless,
 	except for developer for testing the correctnes of the program when
 	experimenting code modifications.


   KNOWN BUGS AND LIMITATIONS

   On some large dataset (over twenty thousands points) the algorithm loops
   or fails, may be due to numerical errors (insufficient numeric precision). 
   DeWall does not manage dataset which contain 4 or more cospherical points; 
   Dewall cannot therefore be applied to regular grid datasets.

   AUTHORS

   This first version of DeWall was written by P. Cignoni, C. Montani and
   R. Scopigno in 1992. This work was supported in part by "Progetto finalizzato
   Sistemi Informatici e Calcolo Parallelo" of the Consiglio Nazionale delle
   Ricerche.