Triangulation of unstructured datasets
The visualization of scattered or curvilinear datasets has been the basis for some
intense work on Computational Geometry. The need to represent and manage datasets with no
topological organization was the reason for our interest in triangulation algorithms, and
particularly Delaunay tesselations.
The tesselation of E3 space into tetrahedra is a very convenient data structure
allowing easy visualization (e.g., surface fitting over tetrahedral cell is
straightforward and also direct rendering techniques are available based on cell
projection or ray tracing).
Two different algorithms for the construction of Delaunay triangulations in 3D space have
been defined. The first one, InCoDe, is
an optimized incremental algorithm; it extends an existing 2D algorithm to higher spaces
and makes use of a data bucketing technique (Uniform Grid) to improve the search for new
points to be added to the triangulation.
The second, called DeWall, is based on the Divide &
Conquer paradigm. In order to avoid the merging phase of a classic Divide & Conquer
algorithm (this phase is not feasible in spaces with a dimension higher than 2), DeWall
first splits the dataset into two partitions, then it builds the part of the solution
which should be produced during the merging phase (a wall of tetrahedra in E3)
and then recursively operates on the two partitions. One of the main characteristics of
this new algorithm is its generality: it can be easily implemented to manage pointsets in
any dimension. This solution is characterized by a very simple structure and high
efficiency, and presents a measured O(n log n) behavior on a number of test datasets in E3.
An implementation of the InCoDe and DeWall triangulators in three-dimensional space
has been released in public domain; the codes are briefly described in the downloads
page.
DeWall: a fast divide & conquer Delaunay
triangulation algorithm in Ed 
P. Cignoni, C. Montani, and R. Scopigno
Computer-Aided Design., Elsevier Science, Vol.30(5), April 1998, pp.333- 341.
Abstract
The paper deals with Delaunay Triangulations (DT) in Ed space.
This classic computational geometry problem is studied from the point of view of the
efficiency, extendibility to any dimensionality, and ease of implementation.
A new solution to DT is proposed, based on an original interpretation of the well-known
Divide and Conquer paradigm. One of the main characteristics of this new algorithm is its
generality: it can be simply extended to triangulate point sets in any dimension. The
technique adopted is very efficient and presents a subquadratic behaviour in real
applications in Ed, although its computational complexity does not improve the
theoretical bounds reported in the literature.
An evaluation of the performance on a number of datasets is reported, together with a
comparison with other DT algorithms.