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.
Table of Contents
1 Introduction
2 Related work
3 Mesh Sampling
3.1 Ray Intersection
3.2 Signed Distance Field
4 Constructing DT
4.1 Initialisation
4.2 Predicates
4.2.1 Robustness
4.3 Point Location
4.3.1 Walking
4.4 Incremental flip based Algorithm
4.4.1 Two Dimension
4.4.2 Three dimension
4.4.3 Degeneracies
4.4.4 Time Complexity
4.5 Duality between DT and VD
5 Implementation
5.1 Algorithm : InsertOnePoint(T,p)
5.2 Algorithm : FLIP(T,Ta)
5.3 Robustness
5.4 Results
6 Conclusion
6.1 Limitations
6.2 Future goals
Research Objectives and Core Topics
The primary objective of this thesis is to implement a robust 3D Delaunay Tetrahedralization (DT) algorithm, facilitating the extraction of its dual, the Voronoi Diagram, for applications in 3D mesh fracturing. The research addresses the challenges of point sampling within mesh volumes and the geometric complexities involved in constructing reliable tetrahedral structures.
- Mesh sampling techniques including Ray Intersection and Signed Distance Fields (SDF).
- Incremental insertion algorithms for constructing Delaunay Tetrahedralizations.
- Geometric predicates and the necessity of robust arithmetic in computational geometry.
- Handling degeneracies and maintaining structural integrity during flip operations.
- Duality and transformation between Delaunay structures and Voronoi diagrams.
Excerpts from the Book
Constructing DT
There are several paradigms in computational geometry for computing the DT in two and three dimensions. However, constructing a DT in three dimensions is quite complicated. In this thesis we have used Incremental insertion algorithm, as this has the complexity O(n^2) which is worst case optimal. With this algorithm, every point is inserted into the DT one at a time. The tetrahedra containing the newly added 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-Watson(1981) is 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. The rest of this chapter we discuss the Incremental Flip-based algorithm.
Summary of Chapters
1 Introduction: Provides an overview of mesh generation, the importance of Delaunay Tetrahedralization in 3D fracturing pipelines, and defines the thesis objectives.
2 Related work: Reviews the historical evolution of Delaunay triangulation and existing algorithms, focusing on incremental insertion, divide-and-conquer, and sweep-line approaches.
3 Mesh Sampling: Discusses methods for generating point samples inside a 3D mesh, comparing Ray Intersection and Signed Distance Field techniques.
4 Constructing DT: Details the theory behind incremental insertion, geometric predicates (Orient, InSphere), flip-based algorithms, and the duality between DT and Voronoi diagrams.
5 Implementation: Describes the C++ development of the DT algorithm, practical challenges regarding robust arithmetic, and results from testing on various mesh types.
6 Conclusion: Summarizes the thesis findings, discusses limitations regarding convex input requirements, and suggests future research directions.
Keywords
Delaunay Tetrahedralization, Voronoi Diagram, Incremental Insertion, Mesh Generation, 3D Fracturing, Computational Geometry, Signed Distance Field, Ray Intersection, Robust Arithmetic, Bistellar Flips, Tetrahedral Mesh, Geometric Predicates, Degeneracies, Spatial Sampling, C++
Frequently Asked Questions
What is the core focus of this research?
The research focuses on the robust implementation of 3D Delaunay Tetrahedralization to facilitate mesh fracturing, specifically using incremental insertion techniques.
Which algorithms are discussed for building the DT structure?
The work compares the Bowyer-Watson algorithm and flip-based algorithms, ultimately implementing an incremental flip-based approach for its lower error profile.
What is the primary goal of the sampling methods?
The sampling methods aim to generate points effectively within the volume of a 3D mesh, which is a necessary prerequisite for performing tetrahedralization in fracturing applications.
How is the robustness issue addressed?
The project addresses robustness by adopting exact arithmetic techniques as proposed by Shewchuck (1997), using them primarily to determine the signs of determinants to prevent numerical errors.
What is the role of the dual Voronoi Diagram?
The Voronoi Diagram is the dual of the DT; it is essential for fracturing pipelines, and the thesis demonstrates how it can be extracted directly from the constructed DT structure.
Which primary keywords characterize this work?
Key terms include Delaunay Tetrahedralization, 3D Fracturing, Incremental Insertion, Voronoi Diagrams, and computational geometry robustness.
Why did the author choose SDF over Ray Intersection?
SDF was found to be more efficient and reliable for complex or concave meshes, whereas Ray Intersection was computationally slower and more prone to generating erroneous points outside the mesh boundaries.
What are the main limitations identified in the final chapter?
The primary limitation is that the current DT implementation requires convex input meshes and can experience performance issues or crashes when handling very high-density point datasets.
- Arbeit zitieren
- Maria Vineeta (Autor:in), 2014, Delaunay Tetrahedralization and its dual Voronoi Diagrams, München, GRIN Verlag, https://www.grin.com/document/358125
