Publications by year

2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  

Most documents on this website are protected by copyright. By clicking on a PDF icon, you confirm that you or your institution has the right to do so. Note that the definitive versions of all EG papers (Eurographics,...) can be downloaded from ACM papers (Siggraph, ...) can be downloaded from


“Restricted Voronoi Diagrams for (Re)-Meshing Surfaces and Volumes”
Bruno Lévy
Curves and Surfaces, 2014

Abstract: We propose an efficient and robust algorithm to compute the intersection between a Voronoi diagram and a simplicial complex, possibly embedded in high dimensional space (typically 6d to 10d). Such a high-dimensional setting is interesting for some anisotropic mesh generation algorithms. Efficiency is obtained from a simple characterization of the bisectors that contribute to each Voronoi cell. This observation results in an algorithm that is practical even in high-dimensional space. Robustness is obtained through a combination of arithmetic filters, expansion arithmetics and symbolic perturbation. To avoid degeneracies, similarly to what is done for the in-sphere predicate, we consider the Voronoi diagram as a power diagram with all its weights set to zero, and apply symbolic perturbation to the weights. We give the derivation of the three predicates (resp. four) used by the surfacic (resp. volumetric) versions of the algorithm. All the derivations are expressed in function of the dot product (kernel) in the embedding space. The algorithm is implemented in the PCK (Predicate Construction Kit) tool, part of the GEOGRAM library.

BibTex reference

   TITLE      = "Restricted Voronoi Diagrams for (Re)-Meshing Surfaces and Volumes",
   AUTHOR     = "Bruno Lévy",
   BOOKTITLE  = "Curves and Surfaces",
   YEAR       = "2014",

Supplemental material, links, hindsight ...

Implementation is available from this link .