The Delaunay tetrahedralization (DT) is one of the most popular and common methods 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 and discuss the result obtained. These points serve as vertices for the tetrahedrons that are a part of the combinatorial structure DT.
3D Delaunay Tetrahedralization is not as optimal as 2D Delaunay triangulations. Implementing them gives rise to several degeneracies, which are quite difficult to handle. In this project, we have implemented a simple Incremental Insertion Algorithm based on the paper presented by Ledoux (2007), inorder to construct the DT structure. Correctness of the structure is given utmost importance rather than its speed.
Inhaltsverzeichnis (Table of Contents)
- Introduction
- Related work
- Mesh Sampling
- Ray Intersection
- Signed Distance Field
- Constructing DT
- Initialisation
- Predicates
- Robustness
- Point Location
- Walking
- Incremental flip based Algorithm
- Two Dimension
- Three dimension
- Degeneracies
- Time Complexity
- Duality between DT and VD
- Implementation
- Algorithm InsertOnePoint(T,p)
- Algorithm: FLIP(T,Ta)
- Robustness
- Results
- Conclusion
- Limitations
- Future goals
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
The main objective of this project is to implement a robust Delaunay Tetrahedralization structure for a set of points generated from sampling a given 3D mesh. The project explores two methods for obtaining points within the mesh volume and discusses the results achieved. The project focuses on creating a correct and robust DT structure, even if it means compromising speed.
- Delaunay Tetrahedralization (DT) and its application in 3D mesh fracturing
- Mesh sampling techniques (Ray Intersection and Signed Distance Field)
- Incremental Insertion Algorithm for DT construction
- Robustness and handling degeneracies in DT
- Duality between DT and Voronoi Diagram (VD)
Zusammenfassung der Kapitel (Chapter Summaries)
Chapter 1 introduces the concept of Delaunay Tetrahedralization and its relevance in 3D mesh fracturing. It highlights the need for efficient computation of Voronoi Diagrams, which are dual to DT, for applications in visual effects pipelines. The chapter also explains the principles of Delaunay Triangulation and its extension to higher dimensions, specifically Tetrahedralization, which forms the foundation of this project.
Chapter 2 explores existing work related to Delaunay Tetrahedralization, discussing its applications in various fields.
Chapter 3 delves into the methods used to generate points inside a 3D mesh. Two techniques, Ray Casting and SDF, are presented and discussed.
Chapter 4 focuses on the construction of Delaunay Tetrahedrons and the various algorithms employed in this process. The chapter emphasizes the Incremental Insertion Algorithm used in this project, including its sub-chapters discussing the handling of degeneracies.
Chapter 5 provides details about the implementation of the chosen algorithm, highlighting the challenges encountered and the limitations of the approach.
Schlüsselwörter (Keywords)
The key terms and concepts addressed in this text are Delaunay Tetrahedralization, 3D mesh fracturing, Voronoi Diagram, mesh sampling, Ray Intersection, Signed Distance Field, Incremental Insertion Algorithm, robustness, degeneracies, and duality between DT and VD.
- Arbeit zitieren
- Maria Vineeta (Autor:in), 2014, Delaunay Tetrahedralization and its dual Voronoi Diagrams, München, GRIN Verlag, https://www.grin.com/document/358125
