StudiengangElektronischeund MechatronischeSysteme ...schorsch.efi.fh-nuernberg.de/mewiki/uploads/... · Als Entwicklungsumgebung für die Web-Applikation des Volumen Renderers wird

Technische Hochschule Nürnberg Georg Simon OhmFakultät Elektrotechnik Feinwerktechnik Informationstechnik

Studiengang Elektronische undMechatronische Systeme

Masterarbeit vonTobias S c h ä f e r

Hierarchisch optimierte Volumenvisualisierung für WebGL

WS 2014/2015

Abgabedatum: 10.2.2015Betreuer: Prof. Dr. Stefan Röttger Tobias Koppers

Markus EberhornFraunhofer Institut

Schlagworte: JavaScript, WebGL, Volume Rendering, GLSL, Octree

Erklärung gemäß APO § 22 (7) Bachelorarbeit Masterarbeit

gemäß RaPO § 35 (7) Diplomarbeit

Studentin/Student (Name, Vorname):

Ich bestätige, dass ich die Abschlussarbeit mit dem Titel:

selbstständig verfasst, noch nicht anderweitig für Prüfungszwecke vorgelegt, keine anderen als die angegebenen Quellen oder Hilfsmittel benützt, sowie wörtliche und sinngemäße Zitate als solche gekennzeichnet habe.

Bei dem vorliegenden Exemplar handelt es sich um eine unkorrigierte Fassung seitens des betreuenden Hochschullehrers.

Datum:

Unterschrift:

Schäfer, Tobias

Hierarchisch optimierte Volumenvisualisierung für WebGL

10.2.2015

Kurzfassung

Kurzfassung

Im Rahmen dieser Arbeit wurde eine Visualisierungssoftware für 3D-Volumendatensätze entwickelt. Bei dieser Software handelt es sich um eine JavascriptApplikation, die über einen Browser aufgerufen werden kann. Um große Volumenda-tensätze visualisieren zu können, werden diese in mehrere Datenblöcke unterteilt undin verschiedenen Auflösungen in einer hierarchischen Datenstruktur abgelegt. Dergroße Vorteil dieser Struktur ist, dass durch die unterschiedlich detaillierten Datendie Leistung und die Qualität der Darstellung variiert werden kann.

Um die Leistung der Applikation zu steigern können niedriger aufgelösteVolumenblöcke angezeigt werden. Für eine Verbesserung der Darstellungsqualitätkönnen höher aufgelöste Daten dargestellt werden.

Das Ergebnis dieser Arbeit sind zwei voneinander unabhängige Programme. Daseine Programm bereitet die Daten für das Speichern in der Datenstruktur vor.Dabei wird ein Octree als Struktur für die Volumendaten verwendet. Das zweiteProgramm nutzt die vorbereiteten Daten und stellt diese mithilfe der WebGL APIim Browser dar. Durch eine adaptive Steuerung der zu visualisierenden Daten wirddie Bildwiederholrate der Darstellung während Interaktionen des Benutzers deutlichverbessert. Die Steuerung wird durch einen Zustandsautomaten realisiert. Für dieBerechnung der Bilder aus den Volumendaten wird eine Image-Order Technik (Ray-Casting) verwendet.

Der in dieser Arbeit entwickelte webbasierte Volume Renderer ist die Basiseiner Applikation zur Visualisierung von Volumendaten. Die bisherigen Ergebnissesind sehr vielversprechend. Durch zusätzliche Features, die unter anderem imAusblick dieser Arbeit beschrieben werden, kann der Funktionsumfang derApplikation weiterentwickelt werden und in der Zukunft Installationen aufwändigerAnalysesoftware ersetzen. Zudem ist es durch den Einsatz von WebGL möglich dieVolumen auf mobilen Endgeräten wie Mobiltelefonen oder Tablets zu visualisieren.

iii

Inhaltsverzeichnis

Inhaltsverzeichnis

Erklärung ii

Kurzfassung iii

1 Einleitung 11.1 Motivation und Ziel der Arbeit . . . . . . . . . . . . . . . . . . . . . . 21.2 Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Grundlagen der Volumendarstellung 42.1 Indirekte Volumenvisualisierung . . . . . . . . . . . . . . . . . . . . . 52.2 Direkte Volumenvisualisierung . . . . . . . . . . . . . . . . . . . . . . 62.3 Ray-Casting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Grundlagen Web 113.1 Entwicklungsumgebung . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 HTML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.3 Javascript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.4 WebGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.4.1 Texturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.4.2 Shader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.4.3 WebGL Rendering Pipeline . . . . . . . . . . . . . . . . . . . . 18

iv

Inhaltsverzeichnis

4 Konzeption 254.1 Octree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2 Vorverarbeitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.2.1 Bricking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2.2 Speicherung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.2.3 Skalierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.3 Volume Renderer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.3.1 Repräsentation der Volumendaten . . . . . . . . . . . . . . . . 374.3.2 Interaktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.3.3 Zustandsautomat der Octree Elemente . . . . . . . . . . . . . 394.3.4 Prioritäten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5 Implementierung 465.1 Kodierung der Voxelwerte . . . . . . . . . . . . . . . . . . . . . . . . 465.2 Erhöhung der Quantisierungsauflösung . . . . . . . . . . . . . . . . . 505.3 Compositing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.3.1 Einfaches Compositing . . . . . . . . . . . . . . . . . . . . . . 535.3.2 Mehrfaches Compositing . . . . . . . . . . . . . . . . . . . . . 58

6 Ergebnisse 60

7 Ausblick 66

A Diagramme viA.1 UML des Programms zur Vorverarbeitung . . . . . . . . . . . . . . . viA.2 UML der Javascript Applikation . . . . . . . . . . . . . . . . . . . . . viiA.3 Zustandsautomat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii

B Testsysteme ixB.1 System A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixB.2 System B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x

Abkürzungsverzeichnis xi

Abbildungsverzeichnis xii

Quellcodeverzeichnis xiv

Literaturverzeichnis xv

v

Kapitel 1Einleitung

1 Einleitung

Seit den ersten digitalen Röntgenaufnahmen (1986 erstmals kommerziell inder Zahnheilkunde) hat sich die Technik rasant weiterentwickelt. Heutzutagefindet Röntgentechnik nicht nur in der Medizin Anwendung, sondern wirdbeispielsweise für die zerstörungsfreie Materialprüfung von Bauteilen angewendet.Hierbei wird der Prüfkörper auf nicht sichtbare Herstellungsfehler überprüft.Durch Weiterentwicklungen der Aufnahmetechnik entstehen immer genauere undhochauflösendere Röntgenaufnahmen. Bei modernen bildgebenden Verfahren wieder Computertomographie werden dreidimensionale Abbildungen der Messobjekteerstellt. Diese 3D-Messdaten werden zusammengefasst als Volumendatensatzgespeichert und können mehrere Gigabyte Speicher verbrauchen.

Parallel zur Verbesserung der Aufnahmetechnik müssen die Programme zurVisualisierung und Auswertung der Daten weiterentwickelt werden. Die Darstellungvon 3D-Volumen wird als Volume Rendering bezeichnet und ist mittlerweile eineigenständiges Fachgebiet der 3D-Computergrafik.

Im Rahmen dieser Arbeit wurde ein Volumen Renderer entwickelt, der auf modernenWebtechnologien basiert. Als Rendering Technik wird ein Ray-Casting Algorithmusverwendet. Die zur Visualisierung notwendigen Daten werden mithilfe eines Octreesstrukturiert und durch einen Zustandsautomaten gesteuert.

1

Kapitel 1Einleitung

1.1 Motivation undZiel der Arbeit

Das Entwicklungszentrum für Röntgen Technik (EZRT) des Fraunhofer Institutsfertigt häufig Auftragsmessungen für Kunden an. Die dabei entstehendenVolumendaten werden dem Kunden derzeit entweder über einen direkten FTP-Download oder einen USB-Stick zugestellt. Um den Datensatz anzusehen muss daskomplette Volumen auf dem Computer des Betrachters gespeichert sein. Darüberhinaus muss die Visualisierungssoftware des EZRT auf dem Computer des Kundeninstalliert sein, um das Objekt darstellen zu können. Zudem stellt diese Softwarehohe Anforderungen an die darunterliegende Hardware des Computers.

Aufgrund der aufwändigen Zustellung und Visualisierung der Daten soll einewebbasierte Software zur Darstellung von Volumendaten entwickelt werden. Durchdie aktuellen Webtechnologien (HTML5) ist es möglich, die Daten direkt im Browserdarzustellen. Auf diese Weise müssen die Volumendaten nicht zuvor direkt beimKunden vorliegen und es wird keine zusätzliche Software benötigt, um die Daten zuvisualisieren.

Die für die Darstellung notwendigen Daten und die Applikation selbst werden vomWebserver bereitgestellt. Die Datensätze liegen hierbei in mehreren Auflösungenbereit und können somit der Geschwindigkeit der Internetverbindung und derLeistungsfähigkeit des Clients angepasst werden. Da mittlerweile auch Browsermobiler Endgeräte den neuen Webstandard HTML 5 teilweise unterstützen, ist eineVisualisierung von 3D-Volumen auch auf Mobiltelefonen oder Tablets möglich.

2

Kapitel 1Einleitung

1.2 Aufbau der Arbeit

Die ersten Kapitel dieser Arbeit geben einen groben Einblick in das Fachgebiet desVolume Rendering. Dabei wird speziell auf die in dieser Arbeit verwendete Technik,das Ray-Casting (Kapitel 2.3), eingegangen.

In Kapitel 3 werden die verwendeten Webtechnologien beschrieben. Hierbei handeltes sich um kurze Erläuterungen zu HTML, Javascript, NodeJS, jQuery und WebGL.Letzteres rückt in diesem Abschnitt in den Fokus, da WebGL für das Verständnisder Arbeit eine sehr wichtige Rolle spielt.

Das Gesamtkonzept der Arbeit wird in Kapitel 4 beschrieben. Dabei wird aufdie Funktionsweise der zwei Teilentwicklungen eingegangen, die im Rahmen dieserArbeit entstanden sind. Der erste Programmteil ist für die Vorverarbeitung derVolumendaten zuständig und wird in Kapitel 4.2 näher beschrieben. Das zweiteProgramm ist die Webapplikation zur Darstellung der Daten und wird in Kapitel 4.3ab Seite 36 erläutert.

In Kapitel 5 wird auf besonders wichtige Stellen während der Realisierung Bezuggenommen. Unter anderem wird in diesem Abschnitt sehr genau erklärt, wie dasCompositing funktioniert.

In Abschnitt 6 wird die entwickelte Software getestet und beurteilt. Darüber hinauswerden die Ergebnisse der Arbeit zusammengefasst. Im letzten Kapitel befindetsich eine Liste, die Ideen für weiterführende Arbeiten an der entstandenen Softwarebeinhaltet.

3

Kapitel 2Grundlagen der Volumendarstellung

2 GrundlagenderVolumendarstellung

Unter Volumenvisualisierung (engl. Volume Rendering (VR)) versteht man Metho-den zur Darstellung von Volumendaten. Volumendaten sind dreidimensionale Da-tensätze, die zum Großteil von Aufnahmen aus der Röntgen-Computertomographie(CT), Magnetresonanztomographie (MRT) oder Positronen Emissions Tomographie(PET) stammen. Volumendatensätze bestehen aus mehreren Schichtbildern (engl.Slices), die zu einem gesamten Datensatz zusammengefasst werden. In jeder Schichtdes Volumens werden Pixelwerte in Reihen und Spalten gespeichert. In einem 3DVolumen spricht man von sogenannten Volumen Pixel (Voxel). Jeder Voxel reprä-sentiert einen Wert, der am einfachsten durch einen Grauwert zu beschreiben ist.Bei der Computertomographie ergibt sich dieser Grauwert durch die Absorptionvon Röntgenstrahlung. Je mehr Röntgenstrahlung von einem Material absorbiertwird, desto heller ist der resultierende Grauwert im Volumendatensatz. Die in dieserArbeit verwendeten Volumendatensätze bestehen aus Voxeln, die Werte der Datenty-pen UInt8, UInt16 oder Float speichern. Abbildung 2.1 veranschaulicht den Aufbausolcher Volumendatensätze.

Im Allgemeinen lassen sich die Methoden der Volumenvisualisierung grob in zweiKategorien unterteilen. Man unterscheidet dabei direkte und indirekte Methoden,die in den folgenden zwei Kapiteln erläutert werden. Dirk Bartz und Michael Meißnerstellen jeweils eine Implementierung dieser Methoden in [7] gegenüber.

4


Abbildung 2.1: Voxel Modell von Volumendatensätzen

2.1 Indirekte Volumenvisualisierung

Indirektes Volume Rendering (IVR) umfasst alle Methoden, die aus denVolumendaten durch einen entsprechenden Algorithmus zusammenhängendeOberflächen extrahieren. Die Oberflächen werden durch Punkte im dreidimensionalenRaum beschrieben, die durch Linien miteinander verbunden werden und zusammenein beliebig komplexes Objekt ergeben. Die dadurch entstandenen Konstrukte werdenin der Computergrafik auch als Polygone bezeichnet. Zur endgültigen Darstellungwerden die Polygone in Dreiecksnetze, sogenannte Meshes, unterteilt. Grafikkartensind für die Darstellung solcher Dreiecksnetze spezialisiert.

Die indirekten Methoden unterscheiden sich imWesentlichen durch den Algorithmus,der die zusammengehörenden Flächen extrahiert. Häufig werden zusammenhängendeOberflächen durch Extraktion von Isoflächen oder Schnittflächen generiert.

5


Ein großer Nachteil der indirekten Methoden ist, dass die Extraktion dieser Oberflä-chen bei großen Volumendatensätzen zeitaufwändig ist. Bei der Isoflächen-Extraktionbilden benachbarte Voxel mit ähnlichen Isowerten eine zusammengehörende Ober-fläche. Über einen Schwellwert kann der Benutzer festlegen, wie weit diese Isowertevariieren dürfen, um zur selben Oberfläche gezählt zu werden. Ein sehr bekannterund weit verbreiteter Algorithmus zur Isoflächen-Extraktion ist der Marching-Cube-Algorithmus, bei dem der Volumendatensatz in kleinere Würfel zerlegt wird. Fürjeden dieser Würfel werden je nach Anzahl und Lage der Voxel, die über bezie-hungsweise unter dem zuvor eingestellten Schwellwert liegen, Dreiecke bestimmt,die das Objekt im Volumendatensatz beschreiben. Eine genauere Erklärung desMarching-Cube-Algorithmus ist in [12] zu finden.

Da die Dateigröße moderner Volumenaufnahmen in der Größenordnung mehrererGigabyte liegt, benötigt ein solcher Algorithmus viel Zeit, um die Isoflächenzu extrahieren. Zudem ist bei einer Änderung des Schwellwertes eine kompletteNeuberechnung der Oberflächen notwendig. Einige der in dieser Arbeit verwendetenDatensätze sind sehr groß, weshalb die Visualisierung durch eine indirekte Methodenicht in Betracht gezogen wurde. Die verwendete Methode zur Volumenvisualisierungwird im folgenden Kapitel näher beschrieben.

2.2 Direkte Volumenvisualisierung

Direktes Volume Rendering (DVR) kommt ohne Vorverarbeitungsschritt aus. ImGegensatz zum IVR wird hierbei nicht versucht, das Volumen in vertexbasierteOberflächen zu unterteilen. Die für die Darstellung notwendigen Daten werdendirekt aus dem voxelbasierten Datensatz gelesen. Dabei werden physikalische Effekteauf einfallende Lichtstrahlen berechnet und für die Darstellung verwendet. Es wirdangenommen, dass dieses Licht vom Betrachter der Szene ausgeht. Von dort ausbreiten sich die Lichtstrahlen auf geraden Linien durch das Objekt hindurch aus.Max Nelson et al. beschreibt in [16] verschiedene Modelle, die diese unterschiedlichenphysikalischen Effekte von Licht und Material berücksichtigen.

6


Abbildung 2.2: Image-Order Rendering Technik – Ray-Casting

Um die Modelle des Direkten Volume Rendering besser verstehen zu können, wirdzunächst angenommen, dass jeder Volumendatensatz aus Gasteilchen besteht. Wieauch Röttger in [21] beschreibt, besitzt jedes Gasteilchen die Eigenschaft, Licht zuemittieren. Einfallendes Licht wird wiederum von jedem Gasteilchen absorbiert odergestreut. Die vorher erwähnten Modelle ergeben sich unter Berücksichtigung derverschiedenen Effekte wie folgt:

