Efficient Proximity Queries on Simplified Height Maps

Performing proximity queries on a 3D surface has gained significant attention from both academic and industry. The height map is one fundamental 3D surface representation with many advantages over others such as the point cloud and Triangular-Irregular Network ( TIN ). In this paper, we study the shortest path query on a height map. Since performing proximity queries using the shortest path on a height map is costly, we propose a simplification algorithm on the height map to accelerate it. We also propose a shortest path query algorithm and algorithms for answering proximity queries on the original/simplified height map. Our experiments show that our simplification algorithm is up to 21 times and 5 times (resp. 412 times and 7 times) better than the best-known adapted point cloud (resp. TIN ) simplification algorithm in terms of the simplification time and output size (the size of the simplified surface), respectively. Performing proximity queries on our simplified height map is up to 5 times and 1,340 times quicker than on the simplified point cloud and the simplified TIN with an error at most 10%, respectively.