GPU-based parallel algorithm for computing point visibility inside simple polygons

• We present a new GPU-based parallel algorithm for the visibility problem.
• The algorithm proposed can solve the point visibility inside simple polygons.
• This is the first work aiming this problem on parallel manycore architectures.
• Experimental evaluations indicate performance advantages of the algorithm.

Given a simple polygon P in the plane, we present a parallel algorithm for computing the visibility polygon of an observer point q inside P. We use chain visibility concept and a bottom-up merge method for constructing the visibility polygon of point q  . The algorithm is simple and mainly designed for GPU architectures, where it runs in O(logn) time using O(n) processors. This is the first work on designing a GPU-based parallel algorithm for the visibility problem. To the best of our knowledge, the presented algorithm is also the first suboptimal parallel algorithm for the visibility problem that can be implemented on existing parallel architectures. We evaluated a sample implementation of the algorithm on several large polygons. The experiments indicate that our algorithm can compute the visibility of a polygon having over 4M points in tenth of a second on an NVIDIA GTX 780 Ti GPU.

Figure optionsDownload high-quality image (379 K)Download as PowerPoint slide