Nur AbsorptionHierbei wird angenommen, dass das Volumen aus maximal absorbierendem Gasbesteht. Dabei wird einfallendes Licht komplett absorbiert. Emission und Streuungwerden vernachlässigt.

Nur EmissionBei diesem Modell emittiert das Gas des Volumens Licht. Dabei wird dieEigenschaft der Gasteilchen, Licht zu absorbieren oder zu streuen, vernachlässigt.

Emission und AbsorptionDies ist das am meisten verbreitete und auch in dieser Arbeit verwendete Modell.Hierbei wird einerseits angenommen, dass jedes Gasteilchen Licht emittiert undandererseits auch Licht absorbiert. Die Streuung von Licht wird vernachlässigtbeziehungsweise nur in Richtung des einfallenden Strahls berücksichtigt.

7


Streuung und SchattierungBei diesem Modell wird auch das Licht berücksichtigt, das zuvor an einemTeilchen im Volumen gestreut wird. Zudem wird berücksichtigt, dass sich diverseGasteilchen gegenseitig verdecken können.

Das Direkte Volume Rendering kann in Image-Order und Object-Order Technikenunterteilt werden. Diese zwei Techniken bestimmen das Ergebnisbild aufunterschiedliche Art. Bei Object-Order Techniken wird ausgehend von denVolumendaten ein Bild erzeugt. Es wird für jedes Voxel des Datensatzes ein Beitragzum Ergebnisbild berechnet. Eine solche Technik ist beispielsweise das Splatting.Dabei wird angenommen, dass jedes Voxel eine Art Farbkugel repräsentiert.Anschließend werden diese Kugeln aus der 3D-Szene in die Richtung des Betrachtersgeworfen und hinterlassen am Punkt des Aufpralls auf dem Bildschirm einenFarbpunkt. Wird dies für jedes Voxel des Datensatzes wiederholt erhält man eine2D-Projektion des 3D-Volumens.

Im Gegensatz zu den Object-Order Techniken gehen Image-Order Techniken vomresultierenden Bild aus. Zunächst handelt es sich bei diesem Bild um den leerenBildschirm beziehungsweise den Teil des Bildschirms, in dem das Volumen angezeigtwerden soll. Ausgehend von diesem noch leeren Bild, muss für jeden Bildpunktein Farbwert bestimmt werden. Das im nächsten Kapitel erläuterte Ray-Casting isteine solche Image-Order Technik und kommt in dieser Arbeit zur Visualisierungder Volumendaten zum Einsatz. Abbildung 2.2 zeigt das Prinzip dieser Technik.Dabei wird die Farbe der Bildpunkte berechnet indem für jeden Bildpunkt einegerade Linie (Sichtstrahlen) ausgehend von der Kamera durch das Volumen gezogenwird. Entlang dieser Linie werden anschließend die Voxelwerte miteinander zu einemFarbwert verrechnet.

8


2.3 Ray-Casting

Ray-Casting beschreibt eine Technik bei der Visualisierung von 3D-Volumendaten.Das endgültige Bild entsteht dabei durch Simulation von Photonen, die durch dasVolumen hindurch zum Auge des Betrachters fliegen. Dabei werden die Lichtteilchendurch Emission verstärkt oder durch Absorption abgeschwächt, wobei Ersteres einlinearer und Letzteres ein exponentieller Prozess ist.

Die Flugbahnen der Photonen werden als gerade Linien angenommen, derenUrsprung das Auge des Betrachters beziehungsweise die Kamera ist. Entlangdieser sogenannten Sichtstrahlen (engl. Viewing Rays) werden in bestimmtenAbständen Samples (Voxel Werte) aus dem Volumen gelesen und mit einemAbsorptions- beziehungsweise Emissionsparameter verrechnet. Die aufgenommenenSamples akkumulieren sich entlang des Sichtstrahls und entsprechen einem sichtbarenPixel auf dem Bildschirm (Fragment). Die Ergebniswerte entlang eines Sichtstrahlswerden anschließend gespeichert. Dieser Speicher beinhaltet das Ergebnisbild, dasfür die Darstellung des Volumens auf dem Bildschirm benötigt wird.

Abbildung 2.3: Sampling der Volumendaten durch Ray-Casting

Abbildung 2.3 zeigt, wie die Samples auf einem Sichtstrahl durch das Volumenaufgenommen werden. Die einzelnen Samples werden mithilfe des Modells der

9


Absorption und Emission (siehe auch Kapitel 2.2, [16]) miteinander verrechnet. Hegeet al. approximieren in [11] das Modell von Absorption und Emission entlang einesLichtstrahls durch ein gasförmiges Volumen durch folgende numerische Annäherung(Volume Rendering Integral):

I(sk) = I(sk−1)e−τ(sk−1,sk) +

sk∫sk−1

q(s)e−τ(s,sk)ds (2.1)

I(sk) ist die Intensität des im Auge des Betrachters ankommenden Lichts. DieVariable sk beschreibt den Punkt auf dem Sichtstrahl, an dem die Intensität durchdie Gleichung bestimmt wird. Der Term:

θk = e−τ(sk−1,sk) (2.2)

wird als Transparenz des Materials bezeichnet. Oft wird dieser Wert als Opazitätαk = 1− θk beschrieben. Der Term:

bk =

sk∫sk−1

q(s)e−τ(s,sk)ds. (2.3)

beschreibt die Zunahme der Intensität durch den Effekt der Emission entlang desLichtstrahls.

Ersetzt man die Terme in Gleichung 2.1 durch die aus 2.2 und 2.3 erhält man folgendevereinfachte Gleichung:

I(sk) = I(sk−1)θk + bk (2.4)

Diese Gleichung ist für das sogenannte Compositing wichtig, das in Kapitel 5.3 abSeite 53 näher erklärt wird. Dabei wird der Farbwert und die Transparenz für jedenBildpunkt auf dem Bildschirm berechnet. Um diese Werte zu erhalten werden dieVoxelwerte entlang das Sichtstrahls nach Gleichung 2.4 miteinander verrechnet. Alsergänzende Literatur zu diesem Thema empfiehlt sich [9], [20] und [8].

10

Kapitel 3Grundlagen Web

3 GrundlagenWeb

In diesem Kapitel werden Grundlagen zum Thema Web erörtert. Zunächst wirdein Einblick in die neueste Version der Hypertext Markup Language (HTML) 5.0gegeben. Einen allgemeinen Überblick über die neuesten Web-Technologien liefertAbbildung 3.1. Darin sind die in dieser Arbeit verwendeten Technologien mit einemStern kenntlich gemacht. Des Weiteren werden die wichtigsten in dieser Arbeitverwendeten Javascript Bibliotheken kurz vorgestellt. Außerdem wird in diesemAbschnitt erklärt, wie über die programmierbare Schnittstelle WebGL aus demBrowser heraus auf die Grafikhardware zugegriffen werden kann.

3.1 Entwicklungsumgebung

Als Entwicklungsumgebung für die Web-Applikation des Volumen Renderers wirddie Laufzeitumgebung NodeJS [13] verwendet. Die NodeJS Umgebung stellt einenrudimentären Webserver zur Entwicklung von Webanwendungen zur Verfügung.Darüber hinaus beinhaltet NodeJS einen eigenen Paketmanager, den sogenanntenNode Package Manager (NPM). Mit dem NPM lassen sich sehr komfortabelergänzende Softwaremodule per Kommandozeile oder per Konfigurationsdateiinstallieren. Vergleichbar ist dieser Paketmanager mit den unter Linux verwendetenSoftwareverwaltungstools. Zwei erwähnenswerte Softwarepakete sind hierbei dasModul Webpack und das Modul Gulp.

WebPack Mit Webpack ist es möglich die Applikation zu modularisieren undobjektorientierte Programmieransätze zu realisieren. Webpack bietet eine ArtCompiler für Javascript Applikationen in Form eines Entwicklungsservers an. Nachdem Starten des Servers werden die modular angelegten Javascript Dateien in eine

11


Abbildung 3.1: Überblick der neueren Web-Technologien [22]. Die mit einem Sternversehenen Technologien wurden u.a. in dieser Arbeit verwendet.

einzige Datei zusammengeführt und im Arbeitsspeicher abgelegt. Anschließend kannüber den Browser direkt darauf zugegriffen werden. Während der Zusammenführungder Javascript Dateien können weitere Operationen auf den Quellcode angewendetwerden. Ein Beispiel für eine solche Operation ist das sogenannte „Uglify“. Dabeiwird der Quellcode gewissermaßen verunstaltet, indem die Formatierung des Codesverworfen wird. Das hat den Vorteil, dass der Code von Dritten nicht mühelosgelesen werden kann und die gesamte Applikation weniger Speicher benötigt.Eine weitere hilfreiche Funktion des Entwicklungsservers ist die Registrierung vonÄnderungen an den Quelldateien. Wird eine Quelldatei mit neuem Inhalt gespeichertwird das Kompilieren der kompletten Applikation automatisch angestoßen. Somitsind während der Entwicklung Manipulationen am Quellcode unmittelbar nachdem Abspeichern der Datei sichtbar. Konfiguriert wird Webpack über eineKonfigurationsdatei.

12


Gulp Durch das Modul Gulp können häufig auftretende Abläufe in sogenanntenTasks zusammengefasst und automatisiert werden. Diese Tasks können beispielsweiseverwendet werden, um den Entwicklungsserver bequem von der Konsole aus zustarten. Die Schachtelung von mehreren Tasks in eine andere Task machen diesesModul zu einem beliebig komplexen Werkzeug.

3.2 HTML

Grundsätzlich handelt es sich bei HTML um eine beschreibende oder auszeichnendeSprache (markup engl. Auszeichnung). Durch Markierungen, sogenannten Tags, wirdbeschrieben, wie ein Text auf dem Bildschirm dargestellt werden soll. In den meistenFällen wird ein zu beschreibender Text mit einem Anfangs- und einem Endetagversehen. Somit lassen sich die Inhalte strukturieren und der Browser stellt diesedementsprechend dar. Möchte man beispielsweise, dass ein Text als Überschriftdargestellt wird, kann das Tag <h1> benutzt werden. Das Ende einer Auszeichnungwird mit einem Backslash vor dem Tag </h1> markiert. Durch Schachtelung solcherAuszeichnungen können beliebig komplexe Webseiten beschrieben werden.

HTML bietet in der Version 5.0 einige Neuerungen wie Abbildung 3.1 zeigt. Einegenaue Spezifikation der fünften Version von HTML kann auf der Webseite des WorldWide Web Consortiums (W3C) [24] nachgeschlagen werden.

Eine der größten Erweiterungen in HTML5 ist das Canvas Element. Dieses direktin HTML eingebundene Element beschreibt eine Zeichenebene, auf der Bilder, 3D-Grafiken, Zeichnungen oder Videos dargestellt werden können. Das Canvas Elementist für diese Masterarbeit besonders wichtig, da es die Schnittstelle vom Browser zurGrafikhardware bereitstellt. Diese programmierbare Schnittstelle zwischen Javascriptund der Grafikhardware wird als WebGL bezeichnet. Weiterführende Erklärungenzu WebGL sind in Kapitel 3.4 zu finden.

13


3.3 Javascript

Javascript ist eine Scriptsprache und wird verwendet, um den meist sehr statischwirkenden HTML-basierten Webseiten Dynamik zu verleihen. Ein gutes Beispielfür die Funktionsweise von Javascript ist die onClick Funktion und wird durch dasCodebeispiel 3.1 veranschaulicht.

Codebeispiel 3.1: Funktionsweise Javascript

1 <button type="button" id="button">Click Me </button>2 <p id="demo"></p>3 <script type="text/javascript">4 document.getElementById("button").onclick = function () {

document.getElementById("demo").innerHTML = "Hello World!"};5 </script>6 </body>

Bei der Betätigung des Buttons wird ein onClick Event ausgelöst. In diesem Beispielwird dadurch der Inhalt des HTML Elements <p id="demo"> durch den String„Hello World!“ ersetzt.

Ergänzend zu Javascript wird in dieser Arbeit die sehr umfangreiche JavascriptBibliothek jQuery [14] verwendet. Diese Bibliothek erleichtert beispielsweise dieManipulation des sogenannten Document Object Models (DOM). Das DOM ist einModell, das den Inhalt einer Webseite durch eine hierarchische Struktur abbildet.Eine solche Manipulation beschreibt das zuvor gezeigte Codebeispiel 3.1. Durch denEinsatz von jQuery kann die JavaScript Anweisung in Zeile 4 im obigen Beispieldurch den Befehl 3.2 ersetzt werden und macht die Handhabung solcher Befehleangenehmer für den Programmierer.

Codebeispiel 3.2: jQuery

1 $("#button").click(function (){$("#demo").html("Hello World!")});

Das jQuery Objekt ist durch die Variable $ gekennzeichnet. Über dieses Objektkönnen die gesamten Funktionen von jQuery aufgerufen werden. Des Weiteren bietetjQuery die Möglichkeit auf die Events einer Webseite zu reagieren oder selbst Eventsauszulösen.

14


Weitere in dieser Arbeit verwendete Softwarepakete, die ebenfalls auf Javascriptbeziehungsweise jQuery aufbauen, sind jQuery UI, QUnit und gl-matrix. Erstereswird verwendet um Eingabeelemente wie zum Beispiel Schieberegler auf der Webseitedarzustellen und zu parametrisieren. QUnit ist eine Testumgebung für JavascriptApplikationen mit der automatisierte Tests geschrieben werden können. Bei derBibliothek gl-matrix handelt es sich um eine Sammlung nützlicher Funktionen, diefür Matrix Operationen benötigt werden. Solche Operationen werden beispielsweiseverwendet, um Objekte in einer Szene zu bewegen oder zu rotieren.

3.4 WebGL

Die sogenannte Web Graphics Library (WebGL) ist eine plattformübergreifendeProgrammierschnittstelle (engl. Application Programming Interface, API) fürJavascript, die seit der Einführung von HTML5 in den meisten aktuellen Browsernverfügbar ist. HTML5 bezeichnet, wie in Kapitel 3.2 beschrieben, den neuestenStandard der Web Technologie und führt als größte Neuerung das sogenannteCanvas Element ein. Dieses Element dient im Browser als Leinwand, auf die mithilfevon Javascript Befehlen gezeichnet werden kann. Über die WebGL Schnittstellekann dabei auf die Grafikkarte der darunterliegenden Plattform zugegriffen werden.Besonders aufwändige 3D Anwendungen, wie zum Beispiel die Darstellung vonVolumendaten, profitieren durch diese Hardwarebeschleunigung.

Die aktuellste und in dieser Arbeit verwendete Grafikbibliothek WebGL 1.0 basiertauf OpenGL ES 2.0. Die Erweiterung ES steht für Embedded Systems unddefiniert eine OpenGL Version mit verkleinertem Funktionsumfang, die es vorallem leistungsschwächeren Geräten wie Mobilfunkgeräten oder Tablets ermöglicht,komplexere Grafikanwendungen darzustellen. Für die Shaderprogrammierung wirddie Shaderprogrammiersprache GLSL ES verwendet. WebGL wurde von dersogenannten Khronos Group [2] spezifiziert und wird von diesem Konsortiumstetig weiterentwickelt. Die Organisatoren dieses Konsortiums sind unter anderemnamhafte Firmen wie AMD, Apple, Intel, Nvidia und ARM.

15


3.4.1 Texturen

In der Computergrafik und in WebGL werden Texturen verwendet um Objekteneiner Grafikszene ein bestimmtes Aussehen zu verleihen. Texturen sind 2D-Bilder wie beispielsweise Aufnahmen einer Digitalkamera. Diese Bilder könnengewissermaßen auf das Drahtgitternetz eines durch Vertices beschriebenen Objektsaufgeklebt werden. Abbildung 3.2 zeigt ein sogenanntes Mapping einer 2D-Textur.Die Bildpunkte der 2D-Rastergrafiken werden Texel (Textur Pixel) genannt. In derComputergrafik gibt es 1D, 2D und 3D Texturen. Davon werden in dieser Arbeitausschließlich 2D-Texturen verwendet, da WebGL die Verwendung von 3D-Texturenin der aktuellen Version noch nicht unterstützt.

Abbildung 3.2: Eine Textur (links) wird über die Texturkoordinaten auf dieOberfläche des 3D-Objekts (rechts) gemapped.

