Null

(19) Visualisierung und Volumenrendering I

Einführung

Computergrafik 3, SS 08 Matthias Raspe

Wissenschaftliche Visualisierung

Wissenschaftliche Visualisierung

• 1987 geprägter Begriff von McGormick et al. • •

Darstellung von Unmengen (simulierter) Zahlenwerte aus „wissenschaftlichem Rechnen“ Computergrafik für Darstellung, da Daten meist geometrische Bedeutung haben

• Computer als „Intelligenz-Verstärker“ (Ashby, 1956!)

• •

Daten nicht nur visualisieren, sondern mit ihnen interagieren Schnittstelle zur Informationsvisualisierung

• •

Mensch-Maschine-Kommunikation Softwareergonomie

M. Raspe

27. Juni 2008

3 / 35

M. Raspe

27. Juni 2008

Volumenrendering • Modelle wurden bisher nur durch ihre Oberfläche beschrieben

• Zusätzlich sorgen verschiedene Techniken für eine anwendungsgemäße Darstellung

• (Eckpunkt-)Farben • Beleuchtungsverfahren • Texturen • Allgemein: Shader

OsiriX Kratz et al.

• Oft wird aber auch Information aus „dem Inneren“ benötigt, v.a. in der Medizin…

M. Raspe

27. Juni 2008

5 / 35

Kniss et al.

4 / 35

Volumenrendering

Volumenrendering

• Volumengrafik stellt jedoch sehr hohe Ansprüche

• Beispiel 2: 4D-Kardio-CT

• Datentiefe: 16 Bit (12 Bit Nutzdaten) • Auflösung pro Bild: 512 x 512 • insgesamt 250 Slices • 25 Zeitschritte

an die Hard- und Software aufgrund der hohen Datenmengen • Beispiel 1: Abdomen-CT-Scan

• Datentiefe: 16 Bit (12 Bit Nutzdaten) • Auflösung pro Bild: 512 x 512 • Insgesamt 800 Schnittbilder („slices“)

! mehr als 3 GB...

OsiriX

• Relevante Faktoren:

• Datentransfer ! z.B. PCIe 16x hat 4 GB/sec… als

mit 0.5 mm Abstand

theoretisches Maximum!

• Grafikspeicher ! Consumer-Grafikkarten bis zu 1 GB • allg. Speichergeschwindigkeit ! Caches, RAM, HD

! 400 MB… Cascada M. Raspe

27. Juni 2008

M. Raspe

7 / 35

27. Juni 2008

8 / 35

Visualisierung und Volumenrendering • Themen der folgenden Veranstaltungen: • Grundlegende Konzepte und Algorithmen • Möglichkeiten zur Visualisierung • GPGPU

Grundlagen

• Der Schwerpunkt liegt auf Volumenrendering: • Modelle und Konzepte

• Volumenintegral • Volumenrendering-Pipeline

• Verschiedene (echtzeitfähige) Direkt-Renderingverfahren • softwarebasiert • hardwarebasiert

• Überblick zu Systemen und weiteren Forschungsgebieten M. Raspe

9 / 35

27. Juni 2008

Volumenrendering-Pipeline

Datenstrukturen • Bisher geometrische Oberflächen:

Akquisition der Daten Bildgebende Verfahren (z.B. CT, MR), Simulationen

Externe Systeme Applikation/Hardware

Transferfunktion Sampling

Filterung

Klassifikation

Shading

Anzahl/Abstand der Slices oder Samples entlang Sehstrahl

Interpolation der vorhandenen Daten für Samples

Zuweisung von Farbe und Opazität/ Transparenz

Auswertung von Beleuchtungsmodellen

Compositing Integration zu Endbild

Darstellung

M. Raspe

27. Juni 2008

11 / 35

• •

Dreiecksnetze, mit/ohne Topologie Parametrische Flächen (Bézier, NURBS etc.)

• •

Punkte(wolken) Volumenelemente

• Oberflächen reichen nicht, daher:

• Zusätzlich sind den Elementen meist Attribute zugeordnet:

• •

