ck's Blog

Ein letztes Kapitel meines Studiums bin ich noch schuldig geblieben: Die Veröffentlichung meiner Diplomarbeit. Da meine Abschlussarbeit schon seit geraumer Zeit korrigiert ist, kann ich diese nun endlich verlinken und somit jedermann zugänglich machen. Worum es thematisch geht, hatte ich ja bereits in einem früheren Blogeintrag erzählt. Deshalb möchte ich nur noch ein mal den Titel erwähnen: Deflektomtrische Positionsbestimmung gegebener Geometrien mit Grafikkartenbeschleunigung.

Thematisch kann ich an meiner neuen Wirkungsstätte an meinem Diplomarbeitsthema in Teilen anknüpfen. Ich forsche nun intensiv im noch recht neuen aber schon sehr weitläufigen Gebiet der GPGPU-Programmierung im Kontext der Nutzung für High Performance Computing. Genau eine Aufgabe, wie ich sie mir vorgestellt habe.

Es ist vollbracht. Heute hab ich als letzten Akt meines Informatikstudiums meine Diplomarbeit abgegeben, die mich grob die letzten neun Monate beschäftigt hat. Zusammen mit meinen Diplomprüfungen von vor ziemlich genau einem Jahr war’s das dann auch inoffiziell mit der Studenterei.

Sobald ich grünes Licht habe, will ich die insgesamt 143 Seiten hier in meinem Blog veröffentlichen, so wie ich das auch mit meinen bisherigen Dokumenten aus meiner Studienzeit gemacht habe. Bis dahin kann ich nur von 42 (man beachte die Zahl) Abbildungen und 15 Tabellen reden, zeigen kann ich sie jedoch noch nicht.

Jetzt sind erst mal knapp zwei Monate Ferien und Akku aufladen angesagt, bevor’s mit Arbeiten losgeht. Wo’s mich da hin verschlägt, verrate ich ein andermal. Jetzt bleibt erst mal zu hoffen, dass April und Mai viele schöne Tage zu bieten haben. Falls nicht: Der Stapel von Serien, die angesehen werden wollen, ist durchaus beachtlich. Auch das ein oder andere PC-Spiel will angetestet werden. Und die Bahn freut sich bestimmt, wenn ich ihr ein paar Euro vermache und sie mich dafür quer durch Bayern kutschiert um Corny, Hagi, Steffen und Co. zu besuchen.

Dom schreibt parallel mit mir auch an seiner Diplomarbeit und twittert darüber fleißig. Seine mehr oder weniger großen Erfolge postet er im Stil “Achivement unlocked“, wie man es von neueren Videospielen her kennt. Erreicht der Spieler dort ein gewisses Limit, legt einen besonderen Stunt hin oder ist in einem Bereich einfach nur besonders gut, so wird ihm eine digitale Auszeichnung zu Teil.

Genau nach diesem Schema verleiht sich Dom selbst kleine Awards für seine Fortschritte, die durchaus nett zu lesen sind. Deshalb bin ich so dreist und kupfere das kurzerhand von ihm ab und übertrage das auf meine eigene Diplomarbeit.

• Achivement unlocked: Antwort auf die Frage “nach dem Leben, dem Universum und dem ganzen Rest”
  Deine Diplomarbeit enthält die Zahl 42.
• Achivement unlocked: Mathematisches Selbstbewusstsein
  Deine Diplomarbeit enthält das Wort (nicht-) trivial.
• Achivement unlocked: Dummschwätzer
  Deine Diplomarbeit enthält Wörter wie sinnfrei, Diskrepanz und legitim.
• Achivement unlocked: Paper Blender
  Deine Diplomarbeit enthält Floskeln wie “stattdessen sei auf [...] verwiesen” und dein Literaturverzeichnis hat 40 Einträge überschritten.
• Achivement unlocked: Nerd
  Deine Diplomarbeit enthält einen popkulturellen Bezug.

…, so lautet er, der Titel meiner Diplomarbeit. Jetzt und heute nehme ich mir endlich mal die Zeit um zu schreiben, was mich seit einem halben Jahr und so richtig intensiv seit knapp über drei Monaten beschäftigt und noch spätestens bis zum 09. April beschäftigen wird.

Dass ich meine Abschlussarbeit im Fach Informatik erarbeite dürfte hinlänglich bekannt sein. Genauer gesagt in der Disziplin “Bild- und Signalverarbeitung”, meinem Vertiefungsgebiet, in dem ich auch schon Programmierpraktikum, HiWi-Job und gesonderte Diplomprüfung gemacht habe. Noch genauer gesagt wird mein Thema von FORWISS gestellt, einem an die Uni angegliederten Forschungsinstitut.

