Delaunay Tetrahedralization and its dual Voronoi Diagrams

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.