Der Alpstein als digitales 3D Geländemodell

Ich bin noch zu Zeiten der ersten StarWars Kinofilme sozialisiert worden. Die Animationen der Verfolgungsjagden durch dreidimensionale Schluchten des Todessterns hatten mich damals schon mächtig beeindruckt.

Die SpaceMouse zur 6DOF-Steuerung der 1st-person Perspektive habe ich ja nun «im Griff«. Fehlt nur noch ein geeignetes Gelände um da wie Luke Skywalker virtuell durchzusausen. Es sollte kein zufällig generiertes sein, sondern möglichst ein reales und mir zumindest grob bekanntes Revier abbilden.

Nach einiger Recherche stiess ich auf das Schweizer Bundesamt für Landestopographie «Swisstopo». Dieses stellt u.a. das Produkt swissALTI3D (bei Einhaltung der Lizenzbedingungen) zur kostenfreien Nutzung per download zur Verfügung. Die Abdeckung umfasst das vollständige Gebiet der Schweiz und Liechtensteins. Die Daten werden in quadratischen «Kacheln» von 1 km Kantenlänge angeboten. Die maximale angebotene Auflösung von 0,5 Metern übertrifft dabei alles mir bisher Bekannte.

Die Kehrseite der enorm hohen Detaillierung ist ein entsprechendes Datenvolumen, welches sämtliche Komponenten eines Computersystems (Netzwerkanbindung, Hauptspeicher, Festplattenspeicher, CPU, GPU) so verarbeiten können sollten, daß ein Anwender im Endergebnis mit einer interaktiven Bildwiederholrate von mindestens 30 fps durch die Szene navigieren können sollte.

Numbers, please!

Über welche Größenordnungen rede wir? Ich habe mich aus allen von Swisstopo zum Download angebotenen Dateiformaten wegen der für Menschen leichten Lesbarkeit für «ASCII X,Y,Z» in 0,5 m Auflösung entschieden. Die Darstellung und Speicherung von Fliesskommazahlen als Zeichenketten ist zwar speicherintensiv und aufwändig zu dekodieren, aber ich war zunächst an schnellen Ergebnissen interessiert. Einer Antwort auf die Frage, ob es sich lohnt, das Projekt ernsthaft zu verfolgen. Daß hier Optimierungspotenzial schlummert, ist mir bewusst.

So sehen die ersten (und letzten) Zeilen einer solchen Kachel aus:

X Y Z
2748000.25 1233999.75 1789.25
2748000.75 1233999.75 1788.82
2748001.25 1233999.75 1788.57
2748001.75 1233999.75 1788.17
...
...  // insgesamt 4 Millionen Datenzeilen 
...
2748998.25 1233000.25 1717.90
2748998.75 1233000.25 1717.75
2748999.25 1233000.25 1717.53
2748999.75 1233000.25 1717.34

Eine quadratische Kachel mit 1 km Kantenlänge erfordert bei 0,5 m Auflösung ein Raster aus 2’000 * 2’000 = 4’000’000 Datenpunkten. Jede der oben gezeigten Zeilen aus dem ASCII File entspricht einem Datenpunkt mit seinen X,Y,Z Koordinaten. Insgesamt resultiert eine Dateigröße von 124’000’007 Byte, entsprechend 124 MB pro Kachel.

Sämtliche Werte haben die Einheit [m], der Punkt entspricht dem Dezimaltrennzeichen. X- und Y-Werte beziehen sich auf die Schweizer Landesvermessung aus dem Jahr 1995, gemäß folgendem Schema:

Die Z-Werte geben die ellipsoidische Höhe an.

Für die Visualisierung der Geländedaten verwende ich die Three.js Bibliothek, im Speziellen eine THREE.PlaneGeometry(). Diese stellt die nötigen Datenstrukturen bereit zur Aufnahme von Positionsdaten der beteiligten Punkte (vertices), sowie zusätzlich die Zerlegung der Ebene in ein zusammenhängendes Gitternetz aus Dreiecksflächen, inklusive der Index-Zuordnung, durch welche vertices jede Dreiecksfläche begrenzt wird.

Mit den vorliegenden Daten lässt sich eine Kachel bisher lediglich als Drahtgittermodell darstellen:

Diese Art der Darstellung reicht aus, um einen ersten Eindruck von der Topographie zu erhalten. Die unvermeidliche Transparenz eines Drahtgitters macht aber die Unterscheidung zwischen nah und fern, Vorder- und Rückseite u.U. mehrdeutig und verwirrend.

Besser wäre eine flächige und schattierte Darstellung, weil hier die näher am Betrachter liegenden Dreiecksflächen evtl. dahinterliegende Flächen verdecken würden, und Helligkeitsnuancen aufgrund unterschiedlich ausgerichteter Flächen- oder Eckpunktnormalen relativ zur Lichtquelle den plastischen 3D-Eindruck verstärken würden.

