Computing Two-dimensional Constrained Delaunay Triangulation Using Graphics Hardware

Meng Qi, Thanh-Tung Cao, Tiow-Seng Tan

{ qimeng | caothanh | tants}@comp.nus.edu.sg

National University of Singapore

School of Computing

$Description: C:\Documents and Settings\dcstants\Desktop\cdt_files\0.png$ $Description: C:\Documents and Settings\dcstants\Desktop\cdt_files\1.png$ $Description: C:\Documents and Settings\dcstants\Desktop\cdt_files\2.png$ $Description: C:\Documents and Settings\dcstants\Desktop\cdt_files\3.png$ $Description: C:\Documents and Settings\dcstants\Desktop\cdt_files\4.png$

Figure 1: Delaunay triangulation (DT) and constrained Delaunay triangulation (CDT).

Abstract

This paper presents a novel approach, termed GPU-CDT, to compute the constrained Delaunay triangulation (CDT) for a planar straight line graph (PSLG), consisting of points and edges, using the graphics processing unit (GPU). Although there are many algorithms for constructing the 2D CDT using the CPU, there has been no known prior approach using the parallel computing power of the GPU efficiently. For the special case of the CDT problem with PSLGs consisting of just points, which is the normal Delaunay triangulation problem, a hybrid approach has recently been proposed that uses the GPU together with the CPU to partially speed up the computation. Our GPU-CDT works for such special case too, but the whole computation is fully accelerated by the GPU. Our implementation using the CUDA programming model on nVidia GPUs is numerically robust and runs several times faster than any existing CPU algorithms as well as the prior GPU-CPU hybrid approach. This result is reflected in our experiment with both randomly generated PSLGs and real world GIS data, with millions of points and edges.

Categories and Subject Descriptors:

I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling - Geometric algorithms

I.3.1 [Computer Graphics]: Hardware Architecture - Graphics processors

Keywords: GPGPU, Computational Geometry, Voronoi Diagram

Software Download: here (old)

Software Download: New version using an improved 2D Delaunay triangulation algorithm, termed gDel2D is available here (October 2015)

Video (Technical Report, April 2011): click here (28.5M) to download

Video (I3D Conference, March 2012): click here (29.1M) to download

Related Projects: GPU-DT, Quality Mesh, PBA

Technical Report: TRB3/11 (March 2011)

The 2012 ACM Siggraph Symp on Interactive 3D Graphics and Games, 9-11 March, CA, USA, pp 39--46. here

Presentation (I3D Conference, March 2012): click here

Journal Paper: Qi, Cao and Tan, "Computing 2D Constrained Delaunay Triangulation Using the GPU".
IEEE Transactions on Visualization and Computer Graphics, vol 19 (5), 2013, 736--748.
(Invited paper for the special issue on I3D 2012 conference) here or Preprint

This document, cdt.html, has been accessed 686 times since 25-Jun-24 11:57:13 +08. This is the 1st time it has been accessed today.

A total of 412 different hosts have accessed this document in the last 311 days; your host, 18.223.172.149, has accessed it 1 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.