GPU-Accelerated LOD Generation for Point Clouds

Markus Schütz, Bernhard Kerbl, Philip Klaus, Michael WimmerarXiv 2023 · arXiv

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:

  1. 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.
  2. 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.
Figure 1: The data structure is a hybrid voxel-point octree that utilizes color-filtered voxels for lower LODs, but displays the original point data at the highest LOD. As most grid cells of each node are empty, surface voxels are stored as vertices in a node’s vertex buffer. During rendering, we aim to rasterize pixel-sized voxels to give viewers the impression that they are looking at full-precision point cloud data.

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.
Figure 6: Comparison of sampling strategies. (a) Sampling grid, (b) Single sample (outliers), (c) Cell averaging, (d) Weighted neighborhood averaging.

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

Abstract

About: We introduce a GPU-accelerated LOD construction process that creates a hybrid voxel-point-based variation of the widely used layered point cloud (LPC) structure for LOD rendering and streaming. The massive performance improvements provided by the GPU allow us to improve the quality of lower LODs via color filtering while still increasing construction speed compared to the non-filtered, CPU-based state of the art. Background: LOD structures are required to render hundreds of millions to trillions of points, but constructing them takes time. Results: LOD structures suitable for rendering and streaming are constructed at rates of about 1 billion points per second (with color filtering) to 4 billion points per second (sample-picking/random sampling, state of the art) on an RTX 3090 -- an improvement of a factor of 80 to 400 times over the CPU-based state of the art (12 million points per second). Due to being in-core, model sizes are limited to about 500 million points per 24GB memory. Discussion: Our method currently focuses on maximizing in-core construction speed on the GPU. Issues such as out-of-core construction of arbitrarily large data sets are not addressed, but we expect it to be suitable as a component of bottom-up out-of-core LOD construction schemes.
BibTeX
@misc{schutz2023gpu,
  author = {Markus Schütz and Bernhard Kerbl and Philip Klaus and Michael Wimmer},
  title = {{GPU-Accelerated LOD Generation for Point Clouds}},
  year = {2023},
  eprint = {2302.14801},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.14801},
}

Loading related content...

Figure