Abstract

A segment tree is a versatile tree-based data structure over intervals or line segments efficiently supporting several computational operations such as stabbing query, segment arrangement, and planar point location, both theoretically and practically. Polygon clipping is a basic operation in domains such as Computer Graphics, Computer-aided Design, and Geographic Information Science (GIS). Given two polygons with n vertices, polygon clipping algorithms find the geometric intersection or union in O(n2) time using Foster's all-to-all edge intersection testing and O((n + k) logn) time using Vatti's sweep line-based method, where k is the number of intersections. No known segment tree implementation, including the CGAL library, supports intersection finding or polygon clipping. We extended the segment tree leveraging Chaselle's PRAM-model augmentation, parallelized the construction of our augmented segment tree, and employed it to find line segment intersections for polygon clipping while handling degenerate cases. Augmented segment tree eliminates 99% of non-intersecting edge pairs compared to 63% by the state-of-the-art filtering based on common minimum bounding rectangle method employed in Foster's GPU-based implementation. This, coupled with O(n logn) work on a single CPU core, beats Foster's GPU performance with O(n2) work. Our OpenMP directive based multi-core implementation achieves up to 4X relative speedup for clipping two polygons with 182K vertices and 5X speedup for five polygons with 398K vertices. We also offloaded the parallel kernels to a GPU using OpenACC achieving performance competitive with Foster's GPU implementation. Our profiling indicates limitations of the compiler directives and potential for superior performance by employing pthread/cuda libraries.

Department(s)

Computer Science

Publication Status

Open Access

Comments

National Science Foundation, Grant 2313039

Keywords and Phrases

computational geometry; Degenerate cases for intersection; Foster's algorithm; OpenACC; OpenMP; Polygon clipping; Segment tree; Vatti's algorithm

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 Association for Computing Machinery, All rights reserved.

Publication Date

12 Aug 2024

Download

Full Text Link

Share

 
COinS