Min-Max Modifiable Nested Octrees (M3NO): Indexing Point Clouds with Arbitrary Attributes in Real Time

We present a data structure that allows 3D point clouds with arbitrary attributes to be indexed in real time. We focus on large datsets from mobile mapping systems such as airborne and terrestrial laser scanners. Compared to traditional indexing approaches running offline, our data structure can be created incrementally while the points are being recorded. This allows the data to be used (i.e. analyzed or visualized) already during acquisition or immediately after it has finished. The data structure enables queries based on spatial extent and value ranges of arbitrary attributes. This is in contrast to existing works, which focus on either spatial or attribute indexing, typically are not real-time capable, or only support a limited set of attributes. Our approach combines Modifiable Nested Octrees and extended Binned Min-Max Octrees. Using a subset of the well known AHN4 dataset with 138 million points, we evaluate the approach, assess quality and query performance, and compare it with an existing state-of-the-art solution. On commodity hardware, our data structure can process 1.97 million points per second, which is more than most commercially available laser scanners can record. When filtering points by attribute value ranges, it also reduces the number of octree nodes that have to be loaded, and it substantially outperforms naive sequential point filtering.