GPU Accelerated Hierarchical Out-Of-Core Point Cloud Indexing

Modern LiDAR surveys produce point clouds at demanding rates. National campaigns now reach several terabytes per acquisition, and city-scale surveys with short repeat cycles generate a constantly updating set of new scans. Preprocessing pipelines that build hierarchical spatial indices from these scans must keep pace with this throughput. Timecritical applications such as disaster response, infrastructure monitoring, and construction tracking require index structures to become available within hours rather than days. Since 2020, the throughput of CPU-based out-of-core indexers has stagnated. In contrast, recent GPU-accelerated approaches achieve much higher throughput, but they are restricted to datasets that fit entirely within VRAM. This excludes precisely the workloads that would benefit most from acceleration. This thesis proposes, implements, and evaluates Taunus, a GPU-accelerated, out-of-core, hierarchical point cloud indexing pipeline that closes the existing gap. The pipeline uses a one-pass GPU counting sort to partition the input into spatially grouped tiles. An indexing stage then builds one subtree of a Modifiable Nested Octree per tile on the GPU using a new bottom-up sampling procedure. Finally, a merging stage joins the subtrees into a Potree index. To reduce disk and PCIe bottlenecks, intermediate data is compressed on the GPU during idle pipeline slots. On a 499 GiB, 14.9 billion-point subset of the AHN5 dataset, Taunus sustains approximately 50 million points per second, 2.9 times faster than the state-of-the-art PotreeConverter 2 with random sampling and 4.8 times faster than its default Poisson sampling. A bandwidthbased time model reproduces the measured end-to-end throughput with an error of less than four percent. Together with sweeps over disk speed, VRAM budget, and compression configuration, the model shows that the architecture shifts the binding constraint from CPU computation to sustained storage I/O. GPU-side intermediate compression is identified as the most effective way to overcome this bottleneck.

Landesweite LiDAR-Erfassungen erreichen mittlerweile mehrere Terabyte pro Aufnahme, und Vermessungen auf Stadtebene mit kurzen Wiederholungszyklen liefern einen kontinuierlich wachsenden Bestand neuer Scans. Vorverarbeitungspipelines, die aus diesen Scans hierarchische räumliche Indexstrukturen erstellen, müssen mit diesem Durchsatz mithalten. Zeitkritische Anwendungen wie Katastrophenhilfe, Infrastrukturüberwachung und Baufortschrittskontrolle erfordern, dass Indexstrukturen innerhalb von Stunden statt Tagen verfügbar werden. Seit 2020 stagniert der Durchsatz CPU-basierter Out-of-Core- Indexer, während aktuelle GPU-beschleunigte Verfahren zwar einen deutlich höheren Durchsatz erreichen, jedoch auf Datensätze beschränkt sind, die vollständig in den VRAM passen, und damit genau jene Anwendungsfälle ausschließen, die am meisten von einer Beschleunigung profitieren würden. Diese Arbeit konzeptioniert, implementiert und evaluiert Taunus, eine GPU-beschleunigte, Out-of-Core-fähige, hierarchische Indexierungspipeline für Punktwolken, die diese Lücke schließt. Die Pipeline partitioniert die Eingabedaten mit einem GPU-Counting-Sort in einem einzigen Durchgang in räumlich gruppierte Kacheln. Eine Indexierungsstufe erstellt anschließend für jede Kachel auf der GPU einen Teilbaum eines Modifiable Nested Octree mithilfe eines neuen Bottom-up-Sampling-Verfahrens. Eine abschließende Merging-Stufe vereint die Teilbäume zu einem Potree-Index. Um Engpässe bei Festplatten- und PCIeÜbertragungen zu reduzieren, werden Zwischendaten auf der GPU komprimiert. Auf einem 499 GiB großen Ausschnitt des AHN5-Datensatzes mit 14,9 Milliarden Punkten erreicht Taunus einen anhaltenden Durchsatz von rund 50 Millionen Punkten pro Sekunde und ist damit 2,9-mal schneller als der etablierte Standard PotreeConverter 2 mit Random-Sampling sowie 4,8-mal schneller als dessen Poisson-Sampling. Ein bandbreitenbasiertes Zeitmodell reproduziert den gemessenen Gesamtdurchsatz mit einem Fehler von weniger als vier Prozent. Zusammen mit Messungen zu Festplattengeschwindigkeit, VRAM-Budget und Kompressionskonfiguration zeigt das Modell, dass die Architektur die Beschränkung von der CPU-Berechnung auf den Festplatten-I/O verlagert. GPU-seitige Zwischenkompression erweist sich dabei als wirksamstes Mittel, um diesen Engpass zu überwinden.