Ray Tracing

In computer graphics, Ray Tracing is an algorithm for generating 3D images by tracing the path of light through pixels in an image plane and simulating the effects of its encounters with virtual objects, like reflections, refractions, shadows. The algorithm produce a very high degree of visual realism.

The algorithm

for each pixel from image

create an infinte ray with the camera position and this pixel

for each object in the scene

if the ray intersects with the object

if the intersection is infront and the nearest to the camera

paint the pixel with the color at the intersection point

else

paint the pixel with the background color

Obviously this is a very simplified version of the algorithm, but already helps us to understand how it works.

800px-Ray_trace_diagram.svg_.png
As we want to create an image from scratch, we have to loop through each pixel of the image and calculate the color with which will have to paint. To calculate the color for each pixel, we create an infinite ray from the camera position to the pixel, wich will cross the scene intersecting with the elements of the scene, after obtaining all intersections of the ray with the elements of the scene, will save the nearest intersection and is in front the camera (the calculations can give intersections that are behind the camera, if there are elements behind it).

Once we have the intersection point, we should paint the pixel with the information about the color that we can obtain from the element surface, else if the ray does not intersect with any element then the pixel will be paint with the background color. At this moment we have two problems, find if the ray intersects with the element of the scene, and what color is the element surface. For now let’s assume that the element surface is red, and see how calculate if a ray intersects some primitive elements.

Ray

Knowing the line equation:
 \vec{r}(t)=p_0 + t \cdot \hat{v}
Where:
 t is the distance from  p_0
 p_0 is a point of the line
 \hat{v} is the direction of the line
Since \vec{r} is a vector, we can decompose like:
 r_x(t)= (p_0)_{x} + t \cdot v_{x}
r_y(t)= (p_0)_{y} + t \cdot v_{y}
 r_z(t)= (p_0)_{z} + t \cdot v_{z}

Now that we know this, we can check if our ray intersects some element of our scene. Also, if we want to calculate some features like reflections, refractions and shadows we will need to know the normal of the intersected element.

Ray vs Plane

An infinite plane is for sure the most simple element that we can intersect with a ray. The plane will give a sense of depth to our image creating the horizon.

RT_suelo.jpg

The equation from a plane is given by a point  p and 2 vectors  \vec{u} and  \vec{v} But in our case we don’t know any point of our infinite plane, but we define it with its normal  \hat{N} and the distance  d from the camera, so we will use:
 \vec{p} \cdot \hat{N} = d
Where  \vec{p} is the ray. Using the line equation we can say that:
 (p_0 + t \cdot \hat{v}) \cdot \hat{N} = d
 p_0 \cdot \hat{N} + t \cdot \hat{v} \cdot \hat{N} = d
With every element from the scene we want to isolate the  t variable because is the distance from the origin of the ray to the element if it intersects.
 t = \dfrac {d - p_0 \cdot \hat{N}}{\hat{v} \cdot \hat{N}}
This  t for every element that we calculate can be:

  • Negative: it means that the ray intersects from behind the origin of the element, so it will return a false value and has to be ignored.
  • Positive: it means that the ray intersects with the element, so it will return a valid value.
  • Zero: this means that the ray is tangent to the element, so it means that the ray only intersects at one point with the element. This is a valid value except for the plane, which will have infinite points, so it will be ignored.

We only need the smaller positive value, so from every  t valid value that we get, we only save the smaller one.

Ray vs Sphere

Now we have a reference to put the elements. We start with the sphere, which is the simplest of geometric figures.

RT_suelo_esfera.jpg

The equation of the sphere centered at the origin of radius R:
 x^2 + y^2 + z^2 = R^2
