Lecture 07: Ray intersection algorithms

Intersection function

Intersection function returns whether or not ray intersects an object. If the intersection exists, the intersection function will return an intersection point [1], [2]

Sphere intersection algorithm

[3], [4]

Sphere intersection algorithm deduction

\[||\vec{X} - \vec{C}||^2 = r^2\]

\[(\vec{X} - \vec{C})\cdot(\vec{X} - \vec{C}) = r^2 \] \[(t\vec{\omega} + \vec{P} - \vec{C})\cdot(t\vec{\omega} + \vec{P} - \vec{C}) = r^2\]

\[\small{ t^2(\vec{\omega}\cdot\vec{\omega})+2t(\vec{\omega}\cdot(\vec{P}-\vec{C}))+((\vec{P}-\vec{C})\cdot(\vec{P}-\vec{C}))-r^2=0 }\]

Möller-Trumbore algorithm

Möller-Trumbore algorithm: ray definition

From ray definition: \[X = P+t\vec{\omega}\]

From barycentric coordinates: \[X = (1 - u - v)V_0 + uV_1 + vV_2\]

\[P+t\vec{\omega} = (1 - u - v)V_0 + uV_1 + vV_2\]

[5]

Möller-Trumbore algorithm: linear equations

\[[-\vec{\omega}, V_1-V_0, V_2-V_0]\begin{bmatrix} t \\ u \\ v \end{bmatrix} = P - V_0\]

[5]

Möller-Trumbore algorithm: Cramer’s rule

\(\vec{E_1} = V_1-V_0\), \(\vec{E_2} = V_2-V_0\), \(\vec{T} = P-V_0\)

\[\begin{bmatrix} t \\ u \\ v \end{bmatrix} = \frac{1}{|-\vec{\omega}, \vec{E_1}, \vec{E_2}|} \begin{bmatrix} |\vec{T} , \vec{E_1}, \vec{E_2}| \\ |-\vec{\omega}, \vec{T} , \vec{E_2}| \\ |-\vec{\omega}, \vec{E_1}, \vec{T}| \end{bmatrix}\]

[5]

Möller-Trumbore algorithm: Triple product

\(|\vec{A}, \vec{B}, \vec{C}| = - (\vec{A}\times\vec{C})\cdot\vec{B} = - (\vec{C}\times\vec{B})\cdot\vec{A}\)

\[\begin{bmatrix} t \\ u \\ v \end{bmatrix} = \frac{1}{(\vec{\omega}\times \vec{E_2}) \cdot \vec{E_1} } \begin{bmatrix} (\vec{T} \times \vec{E_1}) \cdot \vec{E_2} \\ (\vec{\omega} \times \vec{E_2}) \cdot \vec{T} \\ (\vec{T} \times \vec{E_1}) \cdot \vec{\omega} \end{bmatrix}\]

[5]