Introduction
As a graphics programmer, I felt that this was really missing from my portfolio. The goal of this project was to build a simple ray tracer that could be ported to CUDA, eventually. In order to keep my iteration times in a decent range, some optimizations would have to be done during development. These optimizations will include BVH construction, multithreading, and storing data in a cache friendly way.There were some optimizations to consider that would pre-calculate data. However, GPUs do not benefit from reading pre-calculated data at all. Due to this fact, I have decided to not do these optimizations.
The first thing I will talk about is the ray tracing algorithm itself. It is a straightforward algorithm without many caveats. Secondly, I will briefly discuss multithreading, and finally, I will talk about my BVH implementation.
Download Build: raytracer_build.7z
Download Source: raytracer_project.7z
Whitted-style Ray Tracing
This algorithm was described by Turner Whitted and is therefore given his name. He wrote his paper in 1980 where he proposed ray tracing to simulate complex refractions and reflections.Turner’s proposal looks something like the following pseudo code:
for(each Pixel in Viewport) { //create a primary ray Ray primaryRay = GeneratePrimaryRay(Pixel.x, Pixel.y); renderTarget[x][y] = Trace(primaryRay); } Color Trace(Ray ray) { Intersection out_primaryIntersection; if(IntersectScene(primaryRay, out_primaryIntersection)) {//find closest intersection //for diffuse materials we calculate direct illumination if(out_intersection.materialType == DIFFUSE) { Color final; for(each Light in Scene) { Ray shadowRay = GenerateShadowRay(Light); Intersection out_shadowIntersection; if(!IntersectScene(shadowRay, out_shadowIntersection)) {//no intersections means the point is directly illuminated final += (Light.color * out_primaryIntersection.color); } } return final; } //for glass we recursively trace 2 new rays else if(out_intersection.materialType == GLASS) { //use dielectric laws to calculate coefficients and new rays Ray refractiveRay = GenerateRefractiveRay(refractiveIndex); Ray reflectiveRay = GenerateReflectiveRay(refractiveIndex); //recursion if(!TotalInternalReflection) return Trace(refractiveRay) + Trace(reflectiveRay); else return BLACK; } } //no intersection, intersect skybox }For every pixel in the render target we generate a Ray, we find the closest primitive for that ray, and test for direct illumination if the intersected primitive is diffuse/opaque. If the intersected primitive is made of glass we recursively trace two new rays for the refracted and reflected light.
Multithreading
Multithreading the Whitted style ray tracing algorithm is ridiculously easy. There is no communication required between the threads whatsoever. One would simply generate a buffer with rays and have worker threads fetch rays from this buffer to trace, writing the results to the corresponding pixels in the back buffer. This setup follows a simple supplier/consumer pattern. The main thread will stall until the worker threads have finished processing all the threads in the queue.
Local Space Intersections
The most common way of testing triangle-ray intersections would be to generate the ray in world space, transform the vertices of the triangle to world space and test for intersection. I, however, decided to do my intersections in local space. This has multiple benefits. First, instead of having to transform every vertex in our mesh to world space (4 dot products per vertex), we only have to transform our ray to local space once. This saves us a lot of calculations. Secondly, when we add BVHs to our tracer, we can generate the BVH nodes in local space as Axis Aligned Bounding Boxes and do cheap intersections tests with them. There is no need to transform the BVH nodes AABBs to world space. Allowing us to not need to recalculate our BVH when we transform our meshes.We do have to take care; the local spaces of two seperate objects are not guaranteed to be linearly comparable. Scaling causes the units in local spaces to be different. Therefore, when we do find an intersection with a mesh we have to transform the intersection data back into world space before comparing it with the intersection data of other meshes.