Voronoi cells of non-general position spheres using the GPU. Issue 5 (29th July 2017)

• Record Type: Journal Article
• Authors: Hu, Zhongyin; Li, Xiang; Krishnamurthy, Adarsh; Hanniel, Iddo; McMains, Sara
• Is Part Of: Computer-aided design and applications. Volume 14:Issue 5(2017)
• Page Start: 572
• Page End: 581
• Publication Date: 2017-07-29
• Subjects: Voronoi diagram -- spheres -- GPU -- lower envelope; Computer-aided design -- Congresses; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Congresses; Engineering design -- Periodicals; 620.00420285
• DOI: 10.1080/16864360.2016.1273576
• Languages: English
• ISSNs: 1686-4360

Abstract

ABSTRACT: We present a GPU algorithm for computing the Voronoi cells for a set of spheres in R 3 . The algorithm is based on sampling rays from each sphere and finding the lower envelope of intersections of the rays with the sphere bisectors on the GPU. The presence of Voronoi vertices and edges is determined based on where neighboring rays intersect different bisectors. For accurate geometry, we present a numerical iteration approach to calculate the Voronoi vertices' locations within a user-defined tolerance. The algorithm robustly handles input in non-general position and large input sets of thousands of spheres. GRAPHICAL ABSTRACT: