Efficient Computation of 3D Clipped Voronoi Diagram - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2010

Efficient Computation of 3D Clipped Voronoi Diagram

Abstract

The Voronoi diagram is a fundamental geometry structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact 3D domain (i.e. a finite 3D volume), some Voronoi cells of their Voronoi diagram are infinite, but in practice only the parts of the cells inside the domain are needed, as when computing the centroidal Voronoi tessellation. Such a Voronoi diagram confined to a compact domain is called a clipped Voronoi diagram. We present an efficient algorithm for computing the clipped Voronoi diagram for a set of sites with respect to a compact 3D volume, assuming that the volume is represented as a tetrahedral mesh. We also describe an application of the proposed method to implementing a fast method for optimal tetrahedral mesh generation based on the centroidal Voronoi tessellation.
Fichier principal
Vignette du fichier
main.pdf (3.66 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00547794 , version 1 (17-12-2010)

Identifiers

Cite

Dong-Ming Yan, Wenping Wang, Bruno Lévy, Yang Liu. Efficient Computation of 3D Clipped Voronoi Diagram. Geometric Modeling and Processing, University of Cantabria, Jun 2010, Castro Urdiales, Spain. pp.269-282, ⟨10.1007/978-3-642-13411-1_18⟩. ⟨inria-00547794⟩
268 View
506 Download

Altmetric

Share

Gmail Facebook X LinkedIn More