基于GPU栅格化的任意多边形布尔运算

摘要

The Boolean operation of arbitrary polygons is mostly based on the CPU grid method,because of the serialization of CPU,the raster process takes a long time.In order to solve the above problem,an algorithm for polygon Boolean operations based on the Graphics Processing Unit(GPU) rasterization is proposed.The time-consuming process of two-dimensional graphics rasterization in CPU is realized by GPU and the internal and external contour fragments are extracted,the raster data structure in the GPU environment and the vertex data structure in the CPU environment corresponding to its space mapping are constructed.Based on this,the internal and external contours are alternatively visited in order to perform the vertex tracking and the contour fragments compression using CPU and GPU in a coordinated manner.Finally the correct Boolean result polygon is obtained.The experimental results show that compared with the existing algorithm of polygons Boolean operation,the proposed algorithm can effectively control the precision,and also possesses with higher execution efficiency.%任意多边形布尔运算大多基于CPU栅格化方法,而CPU的串行性会增加栅格化过程的耗时.为此,提出一种基于图形处理器(GPU)栅格化思想的多边形布尔运算算法.用GPU实现CPU中较耗时的二维图形栅格化过程并提取内外轮廓片元,构造GPU环境下的栅格数据结构及与之空间映射相对应的CPU环境下的顶点数据结构,采用CPU与GPU相协调的方式交替访问内外轮廓进行顶点跟踪及轮廓片元压缩,最终得到正确的布尔运算结果多边形.实验结果表明,与现有多边形布尔运算算法相比,该算法能有效控制精度,且具有更高的执行效率.