Visualisierung und Verarbeitung großer 3D-Punktdaten

Methoden und Verfahren zur Erfassung von 3D-Daten sind inzwischen in der industriellen Fertigung für verschiedene Anwendungen etabliert. Insbesondere im Rahmen der Qualitätsprüfung werden Computer-Tomographen (CT) zur Erfassung von Volumendaten für die Abbildung des Bauteilinneren oder optische 3D-Messverfahren für die Bestimmung der äußeren geometrischen Form genutzt. Die Erzeugung eines detailgetreuen digitalen Abbildes mit hoher Präzision, Auflösung und Geschwindigkeit zählen zu den großen Vorzügen der Messverfahren. Jedoch stellen die erzeugten großen Datenmengen für eine effiziente Visualisierung und Verarbeitung an das Datenmanagement und die Methoden zur Verarbeitung erhebliche Anforderungen.

Für typische Anwendungsszenarien werden mit aktuellen Geräten mehrere hunderte Millionen bis einige Milliarden 3D-Messdatenpunkten erzeugt. Der dafür erforderliche Datenspeicher beträgt ca. 50-100 Gigabyte und übersteigt damit die Kapazität des Arbeits- und Grafikkartenspeicher von Standardhardware um ein Vielfaches. Um trotzdem eine effiziente Visualisierung und Verarbeitung der 3D-Datenmengen zu erreichen werden Verfahren eingesetzt, welche die 3D-Datenmenge zuvor derart strukturieren, dass diese sukzessive in kleineren und technisch handhabbaren Datenblöcken verarbeitet werden kann. Für die Visualisierung wird zudem die Tatsache genutzt, dass nur diejenigen 3D-Punkte angezeigt werden müssen, die aktuell im Fokus des Anwenders stehen. Zusätzlich ergibt sich eine weitere Limitierung der erforderlichen Daten durch ein endlich hohes Auflösungsvermögen des genutzten Bildschirms. Für die Selektion der erforderlichen Teilmenge an 3D-Punkten aus der Gesamtdatenmenge sind für eine schnelle Verarbeitung hocheffiziente Datenstrukturen eine zwingende Voraussetzung.

Strukturierung großer 3D-Datenmengen

Die erforderliche Strukturierung der Daten basiert im Allgemeinen auf einer hierarchischen, räumlichen Unterteilung der Daten mithilfe algorithmischer Bäume, welche das Messvolumen in immer kleinere Volumen separiert. Die oberen Hierarchien dieser Baumstrukturen sind gering aufgelöst und verwalten Repräsentanten der höher aufgelösten Teilmenge der unteren Hierarchien. Indem man den Verzweigungen einer Baumstruktur nach unten folgt, adressiert man sukzessive sich räumlich verkleinernde Untermengen der Gesamtdatenmenge.

Ein typischer Vertreter einer solchen Baumstruktur ist der sogenannte Octree, mit dem das gesamte Messvolumen zunächst in acht Würfel (auch Voxel genannt) unterteilt wird. Diese werden in den nächsten Hierarchien jeweils weiter unterteilt bis in jedem Voxel nur noch wenige 3D-Datenpunkte enthalten sind. Eine ähnliche Strategie wird mit binären Bäumen verfolgt. Binärbäume unterteilen die Gesamtdatenmenge sukzessive in zwei möglichst gleich große Teilmengen. Ein typischer Vertreter hierfür ist der kD-Baum, mit dem eine 3D-Datenmenge nacheinander folgend mittig entlang der x-, y- und z-Koordinaten wiederholt unterteilt wird.

Baumstrukturen ermöglichen es letztlich, eine Teilmenge der Gesamtdatenmenge schnell und gezielt auszuwählen ohne die restlichen Daten ebenfalls betrachten zu müssen. Die Teilmengen werden in ihrer Größe derart definiert, dass sie der Größe des verfügbaren Arbeits- und Grafikkartenspeichers angemessen sind.