Die bei Swisstopo erhältlichen Daten enthalten zwar keine Normalen-Information, aber zum Glück lassen sich diese berechnen. Die Datenstrukturen von THREE.PlaneGeometry() sind zudem bereits auf die Aufnahme von vertex normal Daten pro vertex eingerichtet. Man muss sie allerdings zuvor berechnen, und Three.js bietet sogar eine passende Funktion dafür an: computeVertexNormals() .

Der Aufruf dieser Funktion ist zwar nur ein Einzeiler, dahinter verbergen sich jedoch aufwendige Berechnungen, welche für jede einzelne Dreiecksfläche durchgeführt werden müssen. Bisher hatte ich nur über 2’000 x 2’000 = 4 millionen Eckpunkte in der höchsten Auflösungsstufe gesprochen. Diese regelmäßig auf Rasterschnittpunkten angeordneten Eckpunkte umschließen 1’999 x 1’999 quadratische Zellen, von denen jede nochmals diagonal in zwei Dreiecksflächen unterteilt ist. In der vollen Auflösung von 0,5 Metern sind dies

1’999 x 1’999 x 2 = 7’992’002 Dreiecksflächen pro Kachel.

Für jede Dreiecksfläche, begrenzt durch die Eckpunkte «A», «B» und «C» werden in der Funktion computeVertexNormals()

• die Differenzvektoren D1 =»A» – «B» und D2 = «B» – «C» gebildet,
• das Skalarprodukt aus D1 und D2 berechnet, welches definitionsgemäß senkrecht (also «normal») auf der durch «A», «B» und «C» aufgespannten Ebene steht.
• Die so ermittelte Flächennormale wird auf jede Eckpunktnormale in den Punkten «A», «B» und «C» aufaddiert, so daß sich schliesslich für jeden Eckpunkt die aus den Flächennormalen aller angrenzenden Flächen gemittelte Eckpunktnormale ergibt.
• Die Eckpunktnormalen (vertex normals) werden schließlich noch normiert, d.h., auf die Länge «1» gebracht.

Und das für jede der knapp 8 millionen Eckpunkte einer Kachel. Das Ergebnis sieht dann beispielsweise so aus:

Schließlich habe ich noch eine on-the-fly generierte Höhenlinien-Textur (Rasterweite: 100 m) aufgebracht, die meiner Meinung nach die Einschätzung des Geländes (welche Punkte befinden sich auf gleicher Höhe, bzw. liegen wieviel höher oder tiefer) erheblich vereinfacht:

Wir erinnern uns: die ursprüngliche Dateigröße einer ASCII-codierten Datei mit reinen Positionsdaten lag bei 124 MB. Die Zahl ergibt sich aus 4 millionen Zeilen zu je 31 Zeichen (je 1 Byte) pro Datenzeile. Wer’s nicht glaubt, kann oben nachzählen – dabei die nicht druckfähigen Zeichen «CR» und «LF» an jedem Zeilenende mit berücksichtigen.

Nach Einlesen in die Three.js Datenstrukturen einer THREE.PlaneGeometry() ergibt sich folgender Speicherbedarf:

• Positionsdaten: drei x-, y- und z-Komponenten zu je vier Byte/vertex
• Eckpunkt Normale: drei x-, y- und z-Komponenten zu je vier Byte/vertex
• Texturkoordinaten: zwei u- und v-Komponenten zu je vier Byte/vertex

Insgesamt also (3 + 3 + 2) = 8 x 4 = 32 Byte/vertex. Das 4 millionen mal, macht 128 MB.

Egal, wie effizient (z.B. binär) man die Positionsdaten durch eine Art «Vorkompilierung» in einer Datei abspeichert: in Three.js kommt man an dem genannten Speicherbedarf von 128 MB/Kachel einfach nicht vorbei – in der maximalen Auflösung. Das ist eine wichtige Erkenntnis die noch eine Rolle spielen wird!

Gemessen an meinen eingangs formulierten Ansprüchen (interaktive Bildrate von mindestens 30 fps) erfüllt mein Ansatz auf meinem inzwischen etwas angejahrten iMac aus Late 2014 …

… alle Erwartungen. 60 fps werden unter allen Umständen eingehalten.

Damit wächst natürlich der Appetit: die virtuelle Fahrt durch «Schluchten» ist im Alpstein auf einer 1 km x 1 km Kachel kaum möglich. Also würde ich gerne mehrere Kacheln gleichzeitig darstellen. Ob und wie das evtl. gelingen kann, beschreibe ich in einem Folgeartikel.