Full Text:   <3178>

CLC number: TP31; O29

On-line Access: 

Received: 2008-03-28

Revision Accepted: 2008-07-30

Crosschecked: 2009-02-09

Cited: 1

Clicked: 5210

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2009 Vol.10 No.4 P.535-545


Adaptive triangular mesh coarsening with centroidal Voronoi tessellations

Author(s):  Zhen-yu SHU, Guo-zhao WANG, Chen-shi DONG

Affiliation(s):  Institute of Computer Graphics and Image Processing, Department of Mathematics, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s):   littlerain_szy@sohu.com, wgz@math.zju.edu.cn

Key Words:  Triangular mesh, Mesh coarsening, Surface subdivision, Centroidal Voronoi tessellations (CVTs)

Zhen-yu SHU, Guo-zhao WANG, Chen-shi DONG. Adaptive triangular mesh coarsening with centroidal Voronoi tessellations[J]. Journal of Zhejiang University Science A, 2009, 10(4): 535-545.

@article{title="Adaptive triangular mesh coarsening with centroidal Voronoi tessellations",
author="Zhen-yu SHU, Guo-zhao WANG, Chen-shi DONG",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Adaptive triangular mesh coarsening with centroidal Voronoi tessellations
%A Zhen-yu SHU
%A Guo-zhao WANG
%A Chen-shi DONG
%J Journal of Zhejiang University SCIENCE A
%V 10
%N 4
%P 535-545
%@ 1673-565X
%D 2009
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A0820229

T1 - Adaptive triangular mesh coarsening with centroidal Voronoi tessellations
A1 - Zhen-yu SHU
A1 - Guo-zhao WANG
A1 - Chen-shi DONG
J0 - Journal of Zhejiang University Science A
VL - 10
IS - 4
SP - 535
EP - 545
%@ 1673-565X
Y1 - 2009
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A0820229

We present a novel algorithm for adaptive triangular mesh coarsening. The algorithm has two stages. First, the input triangular mesh is refined by iteratively applying the adaptive subdivision operator that performs a so-called red-green split. Second, the refined mesh is simplified by a clustering algorithm based on centroidal Voronoi tessellations (CVTs). The accuracy and good quality of the output triangular mesh are achieved by combining adaptive subdivision and the CVTs technique. Test results showed the mesh coarsening scheme to be robust and effective. Examples are shown that validate the method.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Alliez, P., Gotsman, C., 2003. Recent Advances in Compression of 3D Meshes. Proc. Symp. on Multiresolution in Geometric Modeling, p.53-82.

[2] Alliez, P., Meyer, M., Desbrun, M., 2002. Interactive geometry remeshing. ACM Trans. Graph., 21(3):347-354.

[3] Alliez, P., Cohen-Steiner, D., Devillers, O., Lévy, B., Desbrun, M., 2003a. Anisotropic polygonal remeshing. ACM Trans. Graph., 22(3):485-493.

[4] Alliez, P., Verdiere, E.C., Devillers, O., Isenburg, M., 2003b. Isotropic Surface Remeshing. Proc. Shape Modeling Int., p.49-58.

[5] Alliez, P., Verdiere, E.C., Devillers, O., Isenburg, M., 2005. Centroidal Voronoi diagrams for isotropic surface remeshing. Graph. Models, 67(3):204-231.

[6] Bank, R., Sherman, A., Weiser, A., 1983. Some Refinement Algorithms and Data Structures for Regular Local Mesh Refinement. Scientific Computing IMACS, Amsterdam, North-Holland, p.3-17.

[7] Cignoni, P., Rocchini, C., Scopigno, R., 1998. Metro: measuring error on simplified surfaces. Comput. Graph. Forum, 17(2):167-174.

[8] Cohen, J., Varshney, A., Manocha, D., Turk, G., Weber, H., Agarwal, P., Brooks, F., Wright, W., 1996. Simplification Envelopes. Proc. 23rd Annual Conf. on Computer Graphics and Interactive Techniques, p.119-128.

[9] Cohen-Steiner, D., Alliez, P., Desbrun, M., 2004. Variational Shape Approximation. ACM SIGGRAPH, Los Angeles, California, p.905-914.

[10] Du, Q., Faber, V., Gunzburger, M., 1999. Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev., 41(4):637-676.

[11] Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., Stuetzle, W., 1995. Multiresolution Analysis of Arbitrary Meshes. Proc. 22nd Annual Conf. on Computer Graphics and Interactive Techniques, p.173-182.

[12] El-Sana, J., Varshney, A., 1997. Controlled Simplification of Genus for Polygonal Models. Proc. Visualization, p.403-410, 565.

[13] Frey, P.J., 2000. About Surface Remeshing. Proc. 9th Int. Meshing Roundtable, p.123-136.

[14] Frey, P.J., Borouchaki, H., 1997. Surface Mesh Evaluation. Proc. 6th Int. Meshing Roundtable, p.363-374.

[15] Frey, P.J., Borouchaki, H., 1998. Geometric surface mesh optimization. Comput. Visual. Sci., 1(3):113-121.

[16] Garland, M., 1999. Multiresolution Modeling: Survey & Future Opportunities. Eurographics—State of the Art Reports, p.111-131.

[17] Garland, M., Heckbert, P.S., 1997. Surface Simplification Using Quadric Error Metrics. Computer Graphics Proc., Annual Conf. Series, New York, p.209-216.

[18] Gu, X., Gortler, S.J., Hoppe, H., 2002. Geometry images. ACM Trans. Graph., 21(3):355-361.

[19] Guskov, I., Vidimce, K., Sweldens, W., Schröder, P., 2000. Normal Meshes. Proc. 27th Annual Conf. on Computer Graphics and Interactive Techniques, p.95-102.

[20] Hoppe, H., 1996. Progressive Meshes. Proc. 23rd Annual Conf. on Computer Graphics and Interactive Techniques, p.99-108.

[21] Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W., 1993. Mesh Optimization. Proc. 20th Annual Conf. on Computer Graphics and Interactive Techniques, p.19-26.

[22] Hormann, K., Labsik, U., Greiner, G., 2001. Remeshing triangulated surfaces with optimal parameterizations. Computer-Aided Design, 33(11):779-788.

[23] Kobbelt, L., Campagna, S., Seidel, H., 1998. A General Framework for Mesh Decimation. Proc. Graphics Interface, p.43-50.

[24] Kobbelt, L.P., Vorsatz, J., Labsik, U., Seidel, H., 1999. A shrink wrapping approach to remeshing polygonal surfaces. Comput. Graph. Forum, 18(3):119-130.

[25] Lee, A.W.F., Sweldens, W., Schröder, P., Cowsar, L., Dobkin, D., 1998. MAPS: Multiresolution Adaptive Parameterization of Surfaces. Proc. 25th Annual Conf. on Computer Graphics and Interactive Techniques, p.95-104.

[26] Lindstrom, P., Turk, G., 1998. Fast and Memory Efficient Polygonal Simplification. Proc. Conf. on Visualization, Research Triangle Park, North Carolina, USA, p.279-286.

[27] Lloyd, S., 1982. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2):129-137.