Skalare (z.B. Temperatur, Druck, Gewebedichte) Vektoren (z.B. Geschwindigkeit, Gradienten, DTI (7D!))

M. Raspe

27. Juni 2008

12 / 35

Topologien

Räumliche Struktur 2D • Ein zweidimensionales Datenfeld kann logisch strukturiert werden:

Kartesisch (cartesian)

Strukturiert (structured/regular)

Gleichmäßig (regular/uniform)

Rechtwinklig (rectilinear/uniform)

Unstrukturiert (unstructured/regular)

Gestreut (scattered)

M. Raspe

27. Juni 2008

• als Zellen mit den Werten in der Mitte ! „Pixel“ • als Gitternetz mit Werten an den Knoten

M. Raspe

13 / 35

Räumliche Struktur 3D

Räumliche Struktur

• Analog für den dreidimensionalen Raum

• •

• •

Würfel/Zelle mit Werten im Zentrum ! „Voxel“ * Zelle mit Werten an den Knoten ! Voxelzelle/-gitter

• • •

27. Juni 2008

14 / 35

Üblich: Werte in Zellen (Pixel/Voxel) einige Algorithmen verwenden Gitter, z.B.

• •

Marching Cubes/Squares Graph-Cut Verfahren

Einfache Konvertierung, da nur „logische Definition“ Im folgenden wird von Pixeln/Voxeln ausgegangen, sofern nicht ausdrücklich erwähnt Andere Repräsentationen (z.B. hexagonal) werden hier nicht berücksichtigt, da keine Verwendung/Vorteile in der Computergrafik...

*) abgeleitet von „volume element“, in Analogie zu Pixel = „picture element“

M. Raspe

27. Juni 2008

15 / 35

M. Raspe

27. Juni 2008

16 / 35

Darstellung der Daten •

Darstellung der skalaren Werte in Farben üblicherweise mit Hilfe von Farbtabellen („color maps“)

•

Transferfunktionen

Realisierung als einfache Lookup-Tabelle 9.78 9.65 9.22 8.79 8.68 … … … 3.01 2.32 1.92

•

11.23 10.11 9.78 9.65 9.22 8.79 8.68 … … … 3.01 2.32 1.92 1.01 0.78

Werte werden „geclamped“

Werte werden „geclamped“

Direkt in Hardware verfügbar:

• •

glColorTableEXT ! als Palette in fixed-function-pipeline glTexImage1D ! als Textur, z.B. für eigene Shader

M. Raspe

27. Juni 2008

18 / 35

Transferfunktionen • • •

• Genauer:

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 f : R → R Skalare in RGB-Farben f : R → R3 Richtungsvektoren in RGB-Farben f

• Die Transferfunktion (TF) ist aus mathematischer Sicht eine Funktion und keine Relation

• Je nach Dimension der Wertemenge können aber mehrere Ausgabewerte einem Eingabewert zugeordnet sein

• Beispiele: Helligkeit

•

Transferfunktionen

: R3 → R3

Skalar

Kontinuierliche TF

M. Raspe

27. Juni 2008

Diskrete, abschnittsweise definierte TF

Keine gültige TF, da Relation

M. Raspe

19 / 35

Transferfunktionen

Transferfunktionen

•

•

• • • •

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

• •

•

Cascada: 2D-TF

große Datenmengen Kontrolle/User-Interface?

27. Juni 2008

20 / 35

Es existieren sehr viele unterschiedliche Ansätze, jedoch keine universelle Lösung

• Cascada: 1D-TF

Kontinuierliche TF für RGB-Kanäle

•

„High-Level User Interfaces for Transfer Function Design with Semantics“, Rezk-Salama et al., 2006 Transfer Functions „The Transfer Function Bake-Off“, Pfister et al., 2001

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

Siemens Medical Inc.

Figure 3.9: Transfer Functions in syngo

M. Raspe

27. Juni 2008

22 / 35

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.

3D Visualization and Image Processing

Zusammenfassung TF • Transferfunktionen weisen Volumendaten optische Eigenschaften zu, zum Beispiel:

• •

