Generating octrees from the point cloud in conditions of limited random access memory volume

Laser scanning is a modern and actively developing remote sensing method. Laser scanning results are represented by point clouds, which can contain not only the coordinates of each point, but also the color of the points and other attributes. One of laser scanning technology features, which caused its popularity, is the ability to obtain a sufficiently dense cloud of points. Thanks to this function, laser scanning allows you to determine the digital representation of the geometry of the scanned object with high accuracy. In some cases, point clouds can contain billions of points that require hundreds of gigabytes of data storage. Loading and processing such enormous amounts of data requires significant time and computational resources. A common approach is to build an octree to speed up the spatial search operations and group points close in space. Using such an octree together with external memory opens the possibility of limiting the amount of RAM consumed. This article presents the method of an octree generating using a two-tier cache system for caching sections of the point cloud. The method of organizing the process of data structure building is proposed, and the approach to the analysis of the proposed method efficiency on the basis of a computational experiment is given. The results of the proposed method efficiency analysis are presented.