File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Generalized Voronoi Diagram Computation on GPU

TitleGeneralized Voronoi Diagram Computation on GPU
Authors
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
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 How to Cite?
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. © 2011 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/140004
ISBN
References

 

Author Affiliations
  1. The University of Hong Kong
  2. University of Texas at Dallas
DC FieldValueLanguage
dc.contributor.authorYuan, Zen_HK
dc.contributor.authorRong, Gen_HK
dc.contributor.authorGuo, Xen_HK
dc.contributor.authorWang, WPen_HK
dc.date.accessioned2011-09-23T06:04:35Z-
dc.date.available2011-09-23T06:04:35Z-
dc.date.issued2011en_HK
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-82en_HK
dc.identifier.isbn978-076954483-0-
dc.identifier.urihttp://hdl.handle.net/10722/140004-
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.en_HK
dc.languageengen_US
dc.publisherIEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1001201-
dc.relation.ispartofInternational Symposium on Voronoi Diagrams in Science and Engineering Proceedingsen_HK
dc.rightsInternational Symposium on Voronoi Diagrams in Science and Engineering Proceedings. Copyright © IEEE.-
dc.subjectJump Flooding Algorithmen_HK
dc.subjectGraphics Hardwareen_HK
dc.subjectGeneralized Voronoi Diagramen_HK
dc.titleGeneralized Voronoi Diagram Computation on GPUen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailWang, WP: wenping@cs.hku.hken_HK
dc.identifier.authorityWang, WP=rp00186en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1109/ISVD.2011.18en_HK
dc.identifier.scopuseid_2-s2.0-80052631259en_HK
dc.identifier.hkuros194929en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80052631259&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage75en_HK
dc.identifier.epage82en_HK
dc.publisher.placeUnited States-
dc.identifier.scopusauthoridWang, W=35147101600en_HK
dc.identifier.scopusauthoridGuo, X=12791011700en_HK
dc.identifier.scopusauthoridRong, G=14619751200en_HK
dc.identifier.scopusauthoridYuan, Z=52064074100en_HK
dc.customcontrol.immutablesml 140407-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats