发明名称 |
一种基于CPU+GPU架构的空间几何体线段相交判断并行处理方法 |
摘要 |
一种基于CPU+GPU架构的空间几何体线段相交判断并行处理方法,步骤为:(1)数据整理及信息提取,将空间几何体拆分为结点集与线段集并获取所需空间信息;(2)将空间几何体的结点与线段信息高效存储于空间索引中;(3)提取索引中每一个存储单元内所有不同几何体之间的线段组合,同时对每一组线段对进行几何计算的精度判断,依照判断结果是否满足单精度浮点运算的要求,形成两个线段对候选集合;(4)对满足单精度浮点运算要求的线段对候选集合,利用GPU进行相交判断的并行计算,同时对于不满足单精度浮点运算要求的线段对候选集合,利用CPU并行判断每一组线段对中两条线段是否相交,合并CPU与GPU的计算结果。本发明提高了空间几何体线段相交判断的效率并且保证其准确性。 |
申请公布号 |
CN103399730A |
申请公布日期 |
2013.11.20 |
申请号 |
CN201310322544.5 |
申请日期 |
2013.07.29 |
申请人 |
中国科学院地理科学与资源研究所 |
发明人 |
谢传节;马益杭;史磊;龙舟 |
分类号 |
G06F9/38(2006.01)I;G06F17/30(2006.01)I |
主分类号 |
G06F9/38(2006.01)I |
代理机构 |
北京科迪生专利代理有限责任公司 11251 |
代理人 |
成金玉 |
主权项 |
一种基于CPU+GPU架构的空间几何体线段相交判断并行处理方法,其特征在于包括以下步骤:第一步,数据整理及信息提取,将空间几何体拆分为结点集与线段集并获取所需空间信息;所述获取的空间信息包括:原始数据的最大空间范围以及结点集中结点的个数;第二步,根据第一步中获得的空间信息构建空间索引,将空间几何体的结点与线段信息高效存储于空间索引中;第三步,利用第二步中的空间索引,提取索引中每一个存储单元内所有不同几何体之间的线段组合,同时对每一组线段对进行几何计算的精度判断,依照判断结果是否满足单、双精度浮点运算的要求,形成两个线段对候选集合;第四步,对于第三步中的满足单精度浮点运算要求的线段对候选集合,利用GPU进行相交判断的并行计算,同时,对于不满足单精度浮点运算要求的线段对候选集合,则利用CPU并行判断每一组线段对中两条线段是否相交,最终合并CPU与GPU的计算结果。 |
地址 |
100101 北京市朝阳区大屯路甲11号 |