Advanced Computer Graphics Webpage

This is the website for my semester long project in advanced computer graphics . For this class, I have chosen to take the raytracer I coded back in the first semester of computer graphics, and see how I can speed it up.

Introduction to the Project

Ok, first of all, you are probably asking, what exactly is a raytracer? Well, a raytracer is a program that renders graphics by shooting a ray at each pixel on the screen, and seeing what object that ray hits. There are a variety of techniques for how this is done, and beyond the scope of this website to explain (for an introduction to raytracing, go here).Using raytracing to render scenes tends to result in very realistic images. And, it is easy to, via raytracing, add things like shadows, reflection, refraction, and so on.

However, raytracting has one major problem. It is slow. Usually scenes with raytracers are not done real-time except for with scenes with very few objects. There are attempts in progress to speed up raytracing (for one extensive attempt at this, go here ). The major slowdown with a raytracer is that for each pixel, you have to check the ray against every single object on the screen to see if it intersects or not. Obviously, this can take a long time to do when there are a lot of objects.

For an attempt to speed this up, I intend to use Billboard Clouds. Billboard Clouds take a complex object, and cast the 'important' triangles onto a select numebr of planes. This reduces the numebr of objects you have to check for intersection with per pixel from 3000+ triangles down to 100 - 200 planes. This should significantly speed up the rendering time of the scenes in the raytracer

Results

Feburary 23rd, 2006:

