[发明专利]一种基于CPU+GPU架构的空间几何体线段相交判断并行处理方法

摘要

一种基于CPU+GPU架构的空间几何体线段相交判断并行处理方法，步骤为：（1）数据整理及信息提取，将空间几何体拆分为结点集与线段集并获取所需空间信息；（2）将空间几何体的结点与线段信息高效存储于空间索引中；（3）提取索引中每一个存储单元内所有不同几何体之间的线段组合，同时对每一组线段对进行几何计算的精度判断，依照判断结果是否满足单精度浮点运算的要求，形成两个线段对候选集合；（4）对满足单精度浮点运算要求的线段对候选集合，利用GPU进行相交判断的并行计算，同时对于不满足单精度浮点运算要求的线段对候选集合，利用CPU并行判断每一组线段对中两条线段是否相交，合并CPU与GPU的计算结果。本发明提高了空间几何体线段相交判断的效率并且保证其准确性。

主权项

一种基于CPU+GPU架构的空间几何体线段相交判断并行处理方法，其特征在于包括以下步骤：第一步，数据整理及信息提取，将空间几何体拆分为结点集与线段集并获取所需空间信息；所述获取的空间信息包括：原始数据的最大空间范围以及结点集中结点的个数；第二步，根据第一步中获得的空间信息构建空间索引，将空间几何体的结点与线段信息高效存储于空间索引中；第三步，利用第二步中的空间索引，提取索引中每一个存储单元内所有不同几何体之间的线段组合，同时对每一组线段对进行几何计算的精度判断，依照判断结果是否满足单、双精度浮点运算的要求，形成两个线段对候选集合；第四步，对于第三步中的满足单精度浮点运算要求的线段对候选集合，利用GPU进行相交判断的并行计算，同时，对于不满足单精度浮点运算要求的线段对候选集合，则利用CPU并行判断每一组线段对中两条线段是否相交，最终合并CPU与GPU的计算结果。