Computer)GraphikI - eecs.tu-berlin.de fileMarc%Alexa,%TU%Berlin% CG 17 Rekursives)Raytracing) Algorithmus) fürjedesPixeldesBildschirms{1.%Erzeuge%primären%Strahl%vom%Augpunktdurch%das%Pixel%

Marc Alexa, TU Berlin

CG �

1

Computer Graphik I

Globale Beleuchtung – Ray Tracing


CG �

2

Raytracing

§  Albrecht Dürer „der zeichner des liegenden weibes“, 1538 Darstellung des Velo von AlberD (1404 –1472)


CG �

3

Rekursives Raytracing

§  WhiMed 1979: Modell zur IntegraDon •  ReflekDon •  Beugung •  Verdeckungsrechnung •  SchaMen

§  Raytracing simuliert den Prozess der Lichtausbreitung und arbeitet dabei nach den Gesetzen für ideale Spiegelung und Brechung.


CG �

4

Rekursives Raytracing Annahmen

§  Lichtquellen •  Punktlichtquellen

§  Materialien •  Diffuse mit spekulärem Anteil (Phong Modell)

§  Lichtausbreitung •  verdeckende Objekte (SchaMen aber keine HalbschaMen) •  Keine Lichtabschwächung •  nur spekulärer Lichtaustausch zwischen Flächen (Strahlen werden nur in ReflekDonsrichtung verfolgt)


CG �

5

Rekursives Raytracing Whi>ed 1979


CG �

6

Rekursives Raytracing Beispiele

§  Raytracing ist vor allem für Szenen mit hohem spiegelnden und transparenten Flächenanteil gut geeignet.


CG �

7


§  Die Grundidee besteht darin, Lichtstrahlen auf ihrem Weg von der Quelle bis zum Auge zu verfolgen.

§  Zur Vereinfachung werden beim konvenDonellen Raytracing nur ideal reflekDerte und ideal gebrochene Strahlen weiterverfolgt.


CG �

8


§  Nur wenige Strahlen erreichen das Auge

§  Das Verfahren wird umgekehrt •  Reziprozität der Reflexion

§  Man sendet durch jedes Pixel des Bildschirms einen vom Augpunkt ausgehenden Strahl in die Szene


CG �

9


§  SyntheDsche Kamera ist definiert durch einen Augpunkt und eine Bildebene in Weltkoordinaten

§  Bildebene ist in Pixel unterteilt, entsprechend der Auflösung des resulDerenden Bildes


CG �

10


§  Vom Augpunkt aus werden Strahlen durch die Pixel in die Szene geschickt.


CG �

11


§  Falls der Strahl mehr als ein Objekt schneidet, erscheint das nächste Objekt im Bild.

§  Sonst wird Hintergrundfarbe gezeichnet.


CG �

12


§  Falls ein Objekt vom Strahl geschniMen wird, so werden weitere Strahlen vom SchniMpunkt aus zu allen Lichtquellen gesendet.


CG �

13


§  Treffen diese „SchaMenstrahlen“ auf ein Objekt, so liegt der betrachtete Flächenpunkt im SchaMen.


CG �

14


§  Ist das Objekt spiegelnd, wird ein weiterer reflekDerter Strahl in die Szene gesendet.


CG �

15


§  Ist das Objekt transparent, so wird zusätzlich ein gebrochener Strahl weiterverfolgt.


CG �

16


§  Trij ein reflekDerter oder ein transmikerter Strahl auf ein weiteres Objekt, so werden vom neuen SchniMpunkt aus wieder SchaMenstrahlen zu den Lichtquellen und reflekDerte bzw. transmit-‐ Derte Strahlen ausgesendet.

§  Sichtstrahlen sind Parameter einer rekursiven FunkDon, die alle sichtbaren Flächen detekDert, sie schakert und die Resultate zurückliefert.

S

S

S

S


CG �

17

Rekursives Raytracing Algorithmus

für jedes Pixel des Bildschirms {

1. Erzeuge primären Strahl vom Augpunkt durch das Pixel

2. Färbe es entsprechend der Leuchtdichte aus dieser Richtung

}

für jeden Strahl {

1. BesDmme nächstliegenden SchniMpunkt des Sehstrahls mit einem Objekt der Szene

2. Teste den SchaMenfühler auf SchniMpunkte: Falls keine Verdeckung der Lichtquelle, werte das Phong-‐Beleuchtungsmodell im SchniMpunkt aus

3. Erzeuge ideal reflekDerten Lichtstrahl und addiere die Leuchtdichte aus dieser Richtung (Rekursion)

4. Berechne ideal gebrochenen Lichtstrahl und addiere die Leuchtdichte aus dieser Richtung (Rekursion)

5. Gebe die summierte Leuchtdichte zurück

}


CG �

18

Beleuchtungsmodell

§  Beleuchtung auf der Fläche ergibt sich •  ambient + •  diffus + •  spekular (Highlights und ReflekDon) + •  transmikert

§  Äquivalent zum Phong-‐Modell plus Beiträge des reflekDerten und transmikerten Strahls


CG �

19

Beleuchtungsmodell

§  Beleuchtungsmodell •  Lges = LPhong + rrLr + rtLt, •  wobei

–  Lr die Leuchtdichte auf dem reflekDerten Strahl, –  Lt die Leuchtdichte auf dem transmikerten Strahl, –  rr der Reflexionsgrad für die Idealreflexion, –  rt der Reflexionsgrad für die Idealtransmission ist.

R=E-2(N*E)N


CG �

20

Strahl-‐Objekt-‐Schni>

§  Strahl ist durch Ursprung und Richtungsvektor definiert •  R(t) = Ro + t*Rd, wobei Ro Strahlursprung, Rd Richtung •  Ursprung von Sichtstrahlen ist der Augpunkt •  Ursprung von sekundären Strahlpunkt, sind SchniMpunkte von Elternstrahlen mit

Oberflächen

§  Jeder Strahl muss gegen alle Objekte auf SchniM getestet werden, um nächsten SchniMpunkt zu idenDfizieren.


CG �

21

Strahl-‐Objekt-‐Schni> Kugel

§  Abstand zum Zentrum mit Radius vergleichen! •  tca = (Sc -‐ Ro)Rd •  thc2 = Sr2 -‐ D2

•  D2 = LOC2 -‐ tca2 •  => thc2 = Sr2 -‐ LOC2+ tca2 •  Ist thc2 < 0, dann gibt

es keinen SchniMpunkt

§  SchniMpunkt aus dem Parameter besDmmen •  t = tca +/-‐ sqrt(thc2)

§  SchniMpunkt liegt auf dem Strahl nur für t > 0!


CG �

22

Strahl-‐Objekt-‐Schni> Dreieck

§  Dreieck V1, V2, V3 §  SchniM mit der durch das Dreieck definierten Ebene

•  Normale des Dreiecks N = (V3-‐V1)x(V2-‐V1) •  Ebene: alle P für die gilt (P-‐V1)N = 0 •  SchniM: für t mit (Ro + ti*Rd -‐ V1)N = 0

–  t = (Ro -‐ V1)N / RdN

•  SchniMpunkt: S = Ro + ti*Rd §  Liegt der SchniMpunkt im Dreieck?

•  Gleiche OrienDerung der Dreiecke (S,V1,V2), (S,V2,V3), (S,V3,V1) •  OrienDerung: z.B. Vorzeichen von (V1-‐S)x(V2-‐S), usw.


CG �

23

Strahl-‐Objekt-‐Schni> Dreieck -‐ besser

§  SchniMpunkt gleich in baryzentrischen Koordinaten besDmmen •  Dreieck: wV1+uV2+vV3 mit u+v+w=1, also (1-‐u-‐v)V1+uV2+vV3 •  SchniM: Ro + t*Rd = (1-‐u-‐v)V1+uV2+vV3 •  LGS: [-‐Rd (V2-‐V1) (V3-‐V1)] (t,u,v)T = (Ro-‐V1) •  Lösung: det = (Rdx(V3-‐V1))(V2-‐V1)

–  t = det-‐1 ((Ro-‐V1)x(V2-‐V1))(V3-‐V1) –  u = det-‐1 ((Rdx(V3-‐V1))(Ro-‐V1) –  v = det-‐1 ((Ro-‐V1)x(V2-‐V1)) Rd

§  Liegt der SchniMpunkt im Dreieck? •  0<u<1, 0<v<1, u+v < 1 (t > 0)


CG �

24

Strahl-‐Objekt-‐Schni> algebraische Flächen

§  Quadrik •  Ax2+By2+Cz2+2Dxy+2Exz+2Fyz+2Gx+2Hy+2Iz+J=0 •  einsetzen des Strahls liefert quadraDsche Gleichung in t

§  algebraische Fläche vom Grad n > 2 •  einsetzen liefert Polynom vom Grad n •  Für n < 5 algebraische Lösung (eventuell verbessern durch einen NewtonschriM)

•  Für n > 4 NullstellenbesDmmung z.B. durch Unterteilung mit Algorithmus von de Casteljau.


CG �

25

Strahl-‐Objekt-‐Schni> Strahl -‐ implizite Fläche

§  Einsetzen liefert reelle FunkDon in t •  NullstellenbesDmmung z.B. mit Newtonverfahren

§  Ray Marching •  Feste SchriMlänge, SP bei Vorzeichenwechsel

§  Sphere Tracing •  Sei d(x,A) eine Schranke auf den

vorzeichenbeha}eten Abstand d(x,A) ≤ min ||x – y|| für alle y in A

•  d(x,A) ist der Radius einer Kugel, die garanDert die implizite Fläche A nicht schneidet

•  Marschiere entlang des Strahls x = r0 x += d(x,A) rd

•  SchniMpunkt wenn die SchriMe konvergieren


CG �

26

Strahl-‐Objekt-‐Schni>


CG �

27

Rekursives Ray Tracing ConstrucMve Solid Geometry


CG �

28

Ray Tracing ist so langsam!

§  SchniMpunktsberechnungen sind aufwändig! •  Die Anzahl der SchniMpunktberechnungen pro Strahl ist O(n), wobei n die Anzahl

von Objekten in der Szene ist. •  Die Anzahl der benöDgten Strahlen m hängt von der Bildschirmauflösung und der

Anzahl von Lichtquellen ab und wächst (in stark reflekDerenden und transmikerenden) Szenen exponenDell mit der Anzahl r der Rekursionsstufen.

•  Um Aliaseffekte zu unterdrücken, werden häufig mehrere Strahlen pro Pixel gesendet.

•  Jede Lichtquelle induziert SchaMenstrahlen. •  Damit ist die Anzahl von SchniMpunktsberechnungen O(mn).


CG �

29

Ray Tracing beschleunigen

§  Weniger Strahlen! •  AdapDve RekursionsDefenkontrolle •  AdapDves AnDaliasing

§  Schnellere SchniMpunktsberechnungen Strahl -‐ Szene! •  Schneller SchniMpunktsberechnungen Strahl -‐ Objekt

–  Geeignete Bounding Volumes für Objekte (NichtschniM schneller detekDeren) •  Weniger SchniMpunktsberechnungen Strahl-‐Objekt

–  Bounding Volume Hierarchien –  Raumunterteilungen (Grids, BSP-‐Trees, Octrees)

•  Richtungsabhängige Verfahren –  Light-‐Buffer


CG �

30

Weniger Strahlen AdapMve RekursionsMefenkontrolle

§  ReflekDerte und transmikerte Strahlen tragen nur einen besDmmten Bruchteil zur Beleuchtung eines Punktes bei.

§  Je Defer die Rekursion, umso kleiner ist der Beitrag des Strahls zur Beleuchtungsrechnung.

§  Nach einer besDmmten RekursionsDefe fallen die Beiträge unter eine besDmmte Schwelle. In diesem Fall werden keine weiteren Strahlen mehr generiert.


CG �

31

Kugel Achsenparallele Bounding Box (BB)

Orientierte BB

Schneller Strahl-‐Objekt Nicht-‐Schni> Hüllkörper

§  Hüllkörper müssen einfach sein, d.h. SchniMtest mit anderen PrimiDven (Sichtvolumen, Sehstrahl) müssen sich einfach berechnen lassen.


CG �

32

Schneller Strahl-‐Objekt Nicht-‐Schni> Hüllkörperhierarchien

§  Algorithmus: Culling •  Beginne mit der Wurzel des Baumes •  Teste jeden Knoten auf SchniM mit dem Strahl •  Falls SchniM, so wird die Traversierung rekursiv mit den Kindern fortgesetzt. •  Falls kein SchniM, so wird die weitere Bearbeitung des Knotens eingestellt.


CG �

33

Schneller Strahl-‐Objekt Nicht-‐Schni> Hierarchische Raumunterteilung

§  Reguläres GiMer kann schnell miMels Rasterisierung traversiert werden •  Einmalige SchniMpunktberechnung mit dem Wurzelkubus •  Rasterisierung: 3D Digital DifferenDal Analyzer (3DDA)

§  Octree kann auch effizient traversiert werden •  Traversierung ähnlich dem 3DDA •  Zusätzlich Fallunterscheidungen und Halbieren bzw. Verdoppeln

der SchriMweiten bei Änderung der HierarchieDefe


CG �

34


§  Kd-‐Baum (/ BSP-‐ Baum) Traversierung:


CG �

35


§  Kd-‐Baum (/ BSP-‐ Baum) Traversierung:


CG �

36


§  Kd-‐Baum Traversierung: Strahl wird an der AABB geschniMen.


CG �

37


§  Kd-‐Baum Traversierung: Strahl wird auf den vorderen Halbraum beschränkt und auf SchniM gegen die nächste SchniMebene getestet.


CG �

38


§  Kd-‐Baum Traversierung: Vorgang wird wiederholt.


CG �

39


§  Kd-‐Baum Traversierung: Bis zu den BläMern; hier wird gegen die Objekte geschniMen.


CG �

40


§  Kd-‐Baum Traversierung: Dann wird der Baum weiter traversiert und die abgewandten Halbräume bearbeitet.


CG �

41


§  Kd-‐Baum Traversierung: Und so weiter.


CG �

42


§  Kd-‐Baum Traversierung:


CG �

43


§  Kd-‐Baum Traversierung:


CG �

44

Richtungsabhängige Verfahren Light Buffer


CG �

45

DistribuMon Ray Tracing Cook et al. ´84

§  ApproximaDon konDnuierlicher Phänomene durch Vervielfachung von Strahlen (Supersampling) •  StochasDsche Verteilung der Strahlrichtungen

(bzw. VerteilungsfunkDon) •  Anschließendes MiMeln der Farbwerte

§  Phänomene •  HalbschaMen (So} Shadows) •  Glanz (Gloss / Blurred ReflecDon) •  Transluzenz (Blurred transperancy) •  Bewegungsunschärfe (MoDon Blur) •  Tiefenschärfe (Depth of field)

