delaunay3D

Intro

This is the simplest DT (Denaulay Triangulation) algorithm in 3D. Explore combinations of 4 unique points. If this tetrahedron satisfies DT no other point will exist within the sphere through the four points. For each such combination go through and test the sphere against other points.

Since this algorithm generated a tessellation for over a hundred points it is useful to compare with other 3D DT algorithms to ensure that the same mesh was generated. I was surprised that this worked for that many points.

Source

Files

Doxygen

Visual Verification

A cp displays the sphere through one such tetrahedron. By moving in the 3D space you can verify that the other points are outside the sphere. To help you know which tetrahedron is the current tetrahedron in the command line window the tessellation is printed.

Here are some images of verification.

With optimizations CC=g++ -DNDEBUG -O3 -Wall in the makefile, n=120 points took 50 seconds.

$./main n=120