Bildsynthese
Intersection Shader

• 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

• 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}$

$\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}$

$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}$

• 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}$

• 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

• 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 Ray-Sphere (Object Space)

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);
  }
}

• 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.

• 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} $

• 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})$

• 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

• 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
  

  $\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}$

• 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

$\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

$\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

$\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 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;

• 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}\}$

Vereinigungsmenge

Schnittmenge

Differenzmenge

$\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}}]$
  

  $\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)