Da es sich bei Volumendaten allerdings um 3D-Datensätze handelt, wäre es fürdie Darstellung wünschenswert, 3D-Texturen verwenden zu können. Zu diesemZweck wird ein offizieller Workaround [6] verwendet, der von der Khronos Groupveröffentlicht wurde, um im Fragmentshader (siehe Kapitel 3.4.2) eine 3D-Textur zusimulieren. Die Generierung der 2D-Texturen wird imKapitel 4.2.2 näher erläutert.

16


3.4.2 Shader

Als Shader werden kleine programmierbare Programme der Rendering Pipelinebezeichnet. Bei der Version 1.0 von WebGL handelt es sich um den Vertexshaderund den Fragmentshader. Bei anderen Grafikbibliotheken können oft auchzusätzlich Geometryshader oder Tesselationseinheiten programmiert werden. Aufeine Erklärung der Letzteren wird in dieser Arbeit jedoch verzichtet, da diese in derRendering Pipeline der aktuellen Version von WebGL nicht existieren.

Vertexshader Im Vertexshader werden, wie auch im folgenden Kapitel erörtertwird, vertex-basierte Operationen definiert. An welcher Stelle die Shader in derPipeline vorzufinden sind zeigt Abbildung 3.4. In dieser Abbildung ist außerdemersichtlich, welche Ein- und Ausgänge ein Prozess der Rendering Pipeline besitzt.Dem Vertexshader werden Attribute und Uniforms durch die Javascript Applikationbereitgestellt. Attribute sind Werte, die vertex-bezogene Informationen beinhaltenwie beispielsweise:

• Positionen der Vertices im dreidimensionalen Raum

• Farbinformationen für die einzelnen Vertices

• Texturkoordinaten

Uniforms sind beispielsweise Matrizen für Model-View-Projection Transformationenoder andere konstante Parameter.

Die Ausgänge des Vertexshaders sind sogenannte Varying Variablen und spezielleVariablen, die nicht vomBenutzer angelegt werden, sondern in der Rendering Pipelineunveränderbar definiert sind. Varying Variablen werden, wie in Abbildung 3.4 gezeigt,während der Rasterisierung interpoliert und an den Fragmentshader weitergegeben.Ein gutes Beispiel für eine solche Variable ist die Texturkoordinate. Im Vertexshadersind diese Koordinaten nur für die Eckpunkte einer Textur bekannt. Durch dieRasterisierung werden für jedes Fragment solche Texturkoordinaten bestimmt undstehen im Fragmentshader zur Verfügung.

Ein Beispiel für eine spezielle Variable ist gl_Position. Dieser Wert muss während desProgrammablaufs im Vertexshader gesetzt werden, damit das Programm erfolgreich

17


durchlaufen wird. Der Wert enthält die transformierte Position jedes Vertices. Ausdiesen Daten werden für jedes Fragment, das auf dem Bildschirm angezeigt wird,fragment-bezogene Positionskoordinaten berechnet.

Fragmentshader Der Fragmentshader ist für die Berechnung der Farben dereinzelnen Fragmente verantwortlich. Die Farbe eines Fragments wird durch einenRGBA Wert beschrieben. In diesem Shader ist der Ray-Casting Algorithmusimplementiert, der in Kapitel 2.3 erörtert wurde. Eingehende Daten sind abgesehenvon Varying Variablen, die zuvor im Vertexshader definiert wurden, und normalenUniforms auch spezielle Uniforms, sogenannte Sampler. Diese Variablen ermöglichenZugriffe auf Texturen. In der Computergrafik werden diese Zugriffe auch alsTexture Lookups bezeichnet. Über solche Texture Lookups ist es möglich ausTexturen Farbwerte auszulesen, um sie anschließend im Fragmentshader verwendenzu können.

Die spezielle Variable gl_FragColor wird im Fragmentshader für jedes Fragmentausgegeben. Darin befinden sich die im Shader errechneten Farbinformationen derBildpunkte für die spätere Darstellung der Szene.

3.4.3 WebGL Rendering Pipeline

Dieses Kapitel beschreibt, was sich hinter der Rendering Pipeline von WebGLverbirgt. Allgemein handelt es sich bei einer Pipeline um eine Reihe sequenziellablaufender Arbeitsschritte, die während des Rendering Prozesses nacheinanderdurchlaufen werden. Für die Darstellung einer 3D-Szene werden diese Arbeitsschrittemehrfach parallel auf der Grafikkarte ausgeführt. Bei Rendering Pipelines wirdzwischen Fixed Function Pipelines (FFP) und Programmable Rendering Pipelines(PRP) unterschieden. Bei der veralteten Pipeline, der FFP, können nur Parametervon fest vorgegebenen Funktionen der Rendering Pipeline verändert werden.Bei einer PRP können Shader (siehe Kapitel 3.4.2) vom Programmierer selbstprogrammiert werden. Für die Programmierung der Shader werden eigeneShaderprogrammiersprachen verwendet. Bei OpenGL beziehungsweise WebGL wirddiese Sprache als OpenGL Shading Language (GLSL) bezeichnet.

18


WebGL besitzt eine programmierbare Rendering Pipeline. Das bedeutet, dass beidieser Pipeline ein Vertexshader und ein Fragmentshader definiert werden muss.Im Folgenden werden diese Shader sowie die weiteren Prozesse, die nötig sind umGrafiken mithilfe der WebGL Grafikbibliothek auf dem Bildschirm darzustellen,näher beschrieben. Abbildung 3.3 zeigt den groben Ablauf der Rendering Pipelinevon WebGL. In dieser Grafik wird sichtbar, dass sich die Pipeline in zweiTeile unterteilt, die im Fragmentshader zusammengeführt werden. Was genau inden einzelnen Prozessen während des Renderings passiert wird in den folgendenAbschnitten näher erläutert und kann in [17] nachgelesen werden. Abbildung 3.4erweitert die in Abbildung 3.3 gezeigte Rendering Pipeline um Details der einzelnenProzessschritte.

Abbildung 3.3: Rendering Pipeline von WebGL ohne Details

Vertex Operationen Vertices (Singular Vertex) sind Punkte im dreidimensionalenRaum, die durch eine x-, y- und z-Koordinate beschrieben werden. Mehrere solcherVertices, die durch Linien miteinander verbunden werden, ergeben sogenanntePolygone. In der Computergrafik werden darzustellende Objekte häufig in Formsolcher Polygone definiert. Über sogenannte Vertex Operationen werden dieseObjekte im Raum platziert. Durch die Projektionstransformation werden die Verticesvom 3D in den 2D Raum transformiert, um die Szene auf dem Bildschirm ausgebenzu können. Koordinaten von Texturen werden durch die Vertex Operationenfestgelegt und ebenfalls transformiert. In diesem Renderingschritt werden auchhäufig Berechnungen von Normalenvektoren durchgeführt, um diese Daten späterfür eine realistischere Darstellung der Szene durch Beleuchtung oder Schattierungnutzen zu können.

19


Abbildung 3.4: Diese Abbildung zeigt die Rendering Pipeline mit Ein- undAusgängen der einzelnen Prozesse.

20


Pixel Operationen Bei Pixel Operationen handelt es sich um Funktionen, die fürdie Modifikation von Texturen verantwortlich sind. Wie in Kapitel 3.4.1 erwähnt,unterstützt WebGL nur 1D und 2D Texturen. Falls die Texturen komprimiertvorliegen, müssen diese zunächst entpackt werden, um sie im weiteren Verlaufdes Rendering Prozesses verwenden zu können. Wie in Kapitel 3.4.1 ebenfallsangesprochen, werden Texturen benutzt um Objekten in der 3D-Szene ein definiertesAussehen zu verleihen. Befindet sich die Kamera weit weg von der Textur, bedecktein Pixel des Bildschirms mehrere Texel der Textur. Wird die Kamera hingegensehr nahe an das Objekt herangeschoben, bedecken mehrere Pixel des Bildschirmsdenselben Texel der Textur. Für diese Fälle werden spezielle Texturfilter verwendet,um die Qualität der Darstellung zu verbessern. Diese Filter sind häufig verwendetePixel Operationen der Rendering Pipeline.

Clipping und Culling In diesem Prozess der Rendering Pipeline stehen diePositionen der einzelnen Vertices der 3D Szene fest. Nun wird überprüft, ob sichdiese Vertices im Blickfeld, dem sogenannten Viewport, der Szene befinden. Objektederen Vertices außerhalb des festgelegten Viewports liegen, werden abgeschnittenoder komplett verworfen. Durch sogenannte Clipping Ebenen ist es möglich, denViewport zusätzlich einzugrenzen. Des Weiteren besitzt jede Oberfläche Vorder-und Rückseite. Durch einen bestimmten Parameter kann eingestellt werden, ob vonden darzustellenden Objekten Vorder- beziehungsweise Rückseite oder beide Seitengleichzeitig dargestellt werden sollen.

Durch diesen Prozess wird folglich die Anzahl an Vertices verringert die in der3D-Szene dargestellt werden müssen. Es werden nur Teile der Szene gerendert, diefür den Benutzer tatsächlich sichtbar sind. Dieser Abschnitt der Pipeline kann dieLeistung der Applikation stark verbessern.

Primitiven Assemblierung und Rasterisierung In diesem Abschnitt stehen allesichtbaren Vertices einer Szene fest. Diese Vertices geben die Positionen der Objektein der Szene an. Bei der Beschreibung der Objekte wird zudem festgelegt wiedie einzelnen Vertices miteinander verbunden werden. Die daraus resultierendenPolygone werden während der Primitiven Assemblierung in kleinere Objekte,sogenannte Primitive, zerlegt. Komplexe Objekte bestehen aus einer Vielzahl solcher

21


Abbildung 3.5: Die in WebGL verfügbaren Grafik Primitive

Primitive. WebGL benutzt für diese Zerlegung die in Abbildung 3.5 abgebildetenGrundobjekte. Im Gegensatz zu OpenGL unterstützt WebGL keine Primitiven fürQuadrate (QUAD, QUAD_STRIP). Für eine fehlerfreie Zerlegung der Polygone inPrimitive ist die Reihenfolge wichtig, in der die Vertices der Pipeline übergebenwerden. Dabei sollten alle Vertices einheitlich im oder gegen den Uhrzeigersinnangegeben werden.

Nach der Festlegung der Primitiven werden die Pixel berechnet, die ein Primitivauf dem Bildschirm bedeckt. Ein Pixel des Bildschirms wird im Folgendenals Rasterpunkt beziehungsweise als Fragment bezeichnet. Für jedes Fragmentwird die Position innerhalb des Polygons ermittelt und an den nächstenArbeitsschritt der Rendering Pipeline weitergeleitet. Die Positionen werden durchInterpolation zwischen den Eckpunkten der Primitiven berechnet. Es könnenzudem weitere Texturkoordinaten, Normalenvektoren oder andere vertexbezogeneDaten angegeben werden, die während des Rasterisierens ebenfalls durch lineareInterpolation in fragment-bezogene Werte umgerechnet werden (Varying Variablenvgl. Abbildung 3.4). Diese Daten stehen anschließend im nächsten Prozess derRendering Pipeline, dem Fragment Shader, zur Verfügung.

22


Fragment Operationen Diesem Arbeitsschritt stehen alle im Rasterisierungspro-zess berechneten fragment-bezogenen Daten zur Verfügung. Für jedes Fragmentexistiert zudem ein Farbwert, der durch Interpolation zwischen den Vertices im Ras-terisierungsprozess ermittelt wurde. Mithilfe der Fragment Operationen können dieFarbwerte für jedes Fragment modifiziert oder ausgetauscht werden. Dieser Prozesswird in der Computergrafik, wie in Kapitel 2.3 erwähnt, auch Compositing (sieheKapitel 5.3) genannt. Über die Texturkoordinaten, die ebenfalls durch die Rasteri-sierung für jedes Fragment berechnet wurden, kann der Farbwert an dieser Stelleaus einer Textur gelesen werden. Das Lesen eines Farbwertes aus einer Textur wirdals Textur Lookup bezeichnet. Der Farbwert aus dem Lookup kann anschließendmit dem aktuellen Wert des Fragments verrechnet werden. An dieser Stelle werdenauch Werte für Transparenz und Beleuchtung mit der Farbe des Fragments verrech-net. Durch Fragment Operationen können zudem aufwändige Nebelberechnungendurchgeführt werden.

Framebuffer Operationen Bei den Framebuffer Operationen handelt es sich ummehrere Tests, die vor der Ausgabe des Bildes auf dem Bildschirm hintereinanderausgeführt werden. Diese Tests werden in folgender Reihenfolge durchlaufen:

SichtbarkeitstestHierbei wird der sichtbare Bildschirmausschnitt festgelegt. Dabei wird geprüft,was nach dem Rendering Prozess auf dem Bildschirm ausgegeben wird.

Scissor TestFür diesen Test wird ein rechteckiger Bereich definiert und überprüft, ob sich diedarzustellenden Fragmente in diesem Rechteck befinden. Fragmente außerhalb desBereiches werden nicht gerendert und werden nicht in den Framebuffer geschrieben.

Anti-AliasingBei der Darstellung von kontinuierlichen Bilddaten auf dem Pixelraster desBildschirms kommt es unweigerlich zu störenden Aliasing Effekten. Durch Anti-Aliasing wird dieser Effekt, der besonders an Objektkanten auftritt, verringert.

Alpha TestIn diesem Schritt werden Fragmente verworfen, deren Alpha Wert einenvorgegebenen Schwellwert unter- beziehungsweise überschreiten.

23


Stencil TestBei diesem Test werden Fragmente ausgesondert, die nicht in vorgegebeneBildschirmausschnitte (Masken) passen. Das Verhalten dieser Operationen kanndurch sogenannte Stencilfunktionen bzw. Stenciloperationen festgelegt werden.

Depth Buffer TestDurch diesen Test werden Fragmente verworfen, die von einem näher amBetrachterliegenden Objekt verdeckt werden und somit für den Betrachter nicht sichtbarwären.

BlendingDurch das Blending werden Farbwerte von neu berechneten Fragmenten (Source)mit den Farbwerten der bereits im Framebuffer vorhandenen Fragmente (Destina-tion) gemischt. Hierfür gibt es eine Vielzahl an Konfigurationsmöglichkeiten, umfestzulegen, wie die Vermischung der Farbwerte geschehen soll.

DitheringHierbei kann die Farbauflösung der Fragmente auf Kosten der räumlichenAuflösung verbessert werden.

Framebuffer Im Framebuffer wird für jedes Fragment die nötige Informationgespeichert um die Szene auf dem Bildschirm ausgeben zu können. Der Framebuffersetzt sich dabei aus mehreren Buffern zusammen. Der Colorbuffer beinhaltet dieFarbinfomation jedes Fragments sowie den zugehörigen Alpha Wert. Im DepthBuffer (oder Z-Buffer) wird die Tiefeninformation der Fragmente abgespeichert.In einem weiteren Buffer, dem Stencil Buffer, wird ein weiterer Wert für jedesFragment gespeichert. Dieser Wert beschreibt die Zugehörigkeit des Fragments zueinem bestimmten Bildschirmausschnitt (Stencil).

24

Kapitel 4Konzeption

4 Konzeption

In diesem Kapitel wird das Gesamtkonzept der Arbeit erläutert. DiesesGesamtkonzept besteht aus zwei Teilentwicklungen. Die erste Teilentwicklung istdie Vorverarbeitung der Volumendaten. Die Volumendaten liegen unkomprimiert,wie in Kapitel 2 erläutert, als Voxeldatensätze vor. Um solche meist sehr großenDatensätze in einem Browser verfügbar zu machen, müssen diese Daten zunächstdurch geeignete Vorverarbeitung skaliert und komprimiert werden.

Die zweite Teilentwicklung dieser Arbeit ist für die Darstellung der vorbereitetenVolumendaten zuständig. Hierbei handelt es sich um eine Javascript Applikation, diefür die Darstellung der Volumendaten verantwortlich ist. Die Schwerpunkte liegenin diesem Teil der Arbeit auf der hierarchischen Datenhaltung der vorliegendenVolumendaten sowie der Programmierung der Shader und der objektorientiertenSoftwareentwicklung in Javascript. Im Folgenden werden für beide ProgrammeFunktionsweise und Aufbau erläutert.

4.1 Octree

Um die Vorverarbeitung der Volumendaten nachvollziehen zu können, wird in diesemKapitel zunächst das Modell der hierarchischen Datenhaltung erklärt. Hierfür wirddie Struktur des Octrees verwendet. Abbildung 4.2 zeigt den Aufbau dieses Modells.Diese Struktur eignet sich besonders für die Strukturierung von dreidimensionalenDaten. Dabei werden die Originaldatensätze (vgl. 2.1 auf Seite 5) in mehrere kleinereDatensätze zerlegt und in verschiedenen Auflösungen in der Datenstruktur abgelegt.Eine in Javascript realisierte Visualisierung eines Octrees ist auf der Website [4]gezeigt.

25

Kapitel 4Konzeption

Octrees besitzen wie jede andere Baumstruktur eine Wurzel (engl. Root). Die Wurzelbeinhaltet eine Abbildung des gesamten Volumendatensatzes. In diesem Elementwird der am niedrigsten aufgelöste Datensatz gespeichert. Von jedem Element (engl.Node) eines Octrees können acht weitere Elemente abstammen. Die Beziehungzwischen den Elementen des Octrees wird durch Abbildung 4.1 erklärt. Die achtKinderelemente eines Elements beinhalten höher aufgelöste Texturen desselbenVolumenabschnitts.

Abbildung 4.1: Elemente in einem Octree besitzen bis zu acht Kinderelemente(Children). Jedes Element (außer das Wurzelelement) besitzt einElternelement (Parent).

Außer der Wurzel des Baumes repräsentieren alle Elemente Teilvolumina einerAbbildung des ganzen Volumens einer bestimmten Auflösung. Die äußersten Ästedes Baumes werden als Blätter (engl. Leafs) bezeichnet. Der Octree ist von derWurzelbis zu den Blättern in Ebenen, sogenannte Levels, unterteilt (siehe Abbildung 4.2).Jedes Level beinhaltet zusammengenommen einen gesamten Volumendatensatz in

26

Kapitel 4Konzeption

einer bestimmten Auflösung. Dabei wächst die Anzahl der im Octree vorhandenenElemente mit jedem Level um 8Level an. Den niedrigsten Detailgrad besitzendie Volumendaten in der Wurzel des Baumes. Die am höchsten aufgelöstenbeziehungsweise unveränderten, originalen Volumendaten werden in den Blätterndes Octrees gespeichert.

Abbildung 4.2 zeigt, wie die unterteilten Volumen jeweils in einem Octree Elementabgelegt werden. Wie die Zerlegung des Volumens im Detail funktioniert wird inKapitel 4.2 beschrieben.

Abbildung 4.2: Jeder Volumenwürfel wird in absteigender Reihenfolge pro Octree-Level in x-, y- und z-Richtung halbiert (links). Die resultierenden18-Würfel werden im Octree gespeichert (rechts).

Die Nummerierung der Ebenen des Octrees beginnt mit Ebene 0. In dieser Ebenesind die Originaldaten des Volumens abgelegt. Jede weitere Ebene speichert eindurch trilineare Interpolation verkleinertes Volumen.

27

Kapitel 4Konzeption

4.2 Vorverarbeitung

In diesem Abschnitt wird die Vorverarbeitung der Volumendaten erläutert. Das Zieldabei ist es, die Datensätze für die Visualisierung vorzubereiten. Dazu gehört das imvorherigen Kapitel angesprochene Zerlegen der Volumendaten in Teilvolumina, dasSkalieren der Daten durch trilineare Interpolation und die Speicherung der Datenin einem geeigneten Dateiformat. Abbildung 4.3 zeigt das grobe Konzept dieserVorverarbeitung.

Abbildung 4.3: Grobes Konzept der Vorverarbeitung

Das grobe Konzept zeigt, dass die Volumendaten zunächst in 2D-Texturenumgewandelt werden müssen, damit sie später im Rendering Prozess von WebGLverwendet werden können. Nachdem das originale Volumen in Teilvolumina unterteiltund die Daten in 2D-Texturen abgespeichert wurden, wird der Volumendatensatzskaliert. Bei der Zerlegung eines Volumendatensatzes wird außerdem eine Datei mitMetadaten angelegt, die wichtige Parameter für die spätere Darstellung bereitstellt.Zu diesen Parametern gehören:

• Maximaler/Minimaler Grauwert pro Teilvolumen

• Maximaler/Minimaler Grauwert des gesamten Volumens

• Konstante Größe der Teilvolumina (Brickgröße)

• Höhe, Breite und Tiefe des gesamten Volumens

• x-, y- und z-Ausdehnung der Voxel

• Maximales Level der Zerlegung

28

Kapitel 4Konzeption

Um eine Vorstellung von Speichergrößen verschiedener Volumendatensätze zubekommen, sind in der folgenden Tabelle einige Beispiele aufgeführt:

Name Breite Höhe Tiefe Quantisierung SpeicherbedarfEngine 256 256 256 8 bit 16 MBPig 512 512 134 16 bit 268 MBMelanchton Uhr 960 960 960 32 bit 3375 MBContainer 2046 1451 1235 16 bit 6993 MBTurbinenschaufel 2016 2016 1854 16 bit 14372 MB

Tabelle 4.1: Speichergrößen verschiedener Volumendatensätze

Bei den in Tabelle 4.1 aufgeführten Volumenbeispielen ist ersichtlich, dass es bei derVerarbeitung größerer Volumendatensätze zu Speicherplatzproblemen kommen kann.Insbesondere wenn versucht wird, das komplette Volumen auf einmal zu verarbeitenund der gesamte Volumendatensatz in den Arbeitsspeicher geladen werden muss.

Um einem Speicherplatzproblem bei der Vorverarbeitung der Volumendaten zuentgehen, werden die Daten nie komplett in den Arbeitsspeicher geladen. Stattdessenwurde ein System entwickelt, das in der Lage ist, Volumendaten Voxel für Voxel zuverarbeiten. Zusätzlich wurde darauf geachtet, dass der Vorverarbeitungsprozess zumgrößten Teil parallelisiert werden kann, um die Vorverarbeitung zu beschleunigen.

Im Allgemeinen kann die Vorverarbeitung in eine Reihe sequenziell ablaufendeProzessschritte unterteilt werden. Zu Beginn dieser Prozesskette liefert ein Lesemodulimmer genau einen Voxelwert aus dem Volumendatensatz. Dieser Wert wirdanschließend durch die weiteren Prozesse der Vorverarbeitung geschleust. In dieserProzesskette werden grundsätzlich folgende Stationen durchlaufen:

SkalierungBei der Skalierung wird die Auflösung des Volumens in jede Raumrichtung halbiert.Durch trilineare Interpolation werden aus acht Voxeln im Originalvolumen einVoxel des skalierten Volumens.

BrickingWährend des Zerlegens des Volumendatensatzes in mehrere Teilvolumina,dem sogenannten Bricking, werden die gelesenen Voxel dem entsprechendenTeilvolumen zugeordnet.

29

Kapitel 4Konzeption

SpeicherungFür jedes Teilvolumen wird eine 2D-Textur erstellt. Eine solche Texturrepräsentiert die gesamte Bildinformation eines Teilvolumens. In diesem Prozesskönnen beispielsweise auch verschiedene Datenformate zur Speicherung der Datenfestgelegt werden.

In Abbildung 4.4 wird die Prozesskette der Vorverarbeitung dargestellt. Dabei istersichtlich, wie die einzelnen Prozesse parallel ablaufen. Jeder Durchlauf der Pipeline(von rechts nach links) repräsentiert einen gesamten Vorverarbeitungsprozessbei einer jeweils niedrigeren Auflösung (nach oben) der Volumendaten. DerDurchlauf 0 zerlegt das Originalvolumen in Teilvolumina ohne zuvor eineSkalierung vorzunehmen. Die drei Schritte der Vorverarbeitung (Bricking, Skalieren,Speicherung) werden im Folgenden etwas genauer beschrieben. Ein grobesKlassendiagramm der Vorverarbeitungssoftware ist im Anhang A.1 beigefügt.

Abbildung 4.4: Ablaufdiagramm der Vorverarbeitungspipeline

30

Kapitel 4Konzeption

4.2.1 Bricking

Die Zerlegung eines 3D-Volumens in mehrere kleinere Teilvolumina wird Bricking(engl. Brick = Klotz/Stein) genannt. Im diesem Kapitel wird das zugrunde liegendeKonzept des in dieser Arbeit verwendeten Bricking-Algorithmus erklärt.

Über eine Konstante wird die Seitenlänge eines quadratischen Würfels angegeben.Dieser Wert wird im weiteren Verlauf auch als Brickgröße bezeichnet. DieBrickgröße legt den Grad der Zerlegung der Volumendaten fest. Wird dieser Wertbeispielsweise auf 128 gesetzt, entspricht dies einem Würfel mit den Seitenlängen128 × 128 × 128Voxel. Ist das zu zerlegende Volumen ein quadratischer Datensatzder Größe 512× 512× 512Voxel, so wird er, wie in Abbildung 4.5 dargestellt, in 64Teilvolumina unterteilt.

Abbildung 4.5: Volumenunterteilung eines 1·5123 Volumen in 64·1283 Volumen

Wie in Kapitel 4.2 beschrieben, werden einzelne Voxel in die Pipeline derVorverarbeitung geschoben. Abbildung 4.6 veranschaulicht, wie den Teilvoluminadie zugehörigen Voxel zugeordnet werden.

Bei der Darstellung der Teilvolumina kann es an den Übergängen von einemTeilvolumen zum nächsten zu Bildfehlern kommen. Abbildung 4.7 a) zeigt dieseBildfehler bei einem Volumendatensatz eines Sparschweins. Diese Darstellungsfehlerentstehen durch fehlerhafte Interpolation der Voxel an den Übergängen derTeilvolumina. Abbildung 4.8 verdeutlicht die Entstehung dieser Bildfehler an denÜbergängen der Teilvolumina anhand von zwei eindimensionalen, binären Arrays.

31

Kapitel 4Konzeption

Abbildung 4.6: Die Voxel werden einzeln aus dem Originalvolumen gelesen (links)und anschließend dem richtigen Teilvolumen (Brick) zugeordnet(rechts).

Durch Kopieren der am Rand liegenden Pixel eines Teilvolumens in das benachbarteTeilvolumen kann eine fehlerhafte Interpolation korrigiert werden. Abbildung 4.7 b)zeigt das korrekt zusammengefügte Objekt.

4.2.2 Speicherung

Das Abspeichern der Volumendaten läuft generell nach einem sehr simplen Prinzipab. Für jedes Teilvolumen wird ein Buffer mit einer bestimmten Größe angelegt,in dem die Werte der Voxel des Volumens gespeichert werden. Wenn der Buffergefüllt ist, wird eine 2D-Textur, die alle Werte des Teilvolumens beinhaltet, auf dieFestplatte geschrieben.

Da ein Volumen in mehrere 2D-Texturen zerlegt wird, kommt es beim Speicherndarauf an, wie die einzelnen Texturen in einer Datei angeordnet werden, um sie spätermithilfe des Workarounds (siehe Kapitel 3.4.1) als 3D-Textur im Fragmentshaderbenutzen zu können. Abbildung 4.9 zeigt die Generierung der 2D-Texturen.

In dieser Abbildung ist ersichtlich, wie der Volumendatenblock in der z-Ebene inx-y-Ebenen zerteilt wird. Aus dem 8× 8× 8Voxel großen Volumen werden in diesemBeispiel acht 8 × 8Texel große 2D-Texturen. Die resultierenden zweidimensionalenSchichtbilder werden anschließend in einer Textur als Matrix in Zeilen und Spaltenangeordnet. In dieser Arbeit werden die Schichtbilder, angefangen bei z = 0,mit zunehmender z-Position untereinander in die Textur geschrieben. Wenn die

32

Kapitel 4Konzeption

(a) (b)

Abbildung 4.7: Darstellung eines Objektes a) mit Interpolationsfehlern und b) ohneInterpolationsfehler

Abbildung 4.8: Fehlerhafte Interpolation an den Übergängen der Teilvolumina

33

Kapitel 4Konzeption

Abbildung 4.9: 2D-Textur Generierung aus 3D-Volumendatensätzen

Maximalgröße der Textur erreicht ist, wird das nächste Schichtbild in eine neueSpalte geschoben. Die Maximalgröße ist durch eine konstante Variable im Programmeinstellbar.

Die endgültige Speicherung der Texturen und der in Kapitel 4.2 erwähntenMetainformationsdatei muss in einer bestimmten Struktur erfolgen, um die Datenspäter über die Javascript Applikation gezielt abrufen zu können. Demnach wirdfür jede Detailstufe des Volumens ein Dateiordner angelegt. Ein Ordner entsprichteinem Level im Modell des Octrees (siehe Kapitel 4.1). In diesen Dateiordnernbefinden sich die 2D-Texturen, die zum jeweiligen Level gehören. Dabei werdendie Texturen der Teilvolumina durch ihre Position im dreidimensionalen Raumgekennzeichnet. Ihre Position wird im Dateinamen der Textur vermerkt. DasMuster für die Generierung der Dateinamen lautet [x-Position]_[y-Position]_[z-Position]. Die Positionen der Teilvolumina ergeben sich durch die in Abbildung 4.10beschriebene Nummerierung.

34

Kapitel 4Konzeption

Abbildung 4.10: Nummerierung der Teilvolumina durch Position im dreidimensiona-len Raum. Bei der Speicherung der 2D-Texturen zu jedem dieserTeilvolumina wird der Dateiname direkt durch diese Nummerierunggeneriert.

4.2.3 Skalierung

In diesem Kapitel wird darauf eingegangen, wie die Skalierung von Volumendatenfunktioniert. Wie in Kapitel 4.2 erwähnt, wird das Volumen durch trilineareInterpolation skaliert. Durch die Interpolation wird die Auflösung in jedeRaumrichtung halbiert.

In einem Minimalbeispiel soll ein Volumen der Größe 8× 8× 8Voxel skaliert werden.Acht benachbarte Voxelwerte werden dabei zu einemWert im resultierenden Volumengemittelt. Das resultierende Volumen hat folglich die Größe 4 × 4 × 4Voxel. DieserProzess wird durch Abbildung 4.11 vereinfacht dargestellt. Der Mittelwert wird durchdie folgende Gleichung ermittelt:

Mittelwert = (8∑i=0

Vi) ·1

8

In der Formel steht das V für den Wert, der pro Voxel in den Volumendatengespeichert ist. Während ein Volumendatensatz skaliert wird, können dieresultierenden Voxeldaten sofort in den nächsten Durchlauf der Vorverarbeitung

35

Kapitel 4Konzeption

Abbildung 4.11: Skalieren eines 8× 8× 8Voxel Datensatzes

übergeben werden. Es ist nicht notwendig zu warten, bis ein Volumen komplettskaliert wurde.

4.3 VolumeRenderer

In diesem Abschnitt wird beschrieben, wie durch die aus demVorverarbeitungsschrittgenerierten 2D-Texturen ein 3D-Volumen auf dem Bildschirm dargestellt wird. Dabeiwurden verschiedene Anforderungen an die Software gestellt, die im Folgenden näherbeschrieben werden.

Bei der Visualisierung der Volumendaten soll vor allem darauf geachtet werden, dassdie Darstellung der 3D-Szene flüssig abläuft. Das bedeutet, dass die benötigte Zeitfür den Rendering Prozess möglichst kurz sein soll. In dieser Arbeit wird versucht,die 3D-Szene mit einer Bildwiederholrate von 20 Bildern pro Sekunde (engl. framesper second (FPS)) während einer Interaktion des Benutzers darzustellen.

Für eine möglichst kurze Wartezeit vom Aufruf der Applikation bis zur Anzeige desDatensatzes sollen zuerst Daten niedriger Auflösung geladen werden. Hierfür sollzu Beginn nur die Textur für das Wurzelelement des Octrees geladen werden. DieTexturen der niedrigeren Levels dürfen erst danach geladen und angezeigt werden.Zudem soll der Benutzer Einfluss auf die Darstellung nehmen können. Das bedeutet,dass die Teile des Volumens, die den Benutzer am meisten interessieren, mit einerhöheren Detailstufe geladen werden sollen als die anderen Bereiche des Volumens.

36

Kapitel 4Konzeption

In den folgenden Kapiteln wird erklärt, was für das oben definierte Verhalten derApplikation beachtet werden muss und wie diese Funktionen realisiert wurden. Eingrobes Klassendiagramm der Javascript Applikation befindet sich im Anhang A.2.

4.3.1 Repräsentation der Volumendaten

Die gesamten für die Darstellung notwendigen Daten werden in der JavascriptApplikation durch einen Octree repräsentiert (siehe Kapitel 4.1). Um Speicherplatz zusparen beziehungsweise den zur Verfügung stehenden Speicher optimal auszunutzen,sollen nur Daten in den Arbeitsspeicher geladen werden, die für eine Darstellungauf dem Bildschirm benötigt werden. Darüber hinaus sollen für eine beschleunigteDarstellung des Volumenobjektes zuerst die verkleinerten Volumendaten geladenund angezeigt werden.