Deflektometrie ist ein optisches Inspektionsverfahren zur Qualitätsprüfung stark spiegelnder Oberflächen. Sie kann beispielsweise kleinste Kratzer und Unebenheiten der zu vermessenden Bauteile detektieren. Solche Bauteile können Komponenten von Maschinen und im Speziellen Teile von Autos sein aber auch andere Dinge wie hoch präzise geschliffene Spiegel für die Astronomie oder Werkzeuge für den Medizinbereich. Daher das Wort “deflektometrische” im Titel.

Jedoch betrachtet Deflektometrie nur die Oberfläche selbst, liefert jedoch keine direkten Informationen über das zu inspizierende Objekt. Das heißt, sie macht keine Aussagen über die räumliche Orientierung oder das geometrische Aussehen des zu untersuchenden Bauteils. An dieser Stelle kommt das Wort “Positionsbestimmung” ins Spiel. Während die deflektometrischen Messdaten bisher hauptsächlich für die Oberflächeninspektion eingesetzt werden, möchte ich sie verwenden, um Ort und Lage des zu vermessenden Gegenstands zu berechnen.

Das bedeutet genauer, dass ich einen (digitalen) Entwurf des zu prüfenden Objekts habe (daher das “gegebener Geometrien”) und nun wissen will, wie ich diesen virtuellen Entwurf rotieren (also drehen) und translieren (also nach nach oben/unten, vorne/hinten und links/rechts bewegen) muss, damit er mit dem gerade unter dem Versuchsaufbau durchlaufenden realen Bauteil übereinstimmt. Diese Informationen benötigt man, wenn man weitere Qualitätsprüfungen, die über die bloßen Oberflächeneigenschaften hinaus gehen, machen möchte. Zum Beispiel ist es interessant zu wissen, ob die Geometrie innerhalb gewisser Toleranzen gefertigt wurde, ein Fortsatz beispielsweise nur in geringen Maßen vom Optimum abweicht.

Zwar gibt es schon Verfahren, die einem diese Informationen liefern (zum Beispiel Stereorekonstruktion oder Lasermessverfahren), der Clou besteht jedoch darin, eine einzige Messung (nämlich die deflektometrische) herzunehmen um möglichst viele Aussagen über den zu prüfenden Gegenstand machen zu können.

Fehlt noch das “mit Grafikkartenbeschleunigung” aus dem Titel. Dazu muss ich ein bisschen weiter ausholen und beschreiben, wie diese Positionsbestimmung genau abläuft. Im Prinzip geht man her, wählt sich einen beliebigen Satz von Positionsdaten (im Detail handelt es sich dabei um sechs Parameter), führt mit diesem Parametersatz eine virtuelle, simulierte deflektometrische Messung durch und vergleicht diese mit den real aufgenommenen deflektometrischen Messdaten. Virtuell und simuliert bedeutet in diesem Fall, dass diese Berechnungen am Computer stattfinden. In der Regel wird dieser erste beliebige Satz von Positionsparametern nicht mit dem realen Satz von Positionsparametern übereinstimmen. Aus diesem Grund versuche ich im nächsten Schritt einen neuen Satz von Variablen zu finden, die dem realen Satz eher entsprechen als der Erste. Da ich den realen Parametersatz gedoch nicht kenne (den suche ich ja, Stichwort “Positionsbestimmung”) muss ich wieder den Umweg über die Simulation und den Vergleich der virtuellen deflektometrischen Messung mit der realen gehen. Das wiederhole ich so lange, bis Simulation und Realität möglichst gut (am besten perfekt) übereinstimmen.

Natürlich wähle ich nicht wild irgendwelche virtuellen Positionsparameter. Ich möchte ja zum Ziel kommen. So sollte in jedem Schritt der Fehler zwischen virtueller und realer deflektometrischer Aufnahme kleiner werden. Eine Metrik, die mir diesen Fehler misst, musste ich unter anderem in den letzten Monaten erarbeiten. Dass ich auch eine gefunden habe, hatte ich schon gebloggt. Nun kann ich endlich zur Grafikkartenbeschleunigung kommen. Die Algorithmik für die Simulation der Deflektomtrie ist nämlich extrem aufwändig. Außerdem werden extrem viele Iterationsschritte benötigt, bis Simulation und Realität übereinstimmen. Jedoch lassen sich die Berechnungen an vielen Stellen massiv parallelisieren. An dieser Stelle kommen die Grafikkarten ins Spiel: Diese können heutzutage nämlich nicht nur 3D-Visualisierungen erstellen sondern lassen sich mit beliebigen Berechnungen füttern, die überhaupt nichts mit der Darstellung von 3D-Szenen am Monitor zu tun haben. Dabei profitieren im Vergleich zur klassischen CPU-Berechnung eben genau diejenigen Probleme, die sich gut parallelisieren lassen, so wie das bei meinen Simulationen der Fall ist.

Wer nun denkt, dass sich das schon alles kompliziert anhört, dem sei eine kurze Liste von Fachtermini ans Herz gelegt, die bei der Lösung der eben skizzierten Aufgabe auftauchen: Bounding Volume Hierarchies, baryzentrische Koordinaten, nichtlineare Optimierung, effektives Hashing, Quadriken, registerarmes Programmieren, Modellierung präziser Kameraoptiken mit Verzeichnungen und und und…

Einer der zahlreichen Schritte meiner Simulationsberechnungen ist die Darstellung extrem dreiecksreicher Modelle der (gegebenen) Geometrien, deren Position ich bestimmen möchte. Somit haben meine Grafikkartenberechnungen doch wieder was mit der Visualisierung von 3D-Szenarien zu tun. Jedoch handelt es sich bei mir wie gesagt nur um einen Zwischenschritt und während bei 3D-Spielen das Verfahren der Rasterisierung zum Einsatz kommt verwende ich das wesentlich präzisere Raytracing. Der Grund, warum ich den letzten Absatz geschrieben habe ist, dass ich meiner Leserschaft auf diese Weise ein paar tolle Bilder präsentieren kann, die mittlerweile facettenreicher und vor allem korrekter schattiert sind als die meines ersten Blogeintrags zu diesem Thema.

Eine Fläche mit Geschlecht 3 bestehend aus 467240 Dreiecken schattiert mit einem leicht modifizierten Gouraud Shading.

Dieser Drache besteht aus 869910 Dreiecken. Auf meiner Hardware (GeForce 8800 GTS 512) dauert das Rendern dieses Bildes etwa 150ms.

Nachdem ich vor gut zwei Monaten an selber Stelle verkünden durfte, dass mir bei meiner Diplomarbeit der große algorithmische Durchbruch gelungen ist, gibt’s heute den nächsten Meilenstein zu feiern. Musste ich mir beim ersten mal noch alles selbst ausdenken konnte ich für meinen zweiten großen Erfolg auf zahlreiche Paper zurück greifen.

Zwar bin ich immer noch nicht dazu gekommen meine Diplomarbeit hier im Blog genauer und auch für Laien verständlich vorzustellen, jedoch kann man zum heutigen Meilenstein auch ohne große Einleitung einiges erzählen. Wie an den beiden Bildern unten zu erkennen ist, muss ich es offensichtlich geschafft haben, den Teapot und das Bunny zu rendern. Was soll daran nun so besonders sein? Mit OpenGL sollte sowas doch relativ schnell realisiert sein. Mit DirectX auch. Darüber hinaus sieht die Schattierung der beiden Modelle auch noch äußerst gewöhnungsbedürftig aus. Was ist da nun so toll dran?

Nun, gerendert wurden die Modelle weder mit OpenGL noch mit DirectX sondern mit meinem eigenen in CUDA geschriebenen Raytracer. Die Berechnungen zur Erstellung der Bilder werden also nicht vom Hauptprozessor sondern von der Grafikkarte durchgeführt mit dem Vorteil, dass ich 100%ige Kontrolle über den Programmfluss habe, was mir bei OpenGL und DirectX in dieser Form nicht möglich gewesen wäre.

Diese Kontrolle brauche ich, da es in meiner Diplomarbeit nicht primär um Visualisierungen von Dreiecksmengen geht sondern ich die grundlegende Algorithmik eines Raytracers für eine interne Simulation ohne grafische Ausgabe benötige. Auf diese Weise erklärt sich auch die merkwürdige Schattierung: Die Farbe eines Dreiecks korrespondiert nämlich mit dessen Indexnummer in der globalen Dreiecksliste und hat also nichts mit irgendwelchen Beleuchtungen zu tun.

Für all diejenigen, die sich ein wenig näher mit der Materie auskennen dürfte das jetzt alles recht trivial wirken. Jedoch steckt da im Hintergrund doch noch einiges an Intelligenz drin: Zur Beschleunigung werden die Dreiecke des Modells in einer hierarchischen Struktur, einer sogenannten Bounding Volume Hierarchy organisiert. Diese parallel auf der Grafikkarte zu traversieren war die eigentliche Herausforderung. Somit schaffe ich es im Moment pro Sekunde eine dreistellige Anzahl von Bildern in einer Auflösung von 1024×768 zu erstellen. Genau habe ich das noch nicht gebenchmarkt. Darüber hinaus handelt es sich bei den unteren beiden Bilder um das Ergebnis der allerersten Version meiner Software. Da ist noch nichts optimiert, weder irgendwelche Parameter noch eine Zeile Programmcode.

Diese Version des Teapot besteht aus 4032 Dreiecken. Mit größeren Dreiecksmengen kann ich im Moment noch nicht arbeiten, da zwar das Rendering bereits relativ effizient von Statten geht, der Aufbau der zugrunde liegenden Hierarchisierug des Modells noch äußerst ineffizient vom Hauptprozessor übernommen wird.

Das Modell des Bunny besteht aus 3999 Dreiecken.

Hätte ich einen Twitter Account, dann wäre das hier eine ideale Nachricht für den berühmten Microblog.

Im Moment bin ich nämlich dabei, meine CPU samt ihren vier Kernen so richtig zum Schwitzen zu bringen. Nachdem ich gestern nach sehr langer Zeit endlich den algorithmischen Durchbruch bei meiner Diplomarbeit vermelden konnte gilt es nun, die zahlreichen zur Verfügung stehenden Parameter meines Verfahrens so zu optimieren, dass das Ergebnis zwar einer gewissen Güte entspricht, die Berechnungen jedoch nicht all zu lange dauern. Dazu werden im Moment zahllose Parameterkombinationen getestet, welche denn nun den besten Trade-Off ergibt.

100% Prozessorauslastung sehen dann so aus:

OK, jetzt sind es doch mehr als die twittertypischen 140 Zeichen geworden, aber beim Zwitscherdienst hätte ich mich bestimmt kürzer gefasst *gg*.

Moment mal. Vor knapp zwei Jahren gab’s ja schon mal einen Artikel mit praktisch dem selben Namen. Damals berichtete ich von dem wichtigsten Entwicklungsschritt (der noch reichlich fehlerbehaftet war) bei meinem Programmierpraktikum.

Heute kann ich vom wohl wichtigsten Durchbruch bei meiner Diplomarbeit berichten (daher auch das “in groß”), allerdings wohl auch noch reichlich fehlerbehaftet. Wieder habe ich ein mehr oder weniger aussageloses Bild zur Untermauerung meines Erfolgs. Da ich ja schon seit längerem etwas detaillierter über meine Abschlussarbeit berichten wollte, ich jedoch noch nicht die Muse dazu hatte, wird die Verwirrung der nun folgenden Bilder nun noch größer und die Klarheit noch geringer sein. Naja, immerhin habe ich in meinem letzten Blogeintrag mal den Titel online gestellt: Deflektometrische Positionsbestimmung gegebener Geometrien mit Grafikkartenbeschleunigung.

Natürlich lässt sich diese Konsolenausgabe auch grafisch interpretieren.

Somit habe ich den unkalkulierbarsten Teil meiner Diplomarbeit erledigt: Das Finden eines Algorithmus, der mir ein ganz bestimmtes Problem löst. Meine Diplomarbeit ist damit zwar noch sehr lange nicht beendet, aber alle nun folgenden Schritte lassen sich zeitlich wesentlich besser planen. Schließlich weiß man nicht, wann man die Lösung für ein Problem findet oder ob man sie überhaupt findet.

Auf alle Fälle bin ich nun verständlicherweise sehr glücklich. So ein Durchbruch sorgt für Motivation, die ich gleich für weitere Ergebnisse und Erkenntnisse nutzen möchte. Ich bin dann mal wieder bei meiner Diplomarbeit…

…, das bin ich seit heute ganz offiziell. Gestern war mein letzter Tag als immatrikulierter Student.

Naja, eigentlich bin ich nur im beruflichen Sinne arbeitslos, denn im Moment arbeite ich mit Volldampf an meiner Diplomarbeit, habe also sehr wohl etwas zu tun. Da man aber an der Universität Passau seine Diplomarbeit auch abgeben kann, wenn man nicht mehr immatrikuliert ist und ich sonst nichts mehr zu erledigen habe an der Uni, spare ich mir so die Studiengebühren für’s Wintersemester 2009/10. Lediglich zur Anmeldung einer Diplomarbeit muss man offiziell Student sein, weshalb ein Besuch im Prüfungssekretariat gestern meine letzte offizielle Studentenhandlung war.

Somit hab ich jetzt ganz offiziell sechs Monate (und ein paar zerquetschte Tage, bis ich die Bestätigung per Post bekomme) Zeit bis zur Fertigstellung meiner Abschlussarbeit. Wundert mich eigentlich, dass ich da drüber noch nicht gebloggt habe, schließlich ist das Thema und die Roadmap der Vorgehensweise mittlerweile klar. Den Titel kann ich an dieser Stelle ja mal posten: “Deflektometrische Positionsbestimmung gegebener Geometrien mit Grafikkartenbeschleunigung”. Klingt komplex, ist es in Teilen auch, aber diese sechs Wörter treffen die Thematik perfekt.

*Ironie on* So, nun kann ich auch über die ach so faulen Studenten mit ihrem Öko- und Revolutionsgehabe schimpfen, da ich selbst keiner (mehr) bin. Und ich kann mich als arbeitsloser Penner fühlen, der zu Hause rumhängt, Vater Staat auf der Tasche liegt und protestwählt (verdammt, Bundestagswahlen waren erst). *Ironie off*