Per Segment Plane Sweep Line Segment Intersection on the GPU

Polygon overlay operations are used for various purposes, such as GIS searches and queries, VLSI, and basic geometric operations of intersection, union, and difference. There have been recent research articles presenting algorithms using the GPU to perform line segment intersection for geometric operations. We present two parallel algorithms implemented on the GPU that focus on the active list portion of the traditional serial plane sweep algorithm. The first algorithm uses a single block of threads to simulate the active list data structure in hardware; this algorithm is slow due to GPU thread block size limitations and synchronization points but demonstrates favorable time complexity. The second algorithm uses dynamic parallelism to remove synchronization and scales to utilize available GPU hardware (single GPU). We perform experiments on both synthetic and real-world datasets. The presented results show improvement in execution time with respect to recent algorithms and low memory usage compared to recent algorithms. We achieve speedups of up to 38.8 over the serial sweep line algorithm on real-world data.