Durch die Anzahl der Levels des Octrees, die in der Metainformationsdatei ausgelesenwerden kann, wird zunächst ein Gerüst eines Octrees mit der entsprechendenAnzahl an Ebenen erstellt. Bei diesem Gerüst handelt es sich um eine JavascriptImplementierung des Octree Modells. Dabei enthält jedes Element einen Platzhalterfür eine 2D-Textur, der je nach Bedarf der Anwendung durch die entsprechendeVolumentextur belegt werden kann. Das Entfernen einer Textur ist ebenfalls möglich,wodurch verwendeter Speicherplatz freigegeben werden kann, falls dies nötig ist. Wiemehrere Elemente aus unterschiedlichen Ebenen des Octrees zusammen gerendertwerden zeigt Abbildung 4.12. Die Abbildung zeigt auch, wie das Wurzelelement (rot)ausgeblendet wird, wenn die Volumina aus der nächsten Ebene (blau) dargestelltwerden. Dasselbe gilt für die nächsthöhere Ebene (grün).

Das dynamische Laden und Entladen der Volumentexturen wird durch Prioritäts-warteschlangen (engl. priority queues) gesteuert. Es wird jeweils eine Warteschlangefür die zu ladenden Texturen und eine Warteschlange für die zu entladenden Textu-ren verwendet. Innerhalb einer Warteschlange werden Referenzen auf die Elementedes Octrees angeordnet und ihrer Priorität entsprechend sortiert. Die Priorität wirddurch einen Zahlenwert definiert. Die Berechnung dieses Wertes für jedes Elementdes Octrees wird in Kapitel 4.3.4 näher beschrieben.

37

Kapitel 4Konzeption

Abbildung 4.12: Diese Abbildung zeigt wie die Ebenen des Octrees miteinandergerendert werden. Der rote Würfel ist das Wurzelelement mitder niedrigsten Auflösung. Je kleiner die Unterteilung wird, destohochauflösender ist die Darstellung.

Grundsätzlich werden Texturen solange in den Speicher des Browsers undanschließend in den Grafikspeicher nachgeladen, bis ein vorgegebenes Speicherlimiterreicht ist. Der Benutzer kann dieses Limit seiner Hardware entsprechend anpassen.Bei einer Erhöhung des Speicherlimits werden sofort weitere Texturen in denGrafikspeicher nachgeladen. Der momentane Speicherverbrauch der Applikationmuss durch die Maße der Texturen durch die einfache Gleichung:

Länge · Breite · Bits pro Pixel = Speicherbedarf in bit

berechnet werden, da in WebGL noch keine entsprechende Methode existiert, umden Speicherverbrauch der Applikation zu überwachen.

4.3.2 Interaktion

Bei der Realisierung der Visualisierungssoftware wurde darauf geachtet, dass flüssigesRotieren, Skalieren und Translieren der Szene möglich ist. Dies wird zum einen durchdie Darstellung der niedrig aufgelösten Volumendaten während einer Bewegungerreicht, zum anderen wird die Auflösung des Viewports während der Interaktionverringert. Dabei wird wie schon erwähnt eine Bildwiederholfrequenz von ∼20Bildern pro Sekunde angestrebt. Bei dieser Wiederholrate erscheint die Szene fürdas menschliche Auge flüssig.

38

Kapitel 4Konzeption

Beginn und Ende einer Bewegung werden durch Events im Browser gesteuert.Diese Events können durch Funktionen der Javascript Bibliothek jQuery modifiziertund angepasst werden (siehe Kapitel 3.3). Dabei werden Events für das Rotieren,Skalieren und Translieren wie folgt über die Maustasten ausgelöst:

Linke MaustasteBei gedrückter linker Maustaste kann der Benutzer das Objekt in der aktuellenLage in x- und y- Ebene verschieben. Dabei wird in Wirklichkeit die Position desBetrachters auf einer Ebene zum Objekt bewegt.

Rechte MaustasteBei gedrückter rechter Maustaste wird das Objekt gedreht. Genau genommen wirdbei der Drehung der Betrachter um das Objekt bewegt. Der visuelle Eindruck istdabei derselbe (siehe Abbildung 4.15).

MausradDurch die Drehung des Mausrades wird die Position der Kamera zum Objekt hinbeziehungsweise vom Objekt weg bewegt.

Bei Eintritt eines dieser Events wechselt die Anwendung in den sogenanntenFastMode. In diesem Modus werden zunächst alle Teilvolumina ausgeblendet. Es istnur das Wurzelelement des Octrees zu sehen. Zeitgleich wird, wie oben erwähnt, derViewport verkleinert. Das hat zur Folge, dass die Anzahl der in der Szene dargestelltenPixel reduziert wird. Dadurch finden während des Rendering Prozesses wenigerOperationen statt, wodurch die Bildwiederholfrequenz gesteigert wird. Die mit diesenMaßnahmen einhergehenden, für den Benutzer bemerkbaren Qualitätseinbußen derDarstellung sind dabei geringer zu werten als die Leistungssteigerung der gesamtenApplikation während einer Bewegung.

4.3.3 Zustandsautomat der Octree Elemente

Ein Zustandsautomat (engl. finite state machine) steuert das Verhalten der OctreeElemente. Der Automat beschreibt den Vorgang des Ladens und Entladens vonTexturen und regelt die Anzeige der einzelnen Octree Elemente mithilfe vonZuständen und Zustandsübergängen. Für die Erstellung dieses Automaten wirdeine Javascript Bibliothek [5] verwendet.

39

Kapitel 4Konzeption

Für die Definition des Zustandsautomaten müssen zunächst die Zustände festgelegtwerden, die ein Octree Element einnehmen kann. Die wichtigsten Zustände sollenanhand eines Beispiels näher erläutert werden. In diesem Beispiel wird ein Octreewie in Abbildung 4.1 betrachtet. Es gibt außer der Wurzel nur ein weiteres Level.Zu Beginn wird ein leeres Gerüst des Octrees in Javascript erstellt. Jedes Elementbesitzt dabei einen Zustandsautomaten, der die vorgegebenen Zustände wie folgtnach der Reihe einnimmt:

Zuerst befinden sich alle Elemente des Octrees im Zustand Empty. Dabei handeltes sich um das leere Gerüst der Octree Objekte und es wurde noch keine Textur fürdie jeweiligen Elemente geladen. Im weiteren Verlauf wechselt das Wurzelelementden Zustand auf Loading, da durch das Ereignis shouldLoad das Laden der Texturangestoßen wurde. Am Ende des Ladevorgangs wechselt das Element den Zustandüber den Zustandsübergang loaded auf Visible.

Nach dieser Reihe von Zustandsänderungen wird das Wurzelelement auf demBildschirm angezeigt. Steht der Applikation genügend Speicher zur Verfügung, wirdanschließend das Laden der Texturen für die Octree Elemente des nächsten Levelsangestoßen.

Im Gegensatz zum Wurzelelement wechseln die Elemente des nächsten Levels vomZustand Loading in den Zustand Invisible. Diese Elemente werden demnachnicht sofort auf dem Bildschirm sichtbar. Das hat den Grund, dass alle achtKinderelemente der Wurzel geladen sein müssen, um zur selben Zeit sichtbar werdenzu können. Um sicherzustellen, dass die Texturen für die acht Kinderelementegeladen sind, wird dem Wurzelelement gemeldet, wenn eines seiner Kinderelementegeladen wurde. Sind alle acht Kinder der Wurzel bereit, ändert das Wurzelelementdurch inferiorAvailable seinen Zustand auf Invisible. Gleichzeitig ändern dieKinderelemente durch den Übergang superiorInvisible ihren Zustand auf Visible.Die Zustände und Zustandsänderungen für dieses Beispiel sind in Abbildung 4.13 ineinem Sequenzdiagramm zusammengefasst. Gleichfarbige Zustandsübergänge findenzur selben Zeit statt. Nach diesen Zustandsänderungen wird das Wurzelelement nichtmehr auf dem Bildschirm dargestellt. Dafür sind dessen Kinderelemente sichtbar, diedasselbe Volumen jedoch in einer höheren Auflösung bereitstellen. Ein komplettesZustandsdiagramm des in dieser Arbeit entstandenen Zustandsautomaten befindetsich im Anhang A.3.

40

Kapitel 4Konzeption

Abbildung 4.13: Statemachine Sequenzdiagramm

4.3.4 Prioritäten

Für jedes Element des Octrees wird ein Zahlenwert ermittelt, der die Priorität desElements angibt. Dabei wird dem Wurzelelement immer der Wert 0 zugewiesen, dadieses Element stets zuerst geladen und nie entladen werden soll. Wie in Kapitel 4.3.1erwähnt, wird über diesen Wert das Laden und Entladen der Texturen gesteuert.

Nach jeder Bewegung des Objekts oder der Kamera findet eine Neuberechnung dieserWerte statt. Im Rahmen dieser Arbeit wurden zwei Algorithmen zur Berechnungder Prioritäten implementiert. Die Priorität ist ein Maß für die Wichtigkeit desjeweiligen Octree Elements für die Darstellung der gesamten Szene. Abbildung 4.14zeigt eine Gitternetzstruktur eines Octrees mit den Prioritätswerten der geladenenVolumina. Die 56 weiteren Teilvolumina des zweiten Levels haben eine niedrigerePriorität zugewiesen bekommen und wurden deshalb nicht geladen und angezeigt.Grundsätzlich gilt, dass Elemente mit einem hohen Prioritätswert eine niedrigePriorität besitzen. Kleinere Werte stehen folglich für eine höhere Priorität.

In Abbildung 4.14 fällt auf, dass es abgesehen vom Wurzelelement nur einenPrioritätswert für jeweils acht Octree Elemente gibt. Der Grund dafür ist, dass einVolumen nur ausgeblendet und durch höher aufgelöste Teilvolumina ersetzt werdenkann, wenn die Texturen der acht Kinderelemente in den Grafikspeicher geladenwurden. Damit dies mittels Prioritätswarteschlange für die acht Kinderelemente

41

Kapitel 4Konzeption

Abbildung 4.14: Diese Abbildung zeigt, wie die Gitternetzstruktur durch diePrioritäten beeinflusst wird. Acht Octree Elemente besitzen einengemeinsamen Prioritätswert (außer bei der Wurzel).

möglichst zur selben Zeit geschieht, wird ihnen derselbe Prioritätswert zugewiesen.

In den folgenden Abschnitten werden zwei Vorgehensweisen zur Berechnung derPrioritätswerte näher beschrieben.

Distanz zu Look-At Punkt Der Look-At Punkt beschreibt in der Computergrafikden Fixpunkt auf den das Auge des Betrachters gerichtet ist. Bei der Rotation umdie 3D-Szene wird dieser Punkt auch als Bezugspunkt verwendet. Die Kamera wirddabei in einem festen Radius um diesen Punkt gedreht. Abbildung 4.15 zeigt dasPrinzip dieser Drehung.

Der Algorithmus zur Berechnung der Priorität bestimmt den Abstand von diesemLook-At Punkt zumMittelpunkt eines jeden Octree Elements. Die Priorität ist direktproportional zum errechneten Abstand der zwei Punkte. Octree Elemente nahe amLook-At Punkt bekommen daher eine höhere Priorität (kleinerer Prioritätswert) alsElemente, die sich weiter weg befinden.

Werden die Prioritäten nach diesem Verfahren berechnet, ergibt sich eine höher

42

Kapitel 4Konzeption

Abbildung 4.15: Rotation um den Look-At Punkt

aufgelöste Darstellung der Volumendaten in der Umgebung des Look-At Punktes.Der Benutzer kann durch Verschieben des Punktes genau festlegen, welche Stelle desObjekts detaillierter dargestellt werden soll.

Distanz zu Sichtstrahl und Kamera Bei dieser Methode zur Berechnung derPrioritäten dient eine Linie, die von der Position der Kamera durch den Look-At Punkt verläuft (siehe Abbildung 4.17), als Bezugslinie. Zu dieser Linie werdenalle Abstände zu den einzelnen Octree Elementen berechnet. Die Entfernungen zurBezugslinie gehen direkt in den Prioritätswert ein. Somit werden Teilvolumina, diesich näher an dieser Linie befinden, höher priorisiert.

Dieser Wert berechnet sich durch den Abstand von Kameraposition zu den einzelnenTeilvolumina.

Zusammengefasst werden durch diese Methode Prioritätswerte berechnet, die dazuführen, dass diejenigen Teilvolumina zuerst geladen werden, deren Positionen näheram Betrachter und näher an der Bezugslinie liegen.

43

Kapitel 4Konzeption

Vergleich derMethoden Um die Auswirkungen der beiden Berechnungsmethodenauf die Darstellung der 3D-Szene zu demonstrieren, wurden zwei Bilder der resultie-renden Gitternetzstrukturen aufgenommen. Dabei wurde dieselbe Kameraposition,dasselbe Volumen und dieselbe zur Verfügung stehende Speichergröße verwendet,damit die Ergebnisse vergleichbar sind.

In Abbildung 4.16 wurde das Gitternetz durch die Distanz zu Look-At PunktMethode berechnet. Das Gitternetz ist in der nähe des Look-At Punktes sehrengmaschig. In diesem kleinen Bereich des Gitternetzes sind viele hochauflösendeTeilvolumina sichtbar.

Abbildung 4.16: Gitternetzmodell des Octrees nach Berechnung der Prioritätendurch den Distanz zu Look-At Algorithmus.

Abbildung 4.17 zeigt die Gitternetzstruktur nach der Berechnung der Prioritätenanhand der Distanz zu Sichtstrahl und Kamera Methode. Bei diesem Gitternetzwurden weniger sehr hoch aufgelöste Teilvolumina geladen. In der Nähe des Look-AtPunktes gibt es einen Bereich, in dem das Gitternetz etwas engmaschiger ist. Derübrige Teil des Gitternetzes ist einheitlich strukturiert.

Die Distanz zu Sichtstrahl und Kamera Methode ergibt im Vergleich einen besserenvisuellen Eindruck, da das Objekt gleichmäßig scharf dargestellt wird. Deshalbwerden die Prioritäten standardmäßig nach dieser Methode berechnet.

44

Kapitel 4Konzeption

Abbildung 4.17: Gitternetzmodell des Octrees nach Berechnung der Prioritätendurch den Distanz zu Sichtstrahl und Kamera Algorithmus.

45

Kapitel 5Implementierung

5 Implementierung

In diesem Abschnitt wird auf die Implementierung der Software eingegangen. Dabeiwerden die Punkte angesprochen, die für die Funktion der Programme amwichtigstensind oder durch die Konzeption (Kapitel 4) unzureichend erklärt wurden.

5.1 Kodierung der Voxelwerte

Wie in Kapitel 2 dargestellt, sind Voxel die Bildpunkte eines dreidimensionalenDatensatzes. Im Vorverarbeitungsschritt (Kapitel 4.2) werden die Volumendaten in2D-Texturen umgewandelt und auf einer Festplatte gespeichert. In Kapitel 4.2.2wird beschrieben, wie diese Texturen aus mehreren Schichtbildern einesVolumendatensatzes erstellt werden. Bevor eine Textur auf die Festplatte geschriebenwerden kann, muss ein passendes Dateiformat und eine geeignete Kodierung derWerte festgelegt werden. Im folgenden Abschnitt werden dieses Dateiformat undverschiedene Methoden zur Kodierung der Daten vorgestellt.

Als Dateiformat für die Texturen wird das Portable Network Graphics (PNG) Formatverwendet, da es eine verlustfreie Komprimierung der Bilddaten ermöglicht. Bei derErstellung einer Bilddatei muss neben dem Dateiformat ein Pixelformat angegebenwerden. Das Pixelformat eines Bildes gibt an, wie ein einzelnes Pixel in der Bilddateibeschrieben wird. Ein Pixel besteht in der Computergrafik aus den FarbkomponentenRot (R) Grün (G) und Blau (B). Hinzukommen kann ein Wert für die Transparenzdes Pixels. Dieser Wert wird als Alpha (A) des Pixels bezeichnet. Dabei bedeutetein niedriger Wert, dass das Pixel lichtdurchlässig ist. Ein hoher Wert steht fürlichtundurchlässige Pixel.

46


Die Vorverarbeitung arbeitet ausschließlich mit ushort Variablen. Rohdaten andererDatentypen werden während des Lesevorgangs in ushort Variablen umgerechnet.Der Datentyp ushort beschreibt eine 16 bit große Zahl (einen Wert zwischen 0 und65.535).

Ein entsprechendes Pixelformat, das je Pixel einen einzelnen 16 bit Wert speichert,wird im verwendeten .NET Framework nicht unterstützt. Deshalb muss indieser Arbeit auf andere Formate zurückgegriffen werden. Dabei wurden folgendePixelformate für unterschiedliche Verwendungszwecke implementiert:

16 bit pro Farbkanal (RGB) Bei diesem Pixelformat werden drei Farbwertepro Pixel gespeichert. Ein 16 bit Farbwert pro Rot-, Grün- und Blaukanal. Dasgespeicherte Bild enthält keinen Alphakanal. Um ein Graustufenbild zu generieren,können die Werte der einzelnen Voxel in jeden der drei Farbkanäle geschriebenwerden. Dies verändert jedoch lediglich die Farbe der Textur. Für die spätereDarstellung der Daten genügt es, die Werte der Voxel in einen Farbkanal pro Pixel zuspeichern. Abbildung 5.1 zeigt resultierende Beispielbilder dieser zwei Varianten.

(a) (b)

Abbildung 5.1: In a) wurde der Voxelwert in jeden Farbkanal geschrieben. b) zeigtdieselbe Textur wobei der Wert nur im Rotkanal steht.

8 bit pro Farbkanal (RGBA) Dieses Pixelformat speichert pro Pixel vier 8 bitWerte. Hierfür werden die 16 bit Werte der Voxel in 8 bit Werte umgerechnet.Durch die Verringerung der Quantisierung gehen dabei Bildinformationen verloren.Der Wert jedes Voxels wird in den Rotkanal des Pixels geschrieben. Der Vorteildieser Kodierung ist, dass die übrigen Farbkanäle (Grün, Blau, Alpha) verwendet

47


werden können, um beispielsweise den Vektor eines zuvor berechneten Gradienten zuspeichern. Durch diese zusätzliche Information kann im späteren Rendering Prozessdie Beleuchtung des Objekts berechnet werden.

Abbildung 5.2: Diese Abbildung zeigt eine Textur, bei der im roten Farbkanal dieBildinformation gespeichert ist. Im Grün-, Blau- und Alphakanalwird jeweils eine Komponente des Gradienten gespeichert.

8 bit pro Farbkanal (RGBA) – Floating Point Bei diesem Pixelformat werdenwie im Paragraph zuvor pro Pixel vier 8 bit Werte gespeichert. Die 16 bit Werteder Voxel werden hierfür, anders als im letzten Paragraphen, vor dem Speichern inFloating Point Werte umgerechnet. Ein Floating Point Wert ist 4 Byte (4 × 8 bit)groß. In jedem Farbkanal (Rot, Grün, Blau, Alpha) wird ein Byte des FloatingPoint Wertes gespeichert. Wichtig ist dabei, dass die Reihenfolge der Bytes in denFarbkanälen beim Lesen der Daten berücksichtigt wird. Die einzelnen Bytes müssenin der richtigen Reihenfolge zusammengesetzt werden, um den darin enthaltenenWert nicht zu verändern. Eine Textur, die durch diese Kodierung generiert wurde,zeigt Abbildung 5.3.

16 bit pro Farbkanal (RGBA) Hierbei handelt es sich um eine Erweiterungder 16 bit pro Farbkanal (RGB) Kodierung. Für jeden Pixel kann hierbei einweiterer 16 bit Wert in einen Alphakanal geschrieben werden. Somit können nebender Bildinformation im Rotkanal weitere drei 16 bit Werte im Grün-, Blau- undAlphakanal gespeichert werden. In diesen drei ungenutzten Farbkanälen kann, wiebereits erwähnt, der Vektor des Gradient für jeden Pixel gespeichert werden.

48


Abbildung 5.3: 32 bit Floating Point Variablen kodiert in einer Textur mit 8 bit proFarbkanal

Im Programm zur Vorverarbeitung der Volumendaten kann der Benutzer einstellen,welches Pixelformat mit der entsprechenden Kodierung der einzelnen Pixelfür die Generierung der Texturen verwendet werden soll. Eine gleichzeitigeAusgabe der Texturen in den vier möglichen Pixelformaten ist möglich. Diesbenötigt dementsprechend zusätzlichen freien Festplattenspeicher. Die Laufzeit desProgramms wird durch die parallele Ausgabe von unterschiedlich kodierten Texturennur geringfügig beeinflusst.

In den Standardbrowsern wie Chrome, Firefox oder Internet Explorer werden derzeitkeine Texturen unterstützt, deren Farbkanäle Werte speichern, die größer als 8 bitsind. Beispielsweise wird eine 48 bit Textur (jeweils 16 bit für Rot- Grün- undBlaukanal) beim Laden in den Browser in eine 24 bit Textur umgewandelt. Umdennoch Texturen mit einer Quantisierung von 16 bit darstellen zu können, wurdedie Kodierung 8 bit pro Farbkanal (RGBA) – Floating Point verwendet. Im folgendenKapitel wird diese Vorgehensweise näher erläutert.

49


5.2 Erhöhung derQuantisierungsauflösung

Wie im vorherigen Kapitel erwähnt, unterstützen Standardbrowser keine Texturenmit Werten einer höheren Quantisierung als 8 bit pro Farbkanal. Deshalb muss fürdie Darstellung solcher Texturen eine spezielle Lösung gefunden werden. In diesemKapitel wird beschrieben, wie dieses Problem gelöst wurde. Das konkrete Ziel ist,Texturen mit 16 bit Werten zunächst in den Browser und anschließend durch dieWebGL API in den Grafikspeicher zu laden.

Das Codebeispiel 5.1 zeigt, wie die Texturen in den Browser geladen werden. Eswird im Konstruktor einer Textur ein neues Image Objekt angelegt (Zeile 4), dessenProperty src auf den entsprechenden Pfad gesetzt wird (Zeile 14) unter dem dieTextur gespeichert ist. In Zeile 11 des Beispiels wird eine onload Funktion definiert.Diese Funktion wird aufgerufen, nachdem die Textur erfolgreich geladen wurde. Indieser Methode wird zunächst das Pixelformat der geladenen Textur überprüft undanschließend in den Grafikspeicher geladen.

Codebeispiel 5.1: Laden von Texturen

1 function Texture3D(... , src , ...) {2 ...3 this.src = src;4 this.image = new Image ();5 ...6 this.load();7 };89 Texture3D.prototype.load = function () {10 // Onload - after image has been loaded11 this.image.onload = function () {12 this.setupTexture ();13 } .bind(this);14 this.image.src = this.src;15 };

Besitzt die durch src referenzierte Textur 16 bit Farbkanäle, werden die darinenthaltenen Farbwerte während des Ladevorgangs im Browser auf 8 bit umgerechnet.Aus diesem Grund wird die im vorherigen Kapitel vorgestellte 8 bit pro Farbkanal

50


(RGBA) – Floating Point Kodierung verwendet, um Texturen mit 16 bit Farbwertenauf dem Grafikspeicher abzulegen. Da bei dieser Kodierung jeder Wert in den vierFarbkanälen 8 bit groß ist, kann die Textur wie in Codebeispiel 5.1 geladen werdenohne, dass der Browser die Daten verändert.

Nachdem die Textur in den Speicher des Browsers geladen wurde, müssen dievier 8 bit Farbwerte aus den Farbkanälen jedes Pixels in Floating Point Variablenumgewandelt werden. Zuvor wird überprüft, ob der Browser die entsprechendenWebGL-Erweiterungen für die Behandlung von Floating Point Texturen unterstützt.Folgende zwei Erweiterungen sind dabei nötig, um derartige Texturen verwenden zukönnen:

• OES_texture_float

• OES_texture_float_linear

Werden die Erweiterungen unterstützt, wird die Textur durch den Befehl in Zeile 2des Codebeispiels 5.2 auf dem Grafikspeicher abgelegt. Um die 8 bit Werte zukonvertieren, muss die Textur zunächst in einen Framebuffer geschrieben werden. Ausdiesem Speicher können anschließend für jeden Pixel die Werte aus den Farbkanälengelesen werden (siehe Zeile 14). Die Konvertierung der vier 8 bit Werte erfolgtanschließend über ein Float32Array, das mit den zuvor gelesenen Pixelwertenbefüllt wird (Zeile 17). Abbildung 5.4 veranschaulicht die Funktionsweise der fürdie Konvertierung benutzten Typed Arrays.

Abbildung 5.4: Konvertierung von 8 bit Daten in Floating Point Daten durch TypedArrays

51


Nach der Konvertierung der vier 8 bit Farbwerte in die entsprechenden Floating PointWerte können diese in den Grafikspeicher geladen (Zeile 19 in Codebeispiel 5.2) undanschließend im Rendering Prozess verwendet werden.

Codebeispiel 5.2: Umwandlung 4× 8bit in Floating Point

1 //Load the Image onto the texture2 gl.texImage2D(gl.TEXTURE_2D , 0, gl.RGBA , gl.RGBA ,

gl.UNSIGNED_BYTE , this.image);34 // Framebuffer to draw texture5 var fb = gl.createFramebuffer ();6 //Bind the buffer7 gl.bindFramebuffer(gl.FRAMEBUFFER , fb);8 //Draw texture to framebuffer9 gl.framebufferTexture2D(gl.FRAMEBUFFER , gl.COLOR_ATTACHMENT0 ,

gl.TEXTURE_2D , this.texture , 0);1011 // Initialize 8 bit Array12 var pixels = new Uint8Array(width * height * 4);13 //Read Pixels of texture from framebuffer14 gl.readPixels (0, 0, width , height , gl.RGBA , gl.UNSIGNED_BYTE ,

pixels);1516 //Cast 8 bit into floating point17 var floatView = new Float32Array(pixels.buffer);18 //Write floating point values to texture19 gl.texImage2D(gl.TEXTURE_2D , 0, gl.LUMINANCE , width , height , 0,

gl.LUMINANCE , gl.FLOAT , floatView);

52


5.3 Compositing

Das sogenannte Compositing ist ein sehr wichtiger Prozess bei der Darstellungvon Volumendaten. Dabei werden die Voxel miteinander verrechnet, die imVolumendatensatz hintereinanderliegen. In dieser Arbeit wird dabei ein Back-to-Front Compositing-Algorithmus verwendet. Das bedeutet, dass die Werte derhintereinanderliegenden Voxel nacheinander von hinten nach vorne (ausgehend vomBetrachter) miteinander verrechnet werden. Abbildung 5.5 stellt das Compositingbildlich dar.

Abbildung 5.5: Back-to-Front Compositing [1]

5.3.1 Einfaches Compositing

Das Compositing findet im Fragmentshader (siehe Kapitel 3.4.2 und 3.4.3) statt.Ein Algorithmus ermittelt für jeden Pixel des Bildschirms die korrekten Farb- undAlphawerte. Durch den in Kapitel 2.3 erläuterten Ray-Casting-Algorithmus werdenhierfür Sichtstrahlen für jedes Pixel des Bildschirms berechnet. Entlang dieser

53


Sichtstrahlen werden die hintereinanderliegenden Voxel durch den Compositing-Algorithmus miteinander verrechnet.

Während der Rasterisierung (siehe Kapitel 3.4.3) werden die Vorderseitendes Volumens durch sogenanntes Front-Face-Culling verworfen, sodass nur dieRückseiten des Würfels im weiteren Verlauf der Rendering Pipeline berücksichtigtwerden. Das Front-Face-Culling wird durch Abbildung 5.6 verdeutlicht.

Abbildung 5.6: Front-Face-Culling eines Würfels

Um die Farbwerte entlang eines Sichtstrahls zu bestimmen, müssen zuerst diePunkte bestimmt werden, an deren Positionen die Sichtstrahlen in das Volumeneindringen beziehungsweise das Volumen auf der gegenüberliegenden Seite verlassen.Die Eintrittspunkte der Sichtstrahlen ergeben sich aus den Fragmenten, die inder Szene dargestellt werden müssen. Dabei handelt es sich um die Bildpunkte,die sich aus der Rasterisierung der Rückseiten (Front-Face-Culling) des Volumensergeben. Durch die Blickrichtung der Kamera wird auf der gegenüberliegendenSeite des Volumens der Austrittspunkt des Sichtstrahls ermittelt. Zwischen demEintrittspunkt und dem Austrittspunkt findet anschließend das Compositing statt.Abbildung 5.7 fasst die Prozessschritte von der Rasterisierung bis zum Compositingbildlich zusammen.

Die Verrechnung der hintereinanderliegenden Werte entlang eines Sichtstrahlswird mithilfe des Codebeispiels 5.3 beschrieben. Es handelt sich bei diesemCode um den Teil des Fragmentshaders, der für das Lesen und Verarbeiten derSamples verantwortlich ist. Für die Iteration zwischen Ein- und Austrittspunkt des

54


Abbildung 5.7: Prozessschritte von der Rasterisierung bis zum Compositing

55


Sichtstrahls wird eine for-Schleife verwendet. Die Anzahl der Samples, die entlangeines Sichtstrahls abgetastet werden, wird in dieser Arbeit durch folgende Berechnungermittelt:

Samplerate = vmax ∗√3

Dabei steht vmax für die maximale Seitenlänge der verwendeten Texturen.√3 ist die

Länge einer Diagonalen eines gleichseitigen Würfels. Bei dieser Anzahl an Sampleswird jedes Voxel entlang eines diagonal durch das Volumen verlaufenden Sichtstrahlsabgetastet.

Die endgültige Bestimmung des Farb- und Alphawertes entlang eines Sichtstrahlswird im Folgenden anhand des Codebeispiels 5.3 zeilenweise beschrieben:

1. Initialisierung der konstanten Parameter (Zeile 2-7)

2. Textur Lookup an der Eintrittsstelle des Sichtstrahls (Zeile 8)

3. Lesen des Voxelwertes aus dem Rot-Kanal (Zeile 10)

4. Multiplizieren des Voxelwertes mit einem konstanten Opazitätsfaktor (Zeile 13)

5. Konvertierung des Voxelwertes in Grauwert (Zeile 17)

6. Berechnung des Farbwertes (Einfaches Compositing) an der aktuellen Positiondes Sichtstrahls (Zeile 20)

7. Berechnung des Transparenzwertes (Mehrfaches Compositing) für dengesamten Sichtstrahl (Zeile 22)

8. Verschiebung der Position entlang des Sichtstrahls um den Abstand einesSamples in Richtung Kamera (Zeile 25)

56


Codebeispiel 5.3: Compositing Algorithmus

1 // Initialize constant values2 float interBlockTransparency = 1.0;3 vec3 currentPosition = getEntryPoint ();4 vec3 step = (getExitPoint () - getEntryPoint ()) / SAMPLES;5 float opacityFactor = muA * length(step);6 vec3 currentColor = vec3(0.0);78 for (int i = 0; i < stepCount; ++i)9 {10 // Texture lookup11 vec4 data = textureLookUp(currentPosition);12 //Get the "real" data from red channel13 float value = data.r;1415 // Calculate opacity16 float opacity = min(1.0 , value * opacityFactor);17 // Transparency18 float transparency = 1.0 - opacity;1920 vec3 color = vec3(value);2122 // Calculate new color adding old color from sample before23 currentColor = color * opacity + transparency * currentColor;24 // Calculate new transparency multiplying the old transparency25 interBlockTransparency *= transparency;2627 // Increment current position on the ray28 currentPosition += step;29 }3031 return vec4(currentColor , 1.0 - interBlockTransparency);

57


Dieser Ablauf innerhalb der for-Schleife findet für jedes Sample zwischen Eintritts-und Austrittspunkt eines Sichtstrahls statt. Der resultierende Farbwert wird durchdie Gleichung in Zeile 20 bestimmt. Diese Programmroutine:

currentColor = color · opacity + transparency · currentColor

kann durch folgende mathematische Gleichung ausgedrückt werden:

transparency = α, opacity = (1− α)

Cnew = αC + (1− α)Cold (5.1)

Diese Gleichung beschreibt in der Computergrafik das sogenannte Blending. Dabeiwerden in einer 3D-Szene hintereinanderliegende Pixel durch deren Alphawertmiteinander verrechnet um ein Ergebnisbild zu erhalten. Ersetzt man in derGleichung (5.1) die Variablen Cnew durch I(sk), αC durch bk, (1− α) durch θk undCold durch I(sk−1) erhält man exakt dieselbe Gleichung wie (2.4) aus Kapitel 2.3, dieaus dem Modell der Emission und Absorption abgeleitet wurde.

5.3.2 Mehrfaches Compositing

