Rubén Penalva's Blog

Features

• Library implementing divide and conquer Delaunay triangulation algorithm based on  “Primitives for the manipulation of general subdivisions and the computation of Voronoi” paper by Guibas and Stolfi.
• Opengl based test checking triangulation correctness (shown in video).

Downloads:

• Video
• Source code

Report

The test is composed of three projects: a library, which imlpements a divide and conquer delaunay triangulation algorithm, and two tests to check its correctness. One of the tests is an opengl application showing the triangulation (watch the video).

The development of the algorithm is based on the quad edge structure proposed by Guibas and Stolfi. It’s easy to implement because the paper is very well explained and it has a pseudocode of the algorithm. I recommend skipping part three of the paper if you don’t want to see the mathematical details. The difficult part of the development was to get a representation of the quad-edge structure in C++.

Technology

• C++
• Opengl
• Glut for Win32
• Microsoft Visual Studio 2008 Proffessional Edition
• Subversion
• Redmine

Develop/Build/Test Machine Specs

• Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
• 3072 Mb RAM
• GeForce GTX 260GS (256 MB)
• Nvidia Driver Version: 181.20
• Microsoft Windows XP Professional SP3 x86

Resources

• “Primitives for the manipulation of general subdivisions and the computation of Voronoi” by Guibas and Stolfi.
• Delaunay Triangulation, Wikipedia
• Triangle: A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator by Jonathan Richard Shewchuk
• Graphics Gems IV.  Chapter “Incremental Delaunay Triangulation” source code, by Dani Lischinski
• Quad-edge Data Structure and Library by Paul Heckbert

This entry was posted on Wednesday, May 20th, 2009 at 12:30 and is filed under Codepixel, Tests. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.