Home        Presentation       Codes       Results       Acknowledgements


This home page is part of the final project of the Computational Geometry Course at IMPA o. Here you find the slides of the presentation on November 18th, some pictures with the results and all the code in C++ language.

The authors of this project are the master candidates Thiago S. Pereira and Leonardo K. Sacht. For more information about them, check their home pages.

These are some results that we got. For more, check the results section.

image image image

CVT with exponential density

CVT with curvature density

Normal Clustering


We intend to present and implement the basic ideas of CVT's on surfaces and make the algorithms as flexible as possible, in order to use them with many metrics and density functions.

We explore the ideas of the Variational Shape Approximations (VSA) to create Normal Clustering and mix these ideas with CVT's.

On the future, we'll use such implementations for other works involving texture atlas and segmentation of the viewing sphere to obtain good panoramas. Actually, this was our motivation for choosing this theme.


[1] D. Cohen-Steiner, P. Alliez, M. Desbrun: Variational Shape Approximation. ACM Siggraph Papers, pp. 905-914, 2004.
[2] Q. Du, V. Faber, M. Gunzburger: Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM Review, Vol. 41, No. 4, pp. 637-676, 1999.
[3] Q. Du, M. Gunzburger, L. Ju: Constrained Centroidal Voronoi Tessellations on General Surfaces. Report No. AM253, Math. Dept., Penn State, 2002.
[4] G. Peyre, L. Cohen: Surface Segmentation Using Geodesic Centroidal Tessellation. Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, IEEE Computer Society 2004.

Project by Thiago Pereira and Leonardo K. Sacht.