Discrete Voronoi Diagrams are a common and powerful tool to handle geometric properties of discrete surfaces. In some geometric processing algorithms, for sake of complexity, one has to work just with a subset of the original data by some process. This work aims to is investigate the process using a particular construction of these subsets by using a Voronoi-based clustering algorithm and Lloyd's relaxation, regarding the adaptivity of the mesh.


Presentation slides [PDF]


Video: spread
Video: genus3_1.9_24c
Video: genus3_500


This work was elaborated under the supervision of Professor Luiz Velho.

Main references

VALETTE, S. et al.- A generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams – IEEE Transactions on Visualization and Computer Graphics (2008)

BOUBEKEUR, T. and ALEXA, M. - Simplification by Stochastic Sampling and Topological Clustering – Computer and Graphics (2009)

DU, Q. et al. - Centroidal Voronoi Tesselations: Applications and Algorithms – SIAM Review (1999)

DU, Q. et al. - Constrained Centroidal Voronoi Tesselations for Surfaces – SIAM Review (2003)

CEDRIM, D. et al. - Simplificação de malhas triangulares baseada no diagrama de Voronoi intrínseco – Sibgrapi2011 - XXIV Conference on Graphics, Patterns and Images - Workshop of Theses and Dissertations (2011)

SACHT, L. K. & PEREIRA, T. S. - Centroidal Voronoi Tesselation on Meshes