Visualisierung, WS 09/10 · Visualisierung, WS 09/10 Prof. Dr. Detlef Krömker 29.01.2010 4 Begriffsbestimmung Volumendaten Begriff Volumendaten in der Literatur nicht einheitlich

Visualisierung, WS 09/10

Prof. Dr. Detlef Krömker

29.01.2010 1

Visualisierung

Volumenvisualisierung


29.01.2010 2

Übersicht

Volumendaten: Grundlagen – Begriffsbestimmung

Visualisierungspipeline für Volumendaten

Methoden der Volumenvisualisierung

� Dekompositionsmethoden

� Extraktion von Flächen

� Direkte Darstellung als semitransparente Elemente

29.01.2010 3

Grundlagen

Visualisierung von Volumendaten� Kurzbezeichnung: Volumenvisualisierung

� Ausgangspunkt: Merkmale in einem 3-dim. Bezugssystem mit skalaren Daten

Vergleichsweise häufiger DatenfallBeispiele:

� Computertomographie (CT)� Magnetresonanztomographie

(NMR, MRT, MRI)� 3D-Ultraschall� Laserraster- bzw.

Elektronenraster-Mikroskope� Simulationen� Berechnungen, z.B. Finite

Elemente (FE)

Beispiel:MRI-Aufnahme

Beispiel:CT-Aufnahme



29.01.2010 4

Begriffsbestimmung Volumendaten

Begriff Volumendaten in der Literatur nicht einheitlich benutzt; doch oft:

� Ein skalarer Wert pro Beobachtungspunkt in einem 3-dimensionalen räumlichen Bezugssystem (oft mit lokalen Wirkungskreis)

� Regelmäßiges 3D-Gitter: Funktion f auf dem Gebiet

betrachtet an (nx+1) * (ny+1) * (nz+1) Gitterpunkten

� Partitionierung mit