Speicherung und Verwaltung großer 3D-Datenmengen

Die Größe der Gesamtdatenmenge gemeinsam mit der zusätzlichen Baumstruktur zur Verwaltung kann die Größe des vorhandenen Arbeitsspeichers deutlich überschreiten. Daher werden die Daten in Form von Dateien auf Festplatten abgelegt, deren Speichervolumen nur wenig limitiert ist. Ein Prozessor verarbeitet jedoch nur Daten aus dem begrenzt großen Arbeitsspeicher. Um die Datenverarbeitung trotzdem zu ermöglichen, wird ein sogenannter File-Mapping-Mechanismus eingesetzt. Dieser bildet lokale kleine Dateiabschnitte in den begrenzt großen Arbeitsspeicher ab. Durch die sukzessive Abbildung aller lokalen Dateiabschnitte wird letztlich die Gesamtdatenmenge verarbeitet. Die Ermittlung und Adressierung dieser lokalen Dateiabschnitte wird wiederum über die zuvor erläuterten Baumstrukturen gelöst. Dieses Vorgehen wird auch als out-of-core-Methodik bezeichnet.

Die Abbildung eines Dateiabschnittes in den Arbeitsspeicher ist jedoch vergleichsweise langsam und die Effizienz hängt vom verwendeten Festplattentyp ab (z.B. langsame HDD oder schnelle SSD). Für eine hohe Gesamtleistungsfähigkeit der Visualisierung und Verarbeitung kommt dem File-Mapping-Mechanismus daher eine besondere Bedeutung zu. Dieser sollte folgende Aspekte berücksichtigen

• schnelles Laden und Speichern von Dateiabschnitten unter Nutzung hardware-spezifischer Eigenschaften, wie z.B. die Art des Speichermediums (HDD, SSD) und des Dateisystems
• Vorab-Laden von Daten (sog. Prefetching und Caching): Ist ein Datenpunkt einer Teilmenge sichtbar besteht eine hohe Wahrscheinlichkeit, dass auch Nachbar-Punkte sichtbar sind oder durch die nächste Nutzerinteraktion sichtbar werden. Nachbar-Punkte werden vorab geladen, um diese bei Bedarf schnell anzuzeigen.
• Berücksichtigung der Häufigkeit des Zugriffs auf Dateiabschnitte: Höhere Hierarchieebenen der Baumstrukturen werden z.B. sehr häufig verarbeitet, daher werden diese bevorzugt im Arbeitsspeicher gehalten.
• Algorithmen zur Datenverarbeitung müssen den partiellen Dateizugriff berücksichtigen. Ein sequentieller Dateizugriff wird meist schneller als ein stochastischer Zugriff abgearbeitetAusrichtung, Referenzierung und Abstandsbestimmung von Datensätzen

Effiziente Visualisierung mit Level-of-Detail-Verfahren

Unabhängig von der Gesamtanzahl der 3D-Datenpunkte ist die Anzahl der darstellbaren Punkte durch die Pixel-Auflösung des Bildschirms limitiert. Ein HD-tauglicher Bildschirm mit einer Auflösung von 1920×1080 Pixeln kann z.B. nur circa zwei Millionen Punkte darstellen – alle weiteren Punkte müssen also nicht verarbeitet werden, da sie ohnehin nicht darstellbar sind. Die aktuell sichtbaren Punkte ändern sich jedoch stetig je nach Interaktion des Anwenders. Dieser kann in einen Bereich der Daten zoomen, die Daten rotieren oder auch verschieben. Technisch wird dies über eine virtuelle Kamera realisiert, welche je nach Standort die 3D-Datenpunkte auf den Bildschirm projiziert. Ohne eine gezielte Vorverarbeitung werden alle Datenpunkte projiziert, auch diejenigen die letztlich außerhalb des Bildschirms liegen und nicht sichtbar sind. Insbesondere bei dichten Datenmengen werden zudem viele 3D-Datenpunkte auf denselben Bildschirmpixel abgebildet. Bei einer Gesamtdatenmenge von bereits 100 Mio. Punkten würden 98% aller Punkte für die Visualisierung unnötigerweise verarbeitet. Das Potential zur Effizienzsteigerung ist demnach enorm.

