File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Generalized Voronoi Diagram Computation on GPU
  • Basic View
  • Metadata View
  • XML View
TitleGeneralized Voronoi Diagram Computation on GPU
 
AuthorsYuan, Z1
Rong, G2
Guo, X2
Wang, WP1
 
KeywordsJump Flooding Algorithm
Graphics Hardware
Generalized Voronoi Diagram
 
Issue Date2011
 
PublisherIEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1001201
 
CitationThe 8th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2011), Qingdao, China, 28-30 June 2011. In Conference Proceedings, 2011, p. 75-82 [How to Cite?]
DOI: http://dx.doi.org/10.1109/ISVD.2011.18
 
AbstractWe study the problem of using the GPU to compute the generalized Voronoi diagram (GVD) for higher-order sites, such as line segments and curves. This problem has applications in many fields, including computer animation, pattern recognition and so on. A number of methods have been proposed that use the GPU to speed up the computation of the GVD. The jump flooding algorithm (to be called JFA) is such an efficient GPU-based method that is particularly suitable for computing the ordinary Voronoi diagram of point sites. We improve the jump flooding algorithm and apply it to computing the GVD. Specifically, instead of directly propagating the complete information of a site (i.e. the coordinates or other geometric parameters) as in the original JFA, we store the site information in a 1-D texture, and propagate only the IDs, which are short integers, of the sites in another 2D texture to generate the Voronoi diagram. This simple strategy avoids storing redundant data and leads to considerately more accurate computation of the GVD with much less memory than using the original JFA, with only moderate increase of the running time. © 2011 IEEE.
 
ISBN978-076954483-0
 
DOIhttp://dx.doi.org/10.1109/ISVD.2011.18
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorYuan, Z
 
dc.contributor.authorRong, G
 
dc.contributor.authorGuo, X
 
dc.contributor.authorWang, WP
 
dc.date.accessioned2011-09-23T06:04:35Z
 
dc.date.available2011-09-23T06:04:35Z
 
dc.date.issued2011
 
dc.description.abstractWe study the problem of using the GPU to compute the generalized Voronoi diagram (GVD) for higher-order sites, such as line segments and curves. This problem has applications in many fields, including computer animation, pattern recognition and so on. A number of methods have been proposed that use the GPU to speed up the computation of the GVD. The jump flooding algorithm (to be called JFA) is such an efficient GPU-based method that is particularly suitable for computing the ordinary Voronoi diagram of point sites. We improve the jump flooding algorithm and apply it to computing the GVD. Specifically, instead of directly propagating the complete information of a site (i.e. the coordinates or other geometric parameters) as in the original JFA, we store the site information in a 1-D texture, and propagate only the IDs, which are short integers, of the sites in another 2D texture to generate the Voronoi diagram. This simple strategy avoids storing redundant data and leads to considerately more accurate computation of the GVD with much less memory than using the original JFA, with only moderate increase of the running time. © 2011 IEEE.
 
dc.description.naturelink_to_subscribed_fulltext
 
dc.identifier.citationThe 8th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2011), Qingdao, China, 28-30 June 2011. In Conference Proceedings, 2011, p. 75-82 [How to Cite?]
DOI: http://dx.doi.org/10.1109/ISVD.2011.18
 
dc.identifier.doihttp://dx.doi.org/10.1109/ISVD.2011.18
 
dc.identifier.epage82
 
dc.identifier.hkuros194929
 
dc.identifier.isbn978-076954483-0
 
dc.identifier.scopuseid_2-s2.0-80052631259
 
dc.identifier.spage75
 
dc.identifier.urihttp://hdl.handle.net/10722/140004
 
dc.languageeng
 
dc.publisherIEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1001201
 
dc.publisher.placeUnited States
 
dc.relation.ispartofInternational Symposium on Voronoi Diagrams in Science and Engineering Proceedings
 
dc.relation.referencesReferences in Scopus
 
dc.rightsInternational Symposium on Voronoi Diagrams in Science and Engineering Proceedings. Copyright © IEEE.
 
dc.subjectJump Flooding Algorithm
 
dc.subjectGraphics Hardware
 
dc.subjectGeneralized Voronoi Diagram
 
dc.titleGeneralized Voronoi Diagram Computation on GPU
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Yuan, Z</contributor.author>
<contributor.author>Rong, G</contributor.author>
<contributor.author>Guo, X</contributor.author>
<contributor.author>Wang, WP</contributor.author>
<date.accessioned>2011-09-23T06:04:35Z</date.accessioned>
<date.available>2011-09-23T06:04:35Z</date.available>
<date.issued>2011</date.issued>
<identifier.citation>The 8th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2011), Qingdao, China, 28-30 June 2011. In Conference Proceedings, 2011, p. 75-82</identifier.citation>
<identifier.isbn>978-076954483-0</identifier.isbn>
<identifier.uri>http://hdl.handle.net/10722/140004</identifier.uri>
<description.abstract>We study the problem of using the GPU to compute the generalized Voronoi diagram (GVD) for higher-order sites, such as line segments and curves. This problem has applications in many fields, including computer animation, pattern recognition and so on. A number of methods have been proposed that use the GPU to speed up the computation of the GVD. The jump flooding algorithm (to be called JFA) is such an efficient GPU-based method that is particularly suitable for computing the ordinary Voronoi diagram of point sites. We improve the jump flooding algorithm and apply it to computing the GVD. Specifically, instead of directly propagating the complete information of a site (i.e. the coordinates or other geometric parameters) as in the original JFA, we store the site information in a 1-D texture, and propagate only the IDs, which are short integers, of the sites in another 2D texture to generate the Voronoi diagram. This simple strategy avoids storing redundant data and leads to considerately more accurate computation of the GVD with much less memory than using the original JFA, with only moderate increase of the running time. &#169; 2011 IEEE.</description.abstract>
<language>eng</language>
<publisher>IEEE. The Journal&apos;s web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1001201</publisher>
<relation.ispartof>International Symposium on Voronoi Diagrams in Science and Engineering Proceedings</relation.ispartof>
<rights>International Symposium on Voronoi Diagrams in Science and Engineering Proceedings. Copyright &#169; IEEE.</rights>
<subject>Jump Flooding Algorithm</subject>
<subject>Graphics Hardware</subject>
<subject>Generalized Voronoi Diagram</subject>
<title>Generalized Voronoi Diagram Computation on GPU</title>
<type>Conference_Paper</type>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1109/ISVD.2011.18</identifier.doi>
<identifier.scopus>eid_2-s2.0-80052631259</identifier.scopus>
<identifier.hkuros>194929</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-80052631259&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.spage>75</identifier.spage>
<identifier.epage>82</identifier.epage>
<publisher.place>United States</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. University of Texas at Dallas