Hi!Today I will be explaining the basics of the Ray Tracing algorithm described on my previous Ray Tracing post. Click here to read. The algorithm will be explained using pseudo code and I will be uploading and explaining the C++ code project on the next post.
Overall Algorithm (Pseudo code)
Here is a very VERY general idea of how the Ray Tracing algorithm works.
...
// For every column of the image
for (horiz_pix = 0; horiz_pix < horiz_res; horiz_pix++)
{
// For every row of the image
// For every row of the image
for (verti_pix = 0; verti_pix < verti_res; verti_pix++)
{
// Calculate color of pixel [horiz_pix][verti_pix]
// Get the window 3D point corresponding to the given pixel. Will assume Z is always 0.0
window_z = 0.0
// Xmin and Xmax are the minimum and maximum values of the "window" on the X axis
// Ymin and Ymax are the same as the line above but with the Y axis
// horiz_pix : horiz_res :: (window_x - Xmin) : (Xmax - Xmin) -> Therfore:
window_x = Xmin + (((horiz_pix + 1/2) * (Xmax - Xmin)) / horiz_res)
// I use horiz_pix + 1/2 to go through the "center" of the pixel
// verti_pix : verti_res :: (window_Y - Ymin) : (YmaY - Ymin) -> Therfore:
window_y = Ymin + (((verti_pix + 1/2) * (YmaY - Ymin)) / verti_res)
// I use verti_pix + 1/2 to go through the "center" of the pixel
//Make vector "eye - window" a unit vector. |V| = 1
direction_x = (window_x - eye_x)
direction_y = (window_y - eye_y)
direction_z = (window_z - eye_z)
direction_length = sqrt(( direction_x ^2) + ( direction_y ^2) + ( direction_z ^2))
direction_x = direction_x / direction_length
direction_y = direction_y / direction_length
direction_z= direction_z / direction_length
// Ray => ((eye_x, eye_y, eye_z), [direction_x, direction_y, direction_z])
// Find color at the end of the ray
color = get_color( eye_x, eye_y, eye_z , direction_x, direction_y, direction_z )
paint_pixel(horiz_pix, verti_pix, color)
window_z = 0.0
// Xmin and Xmax are the minimum and maximum values of the "window" on the X axis
// Ymin and Ymax are the same as the line above but with the Y axis
// horiz_pix : horiz_res :: (window_x - Xmin) : (Xmax - Xmin) -> Therfore:
window_x = Xmin + (((horiz_pix + 1/2) * (Xmax - Xmin)) / horiz_res)
// I use horiz_pix + 1/2 to go through the "center" of the pixel
// verti_pix : verti_res :: (window_Y - Ymin) : (YmaY - Ymin) -> Therfore:
window_y = Ymin + (((verti_pix + 1/2) * (YmaY - Ymin)) / verti_res)
// I use verti_pix + 1/2 to go through the "center" of the pixel
//Make vector "eye - window" a unit vector. |V| = 1
direction_x = (window_x - eye_x)
direction_y = (window_y - eye_y)
direction_z = (window_z - eye_z)
direction_length = sqrt(( direction_x ^2) + ( direction_y ^2) + ( direction_z ^2))
direction_x = direction_x / direction_length
direction_y = direction_y / direction_length
direction_z= direction_z / direction_length
// Ray => ((eye_x, eye_y, eye_z), [direction_x, direction_y, direction_z])
// Find color at the end of the ray
color = get_color( eye_x, eye_y, eye_z , direction_x, direction_y, direction_z )
paint_pixel(horiz_pix, verti_pix, color)
}}
So what do we have here? We will be throwing a ray that emerges from the eye and passes right through each of the pixels that conform the image with a resolution of horiz_res X verti_res. To do this we map each of the pixels to a 3D point on the scene space that is contained on the window through which the scene objects are seen. This point will be defined by window_x, window_y and window_z, from now on called "window point". To map each pixel we also need to define where is the window that leads to the scene. The window is defined by [Xmin, Ymin] and [Xmax, Ymax]; we will suppose that the window will always remain with a value of 0.0 for the Z axis. Then we calculate the vector that leads from the eye to the window point, from now on called "direction vector", and normalize it (so that is has a length of 1, also called a unit vector). Finally we got ourselves a ray with the eye as the anchor and the direction vector as the ray's direction. We calculate the color of the scene for the ray and paint the image pixel with that color. Pretty easy don't you think?
What does get_color function has inside? Well, it is something like this:
//Get the RGB color of a ray that goes through a pixel
get_color( eye_x, eye_y, eye_z , direction_x, direction_y, direction_z ) returns RgbColor[]
{
RgbColor[] color_list = []
Intersection[] object_list
// Get objects with which the ray has an intersection
object_list = get_intersections( eye_x, eye_y, eye_z , direction_x, direction_y, direction_z );
if object_list is empty
// If there wasn't any intersection at all then we return a background color.
color_list.append(background_color)
else
// Else we return the color of the first object with which there was an intersection.
color_list.append(intersection[0].object.color)
return color_list
}
I think the code above explains itself pretty well, so let's continue with the first_intersection function:
//Obtains a list of intersecting objects of a ray
get_intersections( eye_x, eye_y, eye_z , direction_x, direction_y, direction_z ) returns Intersection[]
{
Intersection[] inter_list = []
...
For Each scene_obj In scene_objects
{
new_inter = scene_obj.calculate_intersection(eye_x, eye_y, eye_z , direction_x, direction_y, direction_z )
If new_inter exists
{
inter_list.append(new_inter)
}
}
// We sort the intersections according to their distance. Intersections with smaller distances from the eye should be put first on the intersection list.
inter_list.sort()
return inter_list
}
The function above calculates all the intersections of the ray given as a parameter. For each of the objects on the scene, an intersection between the ray and the scene is calculated. If no intersection exists the object is ignored, otherwise it is put on a list. After all the scene objects are checked, the list is sorted in distance ascending order between the objects and the ray's anchor.
Some details are missing on the three pseudo code functions described above, but the general idea of the Ray Tracing algorithm remains. I will be inserting new pieces of code in there as the project advances. On the next post I will be translating this pseudo code to C++ language and describing how to calculate intersections between a ray and a sphere. Hope you enjoy!
Best regards,
Carlos Fernandez