Hierzu werden schließlich die Baumstrukturen in verschiedenen Anwendungsarten genutzt. Soll auf dem Bildschirm z.B. die gesamte Datenmenge sichtbar sein, so ist es ausreichend eine entsprechende geringere (d.h. obere) Auflösungshierarchie aus der Baumstruktur zu wählen und feinere Details unterer Hierarchien nicht zu betrachten (siehe Abbildung 1/2). Ändert sich der virtuelle Kamerastandort und soll lediglich ein Ausschnitt der Datenmenge sichtbar sein so wird wiederum nur die entsprechende Verzweigung der Baumstruktur ausgewählt und in der entsprechend sinnvollen Bildschirmauflösung angezeigt. Dieses Prinzip wird auch als Level-of-Detail-Methode bezeichnet.

Zusätzlich führt man eine entfernungsabhängige Filterung durch, um zu vermeiden, dass mehrere hintereinanderliegende 3D-Punkte auf denselben Bildschirmpixel abgebildet werden. Denn projiziert man einen Pixel in den Raum so bildet dieser ein Volumen und die darin enthaltenen Punkte werden alle auf denselben Bildschirmpixel abgebildet. Es wird demnach nur derjenige 3D-Punkt visualisiert, der räumlich vor allen anderen liegt. Dieses Prinzip wird mithilfe des Tiefenpuffers und den entsprechenden Grafikkartenfunktionen umgesetzt (siehe Abbildung 3/4).

Optimiertes Rendering

Für die Visualisierung und Wahl der optimalen Level-of-Detail-Strategie spielt zudem die Wahrnehmung des Anwenders eine wichtige Rolle. Eine neue Ansicht muss schnell ermittelt und angezeigt werden. Bei sehr großen Datenmengen und verzögerten Ladeprozessen sollten dazu Zwischenansichten generiert und ineinander überblendet werden, um dem Anwender eine zeitnahe Rückmeldung auf seine Interaktion zu geben. Es ist zudem hilfreich, eine gering aufgelöste Kopie der Gesamtdatenmenge stetig und sofort verfügbar im Grafikkartenspeicher zu halten. Dies unterstützt den Anwender bei der Navigation und der Interaktion mit den Daten wenn Ladeverzögerungen auftreten.

Doch trotz aller Optimierungsmaßnahmen ist eine Echtzeitvisualisierung von enorm großen Datenmengen nicht uneingeschränkt möglich. Es kann eine Verzögerung entstehen, bis alle sichtbaren Punkte ermittelt, geladen und dargestellt sind. Eine weitere, vor allem visuelle, Effizienzsteigerung erreicht man durch ein mehrstufiges Visualisieren (sogenanntes deferred rendering). Hierbei werden die Datenpunkte, die nahe dem Betrachter sind zuerst und schnell gezeichnet. Die Punkte in der Entfernung, die nicht im direkten Fokus des Betrachters sind werden dann sukzessive hinzugezeichnet. Hierdurch entsteht der visuelle Eindruck, dass trotzdem alle wichtigen Datenpunkte schnell gezeichnet wurden.

Zusammenfassung

Durch die Anwendung intelligenter Verfahren zur Datenspeicherung und Datenverwaltung auf Basis von Baumstrukturen können selbst enorm große 3D-Datenmengen effizient visualisiert und verarbeitet werden. Aktuelle Rendering-Strategien verbessern die Leistungsfähigkeit der Visualisierung zusätzlich. Da lediglich die aktuell sichtbaren 3D-Datenpunkte in der begrenzten Bildschirmauflösung ermittelt, geladen und dargestellt werden müssen besteht für die beschriebene Methodik zudem keine theoretische Obergrenze für die Gesamtgröße der Daten.