Prof. Dr.-Ing. Detlef Krömker
Goethe-Universität, FrankfurtGraphische Datenverarbeitung
Graphische Datenverarbeitung
Klipping und Visibilitätsrechnung
SS 20062Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Die klassischeAusgabepipelineModel-Transformation in WeltkoordinatenView Transormation in normalisierten Koordinaten, z.B. [0,1] Projektion 3D 2D
Model and ViewTransformation
Beleuchtungs-rechnung für Vertices
Projektion
Klipping
Screen Mapping
Rastern(Scan Konvertierung)
Geo
met
risch
e B
erec
hnun
gen:
~ #
Pun
kte
Ras
tern
~# P
ixel
1
2
3
4
2a
( )
Heute:• Klipping (Clipping)• Screen Mapping• Visibilitätsrechnungan verschiedenen Stellen in derPipeline möglich, je nach Algorithmus
SS 20063Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Übersicht
1. Windowing und Klipping2. Klipping in 2D
Linien am HalbraumCohen SutherlandPolygone: Sutherland Hodgeman
3. Klipping in 3DPrinzipIn Homogenen Koordinaten
SS 20064Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Übersicht
4. Einführung VisibilitätsrechnungErster Schritt: back-face culling
5. Painters Algorithmus6. Punktorientierte Verfahren
z-Buffer Algorithmus7. Linienorientierte Verfahren
Watkins AlgorithmusAppels Algorithmus
8. Flächenorientierte VerfahrenWarnocks Algorithmus
SS 20065Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Ausschnittsbildung (Windowing und Klipping)
Um von der gesamten vorhandenen Bildinformation nur einen Ausschnitt darzustellen wird ein üblicherweise rechteckiges Fenster (Window )definiert, dessen Ränder den interessierenden Bildausschnitt begrenzen.
Um ein fehlerfreies Bild zu erhalten, muss die außerhalb des Fensters liegende Bildinformation vor der Bildausgabe abgeschnitten werden (Clipping = Klippen).
In der Regel wird das Fenster in Weltkoordinaten spezifiziert und mit “World-coordinate-window“ oder einfach ''Window'' bezeichnet.
Das „Window“ in der virtuellen Welt! (Sutherland)
SS 20066Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
ViewportBildschirm ist in verschiedene Darstellungs-flächen (Viewports ) augefteilt.
Ohne Clipping würden die Inhalte der einzelnenViewports sich gegenseitig beeinflussen, also falsche Bilder erzeugen
Auf dem Bildschirm wird als Koordinatensystem das Bildschirmkoordintensystem verwendet und das Ausgabefenster (Window) in diesem ausgegeben und Viewport genannt.
Die Transformation zwischen dem Weltkoordinatensystem und dem Bildschirmkoordinatensystem heißt Window-Viewport-Transformation(Screen Mapping).
SS 20067Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Clipping von LiniensegmentenBeim Clipping von Liniensegmenten an einem rechteckigen Fenster (allgemeiner:an einem konvexen Objekt) entsteht entweder kein oder (bei Unterteilung einer Geraden in sichtbare und unsichtbare Teile) ein sichtbarer Teil.
Vektoren, deren beide Endpunkte oberhalb, unterhalb, rechts oder links desFensters liegen, sind völlig unsichtbar.
Können diese Vektoren einfach aussortiertwerden, so ist eine erhebliche Beschleunigung des Clipping zu erwarten.
Der Cohen-Sutherland-Algorithmus (später) nutzt diese Eigenschaft.
SS 20068Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Clipping von Liniensegmenten am Halbraum: Vorbereitung
Jede (Fenster)-Kante wird als implizite Gerade dargestellt:
-Q1
Q2
+Q x y Q x yn y x y y x xP x yE P n P n Q
1 1 1 2 2 2
2 1 2 1
1
= == − = − − −=
= −
( , ), ( , ),( , ) ( , ( ))( , )
( ) * *
Δ Δn
Jedes Liniensegment wird parametrisch dargestellt:
l t P t P P( ) ( )= + −1 2 1P1
P2
P2-P1
Konvention: Normale zeigt ins Innere!Also: Linie (Fensterkante) wird durch einen Punkt Q1 und Normale nin impliziter Form dargestellt
Lian-Barsky-Algorithmus zeigt das Prinzip!
SS 20069Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Clipping von Liniensegmenten am Halbraum
Nun gibt es folgende 3 Fälle (Sonderfälle horizontaler oder vertikaler Geraden sind einfach und sind gesondert zu betrachten
10 0
1 2
1 2
.)( ) , ( )
liegen außen:
P und PE P E P≤ ≤
n-
Q1
Q2
+P2
P1
n-
Q1
Q2
+P2
P1
n-
Q1
Q2
+P2
P1
20 0
1 2
1 2
.)( ) , ( )
liegen innen:
P und PE P E P≥ ≥
30 00 0
1 2
1 2
1 2
.)( ) , ( ) ,( ) , ( )
liegen auf verschiedenen Seiten bzw.
P und PE P E PE P E P
< >> <
SS 200610Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Clipping von Liniensegmenten am Halbraum
Im Fall 3 müssen wir den Schnittpunkt P berechnen:Einsetzen der parametrischen in die implizite Gleichungliefert:
(
t =
E P t P PP t P P n Q n
Q n PnP P n
P P Q n PnP P n
P P
( ( )( ))
( )
( )( )
1 2 1
1 1 2 1
1 1
1 2
11 1
1 22 1
00
+ − =⇔ + − − =
⇔−
−
⇒ = +−
−−
n-
Q1
Q2
+P2
P1
P
SS 200611Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Clipping von Liniensegmenten am Halbraum
Der Lian-Barsky-Algorithmus verallgemeinert auf 3D:
• Halbräume sind nun durch Ebenen definiert.• Ebene wird auch in impliziter Form durch Punkt und
Normale beschrieben.• Parametrische Form für das Liniensegment bleibt
unverändert.
ABER: Algorithmus ist noch zu aufwendig – wir können noch viel Aufwand einsparen!
SS 200612Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Cohen-Sutherland-AlgorithmusStufe 1:
jedem Liniensegmentendpunkt, entsprechend seiner Lage in einer der 9 Regionen, die durch die Fensterbegrenzungen gebildet werden, ein 4-bit-Code zugeordnet.
von rechts nach links:
SS 200613Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Cohen-Sutherland-Algorithmus
Ein Liniensegment liegt völlig • innerhalb des Fensters,
wenn der Code für beide Endpunkte Null ist. • außerhalb des Fensters,
wenn der Durchschnitt (logisches UND) der Codes beider Endpunkte verschieden von Null ist.
Wegen dieser Eigenschaft nennt man diesen 4-bit-Code auch Outcode.
SS 200614Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Beispiele Outcode
0001)1001()0101( =∩=
0000)1000()0101( =∩=
Beide Endpunkte=(0000)
außerhalb
0110)0110()0110( =∩=außerhalb
SS 200615Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Ist beides nicht der Fall, so wird in der zweiten Stufe des Algorithmus der Schnittpunkt des Liniensegments mit einer Fensterbegrenzung berechnet.
Die erforderlichen Schnittpunktberechnungen ergeben sich durch Vergleich der Outcodes der Endpunkte.
Bei ungleichem Wert in einer Bitstelle wird mit der entsprechenden Fensterbegrenzung geschnitten.
Cohen-Sutherland-Algorithmus
)1001()1000()0001()0000()1000()0001(
=⊕=∩
Bit 1
Bit 3
Bit 4
Bit 2
SS 200616Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Cohen-Sutherland-Algorithmus
Jede Schnittpunktsberechnung zerlegt das Linien-segment in zwei Teile, die wieder nach Stufe 1 behandelt werden.
Dabei kann jeweils ein außerhalb des Fensters liegender Teil beseitigt werden.
(Wird der verbleibende Teil weder als völlig innerhalb noch als völlig außerhalb des Fensters erkannt, so wird Stufe 2 mit einer anderen Fensterbegrenzung durchgeführt.)
SS 200617Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Ein Klipping-Algorithmus für geschlossene Polygone muß als Ergebnis des Klippingvorgangs wieder geschlossene Polygone liefern. Dies ist nur durch richtige Einbeziehung von Teilen der Fensterbegrenzung in das ,,geklippte'' Polygon möglich.
Probleme entstehen, wenn das zu ,,klippende'' Polygon Ecken des Fenstersumschließt. Lösungsansatz: Umkehrung der Schleifenschachtelung: Das gesamte Polygon wird zunächst an einer Fenstergrenzegeklippt, anschließend wird an der nächsten Fenstergrenze geklippt etc.
Dies ist die wesentliche Idee des Sutherland-Hodgman-Algorithmus.
Polygon-Clipping
SS 200618Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Sutherland-Hodgeman-Algorithmus
SS 200619Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Der interessierende Teil der Bildinformation wird durch das Sichtvolumen(view volume) begrenzt.
Im Fall der Parallelprojektionist das Sichtvolumen ein in Projektionsrichtung unendlich ausgedehnter Quader.
Im Fall der perspektivischenProjektion eine Pyramide.Beide Volumina werden aus praktischen Gesichts-punkten durch eine vordere und hintere Ebene begrenzt.
x xy yz z
= == == =
0 10 10 1
,, ,
x z x zy z y zz z z z
= = −= = −= =
,,
,min max
Rückblick/ErinnerungProjektion
SS 200620Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
ErinnerungProjektion auf die xy-Ebene
Die z-Komponente wird zu Null gesetztUnterdrückt die z-KomponenteAchtung: positive und negative z-Werte werden aud die xy-Ebene abgebildet
Projektionsebenez0=0
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
=
1000000000100001
0P
z
x
y
Achtung: Auch Objekte auf der Seite des Augpunktes (auch hinter dem Beobachter) werden auf die Bildebene projiziert.
SS 200621Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Ist das Sichtvolumen ein Einheitswürfel, so könnte ein auf 3D erweiterter Cohen-Sutherland-Algorithmus verwendet werden.Ist das Sichtvolumen eine Pyramide, so kann der Lian-Barsky-Algorithmusangewendet werden.
Diese Lösungen hätten folgende Nachteile: • Für parallele und perspektivische Projektionen wird an unterschiedlicheSichtvolumina geclippt. Man benötigt also verschiedene Algorithmen.
• Da das Clipping in affinen Koordinaten durchgeführt wird, dürfen bis zum Clipping nur affine Transformationen verwendet werden. Die Perspektivemuss deshalb in einem separaten Schritt danach berechnet werden.
3D-Klipping
SS 200622Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Lösungsidee:Verzerrung der „Welt“
Wie bei der Parallelprojektion transformieren wir die „Welt“ in das kanonische kubische View VolumeAlso: Der Pyramidenstumpf (view frustum) wird in einen Würfel transformiert!
z
y
zx
y
xx
P(p)
(r,t,n)(l,b,n)
Beachte:Bei symmetrischen Sichtvolumen:
r=-l, t=-b
SS 200623Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Matrix der Transformationder Sichtpyramide
z
y
zx
y
x
P(p)
(r,t,n)(l,b,n)
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
−−−
→
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
−→
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
⎟⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜⎜
⎝
⎛
−−
−+−+
−−
−+
−−
=
1111
1
,
11
11
10100
200
020
002
nbl
ntr
also
nffn
nfnfbtbt
btn
lrrl
lrn
pP
SS 200624Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Zur Dokumentation
OpenGL Gründe wie zuvor angegeben:
0<n‘<f‘ sind Abstände auf der negativen x-Achse
DirectX:near-plane wird auf z=0
abgebildetÄnderungen ergeben sich
aus entsprechender Skalierung und Translation (siehe zuvor)
⎟⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜⎜
⎝
⎛
−−
−−
−
−+
−
−+
−
=
⎟⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜⎜
⎝
⎛
−−
−−+
−
−+
−
−+
−
=
0100''
''''
'00
020
002
0100''''2
''''00
020
002
nfnf
nffbtbt
btn
lrrl
lrn
nfnf
nfnf
btbt
btn
lrrl
lrn
DirectX
OpenGL
P
P
SS 200625Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Schnitt Polygon / Würfel
Viele weitere spezielle Algorithmen für das Clipping, z.B.
1992: Voorhies (Dreiecke) oder Greene : konvexe Polygone
1995: Green & Hatch: Erweiterung Voorhiesfür allgemeine Polygone
und noch viele mehr ... (Graphics Gems Serie)
SS 200626Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Zusammenfassung
Klipping ist eine wichtige Operatio, aber nicht besonders schwierig
In 2 D Systemen am Fensterrand!In 3 D Systemen nach der perspektivischen Transformation am Einheitswürfel
Noch zu behandeln: Visibilitätsproblem und Beleuchtungsrechnung
SS 200627Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
VisibilitätsrechnungVerdeckung (Unsichtbarkeit) entsteht durch ProjektionsäquivalenzSichtbar ist der nächstliegende Punkt zum Auge (zur Virtuellen Kamera), wenn Objekte opaque.Bei Transparenz: an einem Pixel mehr als ein Objekt sichtbar!Bei Spiegelung wären ggf. auch andere Objekte der Szene sichtbar
Wir betrachten bis auf weiterespolygonal modellierte Szenen mitausschließlich opaquen Objekten.
Erst einmal: keine Spiegelungen!
SS 200628Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Visibilitätsrechnung
Hidden Lines
Hidden Surfaces
SS 200629Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Visibilitäts-rechnung
Ist je nach gewähltem Algorithmus an vielen Stellen in der Pipeline möglich! Auch die Kombination verschiedener Algorithmen ist möglich und üblich.
Model and ViewTransformation
Beleuchtungs-rechnung für Vertices
Projektion
Klipping
Screen Mapping
Rastern(Scan Konvertieren)
Visibilitätsrechnung
Geo
met
risch
e B
erec
hnun
gen:
~ #
Pun
kte
Ras
tern
~# P
ixel
1
2
3
4
2a
SS 200630Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Bei einer Szene aus n Polygonen, können n2 sichtbare Fragmente entstehen ... es entstehen ggf. weitere Vertices
es sind ggf. sehr viele Fragmente in der Ausgabepipeline zu behandeln. In Software: unproblematisch in Hardware ggf. anhalten der Pipeline nötig
VisibilitätsverfahrenErste Beobachtung
SS 200631Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Erster SchrittBeseitigung der Rückseiten
(Backface Culling)culling: (aus einer Herde) aussortierenEine (vielleicht die wichtigste) von vielen Culling-Techniken (später)Rückseiten machen etwa die Hälfte aller Flächen ausOhne vorherige perspektivische Transformation kann aus dem Vorzeichen des Skalarprodukts „Sehstrahl mit der Normalen des Polygons“ die Rückseite ermittelt werden Position 1(Für einen konvexen Körper ist das Visibilitätsproblem hiermit schon vollständig gelöst)
SS 200632Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Implementierung des Backface Culling
In der Regel wird das Backface Culling erst nach der perspektivischen Projektion in Bildschirmkoordinaten (x,y,z=0) ausgeführt
Position 2 oder 2aRückseiten sind dadurch gekennzeichnet, dass ihr Normalenvektor eine positive z-Komponente hatMan berechne:
BackfacinggFrontfacin
aa
→→
>⎩⎨⎧
−=
−×−=
0amit
),0,0(),0,0(
)()(
n
vvvvn 0201Überzeugen Sie sich durch etwasVektorrechnung!
SS 200633Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Eine Erweiterung:Clustered Backface Culling
nach Shirman und Abi-Ezzi:Für ein Cluster von Polygonen (z.B. ein Triangle mesh oder eine polygonalisierteparametrischen Fläche wird ein Normalen-Zylinderstumpf (normal truncated cone) berechnet, so dass alle Punkte des Netzes im Stumpf liegen
diverse andere Erweiterungen möglich, siehe z.B. Realtime Rendering (2nd Ed.)
Gekennzeichnet durch:n : „mittlere“ Normaleα : Öffnungswinkelf,b : gemäß SkizzeMit e : Position des Viewers
Backfacing sindFlächen alle sin)2/cos( →=−≥⎟⎟⎠
⎞⎜⎜⎝
⎛
−−
⋅− ααπbeben
SS 200634Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Painters Algorithmus
Idee: Zeichne Polygone wie ein „Ölmaler“ sie malen würde: Die am weitest entferntesten zuerst.
Position in der Pipeline: 2 oder 2a
Das führt zu folgendem Algorithmus:
SS 200635Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Painters Algorithmus
1. Sortiere Polygone nach z-Wert [zmin,zmax].
2. Falls z-Intervalle überlappen, müssen Schnittpolygone berechnet werden.
3. Beginne das Zeichnen mit dem Polygon mit größtem z-Wert.
- der Painters Algorithmus hat eine O(n2)-Komplexität (n = Anzahl Dreiecke).
+ auch Transparenz ist problemlos behandelbar!
SS 200636Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Punktorientierte Algorithmen
Prinzip: Einzelne Punkte der Bildebene (z.B. Pixel, Subpixel) werden auf Sichtbarkeit untersucht
algorithmisch einfachste Algorithmen
Bei Rastergeräten: Punkte = Rasterpunktez-Buffer-Algorithmusschon 1974 vorgeschlagen (W. Strasser), aber damals nicht realisiert wg. Kosten des Speichersheute: Dominierender Algorithmus für RastergeräteSpeicher kostet wenig!
Position in der Pipeline: 4
SS 200637Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Visibilitäts-rechnung
Ist je nach gewähltem Algorithmus an vielen Stellen in der Pipeline möglich! Auch die Kombination verschiedener Algorithmen ist möglich und üblich.
Model and ViewTransformation
Beleuchtungs-rechnung für Vertices
Projektion
Klipping
Screen Mapping
Rastern(Scan Konvertieren)
Visibilitätsrechnung
Geo
met
risch
e B
erec
hnun
gen:
~ #
Pun
kte
Ras
tern
~# P
ixel
1
2
3
4
2a
SS 200638Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
z-Buffer-Algorithmus (1)depth buffering
Neben dem Farbwert wird für jeden Bildpunkt auch ein z-Wert gespeichert. Der Bildspeicher wird mit der Hintergrundfarbe und der z-Speicher dementsprechend mit dem maximal darstellbaren z-Wert initialisiert.Alle Objekte der Szene werden nacheinander mit der Bildauflösung gerastert. Eine besondere Reihenfolge ist nicht erforderlich.Für jedes Objekt und für jeden errechneten Bildpunkt durchläuft der Algorithmus folgende Schleife
SS 200639Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
z-Buffer-Algorithmus (2)1. Berechne z(x,y).
(Auch auf einem perspektivisch transformierten Dreieck kann dies durch lineare Interpolation gemacht werden.)
2. Ist z(x,y) kleiner als der für (x,y) bereits gespeicherte Wert, dann schreibe
z(x,y) in den z-Speicher und den zugehörigen Farbwert an der Stelle (x,y) in den Bildspeicher
SS 200640Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Vorteile des z-Buffers
Jede beliebige Szene kann, unabhängig von der Komplexität der Einzelobjekte, behandelt werden. In einer fertigen Szene können nachträglich Objekte eingefügt werden, sofern deren z-Werte zur Verfügung stehen.Szene kann in Teilen (unabhängig voneinander) gerendert werden
compositing mit z-Wert nötigDies ist besonders auch für die Kombination mit z.B. Kameraaufnahmen interessant (Mixed Reality) oder für spezielle Objekte, z.B. 3D Cursor
Leicht in Hardware zu realisieren
SS 200641Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Nachteile des z-Buffers
Unsichtbare Fragmente werden sehr spät erkannt viele Fragmente werden unnötig gerastert.Pro Bildpunkt wird ein (z-Wert, Farbwert) genau für ein Objekt gespeichert.
Daraus können Abtastfehler resultieren, die durch Supersampling[höhere Auflösung] verkleinert aber nicht beseitigt werden können.Transparenz ist prinzipiell nicht realisierbar.
Die Genauigkeit des z-Buffers ist beschränkt. Bei in der Tiefe weit ausgedehnten Szenen mit starker Perspektive passiert es häufig, dass verschiedene Objekte denselben z-Wert erhalten. Die Farbe wird dann von der Objektreihenfolge bei der Rasterung bestimmt.
SS 200642Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Z-BufferGenauigkeitsprobleme
nach der perspektivischen Transformation erhält man einen Vektor:
Buffer-z im Bitsder Anzahl :b
Wert-Buffer-z]12,0[]1,1[
)1,,,(),,,(
=−→−=
→=
b
w
z
w
z
w
y
w
xwzyx
vv
vv
vv
vvvvvvv
Parallelprojektionabsolute z-Auflösung ist konstant
Zentralprojektionabsolute z-Auflösung ist nicht konstant: bei großen z-Werten immer kleiner z-Aliasing
z-Auflösung hängt stark ab von der Position der near-clipping plane
SS 200643Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Alternativew-Buffer
Die Nichtuniformität der z-Auflösung ist für räumlich stark beschränkte Szenen (CAD) kaum ein Problem, dagegen für Außensichtszenen (Spiele, Sichtsimulation) u.U. problematisch.
Manchmal alternativ genutzt: w-buffer speichert anstelle des z-Wertes (wie auf der vorherigen Folie gezeigt) die w-Komponente nach der perspektivischen Transformation = z-Wert in Viewing-Koordinaten: w-Auflösung ist uniform
Blinn diskutiert diese Alternativen im Detail in A Trip Down the Graphics Pipeline
SS 200644Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Linienorientierte Algorihmen
Linien (= Polygonkanten) werden auf Sichtbarkeit untersuchtWenn sich Objekte nicht durchdringen, gilt prinzipiell: Sichtbarkeit kann sich nur an Körperkanten und Konturen ändern
Zu unterscheiden:Test im Bildraum Watkins Algorithmus
Integration in das Rastern (nächste Woche)
Test im Objektraum Appels Algorithmus
SS 200645Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Appels Algorithmus Objektränder und Konturen ermittelnArbeitet im Objektraum geräteunabhängig (Ähnliche Algorithmen wurden von Galimberti-Montanari (69) und Loutrel (70) entwickelt Eine Weiterentwicklung des Algorithmus für„NonphotorealisticRendering“ wurde von Markosian et.al. auf der Siggraph 97 vorgestellt
SS 200646Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Definition: Ein Polygon (Dreieck) heißt front-facing falls das Skalarproduktseiner Normalen und der Beobachtungsrichtung positiv ist, sonst back-facing (vgl. Backface-Culling). Eine Kante ist Silhouettenkante, falls sie benachbart ist zu einem front-facing und einem back-facing Polygon.
Appel‘s Algorithmus ordnet jedem Punkt einen quantitativen Visibilitätsstatusqi zu, der die Anzahl von front-facing Polygonen zwischen dem Punkt unddem Beobachter zählt. Alle Punkte mit qi=0 sind sichtbar und werden gezeichnet.
Appels AlgorithmusErgänzung
SS 200647Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Berechnung von qi: 1.) Bestimme Silhouettenkanten (forntfacing stößt an backfacing Polygon) (Entlang einer Kante kann sich qi nur ändern, falls ihr projektives Bild das projektive Bild eine Silhouettenkante oder eine Randkante schneidet. (Änderungen können auch in Punkten auf der Silhouette auftreten, s.u.)2.) Für zusammenhängende Kante wird (z.B. mit Ray-Tracing) für einen Punkt qi bestimmt. Dann wird ausgehend von diesem Punkt entlang benachbarter Kanten der Visibilitätsstatus qi für alle Punkte der Zusammenhangskomponente bestimmt. Dazu wird untersucht, ob Kanten hinter Silhouettenkanten verschwinden oder wieder sichtbar werden (siehe Applet).
Appels Algorithmus
SS 200648Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Spitzen (Cusps): Ein Punkt heißt „spizter Punkt“ falls eine der folgenden Bedingungen erfüllt ist:
• Der Punkt ist inzident zu exakt 2 Silhouettenkanten, eine „front-facing“ und eine „back-facing“.
• Er ist benachbart zu mehr als 2 Silhouettenkanten.• Er ist benachbart zu einer Randkante.
Entlang eines Polygons auf der Oberfläche, das nicht Silhouette ist, kann qisich ändern, falls das Polygon einen spitzen Silhouettenpunkt enthält.
Appels Algorithmus
Applet
SS 200649Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
+ Objektraumalgorithmus• keine Abtastfehler• geräteunabhängig• Genauigkeit nicht Auflösungsabhängig, z.B. wichtig für Plotausgabe• liefert Silhouetten• ist für „non-photorealistic rendering“ geeignet.
-relativ aufwendige Berechnung (Optimierungsmöglichkeiten sind z.B. von Markosian et. al.
angegeben)- für große Szenen in der jetzigen Form nicht echtzeitfähig.
ZusammenfassungAppels Algorithmus
SS 200650Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Flächen werden auf Verdeckung getestetGrundsätzlich ist wieder zwischen Rasterflächen (z.B. WarnocksAlgorithmus) und Objektflächen (z.B. Weiler-Atherton-Algorithmus) zu unterscheiden.
Idee des Warnock-Algorithmus: Teile und Herrsche (Divide and Conquer)
Rasterfläche (RF) wird auf Überdeckung mit Polygon getestet. Visibilität ist einfach zu bestimmen, falls1. Die dem Betrachter am nächsten liegende OF überdeckt die gesamte RF.2. Es existiert keine oder nur eine OF innerhalb der RF.
Flächenorientierte Algorithmen
SS 200651Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Ist keine der beiden Bedingungen erfüllt, so wird die Rasterfläche unterteilt und beide Bedingungen werden erneut überprüft.
Bei der Reduktion der Rasterfläche auf einen Rasterpunkt wird dann die erste Bedingung als erfüllt angesehen und die Sichtbarkeit mit einem z-Test (z-Buffer) entschieden.
Warnock Algorithmus
SS 200652Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
ZusammenfassungWarnock Algorithmus
Aufwand: O(np), wobei p Anzahl pixel, n Anzahl Polygone
Muß immer bis auf ein Pixel unterteilt werden, so ist das
Ergebnis ähnlich zum z-Buffer.
Das ist für fast alle großen Szenen (n>p) der Fall.Der Overhead des Unterteilens lohnt sich nicht
mehr.
SS 200653Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Zusammenfassungund Ausblick
Beleuchtungs-rechnung für Vertices
Rasterisieren
Model and ViewTransformation
Projektion
Klipping
Screen Mapping
Geo
met
risch
e B
erec
hnun
gen:
~ #
Pun
kte
Ras
tern
~# P
ixel
Beleuchtungs-rechnung für Pixel
Der Geometrieteil der Pipeline ist fast behandelt.
Es verbleiben:
• Rasterieren + Antaliasing• Beleuchtungsrechnung
und Shading• Texturen
Advanced Renderingim Überblick: Ray Tracingund Radiosity)
SS 200654Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Unsere nächsten Ziele: Beispiele
Nur diffuseReflektion
Multiple Lightsources
Texturiert &Reflection Mapping
SS 200655Computer Grafik6. Klipping und Visibilitätsrechnung© Prof. Dr.-Ing. Detlef Krömker
Glossar
back-face cullingPainters AlgorithmusPunktorientierte Verfahren
z-Buffer AlgorithmusLinienorientierte Verfahren
Watkins AlgorithmusAppels Algorithmus
Flächenorientierte VerfahrenWarnocks Algorithmus