Medizinische Visualisierung - userpages.uni-koblenz.decg/ws1213/medvis/vorlesung/MedVis... · 100 Course 28: Real-Time Volume Graphics w w {{Figure 18.1: The geometric setup for light

Vorlesung 712.12.2012, Universität Koblenz-Landau

Dr. Matthias RaspeSOVAmed GmbH

Medizinische Visualisierung

MedVis - Vorlesung 7 12.12.2012 Dr. Matthias Raspe, SOVAmed GmbH

Agenda

• Organisatorisches• keine Vorlesung am 19.12.2012 => nächste Veranstaltung wieder am 09.01.2013

• Wiederholung

• GPU-Programmierung• Indirektes Volumenrendering• Transferfunktionen

• Volumenvisualisierung 2

• Direktes Volumenrendering• (Multimodale Visualisierung)

• Verarbeitung weihnachtlicher Bilddaten...

2

Wiederholung

GPU-Programmierung (Dank an Niklas Henrich)Volumenvisualisierung 1


Moderne OpenGL Pipeline

• zunehmende Flexibilität und Effekte durch Programmierbarkeit

• nicht nur parametrisierbar, sondern programmierbar• Mini-Programme (“Shader”) laufen auf Prozessoreinheiten der Grafikhardware• je nach Typ und Sprache/Sprachversion unterschiedliche Befehle und Möglichkeiten

• zahlreiche Erweiterungen, wesentlich für MedVis sind

• Fragmentshader: z.T. historisch bedingt, viel Texturoperationen• Vertex- und Geometryshader: je nach Anwendung (Glyphen, Geometrien etc.)

4


Vertexprogramm

• Arbeitet nur auf einem Eckpunkt• keine Information über Topologie (andere Eckpunkte)• keine Punkte erzeugen oder löschen• wahlfreier Zugriff auf Texturspeicher

• Typische Aufgaben:• Eckpunkttransformationen

(Welt- in Kamerakoordinaten,kanon. Volumen)

• Normalentransformation• Beleuchtung (in Kamera-

Koordinaten)

• Nicht in Vertexprogramm:• Clipping, persp. Division

5


Fragmentprogramm

• Arbeitet am Ende der Pipeline• für jedes zu zeichnende Fragment

ausgeführt• arbeitet nur auf aktuellem Fragment

im Framebuffer• wahlfreier Zugriff auf Texturspeicher

• Typische Aufgaben:• Farbe des Pixels berechnen• Texturzugriffe und -operationen• Effekte wie Nebel integrieren

• Nicht in Fragmentprogramm:• Tiefen-/Stenciltest• Alpha-Blending

6


Grundlegender Ablauf

(1) Shader Objekt erzeugen

(2) Sourcecode laden

(3) Shader compilieren

(4) Shader Program Objekt erzeugen

(5) Shader Program mit Shadern belegen

(6) Program linken

(7) Program benutzen

(8) Programm(e) ausführen

(9) Zurück zur OpenGL Fixed-Function Pipeline

7

shader = glCreateShader(TYPE);

glShaderSource(shader,&sourcePtr,0);

glCompileShader(shader);

program = glCreateProgram();

glAttachShader(program,vertexShader);

glLinkProgram(program);

glUseProgram(program);

renderObjects();

glUseProgram(0);

Volumenvisualisierung 1

Einführung, Indirektes Volumenrendering


®

Darstellung von Volumendaten

• Eine Form der Visualisierung ist die Hervorhebung gleicher Werte mit geometrischen Primitiven• Isolinien (auch „Höhenlinien“,

Konturlinien)• Isoflächen (Konturflächen)

• In dieser Form gehören sie zu den indirekten Visualisierungsmethoden

• direkte Methoden → später…

9


®

Marching Squares

• Beispiel Graustufenbild, Isolinie für C = 3• Skalarfeld der Dimension 2• Gitterpunkte = Pixelmitte

• Ergebnis ähnlich zu Kanten-detektion, aber: Kante ≠ Isolinie

0

2

2

1

2

1

2 1

2

4

46

6

4

46

6 4

4 3

5

6

52

4

6

42

4 4

4

5

2

2

1

2

: ≤ C („innerhalb“) : > C („außerhalb“)

10


®

Marching Cubes

• Die Anzahl der möglichen Kombinationen beträgt in einer Voxelzelle insgesamt 28 = 256

• Durch Anwendung der gleichen Prinzipien (Komplement, Symmetrie) lassen sich die Fälle auf die folgenden 15 Kombinationen reduzieren:

• Auch hier gibt es Mehrdeutig-keiten, die sich jedoch teilweisenicht auflösen lassen→ Löcher in Isofläche…

• Mögliche Lösungen• Zusätzliche Komplemente• Gradienten berücksichtigen• Alternative Verfahren (z.B. Marching Tetraeder, Shirley et al, 1990)

Loch in Isofläche

11


Transferfunktionen


®

Transferfunktionen

• Transferfunktionen sind eine Abbildung von der Menge der Attribute in die Menge der visuellen Eigenschaften

• Farbtabelle = diskretisierte Form der allgemeineren Transferfunktion

• Bei der Abbildung muss einem Eingabedatum eindeutig ein Wert zugeordnet werden können…

• Typische Abbildungen sind:• Skalare in Grauwerte• Skalare in RGB-Farben• Richtungsvektoren in RGB-Farben

13

f : R ! R

f : R ! R3

f : R3! R

3


®

• In der Praxis ist die Bestimmung einer “guten” Transferfunktion aufwendig

• eindimensionale TFs ermöglichen nur einfache Abbildungen

• Idee: zusätzliche Informationen wie Gradienten, Abstände etc. mit einbeziehen

• Abgrenzung sonst gleicher Strukturen möglich

• aber: TF wird dadurch mehrdimensional • große Datenmengen

• Kontrolle/User-Interface?

Transferfunktionen

Cascada: 1D-TF

Cascada: 2D-TF14


®

• Es existieren sehr viele unterschiedliche Ansätze, jedoch keine universelle Lösung• „High-Level User Interfaces for Transfer Function Design with Semantics“, Rezk-

Salama et al., 2006• „The Transfer Function Bake-Off“, Pfister et al., 2001

• Med. Workstations bieten oft Kombination aus TF-Bibliothek und manueller Steuerung (1D-TF) an

Transferfunktionen

15

Transfer Functions

3D Visualization and Image Processing 30

Each transfer function has been designed for a specific purpose, e.g. to

enhance vessels or to reveal the kidneys. Accordingly, the transfer functions

might have a lesser effect on a different dataset.

Figure 3.9: Transfer

Functions in syngo

Siemens Medical Inc.


®

Zusammenfassung TF

• Transferfunktionen weisen Volumendaten optische Eigenschaften zu, zum Beispiel:• Dichtewert → Opazität• Windrichtung → RGB-Wert

• verschiedene Dimensionen möglich, jedoch zunehmend komplexer

• kein universelles Verfahren• Unterscheidung nach Automatisierung• stark abhängig von Modalität (CT: einfach, MR: schwierig)

• aktives Forschungsgebiet

16


Grundlagen Direktes Volumenrendering


Kategorien von Volumenrendering-Verfahren

18

Volume Rendering

Indirect Direct

Software Hardware

Image-space Object-space Other

Fourier

Shear-Warp

Image-space Object-space

Ray casting Texture-based

view-parallel volume-parallel

Ray casting Splatting


®

Volumenrendering

• Man unterscheidet bei Volumenrendering direkte (DVR) und indirekte (IDVR) Verfahren

• DVR hat gegenüber IDVR einige Vorteile:• Keine zeitaufwendige und ggf. benutzerabhängige

Generierung von Flächen• Datensatz kann während der Darstellung verändert werden

(z.B. zeitvariante Daten, Clipping)• Kein zusätzlicher Speicherbedarf für Flächen

• Beide Verfahren spielen in med. Visualisierung einegroße Rolle

19


®

DVR-Grundlagen

• Allen DVR-Verfahren liegt ein optisches Modell zugrunde

• Grundsätzlich wird der Weg des Lichtes durch das “beteiligte” (engl. participating) Medium betrachtet

• Absorption → Licht geht “verloren”• Streuung (engl. scattering) → Licht

wird abgelenkt• Emission → Licht wird “erzeugt”• Schatten

• Dichte des Mediums wird direkt durch die Skalarwerte der Voxel repräsentiert

• Bezug zu realen Daten (z.B. Gewebedichte bei CT-Daten, Emission bei PET usw.)

100 Course 28: Real-Time Volume Graphics

ww {{

Figure 18.1: The geometric setup for light transport equations.

The classic volume rendering model is then written as:

L(x1, �⇥) = T (0, l)L(x0, �⇥) +

⇤ l

0

T (s, l)R(x(s))fs(x(s))Llds (18.2)

where R is the surface reflectivity color, fs is the Blinn-Phong surfaceshading model evaluated using the normalized gradient of the scalar datafield at x(s), and Ll is the intensity of a point light source. L(x0, �⇥) is thebackground intensity and T the amount the light is attenuated betweentwo points in the volume:

T (s, l) = exp

��

⇤ l

s

�(s�)ds�⇥

(18.3)

and �(s�) is the attenuation coe⇤cient at the sample s�. This volumeshading model assumes external illumination from a point light sourcethat arrives at each sample unimpeded by the intervening volume. Theonly optical properties required for this model are an achromatic attenu-ation term and the surface reflectivity color, R(x). Naturally, this modelis well-suited for rendering surface-like structures in the volume, but per-forms poorly when attempting to render more translucent materials suchas clouds and smoke. Often, the surface lighting terms are dropped andthe surface reflectivity color, R, is replaced with the emission term, E:

L(x1, �⇥) = T (0, l)L(x0, �⇥) +

⇤ l

0

T (s, l)E(x(s))ds (18.4)

20


®

DVR-Grundlagen

• Probleme: • Streuungseffekte nur sehr aufwendig abzubilden• Schatten ist sehr rechenintensiv→ auf aktueller Grafikhardware echtzeitfähig

• Emission in radiologischen Bilddaten (CT, MR etc.)nicht unmittelbar repräsentiert

• Unterschiedliches Verhalten verschiedener Wellenlängen→ extrem aufwendig, nur grob approximierbar (z.B. RGB)

• Guter Kompromiss: Emissions-Absorptions-Modell• Absorption auf Basis der Volumendaten zusammen mit Transferfunktion• Emission wird “korrigierend hinzugenommen”

21

Hadwiger et al.


®

• Ziel: Strahlungsenergie, die beim Betrachter ankommt• Prinzip analog zum klassischen Rendering (Raytracing)• zusätzlich: Berücksichtigung der Absorption durch Medium

T (s, l) = exp

!

!

" l

s

!(s!)ds!

#

aktueller Absorptions-

koeffizient

allgemein:

T (l) = exp (!! l)

konstante Absorption:

“entlang des gesamten Strahls”

Absorptions-koeffizient

Abschwächung entlang des

aktuellen Strahlwegs

Volumenrendering

22


®

• basiert auf klassischem Modell von Levoy (1988)

• vereinfachte Form, da ohne Shading und Schatten...

L(!xl, !") = T (0, l) · L(!x0, !") +

! l

0

T (s, l) · E(!x(s)) ds

Intensität beim Betrachter aus Blickrichtung

gesamte Abschwächung

Intensität des

Hintergrunds

“entlang des gesamten Strahls”

Abschwächung entlang des

aktuellen Strahlwegs

aktueller Emissionswert


ww {{

Figure 18.1: The geometric setup for light transport equations.

The classic volume rendering model is then written as:

L(x1, �⇥) = T (0, l)L(x0, �⇥) +

⇤ l

0

T (s, l)R(x(s))fs(x(s))Llds (18.2)

where R is the surface reflectivity color, fs is the Blinn-Phong surfaceshading model evaluated using the normalized gradient of the scalar datafield at x(s), and Ll is the intensity of a point light source. L(x0, �⇥) is thebackground intensity and T the amount the light is attenuated betweentwo points in the volume:

T (s, l) = exp

��

⇤ l

s

�(s�)ds�⇥

(18.3)

and �(s�) is the attenuation coe⇤cient at the sample s�. This volumeshading model assumes external illumination from a point light sourcethat arrives at each sample unimpeded by the intervening volume. Theonly optical properties required for this model are an achromatic attenu-ation term and the surface reflectivity color, R(x). Naturally, this modelis well-suited for rendering surface-like structures in the volume, but per-forms poorly when attempting to render more translucent materials suchas clouds and smoke. Often, the surface lighting terms are dropped andthe surface reflectivity color, R, is replaced with the emission term, E:

L(x1, �⇥) = T (0, l)L(x0, �⇥) +

⇤ l

0

T (s, l)E(x(s))ds (18.4)

Volumenrendering-Gleichung

23


®

Volumenrendering-Gleichung

• Bis auf etwas andere Terme vergleichbar mit der “klassischen” Renderinggleichung...?

L(!xl, !") = T (0, l) · L(!x0, !") +

! l

0

T (s, l) · E(!x(s)) ds

L(!xl, !") = T (0, l) · L(!x0, !") +

! l

0e!

R

l

s!(s!)ds

!

· E(!x(s)) ds

Lo(dAe, d !"o) = Le(dAe, d !"o) +

!2!

fr(dAe, d !"i, d !"o) · Li(dAe, d !"i) · cos #id !"i

„Integral hoch Integral“...!

T(s,l) eingesetzt:

24


®

Volumenrendering

• In Worten zusammengefasst:• Es wird entlang des Strahl integriert, d.h. man summiert die einzelnen

“Samples” (Dichtewerte usw.) auf• Und das Ganze für jeden Strahl

• Deshalb sind Schatten und Streuung so aufwendig:• Für jedes Sample entlang jedes (Seh-)strahls muss wiederum entlang eines

(Licht-)Strahls integriert werden - für jede Punktlichtquelle...• Für Streuung muss sogar über die gesamte Umgebung

integriert werden...

• Volumenrendering stellt also auch sehr hohe Anforderungen an die Effizienz der Algorithmen

25


DVR-Verfahren


Überblick

• Frequenzdomäne• Fourier-Volumenrendering• Wavelet-Rendering (hier nicht besprochen)

• Objektraum• Splatting• Texturbasiertes Rendering

• Object-aligned • View-aligned

• Bildraum: Raycasting

• Mischform (Objekt-/Bildraum): Shear-Warp

27


• Aufwand zum direkten Rendern von Volumendaten mit der Voxelauflösung N ist O(N3)

• FDVR nutzt das sog. Zentralschnitt-Theorem: • Parallelprojektion eines Signals entspricht einem

Schnitt der Fouriertransformierten dieses Signals...• Zusammen mit der Radon-Transformation

Grundlage der allgemeinen tomografischen Rekonstruktion (jedes CT-Gerät!)

• “Umkehrung” des Theorems ergibt 2D-Projektion des Volumens mit Aufwand O(N2log2N)

• Problem: gerenderte Bilder sind prinzipbedingt Projektionen der Intensitäten → “Röntgenbild-artig”...

• Spielt im Moment nur für Filterung usw. eine Rolle

1.4. Fourier Volume Rendering 11

generated surfaces depends on how well the constructed continuous function matchesthe underlying continuous function representing the discrete data set.

1.4 Fourier Volume Rendering

Frequency domain volume rendering approach is based on the Fourier projection-slicetheorem and provides high frame rates for the computation of two-dimensional intensityprojections of volumetric data sets. It allows projections of volume data to be generatedin O(n2 log n) time for a volume of size n3. In general, this technique operates on thethree-dimensional frequency domain representation of the data set. The Fourier volumerendering approach consists of the following steps: 1) Preprocessing. Compute the 3Ddiscrete Fourier transform of the volume data by FFT; 2) Actual volume rendering.For each direction � perpendicular to the image plane, firstly interpolate the Fouriertransformed data and resample on a regular grid of points in the slice plane orthogonalto � (slice extraction), then compute the 2D inverse Fourier transform (IFFT), this yieldsX-ray like image (Westenberg and Roerdink 2000).

Figure 1.8: The main steps of the frequency domain volume rendering: instead of directly projectingthe volume data, the data is transformed to frequency domain, and then extract a slice and perform aninverse transform. (Totsuka and Levoy 1993)

The frequency domain rendering concept allows renderings of X-ray images or linearlydepth cued and directional di�use shaded volumes (Totsuka and Levoy 1993; Lippertet al. 1997), but no occlusion and perspective projection. The speed improvements ofthese methods result from the low complexity of the inverse fast Fourier transform butsu�er from the costs for the two dimensional resampling.

Another big disadvantage of the frequency domain volume rendering is the high memorydemand. Where spatial domain acceleration techniques often result in compression ofthe volume, this is not possible in frequency domain (Theul 1999).

The usefulness of frequency domain volume rendering is at least questionable, since thereare other techniques that operate in spatial domain and are capable of generating similar

Fourier-Volumenrendering

28


Splatting

• Entwickelt von Westover (1990)

• Einfaches Prinzip: • Voxel werden durch Filterkerne (Gaussfilter) repräsentiert, die mit den Skalarwerten der

Ausgangsdaten gewichtet werden• Projektion dieser unterschiedlich großen “Klumpen” zu Bildflecken(footprints, splats) mit

abnehmender Intensität am Rand

• guter Vergleich: viele Schneebälle gegen Scheibe werfen...

• liefert gute Ergebnisse, jedoch Nachteile• Unschärfe, Schmiereffekte → Artefakte• Anwendung der Filter als Vorprozess → unflexibel

• zahlreiche Weiterentwicklungen (z.B. EWA-Splatting, 2004)

29

Zwicker et al.


Shear-Warp

• Entwickelt von Lacroute und Levoy (1994)

• Schnellstes softwarebasiertes DVR-Verfahren

• Prinzip: Transformieren der Volumendaten für einfachen und effizienteren Zugriff entlang der Sehstrahlen

• Unterscheidung bezüglich Parallel- oder Perspektivprojektion:

• Heute jedoch kaum mehr relevant, da Grafikhardware performanter

Shear-Scale-Warp bei perspektivischer Projektion

Shear-Warp bei Parallelprojektion

30


Texturbasierte Verfahren

• Grafikhardware ist optimiert für 2D-Texturen• performantere Texturzugriffe (im Vergleich zu 1D/3D)• außerdem viele parallele Pixelpipelines

• Ausnutzen dieser Performance für DVR • Object-aligned („volumenparallel“)

• drei 2D-Texturstapel im Speicher• Umschalten je nach Blickwinkel

• View-aligned („bildparallel“)• eine 3D-Textur im Speicher• Kein Umschalten, da direkte

trilineare Interpolation

31



• Polygone für Texturen (sog. “proxy geometry“) → Generierung durch Geometry Shader denkbar...

• Heutzutage Einsatz von “view-aligned slicing” üblich• Jede aktuelle Grafikkarte kann 3D-Texturen verarbeiten• Ergebnisse sind besser (kein Umschalten nötig, trilineare Interpolation)• Wesentlich geringerer Grafikspeicherbedarf, da nur ein Texturstapel• Weniger Aufwand seitens der Applikation

• Prinzipieller Ablauf• Generiere am Volumen geclippte Polygone parallel zur Bildebene• Erzeuge 2D-Textur pro Slice mit (hardwarebeschleunigte) trilinearer Interpolation • Rendere Slices (üblicherweise) von hinten nach vorne bei aktiviertem Alphablending

32



• Grundlage bildet die Volumenrendering-Gleichung• Integral wird zur Summe• exponentieller Term wird zu Multiplikation

• Nach entsprechenden Umformungen mit Back-to-front-Alphablending approximierbar durch:

33

Cdst = Csrc �src + (1� �src) Cdst

Ergebnis aktuelle Farbe

aktuelle Opazität

Ergebnis aus vorherigem

Schritt

aktuelle Transparenz


• Sehstrahlen werden durch Bildschirmpixel gesendet unddurch das Volumen verfolgt

• In diskreten Abständen werden die Volumendaten abgetastet→ “Sampling”

• Vergleichbar mit Raytracing, jedoch in der Regel keine Sekundärstrahlen (außer evtl. Schattenfühler)

• Bisher meist nur in Software, dafür sehr hohe Qualität:• artefaktfreie Isoflächen

ohne größeren Aufwand• Volumen ohne Samplingfehler

Raycasting

Sehr wichtig für Einsatzin der Medizin…!


eye

rays

view plane

Figure 5.3: Ray casting. For each pixel, one viewing ray is traced. The ray issampled at discrete positions to evaluate the volume rendering integral.

34


GPU-basiertes Raycasting

• Auf Grafikhardware (bereits ab NV3x!) mittlerweile auch interaktive Geschwindigkeiten• Gleichbleibend hohe Qualität, v.a. im Vergleich zu bisherigen echtzeitfähigen

Verfahren• Flexible Interaktionen und Darstellungen („Intervall-Iso“)• Performancegewinn durch mächtigere Shader möglich

• Sprunganweisungen• Schleifen etc.

• Probleme sind/waren im Wesentlichen:• Fließkommaberechnungen teuer/unvollständig• Begrenzte Shaderlänge/Texturzugriffe• Kontrollstrukturen nicht immer effizient

Ersatz für mehrere Renderpasses

35


Vorgehen GPU-Raycasting

• Rendern des Volumens als Farbwürfel (nur front-faces) in Textur• Generierung von Fragments für das Volumen → Eintrittspunkte der Strahlen

• Korrekte Interpolation der Texturkoordinaten

• Rendern der back-faces des Würfels in Textur• Generierung von Fragments→ Austrittspunkte der Strahlen

• Berechnung der Strahlen im Koordinatensystem des Volumens mittels Fragmentshader

• Abtasten des Volumens als Texturzugriffe an Strahlpositionen

• Aufsummieren und Darstellen der Ergebnisse

and Westermann [5]. Since this algorithm uses the graph-

ics card in a very different way than most games do, there

is often some additional effort required to find the most ef-

ficient solution for a certain task. Still, this approach is far

more flexible and can be extended in a number of ways,

which is what the main part of this paper is about, and this

enables us to utilize the specific advantages a GPU has

over a CPU in the best possible way, namely:

• A massively parallel architecture

• A separation into two distinct units (vertex and frag-ment shader) that can double performance if the

workload can be split

• Incredibly fast memory and memory interface

• Dedicated instructions for graphical tasks

• Vector operations on 4 floats that are as fast as scalaroperations

• Trilinear interpolation is automatically (and ex-

tremely fast) implemented in the 3D-texture

Many more advantages may arise through the specific

nature of a GPU-based algorithm. As we will show in the

next sections, there are a couple of advantages that our

raycasting algorithm has over a similar CPU techniques,

like the possibility of very efficient emtpy-space-skipping

via the outer bounding geometry, the implicit support for

perspective projection or the possibility to intersect our

dataset correctly with normal OpenGL primitives by sim-

ply modifying the z-buffer accordingly.

On the other hand, there are still some disadvantages of

GPU-based raycasting that one should not forget and that

still limit the set of possible applications, the biggest one

being the limitation of available video memory. Though

we can improve on that by applying a sophisticated

caching and blocking scheme like the one presented in sec-

tion 8 (which only stores blocks of interest), the overall

amount of important data we can display is still limited by

the available memory.

In the next section, we will first introduce the basic idea

of hardware raycasting and how the algorithm works. In

section 3 we will extend this technique by adding a more

sophisticated bounding geometry for efficient empty space

skipping. Section 4 deals with Hitpoint Refinement, which

significantly improves quality for iso-surface raycasting

without a noticable speed penalty. Interleaved Sampling

is presented as a solution to heavy sampling artefacts in

Section 5, and in Section 6 we add the possibility to in-

tersect the volume with arbitrary OpenGL geometry. Sec-

tion 7 deals with the problems when trying to fly into the

dataset for virtual endoscopy applications and how this can

be solved. Section 8 shows one approach to circumvent the

biggest drawback hardware-based approaches face: The

limited amount of available video memory. Finally, sec-

tions 9 and 10 show some results we were able to achieve

and give a short outlook into our future work.

2 Algorithm Overview

The basic idea of hardware raycasting, as proposed by

Kruger and Westermann [5], is simple: The dataset is

stored in a 3D-texture, in order to take advantage of the

built-in trilinear filtering. Then, a bounding box for this

dataset is created where the position inside the dataset (i.e.

the texture coordinates) is encoded in the color channel, as

shown in the left picture in figure 1.

Figure 1: Front and back faces of our simple bounding

geometry encoding the current position in the color chan-

nel. Subtracting these two images will yield the viewing

vectors for the raycasting step.

Now the viewing vector at any given pixel can be eas-

ily computed by subtracting the color of the front faces of

the color cube at this pixel (which is the entry point into

the dataset) from the color of the back faces at this pixel

(which is the exit point) as shown in figure 1. Normalizing

and storing this vector in a 2D-texture of the exact size of

the current viewport (together with its initial length in the

alpha channel) yields a ’direction texture’ for every screen

pixel.

Casting through the volume is easy now: Render the

front faces again (the entry points into the dataset) and step

along the viewing vector for this pixel (stored at the same

position in the direction texture) until the ray has left the

bounding box again (i.e. the casted distance is greater than

the alpha value of the texture, where the initial length was

stored). Compositing the final color can be done in a sep-

arate texture, which is blended onto the screen at the very

end.

The fragment shader of a modern GPU is perfectly suit-

able for accomplishing that, since the front faces can be

drawn as normal OpenGL geometry and for every pixel of

the bounding box that will be drawn, the fragment shader

is automatically called with the current color (the start-

ing position) and the current pixel position (for the direc-

tion texture lookup) as input parameters. The possibility

to have loops and conditionals within a fragment shader

(as of shader model 3) makes it possible to cast through

the volume with a single function call.

To sum this all up, the basic hardware raycasting algo-

rithm is a 4-step-process:

and Westermann [5]. Since this algorithm uses the graph-

ics card in a very different way than most games do, there

is often some additional effort required to find the most ef-

ficient solution for a certain task. Still, this approach is far

more flexible and can be extended in a number of ways,

which is what the main part of this paper is about, and this

enables us to utilize the specific advantages a GPU has

over a CPU in the best possible way, namely:

• A massively parallel architecture

• A separation into two distinct units (vertex and frag-ment shader) that can double performance if the

workload can be split

• Incredibly fast memory and memory interface

• Dedicated instructions for graphical tasks

• Vector operations on 4 floats that are as fast as scalaroperations

• Trilinear interpolation is automatically (and ex-

tremely fast) implemented in the 3D-texture

Many more advantages may arise through the specific

nature of a GPU-based algorithm. As we will show in the

next sections, there are a couple of advantages that our

raycasting algorithm has over a similar CPU techniques,

like the possibility of very efficient emtpy-space-skipping

via the outer bounding geometry, the implicit support for

perspective projection or the possibility to intersect our

dataset correctly with normal OpenGL primitives by sim-

ply modifying the z-buffer accordingly.

On the other hand, there are still some disadvantages of

GPU-based raycasting that one should not forget and that

still limit the set of possible applications, the biggest one

being the limitation of available video memory. Though

we can improve on that by applying a sophisticated

caching and blocking scheme like the one presented in sec-

tion 8 (which only stores blocks of interest), the overall

amount of important data we can display is still limited by

the available memory.

In the next section, we will first introduce the basic idea

of hardware raycasting and how the algorithm works. In

section 3 we will extend this technique by adding a more

sophisticated bounding geometry for efficient empty space

skipping. Section 4 deals with Hitpoint Refinement, which

significantly improves quality for iso-surface raycasting

without a noticable speed penalty. Interleaved Sampling

is presented as a solution to heavy sampling artefacts in

Section 5, and in Section 6 we add the possibility to in-

tersect the volume with arbitrary OpenGL geometry. Sec-

tion 7 deals with the problems when trying to fly into the

dataset for virtual endoscopy applications and how this can

be solved. Section 8 shows one approach to circumvent the

biggest drawback hardware-based approaches face: The

limited amount of available video memory. Finally, sec-

tions 9 and 10 show some results we were able to achieve

and give a short outlook into our future work.

2 Algorithm Overview

The basic idea of hardware raycasting, as proposed by

Kruger and Westermann [5], is simple: The dataset is

stored in a 3D-texture, in order to take advantage of the

built-in trilinear filtering. Then, a bounding box for this

dataset is created where the position inside the dataset (i.e.

the texture coordinates) is encoded in the color channel, as

shown in the left picture in figure 1.

Figure 1: Front and back faces of our simple bounding

geometry encoding the current position in the color chan-

nel. Subtracting these two images will yield the viewing

vectors for the raycasting step.

Now the viewing vector at any given pixel can be eas-

ily computed by subtracting the color of the front faces of

the color cube at this pixel (which is the entry point into

the dataset) from the color of the back faces at this pixel

(which is the exit point) as shown in figure 1. Normalizing

and storing this vector in a 2D-texture of the exact size of

the current viewport (together with its initial length in the

alpha channel) yields a ’direction texture’ for every screen

pixel.

Casting through the volume is easy now: Render the

front faces again (the entry points into the dataset) and step

along the viewing vector for this pixel (stored at the same

position in the direction texture) until the ray has left the

bounding box again (i.e. the casted distance is greater than

the alpha value of the texture, where the initial length was

stored). Compositing the final color can be done in a sep-

arate texture, which is blended onto the screen at the very

end.

The fragment shader of a modern GPU is perfectly suit-

able for accomplishing that, since the front faces can be

drawn as normal OpenGL geometry and for every pixel of

the bounding box that will be drawn, the fragment shader

is automatically called with the current color (the start-

ing position) and the current pixel position (for the direc-

tion texture lookup) as input parameters. The possibility

to have loops and conditionals within a fragment shader

(as of shader model 3) makes it possible to cast through

the volume with a single function call.

To sum this all up, the basic hardware raycasting algo-

rithm is a 4-step-process:

36


Optimierungen, z.B.

• Early ray termination• Abbruch, wenn Opazitätsgrenze erreicht (ab NV4x durch Flußkontrolle (break))• Aber nicht ganz unproblematisch: „langsamstes Pixel bestimmt Performance“

(„SIMD-aware Ray-Casting“, Leung et al., Volume Graphics 2006)

• Empty space skipping• Überspringen von leeren Bereichen → nach Anwendung der Transferfunktion• Zusätzliche Datenstruktur (meist Octree) für min/max-Werte

• Adaptive sampling• Homogene Bereiche brauchen nicht so häufig abgetastet werden • Erstellung eines „importance volume“, das die jeweiligen Abstände für das Sampling enthält →

geringere Auflösung

• Insgesamt vergleichbare Performancefortschritte wie bei herkömmlichem Raytracing…

37


Diskussion

• heute praktisch nur noch Raycasting und texturbasiert (view-aligned) relevant

• beide Verfahren profitieren von moderner Grafikhardware:• texturbasiert: schnelle Verarbeitung der Geometrie, Texturierung• Raycasting: flexible Programmierung für Optimierungen

38

✓ einfacher, natürlicher Algorithmus

✓ flexible Steuerung “pro Strahl” möglich

✓ maximale Qualität durch zusätzliche Filter möglich

Raycasting Texturbasiert

Performance von vielen Faktoren abhängig

aufwendige Integration von Geometrien

praktisch nicht abwärtskompatibel (mobile Systeme!)

✗

✗

✗

✓ hohe Performance, abwärtskompatibel

✓ kompatibel mit Multiresolution-Systemen

✓ einfache Integration von beliebigen Geometrien

aufwendigerer Algorithmus/Applikationslogik

begrenzte Qualität

Interaktionsmöglich-keiten von Proxygeometrie abhängig

✗

✗

✗

Visualisierung

Weihnachtliche Datensätze...


Christmas Tree Case Study

• Geschmückter Weihnachtsbaum als CT-Datensatz

• Informationen zu Hintergrund, Anwendungen und Visualisierungen siehehttp://www.cg.tuwien.ac.at/xmas/

40

http://www.cg.tuwien.ac.at/xmas/

http://www.cg.tuwien.ac.at/xmas/


Weihnachtlicher Datensatz in MeVisLab ;)

41


Weihnachtlicher Datensatz in MeVisLab

• Laden eines 3D-Modells eines Rentiers (kostenlos bei Google)

• Polygonales Rendering der Daten• Rasterisierung mit OpenGL (hier: OpenInventor-Szenengraph)• Verschiedene Darstellungsmöglichkeiten (Gittemodell, Normalen etc.)

• Umwandlung in Voxeldaten: “Voxelisierung”• Parameter wie Glättung, “Wandstärke” usw.• Gesamtauflösung durch Bilddatensatz bestimmt• Darstellung der Volumendaten in 2D und 3D

• Rückumwandlung der Voxeldaten in Polygonnetz• Marching Cubes-Verfahren• verschiedene Parameter zur Glättung etc.

42

Konvertierungpraktisch immer mit Verlusten verbunden!

=> Artefakte


Diskussion

• Konsequenzen/Relevanz für medizinische Bildgebung• grundsätzlich immer Diskretisierung• relevante Parameter

• Auflösung (räumlich, zeitlich, Frequenzen usw.)• Signal-Rausch-Abstand

• “Partieller Volumeneffekt” bei Bildgebung besonders zu berücksichtigen• Strukturen/Details werden “vermischt”

• unzureichende Auflösung• Objekte liegen nur teilweise im Strahlengang

• lässt sich prinzipbedingt nicht immer vermeiden• Gefahr: Fehlinterpretation von Bilddaten!

43

Documents

Medizinische Visualisierung - userpages.uni-koblenz.decg/ws1213/medvis/vorlesung/MedVis... · 100 Course 28: Real-Time Volume Graphics w w {{Figure 18.1: The geometric setup for light