Grin logo
en de es fr
Shop
GRIN Website
Publish your texts - enjoy our full service for authors
Go to shop › Computer Science - Applied

Delaunay Tetrahedralization and its dual Voronoi Diagrams

Title: Delaunay Tetrahedralization and its dual Voronoi Diagrams

Master's Thesis , 2014 , 27 Pages , Grade: B+

Autor:in: Maria Vineeta (Author)

Computer Science - Applied
Excerpt & Details   Look inside the ebook
Summary Excerpt Details

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.

Excerpt


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.

Excerpt out of 27 pages  - scroll top

Details

Title
Delaunay Tetrahedralization and its dual Voronoi Diagrams
College
Bournemouth University
Course
Msc Computer Animation and Visual Effects
Grade
B+
Author
Maria Vineeta (Author)
Publication Year
2014
Pages
27
Catalog Number
V358125
ISBN (eBook)
9783668444201
ISBN (Book)
9783668444218
Language
English
Tags
voronoi delaunay tetrahedralization tetrahedrons
Product Safety
GRIN Publishing GmbH
Quote paper
Maria Vineeta (Author), 2014, Delaunay Tetrahedralization and its dual Voronoi Diagrams, Munich, GRIN Verlag, https://www.grin.com/document/358125
Look inside the ebook
  • Depending on your browser, you might see this message in place of the failed image.
  • https://cdn.openpublishing.com/images/brand/1/preview_popup_advertising.jpg
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
Excerpt from  27  pages
Grin logo
  • Grin.com
  • Payment & Shipping
  • Contact
  • Privacy
  • Terms
  • Imprint