File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: GPU-assisted computation of centroidal voronoi tessellation

TitleGPU-assisted computation of centroidal voronoi tessellation
Authors
Rong, GLiu, YWang, WYin, XGu, DGuo, X
KeywordsCentroidal Voronoi tessellation
Graphics hardware
L-BFGS algorithm
Lloyd's algorithm
remeshing
Issue Date2011
PublisherIEEE. The Journal's web site is located at http://www.computer.org/tvcg
Citation
IEEE Transactions on Visualization and Computer Graphics, 2011, v. 17 n. 3, p. 345-356 How to Cite?
DOI: http://dx.doi.org/10.1109/TVCG.2010.53
AbstractCentroidal Voronoi tessellations (CVT) are widely used in computational science and engineering. The most commonly used method is Lloyd's method, and recently the L-BFGS method is shown to be faster than Lloyd's method for computing the CVT. However, these methods run on the CPU and are still too slow for many practical applications. We present techniques to implement these methods on the GPU for computing the CVT on 2D planes and on surfaces, and demonstrate significant speedup of these GPU-based methods over their CPU counterparts. For CVT computation on a surface, we use a geometry image stored in the GPU to represent the surface for computing the Voronoi diagram on it. In our implementation a new technique is proposed for parallel regional reduction on the GPU for evaluating integrals over Voronoi cells. © 2011 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/132211
ISSN
1077-2626
2021 Impact Factor: 5.226
2020 SCImago Journal Rankings: 1.005
ISI Accession Number ID
WOS:000286111600007
Funding AgencyGrant Number
US National Science Foundation (NSF)CCF-0727098
European Research CouncilGOOD-SHAPE FP7-ERC-StG-205693
Research Grant Council of Hong Kong718209
717808
NSFC-Microsoft Research Asia60933008
National 863 High-Tech Program of China2009AA01Z304
NSFCCF-0448399
DMS-9626223
DMS-0523363
CCF-0830550
ONRN000140910228
Funding Information:

The authors would like to thank the anonymous reviewers for their constructive comments. We would like to thank Feng Sun and Dongming Yan for their help on CPU programs for the L-BFGS algorithm, and Vasconcelos for providing her source code. Guodong Rong and Xiaohu Guo are partially supported by the US National Science Foundation (NSF) under Grant No. CCF-0727098. Yang Liu is supported by the European Research Council (GOOD-SHAPE FP7-ERC-StG-205693). Wenping Wang is partially supported by the General Research Funds (718209, 717808) of Research Grant Council of Hong Kong, NSFC-Microsoft Research Asia cofunded project (60933008), and National 863 High-Tech Program of China (2009AA01Z304). Xiaotian Yin and Xianfeng David Gu are partially supported by NSF CAREER CCF-0448399, DMS-9626223, DMS-0523363, CCF-0830550, and ONR N000140910228.

References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorRong, Gen_HK
dc.contributor.authorLiu, Yen_HK
dc.contributor.authorWang, Wen_HK
dc.contributor.authorYin, Xen_HK
dc.contributor.authorGu, Den_HK
dc.contributor.authorGuo, Xen_HK
dc.date.accessioned2011-03-21T09:01:58Z-
dc.date.available2011-03-21T09:01:58Z-
dc.date.issued2011en_HK
dc.identifier.citationIEEE Transactions on Visualization and Computer Graphics, 2011, v. 17 n. 3, p. 345-356en_HK
dc.identifier.issn1077-2626en_HK
dc.identifier.urihttp://hdl.handle.net/10722/132211-
dc.description.abstractCentroidal Voronoi tessellations (CVT) are widely used in computational science and engineering. The most commonly used method is Lloyd's method, and recently the L-BFGS method is shown to be faster than Lloyd's method for computing the CVT. However, these methods run on the CPU and are still too slow for many practical applications. We present techniques to implement these methods on the GPU for computing the CVT on 2D planes and on surfaces, and demonstrate significant speedup of these GPU-based methods over their CPU counterparts. For CVT computation on a surface, we use a geometry image stored in the GPU to represent the surface for computing the Voronoi diagram on it. In our implementation a new technique is proposed for parallel regional reduction on the GPU for evaluating integrals over Voronoi cells. © 2011 IEEE.en_HK
dc.languageengen_US
dc.publisherIEEE. The Journal's web site is located at http://www.computer.org/tvcgen_HK
dc.relation.ispartofIEEE Transactions on Visualization and Computer Graphicsen_HK
dc.rights©2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.-
dc.subjectCentroidal Voronoi tessellationen_HK
dc.subjectGraphics hardwareen_HK
dc.subjectL-BFGS algorithmen_HK
dc.subjectLloyd's algorithmen_HK
dc.subjectremeshingen_HK
dc.titleGPU-assisted computation of centroidal voronoi tessellationen_HK
dc.typeArticleen_HK
dc.identifier.emailWang, W:wenping@cs.hku.hken_HK
dc.identifier.authorityWang, W=rp00186en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/TVCG.2010.53en_HK
dc.identifier.pmid21233516-
dc.identifier.scopuseid_2-s2.0-78651315304en_HK
dc.identifier.hkuros177888en_US
dc.identifier.hkuros194922-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-78651315304&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume17en_HK
dc.identifier.issue3en_HK
dc.identifier.spage345en_HK
dc.identifier.epage356en_HK
dc.identifier.isiWOS:000286111600007-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridRong, G=14619751200en_HK
dc.identifier.scopusauthoridLiu, Y=36065585300en_HK
dc.identifier.scopusauthoridWang, W=35147101600en_HK
dc.identifier.scopusauthoridYin, X=23020392200en_HK
dc.identifier.scopusauthoridGu, D=11638885900en_HK
dc.identifier.scopusauthoridGuo, X=12791011700en_HK
dc.identifier.issnl1077-2626-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats