郑晔, 郭仁忠, 贺彪, 马丁, 李晓明, 赵志刚. 利用映射‐归约的分布式区域对象可视查询方法[J]. 武汉大学学报 ( 信息科学版), 2023, 48(9): 1482-1489. DOI: 10.13203/j.whugis20210133
引用本文: 郑晔, 郭仁忠, 贺彪, 马丁, 李晓明, 赵志刚. 利用映射‐归约的分布式区域对象可视查询方法[J]. 武汉大学学报 ( 信息科学版), 2023, 48(9): 1482-1489. DOI: 10.13203/j.whugis20210133
ZHENG Ye, GUO Renzhong, HE Biao, MA Ding, LI Xiaoming, ZHAO Zhigang. Distributed Visible Query Method for Regional Objects Using Map‐Reduce[J]. Geomatics and Information Science of Wuhan University, 2023, 48(9): 1482-1489. DOI: 10.13203/j.whugis20210133
Citation: ZHENG Ye, GUO Renzhong, HE Biao, MA Ding, LI Xiaoming, ZHAO Zhigang. Distributed Visible Query Method for Regional Objects Using Map‐Reduce[J]. Geomatics and Information Science of Wuhan University, 2023, 48(9): 1482-1489. DOI: 10.13203/j.whugis20210133

利用映射‐归约的分布式区域对象可视查询方法

Distributed Visible Query Method for Regional Objects Using Map‐Reduce

  • 摘要: 区域对象的可视查询是沿着区域视线方向剔除三维空间数据中一些表面被遮挡住而导致不可见的数据,从而提高大规模三维场景的可视渲染效率。针对传统区域可视查询视点空间划分粒度细、计算难度大的现状,提出了一种基于映射‐归约的分布式可视查询方法。在映射函数中,按照三维对象的空间分布规律构建层级轴对齐包围盒,以轴对齐包围盒为视点空间划分区,将可视域范围内三维对象发送至规约函数中进行可视判断。在规约函数中,利用平面拆分后射线求交方法,通过构建二叉空间分割树计算每一视点空间划分区的潜在可视集,从而实现三维空间对象的分布式可视查询。将此方法用于深圳市20多万个三维空间对象的可视查询实验中,从数据量、划分粒度和并行度等角度验证了算法的可行性和有效性。

     

    Abstract:
    Objectives In the large-scale of virtual reality scene, it is difficult to add all graphics data into the video memory for rendering. Removing the occluded objects in advance by visible query technology can reduce the amount of data loaded on the display end to improve the rendering efficiency. Therefore, the research of visible query method for regional objects has important application value for real-time rendering of large-scale urban scene.
    Methods We put forward a distributed visible query method based on Map-Reduce. In the map phase, we apply a hierarchical axis-aligned bounding box as viewpoint space partition. When the number of 3D objects in viewpoint space partition exceeds the threshold, the axis-aligned bounding box continues to be divided into sub- boxes. After the above process, the map tasks produce GeoTuples with the VSPID as key and visible query candidate set as value. In the reduce phase, a viewpoint is created for each leaf axis-aligned bounding box where the binary space partitioning trees are build and the visible set is calculated using real-time occlusion algorithm.
    Results The experiment results with a building compound, containing more than 200 000 geometric solids, in Shenzhen, China show that: (1) There is no simple linear relationship between the running time of distributed visible query and the number of viewpoint space partitions. (2) Running time and parallelism are not simply inversely proportional. The computational efficiency of each process first increases and then decreases with the increase of parallelism. About 48 parallelism, the process has the highest efficiency. (3) Whether the distributed approach is better than the traditional approach depends on the number of 3D objects. After the amount of 3D objects reaches about 40 000, the distributed algorithm begins to be better than the traditional algorithm.
    Conclusions The computational experiments reveal the proposed algorithms outperform competitors in terms of the processing efficiency and feasibility, which can meet the requirement of visible query in large-scale scenarios.

     

/

返回文章
返回