TL;DR
This paper introduces a GPU-accelerated pipeline for generating Level-of-Detail (LOD) structures for massive point clouds, achieving throughputs of up to 4 billion points per second. By utilizing a hybrid voxel-point octree and color-filtering techniques, the authors achieve an 80x to 400x speedup over current CPU-based state-of-the-art methods while simultaneously improving visual quality.
What Problem Does This Paper Address?
Point clouds—collections of millions or even trillions of $(x, y, z)$ coordinates with color data—are the standard output of 3D scanning technologies like LiDAR. Visualizing these massive datasets in real-time requires Level-of-Detail (LOD) structures, which allow a renderer to load only the necessary amount of detail for a given view.
The most common structure is the Layered Point Cloud (LPC). However, constructing these LODs is a major bottleneck. Even the fastest CPU-based methods only process about 12 million points per second, making the inspection of large datasets a tedious, time-consuming process. Furthermore, traditional point-based LODs often suffer from "sparkling" aliasing artifacts during motion because they rely on simple random sampling.
Methods
The authors propose a two-stage, GPU-centric construction process implemented in CUDA:
- Partitioning (Top-Down): The input point cloud is split into octree leaf nodes (each containing roughly 50,000 points) using a hierarchical counting sort. This algorithm is highly efficient on GPUs because it only requires two passes over the data: one to count points per cell and another to move them to their sorted locations.
- Voxelization (Bottom-Up): Once the leaves are populated, the inner nodes of the octree are filled from the bottom up. Instead of just picking random points, the authors represent these inner nodes using surface voxels.
The paper explores four sampling strategies for these voxels:
- First-Come-First-Serve: The fastest, taking the first point that hits a voxel cell.
- Random: Picks one random point per cell to avoid scan-line artifacts.
- Cell-wise Average: Computes the average color of all points in a voxel.
- Neighborhood Weighted Average: Uses a linear weight function to average colors from adjacent voxels, providing the highest quality and reducing aliasing.
Datasets
The method was evaluated on several large-scale datasets representing different challenges:
- Retz (145M points): A town scan with high-density regions.
- Palmyra (258M points): An archaeological site.
- Saint Roman (547M points): A complex scan with both interior and exterior surfaces.
- CA21_Bunds (976M points): A massive aerial LiDAR dataset.
- Niederweiden: Used specifically for quality evaluation of high-frequency features like text.
Key Insights and Ideas
- Hybrid Voxel-Point Structure: By using voxels for lower LODs and points for the highest LOD, the system gains the compression benefits of quantized integer coordinates for streaming while maintaining full precision for close-up inspection.
- Replacement vs. Additive LOD: Unlike traditional LPCs where higher levels are added to lower levels, this method uses a "replacement" strategy. When a viewer zooms in, the coarse voxels are completely replaced by finer ones, allowing for better precomputed anti-aliasing (color filtering).
- GPU Counting Sort Efficiency: The authors demonstrate that counting sort, often overlooked for more complex spatial partitioning, is exceptionally well-suited for the GPU's parallel architecture when building octrees.
- Color Filtering Matters: Simple arithmetic averaging within a voxel significantly reduces the "sparkling" artifacts common in point cloud rendering, making the result look more like a textured mesh.
Key Results
The performance gains are massive when tested on an NVIDIA RTX 3090:
- Throughput: The system processes ~1 billion points/sec with high-quality weighted averaging and up to ~4.9 billion points/sec using the first-come strategy.
- Speedup: Compared to the CPU-based state-of-the-art (Potree), the GPU method is 80x to 400x faster. For example, the 145M point "Retz" dataset was processed in just 50ms on the GPU, compared to 13 seconds on the CPU.
- Visual Quality: The weighted average strategy effectively removes outliers and provides homogeneous results similar to textured meshes with mip-mapping.
Limitations and Future Work
- In-Core Limitation: The current implementation is "in-core," meaning the entire dataset and temporary buffers must fit in GPU VRAM. This limits model sizes to roughly 500 million points on a 24GB card. The authors suggest this could be integrated into "out-of-core" (disk-based) schemes in the future.
- View-Dependency: The current color filtering doesn't account for view direction. For example, two sides of a thin wall might be averaged into a single voxel color. Future work could incorporate spherical harmonics or neural radiance fields (NeRFs) to handle view-dependent colors.
- Precision: Using voxels reduces measurement precision at lower LODs, though the authors note that full-precision points can be supported in lower LODs with minor modifications to the pipeline.
Summary updated