Message Board

Respected readers, authors and reviewers, you can add comments to this page on any questions about the contribution, review,        editing and publication of this journal. We will give you an answer as soon as possible. Thank you for your support!

Name
E-mail
Phone
Title
Content
Verification Code
Turn off MathJax
Article Contents

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. 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. doi: 10.13203/j.whugis20210133

Distributed Visible Query Method for Regional Objects Using Map-Reduce

doi: 10.13203/j.whugis20210133
Funds:

Key Projects of the National Natural Science Foundation of China (41930104)

  • Received Date: 2021-09-10
  • 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
  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Article Metrics

Article views(359) PDF downloads(13) Cited by()

Related
Proportional views

Distributed Visible Query Method for Regional Objects Using Map-Reduce

doi: 10.13203/j.whugis20210133
Funds:

Key Projects of the National Natural Science Foundation of China (41930104)

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.

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. 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. doi: 10.13203/j.whugis20210133
Reference (13)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return