The Mystery of the Window into the World

This week saw the due date for what I'm calling "the worst graphics assignment ever." I saw some of the weirdest renders in this assignment. The first mistakes I made were little ones, but they had some very artistic effects. Later, I had one of the most mysterious problems I've ever encountered.

I'll start the story from the beginning: The project was to create a KD Tree from a triangle-based scene using Surface Area Heuristics to choose the best dividing planes. Then, using my KD Tree, I was to render the scene using ray casting (non-recursive ray tracing). And after that, add phong lighting. What could go wrong, right?

I decided to approach the assignment by ignoring the KD Tree altogether. I attempted ray casting by testing ray intersection against every triangle in the scene. Very, very slow, but at least I could isolate problems more easily.

The first render looked like a pre-school paint smear. After realizing that I was performing an integer division when getting my aspect ratio, I got a slightly more intelligible paint smear. The left side of the picture looked correct, but the right half looked like my program just stopped trying. Then, I considered the merits of resetting my color between casting rays, and got what must be the cheapest version of shadow casting I've ever implemented:

(Quick, tell the NPR graphics guys! I got comic book shading!)

Finally, I thought of also resetting my minimum time of intersection between casting rays. I rendered and waited extremely patiently for the picture to form. It looked correct! The slow speed of ray casting without a KD Tree was getting to me, though, so I decided to cast a ray for only every other pixel to speed it up. So, I got the newsprint version:

Then, I implemented my KD Tree. I waited with bated breath as it built the tree and rendered. I was sure it was going to draw something like a sparse spattering of random triangles... But it didn't! It looked perfect. Except for the fact that it only rendered a cube-shaped portion of my scene:

Excuse me, but huh? I moved the camera around, and the rendered cube moved with it, almost like I had a three-dimensional cube-shaped "window" into the world of my scene. Amazing. After I showed everybody I could find, I sat back down to figure it out. Was I miscalculating the area I should be ray casting over? No. Was my Axis-aligned bounding box (AABB) for the whole scene too small? No. I asked other classmates if they had any ideas. No. I asked Seniors if they had any ideas. They thought it was cool, but they were as puzzled as I was.

Finally, I e-mailed my teacher for a consult. He commented out some functions to isolate the problem. (Why didn't I think of that? Oh well, next time.) It turned out the scene rendered completely correctly if I skipped the function that clips the rays against the AABB's. I looked over my algorithm and couldn't find anything wrong with it, so I scrapped the function and wrote it over again using a similar but slightly simpler algorithm, so I would be able to find problems more easily. And then, of course, because the graphics gods are fickle, it worked:

Here is the ray clipping algorithm for those who are curious:

So, I never did truly find out the answer to the Mystery of the Window into the World. If anyone has any ideas I haven't thought of, I would be all ears!