This repository implements a parallelized implementation of a 2D Delaunay triangulation that computes the local Voronoi/Delaunay neighbor of each point independently. It provides both a multithreaded CPU implementation (via openMP) and a GPU-accelerated implementation. Although other packages accomplish the same goal, the primary benefit of the implementation here is that it computes the local triangulation around each point entirely independently. As such, there are no merge phases to the triangulation, and the GPU implementation can be completed without transfering data back and forth between host and device. We anticipate that this will be particularly usefull in combination with GPU-accelerated implementations of MD-like dynamics on systems whose interactions are specified via local triangulations.
The algorithm used to do this is the one described in Renjie Chen and Craig Gotsman, "Localizing the delaunay triangulation and its parallel implementation." Transactions on Computational Science XX. Springer, Berlin, Heidelberg, 2013. 39-55. Testing suggests that -- on uniformly distributed random point sets in square, periodic domains -- this code can be faster than other 2D GPU-accelerated Delaunay triangulations that we are aware of, such as gDel2D.
The main coding advance in bringing this algorithm from the cpu to the gpu was done by Diogo E. P. Pinto; current testing and optimization being done in collaboration with Daniel M. Sussman.
see "INSTALLATION.md" for a few more details.
- $ cd build/
- $ cmake ..
- $ make
The files triangulation.cpp and computationalTimeScaling.cpp compile into (separate) executables when using the included cmake installation. The first provides an example of using the core classes (described below), and can compare the output triangulation with one generated by CGAL (which we used to test the validity and robustness of the triangulations generated by our code). The second is an executable of convenience as we checked the performance and algorithmic scaling of our code.
The four files associated with the DelaunayGPU class form the heart of this repository, defining a class which can do two major tasks:
- Given a point set, construct the Delaunay triangulation of it in a periodic domain, encoded as a list of neighboring point indices given in counter-clockwise order around each point (together with a separate data structure holding the number of neighbors around each point)
- Given a point set and a candidate triangulation, check whether every circumcircle in the triangulation is, in fact, empty. If not, functions are provided to locally repair the triangulation.
Of note, since the triangulation generated by DelaunayGPU is constructed locally, we have only indirect access to self-consistency checks (i.e., checks that point i being a neighbor of point j implies that point j is a neighbor of point i), such as whether the total number of neighbors is consistent with the euler character of the torus and the number of points in the set.
This code assumes that the triangulation is a "generic" one, where all Voronoi vertices are 3-fold coordinated. It should not be used on point sets where this property may not hold.
A wrapper around CGAL's 2D triangulation algorithms is also provided, for easy comparisons between the triangulations found by DelaunayGPU and those generated by CGAL.
Several functions (on both the cpu and gpu) are defined here, including random-number-generating classes and code to perform spatial sorting of input points. There is also the cellListGPU set of files, which provide a simple structure (cell/bucket) for accelerating searches of local neighbors on both the GPU and CPU, which is used by DelaunayGPU for efficient searching.