Point cloud data contains abundant information besides XYZ, such as Level of Importance (LoI) and intensity. These non-spatial dimensions are also frequently used and queried. Therefore, developing an efficient nD solution for managing and querying point clouds is imperative. Previous researchers have developed PlainSFC that maps both nD points and queries into a one-dimensional Space Filling Curve (SFC) space and uses B+-tree for indexing. However, when computing SFC ranges for selection, PlainSFC subdivides the nD space mechanically to approach the query window without considering the point distribution. Then, excessive ranges are generated in vacant areas, and ranges generated in dense point areas are coarse. Consequently, a large number of false positives are selected, slowing down the whole querying process. This paper develops a new solution called HistSFC to resolve the issue. HistSFC builds an nD-histogram which records point data distribution, and uses it to compute ranges for selecting data. Also, this paper discovers a novel statistical metric, Cumulative Hypercubic Coverage (CHC), to measure the uniformity of the point cloud data. Theory is established and it indicates that the nD-histogram is more beneficial when CHC is smaller. Thus, CHC can be used to guide the building of HistSFC. In addition, the paper conducts simulations and benchmark tests to examine the improvement on PlainSFC. It turns out that using the nD-histogram can decrease the false positive rate by orders of magnitude. HistSFC is also evaluated against state-of-the-art solutions. The result shows that HistSFC leads the performance in nearly all the tests.@en

Point clouds contain high detail and high accuracy geometry representation of the scanned Earth surface parts. To manage the huge amount of data, the point clouds are traditionally organized on location and map-scale; e.g. in an octree structure, where top-levels of the tree contain few points suitable for small scale overviews and lower levels of the tree contain more points suitable for large scale detailed views. The drawback of this solution is that it is based on discrete levels, causing visual artifacts in the form of data density shocks when creating the commonly used perspective views. This paper presents a method based on an optimized distribution of points over continuous levels, avoiding the visualization shocks. The traditional distribution ratio's of data amounts over discrete levels of raster or vector data is considered the reference. How to convert this to point clouds with continuous levels (still benefiting from the proven advantages of the data distribution in discrete levels for efficient access at a wide range of scales)? In our solution, for each point a cLoD (continuous Level of Detail) value is computed and added as dimension to the point. A SFC (Space Filling Curve)-based nD data clustering technique can be used to organize the points, so that they can be efficiently queried. It should be noted that also other multi-dimensional indexing and clustering techniques could be applied to realize continuous levels based on the cLoD value. Besides the mathematical foundation of the approach also several implementations are described, varying from a 3D web-browser based solution to an augmented reality point cloud app in a mobile phone. The cLoD enables interactive real-time visualization using perspective views without data density shocks, while supporting continuous zoom-in/out and progressive data streaming between server and client. The described cLoD based approach is generic and supports different types of point clouds: from airborne, terrestrial, mobile and indoor laser scanning, but also from dense matching optical imagery or multi-beam echo soundings.

@en