Compression Techniques for Massive Point Clouds, with Application to Ray Tracing

Abstract

With the increasing capabilities of 3D data scanning devices, point set surfaces are becoming increasingly popular. Even though using points sets already lessens storage requirements (connectivity information is not stored), the ever increasing amount of acquired geometric information gives rise to an equally growing demand for data that needs a compact representation to be stored, transmitted, processed and rendered efficiently.
In this dissertation we are mainly interested in techniques that are useful for rendering massive data sets. In particular, we focus on ray tracing as our rendering algorithm, as its performance is less dependent on scene complexity compared to forward rendering algorithms, which are based on rasterization or splatting.
We present an efficient point set ray tracing algorithm. The surface is modeled implicitly as the zero isosurface of a 3D signed distance function, which can be intersected easily using root-finding. Key to our approach is the use of a simple model for the signed distance function, which does not require costly fitting, yet still provides a robust surface representation. We also present an efficient hierarchical evaluation strategy to determine intersections.
The size of the data sets we are interested in may exceed the main memory of a single computer. As a result, the performance of the ray tracer sporadically and unexpectedly drops when data is needed that still resides on disk. Compression schemes try to alleviate this problem by reducing the size of such data sets in order to fit them into main memory. However, as ray tracing requires neighborhood queries, existing point cloud compression schemes cannot be applied because of their sequential nature. Consequently, we introduce two novel compression techniques that allow random access directly to the compressed data.
We first introduce the Quantized kD-tree. It is an acceleration structure which offers both efficient traversal and storage. The gist of this new representation lies in the quantization of the splitting plane coordinates of a regular kD-tree. We show that the Quantized kD-tree significantly reduces the memory footprint, while not compromising performance. Moreover, the technique can also be employed to provide Level-of-detail to reduce aliasing problems, with little additional storage cost.
The other presented compression scheme is based on the observation that many real-world, surfaces often contain repetitive structures, like bumps, ridges, creases, and so on. The technique therefore exploits self-similarity within a point-sampled surface. The method replaces similar surface patches with an instance of a representative patch. We use a concise shape descriptor to identify and cluster similar patches. Decoding is achieved through simple instancing of the representative patches. Encoding is efficient, and can be applied to large data sets consisting of millions of points. Furthermore, this technique easily allows for storing addition point attributes, like normals.