This is a project that I made for CS 488 – Introduction to Computer Graphics. I achieved the Silver medal for my project. It isn’t visually spectacular, but the research papers that I implemented were challenging enough to balance that out.
For assignment 1, I rendered a Tetris game using OpenGL. For assignment 4, I made a basic raytracer. For the project, I decided to make the raytracer interactive, and to demonstrate this, I ported the Tetris game into the raytracer.
I did three main things to speed up the raytracer, making it interactive:
- I multi-threaded the raytracer.
- I implemented a Bounding Interval Hierarchy (BIH).
- I arranged individual rays into ray “packets”.
The multi-threading was implemented by assigning ray packets to threads, so multiple packets could be traced at once.
A BIH is a sort of hybrid spacial partitioning tree. It is constructed in a similar manner to a kd-tree, but when traversing it, it behaves more like a Bounding Volume Hierarchy. More about this data structure can be found in “Instant Ray Tracing: The Bounding Interval Hierarchy”, written by Carsten Wächter and Alexander Keller.
The main idea behind packet tracing is to group rays together into packets to reduce the amount of time spent traversing the BIH. There are two ways this method saves time. First, the algorithm checks if the first ray in the packet intersects the cell in the BIH, then recurses if it does. The standard ray packet for my program had 16 rays, so this saves 15 intersection checks. Next, using interval arithmetic, the algorithm checks if all of the rays miss the cell. If they do, then we are done and the algorithm has avoided 15 intersection checks again. If both of those steps fail, then the algorithm resorts to checking each ray one at a time. See more about this in “Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies”, written by Wald, Boulos, and Shirley.
Those three methods resulted in enough of a speed-up for my Tetris game to be playable.
I also implemented several basic raytracer essentials, because otherwise I might as well had used OpenGL. They were as follows:
Reflection
Refraction
Anti-aliasing
Linear key frame interpolation
Texture mapping
Bump mapping
Now that you have read this far (or at least scrolled this far), here are some videos:
The point of the above video is to demonstrate the various speeds of the game and linear key frame interpolation. There is also bump mapping on the blocks and texture mapping on the border.
Now, here is the full scene.
Unless you were paying careful attention, you may wonder why I just paused the game and let it sit there at the end of the video. I was demonstrating anti-aliasing. A few seconds after the pause, at the very end of the video, the scene switches from 1 sample per pixel to 9. You really notice it if you watch the edges of the border.
You probably noticed that the game didn’t really run that smoothly. This is because the screen recording software I was using caused the game to slow down a lot.
It has been pointed out to me that a translucent border should not cast such a dark shadow, but I had a limited time to complete this project and I was just focusing on completing all the objectives in time.
The code for this project can be found here: https://github.com/svanleeuwen/CS488/tree/main/Final_Project
