1. Voronoi cells of non-general position spheres using the GPU
- Author
-
Xiang Li, Zhongyin Hu, Iddo Hanniel, Adarsh Krishnamurthy, and Sara McMains
- Subjects
0301 basic medicine ,MathematicsofComputing_GENERAL ,Computational Mechanics ,020207 software engineering ,02 engineering and technology ,Computer Science::Computational Geometry ,Lloyd's algorithm ,Computer Graphics and Computer-Aided Design ,Weighted Voronoi diagram ,Combinatorics ,03 medical and health sciences ,Computational Mathematics ,030104 developmental biology ,Position (vector) ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,0202 electrical engineering, electronic engineering, information engineering ,Power diagram ,Centroidal Voronoi tessellation ,Envelope (mathematics) ,Voronoi diagram ,General position ,Algorithm ,ComputingMethodologies_COMPUTERGRAPHICS ,Mathematics - Abstract
We present a GPU algorithm for computing the Voronoi cells for a set of spheres in R3. 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.
- Published
- 2017
- Full Text
- View/download PDF