Delaunay Tetrahedralization and its dual Voronoi Diagrams

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

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.