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) ¨C amended
to work with CUDA Toolkit 3.1 Software: version 2.0 (124K) (dated: 20 July 2011) ¨C
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) ¨C
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) ¨C a binary
input files generator for GPU-DT (version 2.0) |
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 2011 School of Computing, National
University of Singapore. |