Um ein Volumen darzustellen, das aus mehreren Octree Elementen besteht, müssendie hintereinanderliegenden Teilvolumina ebenfalls miteinander verrechnet werden.Für jedes Teilvolumen des Octrees werden durch Ray-Casting und das oben erläuterteCompositing Farbwerte berechnet, die nur für das jeweilige Teilvolumen gelten. Fürdiese Berechnung werden die Transparenzwerte der Samples entlang des Sichtstrahlsmiteinander multipliziert und in der Variablen interBlockTransparency gespeichert(siehe Zeile 22 im Codebeispiel 5.3). Dieser Wert wird in einen Opazitätswertumgerechnet und zusammen mit dem entsprechenden Farbwert in den Framebuffergeschrieben.

Abbildung 5.8 zeigt das Compositing für zwei hintereinanderliegende Teilvoluminaund soll für die folgenden Erläuterungen als Beispiel dienen. Das Compositingergibt für das erste Teilvolumen, wie im vorherigen Kapitel bereits erklärt, einen

58


Farb- und einen Alphawert, der anschließend in einen Framebuffer geschrieben wird.Dasselbe geschieht für das zweite Teilvolumen. Jedoch werden die Ergebniswertein denselben Framebuffer geschrieben und müssen hierfür miteinander verrechnetwerden. Diese Berechnung wird durch die Grafikeinheit automatisch vorgenommen,wenn die Option Blending aktiviert ist. Die Kombination aus bereits vorhandenenund neu berechneten Werten innerhalb des Framebuffers geschieht im Prinzip,wie in Kapitel 5.3.1 beschrieben, nach Gleichung 5.1. Jedoch wird der Farbwert,der aktuell im Framebuffer steht, nicht mit dem Alphawert multipliziert, da diesdurch die interBlockTransparency bereits geschehen ist. Dieses Verhalten wirddurch die WebGL-Funktion gl.blendFunc(gl.ONE, gl.ONE_MINUS_SRC_ALPHA)festgelegt.

Abbildung 5.8: Compositing von mehreren Teilvolumina

59

Kapitel 6Ergebnisse

6 Ergebnisse

Wie im Kapitel Konzeption bereits erwähnt, ist die Arbeit in zwei Teilentwicklungenunterteilt. Hierbei handelt es sich um zwei unabhängige Programmteile. Mithilfe desersten Programms (Kapitel 4.2) werden Volumendatensätze in kleinere Voluminaunterteilt, skaliert und als 2D-Texturen auf der Festplatte abgelegt. Das zweiteProgramm (Kapitel 4.3) verwendet diese Texturen, um das Volumen in einemWebbrowser zu visualisieren.

In den folgenden zwei Abschnitten werden die Funktionen der Programmezusammengefasst und getestet. Dabei wird die Software anhand von Laufzeit,Darstellungsqualität und Darstellungsgeschwindigkeit beurteilt. Im ersten Abschnittwird die Vorverarbeitung genauer betrachtet. Dabei soll die Zeit bestimmt werden,die für die Vorverarbeitung der Volumendaten benötigt wird. Der zweite Abschnittdes Ergebnisteils bewertet die Visualisierung der Volumina. Die hierfür verwendetenTestsysteme sind im Anhang B beschrieben.

Vorverarbeitung

Die Software für die Vorverarbeitung der Volumendaten arbeitet mit Werten derDatentypen UInt8, UInt16 oder Float. Wie in Kapitel 4.2.2 beschrieben, werden ausVolumendaten mehrere 2D-Texturen generiert und auf der Festplatte gespeichert.Hierfür wird das gesamte Volumen eingelesen und verarbeitet. Interessant ist hierbeidie für den Vorverarbeitungsschritt (Kapitel 4.2) benötigte Zeit. Im Folgenden wirddargestellt, wie sich die Dauer der Vorverarbeitung zur Größe der Volumendatenverhält. Für die Bestimmung dieser Zeiten werden die Volumendatensätze ausTabelle 4.1 mithilfe der Vorverarbeitungssoftware verarbeitet. Die Messergebnissesind in Tabelle 6.1 aufgeführt.

60

Kapitel 6Ergebnisse

Name Größe Typ Dauer TexturenVerarbeiten 1 Speichern 2 GesamtEngine 16 MB 8bit 4s 1s 5s 9Pig 268 MB 16 bit 10s 3s 13s 73Melanchton Uhr 3375 MB 32 bit 281s 60s 341s 585Container 6993 MB 16 bit 989s 317s 1306s 4681Turbinenschaufel 14372 MB 16 bit 2061s 558s 2619s 4681

1 Das Verarbeiten beinhaltet Bricking, Skalieren und Lesen der Daten2 Das Speichern beinhaltet zusätzlich die Komprimierung der Daten in das PNG Format

Tabelle 6.1: Testergebnisse der Vorverarbeitungsdauer

Für die Vorverarbeitung der Volumendaten wurde das System A (Anhang B.1)verwendet. Die maximale Größe der Volumenblöcke wurde bei den durchgeführtenTests auf 128× 128× 128 festgelegt. Die Texel der Texturen wurden im Pixelformat8 bit pro Farbkanal (RGBA) abgespeichert.

Eine Auswertung derMessdaten aus Tabelle 6.1 ist ohne Referenzen nicht zielführend.Die aufgeführten Daten können jedoch für zukünftige Arbeiten als Referenz dienen,die sich mit der Verarbeitung von Volumendaten befassen, um den in dieser Arbeitgewählten Ansatz zu optimieren.

Visualisierung

Die Darstellung der durch die Vorverarbeitung generierten Daten übernimmt eineJavascript Applikation (Kapitel 4.3). Die Texturen unterschiedlicher Detailstufenwerden in einem Octree strukturiert und gespeichert. Zur Visualisierung derDaten wird ein Ray-Casting Algorithmus angewendet. Um die Performanz derVisualisierungssoftware beurteilen zu können wurde das Volumen der MelanchtonUhr auf zwei unterschiedlich leistungsstarken Rechnern (siehe Anhang B) dargestellt.Die hierfür benötigten Texturen liegen im Pixelformat 8 bit pro Farbkanal (RGBA)vor. Die Performanz wird durch die Anzahl der Bilder gemessen, die der Computerpro Sekunde für die Darstellung berechnet. Je mehr Bilder der Rechner pro Sekundeliefern kann, desto flüssiger ist die Darstellung des Volumens. In mehreren Schrittenwird dabei die Anzahl der Teilvolumina in der 3D-Szene erhöht, womit der benötigteRechenaufwand aber auch die Darstellungsqualität ansteigt. Die Testergebnissebefinden sich in Tabelle 6.2.

61

Kapitel 6Ergebnisse

Teilvolumina Voxelanzahl fps (System A) fps (System B)1 1,72 Mio. 8,0 60,1 2

8 13,8 Mio. 3,2 60,0 2

15 25,9 Mio. 2,1 49,022 38,0 Mio. 1,6 32,129 50,1 Mio. 1,4 23,736 62,2 Mio. 1,2 19,043 74,3 Mio. 1,1 16,050 86,4 Mio. 0,9 13,857 98,4 Mio. 0,8 12,264 110 Mio. 0,8 11,071 123 Mio. - 1 10,178 135 Mio. - 1 9,585 147 Mio. - 1 8,9

1 Testabbruch, da Bildwiederholrate zu niedrig2 Browser begrenzt Bildwiederholrate auf 60 fps

Tabelle 6.2: Testergebnisse für die Darstellung der Volumendaten

Die erste Spalte dieser Tabelle zeigt die Anzahl der dargestellten Teilvolumina.In der zweiten Spalte wird angegeben, wie viele Voxel in der Szene dargestelltwerden. Die dritte und vierte Spalte beinhalten die Anzahl der Bilder, welche diebeiden unterschiedlichen Rechnersysteme pro Sekunde während der Visualisierungberechnet haben.

Anhand dieser Testdaten ist ersichtlich, dass selbst der leistungsstarke Rechner(siehe Anhang B.2) bei zunehmender Anzahl an dargestellten Teilvolumina schnellunter einen Wert von 20 fps kommen kann. Das leistungsschwächere System Aschneidet bei diesem Test sehr schlecht ab. Bei Bildwiederholraten unter 8 fpsreagiert die Applikation nur sehr träge. Ab 50 dargestellten Teilvolumina und einerBildwiederholrate von unter 1 fps ist die Bedienung der Applikation unmöglich,weshalb der Test bei 64 dargestellten Teilvolumina abgebrochen wurde.

Aus diesen Testdaten wurden zwei Maßnahmen abgeleitet, um die Performanz derApplikation zu verbessern. Zum einen wird der Rendering Prozess nicht dauerhaftausgeführt. Die darzustellenden Teilvolumina werden an ihrer Position einmalgezeichnet. Anschließend wird das Rendering der Szene angehalten sofern sich dieSzene nicht ändert. Zum anderen wird die Darstellungsqualität der Szene, wie in

62

Kapitel 6Ergebnisse

Kapitel 4.3.2 beschrieben, während einer Interaktion verringert. Dies geschieht überdie Verkleinerung des Viewports und über die Darstellung des niedrig aufgelöstenWurzelelements des Octrees.

Aufgrund der Verkleinerung des Viewports werden für die Darstellung der Szeneweniger pro-pixel Operationen (siehe Kapitel 3.4.3) ausgeführt. Abbildung 6.1zeigt den mit der Verkleinerung des Viewports einhergehenden Qualitätsverlust derDarstellung. Jedoch konnte die Bildwiederholrate durch diese Maßnahme währendInteraktionen des Benutzers auf dem leistungsschwachen System (siehe Anhang B.1)auf 18 fps angehoben werden.

(a) (b)

Abbildung 6.1: Auswirkung der Verkleinerung des Viewports. In (a) wurde derViewport im Vergleich zu (b) halbiert.

Durch die Struktur des Octrees ist es möglich, einen Volumendatensatz inunterschiedlichen Detailstufen auf dem Bildschirm darzustellen. Abbildung 6.2 zeigtvier mal denselben Datensatz der Melanchton Uhr in unterschiedlichen Detailstufen.Dabei ist in (a) nur das Wurzelelement des Octrees geladen. Bei (b) sind acht,in (c) 64 und in (d) 29 Teilvolumina dargestellt. Abbildung 6.2 (d) zeigt, dass hochund niedrig aufgelöste Teilvolumina innerhalb einer 3D-Szene zusammen dargestelltwerden können.

63

Kapitel 6Ergebnisse

Der im Rahmen dieser Arbeit entstandene Volume Renderer zeigt, dass es möglichist, große Volumendatensätze im Browser darzustellen. Durch das Zusammenspiel derhoch und niedrig aufgelösten Texturen ist es möglich, die Darstellungsqualität an dasclientseitige Rechnersystem anzupassen. Interaktionen können durch Ausblendenhoch aufgelöster Teilvolumina sehr flüssig dargestellt werden. Der Ray-CastingAlgorithmus liefert qualitativ hochwertige Ergebnisse.

Die gesamte Entwicklung stellt die Grundfunktionalität eines Volume Rendererszur Verfügung. Der webbasierte Ansatz erlaubt die Ausführung der Applikationauf sehr unterschiedlichen Systemen und kann dank der adaptiven Darstellung vonhoch und niedrig aufgelösten Volumendaten an die Leistungsfähigkeit des jeweiligenRechnersystems angepasst werden. Mit der Unterstützung einiger Features, die imnächsten Kapitel erläutert werden, kann die Applikation in Zukunft genutzt werden,um Kunden des Fraunhofer Instituts EZRT Messdaten eindrucksvoll im Browser zupräsentieren.

64

Kapitel 6Ergebnisse

(a) Ein Volumen (b) Acht Teilvolumina

(c) 64 Teilvolumina (d) 29 Teilvolumina

Abbildung 6.2: Darstellungsqualität bei Zunahme der visualisierten Teilvolumina

65

Kapitel 7Ausblick

7 Ausblick

In diesem Kapitel werden Ideen für weiterführende Entwicklungen vorgestellt,die sowohl Leistungsfähigkeit als auch Darstellungsqualität der in dieser Arbeitentwickelten Software verbessern können. Im ersten Abschnitt befinden sichVerbesserungsvorschläge für das Programm zur Vorverarbeitung der Volumendaten.Der zweite Abschnitt befasst sich mit zusätzlichen Features für den Volume Renderer.Einige der aufgelisteten Funktionen wurden bereits in Ansätzen realisiert. Da einekomplette Implementierung jedoch den Rahmen dieser Arbeit sprengen würde,werden sie nicht im Detail behandelt.

Vorverarbeitung

Multicore UnterstützungDie Verarbeitung der Volumendaten wird derzeit nur auf einem Prozessorkernausgeführt. Moderne Rechner besitzen meist vier oder mehr Kerne. Durch eineparallele Verarbeitung der Daten auf mehreren Kernen kann die Dauer derVorverarbeitung um ein Viertel reduziert werden.

16 bit Grayscale PixelformatWie in Kapitel 5.1 erwähnt, unterstützt das .NET Framework kein Pixelformatfür 16 bit Graustufen Bilder. Durch ein solches Format könnten Texturen mit nureinem Farbkanal pro Pixel und einer Quantisierung von 16 bit gespeichert werden,was den Speicherbedarf dieser Daten reduzieren würde.

66

Kapitel 7Ausblick

Visualisierung

Empy Space SkippingEine vielversprechende Technik zur Leistungsverbesserung ist das sogenannteEmpty Space Skipping. Teilvolumina, die keine relevante Bildinformationbeinhalten werden dabei nicht gerendert. Wie diese Technik funktioniert zeigtAbbildung 7.1.

Adaptiver FastModeMomentan wird während einer Interaktion der Viewport der Szene halbiert undnur das Wurzelelement angezeigt um die Bildwiederholrate zu verbessern. DasZiel könnte jedoch sein, diese Maßnahmen anhand der Leistungsfähigkeit desSystems zu bestimmen. Beispielsweise müsste der Viewport nicht halbiert undanstatt einem könnten acht Teilvolumina dargestellt werden, um die Qualität aufleistungsstarken Rechner auch während Interaktionen zu verbessern.

Clipping EbenenDurch Clipping Ebenen können bestimmte Bereiche der 3D-Szene ausgeblendetwerden. Mithilfe dieser Ebenen kann beispielsweise nur eine Hälte des Objektsdargestellt werden. Abbildung 7.2 demonstriert anhand der Darstellung derMelanchton Uhr, den visuellen Effekt einer Clipping Ebene.

BeleuchtungWie in Kapitel 5.1 erwähnt, können Objekte mithilfe zuvor berechneterGradienten beleuchtet werden. Die Berechnung des Gradienten könnte auch imFragmentshader vorgenommen werden, was jedoch die Bildwiederholrate negativbeeinflusst. Unabhängig davon, wie die Gradienten berechnet werden, ist dervisuelle Effekt einer Beleuchtung, der in Abbildung 7.3 zu sehen ist, in jedem Fallsehr positiv.

Farbige DarstellungDen Grauwerten des Datensatzes können über eine Transferfunktion Farbwertezugewiesen werden. Das hat den Vorteil, dass verschiedene Farben vommenschlichen Auge besser unterschieden werden können als Grauwerte.

67

Kapitel 7Ausblick

BenutzeroberflächeDie Benutzeroberfläche der Javascript Applikation ist in dieser Arbeit nur fürdie Entwicklung konzipiert worden. Bevor die Software den Entwicklungsstatusverlässt, sollte das Design und die Funktionalität der Benutzeroberfläche an dieBedürfnisse der Benutzer angepasst werden.

Unterstützung für mobile EndgerätePrinzipiell ist durch die Verwendung der WebGL API eine Darstellung auf mobilenEndgeräten mit moderner Hard- und Software möglich. Um die Funktionalitätauf diesen Geräten zu gewährleisten müssen gegebenenfalls Anpassungen an derSoftware vorgenommen werden.

(a) Volumen ohne Empty Space Skipping (b) Volumen mit Empty Space Skipping

Abbildung 7.1: Empty Space Skipping

68

Kapitel 7Ausblick

Abbildung 7.2: Melanchton Uhr mit Clipping Ebene

(a) ohne Beleuchtung (b) mit Beleuchtung(Ambient + Diffus)

Abbildung 7.3: Das Volumen Engine ohne und mit Beleuchtung

69

Anhang

A Diagramme

A.1 UMLdes Programms zur Vorverarbeitung

RecoWebPrepareVolume

Reader

-reader

1

1

RecHeader -recHeader

11

MetaData-metaData

1 1