Using the line equation we can say that:
 ((p_0)_{x} + t \cdot v_{x})^2 + ((p_0)_{y} + t \cdot v_{y})^2 + ((p_0)_{z} + t \cdot v_{z})^2=R^2
 ((p_0)_{x}^2 + t^2v_{x}^2 + 2t(p_0)_{x}v_{x}) + ((p_0)_{y}^2 + t^2v_{y}^2 + 2t(p_0)_{y}v_{y}) + ((p_0)_{z}^2 + t^2v_{z}^2 + 2t(p_0)_{z}v_{z}) = R^2
 t^2(v_{x}^2+v_{y}^2+v_{z}^2) + t(2(p_0)_{x}v_{x} + 2(p_0)_{y}v_{y} + 2(p_0)_{z}v_{z}) + ((p_0)_{x}^2 + (p_0)_{y}^2 + (p_0)_{z}^2 - R^2) = 0
This can be a little confusing, but we can simplify to a known formula that we can solve:
 at^2 + bt + c = 0
Now we have to solve what we have simplified:
 a = v_{x}^2+v_{y}^2+v_{z}^2 = 1 if  v is normalized.
 b = 2(2(p_0)_{x}v_{x} + 2(p_0)_{y}v_{y} + 2(p_0)_{z}v_{z}) = 2p_0 \cdot \hat{v}
 c = (p_0)_{x}^2 + (p_0)_{y}^2 + (p_0)_{z}^2 - R^2 = p_0 \cdot p_0 - R^2
Once we have this solved, we can solve the quadratic equation:
 t = \dfrac{-b \pm \sqrt{b^2-4ac}}{2a}
If first we try to solve the root, we can see 3 cases, where  D = b^2 - 4ac :

  •  D < 0 \Rightarrow It doesn’t have intersection
  •  D = 0 \Rightarrow t = \dfrac{-b}{2a}
  •  D > 0 \Rightarrow We pick the smaller positive from:
    •  t_0 = \dfrac {-b + D}{2a}
    •  t_0 = \dfrac {-b - D}{2a}

The sphere normal at the point of intersection is the normalized vector between the point and the center of the sphere.

Illumination

Now that we know how to calculate if our ray intersects with any element of the scene, and get the point from the element where intersects and its normal at this point if it’s true, we should paint the pixel with the element material color. But like in real life, if something it’s not illuminated by a point of light this won’t be visible, whatever the color of its surface.

Ray-Tracing-1.jpg
As we see in the image, the vector  \vec{E_1} comes from the camera and intersects with the red ball at the point  P_1 , this point defines a new vector  \vec{L_1} with the light in the scene, the same happens with the vector  \vec{E_2} but in this case  \vec{L_2} intersects with the sphere so this pixel has to be painted as a shadow and not like the first one as the element material color.

Indeed to know exactly how to paint the element surface we have to take in count some parameters. First a material color is defined by 3 coefficients (Ambient, Diffuse and Specular), also has a level of reflectance, refractance and glossines (the way it shines with a direct light source). The light source also has a color and potential properties.

Ray-Tracing-2-reflection.jpg
In this image we see how the reflectance is calculated and how the light is reflected on a surface, knowing that  ray is the ray from the camera to the scene, and  light is the data from a light source in the scene:

 \hat{E} = -ray.dir
 \hat{L} = P - light.loc
 \hat{E_r} = -\hat{E} + 2*\hat{N} \cdot \hat{E} * \hat{N}
 \hat{L_r} = -\hat{L} + 2*\hat{N} \cdot \hat{L} * \hat{N}
With this calculations done, we can solve the equation that we will use for the final color of the pixel.  C_r = getColor(\hat{E_r}) where  C_r is the color of the reflection on the surface.
 C_l = \displaystyle\sum_{i=0}^n (\hat{N} \cdot \hat{L_i} \cdot K_d + (\hat{L} \cdot \hat{E_r})^g \cdot K_s)*C_i where  C_l is the color based on all lights from the scene.
As we said before if  L_i intersects with an element in the scene we only add to  C_l the ambient coefficient  K_a . And at the end:  C_f = C_r + C_l where  C_f is the final color on the pixel.

RT_billar.jpg

This is how the Ray Tracing should look with some reflections, shadows and different materials. The next image is a level 4 fractal that represents a snowflake made of spheres as the featured image of this post that is a level 2 fractal snowflake.

RT_snowball_4.jpg
Here is the source code: SRC