Map-Tracer: The Object Map Based Ray Tracer

One of the main setbacks of ray tracing is the amount of computation time that goes into calculating collisions of rays with objects in a scene. In traditional ray tracing, each ray is checked against each object in the scene for collision. This can get very computationally expensive when the scene contains meshes with large numbers of polygons that are checked against every ray recursively.

My solution to this was to create a world consisting of a map of hierarchical uniformly subdivided space that at the lowest levels contains a mapping to objects within their bounds. This way is much more accurate than a simple bounding box approach and reduces look-up times for individual components of a mesh to log time. There is a bit extra overhead time to generate the world, but the overhead is negligible compared to the time it saves.

Implementation

To start off, I had to design classes that would make up the world. There is a main world class and several subclasses that represent a hierarchy of bounding boxes inside the world. The world has functions that allow it to populate itself with a mesh file as well as add materials and lights.

Next, I built a function that generated rays based on a image width, image height, field of view, an eye position, a focus point, and an up vector. At first I only shot one ray per pixel to speed up rendering. I then designed a collision detection system to allow the rays to detect collisions with objects in the world. This was very challenging, and I constantly had to make revisions. Eventually, I got rays tracing with normal-based colors.

Next came shadows because they represent the simplest form of recursion in tracing the rays. Once I had shadows drawing correctly, reflection came quickly afterwards.

Before moving on to refraction, I decided to add multi-sampling, soft shadows, and depth of field to the ray tracer. These were all fairly simple to implement as they just involved shooting more rays at perturbed angles.