Conference Paper: Generalized Voronoi diagram computation on GPU
| Title | Generalized Voronoi diagram computation on GPU |
|---|---|
| Authors | Yuan, Z1 Rong, G2 Guo, X2 Wang, W1 |
| Keywords | Generalized Voronoi Diagram Graphics Hardware Jump Flooding Algorithm |
| Issue Date | 2011 |
| Citation | Proceedings - 2011 8Th International Symposium On Voronoi Diagrams In Science And Engineering, Isvd 2011, 2011, p. 75-82 [How to Cite?] DOI: http://dx.doi.org/10.1109/ISVD.2011.18 |
| 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. |
| DOI | http://dx.doi.org/10.1109/ISVD.2011.18 |
| References | References in Scopus |
| dc.contributor.author | Yuan, Z |
|---|---|
| dc.contributor.author | Rong, G |
| dc.contributor.author | Guo, X |
| dc.contributor.author | Wang, W |
| dc.date.accessioned | 2011-09-23T06:04:35Z |
| dc.date.available | 2011-09-23T06:04:35Z |
| dc.date.issued | 2011 |
| dc.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. © 2011 IEEE. |
| dc.description.nature | Link_to_subscribed_fulltext |
| dc.identifier.citation | Proceedings - 2011 8Th International Symposium On Voronoi Diagrams In Science And Engineering, Isvd 2011, 2011, p. 75-82 [How to Cite?] DOI: http://dx.doi.org/10.1109/ISVD.2011.18 |
| dc.identifier.doi | http://dx.doi.org/10.1109/ISVD.2011.18 |
| dc.identifier.epage | 82 |
| dc.identifier.hkuros | 194929 |
| dc.identifier.scopus | eid_2-s2.0-80052631259 |
| dc.identifier.spage | 75 |
| dc.identifier.uri | http://hdl.handle.net/10722/140004 |
| dc.language | eng |
| dc.relation.ispartof | Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011 |
| dc.relation.references | References in Scopus |
| dc.subject | Generalized Voronoi Diagram |
| dc.subject | Graphics Hardware |
| dc.subject | Jump Flooding Algorithm |
| dc.title | Generalized Voronoi diagram computation on GPU |
| dc.type | Conference_Paper |
Author Affiliations
- The University of Hong Kong
- University of Texas at Dallas