Mesh clustering by approximating centroidal voronoi tessellation

Fan Fengtao; Cheng Fuhua; Huang Conglin; Li Yong; Wang Jianzhong; Lai Shuhua

doi:10.1145/1629255.1629294

Mesh clustering by approximating centroidal voronoi tessellation

Fan Fengtao, Cheng Fuhua, Huang Conglin, Li Yong, Wang Jianzhong, Lai Shuhua

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

An elegant and efficient mesh clustering algorithm is presented. The faces of a polygonal mesh are divided into different clusters for mesh coarsening purpose by approximating the Centroidal Voronoi Tessellation of the mesh. The mesh coarsening process after clustering can be done in an isotropic or anisotropic fashion. The presented algorithm improves previous techniques in local geometric operations and parallel updates. The new algorithm is very simple but is guaranteed to converge, and generates better approximating meshes with the same computation cost. Moreover, the new algorithm is suitable for the variational shape approximation problem with L2,1 distortion error metric and the convergence is guaranteed. Examples demonstrating efficiency of the new algorithm are also included in the paper.

Original language	English
Title of host publication	Proceedings - SPM 2009
Subtitle of host publication	SIAM/ACM Joint Conference on Geometric and Physical Modeling
Pages	301-306
Number of pages	6
DOIs	https://doi.org/10.1145/1629255.1629294
State	Published - 2009
Event	SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling - San Francisco, CA, United States Duration: Oct 5 2009 → Oct 8 2009

Publication series

Name	Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling

Conference

Conference	SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling
Country/Territory	United States
City	San Francisco, CA
Period	10/5/09 → 10/8/09

Keywords

Centroidal voronoi tessellation
Mesh clustering
Shape approximation

ASJC Scopus subject areas

Computational Theory and Mathematics
Computer Science Applications
Computer Vision and Pattern Recognition
General Mathematics

Access to Document

10.1145/1629255.1629294

Cite this

Fengtao, F., Fuhua, C., Conglin, H., Yong, L., Jianzhong, W., & Shuhua, L. (2009). Mesh clustering by approximating centroidal voronoi tessellation. In Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling (pp. 301-306). Article 1629294 (Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling). https://doi.org/10.1145/1629255.1629294

@inproceedings{79971e1ebdbb464cbf63cb4020cf39da,

title = "Mesh clustering by approximating centroidal voronoi tessellation",

abstract = "An elegant and efficient mesh clustering algorithm is presented. The faces of a polygonal mesh are divided into different clusters for mesh coarsening purpose by approximating the Centroidal Voronoi Tessellation of the mesh. The mesh coarsening process after clustering can be done in an isotropic or anisotropic fashion. The presented algorithm improves previous techniques in local geometric operations and parallel updates. The new algorithm is very simple but is guaranteed to converge, and generates better approximating meshes with the same computation cost. Moreover, the new algorithm is suitable for the variational shape approximation problem with L2,1 distortion error metric and the convergence is guaranteed. Examples demonstrating efficiency of the new algorithm are also included in the paper.",

keywords = "Centroidal voronoi tessellation, Mesh clustering, Shape approximation",

author = "Fan Fengtao and Cheng Fuhua and Huang Conglin and Li Yong and Wang Jianzhong and Lai Shuhua",

year = "2009",

doi = "10.1145/1629255.1629294",

language = "English",

isbn = "9781605587110",

series = "Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling",

pages = "301--306",

booktitle = "Proceedings - SPM 2009",

note = "SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling ; Conference date: 05-10-2009 Through 08-10-2009",

}

Fengtao, F, Fuhua, C, Conglin, H, Yong, L, Jianzhong, W & Shuhua, L 2009, Mesh clustering by approximating centroidal voronoi tessellation. in Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling., 1629294, Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling, pp. 301-306, SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling, San Francisco, CA, United States, 10/5/09. https://doi.org/10.1145/1629255.1629294

Mesh clustering by approximating centroidal voronoi tessellation. / Fengtao, Fan; Fuhua, Cheng; Conglin, Huang et al.
Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling. 2009. p. 301-306 1629294 (Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Mesh clustering by approximating centroidal voronoi tessellation

AU - Fengtao, Fan

AU - Fuhua, Cheng

AU - Conglin, Huang

AU - Yong, Li

AU - Jianzhong, Wang

AU - Shuhua, Lai

PY - 2009

Y1 - 2009

N2 - An elegant and efficient mesh clustering algorithm is presented. The faces of a polygonal mesh are divided into different clusters for mesh coarsening purpose by approximating the Centroidal Voronoi Tessellation of the mesh. The mesh coarsening process after clustering can be done in an isotropic or anisotropic fashion. The presented algorithm improves previous techniques in local geometric operations and parallel updates. The new algorithm is very simple but is guaranteed to converge, and generates better approximating meshes with the same computation cost. Moreover, the new algorithm is suitable for the variational shape approximation problem with L2,1 distortion error metric and the convergence is guaranteed. Examples demonstrating efficiency of the new algorithm are also included in the paper.

AB - An elegant and efficient mesh clustering algorithm is presented. The faces of a polygonal mesh are divided into different clusters for mesh coarsening purpose by approximating the Centroidal Voronoi Tessellation of the mesh. The mesh coarsening process after clustering can be done in an isotropic or anisotropic fashion. The presented algorithm improves previous techniques in local geometric operations and parallel updates. The new algorithm is very simple but is guaranteed to converge, and generates better approximating meshes with the same computation cost. Moreover, the new algorithm is suitable for the variational shape approximation problem with L2,1 distortion error metric and the convergence is guaranteed. Examples demonstrating efficiency of the new algorithm are also included in the paper.

KW - Centroidal voronoi tessellation

KW - Mesh clustering

KW - Shape approximation

UR - http://www.scopus.com/inward/record.url?scp=70350656080&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350656080&partnerID=8YFLogxK

U2 - 10.1145/1629255.1629294

DO - 10.1145/1629255.1629294

M3 - Conference contribution

AN - SCOPUS:70350656080

SN - 9781605587110

T3 - Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling

SP - 301

EP - 306

BT - Proceedings - SPM 2009

T2 - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling

Y2 - 5 October 2009 through 8 October 2009

ER -

Mesh clustering by approximating centroidal voronoi tessellation

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this