Assignment #3 - Acceleration Data Structure

This week we're building some structure and functionality to make our ray-tracing faster.  The recommended approach is the bounding volume hierarchy, which I've been thinking through the past few days.

In order to motivate this work, we were first recommended to see how bad things currently are, by making a scene with a lot of objects and using our existing code to trace it.  I took my previous assignment and added some recursive code to generate a "sphereflake", then set the recursion level to 5 and tried it out.  Here's the result, an interesting image:

And here is the timing information:

Number of geometric objects: 937
Raytraced image in 33987103 microseconds

So that's almost 34 seconds to ray-trace 937 spheres with 1 light and 3 levels of recursive light bounce allowed.  I should probably add another light to the opposite side of the scene so I can see some of those spheres better, and this will also increase the tracing time.

So there's the motivation: see how much better we can do rendering 937 spheres. If the spheres were instead triangles, I'd expect a lot more savings from a hierarchy of axis-aligned minimum bounding boxes, but hopefully I'll see some benefit anyway.

Assignment #2 - Part 2 - Vanilla Raytracer

This time we had to render a scene with a few simple geometric objects, light them with Phong lighting, have them cast shadows on each other, implement 3 reflective bounces, and come up with an optimization.

I got started by putting together a small inheritance structure so that I could take advantage of polymorphism to hit all kinds of geometric objects the same way.  Once I thought I  had this working, I could test multiple geometric objects in one scene.  Here's my first multi-object scene!

Multiple objects in one scene

After that, I moved the camera to the required position, used that information to position the image plane, then sized and positioned my first two objects, spheres.

Correctly positioned camera, image plane, and objects

Then it was time to start trying to do Phong shading.  The first step for me was getting the diffuse part working.

Got the diffuse part of Phong lighting

Then I added a Plane class to my geometric object heirarchy and added one to my scene, positioned per the instructions for the assignment.

Added the infinite plane to the scene

After adding the plane, I tried to add the specular component to the lighting, but it appeared to tear holes in the skin of my objects.

Added a specular lighting, but it's incorrect 

To make sure not to miss anything easy while I was trying to debug the specular lighting issue, I made sure I could add my final object to the scene, a triangle.  The triangle turned out to be yellow and mostly blocked by one of the spheres.

Added the triangle to the scene

As it turned out, I was adding three color components together and the sum of one or more of the components was larger than 1.0 which caused an overflow of the unsigned bytes I was converting them too.  Once I truncated my final color components to be within 0.0 - 1.0 before converting them to 0 - 255, the specular lighting mess seemed cleared up.

Specular highlights fixed

So next I added shadows to the scene.  These turned out to be very easy to implement, as they just require a distance to the light calculation along with an attempt to hit all the objects with a ray in the direction of the light.  Any hits in that direction mean the point should be in shadow with respect to that light.

With shadows added

One of the final parts of the assignment required us to implement up to three recursive bounces for each pixel/ray.  I needed to change my tracing code so that it could be recursive.  Each time I send out a ray from the camera, if I hit an object, that object should potentially be lit by two lights: the main light in the scene, along with light coming in along the reflection direction if there's an object in that direction and we haven't recursed too far (bounced too many times) already.

So below you can see the first results of this attempt at reflective bounces with the recursive depth set to 1.

With 1 reflective bounce

The problem gets worse when I allow up to 3 reflective bounces.

With 3 reflective bounces

An Optimization

To make sure I finish as much of the assignment as possible on time, I went ahead and looked into optimizations at this point.  It's late in the homework period, so I was looking for an easy win.  Adding multiple threads to render separate tiles in the image seemed like a lot of work, and so did implementing an acceleration data structure.

The book by Kevin Suffern had a nice description of using axis-aligned bounding boxes to enclose harder-to-hit objects, so I thought I'd see if it was worth putting a bounding box around the triangle.  I counted up the operations I was currently doing to hit the triangle with every ray, and also the operations required to do the bounding box test.  In the svn-controlled file "OPTIMIZATIONS.txt", I describe why I thought adding a bounding box around the triangle could make sense, then I added it to my project and timed the results, with and without it.

I did 10 runs with 3 reflective bounces as the limit, and with the bounding box test turned on and off and the results were as follows:

Average time to render the scene without bbox test:

912075 microseconds

Average time to render the scene with bbox test:

583136 microseconds

In these trials, using a bbox test around the triangle resulted in an average render time that was around 36% faster.  This wasn't as much as I expected, as you can read in my "OPTIMIZATIONS.txt" file.


If you have checked out my repository before, you can just do:

svn update

Otherwise, see this post (at the bottom) for instructions on how to check out my repository.

Also, I think I fixed the reflective bounce bug I made.  I had been looking down the reflection vector of the single point light in the scene, instead of reflecting the view vector about the normal and looking for the reflected light there.  The final image for this project is pretty cool.  This is with a recursion limit of 3 reflected bounces.

This image made my heart skip a beat or two

Assignment #2 - Raytracing a Sphere

For this project, we were supposed to keep everything very simple and just raytrace our first sphere.  To minimize the amount of work needed, I just re-used my code from the first project (the image viewer), and added one new function to raytrace a sphere into texture instead of reading the texture from a ppm file.  I also added some code to visualize the depth of each point where a ray intersects the visible side of the sphere.

I also added code to this project to allow me to save a screenshot of my raytraced image to a ppm file, complete with a comment in the header including a command-line sequence to recreate the image!  Unfortunately (or maybe not, they're big files) I can't add a ppm image to this blog entry, so I used "convert", included with ImageMagick, to make my ppm into a png.

If you're on the UNM CS network, you can check out my repository with:

svn checkout file:///nfs/student/s/switt/svnrepository 


Then change into the assignment02 directory:

cd svnrepository/cs513/assignment02/ 


Finally, view the README to see how to build (with CMake) and run:

more README.txt