[28] Meyer, M., Desbrun, M., Schröder, P., Barr, A.H., 2002. Discrete Differential Geometry Operators for Triangulated 2-Manifolds. Visualization and Mathematics III, p.35-57.

[29] Peyré, G., Cohen, L., 2006. Geodesic remeshing using front propagation. Int. J. Comput. Vis., 69(1):145-156.

[30] Schroeder, W.J., Zarge, J.A., Lorensen, W.E., 1992. Decimation of Triangle Meshes. Proc. 19th Annual Conf. on Computer Graphics and Interactive Techniques, p.65-70.

[31] Sifri, O., Sheffer, A., Gotsman, C., 2003. Geodesic-based Surface Remeshing. Int. Meshing Roundtable, p.189-199.

[32] Surazhsky, V., Gotsman, C., 2003. Explicit Surface Remeshing. Proc. Eurographics/ACM SIGGRAPH Symp. on Geometry Processing, Aachen, Germany, p.20-30.

[33] Surazhsky, V., Alliez, P., Gotsman, C., 2003. Isotropic Remeshing of Surfaces: A Local Parameterization Approach. Proc. Int. Meshing Roundtable, p.215-224.

[34] Turk, G., 1992. Re-tiling polygonal surfaces. ACM SIGGRAPH Comput. Graph., 26(2):55-64.

[35] Valette, S., Chassery, J., 2004. Approximated centroidal Voronoi diagrams for uniform polygonal mesh coarsening. Comput. Graph. Forum, 23(3):381-389.

[36] Valette, S., Kompatsiaris, I., Chassery, J., 2005. Adaptive Polygonal Mesh Simplification with Discrete Centroidal Voronoi Diagrams. 2nd Int. Conf. on Machine Intelligence, Tozeur, Tunisia, p.655-662.

[37] Valette, S., Chassery, J., Prost, R., 2008. Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams. IEEE Trans. Visual. Comput. Graph., 14(2):369-381.

[38] Vasilescu, M., Terzopoulos, D., 1992. Adaptive Meshes and Shells: Irregular Triangulation, Discontinuities, and Hierarchical Subdivision. Proc. Computer Vision and Pattern Recognition, p.829-832.

[39] Verfürth, R., 1994. A posteriori error estimation and adaptive mesh-refinement techniques. J. Comput. Appl. Math., 50(1-3):67-83.

[40] Zelinka, S., Garland, M., 2002. Permission grids: practical, error-bounded simplification. ACM Trans. Graph., 21(2):207-229.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE