Return to Computer Vision Notebooks

Ray-Triangle Intersection



Implementation of ray-triangle intersection algorithm.

Primitives


The first thing is to define the ray origin $O$ and direction $\large ê$, where the unit vector $\large ê = \frac{\vec{e}}{\parallel \vec{e} \parallel}$.

image 01

Next step is to define the 3D triangle in counter-clockwise order in relation to the direction of the face.

image 02

Intersection


To find the ray intersection, the next step is to define the triangle normal $\hat{n}$, where:

$$ \large \hat{n} = \frac{\vec{AB} \times \vec{AC}}{\parallel \vec{AB} \times \vec{AC} \parallel} $$

p.s.: to calculate ray-triangle intersection it is not necessary to normalize the normal vector.

image 03

The supporting plane is what the triangle lies on, sharing the same normal vector. Given the plane equation:

$$ \large ax + by + cz + d = 0 $$

Having the vector normal as $\hat{n} = [a b c]^T$ and $P = [x y z]^T$ as any point on the plane, we can define $d$ as follows:

$$ \large \hat{n} \cdot P + d = 0 \quad \therefore \quad d = - \hat{n} \cdot P $$

p.s.: in this case any known point can be used. Lets use the point $A$ so $P = A$

image 04

Before finding the intersection point $P$ on the plane, we must calculate the parameter $t$. We start by looking at the parametric equation of a line segment, which has the same direction of $ê$ and origin from $O$:

$$ \large P(P_x, P_y, P_z) = O + ê t $$

where:

$$ \large P_x = O_x + ê_x t \\ \large P_y = O_y + ê_y t \\ \large P_z = O_z + ê_z t $$

Using this concept on the plane equation, we have:

$$ \large ax + by + cz + d = 0 \\ \large aP_x + bP_y + cP_z + d = 0 \\ \large a(O_x + ê_x t) + b(O_y + ê_y t) + c(O_z + ê_z t) + d = 0 \\ \large aO_x + aê_x t + bO_y + bê_y t + cO_z + cê_z t + d = 0 \\ \large (aê_x + bê_y + cê_z)t + (aO_x + bO_y + cO_z) + d = 0 \\ \large (\hat{n} \cdot \hat{e})t + \hat{n} \cdot O + d = 0 \\ \large t = - \frac{\hat{n} \cdot O + d}{\hat{n} \cdot \hat{e}} $$

image 05

To figure out if the plane intersection point is inside or outside the triangle, we basically have to define the vector from each vertices to $P$ and cross it with its oriented edge segment (for each vertex). If the intersection point is outside the triangle, the resulting vector will be in the opposite direction from the normal one.

$$ \large [(B - A) \times (P - A)] \cdot \hat{n} \geq 0 \\ \large [(B - B) \times (P - B)] \cdot \hat{n} \geq 0 \\ \large [(B - C) \times (P - C)] \cdot \hat{n} \geq 0 $$

If all these conditionals are obeyed, we can conclude that the point $P$ is inside the triangle. Otherwise, the point is going to be outiside toward to the edges of the negative values.

image 06

3D Intersection


Apply same model for each pixel of an image plane as the origin and the ray direction is based on the perspective camera model:

image 07

Barycentric coordinates


The barycentric coordinates will help us to interpolate in-between vertex values. To do that we have to calculate the area of all resulting triangles. Any triangle area can be calculated as follows:

$$ \large \text{Area}_{ABC} = \frac{\parallel (B - A) \times (C - A) \parallel}{2} $$

Next step is to find the weight of each point so that we can use it to interpolate any desired values.

$$ \large \alpha = \frac{\text{Area}_{BCP}}{\text{Area}_{ABC}} = \frac{\parallel (C - B) \times (P - B) \parallel}{\parallel (B - A) \times (C - A) \parallel} \\\\ \large \beta = \frac{\text{Area}_{CAP}}{\text{Area}_{ABC}} = \frac{\parallel (A - C) \times (P - C) \parallel}{\parallel (B - A) \times (C - A) \parallel} \\\\ \large \gamma = \frac{\text{Area}_{ABP}}{\text{Area}_{ABC}} = \frac{\parallel (B - A) \times (P - A) \parallel}{\parallel (B - A) \times (C - A) \parallel} $$

Have the weights we can interpolate any kind of value (color, for example) by using:

$$ \large V = \frac{\alpha V_A + \beta V_B + \gamma V_C}{\alpha + \beta + \gamma} $$

image 08