My Programming Space: Masters Project

Delaunay Tetrahedralization and its dual Voronoi Diagrams

The Delaunay tetrahedralization is one of the most popular and common method used for solving problems related to meshes. It is either used for generating a mesh or for breaking it up, as Voronoi diagrams, dual of the DT is a commonly used process for that. The main task of this project is to implement a robust Delaunay Tetrahedralization structure, with a set of points generated from sampling a given 3D Mesh.

Points within the volume of the mesh can be obtained by several methods. We present two such methods for Mesh Sampling : Ray Intersection and SDF(Signed Distance Field).

Mesh Sampling from Maria Vineeta on Vimeo.

These points serve as vertices for the tetrahedrons that are a part of the combinatorial structure DT.

In this project we have used Incremental insertion algorithm, has a complexity which is worst case-optimal. With this algorithm, every point is inserted into the DT one at a time. The tetrahedra containing the newlyadded point is partitioned and new tetrahedrons are created thus updating the DT structure.

By inserting each point one at a time, we observe that only the Delaunay tetrahedra local to the point is altered and not the entire structure. Whereas in the other two paradigm, divide-and-conquer and sweep plane, the entire structure is built in a single operation. Inserting a new vertex would result in computing the whole structure again. Hence, incremental insertion is mandatory when a dynamic spatial model is built. The insertion of a single point can be achieved with two incremental insertion algorithms

1) the Bowyer-Watson algorithm and

2) flip-based algorithm.

The idea behind Bowyer-Watsons very simple. Tetrahedrons that does not satisfy the Delaunay criterion when a point is inserted, are deleted. However, this method is prone to errors as it forms a ‘gap’ or ‘hole’ when the tetrahedrons are deleted and affects the overall topological structure as well. Hence, flip based algorithm is preferred over the former.