三维地学实体多粒度栅格剖分与布尔运算的并行算法

 三维栅格是空间单元属性插值与实体内部特征精细表达的理想模型,但海量栅格单元的快速剖分与数据压缩成为其应用瓶颈。本文分析了三维地学实体模型三维栅格剖分的研究现状,针对矢栅转换与数据存储的时间效率及空间节约问题,面向多核CPU与计算集群新型硬件架构,采用MPI并行技术,设计了一种基于八叉树的地矿实体多粒度并行三重轴向扫描剖分算法(P-TAS)。并面向矿山及地下工程开挖模拟与动态仿真需求,设计并实现了基于多粒度栅格的三维模型布尔运算算法。测试表明,该剖分算法的并行效率达50%—60%,数据压缩率达80%以上,具有推广和应用价值。

Multi-granularity Rasterization and Boolean Operation Parallel Algorithm for 3D Spatial Entities

3D raster is an ideal model which performs really well at the aspects of detailed representation and spatial interpolation for internal attributes of spatial entities. However, due to the large scale of raster data, rasterizing efficiency and data compression still remain the bottlenecks in practical applications. The present situation of rasterization algorithms for 3D vector model was comprehensively reviewed. In order to improve the time efficiency of 3D vector-raster conversion and save storage space of raster data, a Parallel Ternary Axes Scan (P-TAS) algorithm, which could run on the new multi-core CPU and high performance computer cluster, was designed for transforming 3D vector model to raster model with Octree structure by using MPI parallel techniques. Furthermore, the Boolean operation algorithm for 3D spatial entities represented with multi-granularity raster was designed for the dynamic simulation of underground excavation process. The experiment results demonstrate that the parallel efficiency of P-TAS is about 50%—60% and the data compression ratio is about 80%. The high application values of P-TAS and Boolean algorithms proposed are proved up to the hilt.