Icosatree Data Partitioning of Massive Geospatial Point Clouds with User-Selectable Entities and Surface Modeling

Massive point cloud data sets are currently being created and studied in academia, the private sector, and the military. Many previous attempts at rendering point clouds have allowed the user to visualize the data in a three-dimensional way but did not allow them to interact with the data and would require all data to be in memory at runtime. Recently, a few systems have emerged that deal with real-time rendering of massive point clouds with on-the-fly level of detail modification that handles out-of-core processing but these systems have their own limitations. With the size and scale of massive point cloud data coming from LiDAR (Light Detection and Ranging) systems, being able to visualize the data as well as interact and transform the data is needed. Previous work in out-of-core rendering showed that using Octrees and k-d trees can increase the availability of data as well as allow a user to visualize the information in a much more useful manner. However, viewing the data isn’t enough; applying work in context-aware selection and surface creation the visualization system would greatly benefit in usability and functionality. This paper explores a new data structure called an Icosatree, or icosahedral tree, that can be used to partition a point cloud dataset in the same fashion as an Octree is currently used. However, the Icosatree is made from triangular prism sub-cells which are tangential to the ellipsoidal surface used by Earth-based projected coordinate systems. In doing so, as new sub-cells are added to the rendering system, a much more uniform visualization emerges. Along the same lines, this paper applies portions of the aforementioned context-aware selection and surface creation algorithms to the resulting visualization such that a user may triangulate, prune and/or export portions of the point cloud dataset using an intuitive three dimensional interface and user-modifiable set of parameters. This allows the user to save items of interest for later analysis