Computing Two-dimensional Delaunay Triangulation Using Graphics Hardware

Guodong Rong, Tiow-Seng Tan, Thanh-Tung Cao, Stephanus

{ rongguod | tants | caothanh | stephanu}@comp.nus.edu.sg

National University of Singapore

School of Computing

Abstract

This paper presents a novel approach to compute, for a given point set S in RXR, its Delaunay triangulation T(S). Though prior work mentions the possibility of using the graphics processing unit (GPU) to compute Delaunay triangulations, no known implementation and performance have been reported. Our work uncovers various challenges in the use of GPU for such a purpose. In practice, our approach exploits the GPU to assist in the computation of a triangulation T′ of S that is a good approximation to T(S). From that, the approach employs the CPU to transform T′to T(S). As a major part of the total work is done by the GPU with parallel computing capability, it is a fast and practical approach, particularly for a large number of points (millions with the current state-of-the-art GPU). For such cases, our current implementation can run up to 53% faster on a Core2 Duo machine when compared to Triangle, the well-known fastest Delaunay triangulation implementation.

 CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Geometric algorithms; I.3.1 [Computer Graphics]: Hardware Architecture—Graphics processors

Keywords: Voronoi diagram, GPGPU, computational geometry, graphics hardware

Paper in The Proceedings of ACM Symposium on Interactive 3D Graphics and Games (I3D 2008), Feb 15-17, 2008, Redwood City, CA, USA, pp. 89--97.

Video: click here to download/play the video clip (42M).

Software Download: here

Related Projects: JFA, JFA Variants, Constrained Delaunay, and Quality Mesh

Dated: 15 Feb 2008. 4 March 2009, 30 April, 23 May 2011, 20 Feb 2017

A total of 151 different hosts have accessed this document in the last 148 days; your host, 13.59.38.110, 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.