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

摘要

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(log n) 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. (C) 2015 Elsevier Ltd. All rights reserved.