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. © 4 March 09, 10 Jan 10, 27 Jan 10, 19 August 10, 25 Sept 10, 04 Jan
11, 30 April 11, 20 July 11, 24 Oct 11, 27 Oct 15 School of Computing, National University of Singapore. |