File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: GPU-assisted computation of centroidal voronoi tessellation
  • Basic View
  • Metadata View
  • XML View
TitleGPU-assisted computation of centroidal voronoi tessellation
 
AuthorsRong, G3
Liu, Y1
Wang, W2
Yin, X4
Gu, D4
Guo, X3
 
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
 
CitationIEEE 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.
 
ISSN1077-2626
2012 Impact Factor: 1.898
2012 SCImago Journal Rankings: 1.890
 
DOIhttp://dx.doi.org/10.1109/TVCG.2010.53
 
ISI Accession Number IDWOS: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.

 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorRong, G
 
dc.contributor.authorLiu, Y
 
dc.contributor.authorWang, W
 
dc.contributor.authorYin, X
 
dc.contributor.authorGu, D
 
dc.contributor.authorGuo, X
 
dc.date.accessioned2011-03-21T09:01:58Z
 
dc.date.available2011-03-21T09:01:58Z
 
dc.date.issued2011
 
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.
 
dc.description.natureLink_to_subscribed_fulltext
 
dc.description.uripublished_or_final_version
 
dc.identifier.citationIEEE 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
 
dc.identifier.doihttp://dx.doi.org/10.1109/TVCG.2010.53
 
dc.identifier.epage356
 
dc.identifier.hkuros177888
 
dc.identifier.hkuros194922
 
dc.identifier.isiWOS: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.

 
dc.identifier.issn1077-2626
2012 Impact Factor: 1.898
2012 SCImago Journal Rankings: 1.890
 
dc.identifier.issue3
 
dc.identifier.openurl
 
dc.identifier.pmid21233516
 
dc.identifier.scopuseid_2-s2.0-78651315304
 
dc.identifier.spage345
 
dc.identifier.urihttp://hdl.handle.net/10722/132211
 
dc.identifier.volume17
 
dc.languageeng
 
dc.publisherIEEE. The Journal's web site is located at http://www.computer.org/tvcg
 
dc.publisher.placeUnited States
 
dc.relation.ispartofIEEE Transactions on Visualization and Computer Graphics
 
dc.relation.referencesReferences in Scopus
 
dc.rightsIEEE Transactions on Visualization and Computer Graphics. Copyright © IEEE.
 
dc.rights©2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
 
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
 
dc.subjectCentroidal Voronoi tessellation
 
dc.subjectGraphics hardware
 
dc.subjectL-BFGS algorithm
 
dc.subjectLloyd's algorithm
 
dc.subjectremeshing
 
dc.titleGPU-assisted computation of centroidal voronoi tessellation
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Rong, G</contributor.author>
<contributor.author>Liu, Y</contributor.author>
<contributor.author>Wang, W</contributor.author>
<contributor.author>Yin, X</contributor.author>
<contributor.author>Gu, D</contributor.author>
<contributor.author>Guo, X</contributor.author>
<date.accessioned>2011-03-21T09:01:58Z</date.accessioned>
<date.available>2011-03-21T09:01:58Z</date.available>
<date.issued>2011</date.issued>
<identifier.citation>IEEE Transactions on Visualization and Computer Graphics, 2011, v. 17 n. 3, p. 345-356</identifier.citation>
<identifier.issn>1077-2626</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/132211</identifier.uri>
<description.abstract>Centroidal Voronoi tessellations (CVT) are widely used in computational science and engineering. The most commonly used method is Lloyd&apos;s method, and recently the L-BFGS method is shown to be faster than Lloyd&apos;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. &#169; 2011 IEEE.</description.abstract>
<description.uri>published_or_final_version</description.uri>
<language>eng</language>
<publisher>IEEE. The Journal&apos;s web site is located at http://www.computer.org/tvcg</publisher>
<relation.ispartof>IEEE Transactions on Visualization and Computer Graphics</relation.ispartof>
<rights>IEEE Transactions on Visualization and Computer Graphics. Copyright &#169; IEEE.</rights>
<rights>&#169;2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.</rights>
<rights>Creative Commons: Attribution 3.0 Hong Kong License</rights>
<subject>Centroidal Voronoi tessellation</subject>
<subject>Graphics hardware</subject>
<subject>L-BFGS algorithm</subject>
<subject>Lloyd&apos;s algorithm</subject>
<subject>remeshing</subject>
<title>GPU-assisted computation of centroidal voronoi tessellation</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=1077-2626&amp;volume=17&amp;issue=3&amp;spage=345&amp;epage=356&amp;date=2010&amp;atitle=GPU-assisted+computation+of+Centroidal+Voronoi+Tessellation</identifier.openurl>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1109/TVCG.2010.53</identifier.doi>
<identifier.pmid>21233516</identifier.pmid>
<identifier.scopus>eid_2-s2.0-78651315304</identifier.scopus>
<identifier.hkuros>177888</identifier.hkuros>
<identifier.hkuros>194922</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-78651315304&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>17</identifier.volume>
<identifier.issue>3</identifier.issue>
<identifier.spage>345</identifier.spage>
<identifier.epage>356</identifier.epage>
<identifier.isi>WOS:000286111600007</identifier.isi>
<publisher.place>United States</publisher.place>
<bitstream.url>http://hub.hku.hk/bitstream/10722/132211/1/Content.pdf</bitstream.url>
</item>
Author Affiliations
  1. INRIA Lorraine
  2. The University of Hong Kong
  3. University of Texas at Dallas
  4. Stony Brook University State University of New York