So far I have re-written the old raytracing code done last semester so that it is easier to follow. Currently it supports shadows, up to 8 planes or spheres (but can go to 100 if you change one line of code), 1 light source, and reflective surfaces. Plan is to add refraction and support for complex objects next.

  • To get the code for a basic raytracer: raytracer.c This is set to compile under Visual Studio 6, but should run under any C compiler with some changes (specifically, the time checking code is Windows dependent). Also please note it is not fully optimized yet. For the fully optimized code, you will have to wait until May.
    Note there are a few bugs in the above code, those are left in so that no one can use this code (well at least) for a class. They can be fixed in 10 minutes if you know where they are though.
  • Results: Right now it will render the scene that I coded into it at about 1 frame every 2 - 3 seconds.
  • Special Notes: You can change the eye view in x and y by the WASD keys, and Z and X will increase (respectively decrease) the z axis value by 1. There is nothing stopping you from going through objects, so have fun!
  • Also note that the eye position is fixed at (0, 0, 0), so it may feel odd how the scene shifts. I intend to soon add the ability to change the lookat point too.

    March 1st, 2006:

    I added refraction back to the code, and the speed dropped down to one frame every 4 - 5 seconds. Once I figure out how to upload the exe file from windows to linux I will post here a run-time file to play with.

    April 4th, 2006:
    Ok, so a little later than I planned for the next update. Been having some problems getting the pictures here, and my system will not let me transfer the .exe file as of this moment, so those will come when I figure out how to get around that.

  • Progress so far: So far I have implimented texture mapping to spheres, triangles can be easily added with 3 lines of code or so. Been having trouble with plans though, but decided to leave that alone for a while until the clouds are up and running.
  • I changed the color code for refraction so the refractive object's color now contributes to the final color. This allows for effects like looking through a blue diamond for instance. I did not go as far as to do Beer's law perfectly, as the lenght of my refractive objects are small, I did not feel it necessary at this time.
  • I upped the total number of objects to 500, and have added support for triangles and quads to the raytracer (boxes coming soon!).
  • I also added and have working support for one .obj model, centered at (0,0 0). I will allow for placing it somewhere else shortly, as well as more .obj models

  • Performance notes: Ok, this gets interesting. When I upped it to 500 objects, my runtime tripled, even if those objects were not used. This showed me that the inner for loop was a problem. A check to make sure the objects are not NULL got rid of this problem
  • I learned that refraction is really slow on this raytracer. The higher the refractive index, the slower it runs. I tested this with a diamond refractive plane covering the entire scene (ri = 2.417), and the runtime also tripled. However, as this is due to it spawning many rays, I am not sure this can be fixed.
  • Triangle intersection really slows things down: I had the scene with 480 tirangles, 20 other objects, and it took ~1715 seconds to run. However, using the code for fast triangle intersection which eliminates the coverting it to a plane and back got that time down to ~300 seconds.
  • Complex .obj files are a slowdown: A scene rending a f-16 (4400+ triangles) with some planes in the background (not the type with wings) took almost 2 hours! Some of this was due to the fact I have it print out current (x, y) coord in the loop so I know it is still working. Taking it out should half the time
  • What does all this show? It shows the billboard clouds are desperately needed. Billboard clouds should take that object of 4400+ triangles and knock it down to ~100 quads (200 triangles). Based on these results, I expect that will cut run-time from ~2 hours to maybe 5 minutes.
  • Pictures: Coming soon, as soon as I get them to successfuly transfer off of my computer.

    April 28th, 2006:
    Ok, so I am a little behind updating this site. There has been lots of progress on the program since the last update
  • First of all, I tested the code with more complex objects. Here were some of the run times based on the program as of 4/4/06:
  • ~20 spheres and planes, f-16 object (4400 triangles): Run time ~2 hours
  • ~2 planes, dragon (1000 triangles): Run time ~3 hours
  • -2 planes, dragon (871000 triangles): Run time ~14 hours (49394 seconds to be exact).

  • So, I tried to speed up the run times on the objects. The first attempt was to put 1 bounding box around the objects. If the ray did not hit the box, it did not test the other triangles for intersection. This cut the runtime down significantly. Here are some of the results:
  • ~20 spheres and planes, f-16: Run time ~3 minutes
  • Same, but with the 10K triangle dragon: Run time ~6.5 minutes
  • New scene: 5 spheres (2 of them refractive), f-16 and dragon models: ~11 minutes (about 670 seconds).

  • Next, I implemented a bounding volume hierarchy on the scene to see how that cut time down. A bounding volume hierarchy takes every object and puts boxes around them in a binary tree form. Note this puts a box on every triangle in the complex objects. This should significantly speed up run-time. Results:
  • 5 spheres: 0 - 3 seconds. So that is getting close to realtime.
  • 5 spheres, f-16 and dragon object (14400 triangles combined): 14 - 17 seconds. Needless to say that is a nice improvement on 11 minutes.

  • I also got texture mapping working for planes. It maps the texture based on screenspace though. So this means the texture does not move as the eye moves. Can give interesting results if you look at the plane at an odd angle.
  • I implemented the phong model for shading completely now into the program. It accounts for ambient and specular colors, as well as a shininess component. Gives better results than the last implementation.
  • Billboard clouds are all I have left to implement unless a new idea comes to mind on how to speed this up. Results pending on that.

    Final update: May 13th, 2006:
  • Well, I got the billboard clouds up, sort of. Speed gain was about 9 seconds, but the image quality was terrible unless I use a small epsilon for distance from the planes. However, if I go too small, each billboard is covering basically one triangle!
  • The main problem I had with billboard clouds was implemention. Further details can be found in my final paper for this project. Also, there is a lot of self-shadowing where there should be none, so that bug needs to be fixed before usign this to speed up a raytracer. However, I could not find a fix
  • Link to the final paper (with all the details): Final Paper
  • Links to the 6 pictures
  • Picture 1. This is of the scene with everything behind a refractive plane (refraction index = 1.333)
  • Picture 2. This picture is a less crowded scene, and shows off the texture mapping. Also it shows you a refractive object within a refractive object (see the sphere to the right).
  • Picture 3. This is the same scene as above, but without the dragon. Render time is 21 seconds. Included for comparsion against the next 3 pictures.
  • Picture 4. This is the same scene, with the first attempt at billboard clouds. Notice it looks more like a bowl than a teapot. This was done with epsilion < .05, which apparantely is too high. Scene did render in 10 seconds now (so 11 seconds faster than before), but the image quality is way too poor to use
  • Picture 5. This is the same scene, with a smaller epsilon. It sort-of looks like a teapot now. It took 24 minutes to generate those clouds, and the scene did render in 12 seconds.
  • Picture 6. This was done with a really small epsilon. It generated > 2500 clouds for the teapot (which is 6300+ triangles), and took over an hour to generate those clouds. It now looks a lot like a teapot, but the sprout and handle are black and not the correct color. This is odd as shadows were turned off for this scene, so there should be no shaodws whatsoever. The cause of this bug is unknown, and further investigation is needed to fix this. Also, you will notice blurriness at the bottom of the teapot. That could be due to the curvature of the teapot there.