Performanceoptimierung Mercatorprojektion

02.06.2017

Nachdem ich neulich die dreidimensionale Generierung von Spielwelten durch eine Mercatorprojektion auch in der zweiten Dimension abgebildet hatte, machte ich mir einige Gedanken zur Performance der Generierung...

Die Mercatorprojektion lief wie folgt ab: zu jedem Pixel bestimmte ich Longitude und Latitude der Richtung des Strahls, der ausgehend aus dem Koordinatenursprung den Planeten durchstoßen müsste, um den korrekten Ort für die Einfärbung des Punktes in der Projektion zu bestimmen. Anschließend wurden alle Dreiecke, die den Planeten als Gesamtheit darstellen daraufhin untersucht, ob der Strahl sie traf. sobald eines gefunden wurde, wurde die Suche abgebrochen und der Pixel mit der Farbe dieses Dreieckes eingefärbt.

Zunächst einige Randbedingungen: Die Erzeugung der Benchmark-Planeten lief bis in die 6. Rekursionsebene. Daraus resultieren 81920 Dreiecke. Die Mercatorprojektion wurde als Bild mit einer Auflösung von 800 Pixel * 600 Pixel erzeugt. In einem Single-Thread Durchlauf ohne irgendwelche Optimierungen wurde eine Generierung in rund 28 Sekunden absolviert.

ray tracing took 00:28:32.358739

Da hierbei der Computer nur zu 25% ausgelastet war, war die nächste Optimierung klar: Alle Kerne wurden genutzt. Die Tests ergaben, dass bereits 4 Threads (einer pro Kern) für die Rückprojektion ausreichten, die Auslastung des Rechners auf 99% zu heben. Wir ich bereits im Hauptseminar lernte, macht es keinen Sinn, Raytracing mit General-Purpose-CPUs auf Pixelebene zu parallelisieren. Daher wurden Worker erstellt, die jeweils eine Zeile der Projektion zu berechnen hatten und vier Threads, die diese insgesamt 600 Worker abarbeiten mussten. Dadurch wurde eine Beschleunigung erreicht, die jedoch nur marginal ausfiel: nunmehr brauchte die Erzeugung der Projektion nur noch rund 20 Sekunden:

ray tracing took 00:20:14.845007

Das reichte mir noch nicht. Da die Suche bisher in einem großen unsortierten Heuhaufen von Dreiecken operierte, versuchte ich vor dem eigentlichen Check auf Durchdringung eines Dreiecks durch den Strahl - eine Aufgabe, die mit vielen komplexen Operationen (Trigonometrie, Quadratwurzeln,...) verbunden ist - die Anzahl der zu testenden Dreiecke zuu reduzieren. Ich teilte dazu den Raum in Oktanten ein und testete vor jedem Durchdringungstest zunächst, ob der Strahl in den Oktanten zeigte, in dem das fragliche Dreieck lag. Diese Optimierung lieferte drastisch bessere Ergebnisse - die Berechnung wurde nun in erwas mehr als 11 Sekunden erledigt:

ray tracing took 00:11:23.174519

Die Berechnung des Oktanten für die Dreiecke wurde aus dem Code für den Durchdringungscheck ausgelagert - jetzt berechnete ich den Oktanten für jedes Dreieck vor Beginn der Projektion. Dadurch erreichte ich eine nochmalige Verbesserung auf rund 10 Sekunden:

ray tracing took 00:10:14.295899

Bis zu diesem Zeitpunkt mussten sich die einzelnen Worker beim Übertragen der Farben in das Zielbild immer noch synchronisieren - Daher erzeugte ich nun ein Zielbild für jeden Worker, deren Inhalte ich nach Abschluss der Berechnung "übereinanderkopierte", woraus erst das eigentliche Zielbild entstand. Das machte den Prozess der Erzeugung nochmals geringfügig schneller und ich erreichte das erste Mal eine Zeit von unter 10 Sekunden:

ray tracing took 00:09:44.255353

An diesem Punkt bemerkte ich einen fatalen Fehler in der Bestimmung der Oktanten der dazu führte, dass ich bisher die Dreiecke nicht in 8, sondern nur in zwei Untermengen aufgeteilt hatte. Dieser Fehler wurde beseitigt und die Separierung der Dreiecke nochmals erweitert: Nunmehr benutzte ich statt 8 Oktanten 16 Bereiche (wie nennt man das eigentlich?) und dadurch wurde der vorerst letzte Quantensprung in der Performance erreicht:

ray tracing took 00:02:56.765160

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

  • Mandelbrot-Sets mittels Shadern berechnen

    17.05.2019

    Nachdem ich in den letzten verregneten Tagen auf Youtube in den Videos von Numberphile versunken bin, hat mich eines davon angestachelt, mich selbst mit dem Mandelbrotset zu beschäftigen. Als ich dann noch Code fand, der behauptete, das auf einer Graphikkarte mittels Shadern berechnen zu können, war es um mich geschehen...

    Weiterlesen...

Neueste Artikel

  • Erste Vor-Version eines Gis-Plugin für die sQLshell

    Wie bereits in einem früheren Artikel erwähnt plane ich, demnächst ein Plugin für die sQLshell anzubieten, das eine Visualisierung von Daten mit räumlichem Bezug im Stil eines Geoinformationssystems erlaubt.

    Weiterlesen...
  • bad-certificates Version 2.1.0

    Das bereits vorgestellte Projekt zur automatisierten Erzeugung von Zertifikaten mit allen möglichen Fehlern hat eine Erweiterung erfahren und verfügt über ein Partnerprojekt - beide sind nunmehr in der Version 2.1.0 freigegeben

    Weiterlesen...
  • SQLite als Geodatenbank

    Wie bereits in einem früheren Artikel beschrieben treibe ich derzeit Anstrengungen voran, die sQLshell attraktiver für Nutzer zu machen, die mit Geodatenbanken arbeiten.

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier - meine öffentlichen GitLab-Repositories finden sich dagegen hier.