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: In this paper, 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 study experimented with a building compound, containing more than 200,000 geometric solids, in Shenzhen, China. The experimental results 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.
-
[1] Pantazopoulos I, Tzafestas S. Occlusion Culling Algorithms:A Comprehensive Survey[J]. Journal of Intelligent & Robotic Systems Theory & Applications. 2002, 35(2):123-156. [2] Clarisse P. Smart Cities in Japan:An Assessment on the Potential for EU-Japan Cooperation and Business Development[M]. Tokyo:EU-Japan Centre for Industrial Cooperation, 2014 [3] Zhou C, Chen Z, Li M. A parallel method to accelerate spatial operations involving polygon intersections[J]. International Journal of Geographical Information Science. 2018, 32(12):2402-2426. [4] Zhang F, Zheng Y, Xu D, et al. Real-Time Spatial Queries for Moving Objects Using Storm Topology[J]. ISPRS International Journal of Geo-Information, 2016, 5(10):178. [5] Li J, Meng L, Wang F Z, et al. A Map-Reduce-enabled SOLAP cube for large-scale remotely sensed data aggregation[J]. Comput. Geosci. 2014, 70(C):110-119. [6] Hladky J, Seidel H, Steinberger M. The camera offset space:real-time potentially visible set computations for streaming rendering[J]. ACM Trans. Graph. 2019, 38(6):231. [7] Nutanong S, Tanin E, Rui Z. Visible Nearest Neighbor Queries[C]. 2007. [8] Sultana N, Hashem T, Kulik L. Group nearest neighbor queries in the presence of obstacles[C]. Dallas, Texas:Association for Computing Machinery, 2014. [9] Luebke D, Georges C. Simple, Fast Evaluation of Potentially Visible Sets[J]. 2020. [10] Chakravarty I, Freeman H. Characteristic Views As A Basis For Three-Dimensional Object Recognition[J]. Proceedings of SPIE-The International Society for Optical Engineering. 1982, 336. [11] O'Rourke J. Finding minimal enclosing boxes[J]. International Journal of Computer & Information Sciences. 1985, 14(3):183-199. [12] Cohen-Or D, Fibich G, Halperin D, et al. Conservative Visibility and Strong Occlusion for Viewspace Partitioning of Densely Occluded Scenes[J]. Comput. Graph. Forum. 1998, 17:243-254 [13] Naylor B, Amanatides J, Thibault W. Merging BSP trees yields polyhedral set operations[J]. SIGGRAPH Comput. Graph. 1990, 24(4):115-124 -
点击查看大图
计量
- 文章访问数: 454
- HTML全文浏览量: 61
- PDF下载量: 14
- 被引次数: 0
下载:
