Steuerungstasten

nächste Folie (auch Enter oder Spacebar).
vorherige Folie
 d  schaltet das Zeichnen auf Folien ein/aus
 p  wechselt zwischen Druck- und Präsentationsansicht
CTRL  +  vergrößert die Folien
CTRL  -  verkleinert die Folien
CTRL  0  setzt die Größenänderung zurück

Das Weiterschalten der Folien kann ebenfalls durch das Klicken auf den rechten bzw. linken Folienrand erfolgen.

Notation

Typ Schriftart Beispiele
Variablen (Skalare) kursiv $a, b, x, y$
Funktionen aufrecht $\mathrm{f}, \mathrm{g}(x), \mathrm{max}(x)$
Vektoren fett, Elemente zeilenweise $\mathbf{a}, \mathbf{b}= \begin{pmatrix}x\\y\end{pmatrix} = (x, y)^\top,$ $\mathbf{B}=(x, y, z)^\top$
Matrizen Schreibmaschine $\mathtt{A}, \mathtt{B}= \begin{bmatrix}a &b\\c &d\end{bmatrix}$
Mengen kalligrafisch $\mathcal{A}, B=\{a, b\}, b \in \mathcal{B}$
Zahlenbereiche, Koordinatenräume doppelt gestrichen $\mathbb{N}, \mathbb{Z}, \mathbb{R}^2, \mathbb{R}^3$

Intersection Shader

raytracing_pipeline
  • In diesem Kapitel werden verschiedene Intersection Shader für die Vulkan GLSL Ray Tracing Pipeline vorgestellt
  • Die Ray Tracing Pipeline hat eine eingebaute Schnittpunktberechnung für Dreiecke. Für andere Primitive (Würfel, Kugeln, usw.) wird ein eigener Shader benötigt
  • Wenn der Intersection Shader berechnet, dass ein Stahl-Primitiv-Schnittpunkt innerhalb der Bounding Box aufgetreten ist, benachrichtigt er die Stahlverfolgung mit der Funktion reportIntersectionEXT(...)
  • Darüber hinaus kann der Intersection Shader Daten in die hitAttributeEXT Variable schreiben, die vom benutzerdefinierten Typ ist und im Closest-Hit oder Any-Hit Shader ausgewertet werden kann

Schnittpunkt Strahl-Kugel

Schnittpunkt Strahl-Kugel

  • Parametrierung des Strahls mit:
    $\mathbf{x}(t) = \mathbf{s} + t \,\, \mathbf{r} \quad \forall\, \, t \in [t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$
    wobei $\mathbf{s}$ den Strahlursprung und $\mathbf{r}$ die Richtung bezeichnet
  • Parametrierung der Kugel mittels impliziter Kugelgleichung:
    $\begin{aligned}(x - c_x)^2 + (y - c_y)^2 + (z - c_z)^2 - r^2 &= 0\\ (\mathbf{x} - \mathbf{c})^\top \, (\mathbf{x} - \mathbf{c}) - r^2 &= 0\end{aligned}$
    wobei $\mathbf{c} = (c_x, c_y, c_z)^\top$ den Kugelmittelpunkt, und $r$ den Radius bezeichnet
  • Durch Einsetzen können die Schnittpunkte gefunden werden:
    $\begin{aligned} &(\mathbf{s} + t \,\, \mathbf{r} - \mathbf{c})^\top \, (\mathbf{s} + t \,\, \mathbf{r} - \mathbf{c}) - r^2 = 0\\ \Leftrightarrow &(t \,\, \mathbf{r} + \mathbf{b})^\top \, (t \,\, \mathbf{r} + \mathbf{b}) - r^2 = 0 \\ \Leftrightarrow &t^2 + p \,t + q = 0\end{aligned}$
    mit $\mathbf{b} = (\mathbf{s} - \mathbf{c})$, $p = 2 \, (\mathbf{r}^\top \, \mathbf{b}) / (\mathbf{r}^\top\,\mathbf{r})$ und $q = ((\mathbf{b}^\top \, \mathbf{b}) - r^2) / (\mathbf{r}^\top\,\mathbf{r})$
    $\Rightarrow t_{1,2} = - \frac{p}{2} \pm \sqrt{\frac{p^2}{4} - q}$

Schnittpunkt Strahl-Kugel

ray_sphere_intersection
$\mathbf{s}$
$\mathbf{r}$
$t_{\mathrm{\small in}}$
$t_{\mathrm{\small out}}$
  • Es kann keinen, einen oder zwei Schnittpunkte geben
    $\begin{align} t_{\mathrm{\small in}} &= - \frac{p}{2} - \sqrt{\frac{p^2}{4} - q}\\ t_{\mathrm{\small out}} &= - \frac{p}{2} + \sqrt{\frac{p^2}{4} - q}\end{align}$
  • Der Fall "kein Schnittpunkt" tritt genau dann auf, wenn
    $\frac{p^2}{4} - q < 0$
    Diese Bedingung sollte so früh wie möglich geprüft werden.
  • Andernfalls
    • wenn $t_{\mathrm{\small in}} < t_{\mathrm{\small out}}$ und $t_{\mathrm{\small in}} \in [t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$, ist der nächste Schnittpunkt:
      $\mathbf{x}(t_{\mathrm{\small in}}) = \mathbf{s} + t_{\mathrm{\small in}} \,\, \mathbf{r}$
    • ansonsten, wenn $t_{\mathrm{\small out}} \in [t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$, ist der nächste Schnittpunkt:
      $\mathbf{x}(t_{\mathrm{\small out}}) = \mathbf{s} + t_{\mathrm{\small out}} \,\, \mathbf{r}$

Schnittpunkt Strahl-Kugel

spherical_coord
$y$
$x$
$z$
$\tilde{\mathbf{n}}$
$\phi$
$\theta$
  • Die Oberflächennormale $\mathbf{n}$ im Schnittpunkt $\mathbf{x}(t_{\mathrm{\small hit}})$ berechnet sich zu:
    $\mathbf{n} = \frac{\mathbf{x}(t_{\mathrm{\small hit}}) - \mathbf{c}}{r}$
  • Zur Berechnung der Texturkoordinaten kann die Normale in das lokale Koordinatensystem transformieren werden. Dort die transformierte Normale $\tilde{\mathbf{n}}=(\tilde{n}_x,\tilde{n}_y,\tilde{n}_z)^\top$ in Kugelkoordinaten mit den Winkeln $\phi$ und $\theta$ umrechnen.
    Für die Texturkoordinaten ergibt sich damit:
    $\begin{align} s &= \frac{1}{2\pi} \phi = \frac{1}{2\pi} \operatorname{arctan2}(\tilde{n}_y, \tilde{n}_x)\\ t &= 1.0 - \frac{1}{\pi} \theta \\ &= 1.0 - \frac{1}{\pi} \arccos(\tilde{n}_z) = \frac{1}{\pi} \arccos(-\tilde{n}_z) \end{align}$

Beispiel: Intersection Shader Kugel

Beispiel: Intersection Shader Kugel

struct HitAttributeType {
  vec3 normal; 
  vec2 texCoord;
}; // type of the "hit" variable

...

void main() { /**** INTERSECTION SHADER ****/

  // ray-sphere intersection in world space
  
  // get bounding box in object space
  vec3 aabbMin;
  vec3 aabbMax;
  gsnGetIntersectionBox(gl_InstanceID, gl_PrimitiveID, aabbMin, aabbMax);
  
  // transform to world space
  vec3 minWorld = gl_ObjectToWorldEXT * vec4(aabbMin, 1.0);
  vec3 maxWorld = gl_ObjectToWorldEXT * vec4(aabbMax, 1.0);
  
  // center and radius of sphere in world space
  vec3 center = (minWorld + maxWorld) / 2.0;
  float radius = length((maxWorld - minWorld) / (sqrt(3.0) * 2.0));

  vec3 b = gl_WorldRayOriginEXT - center;
  vec3 r = normalize(gl_WorldRayDirectionEXT);
  float p = 2.0 * dot(r, b);
  float q = dot(b, b) - radius * radius;
  
  // discriminant of the quadratic equation
  float d =(p * p / 4.0) - q;
  
  // if no solution, cancel computation
  if(d < 0.0) return;
  
  // two solutions for quadratic equation
  float tin = -p / 2.0 - sqrt(d);
  float tout = -p / 2.0 + sqrt(d);
  
  // intersection at tin or tout?
  float t = tout;
  uint hitKind = 2u;
  if(tin < tout && tin >= gl_RayTminEXT && tin <= gl_RayTmaxEXT) {
    t = tin;
    hitKind = 1u;
  }
  if(t >= gl_RayTminEXT && t <= gl_RayTmaxEXT) {
    vec3 hitPoint = gl_WorldRayOriginEXT + t * gl_WorldRayDirectionEXT;
    vec3 n = normalize(hitPoint - center);
    vec3 localN = normalize(gl_WorldToObjectEXT * vec4(n, 0.0));
    hit.normal = n;
    hit.texCoord.s = fract(atan(localN.y, localN.x) / (2.0 * PI));
    hit.texCoord.t = acos(-localN.z)  / (PI);
    reportIntersectionEXT(t, hitKind);
  }
}

TLAS und BLAS

tlas_blas
TLAS
BLAS
gl_ObjectToWorldEXT
gl_WorldToObjectEXT
gl_InstanceID = 0
gl_InstanceID = 1
gl_InstanceID = 2
Triangle Mesh
Intersection Boxes
Intersection Boxes

Schnittpunkt im Objekt- oder Weltkoordinatensystem

  • Bei der vorherigen Implementierung wurde der Schnittpunkt im Weltkoordinatensystem berechnet
  • Dies war anscheinend nötig, da reportIntersectionEXT(...) den Wert für $t$ im Weltkoordinatensystem erwartet. Außerdem sind gl_RayTminEXT und gl_RayTmaxEXT ebenfalls im Weltkoordinatensystem definiert.
  • Die Berechnung kann jedoch ebenfalls im Objektkoordinatensystem erfolgen
  • Dies ist sogar einfacher und schneller, da die Transformation in das Weltkoordinatensystem gespart wird

Schnittpunkt im Objekt- oder Weltkoordinatensystem

  • Sei $\mathtt{T}$ eine 4 x 4 Matrix zur Transformation vom Objekt- in das Weltkoordinatensystem und $\underline{\tilde{\mathbf{p}}}$ der zu transformierende Punkt im Objektkoordinatensystem in homogenen Koordinaten
    $\underline{\mathbf{p}} = \begin{pmatrix} x \\ y \\ z \\ 1 \end{pmatrix} = \begin{bmatrix} m_{11} &m_{12}&m_{13} &t_x \\ m_{21} &m_{22}&m_{23} &t_y \\ m_{31} &m_{32}&m_{33} &t_z \\ 0 &0 &0 &1 \\ \end{bmatrix} \begin{pmatrix} \tilde{x} \\ \tilde{y} \\ \tilde{z} \\ 1 \end{pmatrix} = \mathtt{T} \, \underline{\tilde{\mathbf{p}}}$
  • Die bereitgestellte Matrix gl_ObjectToWorldEXT ist eine 3 x 4 Matrix, d.h. sie enthält nur die obersten drei Zeilen von $\mathtt{T}$
  • Die Idee für die Schnittpunktberechnung im Objektkoordinatensystem ist, nicht (wie bisher) das 3D-Objekt in das Weltkoordinatensystem zu transformieren, sondern stattdessen den Strahl in das Objektkoordinatensystem
  • Dazu wird einfach die inverse Transformation $\mathtt{T}^{-1}$ auf den Strahl angewendet
  • Die bereitgestellte Matrix gl_WorldToObjectEXT ist eine 3 x 4 Matrix, d.h. sie enthält nur die obersten drei Zeilen von $\mathtt{T}^{-1}$

Schnittpunkt im Objekt- oder Weltkoordinatensystem

  • Parametrierung des Strahls im Weltkoordinatensystem:
    $\mathbf{p} = \mathbf{s} + t \,\, \mathbf{r} \quad \forall\, \, t \in [t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$
    wobei $\mathbf{s}$ den Strahlursprung und $\mathbf{r}$ die normierte Richtung bezeichnet
  • Bei der Transformation des Strahls in das Objektkoordinatensystem, ist zu beachten, das $\mathbf{r}$ eine Richtung ist, die nicht transliert werden darf. Daher wird die letzte Komponente der homogenen Koordinaten auf 0 gesetzt.
  • Damit ergibt sich für den transformierten Strahl im Objektkoordinatensystem:
    $\begin{align} \underline{\tilde{\mathbf{p}}} = \mathtt{T}^{-1} \underline{\mathbf{p}} = \mathtt{T}^{-1} \left(\begin{pmatrix} \mathbf{s} \\ 1 \end{pmatrix} + t \,\, \begin{pmatrix} \mathbf{r} \\ 0 \end{pmatrix}\right) &= \mathtt{T}^{-1} \begin{pmatrix} \mathbf{s} \\ 1 \end{pmatrix} + t \,\, \mathtt{T}^{-1} \begin{pmatrix} \mathbf{r} \\ 0 \end{pmatrix} \\ &= \begin{pmatrix} \tilde{\mathbf{s}} \\ 1 \end{pmatrix} + t \,\, \begin{pmatrix} \tilde{\mathbf{r}} \\ 0 \end{pmatrix}\end{align}$
  • Der Vektor $\tilde{\mathbf{s}}$ wird durch die Variable gl_ObjectRayOriginEXT und $\tilde{\mathbf{r}}$ durch gl_ObjectRayDirectionEXT bereit gestellt

Schnittpunkt im Objekt- oder Weltkoordinatensystem

  • Parametrierung des Strahls im Weltkoordinatensystem:
    $\mathbf{p} = \mathbf{s} + t \,\, \mathbf{r} \quad \forall\, \, t \in [t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$
    mit gl_WorldRayOriginEXT $\,\mathbf{s}$ und gl_WorldRayDirectionEXT $\,\mathbf{r}$
  • Parametrierung des Strahls im Objektkoordinatensystem:
    $\tilde{\mathbf{p}} = \tilde{\mathbf{s}} + t \,\, \tilde{\mathbf{r}} \quad \forall\, \, t \in [t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$
    mit gl_ObjectRayOriginEXT $\,\tilde{\mathbf{s}}$ und gl_ObjectRayDirectionEXT $\,\tilde{\mathbf{r}}$
  • Der Parameter $t$ bleibt erhalten, d.h. ein $t$, das auf diese Weise im Objektkoordinatensystem ermittelt wird, entspricht dem $t$ im Weltkoordinatensystem
  • Wichtig: Bei Transformationen die Skalierungen enthalten, funktioniert der Ansatz nur, weil $\,\tilde{\mathbf{r}}$ nicht von der Ray Tracing Pipeline auf die Länge 1 normiert wird. Daher gl_ObjectRayDirectionEXT nicht im Intersection Shader normieren!

Intersection Shader Kugel im Objektkoordinatensystem

struct HitAttributeType {
  vec3 normal; 
  vec2 texCoord;
}; // type of the "hit" variable

...

void main() { /**** INTERSECTION SHADER ****/

  // ray-sphere intersection in object space
  
  // get bounding box in object space
  vec3 aabbMin;
  vec3 aabbMax;
  gsnGetIntersectionBox(gl_InstanceID, gl_PrimitiveID, aabbMin, aabbMax);
  
  // center and radius of sphere in object space
  vec3 center = (aabbMin + aabbMax) / 2.0;
  float radius = length(aabbMax.x - aabbMin.x) / 2.0;

  vec3 b = gl_ObjectRayOriginEXT - center;
  vec3 r = gl_ObjectRayDirectionEXT; // not normalized
  float rr = dot(r, r);
  float p = 2.0 * dot(r, b) / rr;
  float q = (dot(b, b) - radius * radius) / rr;
  
  // discriminant of the quadratic equation
  float d =(p * p / 4.0) - q;
  
  // if no solution, cancel computation
  if(d < 0.0) return;
  
  // two solutions for quadratic equation
  float tmin = -p / 2.0 - sqrt(d);
  float tmax = -p / 2.0 + sqrt(d);
  
  // intersection at tmin or tmax?
  float t = tmax;
  uint hitKind = 2u;
  if(tmin < tmax && tmin >= gl_RayTminEXT && tmin <= gl_RayTmaxEXT) {
    t = tmin;
    hitKind = 1u;
  }
  if(t >= gl_RayTminEXT && t <= gl_RayTmaxEXT) {
    vec3 hitPoint = gl_ObjectRayOriginEXT + t * gl_ObjectRayDirectionEXT;
    vec3 n = normalize(hitPoint - center);
    hit.normal = n;
    hit.texCoord.s = fract(atan(n.y, n.x) / (2.0 * PI));
    hit.texCoord.t = acos(-n.z)  / (PI);
    reportIntersectionEXT(t, hitKind);
  }
}

Beispiel: Viele Kugeln

example_manyspheres

Schnittpunkt Strahl-AABB

Schnittpunkt Strahl-AABB

  • Als Nächstes soll die Schnittpunktberechnung eines Strahls mit einer Axis-Aligned Bounding Box (AABB) betrachtet werden
  • Im Gegensatz zu einer orientierten Bounding Box ist eine AABB am Koordinatensystem ausgerichtet, was die Schnittpunktberechnung vereinfacht
  • Dabei wird die so genannte "Slab" Methode verwendet (Kay und Kajiya: "Ray tracing complex scenes", SIGGRAPH 1986)
  • Ein "Slab" ist ein Intervall in einer Raumrichtung und wird von zwei parallelen Ebenen begrenzt
  • Durch Analyse der Intervalle kann festgestellt werden, ob und wo ein Schnittpunkt auftritt
  • Dazu soll auf der nächsten Folie zunächst in 2D experimentiert werden. Die blauen Stützpunkte können mit der Maus verschoben werden.

Schnittpunkt Strahl-AABB: Interaktives 2D Beispiel

Schnittpunkt Strahl-AABB

  • Parametrierung des Strahls:
    $\mathbf{x}(t) = \mathbf{s} + t \,\, \mathbf{r} \quad \forall\, \, t \in [t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$
    wobei $\mathbf{s}$ den Strahlursprung und $\mathbf{r}$ die normierte Richtung bezeichnet
  • Die AABB wird durch zwei beliebige 3D Punkte $\mathbf{a}$ und $\mathbf{b}$ aufgespannt
    $\mathbf{a} = (a_x, a_y, a_z)^\top \quad \quad \mathbf{b} = (b_x, b_y, b_z)^\top$
  • Durch Einsetzen von $\mathbf{a}$ und $\mathbf{b}$ in die Strahlgleichung ergeben sich die 6 Schnittpunkte des Strahls mit den 6 Ebenen der AABB:
    $\begin{pmatrix}a_x\\a_y \\a_z\end{pmatrix}= \begin{pmatrix}s_x\\s_y \\s_z\end{pmatrix} + t \,\, \begin{pmatrix}r_x\\r_y \\r_z\end{pmatrix} \quad \quad \quad \begin{pmatrix}b_x\\b_y \\b_z\end{pmatrix}= \begin{pmatrix}s_x\\s_y \\s_z\end{pmatrix} + t \,\, \begin{pmatrix}r_x\\r_y \\r_z\end{pmatrix} $

Schnittpunkt Strahl-AABB

  • Werden die Gleichungen nach $t$ aufgelöst, ergeben sich die Positionen auf dem Strahl für alle 6 Schnittpunkte mit den AABB-Ebenen:
    $\begin{aligned} t_{a_x} = (a_x - s_x) / r_x & &t_{b_x} = (b_x - s_x) / r_x \\ t_{a_y} = (a_y - s_y) / r_y &&t_{b_y} = (b_y - s_y) / r_y \\ t_{a_z} = (a_z - s_z) / r_z &&t_{b_z} = (b_z - s_z) / r_z\\ \end{aligned}$
  • Für jede Dimension $x$, $y$ und $z$ ergibt sich ein Schnittintervall:
    • x-Intervall: $t \in [t_{{\small\mbox{min}}_x}, \,t_{{\small\mbox{max}}_x}] = [\min(t_{a_x}, t_{b_x}), \max(t_{a_x}, t_{b_x})]$
    • y-Intervall: $t \in [t_{{\small\mbox{min}}_y}, \,t_{{\small\mbox{max}}_y}] = [\min(t_{a_y}, t_{b_y}), \max(t_{a_y}, t_{b_y})]$
    • z-Intervall: $t \in [t_{{\small\mbox{min}}_z}, \,t_{{\small\mbox{max}}_z}] = [\min(t_{a_z}, t_{b_z}), \max(t_{a_z}, t_{b_z})]$
  • Es existieren zwei potenzielle Schnittpunkte:
    • das Maximum der Minimalwerte $t_{\mathrm{\small in}} = \max(t_{{\small\mbox{min}}_x}, \,t_{{\small\mbox{min}}_y}, \,t_{{\small\mbox{min}}_z})$
    • das Minimum der Maximalwerte $t_{\mathrm{\small out}} = \min(t_{{\small\mbox{max}}_x}, \,t_{{\small\mbox{max}}_y}, \,t_{{\small\mbox{max}}_z})$

Schnittpunkt Strahl-AABB

  • Es kann keinen, einen oder zwei Schnittpunkte geben
    • Zwei Schnittpunkte, wenn $t_{\mathrm{\small in}} < t_{\mathrm{\small out}}$:
      Eintritt bei $t_{\mathrm{\small in}}$
      Austritt bei $t_{\mathrm{\small out}}$
    • Ein Schnittpunkt, wenn $t_{\mathrm{\small in}} = t_{\mathrm{\small out}}$
    • Kein Schnittpunkt, wenn $t_{\mathrm{\small in}} > t_{\mathrm{\small out}}$
  • Typischerweise ist das Strahlintervall begrenzt
    $\mathbf{x}(t) = \mathbf{s} + t \,\, \mathbf{r} \quad \forall\, \, t \in [t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$.
    Dann muss natürlich zusätzlich geprüft werden, ob $t_{\mathrm{\small in}}$ bzw. $t_{\mathrm{\small out}}$ innerhalb des gewünschten Intervalls $[t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$ liegt

Zwei Schnittpunkte: Beispiel in 2D

ray-box_example1
$t_{\mathrm{\small in}} \le t_{\mathrm{\small out}} \Rightarrow$ Schnitt
$t_{{\small\mbox{min}}_x} = t_{\mathrm{\small in}}$
$t_{{\small\mbox{max}}_x}$
$t_{{\small\mbox{min}}_y}$
$t_{{\small\mbox{max}}_y} = t_{\mathrm{\small out}}$
$x$
$y$
ray-box_example1_ranges
$t_{{\small\mbox{min}}_x}$
$t_{{\small\mbox{max}}_x}$
$t_{{\small\mbox{min}}_y}$
$t_{{\small\mbox{max}}_y}$
x-Intervall
y-Intervall

Kein Schnittpunkt: Beispiel in 2D

ray-box_example2
$t_{\mathrm{\small in}} > t_{\mathrm{\small out}} \Rightarrow$ Kein Schnitt
$t_{{\small\mbox{max}}_y}$
$t_{{\small\mbox{max}}_x}$
$t_{{\small\mbox{min}}_y}$
$t_{{\small\mbox{min}}_x}$
$x$
$y$
ray-box_example2_ranges
$t_{{\small\mbox{max}}_y}$
$t_{{\small\mbox{max}}_x}$
$t_{{\small\mbox{min}}_y}$
$t_{{\small\mbox{min}}_x}$
x-Intervall
y-Intervall

Schnittpunkt Strahl-AABB in GLSL

bool slabs(vec3 a, vec3 b, vec3 rayOrigin, vec3 invRayDir) {
  vec3 ta = (a - rayOrigin) * invRayDir;
  vec3 tb = (b - rayOrigin) * invRayDir;
  vec3 tmin = min(ta, tb);
  vec3 tmax = max(ta, tb);
  float tin = max(max(tmin.x, tmin.y), tmin.z);
  float tout = min(min(tmax.x, tmax.y), tmax.z);
  return (tin <= tout);
}

Beispiel: Intersection Shader AABB

Beispiel: Intersection Shader AABB

struct HitAttributeType {
  vec3 normal; 
  vec2 texCoord;
}; // type of the "hit" variable

...

void main() { /**** INTERSECTION SHADER ****/

  // ray-box intersection
  
  // get bounding box in object space
  vec3 a, b;
  gsnGetIntersectionBox(gl_InstanceID, gl_PrimitiveID, a, b);

  // perform intersection in object space using the slab method
  // Kay and Kajiya, SIGGRAPH 1986
  // Majercik et al., JCGT 2018
  vec3 invRayDir = 1.0 / gl_ObjectRayDirectionEXT;
  vec3 ta = (a - gl_ObjectRayOriginEXT) * invRayDir;
  vec3 tb = (b - gl_ObjectRayOriginEXT) * invRayDir;
  vec3 tmin = min(ta, tb);
  vec3 tmax = max(ta, tb);
  float t_in = max(tmin.x, max(tmin.y, tmin.z));
  float t_out = min(tmax.x, min(tmax.y, tmax.z));
  
  if(t_in <= t_out) { // intersection found
    // decide if first or second hit is selected
    float t = t_in;
    uint hitKind = 1u; // hit outside->inside
    if(t < gl_RayTminEXT) {
      t = t_out;
      hitKind = 2u; //  hit inside->outside
    }
    if(t >= gl_RayTminEXT && t <= gl_RayTmaxEXT) {
      // compute normal and texture coordinates
      vec3 center = (a + b) / 2.0;
      vec3 p = gl_ObjectRayOriginEXT + t * gl_ObjectRayDirectionEXT;
      vec3 n = normalize(p - center);
      vec2 tc = vec2(0.0, 0.0);
      vec3 n_abs = abs(n);
      float max_n_abs = max(n_abs.x, max(n_abs.y, n_abs.z));
      if(n_abs.x == max_n_abs) {
        tc =  (vec2(sign(n.x), 1.0) * p.yz - a.yz) / (b.yz - a.yz);
        n = vec3(sign(n.x), 0.0, 0.0);
      } else if(n_abs.y == max_n_abs) {
        tc = (vec2(-sign(n.y), 1.0) * p.xz - a.xz) / (b.xz - a.xz);
        n = vec3(0.0, sign(n.y), 0.0);
      } else {
        tc = (vec2(sign(n.z), 1.0) * p.xy - a.xy) / (b.xy - a.xy);
        n = vec3(0.0, 0.0, sign(n.z));
      }
      hit.normal = n;
      hit.texCoord = tc;
      
      reportIntersectionEXT(t, hitKind);
    }
  }
}

Schnittpunkt Strahl-Dreieck

Schnittpunkt Strahl-Dreieck

  • Parametrierung des Strahls:
    $\mathbf{x}(t) = \mathbf{s} + t \,\, \mathbf{r} \quad \forall\, \, t \in [t_{\mathrm{\small min}}, t_{\mathrm{\small max}}]$
    wobei $\mathbf{s}$ den Strahlursprung und $\mathbf{r}$ die normierte Richtung bezeichnet
  • Das Dreieck wird durch drei Punkte $\mathbf{a}$, $\mathbf{b}$ und $\mathbf{c}$ definiert
    ray_tri_intersection
    $\mathbf{a}$
    $\mathbf{b}$
    $\mathbf{c}$
    $\mathbf{s}$
    $\mathbf{r}$
  • Ebenengleichung:
    $\mathbf{x}(u, v) = \mathbf{a} + u \,(\mathbf{b} - \mathbf{a}) + v \,(\mathbf{c} - \mathbf{a})$
  • Durch Gleichsetzen ergibt sich:
    $\mathbf{a} + u \,(\mathbf{b} - \mathbf{a}) + v \,(\mathbf{c} - \mathbf{a}) = \mathbf{s} + t \,\, \mathbf{r}$
  • Gleichungsystem in Matrixschreibweise
    (3 Gleichungen, 3 Unbekannte):
    $\begin{bmatrix}-\mathbf{r} & \mathbf{b} - \mathbf{a} &\mathbf{c} - \mathbf{a}\end{bmatrix} \begin{pmatrix}t\\u\\v\end{pmatrix} = \mathbf{s} - \mathbf{a}$

Schnittpunkt Strahl-Dreieck

  • Durch Substitution mit $(\mathbf{b} - \mathbf{a}) = \mathbf{i}$, $(\mathbf{c} - \mathbf{a}) = \mathbf{j}$ und $(\mathbf{s} - \mathbf{a}) = \mathbf{k}$:
    $\begin{bmatrix}-\mathbf{r} & \mathbf{b} - \mathbf{a} &\mathbf{c} - \mathbf{a}\end{bmatrix} \begin{pmatrix}t\\u\\v\end{pmatrix} = \mathbf{s} - \mathbf{a} \quad\Leftrightarrow \quad \begin{bmatrix}-\mathbf{r} & \mathbf{i} &\mathbf{j}\end{bmatrix} \begin{pmatrix}t\\u\\v\end{pmatrix} = \mathbf{k} $
  • Lösung des linearen Gleichungssystems ist gegeben durch (Cramersche_Regel)
    $\begin{pmatrix}t\\u\\v\end{pmatrix} = \frac{1}{\det(-\mathbf{r}, \mathbf{i}, \mathbf{j})} \begin{bmatrix}\det(\mathbf{k}, \mathbf{i}, \mathbf{j})\\ \det(-\mathbf{r}, \mathbf{k}, \mathbf{j})\\ \det(-\mathbf{r}, \mathbf{i}, \mathbf{k})\\ \end{bmatrix} = \frac{1}{(\mathbf{r} \times \mathbf{j})^\top \mathbf{i}} \begin{bmatrix}(\mathbf{k} \times \mathbf{i})^\top \mathbf{j}\\ (\mathbf{r} \times \mathbf{j})^\top \mathbf{k}\\ (\mathbf{k} \times \mathbf{i})^\top \mathbf{r}\\ \end{bmatrix}$
    mit $\det(\mathbf{x}, \mathbf{y}, \mathbf{z}) = (\mathbf{x} \times \mathbf{y})^\top \mathbf{z} = -(\mathbf{x} \times \mathbf{z})^\top \mathbf{y} = -(\mathbf{z} \times \mathbf{y})^\top \mathbf{x}$
  • Lösung benötigt nur 2 Kreuz- und 4 Skalarprodukte

Schnittpunkt Strahl-Dreieck

ray_tri_intersection2
$\mathbf{a}$
$\mathbf{b}$
$\mathbf{c}$
$\mathbf{s}$
$\mathbf{r}$
$u$
$v$
$\mathbf{i}$
$\mathbf{j}$
$\mathbf{i}$
$\mathbf{j}$
$1$
$1$
$0$
$v = (-1) u + 1$
  • Schnittpunkt mit der Ebene ist innerhalb des Dreiecks, wenn
    • $u$ und $v$ im Bereich $[0, 1]$
    • und $u + v < 1$

Baryzentrische Koordinaten

triangle
$\mathbf{a}$
$\mathbf{b}$
$\mathbf{c}$
  • Die bisherige Ebenengleichung
    $\mathbf{x}(u, v) = \mathbf{a} + u \,(\mathbf{b} - \mathbf{a}) + v \,(\mathbf{c} - \mathbf{a})$
    kann auch geschrieben werden als
    $\mathbf{x}(u, v) = (1- u - v) \,\mathbf{a} + u \,\mathbf{b} + v \,\mathbf{c}$
  • Nun wird eine zusätzliche Variable eingeführt $w = (1 - u - v)$ und die Ebenengleichung lautet:
    $\mathbf{x}(w, u, v) = w \,\mathbf{a} + u \,\mathbf{b} + v \,\mathbf{c}$
    mit der Nebenbedingung $u + v + w = 1$
  • Die Ebene ist jetzt zwar überparametrisiert (3 anstatt 2 Parameter) aber durch die Nebenbedingung wird sichergestellt, dass alle Punkte $\mathbf{x}(w, u, v)$ auf der Ebene liegen
  • Die Parameter $w$, $u$, $v$ werden baryzentrische Koordinaten genannt

Baryzentrische Koordinaten

triangle
$\mathbf{a}$
$\mathbf{b}$
$\mathbf{c}$
  • Die baryzentrischen Koordinaten $u$, $v$ und $w$ sind die Koeffizienten der Linearkombination der Stützstellen des Dreiecks:
    $\mathbf{x}(w, u, v) = w \,\mathbf{a} + u \,\mathbf{b} + v \,\mathbf{c}$
    mit der Nebenbedingung $u + v + w = 1$
  • Sind $u$, $v$ und $w \ge 0$, liegt der Punkt $\mathbf{x}(w, u, v)$ innerhalb des Dreiecks
triangle_bary
$\mathbf{x}(w=\frac{1}{3}, u=\frac{1}{3}, v=\frac{1}{3})$
$\mathbf{x}(w=0, u=\frac{1}{2}, v=\frac{1}{2})$
$\mathbf{x}(w=0, u=0, v=1)$
$\mathbf{x}$
$\mathbf{x}$
$\mathbf{x}$

Baryzentrische Koordinaten

  • Geometrische Interpretation: Der Punkt $\mathbf{x}$ teilt das Dreieck in drei Unterdreiecke. Das Verhältnis der Fläche des gegenüberliegenden Unterdreiecks zur Gesamtfläche entspricht der baryzentrischen Koordinate:
    $w = \frac{A_{\mathbf{a}}}{A} \quad \quad\quad \quad u = \frac{A_{\mathbf{b}}}{A}\quad \quad \quad\quad v = \frac{A_{\mathbf{c}}}{A}$
triangle_bary_area
$\mathbf{a}$
$\mathbf{b}$
$\mathbf{c}$
$\mathbf{a}$
$\mathbf{b}$
$\mathbf{c}$
$\mathbf{a}$
$\mathbf{b}$
$\mathbf{c}$
$\mathbf{x}$
$\mathbf{x}$
$\mathbf{x}$
$A_{\mathbf{a}}$
$A_{\mathbf{b}}$
$A_{\mathbf{c}}$

Baryzentrische Koordinaten

triangle_colorinterpolation
  • Baryzentrische Koordinaten werden häufig verwendet, um Vertex-Daten zu interpolierten (wie Farbe, Textur-Koordinate, Normale usw.)
  • Auch die eingebaute Schnittpunktberechnung für Dreiecke liefert die baryzentrische Koordinaten
    $u$ und $v$ des Schnittpunkts durch die
    "hitAttributeEXT vec2 baryCoord" Variable
  • Die $w$ Koordinate ergibt sich aus:
    $w = (1 - u - v)$
vec3 barys = vec3(1.0f - baryCoord.x - baryCoord.y, baryCoord.x, baryCoord.y);
vec3 interpColor = blue * barys.x + red * barys.y + green * barys.z;

Beispiel: Intersection Shader Dreieck

Beispiel: Intersection Shader Dreieck

struct HitAttributeType {
  vec3 normal; 
  vec2 texCoord;
  vec2 baryCoord;
}; // type of the "hit" variable

...

void main() { /**** INTERSECTION SHADER ****/

  // ray-triangle intersection
  
  // Note: Ray-triangle intersection is a
  // built-in feature of the ray tracing shader pipeline. 
  // It is just provided for educational purpose.
  
  // get bounding box in object space
  vec3 aabbMin;
  vec3 aabbMax;
  gsnGetIntersectionBox(gl_InstanceID, gl_PrimitiveID, aabbMin, aabbMax);
  vec3 diff = aabbMax - aabbMin;

  // a, b, and c are the three triangle vertices
  vec3 a = aabbMin + vec3(0.0, 0.0, diff.z / 2.0);
  vec3 b = aabbMin + vec3(diff.x, 0.0, diff.z / 2.0);
  vec3 c = aabbMin + vec3(diff.x / 2.0, diff.y, diff.z / 2.0);

  // performing ray-triangle intersection in object space using
  // Tomas Möller and Ben Trumbore:
  // "Fast, Minimum Storage Ray / Triangle Intersection",
  // Journal of Graphics Tools, 2(1):21--28, 1997
  
  // here we use exactly the notation from the lecture slides
  vec3 i = b - a;
  vec3 j = c - a;
  vec3 k = gl_ObjectRayOriginEXT - a;
  vec3 r = gl_ObjectRayDirectionEXT;
  
  // implementing ray/triangle intersection according to
  // the lecture slides by computing
  // (t, u, v) = (1 / (r x j) * i) ((k x i) * j, (r x j) *k, (k x i) * r)
  vec3 rxj = cross(r, j);
  float rxji = dot(rxj, i);
  
  // denominator close to zero?
  if (abs(rxji) < 1e-16) return;
  
  uint hitKind = 0xFEu; // front facing
  if (rxji < 0.0) {
    hitKind = 0xFFu; // back facing
  }
  
  float f = 1.0f / rxji;
  
  // compute u
  float u = dot(rxj, k) * f;
  if (u < 0.0f || u > 1.0f) return;
  
  // compute v
  vec3 kxi = cross(k, i);
  float v =  dot(kxi, r) * f;
  if (v < 0.0 || v > 1.0) return;
  if(u + v > 1.0) return;
  
  // compute t
  float t =  dot(kxi, j) * f;

  if (t < gl_RayTminEXT) return;
  if (t > gl_RayTmaxEXT) return;
    
  vec3 hitPoint = gl_ObjectRayOriginEXT + t * gl_ObjectRayDirectionEXT;
  hit.texCoord = (hitPoint.xy - aabbMin.xy) / diff.xy;
  hit.normal = vec3(0.0, 0.0, 1.0);
  hit.baryCoord = vec2(u, v);
  reportIntersectionEXT(t, hitKind);
}

CSG

Constructive Solid Geometry (CSG)

  • Schnittpunktberechnungen für kompliziertere Objekte können aus Schnittpunktberechnungen für einfache Grundformen (Primitive) zusammengesetzt werden
  • Die Kombination findet dabei typischerweise durch folgende Operationen statt:
    • Vereinigungsmenge $\mathcal{A}\cup \mathcal{B}=\{x\in \mathcal{A} \lor x\in \mathcal{B}\}$
    • Schnittmenge $\mathcal{A} \cap \mathcal{B} =\{x\in \mathcal{A} \land x\in \mathcal{B}\}$
    • Differenzmenge $\mathcal{A}\setminus \mathcal{B}=\{x\in \mathcal{A}\land x\notin \mathcal{B}\}$
csg
Vereinigungsmenge
Schnittmenge
Differenzmenge

Constructive Solid Geometry (CSG)

ray_sphere_intersection
$\mathbf{s}$
$\mathbf{r}$
$t_{\mathrm{\small in}}$
$t_{\mathrm{\small out}}$
  • Um die Operationen in einem Intersection Shader zu implementieren, werden die Intervalle für den Strahlparameter $t$ betrachtet, in denen $t$ innerhalb des Objekts ist
  • Bei einfachen (konvexen) Objekten (Kugel, Würfel) kann dies durch den Ein- und Austrittspunkt beschrieben werden $[t_{\mathrm{\small in}}, t_{\mathrm{\small out}}]$
    ray_csg_intersection
    $\mathcal{A}$
    $\mathcal{B}$
    $t_{\mathcal{A}, \mathrm{\small in}}$
    $t_{\mathcal{A}, \mathrm{\small out}}$
    $t_{\mathcal{B}, \mathrm{\small in}}$
    $t_{\mathcal{B}, \mathrm{\small out}}$
  • Im Folgenden soll überlegt werden, wie sich die neuen Intervalle nach den verschiedenen CSG-Operationen berechnen
  • Dazu werden 5 verschiedene Fälle betrachtet (siehe nächste Folie)

Constructive Solid Geometry (CSG)

ray_csg_cases
1. kein Schnittpunkt
2. Schnitt nur Objekt $\mathcal{A}$
3. Schnitt nur Objekt $\mathcal{B}$
4. Schnitt mit beiden Objekten, Intervalle überlappen nicht
5. Schnitt mit beiden Objekten, Intervalle überlappen
$\mathcal{A}$
$\mathcal{B}$

CSG: Vereinigungsmenge

bool computeCsgUnion(in vec2 interval0, in vec2 interval1, float tmin,
                     out vec2 combinedInterval, out ivec2 hitIndex) {
  // handle the 5 cases from the lecture/tutorial
  if(interval0.x > interval0.y && interval1.x > interval1.y) {
    // case 1: no intersection
    combinedInterval = vec2(1e8, -1e8);
    return false;
  } else if(interval0.x <= interval0.y && interval1.x > interval1.y) {
     // case 2: only object0
    hitIndex =  ivec2(0, 0); // hit object0
    combinedInterval = interval0;
  } else if(interval0.x > interval0.y && interval1.x <= interval1.y) {
    // case 3: only object1
    hitIndex = ivec2(1, 1); // hit object1
    combinedInterval = interval1;
  } else if(!intervalsOverlap(interval0, interval1)) {
    //case 4: intervals are not overlaping 
    if(interval0.x < interval1.x && interval0.y >= tmin) {
      combinedInterval = interval0;
      hitIndex = ivec2(0, 0); // hit object0
    } else if(interval1.y >= tmin) {
      combinedInterval = interval1;
      hitIndex = ivec2(1, 1); // hit object1
    } else {
      combinedInterval = vec2(1e8, -1e8);
      return false;
    }
  } else {
    //case 5: intervals are overlaping 
    if(interval0.x < interval1.x) {
      hitIndex.x = 0; // hit object0
      combinedInterval.x = interval0.x;
    } else {
      hitIndex.x = 1; // hit object1
      combinedInterval.x = interval1.x;
    }
    if(interval0.y > interval1.y) {
      hitIndex.y = 0; // hit object0
      combinedInterval.y = interval0.y;
    } else {
      hitIndex.y = 1; // hit object1
      combinedInterval.y = interval1.y;     
    }
  }
  return true;
}

CSG: Schnittmenge

bool computeCsgIntersection(in vec2 interval0, in vec2 interval1, float tmin,
                            out vec2 combinedInterval, out ivec2 hitIndex) {
  // handle the 5 cases from the lecture/tutorial
  if(interval0.x > interval0.y && interval1.x > interval1.y) {
    // case 1: no intersection
    combinedInterval = vec2(1e8, -1e8);
    return false;
  } else if(interval0.x <= interval0.y && interval1.x > interval1.y) {
    // case 2: only object0
    combinedInterval = vec2(1e8, -1e8);
    return false;
  } else if(interval0.x > interval0.y && interval1.x <= interval1.y) {
    // case 3: only object1
    combinedInterval = vec2(1e8, -1e8);
    return false;
  } else if(!intervalsOverlap(interval0, interval1)) {
    //case 4: intervals are not overlaping 
    combinedInterval = vec2(1e8, -1e8);
    return false;
  } else {
    //case 5: intervals are overlaping 
    if(interval0.x >= interval1.x) {
      hitIndex.x = 0; // hit object0
      combinedInterval.x = interval0.x;
    } else {
      hitIndex.x = 1; // hit object1
      combinedInterval.x = interval1.x;
    }
    if(interval0.y <= interval1.y) {
      hitIndex.y = 0; // hit object0
      combinedInterval.y = interval0.y;
    } else {
      hitIndex.y = 1; // hit object1
      combinedInterval.y = interval1.y;     
    }
  }
  return true;
}

CSG: Differenzmenge

bool computeCsgDifference(in vec2 interval0, in vec2 interval1, float tmin,
                          out vec2 combinedInterval, out ivec2 hitIndex) {
  // handle the 5 cases from the lecture/tutorial
  if(interval0.x > interval0.y && interval1.x > interval1.y) {
    // case 1: no intersection
    combinedInterval = vec2(1e8, -1e8);
    return false;
  } else if(interval0.x <= interval0.y && interval1.x > interval1.y) {
     // case 2: only object0
    hitIndex =  ivec2(0, 0); // hit object0
    combinedInterval = interval0;
  } else if(interval0.x > interval0.y && interval1.x <= interval1.y) {
    // case 3: only object1
    combinedInterval = vec2(1e8, -1e8);
    return false;
  } else if(!intervalsOverlap(interval0, interval1)) {
    //case 4: intervals are not overlaping 
    combinedInterval = interval0;
    hitIndex = ivec2(0, 0); // hit object0
  } else {
    //case 5: intervals are overlaping 
    if(interval0.x < interval1.x && interval1.x >= tmin) {
      hitIndex = ivec2(0, 1); // first hit object0, second hit object1
      combinedInterval.x = interval0.x;
      combinedInterval.y = interval1.x;
    } else if(interval1.y < interval0.y && interval0.y >= tmin) {
      hitIndex = ivec2(1, 0); // first hit object2, second hit object0
      combinedInterval.x = interval1.y;
      combinedInterval.y = interval0.y;
    } else {
      combinedInterval = vec2(1e8, -1e8);
      return false;
    }
  }
  return true;
}

Beispiel: CSG

example_csg
  • Beispiel: CSG

Gibt es Fragen?

questions

Anregungen oder Verbesserungsvorschläge können auch gerne per E-Mail an mich gesendet werden: Kontakt

Weitere Vorlesungsfolien

Folien auf Englisch (Slides in English)