计算机工程

• 开发研究与工程应用 • 上一篇    下一篇

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

高艺 1,2,罗健欣 1,裘杭萍 1,吴波 1   

  1. (1.解放军理工大学 指挥信息系统学院,南京 210007; 2.中国人民解放军61175部队,南京 210049)
  • 收稿日期:2017-03-20 出版日期:2018-03-15 发布日期:2018-03-15
  • 作者简介:高艺(1982—),女,博士研究生,主研方向为虚拟现实与仿真;罗健欣,讲师;裘杭萍,教授、博士生导师;吴波,讲师。
  • 基金项目:
    江苏省青年科学基金(BK20150722)。

Arbitrary Polygons Boolean Operation Based on GPU Rasterization

GAO Yi  1,2,LUO Jianxin  1,QIU Hangping  1,WU Bo  1   

  1. (1.College of Command Information System,PLA University of Science and Technology,Nanjing 210007,China; 2.PLA Troops of 61175,Nanjing 210049,China)
  • Received:2017-03-20 Online:2018-03-15 Published:2018-03-15

摘要: 任意多边形布尔运算大多基于CPU栅格化方法,而CPU的串行性会增加栅格化过程的耗时。为此,提出一种基于图形处理器(GPU)栅格化思想的多边形布尔运算算法。用GPU实现CPU中较耗时的二维图形栅格化过程并提取内外轮廓片元,构造GPU环境下的栅格数据结构及与之空间映射相对应的CPU环境下的顶点数据结构,采用CPU与GPU相协调的方式交替访问内外轮廓进行顶点跟踪及轮廓片元压缩,最终得到正确的布尔运算结果多边形。实验结果表明,与现有多边形布尔运算算法相比,该算法能有效控制精度,且具有更高的执行效率。

关键词: 图形处理器, 栅格化, 顶点跟踪, 轮廓片元压缩, 布尔运算, 交点精度

Abstract: 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.

Key words: Graphics Processing Unit(GPU), rasterization, vertex tracing, contour fragment compression, Boolean operation, intersection accuracy

中图分类号: