A GPU-Based Rasterization Algorithm for Boolean Operations on Polygons

Yi GAO  Jianxin LUO  Hangping QIU  Bin TANG  Bo WU  Weiwei DUAN  

IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.1   pp.234-238
Publication Date: 2018/01/01
Publicized: 2017/09/29
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017EDL8119
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
GPU,  CPU,  rasterization,  Boolean operation,  error-free,  

Full Text: PDF>>
Buy this Article

This paper presents a new GPU-based rasterization algorithm for Boolean operations that handles arbitary closed polygons. We construct an efficient data structure for interoperation of CPU and GPU and propose a fast GPU-based contour extraction method to ensure the performance of our algorithm. We then design a novel traversing strategy to achieve an error-free calculation of intersection point for correct Boolean operations. We finally give a detail evaluation and the results show that our algorithm has a higher performance than exsiting algorithms on processing polygons with large amount of vertices.