� Volumendaten: Daten der Form

},...,0;,...,0;,...,0),,(,,,{( zyxkjikji nknjnizyxfzyx ===

]},[];,[];,[|),,({ maxminmaxminmaxmin zzzyyyxxxzyxXG ∈∈∈==

z

z

i

y

y

i

x

x

i

nin

zzdzdzizz

nin

yydydiyy

nin

xxdxdxixx

,...,0 ;mit *

,...,0 ;mit y *

,...,0 ;mit *

minmaxmin

minmaxmin

minmaxmin

=−

=+=

=−

=+=

=−

=+=

29.01.2010 5

Repräsentation von Volumendaten

Volumendaten i.A. basierend auf regelmäßigen Gittern

� Koordinaten der Gitterpunkte meist implizit (als Index) und nicht explizit gespeichert

� Speicherung in dreidimensionalen Arrays

Ausgangsdaten Datengitter Gitter im Raum

29.01.2010 6

Begriffsbestimmung Voxel

Voxel, Volumenelement� Volumenwert einer Gitterzelle

Häufige Unterscheidung � f(x,y,z) kontinuierlich� f(x,y,z) stückweise konstant

Oft besser als Abtastwert gemäß der Abtasttheorie betrachten!

Beobachtungspunkte können sein:� Zentrum einer Zelle:

1 Datenpunkt pro Zelle

� Eckpunkt einer Zelle: 8 Datenpunkte pro Zelle

� entspricht nur Verschiebung um ½ Voxelbreite in x, y, z

Auswertung im Zentrum des Voxels

Auswertung an Eckpunkten des Voxels



29.01.2010 7

Beispiel: Volumendaten

Visible Human Project

� MRI- und CT-Daten eines Mannes und einer Frau in hoher Auflösung

� 15 GB (Visual Human Male) bzw. 40 GB (Visual Human Female)

http://www.nlm.nih.gov/research/visible/visible_human.html

29.01.2010 8

Beobachtungspunkt Eckpunkt der Zelle

Bestimmung der Werteverteilung innerhalb Zelle � Meist einfach durch trilineare Interpolation � Selten durch Interpolation höherer Ordnung

Trilineare Interpolation� WI Wert am Eckpunkt I = A, …, H mit

� A = (0,0,0), …. H = (1,1,1)

C

G H

D

E F

A B

(0,1,0)

(0,1,1) (1,1,1)

(1,1,0)

(0,0,1) (1,0,1)

(0,0,0) (1,0,0)

P

Wp =WA (1− xp)(1− yp )(1− zp)+WE(1− x p)(1− yp)(zp)+

WB (xp)(1− yp)(1− zp)+WF(xp)(1− yp )(zp )+

WC (1− xp)(yp)(1− zp)+WG(1− xp)(yp )(zp )+

WD(xp)(yp)(1− zp )+WH (xp)(yp)(zp )

Wenn A und H auf beliebigen Koordinaten (xa,ya,za ) liegen,

wird xp durch xp − xaxh − xa

ersetzt, yp,zp entsprechend.

29.01.2010 9

Gradientenberechnung

Für diverse Aufgaben (z.B. Beleuchtungsrechnung) wird der Gradientder skalaren Funktion f(x,y,z) benötigt:

Eigenschaften

� Gradienten stehen senkrecht auf Isoflächen: f(x,y,z) = const.

� I.d.R abgeschätzt durch Zentraldifferenzen:

Richtung-z y-, in x-,ktoren Einheitsve die sind ,, KJImit

Kz

fJ

y

fI

x

ffgrad

rrr

rrr

∂∂

∂∂

∂∂

++=

z

z

y

y

x

x

s

zyxfzyxfG

s

zyxfzyxfG

s

zyxfzyxfG

2

)1,,()1,,(

;2

),1,(),1,(

;2

),,1(),,1(

−−+=

−−+=

−−+=

Gx, Gy, Gz Komponenten des Gradienten,sx, sy, szSchrittweiten des Gitters



29.01.2010 10

Visualisierungspipeline Volumendaten

Filtering Rendering

Mapping

Klassi-fikation

Flächen-extraktion

Volumen-daten

Bild

Visualisierungspipeline für Volumendaten mit zus. Komponenten� Klassifikation von Voxeln� Ggf. Extraktion von Flächenelementen

Herausforderung: Datenumfang in der Regel sehr groß� Datenwürfel von nur 64 x 64 x 64 Voxel entsprechen mit

4Byte/Voxel 1 MByte Daten� 512 x 512 x 512 Voxel entsprechend 512 MByte

29.01.2010 11

Datenaufbereitung: Filtering

Schritte bei der Filterung

� Datenerfassung und -konvertierung in geeignete Formate

� Datenvervollständigung

� Datenreduktion

� Überführung von skalaren Daten in einem räumlichen Bezugssystem auf ein regelmäßiges Gitter

29.01.2010 12

Datenaufbereitung: Mapping

Abbildung der Datenwerte auf graphische (visuelle) Attribute

Klassifikation

� Datenklassen werden Grauwert, Farbwerte oder Transparenzwerte zugeordnet z.B. mit LUTs

� Sehr sensibler Schritt: Potentiell fehlerinduzierend!

� [Drebbin, Levoy] schlagen deshalb Fuzzy-Klassen vor:� Datenwert wird eine Zugehörwahrscheinlichkeit zu einem Attributwert zugeordnet, nicht der Attributwert selbst

Ergebnis kann gerendert werden

� Direkte Darstellung oder

� Flächenextraktion (Ermittlung von Isoflächen)



29.01.2010 13

Strategien zur Volumenvisualisierung

Direkte Darstellung

� Dekomposition der Datenmenge in Punkte, Volumenelemente oder Schichten und Darstellung dieser Elemente

� Darstellung als semitransparente Objekte („Wolken“)

Flächenextraktion

� i.d.R Bestimmung von Isoflächen und Darstellung dieser Flächen

29.01.2010 14

Dekompositionsmethoden

� Einfachste Variante: Darstellung der Gitterpunkte als farbige, ggf. transparente Pixel

� Pro: Einfach, schnell

� Contra: Durch die Winzigkeit der Primitive ist die Interpretation schwierig und eingeschränkt

� Beispiel: Quadermethode

29.01.2010 15

Quadermethode (Tiny Cubes Method)

Ansatz

� Bestimmung eines Quaders für jedes Volumenelement zur Repräsentation

� Darstellung der Quadern mit Abstand M belassen, um ins innere des Volumen schauen zu können



29.01.2010 16


Vorgehensweise� Maße und Positionen (untere linke Ecke) der Quader

bestimmen sich zu:

� Zuordnung von Farbwerten zu Eckpunkten� Gouraud-Schattierung von Quaderflächen

),,( zyx ∆∆∆

MMn

zz

MMn

yy

MMn

xx

z

z

y

y

x

x

−+

−=∆

−+

−=∆

−+

−=∆

)1(

)1(

)1(

minmax

minmax

minmax

zzk

yj

xxi

nkMkzz

njMjyy

niMixx

,...,1 und )1(

,...,1 und )1(

,...,1und)1(

0

y0

0

=+∆+=

=+∆+=

=+∆+=

29.01.2010 17


Großes M Kleineres M� Kleine Quader, hohe Transparenz � größere Quader, geringere Transp.

Beispiel mit 11x11x11 Datenwerten

29.01.2010 18


Achtung Kleine Quader sind sehr anfällig für Aliasingartifakte!



29.01.2010 19

Quadermethode: Alternative

Tetraeder als Primitive Kugeln als PrimitiveNachteil: Induzieren Richtungen

Alternativer Ansatz� Andere Primitive für Zellen statt Quader: Kugeln, Tetraeder

29.01.2010 20

Transparente Quadermethode

Transparente Quadermethode� Vanishing Cube Method� Nielson 90/93, Hamann 91� Rendering der Quader mit transparenten Seiten gerendert

� Aus je vier Gitterpunkte werden semitransparente Polygone

Probleme beim Rendering� z-Buffer Sichtbarkeitsbestimmungnicht anwendbar

� Back-to-Front-Order Ausgabe nötig!

29.01.2010 21

Transparente Quadermethode

Geringe Transparenz Höhere Transparenz

Nielson 1990



29.01.2010 22

Dekomposition in Schichten

Dekomposition in Schichten� Andere Bezeichnung: Slicing� Anstelle der trivariaten Funktion f(x,y,z) Darstellung bivariater

Funktionen der Form

� Schnittebenen: Sweeping Planes� i.d.R. interaktiv festlegbar

Verfahren wird sehr häufig genutztLange Tradition in vielen Anwendungsfeldern

)1(,...,0 mit),,(),(

)1(,...,0 mit ),,(),(

)1(,...,0 mit ),,(),(

+==

+==

+==

zkk

yjj

xii

nkzyxfyxf

njzyxfzxf

nizyxfzyf

29.01.2010 23

Dekomposition in Schichten

29.01.2010 24

Varianten des Slicing

Varianten des Slicing

� Änderung der Anordnung der Schnitt-ebenen

� Zusätzliche Kodierung der Daten in einem Höhenfeld (indirekter Raumbezug)



29.01.2010 25

Extraktion von Flächen

Extraktion von Flächen� Alternativer Ansatz zur Visualisierung von Volumendaten� Bestimmung von Isoflächen (f(x,y,z) = const.) auf Basis konstanter

Bereiche in den Daten (Schwellwerte)� und Darstellung entsprechender geometrischer Modelle

Vorteile� Topologische und geometrische Eigenschaften werden

offensichtlich� Flächeninhalte oder Volumina können einfach abgeschätzt werden

Aber:� Verdeckungen (Occlusion)� Wahl des Schwellwertes (und damit die Segmentierung)

beeinflusst das Ergebnis sehr stark� Sehr leicht können u.U. auch falsche Interpretationen suggeriert

werden!

29.01.2010 26

Extraktion von Flächen: Beispiele

Ebert 2004

29.01.2010 27

Segmentierung und einfache Approximationen

Alternative Vorgehensweisen

� Ein Schwellwert vs. Schwellwertintervall

� 2 Klassen vs. 3 Klassen

3 Klassen

� Klassifizierung in innen - auf - außen

� Alle „auf“-Voxel repräsentieren grobe Approximation der Isofläche

� Problem: numerisch instabil

2 Klassen

� Klassifizierung in innen – außen

� Seitenflächen, die einen „innen“ und einen „außen“ Nachbarn haben, approximieren die Isofläche

� Problem: Voxelstruktur (Blockstruktur) bleibt deutlich sichtbar!



29.01.2010 28

Extraktion von Flächen aus Zellen

Isoflächen verlaufen beliebig innerhalb einer Zelle

Hauptmethoden zur Extraktion von Flächen aus Zellen

� Contouring & Connecting

� Marching Cube

� Dividing Cube

� Marching Tetraeder

29.01.2010 29

Contouring & Connecting

Ansatz � Auf parallelen Schnitten eines

Datenwürfels werden 2D-Isolinien extrahiert� Verfahren hierzu siehe Isoliniendarstellung!

� Benachbarte Ebenen werden durch Dreiecksnetze verbunden

Problem: Mehrdeutigkeit� Bei verschiedenen Kontur-

Topologien auf benachbarten Ebenen ist eine eindeutige Verbindung nicht möglich

29.01.2010 30

Contouring & Connecting

Ansätze zur Lösung des Mehrdeutigkeitsproblems beimContouring & Connecting

� Interaktive Nutzereingabe zur Spezifikation von Konturen, die miteinander verknüpft werden sollen

� Unterteilung der Bereiche mit Mehrdeutigkeiten und Versuch der Problemlösung in abgegrenzten Gebieten

� Verwendung von Kostenfunktionen als Entscheidungsgrundlage

� Einbeziehung weiterer Eigenschaften der Konturen wie Form, Konvexität oder Orientierung



29.01.2010 31

Ablaufschema Contouring & Connecting ( nach Abramowski 1991)

Schritt 1: Konstruktion der konvexen Hüllen der gesuchten Körperscheiben Grund- und Deckfläche der Körperscheiben sind durch die Konturen auf zwei benachbarten Schnitten gegeben. Jede Kontur definiert ein Polygon. Die Punkte zur Spezifikation der Konturen definieren zwei Punktmengen, die Ausgangspunkt für die 2,5D-Delauny-Triangulierung[1] sind. Falls die Konturkanten keine Delaunykanten sind, erfolgt eine rekursive Halbierung dieser Kanten. Die 2,5D-Delauny-Triangulierung liefert die konvexen Hüllen der gesuchten Körperscheiben, bestehend aus benachbarten Tetraedern.

Schritt 2: Elimination überzähliger Tetraeder Da Punktmengen betrachtet werden, können Tetraeder konstruiert werden, die Kanten enthalten, die außerhalb der durch die jeweiligen Konturen definierten Polygone liegen. Diese Tetraeder gehören zwar zur konvexen Hülle der gesuchten Körperscheiben, nicht aber zu der gesuchten Körperscheibe selbst. Auf Grund der gegebenen Orientierung der Konturen ist es aber möglich, solche Kanten zu ermitteln und die entsprechenden Tetraeder zu eliminieren.

Schritt 3: Entfernung nicht solider VerbindungenNicht solide Verbindungen entstehen, wenn zwei benachbarte Tetraeder nur in einer parallelen Ebene auch nur eine Kante oder nur einen Punkt gemeinsam haben. In diesem Fall wurden zwei verschiedene Körperscheiben fälschlicherweise miteinander verbunden und müssen demzufolge wieder getrennt werden (vgl. Abb. 7.9).

[1] Ein Delauny-Dreieck erfüllt bezüglich einer gegebenen Punktmenge die Umkreisbedingung. Das heißt, kein Punkt der Punktmenge liegt innerhalb des Umkreises von . Mit der 2,5D-Delauny-Triangulierung werden Delauny-Triangulierungen auf zwei parallelen Ebenen mit Tetraedern verknüpft. Die Bedingungen, die hierbei an die Tetraeder zu stellen sind, werden in [Abramowski 91b] genau angegeben.

29.01.2010 32

Contouring in 2D

Purpose: construct explicit boundary between regions

Example: topological maps

Algorithm

� Select contour value

� Calculate intersection of points on cell edges

� For edges straddling contour valuedo linear interpolation to find intersection

r = (C - s0)/(s1 - s0)

� Connect intersections

� Edge tracking: track contours across cell boundaries until all crossings used

29.01.2010 33

Example of 2D Contouring



29.01.2010 34

Contouring in 2D (con’t): Marching Squares

Marching Squares: based on topological state

� Look up in case table based on combinations of vertex state

� Merge duplicates (only for marching squares)

29.01.2010 35

Contouring Ambiguity

Single configuration can indicate two different underlying distributions

Two possible actions

29.01.2010 36

Contouring in 3D

Isosurface: surface of constant value

Examples:

� Extent of tumor (or other tissues)

� Region of space exceeding safe toxin level

� Historical approaches: � Find contours in 2D, then connect contours (e.g., lofting)

The isosurface with value 37 at time 60 in a jet shockwave data setThe isosurface with value 37 at time 60 in a jet shockwave data set



29.01.2010 37

Contouring in 3D

Treat volume as a set of 2D slices

� Apply 2D contouring algorithm on each slice.

� Or given as a set of hand-drawn contours

Stitch the slices together.

29.01.2010 38

Contouring in 3D

Find iso-surfaces from 2D contours� Segmentation: find closed contours in 2D slices and represent themas polylines

� Labeling: identify different structures by means of the iso-value of higher order characteristics

� Tracing/Stiching: connect contours representing the same objectfrom adjacent slices and form triangles

� Rendering: display triangles

29.01.2010 39

Contouring in 3D

Issues:� Choose topological or geometrical reconstruction

� Problems:� Sometimes there are many contours in each slice or there is a high

variation between slices

→ Tracing becomes very difficult



29.01.2010 40

2

1

Contour StitchingContour Stitching

29.01.2010 41

Contour Stitching

••Problem:Problem:

Given: 2 twoGiven: 2 two--dimensional dimensional closedclosed curvescurves

Curve #1 has Curve #1 has mm pointspoints

Curve #2 has Curve #2 has nn pointspoints

Which Which point(spoint(s) does vertex ) does vertex ii

on curve one correspond to on curve one correspond to

on curve two?on curve two? ??

i

29.01.2010 42

Surface Fitting Techniques

General method:� Choose an iso-value (arbitrarily or from segmentation)

� Detect all cells the surface is passing through by checking thevertices

� Mark vertices with respect to f(x,y,z)≥/< (+/-) c

� Consider all cells with different signs at vertices

� Place graphical primitives in each marked cell and render thesurface



29.01.2010 43

Ablaufschema Contouring & Connecting ( nach Abramowski 1991)

Nicht solide Verbindungen von Körperscheiben

29.01.2010 44

Marching Cube

Marching Cube Verfahren

� Lorensen und Cline 1987

Ansatz

� Würfel (Quader) wandert im Datenwürfel von Zelle zu Zelle

� Eckpunkte der Zellen werden gemäß der Schwelle klassifiziert (innen –außen)

� Schnittpunkte Isofläche/Würfelkante werden durch lineare Interpolation ermittelt und zu Flächen verbunden

innen

V1 V2 V3 V4 V5 V6 V7 V8

0 0 1 0 0 0 0 0

V1 V2

V3V4

V5 V6

V7V8

außen

außen

außenaußen

außen

außen

außen

29.01.2010 45

Marching Cube

innen

V1 V2 V3 V4 V5 V6 V7 V8

0 0 1 0 0 0 0 0

V1 V2

V3V4

V5 V6

V7V8

außen

außen

außenaußen

außen

außen

außen



29.01.2010 46

Marching Cube

Klassische Fallunterscheidungen beim Marching Cube � Die Bitbelegung im

Klassifizierungsvektor bestimmt das Flächenbild

� 256 mögliche Belegungen mit 15 verschiedenen Topologien

Problem: � Theoretisch nicht ausreichend� Fälle 3, 6, 7, 10, 12, 13 sind nicht

eindeutig

Trotzdem: Für visuelle Auswertungen bei großen Datensätzen ausreichend!

29.01.2010 47

Marching Cube

Lösung des Mehrdeutigkeitsproblems� Beispiel: Fall 3

Problem� 2 Möglichkeiten für die Konstruktion der Kanten

Lösung� Ermittelung eines weiteren Datenpunktes in der Mitte der Fläche durch

Interpolation ermittelt� Klassifikation des neuen Punktes � Lage der Flächen werden eindeutig

?

29.01.2010 48

MC 6: Interp. Triangle Vertex

For each triangle edge, find the vertex location along the edge using linear interpolation of the voxel values

=10=0

T=8T=5

i i+1x

[ ][ ] [ ]

−+

−+=

iviv

ivTix

1



29.01.2010 49

MC: Compute Normals

Calculate the normal at each cube vertex

Gx = Vx-1,y,z - Vx+1,y,z

Gy = Vx,y-1,z - Vx,y+1,z

Gz = Vx,y,z-1 - Vx,y,z+1

Use linear interpolation to compute the polygon vertex normal

29.01.2010 50

MC: Ambiguous Cases

Ambiguous cases:3, 6, 7, 10, 12, 13

Adjacent vertices: different states

Diagonal vertices: same state

Resolution:decide for one case

or

or

29.01.2010 51

Marching Cube

Probleme des Marching Cube Algorithmus

� Bei großvolumigen Daten entstehen sehr viele Dreiecke� Bis zu 5 Dreiecke pro Voxel

� Datensatz von 5123 Voxeln kann mehrere Millionen Dreiecke produzieren! � hoher Speicherbedarf, große Render-Zeiten

Verbesserungen

� Triangle Strips zur Reduktion von Render-Zeiten

� Reduzierung der Anzahl der Dreiecke durch Zusammenfassungen (Simplification) , z.B. des Unterschiedes der Flächennormalen, anhand der Größe der Dreiecke, etc.� Viele verschiedene Algorithmen bekannt: z.B. [Klein, et.al], [Shekar et.al.]



29.01.2010 52

Ablaufschema Marching Cube (I)

Schritt 1: Initialisierung� Festlegung des Schwellwerts s

Schritt 2: Festlegung der aktuellen Zelle

� Festlegung der Position des wandernden Würfels im Datenwürfel� Eckpunkte der aktuellen Zelle V1 bis V8 und die Datenwerte an den

Eckpunkten W1 bis W8

Schritt 3: Klassifikation der Eckpunkte der aktuellen Zelle � Eckpunkt Vi wird genau dann als außen klassifiziert, wenn Wi > s� Anderenfalls Klassifikation als innen

Schritt 4: Belegung eines Index zur Speicherung der Klassifikation� Beschreibung der Klassifikation pro Eckpunkt über Binärcode � Byte wird als Pointer in eine Look-up-Tabelle für jeden Fall die

Identifikatoren der Kanten der aktuellen Zelle, die von der Isofläche geschnitten werden, enthält

29.01.2010 53

Ablaufschema Marching Cube (II)

Schritt 5: Erzeugung einer Kantenliste� Anhand der in Schritt 4 ermittelten Kanten wird eine Kantenliste

erzeugt, die konkrete Angaben zu den von der Isofläche geschnittenen Kanten der aktuellen Zelle enthält

� Kantenliste wird zur Berechnung der Schnittpunkte (Kante -Isofläche) herangezogen

� Wenn die Kantenliste leer ist, wandert der Würfel weiter.Schritt 6: Bestimmung der Dreieckspunkte� Bestimmung der Schnittpunkte der Isofläche mit den Kanten der

aktuellen Zelle durch lineare Interpolation der Datenwerte in den zugehörigen Eckpunkten

� So berechnete Schnittpunkte definieren Eckpunkte der Dreiecke zur Approximation der Isofläche

� Ggf. Behebung von Mehrdeutigkeiten behoben

29.01.2010 54

Ablaufschema Marching Cube (III)

Schritt 7: Zuweisung von Normalen zu Dreieckspunkten

� Ermittlung des Gradienten In jedem Gitterpunkt des Datenwürfels

� Abschätzung der Normalen in den Dreieckspunkten durch lineare Interpolation der Gradienten in den Eckpunkten der aktuellen Zelle

Schritt 8: Speicherung

� Speicherung der Dreiecke und der zugehörigen Normalen zur Beschreibung der Isofläche

Wenn noch nicht alle Zellen betrachtet wurden, Wiederholung der Prozedur ab Schritt 2

Schritt 9: Reduktion der Anzahl der Dreiecke



29.01.2010 55

MC 5: Interpolation ExampleIndex = 10110001

Number of triangles = 4

triangle 1 = e4,e7,e11

triangle 2 = e1, e7, e4



e1e10

e6

e7e11

e4

29.01.2010 56

Another View – Combined Cells

29.01.2010 57

MC Hole Problem Example



29.01.2010 58

Marching Cubes (MC)

Lorensen and Cline ’87

Basic approach: 3D generalization of marching squares

Two main steps:

� Locate the surface corresponding to the user-specified value� Using a divide and conquer strategy

� Generate surface normals

29.01.2010 59

Marching Cubes: Beispiel

Ebert 2004

29.01.2010 60

Marching Cubes – Statement

Extracting an iso-surface from an implicit function, that is,

Extracting a surface from volume data (discrete implicit function),

f (x ,y ,z ) = C



29.01.2010 61

Marching Cubes

Treat each cube individually

� No 2D contour curves

Allow intersections only on the edges or at vertices.

Pre-calculate all of the necessary information to construct a surface

Use table lookup

� Like Marching Squares

29.01.2010 62

The MC-Algorithm

The core algorithm

� Cell consists of 8 voxel values:(i+[01], j+[01], k+[01])

� 1. Consider a Cell

� 2. Classify each vertex as inside or outside

� 3. Build an index

� 4. Get edge list from table[index]

� 5. Interpolate the edge location

� 6. Go to next cell

29.01.2010 63

MC 1: Create a Cube

Consider a Cube defined by eight data values:

(i,j,k) (i+1,j,k)

(i,j+1,k)

(i,j,k+1)

(i,j+1,k+1) (i+1,j+1,k+1)

(i+1,j+1,k)

(i+1,j,k+1)



29.01.2010 64

MC 2: Classify Each Voxel

Classify each voxel according to whether it liesoutside the surface: (value > iso-surface value)

inside the surface:(value <= iso-surface value)

8Iso=7

8

8

55

1010

10

Iso=9

=inside=outside

29.01.2010 65

MC 3: Build An Index

Use the binary labeling of each voxel to create an index

v1 v2

v6

v3v4

v7v8

v5

inside =1outside=0

11110100

00110000

Index:v1 v2 v3 v4 v5 v6 v7 v8

29.01.2010 66

MC 4: Lookup Edge List

For a given index, access an array storing a list of edges

all 256 cases can be derived from 15 base cases



29.01.2010 67

MC Hole Solutions

Tessellate cubes w/ tetrahedron and compute marching tetrahedron

� No ambiguities

� LOTS of polygons� Orientation of tetrahedron affects contour

location

Asymptotic decider -- Nielson and Hamann ’91� Analyze bilinear variation over

face to choose patches

Add complementary cases� Use when necessary

29.01.2010 68

Asymptotic Decider

Assume bilinear interpolation within a face

Hence iso-surface is a hyperbola

Compute the point p where the asymptotes meet

Sign of S(p) decides the connectivity

asymptotes

hyperbolas

p

29.01.2010 Prof. Dr. Wolfgang Müller, HS Anhalt 69

Summary of Algorithm

� Read 4 slices of data

� Scan 2, creating cubes

� For each cube, determine triangle table index to find triangulation of the cube surface intersection

� Find exact intersections using linear interpolation

� Create vertex normal vectors using gradient

� Output triangles and normals



29.01.2010 70

Marching Cubes - Summary 1

256 Cases

reduce to 15 cases by symmetry

Complementary cases - (swap in- and outside)

Ambiguity resides in cases 3, 6, 7, 10, 12, 13

Causes holes if arbitrary choices are made.

29.01.2010 71

Marching Cubes - Summary 2

Up to 5 triangles per cube

Dataset of 5123 voxels can result in several million triangles (many Mbytes!!!)

Iso-surface does not represent an object!!!

No depth information

Semi-transparent representation --> sorting

Optimization:

� Reuse intermediate results

� Prevent vertex replication

� Mesh simplification

29.01.2010 72

MC Examples

1 Iso-surface

2 Iso-surfaces

3 Iso-surfaces



29.01.2010 73

MC Extensions

Higher order surfaces

� Use parametric cubics instead of polygons

� Particularly useful for large or irregular grids

� Use gradients to get curvature

Adaptive subdivision

� Estimate error based on gradient

� Subdivide mesh adaptively

29.01.2010 74

Dividing Cube

Dividing Cube Verfahren� Levoy 1990� Alternatives Verfahren zu Marching Cube

Ansatz: Erzeugung von Oberflächenpunkten anstelle von Dreiecken� Klassifizierung von Zellen in „innen“ – „außen“ – „Oberfläche“

� Innen-Zelle: Alle in der Zelle präsenten Datenwerte sind kleiner als der gegebene Schwellwert

� Außen-Zelle: Alle in der Zelle präsenten Datenwerte sind größer als der gegebene Schwellwert

� Oberflächenzelle: Die durch den Schwellwert spezifizierte Isofläche schneidet die Zelle

� Rekursive Unterteilung von Oberflächenzellen und erneute Klassifikation (Ermittlung neuer Datenpunkte durch trilineare Interpolation)

� Oberflächenzellen nach dem letzten Unterteilungsschritt werden als Oberflächenpunkte aufgefasst� Berechnung von Normalen (z.B. durch Zentraldifferenzen)

29.01.2010 75

Dividing Cube

Vorteile� Entstehende Punkt-Informationen können effizient unter

Verwendung heutiger Graphik-Hardware gerendert werden� Keine Scan-Konvertierung des Volumens� Stattdessen: Projektion von Pixel-grossen Punkten� Aktueller Bezug zu anderen Punktbasierten Techniken

� “Points as Display Primitives” (Levoy & Whitted)� Splatting Techniken (Westover, etc.)� Surfels (Pfister & Gross)� Andere punkt-basierte Rendering Techniken (OpenGL)

� Keine störenden Artefakte aufgrund mangelnder Auflösung von Dreiecken

� Geringerer Aufwand als bei komplexer Klassifikation mit MarchingCube Verfahren



29.01.2010 76

Dividing Cubes (Cline et. al 1988)

Motivation: Marching Cubes generates a large number of very small polygons, which take a long time to render

Subdivide voxel into a x b x c cubes that are the size of a pixel if:

� The voxel intersects the surface

Render these as points

29.01.2010 77

Dividing Cubes

� Choose a cube

� Classify, whether an iso-surface is passing

through it or not

� If (surface is passing through)

� Recursively subdivide cube until pixel size

� Compute normals at each corner

� Render shaded points with averaged normal

29.01.2010 78

Advantages of Dividing Cubes

No scan-conversion needed

� Simple projection of pixel-sized points

� Similarity to:� “Points as Display Primitives” (Levoy & Whitted)

� splatting techniques (Westover, others)

� Surfels (Pfister & Gross)

� other point-based rendering techniques (OpenGL)

No triangle resolution artifacts



29.01.2010 79

Vergleich Marching Cube und Dividing Cube

Vergleich unter dem Aspekt des Rendering

Dividing Cubes

� (+) Point Shading Hardware inzwischen von OpenGL unterstützt

� (-) Adaptive Subdivision langsam

Marching Cubes

� (+) Gut bei Hardware-unterstütztem Polygon-Rendering� Graphikkarten-Entwicklung in diesem Bereich getrieben durch

Computerspiele-Sektor

� Preiswerte Graphik-Hardware verfügbar

� (-) Erzeugt ggf. mehrere Millionen Polygone� Verfahren zur Polygon Simplification notwendig

29.01.2010 80

Ansatz:

� Anstelle eines Würfels wandert ein Tetraeder durch den Datensatz

Vorteile

� Nur drei Fälle müssen unterschieden werden

� Max. zwei Dreiecke/Tetraeder

� Keine Mehrdeutigkeiten

Nachteile

� Resampling auf Tetraedergitter nötig

� Manchmal, z.B. bei Berechnungen/Simulationen lassen sich die Beobachtungspunkte frei wählen

Marching Tetraeder

29.01.2010 81

Zusammenfassung Flächenextraktion

Unterstützt insbesondere die Analyse geometrischer und topologischer Eigenschaften

Isoflächen lassen sich mit Standard-Graphikbibliotheken effektiv unterstützen

Isoflächen lassen sich mit an-deren Objekten gemeinsam darstellen

Extraktion ist ein vergleichsweise aufwendiger Prozess

Festlegung der Schwelle sehr sensible EntscheidungZellkern



29.01.2010 82

Volume Rendering

Volume Rendering� Direkte Darstellung als semitransparente Elemente

� Abbildung von Datenwerten auf Transparenz und Farbe

� Kontinuierliche Darstellung der Datenwerte, einschließlich verschwommener Grenzen

� Darstellung des gesamten Datensatzes� Techniken

� Volume Tracing� Shear-Warp factorization� Splatting� Hardware Texturing

29.01.2010 83

Volume Rendering

Bildebene mit x*y Pixeln

Datenwürfel mit N*N*N Volumenelementen

Volumenelement V(i, j, k)

Strahl

Pixel (x, y)mit Farbe Cx,y

29.01.2010 Prof. Dr. Wolfgang Müller, HS Anhalt 84

Volume Rendering

Grundsätzliche Ansätze:

Bildraumverfahren (Volume Ray Casting)

FOR each pixel on image plane DOFOR each sampling point on associated ray DO

compute contribution to pixel;

Objektraumverfahren

FOR each volume element DOFOR each pixel projected onto DO

compute contribution to pixel;



29.01.2010 85

Volume Ray Casting

Transferfunktion zur Beschreibung des Anteils, den ein Volumes an einem Pixel hat� Transferfunktion definiert Abbildung von Datenwerten auf

Präsentationsparameter (Farben, Grauwerte, Transparenz)� Bestimmt Sichtbarkeit und Erkennbarkeit von Strukturen

Typische Transferfunktionen� Fensterung� Bi- bzw. Trilevel-Fensterung� Inverse Fensterung� Stückweise lineare Funktionen� Polynome höheren Grades bzw. Splines

Problem: kein erkennbarer Bezug zwischen Eigenschaften der Transferfunktion und der Visualisierung

29.01.2010 86

Volume Ray Casting: Transferfunktionen

Summation aller Intensitäten Maximale Intensität

Gewichtetes Blending (Opacity) Gewichtetes Blending (Opacity mit Shading)

Mroz,vrvis 2001

29.01.2010 87

Volume Ray Casting: Transferfunktionen

gradientenabhängige Transferfunktion am Beispiel des Visible Man CT-Datensatzes (Preim 2001, nach Levoy 1988)



29.01.2010 88

Volume Ray Casting und Texturing (I)

Ansatz� Nutzung der Texture Mapping-Funktionen heutiger

Graphikhardware zur Beschleunigung des Volume Ray CastingIdee� Parallelisierung der Strahlverfolgung

Aspekte der Hardware� Texture-Engines mit Möglichkeit zur Speicherung

dreidimensionaler Textur-Volumen� Hardware-unterstützte Extraktion beliebiger Schnitte unter

Verwendung von trilinearer Interpolation� Hardware-unterstützte Berechnung von Reflexionen

Vorgehensweise� Sampling des Volumes durch Berechnung von Schnitten parallel

zur Bildebene� Überlagerung der Schnitte zur Berechnung des Bildes

29.01.2010 89

Volume Ray Casting und Texturing (II)

29.01.2010 90

Volumenvisualisierung: Objektraumverfahren

Typen von Objektraumverfahren

� Splatting

� Shear-Warp-Techniken



29.01.2010 91

Objektraumverfahren: Splatting

Westover 1990� Idee: Werfen eines Scheeballs auf eine Glasplatte, bei der die

Verteilung des Schnees mit Entfernung von Zielpunkt abnimmt� Voxel des Datenvolumens werden von vorne (aus Sicht des

Betrachters) nach hinten durchlaufen� Projektion jedes Voxel auf Bildschirmebene

� Verteilung der Bildanteile auf Pixel unter Verwendung einer Filtermaske (Reconstruction Kernel, typischerweise Gauss)

� Footprint: Projektion des Reconstruction Kernel auf Bildebene� Größe der Projektionsfläche proportional zu Volumen- und Bildgröße

Aspekte des Splatting� Qualitativ gute Bilder� GGf. Glättung zur Vermeidung

von Löchern bei Vorwärtsprojektionder Voxel auf Bildebene� Nachteil: Verwischungseffekte

29.01.2010 92

Objektraumverfahren: Shear-Warp-Technik

Shear-Warp (Lacroute 1995) � Vermeidung komplexer Projektionsberechnung durch Zerlegung der

Rotation in 3D-Scherung und Verzerrung des Ergebnisbildes� Erweiterungen zur Perspektivprojektion und freier Wahl der

Beobachterposition möglichAspekte� Schnellstes Verfahren in Software� Durch Verzerrungen auf Bildebene ggf. schlechtere Qualität

29.01.2010 93

Shear Warp Techniken

Approaches which utilize shear/warp-based projection (like the one presented in this work) are the fastest software-based methods for volume rendering. The usually quite costly process of transforming data from the volume coordinate system into image coordinates for projection is split into two shears along axes of the volume (plus a scaling operation if perspective projection is performed), and a 2D warp operation. The data is sheared and projected onto one of the faces of the volume (base plane, a plane which is normal to an axis of the volume coordinate system). The cheap shear-based projection is performed for all voxels of the volume, creating a distorted version of the rendered image. The warp (which can be, for example, efficiently done by texture mapping hardware) transforms the base plane image into the final image (see figureﾊ2.2).



29.01.2010 94

Shear Warp Techniken

Lacroute [1995]

29.01.2010 95

Vergleich Flächenextraktion vs. Volume Rendering

Flächenextraktion

� Darstellung eines Subsets der Daten mittels Flächenelementen

Aspekte

� Bei Verwendung mehrerer unterschiedlicher Isoflächen ggf. Verständnisprobleme

� Verdeckungen (Occlusion)

� Interaktive Rendering-Raten auf Low-Cost PCs möglich

Volume Rendering

� Darstellung aller selektierten Daten

Aspekte

� “Echtere” Darstellung von Volumendaten

� Transferfunktions ggf. schwierig zu designen

� Interaktive Rendering-Raten schwer zu erreichen

29.01.2010 96

Common Issues for All Types of Visualization Techniques

Accuracy of results

Accurate sampling

Hidden surface removal / rendering

Shading and illumination

Perception of information

User interaction



29.01.2010 97

Hierarchische Datenstrukturen

Spezielle Datenstrukturen können den Zugriff und die Analyse von 3D-Daten unterstützen und beschleunigen

� Octree

� B-Tree

� K-D-Tree

29.01.2010 98

Zusammenfassung

Volumenvisualisierung

� Flächenrekonstruktion (z.B. Marching Cubes)

� Direktes Volumenrendering (z.B. Splatting)

Beide Verfahren mit spezifischen Vor- und Nachteilen

Zentrale Probleme

� Große Datenmengen

� Hohe Renderingzeiten

Viele technische Ansätze zur Beschleunigung der Verfahren

29.01.2010 99

Hausaufgabe

Schumann, Müller: Kap. 7.2, 7.3, 7.4, 7.5



29.01.2010 100

Danksagung

Diese Vorlesung basiert auf Material von

� Prof. Dr. Wolfgang Müller

� Prof. Dr. Colin Ware

� Prof. Dr. Ralf Dörner

� Prof. David Ebert, PhD

Documents

Visualisierung, WS 09/10 · Visualisierung, WS 09/10 Prof. Dr. Detlef Krömker 29.01.2010 4 Begriffsbestimmung Volumendaten Begriff Volumendaten in der Literatur nicht einheitlich