Dichtewert ! Opazität Windrichtung ! RGB-Wert

Indirekte Verfahren

• 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

M. Raspe

27. Juni 2008

23 / 35

30

Darstellung II

Darstellung II

• Eine andere Form der

•

dargestellt werden, z.B.

• Isolinien für bestimmte Höhen eines Geländes • Farbe/Sättigung für Vorzeichen/Betrag des Gradienten

Isolinien (auch „Höhenlinien“, Konturlinien) Isoflächen (Konturflächen)

• Steile Anstiege ! intensives Rot • Flache Gefälle ! leichtes Blau

• In dieser Form gehören sie zu •

CHAPTER 5. NON-PHOTOREALISTIC VOLU

concept of deferred computations is that it reduces their complexity fr to object space, e.g., the number of voxels in a volume, to the complex the number of pixels in the final output image. Naturally, these compu to shading equations per se, but can also include the derivation of addi is only needed for visible pixels and may be required as input for shadi surface properties. In this section, we describe deferred shading computations for re volumetric data. The computations that are deferred to image space ar shading, but also include the derivation of differential implicit surface gradient (first order partial derivatives), the Hessian matrix (second ord and principal curvature information. Figure 5.5 illustrates a pipeline for deferred shading of isosurface figure 5.6 shows example images corresponding to the output of specific passes. The input to the pipeline is a single floating point image storin tion positions of the viewing rays and the isosurface. This image is obt the volume, or first hit ray casting, as outlined above and illustrated i From this intersection position image, differential isosurface propert and additional partial derivatives such as the Hessian matrix can be

• Diese können mit weiteren Attributen erweitert

Visualisierung ist die Hervorhebung gleicher Werte mit geometrischen Primitiven

•

106

• Isolinien und vor allem Iso-

den indirekten Visualisierungsmethoden Als direkte Methode im Zusammenhang mit Volumenrendering ! später…

flächen spielen in vielen Anwendungsgebieten eine sehr große Rolle

M. Raspe

27. Juni 2008

M. Raspe

25 / 35

27. Juni 2008

26 / 35

Figure 5.6: Example image space rendering passes of deferred isosur properties such as (a) the gradient (here color-coded in RGB), (b) prin tudes (here: κ1 ), and (c) principal curvature directions can be reconstru can be used in shading passes, e.g., (d) Blinn-Phong shading, (e) col ! measures (here: κ21 + κ22 [70]), and (f) advection of flow along principa

Exkurs: Gradient

Marching Cubes

• Beim bisherigen (Oberflächen-)Rendering waren die Normalen • •

gegeben oder konnten berechnet werden Für Volumendaten (genauer: 3D-Skalarfelder) gibt es jedoch keine Normalen im eigentlichen Sinn... Guter Ersatz: der Gradientenvektor

generiert werden?

• Marching Cubes (Lorensen et al., 1987)

• Übliches Verfahren zur Konstruktion von Isoflächen aus 3D-

• entspricht der Normale auf Isofläche • analog zu Gradient in Bildverarbeitung (vgl. Kantendetektion)

Skalarfeldern (d.h. Volumen)

• Auch allgemein definiert auf anderen Daten • Bei höherdimensionalen Daten (Vektorfelder etc.) wird eine

• Der Gradientenvektor ∇f ist die erste Ableitung eines 3DSkalarfeldes f (x, y, z) , d.h ∇f = (fx , fy , fz ) =

!

∂f ∂f ∂f , , ∂x ∂y ∂z

"

||∇f || =

• Wie können Isoflächen automatisch aus Volumendaten

entsprechende Ordnungsrelation benötigt, z.B.

• Betrag des Vektors • Gradient (auch bei Skalaren)

! fx 2 + fy 2 + fz 2

• Wird oft durch Zentraldifferenzen berechnet, z.B. in x-Richtung:

• Zunächst im 2D: Marching Squares

fx (x, y, z) = f (x + 1, y, z) − f (x − 1, y, z) mit x, y, z ∈ N M. Raspe

Marching Squares

Marching Squares

• Ausgangsdaten: Skalare an Gitterpunkten • Annahmen:

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

• Isowert wird höchstens einmal zwischen zwei Gitterpunkten

• Ergebnis ähnlich zu Kanten-

angenommen ! ausreichend hohe Auflösung

• Werte (und damit die Konturen) verlaufen linear

detektion, aber: Kante ! Isolinie

• Vorgehen:

• Bestimme für jeden Gitterpunkt, ob er innerhalb/außerhalb • • •

liegt ! Bitcode Ermittle beteiligte Kante aus unterschiedlichen Bitcodes Bestimme Punkt auf dieser Kante durch lineare Interpolation Verbindung dieser Punkte zu Linien

2

4

4

6

4

1

2

4

6

4

2

2

2

5

6

4

2

2

4

6

6

4

2

5

6

5

4

2

1

4

4

3

2

1

0

: ! C („innerhalb“)

M. Raspe

28 / 35

27. Juni 2008

27. Juni 2008

29 / 35

M. Raspe

:

1

> C („außerhalb“)

27. Juni 2008

30 / 35

Marching Squares

Marching Cubes

• Betrachtet man sich eine Gitterzelle genauer, gibt es nur eine

• Die Erweiterung des Marching Squares Ansatzes

begrenzte Zahl von Kombinationen, wie die Linie grundsätzlich verlaufen kann

•

führt zu Marching Cubes

• Prinzipiell gleicher Ablauf • Statt (Iso-)Linien werden Isoflächen erzeugt

Insgesamt 24 = 16 Möglichkeiten:

• Ausgangsdaten sind hier wieder Skalare in einer regulären Gitterstruktur (Voxelzelle)

• Anzahl läßt sich deutlich reduzieren:

• Durch Komplementbildung ! 8 Möglichkeiten • Durch Rotation und Symmetrie ! 4 Möglichkeiten

• Es gibt aber dennoch eine Mehrdeutigkeit… M. Raspe

27. Juni 2008

Marching Cubes

32 / 35

• Allgemeines Vorgehen bei Marching Cubes:

• Betrachtung von Würfeln aus je 4 Voxeln der Schicht k und k+1 • Bestimmung der Codes für Eckpunkte (innerhalb/außerhalb) • Ermittlung der beteiligten Kanten • Ermittlung von Punkten auf diesen Kanten durch lineare Interpolation • Verbindung der Punkte zu Dreiecken

Voxelzelle insgesamt 2 = 256

• Durch Anwendung der gleichen Prinzipien (Komplement,

•

27. Juni 2008

Marching Cubes

Kombinationen beträgt in einer • Die Anzahl der möglichen 8

•

M. Raspe

31 / 35

Symmetrie) lassen sich die Fälle auf die folgenden 15 Kombinationen reduzieren: Auch hier gibt es Mehrdeutigkeiten, die sich jedoch teilweise nicht auflösen lassen ! Löcher in Isofläche… Mögliche Lösungen

• Zusätzlich:

• Zusammenfassung der Dreiecke/Dreiecksnetze zu möglichst effizienten Meshes (Triangle Strips usw.)

• Bestimmung von Gradienten, z.B. für Shading • Speicherung der Vektoren in Textur (RGB+A) • exakter, aber teurer: on-the-fly Berechnung

Loch in

• Zusätzliche Komplemente Isofläche • Gradienten berücksichtigen • Alternative Verfahren (z.B. Marching Tetraeder, Shirley et al, 1990) M. Raspe

27. Juni 2008

33 / 35

Zusammenfassung MC • Marching Cubes als Methode zur Generierung von Isoflächen aus einem Voxelgitter

• Mehrdeutigkeiten, begrenzte Anzahl von Kombinationen ! Optimierung möglich:

• Bitcodes • Lookup-Tabelle

• Benötigt jedoch hohe Auflösung

des Gitternetzes für ausreichende Qualität

• Problematisch wegen erhöhter Datenmenge und Laufzeit

• Ideal: adaptive Verfahren

M. Raspe

27. Juni 2008

35 / 35

M. Raspe

27. Juni 2008

34 / 35