+ConsumeVoxel()

«interface»IVolumeConsumer

+ConsumeVoxel()

MultiVC

+ConsumeVoxel()

ScaleDownVC

+ConsumeVoxel()

KernelVC

-consumer

1

*

+ConsumeVoxel()

ConverterVC

+ConsumeVoxel()

TextureSaverVC

+ConsumeVoxel()

BrickingVC

+ConsumeVoxel()

SobelGradientVC

-consumers1*

-consumer

1

1

-consumer 11

-consumer

1

1

-consumers

1

*

-consumer

1

1

Abbildung A.1: Diese Abbildung zeigt das UML-Diagramm des Programms zurVorverarbeitung der Volummendaten

vi

Anhang

A.2 UMLder Javascript Applikation

-camera

1

1

-CanvasMouseControl1

1

«interface»Renderer

-renderer1

1

-FrameCounter

1

1

EventEmitter

EventEmitter

OctreePriorityQueue

EventEmitter

-octree1

1

-children

0..8

-parent

0..1

VolumeOctreeRenderer

Main

FrameCounterCameraCanvasMouseControl

«interface»PartRenderer

Shader

RTVolumePartRenderer

FrameVertices

UtilityRenderer

-stateMachine

1

1StateMachine

BrickFrameRenderer

-vertices

1

1

-vertices

1

1

-textures

1

0..*

Texture3DRTVertices

-queues

1

2

-shader

1

1

-shader

1

1

-shader

1

1

-utilityRenderer

1

1

-partRenderer

1

1

Abbildung A.2: In dieser Abbildung ist das UML-Diagramm der JavascriptApplikation zu sehen, die das Rendern der Volumendatenübernimmt.

vii

Anhang

A.3 Zustandsautomat

Empty

Loading

Visible

shouldLoad

Invisible - ChildrenInvisible - Parent

inferiorAvailable superiorVisible

superiorInvisible

shouldUnload

Unloading

superiorVisible

Empty - Children

shouldUnload

loading - children

shouldLoad

loaded

shouldUnload

AbortLoading

shouldUnload

shouldLoad

loaded

superiorVisible

AbortLoading - children

shouldUnload

shouldLoad

loaded

superiorVisible

superiorVisible

inferiorUnavailable

ForcedVisible

forcedVisibility unforcedVisibility superiorVisible

inferiorUnavailable

rootCheck

loaded

loaded

rootLoaded

Abbildung A.3: Zustandsdiagramm für den Zustandsautomaten der das Verhaltender Octree Elemente beschreibt.

viii

Anhang

B Testsysteme

B.1 SystemA

Betriebssystem Prozessor Arbeitsspeicher

Windows 7 (64 bit) Hersteller Name Takt Speicher TaktIntel Core i5 3.30 GHz 8 GB 665 MHz

Tabelle B.1: Leistungsbeschreibung des Testsystems

Hersteller Bezeichnung Takt in MHz Speicher Busbreite

NVIDIA GeForce 210 Core Shader Memory 1024 MB 64 Bit589 1402 600

Tabelle B.2: Leistungsbeschreibung der Grafikkarte

ix

Anhang

B.2 SystemB

Betriebssystem Prozessor Arbeitsspeicher

Windows 8.1 (64 bit) Hersteller Name Takt Speicher TaktIntel Xeon E5-2640 2.50 GHz 64 GB 665 MHz

Tabelle B.3: Leistungsbeschreibung des Testsystems

Hersteller Bezeichnung Takt in MHz Speicher Busbreite

NVIDIA GeForce GTX 680 Core Boost Memory 2048 MB 64 Bit1137 1202 1502

Tabelle B.4: Leistungsbeschreibung der Grafikkarte

x

Abkürzungsverzeichnis

Abkürzungsverzeichnis

Application Programming Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . API

Direktes Volume Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DVR

Document Object Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DOM

Fixed Function Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . FFP

Frames Per Second . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . fps

Hypertext Markup Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HTML

Indirektes Volume Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IVR

Magnetresonanztomographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . MRT

Node Package Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NPM

OpenGL Shading Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . GLSL

Portable Network Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . PNG

Positronen Emissions Tomographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . PET

Programmable Rendering Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . PRP

Röntgen Computer Tomographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CT

Volume Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VR

Web Graphics Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . WebGL

xi

Abbildungsverzeichnis


2.1 Voxel Modell von Volumendatensätzen . . . . . . . . . . . . . . . . . 52.2 Image-Order Rendering Technik – Ray-Casting . . . . . . . . . . . . . 72.3 Sampling der Volumendaten durch Ray-Casting . . . . . . . . . . . . 9

3.1 Überblick Web-Technologien . . . . . . . . . . . . . . . . . . . . . . . 123.2 Textur und Textur Mapping . . . . . . . . . . . . . . . . . . . . . . . 163.3 Rendering Pipeline ohne Details . . . . . . . . . . . . . . . . . . . . . 193.4 Rendering Pipeline mit Details . . . . . . . . . . . . . . . . . . . . . . 203.5 WebGL Grafik Primitive . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.1 Beziehung zwischen Octree Elementen . . . . . . . . . . . . . . . . . . 264.2 Aufbau des Octrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.3 Grobes Konzept der Vorverarbeitung . . . . . . . . . . . . . . . . . . 284.4 Ablaufdiagramm der Vorverarbeitungspipeline . . . . . . . . . . . . . 304.5 Bricking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.6 Zuordnung der Voxel im Bricking Prozess . . . . . . . . . . . . . . . . 324.7 Vergleich Darstellung mit und ohne Interpolationsfehler . . . . . . . . 334.8 Fehlerhafte Interpolation an den Übergängen der Teilvolumina . . . . 334.9 2D-Textur Generierung aus 3D-Volumendatensätzen . . . . . . . . . . 344.10 Nummerierung der Teilvolumina . . . . . . . . . . . . . . . . . . . . . 354.11 Skalieren eines 8× 8× 8Voxel Datensatzes . . . . . . . . . . . . . . . 364.12 Verschieden aufgelöste Bereiche durch Octree . . . . . . . . . . . . . . 384.13 Statemachine Sequenzdiagramm . . . . . . . . . . . . . . . . . . . . . 414.14 Gitternetzstruktur mit Prioritäten . . . . . . . . . . . . . . . . . . . . 424.15 Rotation um den Look-At Punkt . . . . . . . . . . . . . . . . . . . . . 434.16 Prioritäten nach Distanz zu Look-At Methode . . . . . . . . . . . . . 444.17 Prioritäten nach Distanz zu Sichtstrahl und Kamera Methode . . . . . 45

xii


5.1 Textur mit 16 bit Kodierung (RGB) . . . . . . . . . . . . . . . . . . . 475.2 Kodierung von Gradienten und Bildinformation in 8 bit Farbkanälen . 485.3 Textur mit 8 bit (RGBA) Kodierung . . . . . . . . . . . . . . . . . . . 495.4 Typed Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.5 Back-to-Front Compositing [1] . . . . . . . . . . . . . . . . . . . . . . 535.6 Front-Face-Culling eines Würfels . . . . . . . . . . . . . . . . . . . . . 545.7 Prozessschritte von der Rasterisierung bis zum Compositing . . . . . . 555.8 Compositing von mehreren Teilvolumina . . . . . . . . . . . . . . . . 59

6.1 Auswirkung der Verkleinerung des Viewports . . . . . . . . . . . . . . 636.2 Darstellungsqualität bei Zunahme der visualisierten Teilvolumina . . . 65

7.1 Empty Space Skipping . . . . . . . . . . . . . . . . . . . . . . . . . . 687.2 Melanchton Uhr mit Clipping Ebene . . . . . . . . . . . . . . . . . . . 697.3 Das Volumen Engine ohne und mit Beleuchtung . . . . . . . . . . . . 69

A.1 UML-Diagramm des Programms zur Vorverarbeitung . . . . . . . . . viA.2 UML-Diagramm der Javascript Applikation . . . . . . . . . . . . . . . viiA.3 Zustandsdiagramm für den Zustandsautomaten . . . . . . . . . . . . . viii

xiii

Quellcodeverzeichnis

Quellcodeverzeichnis

3.1 Funktionsweise Javascript . . . . . . . . . . . . . . . . . . . . . . . . 143.2 jQuery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

5.1 Laden von Texturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.2 Umwandlung 4× 8 bit in Floating Point . . . . . . . . . . . . . . . . . 525.3 Compositing Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 57

xiv

Literaturverzeichnis


[1] Compositing - Vorlage für Abbildung, . URL http://commons.wikimedia.

org/wiki/File:Compositing_Front_To_Back.svg. Zugriffsdatum: 7. Januar2014.

[2] Webseite der Khronos Group - Entwickler von WebGL, . URL hhttps:

//www.khronos.org/. Zugriffsdatum: 10. Dezember 2014.

[3] Learning WebGL, . URL http://learningwebgl.com/. Zugriffsdatum: 11.November 2014.

[4] Javascript Octree Visualisierung, . URL http://pawlowski.it/octtree/.Zugriffsdatum: 2. Dezember 2014.

[5] Compositing - Vorlage für Abbildung, . URL https://github.com/

jakesgordon/javascript-state-machine. Zugriffsdatum: 7. Januar 2014.

[6] WebGL and OpenGL Differences: „No 3D Texture support“, . URL https:

//www.khronos.org/webgl/wiki/WebGL_and_OpenGL_Differences. Zugriffs-datum: 13. November 2014.

[7] Dirk Bartz and Michael Meißner. Voxels versus polygons: A comparativeapproach for volume graphics. In Min Chen, ArieE. Kaufman, and RoniYagel, editors, Volume Graphics, pages 171–184. Springer London, 2000.ISBN 978-1-85233-192-4. doi: 10.1007/978-1-4471-0737-8_10. URL http:

//dx.doi.org/10.1007/978-1-4471-0737-8_10.

[8] Klaus Engel, Martin Kraus, and Thomas Ertl. High-quality pre-integratedvolume rendering using hardware-accelerated pixel shading. In Proceedings ofthe ACM SIGGRAPH/EUROGRAPHICS Workshop on Graphics Hardware,

xv

http://commons.wikimedia.org/wiki/File:Compositing_Front_To_Back.svg

http://commons.wikimedia.org/wiki/File:Compositing_Front_To_Back.svg

hhttps://www.khronos.org/

hhttps://www.khronos.org/

http://learningwebgl.com/

http://pawlowski.it/octtree/

https://github.com/jakesgordon/javascript-state-machine

https://github.com/jakesgordon/javascript-state-machine

https://www.khronos.org/webgl/wiki/WebGL_and_OpenGL_Differences

https://www.khronos.org/webgl/wiki/WebGL_and_OpenGL_Differences

http://dx.doi.org/10.1007/978-1-4471-0737-8_10

http://dx.doi.org/10.1007/978-1-4471-0737-8_10


HWWS ’01, pages 9–16, New York, NY, USA, 2001. ACM. ISBN 1-58113-407-X. doi: 10.1145/383507.383515. URL http://doi.acm.org/10.1145/383507.

383515.

[9] Klaus Engel, Markus Hadwiger, Joe M. Kniss, Aaron E. Lefohn, Christof RezkSalama, and Daniel Weiskopf. Real-time volume graphics. In ACM SIGGRAPH2004 Course Notes, SIGGRAPH ’04, New York, NY, USA, 2004. ACM.doi: 10.1145/1103900.1103929. URL http://doi.acm.org/10.1145/1103900.

1103929.

[10] Khronos Group. WebGL Specification. URL https://www.khronos.org/

registry/webgl/specs/1.0/. Zugriffsdatum: 13. November 2014.

[11] Hans-Christian Hege, T. Höllerer, and Detlev Stalling. Volume rendering -mathematicals models and algorithmic aspects. Technical Report TR-93-07,ZIB, Takustr.7, 14195 Berlin, 1993.

[12] W. Heiden, T. Goetze, and J. Brickmann. „Marching Cube“-Algorithmenzur schnellen Generierung von Isoflächen auf der Basis dreidimensionalerDatenfelder. In Martin Frühauf and Martin Göbel, editors, Visualisierungvon Volumendaten, Beiträge zur Graphischen Datenverarbeitung, pages112–117. Springer Berlin Heidelberg, 1991. ISBN 978-3-540-54295-7.doi: 10.1007/978-3-642-76780-7_7. URL http://dx.doi.org/10.1007/

978-3-642-76780-7_7.

[13] Inc. Joyent. Entwicklungsplattform „nodeJS“. URL http://www.nodeJS.org.Zugriffsdatum: 29. Oktober 2014.

[14] The jQuery Foundation. jQuery. URL http://jquery.com/. Zugriffsdatum:31. Oktober 2014.

[15] K. Matsuda and R. Lea. WebGL Programming Guide: Interactive 3D GraphicsProgramming with WebGL. OpenGL. Pearson Education, 2013. ISBN9780133364927. URL http://books.google.de/books?id=3c-jmWkLNwUC.

[16] N.Max. Optical models for direct volume rendering. Visualization and ComputerGraphics, IEEE Transactions on, 1(2):99–108, Jun 1995. ISSN 1077-2626. doi:10.1109/2945.468400.

xvi

http://doi.acm.org/10.1145/383507.383515

http://doi.acm.org/10.1145/383507.383515

http://doi.acm.org/10.1145/1103900.1103929

http://doi.acm.org/10.1145/1103900.1103929

https://www.khronos.org/registry/webgl/specs/1.0/

https://www.khronos.org/registry/webgl/specs/1.0/

http://dx.doi.org/10.1007/978-3-642-76780-7_7

http://dx.doi.org/10.1007/978-3-642-76780-7_7

http://www.nodeJS.org

http://jquery.com/

http://books.google.de/books?id=3c-jmWkLNwUC


[17] Alfred Nischwitz, Max Fischer, Peter Haberäcker, and Gudrun Socher.Einführung in die 3D-Computergrafik mit OpenGL. In Computergrafik undBildverarbeitung, pages 38–71. Vieweg+Teubner Verlag, 2012. ISBN 978-3-8348-1304-6. doi: 10.1007/978-3-8348-8323-0_5. URL http://dx.doi.org/

10.1007/978-3-8348-8323-0_5.

[18] H. Ray, H. Pfister, D. Silver, and T.A. Cook. Ray casting architectures for volumevisualization. Visualization and Computer Graphics, IEEE Transactions on, 5(3):210–223, Jul 1999. ISSN 1077-2626. doi: 10.1109/2945.795213.

[19] Christof Rezk-Salama. Techniken der Volumenvisualisierung auf universelleinsetzbarer Graphik-Hardware. PhD thesis, Technische Fakultät der UniversitätErlangen-Nürnberg, Dezember 2001.

[20] Stefan Roettger, Stefan Guthe, Daniel Weiskopf, Thomas Ertl, and WolfgangStrasser. Smart hardware-accelerated volume rendering. In VisSym, volume 3,pages 231–238. Citeseer, 2003.

[21] Stefan Röttger. How To Build A 3D Volume Renderer. URL http://schorsch.

efi.fh-nuernberg.de/roettger/index.php/Lectures/VolumeRendering.Zugriffsdatum: 17. November 2014.

[22] SirPepe. Übersichtsgraph zu Web-Technologien. License: Creative CommonsAttribution 3.0 Germany. URL https://github.com/SirPepe/SpecGraph.Zugriffsdatum: 29. Oktober 2014.

[23] W3C. The canvas element, . URL http://www.w3.org/TR/html5/

scripting-1.html#the-canvas-element. Zugriffsdatum: 15. Oktober 2014.

[24] W3C. HTML5, . URL http://www.w3.org/TR/html5/. Zugriffsdatum: 30.Oktober 2014.

xvii

http://dx.doi.org/10.1007/978-3-8348-8323-0_5

http://dx.doi.org/10.1007/978-3-8348-8323-0_5

http://schorsch.efi.fh-nuernberg.de/roettger/index.php/Lectures/VolumeRendering

http://schorsch.efi.fh-nuernberg.de/roettger/index.php/Lectures/VolumeRendering

http://creativecommons.org/licenses/by/3.0/de/deed.en

http://creativecommons.org/licenses/by/3.0/de/deed.en

https://github.com/SirPepe/SpecGraph

http://www.w3.org/TR/html5/scripting-1.html#the-canvas-element

http://www.w3.org/TR/html5/scripting-1.html#the-canvas-element

http://www.w3.org/TR/html5/

Documents

StudiengangElektronischeund MechatronischeSysteme ...schorsch.efi.fh-nuernberg.de/mewiki/uploads/... · Als Entwicklungsumgebung für die Web-Applikation des Volumen Renderers wird