Features

Multithreaded draw with pthreads

There are 8 threads being launched, and each asks for which pixel to process from a Job Queue system.

Multithreading on the CPU is a bit simpler than on the GPU. Each thread can share the same memory space, and recursion is allowed which is typically what a ray tracer utilizes a lot for bouncing rays. You can think of a thread as a worker, and the more execution threads you have the more workers doing your task. The first easy implementation of multithreading is to launch multiple threads at the same time, and each thread processes 1 pixel. With 8 execution threads in the draw loop, you can advance 8 pixels at a time. However, this is not the optimal solution because each thread would have to wait for each other to finish before getting new work. Thus, the throughput is not 100%, and a lot of threads would be spending most of their time idling. To remedy the problem, a Job Queue system is implemented. With this, 8 threads of execution will never stop and constantly ask for new job once they finish processing their assigned pixels. If there is no work left in the Job Queue, each thread would stop.

Morton Code Linear BVH tree

A BVH linear tree (using a contiguous memory array instead of random memory location) is also implemented as an acceleration structure to further improve rendering time. The idea is to drastically minimize the number of ray collision test against objects in the scene. Without an acceleration structure, the ray casted from the camera would have to check with every single collidable objects in the scene, and this is extremely bad for performance. If a ray is heading toward an object in a specific area of the scene, then the ray would only have to check for collision with the area hierarchy that is bounding only that region of space.

There are many schemes to partition the scene area to different hierarchies, a.k.a BVH tree nodes. The scheme I have chosen is to split the area based on the Morton encoding of the centroid of each object’s bounding volume. This scheme is great for parallelization because building a hierarchy typically uses a branchy approach (such as Surface Area Heuristic), and this method converts the partitioning problem to a sorting problem, which is relatively less branchy. After the Morton codes are sorted, codes that are close to each other can be grouped to form BVH nodes, and codes that are inside each node, again, can be grouped into smaller nodes.

After the tree is built, it also gets flatten to an array. The easy implementation of a binary tree, like our BVH tree, is to just dynamically allocate random chunks of memory; this is terrible for cache locality, and since our tree is going to be traversed a lot (many rays casted from the camera and also bouncing rays from different materials), it is worth the time to use a contiguous memory to represent our tree.

Due to time constraint, this feature in the current state does not play well with transformations, so if there is any transformation specified in the POV-Ray file, the ray tracer would not use the BVH tree. Furthermore, the BVH tree can only support spheres and meshes.