§  Harte SchaMen, etc. können als Aliasing verstanden werden!


CG �

46

50% Verdeckung

DistribuMon Ray Tracing So[ Shadows

§  SchaMenfühler werden zufällig auf der projizierten Fläche ausgewählt •  Graduelle Verdeckung entspricht dem Verhältnis aus versperrten zu

ungehinderten Fühlern •  In der Praxis wird eine günsDge Gleichverteilung der Strahlen durch

Vorberechnung erreicht •  Um Mustereffekte zu vermeiden kann Rauschen hinzugefügt werden


CG �

47

DistribuMon Ray Tracing So[ Shadows


CG �

48

DistribuMon Ray Tracing Gloss

§  ReflekDerte Strahlen werden gemäß einer spekulären VerteilungsfunkDon gestreut (Im Extremfall ApproximaDon global diffuser Beleuchtung ?)


CG �

49

DistribuMon Ray Tracing Transluzenz


CG �

50

DistribuMon Ray Tracing MoMon Blur

§  Zeitliches Sampling: Strahlen werden „zeitlich“ gestreut •  Die Kamera und die Objekte werden in die PosiDon eines zufällig gewählten

Momentes innerhalb eines Zei�ensters transformiert. •  Strahlen werden verfolgt •  Farbwerte werden gemiMelt •  Entspricht der Verschlußzeit

beim Fotografieren •  Zeitliches AnDaliasing


CG �

51

DistribuMon Ray Tracing Depth of Field

§  Tiefenschärfe miMels virtueller Linse und Blende •  SchniM von Strahl durch PixelmiMe und fokaler Ebene besDmmt den fokalen Punkt

eines Strahls bzw. Pixels (Linse) •  Strahlursprung wird auf der

Bildebene gestreut (Blende) •  Alle Strahlen dieses Pixels

verlaufen durch den Fokalen Punkt


CG �

52

DistribuMon Ray Tracing Depth of Field


CG �

53

Beispiele


CG �

54

Beispiele

§  Norbert Kern -‐ trace 101 h 18 min §  Machine -‐ 1,4 GHz Athlon C / 1 GB RAM


CG �

55

Vorteile von Ray Tracing

§  Beliebig komplexe Szene und Objekte •  Bedingung: Es können SchniMpunkte und dort dann Objektnormalen besDmmt

werden (Fraktale?).

§  Berechnung von Verdeckung, SchaMen, Reflexion, Transparenz, perspekDvischer TransformaDon, Clipping geschieht automaDsch

§  Objekte dürfen sich gegenseiDg durchdringen -‐ SchniMe zwischen Objekten brauchen nicht berechnet zu werden.

§  Das Beleuchtungsmodell wird nur in sichtbaren Objektpunkten ausgewertet.


CG �

56

Nachteile

§  Abtastung führt zu Aliasing •  Abhilfe: Teures Supersampling oder stochasDsches Abtasten

§  Rechenaufwand ist sehr groß §  Scharfe SchaMenkanten -‐ HalbschaMen sind sehr teuer §  Keine Ausnutzung von Kohärenz

•  StaDsche Szene = konstante SchaMen, müssen aber trotzdem für jeden Blickpunkt neu gerechnet werden

•  Diffuse Effekte sind auch unabhängig vom Blickpunkt


CG �

57

Nachteile Diffuse Lichtausbreitung

§  Spekular-‐diffus-‐Übergang wird nicht berücksichDgt. Lösung z.B. durch Beam-‐Tracing oder Photon Maps

§  Globales diffuses Licht wird beim konvenDonellen Raytracing-‐Verfahren nicht berücksichDgt.


CG �

58

Probleme mit diffuser Beleuchtung

A Daylight Experiment, John Ferren


CG �

59

Probleme mit diffuser Beleuchtung

Documents

Computer)GraphikI - eecs.tu-berlin.de fileMarc%Alexa,%TU%Berlin% CG 17 Rekursives)Raytracing) Algorithmus) fürjedesPixeldesBildschirms{1.%Erzeuge%primären%Strahl%vom%Augpunktdurch%das%Pixel%