GPU-DT: 2D Delaunay Triangulator using Graphics Hardware

GPU-DT: A 2D Delaunay Triangulator using Graphics Hardware

GPU-DT is a C Library that utilizes graphics hardware to compute exact Delaunay triangulation. The result is a triangle mesh, each contain the index of its 3 vertices and the three neighbor triangles.

Software: version 1.0 (96K) (dated: 4 March 2009)

Software: version 1.1 (100K) (dated: 27 January 2010)

Software: version 1.1.1 (98K) (dated: 25 September 2010) – amended to work with CUDA Toolkit 3.1

Software: version 2.0 (124K) (dated: 20 July 2011) – amended to work with CUDA Toolkit 3.2; amended to handle edges specified before hand (i.e. constrained Delaunay triangulation); amended to be suitable for 64-bit Windows and Linux environment

Software: version 2.1 (112K) (dated: 20 October 2011) – amended to work with CUDA Toolkit 4.0; an optimized version derived from version 2.0

If you use this software and you like it or have comments on its usefulness etc., we would love to hear from you. You may share with us your experience and any possibilities that we may improve the work/code.

Please send bugs and comments to: bug.gpudt AT gmail.com and tants AT comp.nus.edu.sg

Software: Generator (14K) (dated: 20 July 2011) – a binary input files generator for GPU-DT (version 2.0)

Software: gDel2D (dated: 25 October 2015) – a new C++ library that supersedes GPU-DT as the fastest GPU 2D Delaunay Triangulator using the GPU. For more details, please check the README file in the download.

1. Algorithm

Reference: Computing Two-dimensional Delaunay Triangulation Using Graphics Hardware. G.D. Rong, T.S. Tan, Thanh-Tung Cao and Stephanus. The 2008 ACM Symposium on Interactive 3D Graphics and Games, 15--17 Feb, Redwood City, CA, USA, pp. 89--97. See, http://www.comp.nus.edu.sg/~tants/delaunay.html

Remark: Our implementation is an improvement to the algorithm reported in the above reference. The new algorithm is run mainly in GPU instead of GPU+CPU, and is much faster than that reported in the above reference. In particular, it runs up to 4 times faster than the Triangle Software by Shewchuk. An update to the above reference is in preparation and will be posted to the project webpage in due course.

Technical Report TRB 3/11: “Computing 2D Constrained Delaunay Triangulation Using Graphics Hardware”, School of Computing, NUS, March 2011. Project webpage.

Manuscript (submitted for consideration for publication): T.T. Cao, H. Edelsbrunner and T.S. Tan. “Proof of correctness of the digital Delaunay triangulation algorithm”, 2010. pdf file (file updated with 2 new references in April, 2011)

2. Requirement

- CUDA Toolkit version 2.0 and above.

- A GPU capable of running CUDA.

By default, GPUDT performs all floating point computation in Double precision. You can also turn on the definition SINGLE_PRECISION (see gpudt.h) to switch to Single precision mode.

To run GPUDT with Double precision, you need a GPU with compute capability 1.3 (NVIDIA GT200 series onward). In Single precision mode, GPUDT only require a GPU with compute capability 1.1 (NVIDIA G8xxx series onward, except Geforce 8800GTX).

3. GPU Tested

GPUDT has been tested on NVIDIA Geforce 8800GT, 9500GT, GTX280, GTX 460, GTX 470, GTX 560, GTX 580 and Tesla C2050.

4. Zip File

The zip file contains all the source codes necessary to use GPUDT. It also includes a sample Visual Studio project using GPUDT to compute Delaunay Triangle of a randomly uniformly distributed set of 2D points. The computed triangulation is then drawn using OpenGL, and the user can zoom in and move around the triangle mesh. The sample project also demonstrates how to work (by walking from triangle to triangle) with the data structure storing the Delaunay triangulation.

Note: When compiling the CUDA code using Double precision, you have to enable compute capability 1.3 using the switch -sm_13. If you use Single precision, you can use the switch -sm_11.

The project is funded by the National University of Singapore under grant R-252-000-337-112.