Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial

摘要

Three Dimensional (3D) have given new perspective in various field such as urban planning, hydrology, infrastructure modeling, geology etc due to its capability of handling real world object in more realistic manners, rather than two-dimensional (2D) approach. However, implementation of 3D spatial analysis in the real world has proven difficult due to the complexity of algorithm, computational power and time consuming. Existing GIS system enables 2D and two-and-a-half dimensional (2.5D) spatial datasets, but less capable of supporting 3D data structures. Recent development in Octree see more effort to improve weakness of octree in finding neighbor node by using various address encoding scheme with specific rule to eliminate the need of tree traversal. This paper proposed a new method to speed up neighbor searching and eliminating the needs of complex operation to extract spatial information from octree by preserving 3D spatial information directly from Octree data structure. This new method able to achieve O(1) complexity and utilizing Bit Manipulation Instruction 2 (BMI2) to speedup address encoding, extraction and voxel search 700% compared with generic implementation.