Distributed Visible Query Method for Regional Objects Using Map‐Reduce

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.