Point Cloud Management

This portion of the project investigated ways of managing large data sets, in particular the large point clouds produced by laser scanners. These point clouds are often very large, containing billions of points with file sizes over 50GB. Even using advanced technology and well developed methods for point cloud rendering, it is not possible to view these point clouds interactively. Ways of managing these large point clouds are investigated. The final system developed enables users to perform fast region extractions from the point cloud, at a specified resolution. This is achieved by building an index for the cloud as a pre-process. The system also enables users to stream the extractions from a central server to client machines.

Region Extraction

To enable efficient region extraction the point cloud is subdivided into regions, similar to the partitioning provided by octrees. Additionally, the indexing system allows for a variable level of subdivision for regions where the point cloud is very dense. When performing a region extraction from the cloud the user specifies which region is required. The system then builds this region from the subdivision scheme in the index.

Multiresolution Component

Given the vast sizes of the point clouds a multiresolution component was developed. This allows the user to specify what resolution they require when performing an extraction. The approach taken to building a multiresolution index is a simple reordering of the points. This reordering is constructed in such a way that to gain the point cloud at 50% resolution, for example, one need only read 50% of each of the region files. The order in which the points occur in the new indexed file now gives us implicit additional information. This is ideal, since it does not increase the size of the index, and it does not add overhead to reading the points. To achieve a representative reordering the indexing system builds an octree for each region which contains all the points in the leaf nodes. One can then iterate over the leaf nodes of the octree in turn, writing out a point to the new restructured file and then moving to the next leaf. As an additional step, the points from each leaf node are written out in a random order to ensure the points are evenly distributed in the region.

varying resolution
The same region represented at two different resolutions. The image on the left is at full resolution (10,621,148 points) and the image on the right is at 5% resolution (622,732 points)

Client/Server Streaming

The developed system also allows for multiple clients to connect to a central server and request extractions. The server will then perform the extraction using the index and stream the points to the client machines. Due to the design of the index it is easy to stream points while the extraction is still being performed. This means that the client can still examine the point cloud, even if the entire transfer has not yet been completed. Also, if the points are being fed to some other process, such as meshing, the meshing process can begin even before the full extraction is complete. The client/server protocol is shown in the following figure:

client/server protocol
The client/server protocol used for the streaming.
 

Evaluation

Evaluation showed that the system was reasonably fast, performing extractions in a few seconds, even when the point cloud contained billions of points. It was also shown that as one increases the resolution of the extraction, the time taken scales linearly. It was also shown that the streaming of the points could be done efficiently, since the points could be sent while the extraction was being performed. The following figure shows the times taken for performing an extraction from the point cloud of the Gede Ruins which contains 2,403,821,971 points

time taken for extraction
The time taken as the resolution varies scales linearly.
 

When varying the size of the region for extraction, it was also shown that the time taken varied more or less linearly with the size of the point cloud. However, in this case it was also important to consider the density of the point cloud at that point. Finally, the streaming system was shown to be able to stream the points to client machines efficiently.

Source:
pointcloud_source.zip