Article: GPU-assisted computation of centroidal voronoi tessellation
(May Require Subscription)
- Publisher Website: 10.1109/TVCG.2010.53
- Scopus: eid_2-s2.0-78651315304
- Find via
-
Citations:
-
Appears in Collections:
| Title | GPU-assisted computation of centroidal voronoi tessellation | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Authors | Rong, G3 Liu, Y1 Wang, W2 Yin, X4 Gu, D4 Guo, X3 | ||||||||||||||||
| Keywords | Centroidal Voronoi tessellation Graphics hardware L-BFGS algorithm Lloyd's algorithm remeshing | ||||||||||||||||
| Issue Date | 2011 | ||||||||||||||||
| Publisher | IEEE. 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 | ||||||||||||||||
| Abstract | Centroidal 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. | ||||||||||||||||
| ISSN | 1077-2626 2011 Impact Factor: 2.215 2011 SCImago Journal Rankings: 0.073 | ||||||||||||||||
| DOI | http://dx.doi.org/10.1109/TVCG.2010.53 | ||||||||||||||||
| ISI Accession Number ID | WOS:000286111600007
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.contributor.author | Rong, G | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| dc.contributor.author | Liu, Y | ||||||||||||||||
| dc.contributor.author | Wang, W | ||||||||||||||||
| dc.contributor.author | Yin, X | ||||||||||||||||
| dc.contributor.author | Gu, D | ||||||||||||||||
| dc.contributor.author | Guo, X | ||||||||||||||||
| dc.date.accessioned | 2011-03-21T09:01:58Z | ||||||||||||||||
| dc.date.available | 2011-03-21T09:01:58Z | ||||||||||||||||
| dc.date.issued | 2011 | ||||||||||||||||
| dc.description.abstract | Centroidal 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.nature | Link_to_subscribed_fulltext | ||||||||||||||||
| dc.description.uri | published_or_final_version | ||||||||||||||||
| dc.identifier.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 | ||||||||||||||||
| dc.identifier.doi | http://dx.doi.org/10.1109/TVCG.2010.53 | ||||||||||||||||
| dc.identifier.epage | 356 | ||||||||||||||||
| dc.identifier.hkuros | 177888 | ||||||||||||||||
| dc.identifier.hkuros | 194922 | ||||||||||||||||
| dc.identifier.isi | WOS:000286111600007
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.issn | 1077-2626 2011 Impact Factor: 2.215 2011 SCImago Journal Rankings: 0.073 | ||||||||||||||||
| dc.identifier.issue | 3 | ||||||||||||||||
| dc.identifier.openurl | | ||||||||||||||||
| dc.identifier.scopus | eid_2-s2.0-78651315304 | ||||||||||||||||
| dc.identifier.spage | 345 | ||||||||||||||||
| dc.identifier.uri | http://hdl.handle.net/10722/132211 | ||||||||||||||||
| dc.identifier.volume | 17 | ||||||||||||||||
| dc.language | eng | ||||||||||||||||
| dc.publisher | IEEE. The Journal's web site is located at http://www.computer.org/tvcg | ||||||||||||||||
| dc.publisher.place | United States | ||||||||||||||||
| dc.relation.ispartof | IEEE Transactions on Visualization and Computer Graphics | ||||||||||||||||
| dc.relation.references | References in Scopus | ||||||||||||||||
| dc.rights | IEEE 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.rights | Creative Commons: Attribution 3.0 Hong Kong License | ||||||||||||||||
| dc.subject | Centroidal Voronoi tessellation | ||||||||||||||||
| dc.subject | Graphics hardware | ||||||||||||||||
| dc.subject | L-BFGS algorithm | ||||||||||||||||
| dc.subject | Lloyd's algorithm | ||||||||||||||||
| dc.subject | remeshing | ||||||||||||||||
| dc.title | GPU-assisted computation of centroidal voronoi tessellation | ||||||||||||||||
| dc.type | Article |
- INRIA Lorraine
- The University of Hong Kong
- University of Texas at Dallas
- Stony Brook University State University of New York